Evolução da arquitetura do sistema de negociação e compensação da Bolsa de Moscou. Parte 1

Olá a todos! Meu nome é Sergey Kostanbaev, na Bolsa estou desenvolvendo o núcleo do sistema de negociação.

Quando os filmes de Hollywood mostram a Bolsa de Valores de Nova York, sempre fica assim: uma multidão, todo mundo grita alguma coisa, agitando papéis, um caos completo está acontecendo. Isso nunca aconteceu aqui na Bolsa de Moscou, porque a negociação foi realizada eletronicamente desde o início e é baseada em duas plataformas principais - Spectra (mercado cambial) e ASTS (mercado cambial, de ações e monetário). E hoje quero falar sobre a evolução da arquitetura do sistema de negociação e compensação ASTS, sobre diversas soluções e descobertas. A história será longa, então tive que dividi-la em duas partes.

Somos uma das poucas bolsas no mundo que negocia ativos de todas as classes e oferece uma gama completa de serviços de câmbio. Por exemplo, no ano passado ficámos em segundo lugar no mundo em termos de volume de negociação de títulos, em 25º lugar entre todas as bolsas de valores, em 13º lugar em capitalização entre as bolsas públicas.

Para participantes comerciais profissionais, parâmetros como tempo de resposta, estabilidade da distribuição do tempo (jitter) e confiabilidade de todo o complexo são críticos. Atualmente processamos dezenas de milhões de transações por dia. O processamento de cada transação pelo kernel do sistema leva dezenas de microssegundos. Claro que as operadoras móveis na passagem de ano ou os próprios motores de busca têm uma carga de trabalho superior à nossa, mas em termos de carga de trabalho, aliada às características acima mencionadas, poucos se comparam a nós, parece-me. Ao mesmo tempo, é importante para nós que o sistema não fique lento por um segundo, funcione de forma absolutamente estável e que todos os usuários estejam em pé de igualdade.

Um pouco de história

Em 1994, o sistema australiano ASTS foi lançado na Bolsa Interbancária de Moeda de Moscou (MICEX), e a partir desse momento a história russa do comércio eletrônico pode ser contada. Em 1998, a arquitetura da bolsa foi modernizada para introduzir o comércio pela Internet. Desde então, a velocidade de implementação de novas soluções e mudanças arquitetônicas em todos os sistemas e subsistemas só vem ganhando força.

Naqueles anos, o sistema de troca funcionava em hardware de última geração - servidores HP Superdome 9000 ultraconfiáveis ​​(construídos no PA-RISC), em que absolutamente tudo foi duplicado: subsistemas de entrada/saída, rede, RAM (na verdade, havia uma matriz RAID de RAM), processadores (hot-swappable). Foi possível alterar qualquer componente do servidor sem parar a máquina. Confiamos nesses dispositivos e os consideramos praticamente à prova de falhas. O sistema operacional era um sistema HP UX semelhante ao Unix.

Mas desde cerca de 2010, surgiu um fenómeno chamado negociação de alta frequência (HFT), ou negociação de alta frequência - simplesmente, robôs da bolsa de valores. Em apenas 2,5 anos, a carga nos nossos servidores aumentou 140 vezes.

Era impossível suportar tamanha carga com a arquitetura e os equipamentos antigos. Foi necessário se adaptar de alguma forma.

começo

As solicitações ao sistema de troca podem ser divididas em dois tipos:

• Transações. Se quiser comprar dólares, ações ou qualquer outra coisa, você envia uma transação ao sistema de negociação e recebe uma resposta sobre o sucesso.
• Pedidos de informação. Se quiser saber o preço atual, consulte a carteira de ofertas ou índices e envie pedidos de informação.

Esquematicamente, o núcleo do sistema pode ser dividido em três níveis:

