Bolsa de valores (matching engine)

01 · CONTEXTO

O coração de uma bolsa

Uma bolsa de valores eletrônica gira em torno do sistema de casamento de ordens, o matching engine: o componente que cruza ordens de compra e de venda e produz os negócios. O exercício clássico pede o desenho desse núcleo, com os participantes enviando ordens, o livro de ofertas sendo atualizado e os negócios sendo publicados. A fonte o descreve como o núcleo de todas as bolsas eletrônicas, em geral parte de um sistema maior que inclui liquidação e depositário central.

O mercado funciona em dois estados. Na negociação contínua, as ordens são casadas assim que chegam; no leilão, o casamento acontece em intervalos fixos, como na abertura do mercado, quando ordens se acumularam. Este caso trata do estado contínuo, que é o que ocupa a maior parte do dia.

A exigência dominante é a latência. Uma plataforma de negociação precisa processar as ordens muito depressa porque o mercado se move rápido, e cada ordem processada muda as condições para as seguintes. Não basta ser rápido: é preciso processar em uma ordem bem definida.

02 · LIVRO DE OFERTAS

Quem é atendido primeiro

O livro de ofertas guarda as ordens limitadas ainda não executadas, separadas em compras e vendas e organizadas por preço. Uma ordem que chega ou cruza com o outro lado do livro e gera negócio, ou fica esperando no livro. Quando várias ordens têm o mesmo preço, uma regra de prioridade decide quem é atendida primeiro.

Os algoritmos de casamento mais comuns são o Pro-Rata e o Price/Time, este também chamado de FIFO. Cada um cria incentivos diferentes para quem negocia.

Seja qual for a regra, ela precisa ser determinística: a mesma sequência de ordens tem de produzir sempre os mesmos negócios. Essa propriedade será a base da recuperação de falhas mais adiante.

03 · UMA THREAD

Por que não paralelizar o casamento

O instinto é paralelizar: várias threads processando ordens ao mesmo tempo. A equipe da LMAX, plataforma de negociação financeira de varejo, tentou esse caminho primeiro, com um protótipo de bolsa baseado em atores, e mediu. Os processadores gastavam mais tempo gerenciando filas do que executando a lógica da aplicação.

Terminaram com a lógica de negócio de todos os clientes e de todos os mercados numa única thread, que processa milhões de ordens por segundo em hardware comum. A própria fonte ressalva que o número vem de um servidor de dois soquetes da época, e que cada ordem exige checagens e escolha de política de casamento, ou seja, não é uma operação trivial.

1. A ordem do participante chega pela rede ao gateway, que a recebe e a converte para o formato interno do sistema.

2. O sequenciador dá a cada ordem um lugar único na fila global. É essa ordem total que torna o resultado reproduzível.

3. Antes de a ordem ser processada, o evento é gravado em um registro durável, de modo que o estado possa ser reconstruído depois.

4. O motor de casamento lê os eventos em sequência, numa só thread e só em memória, aplica a regra de prioridade e atualiza o livro de ofertas.

5. Os negócios gerados e as mudanças no livro saem como eventos de saída, publicados de forma assíncrona aos participantes do mercado.

Rodar só em memória e de forma sequencial dá velocidade: não há acesso lento a um banco de dados nem comportamento transacional a executar. Fica a pergunta de como sobreviver a uma queda, tratada adiante.

04 · ENTRADA

Sequenciar, registrar e replicar

Antes de uma ordem chegar à lógica de negócio, ela precisa ser retirada do gateway e desserializada, replicada e registrada em um journal. O replicador e o journaler fazem I/O e são relativamente lentos, mas são independentes entre si e, por isso, podem rodar em paralelo, desde que todos terminem antes de a lógica de negócio processar a mensagem.

O journal da LMAX não é um banco de dados, apenas o sistema de arquivos. Já a replicação é necessária mesmo com multicast, porque as mensagens podem chegar em ordem diferente em nós diferentes; por isso o nó líder fornece a sequência determinística que todo o resto segue.

05 · FALHAS

Reconstruir o estado e trocar de réplica

Manter tudo em memória tem uma consequência óbvia: o que acontece se tudo cair? A resposta é event sourcing: o estado do processador é inteiramente derivável dos eventos de entrada. Enquanto o fluxo de eventos estiver em armazenamento durável, basta reprocessá-lo para recriar o estado.

Reprocessar todos os eventos levaria tempo demais para subir um novo processador, então a LMAX também tira snapshots do estado, todas as noites, em período de baixa atividade. E, como nem isso basta para uma queda no meio do dia, mantém vários processadores sempre em execução: todos processam cada evento de entrada, mas a saída de todos menos um é ignorada. Se o processador ativo falha, o sistema troca para outro.

1. O sequenciador líder grava cada evento de entrada no journal, que é a fonte da verdade de tudo o que o sistema já aceitou.

2. A mesma sequência de entrada é replicada para todos os processadores, que a aplicam na mesma ordem e chegam ao mesmo estado.

3. Só a saída do processador ativo segue para o canal de saída; a dos demais é descartada.

4. Periodicamente o estado é salvo em um snapshot, para que um processador novo não precise reprocessar todo o journal.

5. Quando o ativo cai, uma réplica já atualizada assume a publicação da saída, sem precisar reconstruir o estado do zero.

Quando o líder cai, outro nó assume a liderança, passa a processar eventos de entrada e inicia o seu replicador. A eleição e o acordo sobre quem é o líder são o terreno dos algoritmos de consenso, e manter réplicas prontas é uma questão de disponibilidade.

06 · MODELO

Restrições e quando usar

O modelo impõe regras à lógica de negócio. Não se pode chamar serviços externos de dentro dela, pois uma chamada lenta pararia todo o processamento; a interação termina com um evento de saída e só é retomada quando outro evento de entrada chega. E não há rollback automático, por isso a equipe valida os eventos por inteiro antes de alterar o estado em memória.

Em troca, o determinismo dá ganhos de operação. Para diagnosticar um problema, a equipe copia a sequência de eventos para o ambiente de desenvolvimento e a reproduz. Cálculos pesados que não fazem parte do processamento de ordens rodam em um modelo replicado, sem interferir no núcleo.

A fonte vê esse processador como uma escolha natural para o lado de comandos de um sistema CQRS. Ela também aponta a condição que favorece o desenho: um domínio conectado, em que processar uma transação pode mudar o resultado das seguintes. Quando as transações são mais independentes, processadores paralelos ficam mais atraentes.