Projetando sistemas de negociação de baixa latência

Projetando sistemas de negociação de baixa latência
Obter através da App Store Leia esta publicação em nosso aplicativo!
Qual é o princípio da baixa latência na aplicação comercial?
Parece que todos os principais bancos de investimento usam o C ++ no Unix (Linux, Solaris) para suas aplicações de servidor de baixa latência / alta freqüência. Como as pessoas conseguem baixa latência na negociação de equidade de alta freqüência? Qualquer livro ensina como conseguir isso?
Verifique esses sites que você pode ter alguma idéia sobre a programação de baixa latência.
mas esteja ciente de que alguns códigos podem não ser padronizados. O que significa que não será por mais tempo.

11 Práticas recomendadas para sistemas de baixa latência.
Foram 8 anos desde que o Google notou que um extra de 500ms de latência caiu o tráfego em 20% e a Amazon percebeu que 100ms de latência extra caíram as vendas em 1%. Desde então, os desenvolvedores estiveram correndo para o fundo da curva de latência, culminando em desenvolvedores de front-end espremendo todos os últimos milésimos de segundo de seu JavaScript, CSS e HTML. O que se segue é uma caminhada aleatória através de uma variedade de práticas recomendadas para ter em mente ao projetar sistemas de baixa latência. A maioria dessas sugestões são levadas ao extremo lógico, mas é claro que podem ser feitas compensações. (Obrigado a um usuário anônimo por fazer esta pergunta no Quora e me fazer colocar meus pensamentos por escrito).
Escolha o idioma certo.
As linguagens de script não precisam se aplicar. Embora eles continuem ficando cada vez mais rápidos, quando você está olhando para raspar os últimos milissegundos do seu tempo de processamento, você não pode ter a sobrecarga de um idioma interpretado. Além disso, você vai querer um modelo de memória forte para habilitar a programação sem bloqueio para que você esteja olhando Java, Scala, C ++ 11 ou Go.
Mantenha tudo na memória.
I / O irá matar sua latência, portanto, certifique-se de que todos os seus dados estão na memória. Isso geralmente significa gerenciar suas próprias estruturas de dados em memória e manter um registro persistente, para que você possa reconstruir o estado após uma reinicialização de máquina ou processo. Algumas opções para um registro persistente incluem Bitcask, Krati, LevelDB e BDB-JE. Alternativamente, você pode fugir com a execução de um banco de dados local, persistente na memória, como redis ou MongoDB (com dados da memória & gt; & gt;). Observe que você pode perder alguns dados sobre falhas devido à sua sincronização de fundo no disco.
Mantenha dados e processamento colocados.
O lúpulo de rede é mais rápido do que o disco, mas mesmo assim eles vão adicionar muitas despesas gerais. Idealmente, seus dados devem caber inteiramente na memória em um host. Com a AWS fornecendo quase 1/4 TB de RAM na nuvem e servidores físicos que oferecem múltiplas TBs, isso geralmente é possível. Se você precisa executar em mais de um host, você deve garantir que seus dados e solicitações sejam adequadamente particionados para que todos os dados necessários para atender uma determinada solicitação estejam disponíveis localmente.
Mantenha o sistema subutilizado.
A baixa latência requer sempre recursos para processar a solicitação. Não tente executar no limite do que seu hardware / software pode fornecer. Sempre tem muita sala de cabeça para rajadas e depois algumas.
Mantenha os parâmetros de contexto ao mínimo.
Os switches de contexto são um sinal de que você está fazendo mais trabalho de computação do que você tem recursos. Você quer limitar seu número de segmentos ao número de núcleos em seu sistema e colocar cada segmento no seu núcleo.
Mantenha suas leituras seqüenciais.
Todas as formas de armazenamento, murchar é rotacional, com base em flash ou memória, melhoram significativamente quando usado sequencialmente. Ao emitir leituras seqüenciais para a memória, você desencadeia o uso da pré-busca no nível de RAM, bem como no nível de cache da CPU. Se for feito corretamente, a próxima peça de dados que você precisa estará sempre em cache L1 antes de precisar. A maneira mais fácil de ajudar esse processo é fazer uso intenso de matrizes de tipos ou tipos de dados primitivos. Os ponteiros a seguir, seja através do uso de listas vinculadas ou através de matrizes de objetos, devem ser evitados a todo custo.
Lote suas escritas.
Isso parece contraintuitivo, mas você pode obter melhorias significativas no desempenho através de gravações por lotes. No entanto, existe um equívoco de que isso significa que o sistema deve aguardar uma quantidade arbitrária de tempo antes de escrever. Em vez disso, um segmento deve girar em um loop apertado fazendo I / O. Cada escrita irá lote todos os dados que chegaram desde a última gravação emitida. Isso faz com que um sistema muito rápido e adaptável.
Respeite seu cache.
Com todas essas otimizações no local, o acesso à memória rapidamente se torna um gargalo. Fixar threads para seus próprios núcleos ajuda a reduzir a poluição do cache da CPU e as E / S seqüenciais também ajudam a pré-carregar o cache. Além disso, você deve manter os tamanhos de memória para baixo usando tipos de dados primitivos para que mais dados se encaixem no cache. Além disso, você pode procurar algoritmos cache-inconscientes que funcionam recursivamente, quebrando os dados até que ele se encaixe no cache e depois faça qualquer processamento necessário.
Não bloqueando o máximo possível.
Faça com que os amigos não bloqueiem e aguardem estruturas e algoritmos de dados gratuitos. Toda vez que você usa um bloqueio, você precisa baixar a pilha para o sistema operacional para mediar o bloqueio, que é uma enorme sobrecarga. Muitas vezes, se você sabe o que está fazendo, você pode contornar os bloqueios através da compreensão do modelo de memória da JVM, C ++ 11 ou Go.
Async, tanto quanto possível.
Qualquer processamento e particularmente qualquer E / S que não seja absolutamente necessário para a construção da resposta deve ser feito fora do caminho crítico.
Paralelize o máximo possível.
Qualquer processamento e particularmente qualquer E / S que possa acontecer em paralelo deve ser feito em paralelo. Por exemplo, se sua estratégia de alta disponibilidade inclui o log de transações para o disco e o envio de transações para um servidor secundário, essas ações podem acontecer em paralelo.
Quase tudo isso vem de seguir o que o LMAX está fazendo com seu projeto Disruptor. Leia sobre isso e siga tudo o que Martin Thompson faz.
Compartilhar isso:
Relacionados.
Publicado por.
Benjamin Darfler.
29 pensamentos sobre & ldquo; 11 melhores práticas para sistemas de baixa latência & rdquo;
E feliz em estar na sua lista 🙂
Bom artigo. One beef: Go doesn & # 8217; t tem um modelo de memória sofisticado como Java ou C ++ 11. Se o seu sistema se encaixa com a rotina da rotina e a arquitetura dos canais, é bom demais, sem sorte. O AFAIK não é possível excluir o agendador de tempo de execução, portanto, não há falhas de sistema operacional nativas e a capacidade de criar suas próprias estruturas de dados livres de bloqueio como (colunas SPSC / anejadores) também faltam severamente.
Obrigado pela resposta. Embora o modelo de memória Go (golang / ref / mem) possa não ser tão robusto quanto o Java ou o C ++ 11, tive a impressão de que você ainda poderia criar estruturas de dados sem bloqueio usando isso. Por exemplo, github / textnode / gringo, github / scryner / lfreequeue e github / mocchira / golfhash. Talvez eu estivesse faltando alguma coisa? É certo que eu sei muito menos sobre o Go do que a JVM.
Benjamin, o modelo de memória Go detalhado aqui: golang / ref / mem é principalmente em termos de canais e mutexes. Eu olhei através dos pacotes que você listou e enquanto as estruturas de dados existem & # 8220; lock free & # 8221; eles não são equivalentes ao que um pode construir em Java / C ++ 11. O pacote de sincronização a partir de agora, não tem suporte para átomos relaxados ou a semântica de aquisição / lançamento do C ++ 11. Sem esse suporte, é difícil construir estruturas de dados SPSC tão eficientes quanto as possíveis em C ++ / Java. Os projetos que você liga usam atomic. Add & # 8230; que é um átomo consistente consecutivamente. Ele é construído com XADD como deveria ser # 8211; github / tonnerre / golang / blob / master / src / pkg / sync / atomic / asm_amd64.s.
Eu não estou tentando derrubar Ir para baixo. É preciso um esforço mínimo para escrever IO assíncrono e concorrente.
código suficientemente rápido para a maioria das pessoas. A biblioteca std também está altamente ajustada para o desempenho. A Golang também tem suporte para estruturas que estão faltando em Java. Mas, como está, penso que o modelo de memória simplista e o tempo de execução da rotina estão no caminho da construção do tipo de sistemas de que você está falando.
Obrigado pela resposta em profundidade. Espero que as pessoas achem isso útil.
Enquanto um & # 8216; native & # 8217; O idioma provavelmente é melhor, não é estritamente necessário. O Facebook nos mostrou que pode ser feito em PHP. Concedido eles usam o PHP pré-compilado com sua máquina HHVM. Mas é possível!
Infelizmente, o PHP ainda não possui um modelo de memória aceitável, mesmo que o HHVM melhore significativamente a velocidade de execução.
Enquanto eu lutarei para usar linguagens de nível superior, tanto quanto o próximo cara, acho que a única maneira de alcançar os aplicativos de baixa latência que as pessoas estão procurando é deslizar para um idioma como C. Parece que a mais difícil é escrever em um idioma, mais rápido ele executa.
Eu recomendo que você olhe para o trabalho que está sendo feito nos projetos e blogs aos quais eu liguei. A JVM está rapidamente se tornando o ponto quente para esses tipos de sistemas porque fornece um modelo de memória forte e uma coleta de lixo que permitem a programação sem bloqueio quase impossivel com um modelo de memória fraco ou indefinido e contadores de referência para gerenciamento de memória.
Olharei, Benjamin. Obrigado por apontá-los.
A coleta de lixo para programação sem bloqueio é um pouco de um deus ex machina. As filas MPMC e SPSC podem ser criadas sem necessidade de GC. Há também muitas maneiras de fazer programação sem bloqueio sem coleta de lixo e a contagem de referências não é a única maneira. Os ponteiros de perigo, RCU, Proxy-Collectors, etc, fornecem suporte para recuperação diferida e geralmente são codificados em suporte de um algoritmo (não genérico), portanto, eles geralmente são muito mais fáceis de construir. É claro que o trade-off reside no fato de que os GCs de qualidade de produção têm muito trabalho colocado neles e ajudarão o programador menos experiente a escrever algoritmos sem bloqueio (eles deveriam estar fazendo isso?) Sem codificação de esquemas de recuperação diferida . Alguns links sobre o trabalho realizado neste campo: cs. toronto. edu/
Sim C / C ++ recentemente ganhou um modelo de memória, mas isso não significa que eles eram completamente inadequados para o código sem bloqueio anteriormente. O GCC e outros compiladores de alta qualidade tinham diretrizes específicas do compilador para fazer programação gratuita de bloqueio em plataformas suportadas por um tempo realmente grande # 8211; não era padronizado na língua. Linux e outras plataformas forneceram essas primitivas por algum tempo também. A posição única de Java foi que forneceu um modelo de memória formalizado que garantiu trabalhar em todas as plataformas suportadas. Embora, em princípio, isso seja incrível, a maioria dos desenvolvedores do lado do servidor trabalham em uma plataforma (Linux / Windows). Eles já tinham as ferramentas para criar código sem bloqueio para sua plataforma.
GC é uma ótima ferramenta, mas não é necessária. Tem um custo tanto em termos de desempenho como em complexidade (todos os truques necessários para evitar STW GC). C ++ 11 / C11 já possui suporte para modelos de memória adequados. Não vamos esquecer que as JVMs não têm responsabilidade em suportar a API insegura no futuro. O código inseguro é & # 8220; unsafe & # 8221; então você perde os benefícios das características de segurança da Java. Finalmente, o código inseguro usado para criar memória e simular estruturas em Java parece muito mais feio do que as estruturas C / C ++ onde o compilador está fazendo isso funciona de maneira confiável. C e C ++ também fornecem acesso a todas as ferramentas elétricas específicas de plataforma de baixo nível, como PAUSE ins, SSE / AVX / NEON etc. Você pode até ajustar seu layout de código através de scripts de linker! O poder fornecido pela cadeia de ferramentas C / C ++ é realmente incomparável pela JVM. O Java é uma ótima plataforma, no entanto, acho que a maior vantagem é que a lógica comercial comum (90% do seu código?) Ainda pode depender do GC e dos recursos de segurança e fazer uso de bibliotecas altamente sintonizadas e testadas escritas com inseguro. Este é um grande trade-off entre obter os últimos 5% de perf e ser produtivo. Um trade-off que faz sentido para muitas pessoas, mas um trade-off, no entanto. Escrever um código de aplicação complicado em C / C ++ é um pesadelo depois de tudo.
No dia 10 de março de 2017 às 12:52, CodeDependents escreveu:
& gt; Graham Swan comentou: "Tenho uma olhada, Benjamin. Obrigado por & gt; apontando para fora. & # 8221;
Falta o 12: Não use linguagens coletadas Garbadge. GC é um gargalo na piora. Provavelmente, interrompe todos os tópicos. É um global. Isso distrai o arquiteto para gerenciar um dos recursos mais craterais (CPU-near memory).
Na verdade, muito deste trabalho vem diretamente de Java. Para fazer uma programação livre de bloqueio, você precisa de um modelo de memória claro, que c ++ recentemente ganhou recentemente. Se você sabe trabalhar com GC e não contra isso, você pode criar sistemas de baixa latência com muita facilidade.
Eu tenho que concordar com Ben aqui. Houve muitos progressos no paralelismo do GC na última década, ou seja, com o coletor G1 sendo o incantation mais recente. Pode levar um pouco de tempo para sintonizar o heap e vários botões para obter o GC para coletar com quase nenhuma pausa, mas isso contrasta em comparação com o tempo de desenvolvimento necessário para não ter GC.
Você pode até dar um passo adiante e criar sistemas que produzem tão pouco lixo que você pode facilmente empurrar o seu GC fora da sua janela de operação. É assim que todas as lojas comerciais de alta freqüência o fazem quando são executados na JVM.
A coleta de lixo para programação sem bloqueio é um pouco de um deus ex machina. As filas MPMC e SPSC podem ser criadas sem necessidade de GC. Há também muitas maneiras de fazer programação sem bloqueio sem coleta de lixo e a contagem de referências não é a única maneira. Os ponteiros de perigo, RCU, Proxy-Collectors, etc, fornecem suporte para recuperação diferida e são codificados em suporte de um algoritmo (não genérico), portanto, eles são muito mais fáceis de construir. É claro que o trade-off reside no fato de que os GCs de qualidade de produção têm muito trabalho colocado neles e ajudarão o programador menos experiente a escrever algoritmos sem bloqueio (eles deveriam estar fazendo isso?) Sem codificação de esquemas de recuperação diferida . Alguns links sobre o trabalho realizado neste campo: cs. toronto. edu/
Sim C / C ++ recentemente ganhou um modelo de memória, mas isso não significa que eles eram completamente inadequados para o código sem bloqueio anteriormente. O GCC e outros compiladores de alta qualidade tinham diretrizes específicas do compilador para fazer programação gratuita de bloqueio em plataformas suportadas por um tempo realmente grande # 8211; não era padronizado na língua. Linux e outras plataformas forneceram essas primitivas por algum tempo também. A posição única de Java foi que forneceu um modelo de memória formalizado que garantiu trabalhar em todas as plataformas suportadas. Embora, em princípio, isso seja incrível, a maioria dos desenvolvedores do lado do servidor trabalham em uma plataforma (Linux / Windows). Eles já tinham as ferramentas para criar código sem bloqueio para sua plataforma.
GC é uma ótima ferramenta, mas não é necessária. Tem um custo tanto em termos de desempenho quanto em complexidade (todos os truques necessários para atrasar e evitar STW GC). C ++ 11 / C11 já possui suporte para modelos de memória adequados. Não vamos esquecer que as JVMs não têm responsabilidade em suportar a API insegura no futuro. O código inseguro é & # 8220; unsafe & # 8221; então você perde os benefícios das características de segurança da Java. Finalmente, o código inseguro usado para criar memória e simular estruturas em Java parece muito mais feio do que as estruturas C / C ++ onde o compilador está fazendo isso funciona de maneira confiável. C e C ++ também fornecem acesso a todas as ferramentas elétricas específicas de plataforma de baixo nível, como PAUSE ins, SSE / AVX / NEON etc. Você pode até ajustar seu layout de código através de scripts de linker! O poder fornecido pela cadeia de ferramentas C / C ++ é realmente incomparável pela JVM. O Java é uma ótima plataforma, no entanto, acho que a maior vantagem é que a lógica comercial comum (90% do seu código?) Ainda pode depender do GC e dos recursos de segurança e fazer uso de bibliotecas altamente sintonizadas e testadas escritas com inseguro. Este é um grande trade-off entre obter os últimos 5% de perf e ser produtivo. Um trade-off que faz sentido para muitas pessoas, mas um trade-off, no entanto. Escrever um código de aplicação complicado em C / C ++ é um pesadelo depois de tudo.
& gt; Não use linguagens coletadas garbadge.
Ou, pelo menos, & # 8220; tradicional & # 8221; Lixo coletado línguas. Porque eles são diferentes & # 8211; enquanto Erlang também tem um colecionador, não criou gargalos porque não pára o mundo & # 8217; t & # 8220; pára o mundo & # 8221; como Java, enquanto colecionava lixo e # 8211; em vez disso, interrompe os microcréditos pequenos individuais & # 8220; & # 8221; em uma escala de microssegunda, portanto, não é visível no grande.
Reescreva isso para & # 8220; tradicional & # 8221; algoritmos [i] de coleta de lixo [/ i]. Na LMAX usamos o Azul Zing, e apenas usando uma JVM diferente com uma abordagem diferente para a coleta de lixo, vimos grandes melhorias no desempenho, porque os GCs maiores e menores são ordens de magnitude mais baratas.
Existem outros custos que compensam isso, é claro: você usa um monte muito mais, e o Zing não é barato.
Reblogged this em Java Prorgram Exemplos e comentou:
Um dos artigos de leitura obrigatória para programadores Java, é a lição que você aprenderá depois de passar um tempo considerável de afinação e desenvolver sistemas de baixa latência em Java em 10 minutos.
Revivendo um tópico antigo, mas (incrivelmente) isso deve ser apontado:
1) Linguagens de nível superior (por exemplo, Java) não desejam a funcionalidade do hardware que não está disponível para idiomas de nível inferior (por exemplo, C); declarar que assim e assim é completamente impossível & # 8221; em C, facilmente acessível em Java, é um lixo completo sem reconhecer que o Java é executado em hardware virtual onde a JVM deve sintetizar a funcionalidade exigida pelo Java, mas não fornecida pelo hardware físico. Se uma JVM (por exemplo, escrita em C) pode sintetizar a funcionalidade X, então também pode um programador C.
2) & # 8220; Lock free & # 8221; não é o que as pessoas pensam, exceto quase por coincidência em certas circunstâncias, como o único núcleo x86; multicore x86 não pode ser executado sem bloqueio sem barreiras de memória, que tem complexidades e custos semelhantes ao bloqueio regular. De acordo com 1 acima, se o Lock Free funcionar em um determinado ambiente, é porque ele é suportado pelo hardware, ou emulado / sintetizado por software em um ambiente virtual.
Great Points Julius. O ponto que eu estava tentando (talvez sem sucesso) é que é proibitivamente difícil aplicar muitos desses padrões em C, pois eles dependem do GC. Isso vai além do simples uso de barreiras de memória. Você também deve considerar a liberação de memória, o que fica particularmente difícil quando você está lidando com algoritmos livres de segurança e sem espera. É aqui que o GC adiciona uma grande vitória. Dito isto, eu ouço que Rust tenha algumas idéias muito interessantes sobre a propriedade da memória que possam começar a abordar algumas dessas questões.