• O nível do cliente, em que corretores e clientes trabalham. Todos eles interagem com servidores de acesso.
• Os servidores gateway são servidores de cache que processam localmente todas as solicitações de informações. Quer saber a que preço as ações do Sberbank estão sendo negociadas atualmente? A solicitação vai para o servidor de acesso.
• Mas se você quiser comprar ações, a solicitação vai para o servidor central (Trade Engine). Existe um desses servidores para cada tipo de mercado, eles desempenham um papel vital, foi para eles que criamos este sistema.

O núcleo do sistema de negociação é um banco de dados inteligente na memória, no qual todas as transações são transações de câmbio. A base foi escrita em C, as únicas dependências externas eram a biblioteca libc e não havia nenhuma alocação dinâmica de memória. Para reduzir o tempo de processamento, o sistema inicia com um conjunto estático de arrays e com realocação estática de dados: primeiro, todos os dados do dia atual são carregados na memória e nenhum outro acesso ao disco é realizado, todo o trabalho é realizado apenas na memória. Quando o sistema é iniciado, todos os dados de referência já estão ordenados, portanto a busca funciona de forma muito eficiente e leva pouco tempo em tempo de execução. Todas as tabelas são feitas com listas e árvores intrusivas para estruturas de dados dinâmicas para que não exijam alocação de memória em tempo de execução.

Vamos repassar brevemente a história do desenvolvimento do nosso sistema de negociação e compensação.
A primeira versão da arquitetura do sistema de negociação e compensação foi construída na chamada interação Unix: foram utilizados memória compartilhada, semáforos e filas, e cada processo consistia em um único thread. Essa abordagem foi generalizada no início da década de 1990.

A primeira versão do sistema continha dois níveis de Gateway e um servidor central do sistema de negociação. O fluxo de trabalho era assim:

• O cliente envia uma solicitação, que chega ao Gateway. Verifica a validade do formato (mas não os dados em si) e rejeita transações incorretas.
• Caso tenha sido enviado um pedido de informação, este é executado localmente; se estamos falando de uma transação, ela é redirecionada para o servidor central.
• O mecanismo de negociação então processa a transação, modifica a memória local e envia uma resposta à transação e à própria transação para replicação usando um mecanismo de replicação separado.
• O Gateway recebe a resposta do nó central e a encaminha ao cliente.
• Após algum tempo, o Gateway recebe a transação através do mecanismo de replicação, e desta vez a executa localmente, alterando suas estruturas de dados para que as próximas solicitações de informações exibam os dados mais recentes.

Na verdade, descreve um modelo de replicação em que o Gateway replicou completamente as ações realizadas no sistema de negociação. Um canal de replicação separado garantiu que as transações fossem executadas na mesma ordem em vários nós de acesso.

Como o código era single-thread, um esquema clássico com bifurcações de processo foi usado para atender muitos clientes. No entanto, era muito caro bifurcar todo o banco de dados, então foram usados ​​processos de serviço leves que coletavam pacotes de sessões TCP e os transferiam para uma fila (SystemV Message Queue). Gateway e Trade Engine funcionavam apenas com essa fila, retirando as transações de lá para execução. Não foi mais possível enviar resposta, pois não estava claro qual processo de serviço deveria lê-lo. Então recorremos a um truque: cada processo bifurcado criava uma fila de resposta para si mesmo e, quando uma solicitação chegava à fila de entrada, uma tag para a fila de resposta era imediatamente adicionada a ela.

A cópia constante de grandes quantidades de dados de uma fila para outra criava problemas, especialmente típicos para solicitações de informações. Portanto, usamos outro truque: além da fila de resposta, cada processo também criava memória compartilhada (SystemV Shared Memory). Nele foram colocados os próprios pacotes, e apenas uma tag foi armazenada na fila, permitindo encontrar o pacote original. Isso ajudou a armazenar dados no cache do processador.

SystemV IPC inclui utilitários para visualizar o estado de objetos de fila, memória e semáforo. Usamos isso ativamente para entender o que estava acontecendo no sistema em um determinado momento, onde os pacotes se acumulavam, o que estava bloqueado, etc.