Projetando sistemas de negociação de baixa latência
Obter através da App Store Leia esta publicação em nosso aplicativo!
Programação de baixa latência.
Eu tenho lido muito sobre os sistemas financeiros de baixa latência (especialmente desde o famoso caso de espionagem corporativa) e a idéia de sistemas de baixa latência tem estado em mente desde então. Há um milhão de aplicativos que podem usar o que esses caras estão fazendo, então eu gostaria de aprender mais sobre o assunto. A coisa é que não consigo encontrar nada valioso sobre o assunto. Alguém pode recomendar livros, sites, exemplos de sistemas de baixa latência?
12 Respostas.
Eu trabalho para uma empresa financeira que produz software de baixa latência para comunicação diretamente com trocas (para envio de trades e preços de transmissão). Atualmente, desenvolvemos principalmente em Java. Embora o lado de baixa latência não seja uma área na qual eu trabalho diretamente, tenho uma idéia justa da qualificação exigida, o que inclui o seguinte na minha opinião:
Conhecimento detalhado do modelo e técnicas de memória Java para evitar a coleta de lixo desnecessária (por exemplo, agrupamento de objetos). Algumas das técnicas utilizadas geralmente podem ser consideradas como "anti-padrões" em um OO-ambiente tradicional. Conhecimento detalhado de multicast TCP / IP e UDP incluindo utilitários para depuração e medição de latência (por exemplo, DTrace no Solaris). Experiência em aplicações de perfil. Conhecimento do pacote java. nio, experiência no desenvolvimento de aplicativos de servidor escaláveis ​​baseados em NIO, experiência na criação de protocolos de fio. Observe também que, normalmente, evitamos o uso de estruturas e bibliotecas externas (por exemplo, o Google Protobuf), preferindo escrever muito código personalizado. Conhecimento das bibliotecas FIX e FIX comerciais (por exemplo, Cameron FIX).
Infelizmente, muitas das habilidades só podem ser desenvolvidas "no trabalho", pois não há substituto para a experiência adquirida implementando um servidor de preços ou um mecanismo comercial baseado em uma especificação. de uma troca ou vendedor. No entanto, também vale a pena mencionar que nossa empresa, pelo menos, tende a não procurar uma experiência específica nessas áreas de nicho (ou outras), preferindo contratar pessoas com boas habilidades analíticas e de resolução de problemas.
A baixa latência é uma função de muitas coisas, sendo as duas mais importantes:
latência da rede - ou seja, o tempo gasto na rede para transmitir / receber mensagens. latência de processamento - ou seja, o tempo gasto pelo seu aplicativo para atuar em uma mensagem / evento.
Então, se você diz que está escrevendo um sistema de Correspondência de Pedidos, a latência da rede representaria o quão breve dentro da sua rede você conseguiu receber o pedido de correspondência de pedidos. E a latência de processamento representaria o tempo de sua aplicação para coincidir com a Ordem contra ordens abertas existentes.
Multicast, UDP, multicast confiável, Kernel bypass (suportado por Java 7, Informatica Ultra Messaging e muitos outros) nas redes Infiniband são algumas das tecnologias comuns utilizadas por todas as empresas neste campo.
Além disso, existem estruturas de programação de baixa latência como disruptor (code. google/p/disruptor/) que implementam padrões de design para lidar com aplicativos de baixa latência. O que poderia matá-lo é ter que escrever em um banco de dados ou arquivos de log como parte do seu fluxo de trabalho principal. Você terá que encontrar soluções únicas que atendam aos requisitos do problema que você está tentando resolver.
Em linguagens como Java, implementar seu aplicativo de forma que ele cria (quase) zero lixo torna-se extremamente importante para a latência. Como diz Adamski, ter um conhecimento do modelo de memória Java é extremamente importante. Compreenda as diferentes implementações da JVM e suas limitações. Os padrões típicos de design Java em torno da criação de pequenos objetos são as primeiras coisas que você vai jogar fora da janela - um nunca pode consertar o coletor de lixo Java o suficiente para alcançar baixa latência - o único que pode ser corrigido é o lixo.
Bem, não é apenas uma programação "tradicional" em tempo real, é tudo. Eu trabalho para uma bolsa de valores - a velocidade é rei. um problema típico é qual a maneira mais rápida de escrever em um arquivo? a maneira mais rápida de serializar um objeto? etc.
Qualquer coisa na programação em tempo real caberia na conta. Não é exatamente o que você está procurando, eu suspeito, mas é um lugar extremamente bom para começar.
Há muitas boas respostas nesta publicação. Eu gostaria de adicionar minha experiência também.
Para obter baixa latência em java, você tem que assumir o controle do GC em java, existem muitas maneiras de fazer isso, por exemplo, pré-alocar objetos (ou seja, usar padrão de design de peso mosca), usar objetos primitivos - é bom para isso, todos os dados A estrutura é baseada em primitiva, Reuse a instância do objeto, por exemplo, crie o dicionário do sistema inteiro para reduzir a criação de novos objetos, muito boa opção ao ler dados de stream / socket / db.
Tente usar algo sem espera (o que é um pouco difícil), bloquear algo livre. Você pode encontrar toneladas de exemplos para isso.
Use computação em memória. A memória é barata, você pode ter tera byte de dados na memória.
Se você pode dominar bit-wise algo, então dá um desempenho muito bom.
Use simpatia mecânica - Consulte o disruptor lmax, excelente estrutura.
Leia os whitepapers nesse site e você terá uma visão do que é necessário para a baixa latência.
Se você estiver interessado em desenvolver Java de baixa latência, você deve saber que ele pode ser feito sem JVM RTSJ (em tempo real) desde que você mantenha o coletor de lixo sob controle. Eu sugiro que você dê uma olhada neste artigo que fala sobre Desenvolvimento Java sem sobrecarga CG. Também temos muitos outros artigos em nosso site que falam sobre componentes Java de baixa latência.
Gostaria de comentar sobre programação de baixa latência. Atualmente tenho mais de 5 anos de experiência no desenvolvimento de baixa latência e motores de alta execução em software financeiro.
É necessário entender o que é latência?
Latência significa que precisa de tempo para completar seu processo. Não depende necessariamente das ferramentas de desenvolvimento que você está usando, como java, c ++, etc., depende de suas habilidades de programação e sistema.
Suponha que você esteja usando java, mas um erro pode fazer um atraso no processo. Por exemplo, você desenvolveu um aplicativo comercial em que, em cada atualização de preço, você chama algumas funções e assim por diante. Isso pode resultar em variáveis ​​extras, uso de memória desnecessário, loops desnecessários que podem causar atraso no processo. O mesmo aplicativo desenvolvido pode ser melhor do que o java se o desenvolvedor se importasse com os erros acima.
Também depende do seu sistema de servidor, como o sistema multiprocessador pode funcionar bem se sua aplicação for multi-thread.
Se eu me lembro corretamente, em tempo real, Java (RTSJ) é usado nesta área, embora não consegui encontrar um artigo bom para vincular até agora.
Normalmente, trabalhar em ambientes de baixa latência significa ter uma compreensão das dependências de chamadas e como reduzi-las para minimizar a cadeia de dependência. Isso inclui o uso de estruturas de dados e bibliotecas para armazenar os dados armazenados em cache desejados, bem como refatorar recursos existentes para reduzir interdependências.