Primeiras atualizações

Em primeiro lugar, nos livramos do Gateway de processo único. Sua desvantagem significativa era que ele poderia lidar com uma transação de replicação ou com uma solicitação de informações de um cliente. E à medida que a carga aumenta, o Gateway demorará mais para processar as solicitações e não será capaz de processar o fluxo de replicação. Além disso, se o cliente enviou uma transação, basta verificar sua validade e encaminhá-la posteriormente. Portanto, substituímos o processo único do Gateway por vários componentes que podem ser executados em paralelo: informações multithread e processos de transação executados independentemente uns dos outros em uma área de memória compartilhada usando bloqueio RW. E ao mesmo tempo introduzimos processos de expedição e replicação.

Impacto da negociação de alta frequência

A versão acima da arquitetura existiu até 2010. Enquanto isso, não estávamos mais satisfeitos com o desempenho dos servidores HP Superdome. Além disso, a arquitetura PA-RISC estava praticamente morta; o fornecedor não ofereceu nenhuma atualização significativa. Como resultado, começamos a migrar do HP UX/PA RISC para o Linux/x86. A transição começou com a adaptação dos servidores de acesso.

Por que tivemos que mudar a arquitetura novamente? O fato é que a negociação de alta frequência alterou significativamente o perfil de carga no núcleo do sistema.

Digamos que temos uma pequena transação que causou uma mudança significativa de preço – alguém comprou meio bilhão de dólares. Depois de alguns milissegundos, todos os participantes do mercado percebem isso e começam a fazer uma correção. Naturalmente, as solicitações se alinham em uma fila enorme, que o sistema levará muito tempo para limpar.

Nesse intervalo de 50 ms, a velocidade média é de cerca de 16 mil transações por segundo. Se reduzirmos a janela para 20 ms, obtemos uma velocidade média de 90 mil transações por segundo, com 200 mil transações no pico. Ou seja, a carga não é constante, com picos repentinos. E a fila de solicitações deve ser sempre processada rapidamente.

Mas por que existe uma fila? Assim, em nosso exemplo, muitos usuários notaram a mudança de preço e enviaram as transações de acordo. Eles chegam ao Gateway, ele os serializa, define uma determinada ordem e os envia para a rede. Os roteadores embaralham os pacotes e os encaminham. Cujo pacote chegou primeiro, essa transação “ganhou”. Com isso, os clientes da exchange começaram a perceber que se a mesma transação fosse enviada de vários Gateways, as chances de seu processamento rápido aumentavam. Logo, os robôs de câmbio começaram a bombardear o Gateway com solicitações e surgiu uma avalanche de transações.

Uma nova rodada de evolução

Após extensos testes e pesquisas, mudamos para o kernel do sistema operacional em tempo real. Para isso escolhemos RedHat Enterprise MRG Linux, onde MRG significa grade de mensagens em tempo real. A vantagem dos patches em tempo real é que eles otimizam o sistema para a execução mais rápida possível: todos os processos são alinhados em uma fila FIFO, os núcleos podem ser isolados, não há ejeções, todas as transações são processadas em sequência estrita.

Vermelho - trabalhando com fila em um kernel normal, verde - trabalhando em um kernel em tempo real.

Mas conseguir baixa latência em servidores regulares não é tão fácil:

• O modo SMI, que na arquitetura x86 é a base para trabalhar com periféricos importantes, interfere bastante. O processamento de todos os tipos de eventos de hardware e o gerenciamento de componentes e dispositivos são realizados pelo firmware no chamado modo SMI transparente, no qual o sistema operacional não vê o que o firmware está fazendo. Via de regra, todos os principais fornecedores oferecem extensões especiais para servidores de firmware que permitem reduzir a quantidade de processamento SMI.
• Não deve haver controle dinâmico da frequência do processador, o que leva a um tempo de inatividade adicional.
• Quando o log do sistema de arquivos é liberado, determinados processos ocorrem no kernel que causam atrasos imprevisíveis.
• Você precisa prestar atenção a coisas como afinidade de CPU, afinidade de interrupção, NUMA.