Por que baixa latência.
Clone este wiki localmente.
No mercado de alta freqüência (HFT), é quase impossível evitar o sujeito de baixa latência. O que a baixa latência significa neste contexto? A latência é uma medida de tempo para obter uma resposta para uma determinada ação. Para alcançar baixa latência, uma resposta deve ser rápida, onde é frequentemente medido em micro ou nano segundos para HFT. Os sistemas HFT devem responder oportunamente aos eventos de mercado, caso contrário, uma oportunidade de negociação é perdida na melhor das hipóteses, ou na pior das hipóteses pode significar que o algoritmo de negociação está exposto a riscos significativos à medida que atrasam o mercado.
O que o nome de baixa latência não transmite é a importância de ter latência consistente. Muitas vezes, é mais importante ser consistente do que ser rápido na maioria das vezes, mas ocasionalmente lento. Portanto, sistemas de negociação e trocas se esforçam para não apenas oferecer baixa latência, também tentam minimizar a variação. Alcançar baixa latência com variância mínima pode ser um desafio real ao lidar com tempos de resposta medidos em microssegundos, especialmente nas taxas de eventos que podem estar em muitos milhões por segundo para os maiores feeds.
Para que um sistema seja muito receptivo quando confrontado com grandes taxas de eventos, ele deve ser incrivelmente eficiente. Não há espaço para resíduos em tal sistema. Cada instrução executada deve pagar seu próprio caminho e ser puramente focada no objetivo de processar os eventos recebidos e responder de acordo. O design de tais sistemas precisa de uma abordagem de design semelhante à de aeronave ou espaçonave. O Spacecraft foi concebido para ser o mais minimalista possível com o nível adequado de características de segurança. Isso requer uma compreensão profunda do que exatamente é exigido e um foco nítido na eficiência. Nenhuma bagagem extra deve ser realizada no caminho.
Para minimizar a variação, é necessária uma pilha ou plataforma completa, de modo a que o sistema esteja sempre a amortizar o custo de operações caras e todos os algoritmos têm uma notação Big O de O (log n) ou mesmo melhor.
A variância pode ser introduzida em todas as camadas ou na pilha. Em um nível muito baixo, poderia ser SMI interromper a verificação do status de hardware ou interrupções do sistema antecipando a execução. Mais na pilha pode ser o sistema operacional ou as máquinas virtuais gerenciando a memória que está sendo agitada pelas aplicações. A diferença geralmente vem de algoritmos empregados nos próprios sistemas comerciais que atravessam estruturas de dados que podem causar falhas no cache e O (n) processamento ou pesquisa.
A abordagem de projeto adotada para o codec SBE tem os objetivos de ser o mais eficiente possível e manter a variância ao mínimo enquanto se arrisca a uma abordagem apropriada para a segurança.
&cópia de; 2017 GitHub, Inc. Termos Privacidade Segurança Status Ajuda.
Você não pode executar essa ação neste momento.
Você fez login com outra guia ou janela. Recarregue para atualizar sua sessão. Você se separou em outra guia ou janela. Recarregue para atualizar sua sessão.