Devo dizer que o tópico de configuração do hardware e do kernel Linux para processamento em tempo real merece um artigo separado. Passamos muito tempo experimentando e pesquisando antes de alcançarmos um bom resultado.

Ao passar dos servidores PA-RISC para x86, praticamente não tivemos que alterar muito o código do sistema, apenas o adaptamos e reconfiguramos. Ao mesmo tempo, corrigimos vários bugs. Por exemplo, as consequências do fato de PA RISC ser um sistema Big endian e x86 ser um sistema Little endian surgiram rapidamente: por exemplo, os dados foram lidos incorretamente. O bug mais complicado é que o PA RISC usa consistentemente consistente (Sequencialmente consistente) acesso à memória, enquanto o x86 pode reordenar as operações de leitura, de modo que o código que era absolutamente válido em uma plataforma foi quebrado em outra.

Depois de mudar para x86, o desempenho quase triplicou, o tempo médio de processamento de transações diminuiu para 60 μs.

Vamos agora dar uma olhada mais de perto nas principais mudanças que foram feitas na arquitetura do sistema.

Épico de reserva quente

Ao mudar para servidores comuns, sabíamos que eles eram menos confiáveis. Portanto, ao criar uma nova arquitetura, assumimos a priori a possibilidade de falha de um ou mais nós. Portanto, era necessário um sistema de espera a quente que pudesse mudar rapidamente para máquinas de backup.

Além disso, havia outros requisitos:

• Sob nenhuma circunstância você deve perder transações processadas.
• O sistema deve ser absolutamente transparente para a nossa infraestrutura.
• Os clientes não devem ver conexões perdidas.
• As reservas não devem introduzir atrasos significativos porque este é um fator crítico para a troca.

Ao criar um sistema hot standby, não consideramos cenários como falhas duplas (por exemplo, a rede em um servidor parou de funcionar e o servidor principal congelou); não considerou a possibilidade de erros no software porque são identificados durante os testes; e não considerou o funcionamento incorreto do hardware.

Como resultado, chegamos ao seguinte esquema:

• O servidor principal interagiu diretamente com os servidores Gateway.
• Todas as transações recebidas no servidor principal foram replicadas instantaneamente para o servidor de backup através de um canal separado. O árbitro (governador) coordenava a troca caso surgisse algum problema.

  

• O servidor principal processou cada transação e aguardou a confirmação do servidor de backup. Para manter a latência no mínimo, evitamos esperar a conclusão da transação no servidor de backup. Como o tempo que uma transação levava para percorrer a rede era comparável ao tempo de execução, nenhuma latência adicional foi adicionada.
• Só pudemos verificar o status de processamento dos servidores principal e de backup da transação anterior, e o status de processamento da transação atual era desconhecido. Como ainda estávamos usando processos single-threaded, aguardar uma resposta do Backup teria desacelerado todo o fluxo de processamento, então fizemos um acordo razoável: verificamos o resultado da transação anterior.

O esquema funcionou da seguinte maneira.

Digamos que o servidor principal pare de responder, mas os Gateways continuem a se comunicar. Ocorre um tempo limite no servidor de backup, ele entra em contato com o Governador, que lhe atribui a função de servidor principal, e todos os Gateways mudam para o novo servidor principal.

Se o servidor principal voltar a ficar online, também acionará um timeout interno, pois não houve chamadas do Gateway para o servidor por um determinado período. Depois ele também recorre ao governador e o exclui do esquema. Como resultado, a bolsa funciona com um servidor até o final do período de negociação. Como a probabilidade de falha do servidor é bastante baixa, este esquema foi considerado bastante aceitável; não continha lógica complexa e era fácil de testar.

Para ser continuado.

Fonte: habr.com