Evolução e prática: aplicativos distribuídos de baixa latência em finanças.
O setor financeiro possui demandas únicas para sistemas distribuídos de baixa latência.
Andrew Brook.
Praticamente todos os sistemas têm alguns requisitos de latência, definidos aqui como o tempo necessário para que um sistema responda à entrada. (Existem cálculos de falta de interrupção, mas têm poucas aplicações práticas). Os requisitos de latência aparecem em domínios problemáticos tão diversos quanto os controles de vôo da aeronave (copter. ardupilot /), comunicações de voz (queue. acm / detail. cfm? Id = 1028895), jogos multijogantes (queue. acm / detail. cfm? id = 971591), publicidade online (acuityads / lances em tempo real /) e experiências científicas (home. web. cern. ch/about/accelerators/cern-neutrinos-gran - sasso).
Sistemas distribuídos e mdash, em que computação ocorre em vários computadores em rede que se comunicam e coordenam suas ações passando mensagens e mensagens; apresentam considerações especiais de latência. Nos últimos anos, a automação do comércio financeiro conduziu os requisitos para sistemas distribuídos com requisitos de latência desafiadores (geralmente medidos em microssegundos ou mesmo nanossegundos, ver tabela 1) e distribuição geográfica global. A negociação automatizada fornece uma janela para os desafios de engenharia dos requisitos de latência em constante encolhimento, o que pode ser útil para engenheiros de software em outros campos.
Este artigo centra-se em aplicações em que a latência (em oposição ao rendimento, eficiência ou alguma outra métrica) é uma das principais considerações de projeto. Fraseado de forma diferente, "sistemas de baixa latência" são aqueles para os quais a latência é a principal medida de sucesso e geralmente é a restrição mais difícil de projetar. O artigo apresenta exemplos de sistemas de baixa latência que ilustram os fatores externos que geram latência e, em seguida, discute algumas abordagens práticas de engenharia para construir sistemas que operam em baixa latência.
Por que todos estão com tanta pressa?
Para entender o impacto da latência em um aplicativo, é importante primeiro entender os fatores externos, do mundo real que impulsionam o requisito. Os exemplos a seguir do setor financeiro ilustram o impacto de alguns fatores do mundo real.
Solicitação de Negociação de Cotações.
Em 2003, trabalhei em um grande banco que acabava de implantar um novo sistema de comércio de moeda estrangeira institucional baseado na Web. O mecanismo de citação e comércio, um aplicativo J2EE (Java 2 Platform, Enterprise Edition) executado em um servidor WebLogic em cima de um banco de dados Oracle, teve tempos de resposta confiáveis ​​em menos de dois segundos e rápido, para garantir uma boa experiência do usuário.
Ao mesmo tempo que o site do banco entrou em operação, foi lançada uma plataforma multibanca de negociação on-line. Nesta nova plataforma, um cliente apresentaria um pedido de pedido (pedido de cotação) que seria encaminhado para vários bancos participantes. Cada banco responderia com uma cotação, e o cliente escolheria qual aceitação.
Meu banco iniciou um projeto para se conectar à nova plataforma multibanco. O raciocínio era que, uma vez que um tempo de resposta de dois segundos era bom o suficiente para um usuário no site, ele deveria ser bom o suficiente para a nova plataforma e, assim, o mesmo mecanismo de negociação e troca poderia ser reutilizado. Poucas semanas depois de viver, o banco estava ganhando uma porcentagem surpreendentemente pequena de PDOs. A causa raiz foi a latência. When two banks responded with the same price (which happened quite often), the first response was displayed at the top of the list. Most clients waited to see a few different quotes and then clicked on the one at the top of the list. The result was that the fastest bank often won the client's business—and my bank wasn't the fastest.
The slowest part of the quote-generation process occurred in the database queries loading customer pricing parameters. Adding a cache to the quote engine and optimizing a few other "hot spots" in the code brought quote latency down to the range of roughly 100 milliseconds. With a faster engine, the bank was able to capture significant market share on the competitive quotation platform—but the market continued to evolve.
Citações de transmissão.
By 2006 a new style of currency trading was becoming popular. Instead of a customer sending a specific request and the bank responding with a quote, customers wanted the banks to send a continuous stream of quotes. This streaming-quotes style of trading was especially popular with certain hedge funds that were developing automated trading strategies—applications that would receive streams of quotes from multiple banks and automatically decide when to trade. In many cases, humans were now out of the loop on both sides of the trade.
To understand this new competitive dynamic, it's important to know how banks compute the rates they charge their clients for foreign-exchange transactions. The largest banks trade currencies with each other in the so-called interbank market. The exchange rates set in that market are the most competitive and form the basis for the rates (plus some markup) that are offered to clients. Every time the interbank rate changes, each bank recomputes and republishes the corresponding client rate quotes. If a client accepts a quote (i. e., requests to trade against a quoted exchange rate), the bank can immediately execute an offsetting trade with the interbank market, minimizing risk and locking in a small profit. There are, however, risks to banks that are slow to update their quotes. A simple example can illustrate:
Imagine that the interbank spot market for EUR/USD has rates of 1.3558 / 1.3560. (The term spot means that the agreed-upon currencies are to be exchanged within two business days. Currencies can be traded for delivery at any mutually agreed-upon date in the future, but the spot market is the most active in terms of number of trades.) Two rates are quoted: one for buying (the bid rate), and one for selling (the offered or ask rate). In this case, a participant in the interbank market could sell one euro and receive 1.3558 US dollars in return. Conversely, one could buy one euro for a price of 1.3560 US dollars.
Say that two banks, A and B, are participants in the interbank market and are publishing quotes to the same hedge fund client, C. Both banks add a margin of 0.0001 to the exchange rates they quote to their clients—so both publish quotes of 1.3557 / 1.3561 to client C. Bank A, however, is faster at updating its quotes than bank B, taking about 50 milliseconds while bank B takes about 250 milliseconds. There are approximately 50 milliseconds of network latency between banks A and B and their mutual client C. Both banks A and B take about 10 milliseconds to acknowledge an order, while the hedge fund C takes about 10 milliseconds to evaluate new quotes and submit orders. Table 2 breaks down the sequence of events.
The net effect of this new streaming-quote style of trading was that any bank that was significantly slower than its rivals was likely to suffer losses when market prices changed and its quotes weren't updated quickly enough. At the same time, those banks that could update their quotes fastest made significant profits. Latency was no longer just a factor in operational efficiency or market share—it directly impacted the profit and loss of the trading desk. As the volume and speed of trading increased throughout the mid-2000s, these profits and losses grew to be quite large. (How low can you go? Table 3 shows some examples of approximate latencies of systems and applications across nine orders of magnitude.)
To improve its latency, my bank split its quote and trading engine into distinct applications and rewrote the quote engine in C++. The small delays added by each hop in the network from the interbank market to the bank and onward to its clients were now significant, so the bank upgraded firewalls and procured dedicated telecom circuits. Network upgrades combined with the faster quote engine brought end-to-end quote latency down below 10 milliseconds for clients who were physically located close to our facilities in New York, London, or Hong Kong. Trading performance and profits rose accordingly—but, of course, the market kept evolving.
Engineering systems for low latency.
The latency requirements of a given application can be addressed in many ways, and each problem requires a different solution. There are some common themes, though. First, it is usually necessary to measure latency before it can be improved. Second, optimization often requires looking below abstraction layers and adapting to the reality of the physical infrastructure. Finally, it is sometimes possible to restructure the algorithms (or even the problem definition itself) to achieve low latency.
Lies, damn lies, and statistics.
The first step to solving most optimization problems (not just those that involve software) is to measure the current system's performance. Start from the highest level and measure the end-to-end latency. Then measure the latency of each component or processing stage. If any stage is taking an unusually large portion of the latency, then break it down further and measure the latency of its substages. The goal is to find the parts of the system that contribute the most to the total latency and focus optimization efforts there. This is not always straightforward in practice, however.
For example, imagine an application that responds to customer quote requests received over a network. The client sends 100 quote requests in quick succession (the next request is sent as soon as the prior response is received) and reports total elapsed time of 360 milliseconds—or 3.6 milliseconds on average to service a request. The internals of the application are broken down and measured using the same 100-quote test set:
&touro; Read input message from network and parse - 5 microseconds.
&touro; Look up client profile - 3.2 milliseconds (3,200 microseconds)
&touro; Compute client quote - 15 microseconds.
&touro; Log quote - 20 microseconds.
&touro; Serialize quote to a response message - 5 microseconds.
&touro; Write to network - 5 microseconds.
As clearly shown in this example, significantly reducing latency means addressing the time it takes to look up the client's profile. A quick inspection shows that the client profile is loaded from a database and cached locally. Further testing shows that when the profile is in the local cache (a simple hash table), response time is usually under a microsecond, but when the cache is missed it takes several hundred milliseconds to load the profile. The average of 3.2 milliseconds was almost entirely the result of one very slow response (of about 320 milliseconds) caused by a cache miss. Likewise, the client's reported 3.6-millisecond average response time turns out to be a single very slow response (350 milliseconds) and 99 fast responses that took around 100 microseconds each.
Means and outliers.
Most systems exhibit some variance in latency from one event to the next. In some cases the variance (and especially the highest-latency outliers) drives the design, much more so than the average case. It is important to understand which statistical measure of latency is appropriate to the specific problem. For example, if you are building a trading system that earns small profits when the latency is below some threshold but incurs massive losses when latency exceeds that threshold, then you should be measuring the peak latency (or, alternatively, the percentage of requests that exceed the threshold) rather than the mean. On the other hand, if the value of the system is more or less inversely proportional to the latency, then measuring (and optimizing) the average latency makes more sense even if it means there are some large outliers.
What are you measuring?
Astute readers may have noticed that the latency measured inside the quote server application doesn't quite add up to the latency reported by the client application. That is most likely because they aren't actually measuring the same thing. Consider the following simplified pseudocode:
(In the client application)
for (int i = 0; i < 100; i++)
RequestMessage requestMessage = new RequestMessage(quoteRequest);
long sentTime = getSystemTime();
ResponseMessage responseMessage = receiveMessage();
long quoteLatency = getSystemTime() - sentTime;
(In the quote server application)
RequestMessage requestMessage = receive();
long receivedTime = getSystemTime();
QuoteRequest quoteRequest = parseRequest(requestMessage);
long parseTime = getSystemTime();
long parseLatency = parseTime - receivedTime;
ClientProfile profile = lookupClientProfile(quoteRequest. client);
long profileTime = getSystemTime();
long profileLatency = profileTime - parseTime;
Quote quote = computeQuote(profile);
long computeTime = getSystemTime();
long computeLatency = computeTime - profileTime;
long logTime = getSystemTime();
long logLatency = logTime - computeTime;
QuoteMessage quoteMessage = new QuoteMessage(quote);
long serializeTime = getSystemTime();
long serializationLatency = serializeTime - logTime;
long sentTime = getSystemTime();
long sendLatency = sentTime - serializeTime;
logStats(parseLatency, profileLatency, computeLatency,
logLatency, serializationLatency, sendLatency);
Note that the elapsed time measured by the client application includes the time to transmit the request over the network, as well as the time for the response to be transmitted back. The quote server, on the other hand, measures the time elapsed only from the arrival of the quote to when it is sent (or more precisely, when the send method returns). The 350-microsecond discrepancy between the average response time measured by the client and the equivalent measurement by the quote server could be caused by the network, but it might also be the result of delays within the client or server. Moreover, depending on the programming language and operating system, checking the system clock and logging the latency statistics may introduce material delays.
This approach is simplistic, but when combined with code-profiling tools to find the most commonly executed code and resource contention, it is usually good enough to identify the first (and often easiest) targets for latency optimization. It's important to keep this limitation in mind, though.
Measuring distributed systems latency via network traffic capture.
Distributed systems pose some additional challenges to latency measurement—as well as some opportunities. In cases where the system is distributed across multiple servers it can be hard to correlate timestamps of related events. The network itself can be a significant contributor to the latency of the system. Messaging middleware and the networking stacks of operating systems can be complex sources of latency.
At the same time, the decomposition of the overall system into separate processes running on independent servers can make it easier to measure certain interactions accurately between components of the system over the network. Many network devices (such as switches and routers) provide mechanisms for making timestamped copies of the data that traverse the device with minimal impact on the performance of the device. Most operating systems provide similar capabilities in software, albeit with a somewhat higher risk of delaying the actual traffic. Timestamped network-traffic captures (often called packet captures ) can be a useful tool to measure more precisely when a message was exchanged between two parts of the system. These measurements can be obtained without modifying the application itself and generally with very little impact on the performance of the system as a whole. (See wireshark and tcpdump.)
One of the challenges of measuring performance at short time scales across distributed systems is clock synchronization. In general, to measure the time elapsed from when an application on server A transmits a message to when the message reaches a second application on server B, it is necessary to check the time on A's clock when the message is sent and on B's clock when the message arrives, and then subtract those two timestamps to determine the latency. If the clocks on A and B are not in sync, then the computed latency will actually be the real latency plus the clock skew between A and B.
When is this a problem in the real world? Real-world drift rates for the quartz oscillators that are used in most commodity server motherboards are on the order of 10^-5, which means that the oscillator may be expected to drift by 10 microseconds each second. If uncorrected, it may gain or lose as much as a second over the course of a day. For systems operating at time scales of milliseconds or less, clock skew may render the measured latency meaningless. Oscillators with significantly lower drift rates are available, but without some form of synchronization, they will eventually drift apart. Some mechanism is needed to bring each server's local clock into alignment with some common reference time.
Developers of distributed systems should understand NTP (Network Time Protocol) at a minimum and are encouraged to learn about PTP (Precision Time Protocol) and usage of external signals such as GPS to obtain high-accuracy time synchronization in practice. Those who need time accuracy at the sub-microsecond scale will want to become familiar with hardware implementations of PTP (especially at the network interface) as well as tools for extracting time information from each core's local clock. (See tools. ietf/html/rfc1305, tools. ietf/html/rfc5905, nist. gov/el/isd/ieee/ieee1588.cfm, and queue. acm/detail. cfm? id=2354406.)
Abstraction versus Reality.
Modern software engineering is built upon abstractions that allow programmers to manage the complexity of ever-larger systems. Abstractions do this by simplifying or generalizing some aspect of the underlying system. This doesn't come for free, though—simplification is an inherently lossy process and some of the lost details may be important. Moreover, abstractions are often defined in terms of function rather than performance.
Somewhere deep below an application are electrical currents flowing through semiconductors and pulses of light traveling down fibers. Programmers rarely need to think of their systems in these terms, but if their conceptualized view drifts too far from reality they are likely to experience unpleasant surprises.
Four examples illustrate this point:
&touro; TCP provides a useful abstraction over UDP (User Datagram Protocol) in terms of delivery of a sequence of bytes. TCP ensures that bytes will be delivered in the order they were sent even if some of the underlying UDP datagrams are lost. The transmission latency of each byte (the time from when it is written to a TCP socket in the sending application until it is read from the corresponding receiving application's socket) is not guaranteed, however. In certain cases (specifically when an intervening datagram is lost) the data contained in a given UDP datagram may be delayed significantly from delivery to the application, while the missed data ahead of it is recovered.
&touro; Cloud hosting provides virtual servers that can be created on demand without precise control over the location of the hardware. An application or administrator can create a new virtual server "on the cloud" in less than a minute—an impossible feat when assembling and installing physical hardware in a data center. Unlike the physical server, however, the location of the cloud server or its location in the network topology may not be precisely known. If a distributed application depends on the rapid exchange of messages between servers, the physical proximity of those servers may have a significant impact on the overall application performance.
&touro; Threads allow developers to decompose a problem into separate sequences of instructions that can be allowed to run concurrently, subject to certain ordering constraints, and that can operate on shared resources (such as memory). This allows developers to take advantage of multicore processors without needing to deal directly with issues of scheduling and core assignment. In some cases, however, the overhead of context switches and passing data between cores can outweigh the advantages gained by concurrency.
&touro; Hierarchical storage and cache-coherency protocols allow programmers to write applications that use large amounts of virtual memory (on the order of terabytes in modern commodity servers), while experiencing latencies measured in nanoseconds when requests can be serviced by the closest caches. The abstraction hides the fact that the fastest memory is very limited in capacity (e. g., register files on the order of a few kilobytes), while memory that has been swapped out to disk may incur latencies in the tens of milliseconds.
Each of these abstractions is extremely useful but can have unanticipated consequences for low-latency applications. There are some practical steps to take to identify and mitigate latency issues resulting from these abstractions.
Messaging and Network Protocols.
The near ubiquity of IP-based networks means that regardless of which messaging product is in use, under the covers the data is being transmitted over the network as a series of discrete packets. The performance characteristics of the network and the needs of an application can vary dramatically—so one size almost certainly does not fit all when it comes to messaging middleware for latency-sensitive distributed systems.
There's no substitute for getting under the hood here. For example, if an application runs on a private network (you control the hardware), communications follow a publisher/subscriber model, and the application can tolerate a certain rate of data loss, then raw multicast may offer significant performance gains over any middleware based on TCP. If an application is distributed across very long distances and data order is not important, then a UDP-based protocol may offer advantages in terms of not stalling to resend a missed packet. If TCP-based messaging is being used, then it's worth keeping in mind that many of its parameters (especially buffer sizes, slow start, and Nagle's algorithm) are configurable and the "out-of-the-box" settings are usually optimized for throughput rather than latency (queue. acm/detail. cfm? id=2539132).
The physical constraint that information cannot propagate faster than the speed of light is a very real consideration when dealing with short time scales and/or long distances. The two largest stock exchanges, NASDAQ and NYSE, run their matching engines in data centers in Carteret and Mahwah, New Jersey, respectively. A ray of light takes 185 microseconds to travel the 55.4-km distance between these two locations. Light in a glass fiber with a refractive index of 1.6 and following a slightly longer path (roughly 65 km) takes almost 350 microseconds to make the same one-way trip. Given that the computations involved in trading decisions can now be made on time scales of 10 microseconds or less, signal propagation latency cannot be ignored.
Decomposing a problem into a number of threads that can be executed concurrently can greatly increase performance, especially in multicore systems, but in some cases it may actually be slower than a single-threaded solution.
Specifically, multithreaded code incurs overhead in the following three ways:
&touro; When multiple threads operate on the same data, controls are required to ensure that the data remains consistent. This may include acquisition of locks or implementations of read or write barriers. In multicore systems, these concurrency controls require that thread execution is suspended while messages are passed between cores. If a lock is already held by one thread, then other threads seeking that lock will need to wait until the first one is finished. If several threads are frequently accessing the same data, there may be significant contention for locks.
&touro; Similarly, when multiple threads operate on the same data, the data itself must be passed between cores. If several threads access the same data but each performs only a few computations on it, the time required to move the data between cores may exceed the time spent operating on it.
&touro; Finally, if there are more threads than cores, the operating system must periodically perform a context switch in which the thread running on a given core is halted, its state is saved, and another thread is allowed to run. The cost of a context switch can be significant. If the number of threads far exceeds the number of cores, context switching can be a significant source of delay.
In general, application design should use threads in a way that represents the inherent concurrency of the underlying problem. If the problem contains significant computation that can be performed in isolation, then a larger number of threads is called for. On the other hand, if there is a high degree of interdependency between computations or (worst case) if the problem is inherently serial, then a single-threaded solution may make more sense. In both cases, profiling tools should be used to identify excessive lock contention or context switching. Lock-free data structures (now available for several programming languages) are another alternative to consider (queue. acm/detail. cfm? id=2492433).
It's also worth noting that the physical arrangement of cores, memory, and I/O may not be uniform. For example, on modern Intel microprocessors certain cores can interact with external I/O (e. g., network interfaces) with much lower latency than others, and exchanging data between certain cores is faster than others. As a result, it may be advantageous explicitly to pin specific threads to specific cores (queue. acm/detail. cfm? id=2513149).
Hierarchical storage and cache misses.
All modern computing systems use hierarchical data storage—a small amount of fast memory combined with multiple levels of larger (but slower) memory. Recently accessed data is cached so that subsequent access is faster. Since most applications exhibit a tendency to access the same memory multiple times in a short period, this can greatly increase performance. To obtain maximum benefit, however, the following three factors should be incorporated into application design:
&touro; Using less memory overall (or at least in the parts of the application that are latency-sensitive) increases the probability that needed data will be available in one of the caches. In particular, for especially latency-sensitive applications, designing the app so that frequently accessed data fits within the CPU's caches can significantly improve performance. Specifications vary but Intel's Haswell microprocessors, for example, provide 32 KB per core for L1 data cache and up to 40 MB of shared L3 cache for the entire CPU.
&touro; Repeated allocation and release of memory should be avoided if reuse is possible. An object or data structure that is allocated once and reused has a much greater chance of being present in a cache than one that is repeatedly allocated anew. This is especially true when developing in environments where memory is managed automatically, as overhead caused by garbage collection of memory that is released can be significant.
&touro; The layout of data structures in memory can have a significant impact on performance because of the architecture of caches in modern processors. While the details vary by platform and are outside the scope of this article, it is generally a good idea to prefer arrays as data structures over linked lists and trees and to prefer algorithms that access memory sequentially since these allow the hardware prefetcher (which attempts to load data preemptively from main memory into cache before it is requested by the application) to operate most efficiently. Note also that data that will be operated on concurrently by different cores should be structured so that it is unlikely to fall in the same cache line (the latest Intel CPUs use 64-byte cache lines) to avoid cache-coherency contention.
A note on premature optimization.
The optimizations just presented should be considered part of a broader design process that takes into account other important objectives including functional correctness, maintainability, etc. Keep in mind Knuth's quote about premature optimization being the root of all evil; even in the most performance-sensitive environments, it is rare that a programmer should be concerned with determining the correct number of threads or the optimal data structure until empirical measurements indicate that a specific part of the application is a hot spot. The focus instead should be on ensuring that performance requirements are understood early in the design process and that the system architecture is sufficiently decomposable to allow detailed measurement of latency when and as optimization becomes necessary. Moreover (and as discussed in the next section), the most useful optimizations may not be in the application code at all.
Changes in Design.
The optimizations presented so far have been limited to improving the performance of a system for a given set of functional requirements. There may also be opportunities to change the broader design of the system or even to change the functional requirements of the system in a way that still meets the overall objectives but significantly improves performance. Latency optimization is no exception. In particular, there are often opportunities to trade reduced efficiency for improved latency.
Three real-world examples of design tradeoffs between efficiency and latency are presented here, followed by an example where the requirements themselves present the best opportunity for redesign.
In certain cases trading efficiency for latency may be possible, especially in systems that operate well below their peak capacity. In particular, it may be advantageous to compute possible outputs in advance, especially when the system is idle most of the time but must react quickly when an input arrives.
A real-world example can be found in the systems used by some firms to trade stocks based on news such as earnings announcements. Imagine that the market expects Apple to earn between $9.45 and $12.51 per share. The goal of the trading system, upon receiving Apple's actual earnings, would be to sell some number of shares Apple stock if the earnings were below $9.45, buy some number of shares if the earnings were above $12.51, and do nothing if the earnings fall within the expected range. The act of buying or selling stocks begins with submitting an order to the exchange. The order consists of (among other things) an indicator of whether the client wishes to buy or sell, the identifier of the stock to buy or sell, the number of shares desired, and the price at which the client wishes to buy or sell. Throughout the afternoon leading up to Apple's announcement, the client would receive a steady stream of market-data messages that indicate the current price at which Apple's stock is trading.
A conventional implementation of this trading system would cache the market-price data and, upon receipt of the earnings data, decide whether to buy or sell (or neither), construct an order, and serialize that order to an array of bytes to be placed into the payload of a message and sent to the exchange.
An alternative implementation performs most of the same steps but does so on every market-data update rather than only upon receipt of the earnings data. Specifically, when each market-data update message is received, the application constructs two new orders (one to buy, one to sell) at the current prices and serializes each order into a message. The messages are cached but not sent. When the next market-data update arrives, the old order messages are discarded and new ones are created. When the earnings data arrives, the application simply decides which (if either) of the order messages to send.
The first implementation is clearly more efficient (it has a lot less wasted computation), but at the moment when latency matters most (i. e., when the earnings data has been received), the second algorithm is able to send out the appropriate order message sooner. Note that this example presents application-level precomputation; there is an analogous process of branch prediction that takes place in pipelined processors which can also be optimized (via guided profiling) but is outside the scope of this article.
Keeping the system warm.
In some low-latency systems long delays may occur between inputs. During these idle periods, the system may grow "cold." Critical instructions and data may be evicted from caches (costing hundreds of nanoseconds to reload), threads that would process the latency-sensitive input are context-switched out (costing tens of microseconds to resume), CPUs may switch into power-saving states (costing a few milliseconds to exit), etc. Each of these steps makes sense from an efficiency standpoint (why run a CPU at full power when nothing is happening?), but all of them impose latency penalties when the input data arrives.
In cases where the system may go for hours or days between input events there is a potential operational issue as well: configuration or environmental changes may have "broken" the system in some important way that won't be discovered until the event occurs—when it's too late to fix.
A common solution to both problems is to generate a continuous stream of dummy input data to keep the system "warm." The dummy data needs to be as realistic as possible to ensure that it keeps the right data in the caches and that breaking changes to the environment are detected. The dummy data needs to be reliably distinguishable from legitimate data, though, to prevent downstream systems or clients from being confused.
It is common in many systems to process the same data through multiple independent instances of the system in parallel, primarily for the improved resiliency that is conferred. If some component fails, the user will still receive the result needed. Low-latency systems gain the same resiliency benefits of parallel, redundant processing but can also use this approach to reduce certain kinds of variable latency.
All real-world computational processes of nontrivial complexity have some variance in latency even when the input data is the same. These variations can be caused by minute differences in thread scheduling, explicitly randomized behaviors such as Ethernet's exponential back-off algorithm, or other unpredictable factors. Some of these variations can be quite large: page faults, garbage collections, network congestion, etc., can all cause occasional delays that are several orders of magnitude larger than the typical processing latency for the same input.
Running multiple, independent instances of the system, combined with a protocol that allows the end recipient to accept the first result produced and discard subsequent redundant copies, both provides the benefit of less-frequent outages and avoids some of the larger delays.
Stream processing and short circuits.
Consider a news analytics system whose requirements are understood to be "build an application that can extract corporate earnings data from a press release document as quickly as possible." Separately, it was specified that the press releases would be pushed to the system via FTP. The system was thus designed as two applications: one that received the document via FTP, and a second that parsed the document and extracted the earnings data. In the first version of this system, an open-source FTP server was used as the first application, and the second application (the parser) assumed that it would receive a fully formed document as input, so it did not start parsing the document until it had fully arrived.
Measuring the performance of the system showed that while parsing was typically completed in just a few milliseconds, receiving the document via FTP could take tens of milliseconds from the arrival of the first packet to the arrival of the last packet. Moreover, the earnings data was often present in the first paragraph of the document.
In a multistep process it may be possible for subsequent stages to start processing before prior stages have finished, sometimes referred to as stream-oriented or pipelined processing . This can be especially useful if the output can be computed from a partial input. Taking this into account, the developers reconceived their overall objective as "build a system that can deliver earnings data to the client as quickly as possible." This broader objective, combined with the understanding that the press release would arrive via FTP and that it was possible to extract the earnings data from the first part of the document (i. e., before the rest of the document had arrived), led to a redesign of the system.
The FTP server was rewritten to forward portions of the document to the parser as they arrived rather than wait for the entire document. Likewise, the parser was rewritten to operate on a stream of incoming data rather than on a single document. The result was that in many cases the earnings data could be extracted within just a few milliseconds of the start of the arrival of the document. This reduced overall latency (as observed by the client) by several tens of milliseconds without the internal implementation of the parsing algorithm being any faster.
Conclusão.
While latency requirements are common to a wide array of software applications, the financial trading industry and the segment of the news media that supplies it with data have an especially competitive ecosystem that produces challenging demands for low-latency distributed systems.
As with most engineering problems, building effective low-latency distributed systems starts with having a clear understanding of the problem. The next step is measuring actual performance and then, where necessary, making improvements. In this domain, improvements often require some combination of digging below the surface of common software abstractions and trading some degree of efficiency for improved latency.
LOVE IT, HATE IT? LET US KNOW.
Andrew Brook is the CTO of Selerity, a provider of realtime news, data, and content analytics. Previously he led development of electronic currency trading systems at two large investment banks and launched a pre-dot-com startup to deliver AI-powered scheduling software to agile manufacturers. His expertise lies in applying distributed, realtime systems technology and data science to real-world business problems. He finds Wireshark to be more interesting than PowerPoint.
&cópia de; 2018 ACM 1542-7730/14/0300 $10.00.
An apostate's opinion.
Ivan Beschastnikh, Patty Wang, Yuriy Brun, Michael D, Ernst - Debugging Distributed Systems.
Challenges and options for validation and debugging.
The accepted wisdom does not always hold true.
Lunchtime doubly so. - Ford Prefect to Arthur Dent in "The Hitchhiker's Guide to the Galaxy", by Douglas Adams.
Elios | Sat, 07 Nov 2018 09:29:52 UTC.
Thanks for the nice post. That's a great sum-up of problems in the design and implementation of distributed low latency systems.
I'm working on a distributed low-latency market data distribution system. In this system, one of the biggest challenge is how to measure its latency which is supposed to be several micro seconds.
In our previous system, the latency is measured in an end-to-end manner. We take timestamp in milli seconds on both publisher and subscriber side and record the difference between them. This works but we are aware that the result is not accurate because even with servers having clock synchronized with NTP, users complain sometimes that negative latency is observed.
Given we are reducing the latency to micro seconds, the end-to-end measurement seems to be too limited (it should be better with PTP but we can't force our users to support PTP in their infrastructure) and thus we are trying to get a round-trip latency. However, I can see immediately several cons with this method :
- extra complexity to configure and implement the system because we need to ensure two-way communication. - we can't deduce the end-to-end latency from the round trip one because the loads on both direction are not the same. (we want to send only some probes and get them back)
Do you have some experiences on the round-trip latency measurement and if so could you please share some best practices ?