Projetando um Matching Engine em Rust: Price-Time Priority Sem Pausas de GC

Um matching engine de exchange spot tem um trabalho estreito. Ele recebe um fluxo ordenado de comandos - nova ordem, cancelamento, substituição -, aplica-os a um order book sob price-time priority e emite um fluxo ordenado de eventos: negócios, atualizações do book, rejeições, confirmações.

Tudo que é difícil nisso vem de três restrições empilhadas sobre esse trabalho: o resultado precisa ser idêntico em cada replay da mesma entrada, o restante de uma ordem parcialmente executada precisa manter seu lugar na fila, e a cauda de latência não pode se mover quando chega uma rajada.

O order book é um índice ordenado de níveis de preço sobre filas FIFO

O book são dois lados, cada um uma coleção de níveis ordenada por preço. Um nível não é um número - é uma fila de ordens em repouso naquele preço, em ordem de chegada. O casamento toca o melhor nível constantemente e os níveis profundos raramente, então a estrutura é escolhida para esse padrão de acesso, e não pela elegância.

• Preços são inteiros em ticks, nunca ponto flutuante - um tick é a unidade do instrumento, e comparação e aritmética com inteiros são exatas
• Cada lado mantém seus níveis em ordem de preço, com o melhor preço acessível sem busca - o topo do book é lido em cada comando
• Um nível mantém uma fila FIFO de ordens em repouso, além da quantidade agregada em repouso, para que o agregado não precise ser recalculado percorrendo a fila
• As ordens ficam em um slab pré-alocado e são referenciadas por handles de índice, e a fila é intrusiva: os elos anterior e seguinte vivem dentro do próprio registro da ordem
• Um mapa separado de client order id para handle do slab torna cancelar e substituir uma busca direta, então um cancelamento nunca varre o book
• A remoção de uma fila é por handle, e não por busca - cancelar uma ordem em repouso no fundo custa o mesmo que cancelar no topo do book

A consequência das filas intrusivas e dos handles de índice é que uma ordem em repouso nunca se move na memória enquanto vive. Sua posição na fila é uma propriedade dos seus elos, e não de onde ela por acaso está - e é isso que torna as execuções parciais baratas mais adiante.

Price-time priority é um laço sobre níveis e depois sobre uma fila

Uma ordem agressiva que chega percorre o lado oposto a partir do melhor preço para dentro. Em cada nível ela percorre a fila FIFO a partir da frente. Ela para quando o preço do nível deixa de ser aceitável para a ordem que chegou ou quando a quantidade que chegou zera.

• Pegar o melhor nível do lado oposto; se o preço dele não cruzar o preço limite que chegou, parar
• Pegar a ordem da frente da fila desse nível - ela é a mais antiga naquele preço, e prioridade de tempo significa que ela executa primeiro
• A quantidade negociada é a menor das duas quantidades restantes; o preço do negócio é o preço da ordem em repouso, porque foi ela que definiu os termos
• Decrementar os dois restos, emitir o evento de negócio e decrementar o agregado do nível
• Se o resto da ordem em repouso chega a zero, desligue-a da fila e devolva seu slot no slab; se o nível ficar vazio, remova o nível
• Repetir até que a quantidade que chegou seja zero ou não reste nenhum nível aceitável

A semântica dos tipos de ordem é decidida na fronteira desse laço, e não dentro dele. Immediate-or-cancel descarta o restante em vez de deixá-lo em repouso. Fill-or-kill faz uma passada seca primeiro e ou executa por inteiro ou rejeita. Post-only rejeita se a ordem cruzaria na chegada. Manter isso fora do laço faz do laço o único lugar onde o estado do book muda.

A prevenção de self-trade, as quantidades mínimas e a validação de tick e de lote também ficam antes do laço. Uma ordem que chega ao casamento já foi provada bem formada, então o laço não tem ramos de erro para atrasá-lo ou para discordar.

Determinismo é o que torna a cauda previsível, e alocação é o que a quebra

A latência média raramente é o problema. O problema é a pior observação durante uma rajada, que é quando o engine mais importa e quando uma pausa stop-the-world tem mais chance de cair. Sob um runtime gerenciado com garbage collector, essa pausa é agendada pelo coletor e não por você, e ela cai no meio da rajada que produziu o lixo.

A alocação manual é uma versão menor do mesmo problema. Um alocador de uso geral pode percorrer free lists, tomar um lock ou pedir mais memória ao kernel, e a chamada que faz isso é a chamada que aparece na cauda. A correção é a mesma nos dois casos: não alocar no hot path, ponto.

• Registros de ordem, registros de nível e buffers de eventos vêm de arenas dimensionadas na inicialização - em regime estável, a contagem de alocações no caminho de casamento é zero
• Slots liberados voltam para uma free list dentro da arena, então um instrumento movimentado recicla a mesma memória durante toda a sessão
• As estruturas têm forma e tamanho fixos, com limites de capacidade aplicados como rejeição e não como evento de crescimento
• Os eventos de saída são escritos em um ring buffer pré-alocado que outra thread esvazia - a thread de casamento nunca bloqueia por causa de um consumidor
• A thread de casamento é a única escritora sobre o book, então não há lock no estado do book nem ambiguidade de ordenação a resolver
• As entradas são sequenciadas antes de chegar ao engine, e o número de sequência, não o horário de chegada, decide a ordem

Um engine é determinístico quando a mesma sequência de entrada produz a mesma sequência de saída, byte a byte, em outra máquina e um ano depois. Qualquer coisa que leia o relógio de parede, o escalonamento de threads ou a ordem de iteração de hash dentro do caminho de casamento quebra essa propriedade.

Portanto, os timestamps são uma entrada, e não algo que o engine lê por conta própria. O sequenciador carimba um comando quando o aceita, e o laço de casamento trata o carimbo como dado. A aleatoriedade, se for necessária, vem de um gerador com semente, e a semente faz parte do journal.

O journal é o estado do engine, e o book é um cache dele

Recuperação não é um recurso aparafusado depois que o casamento funciona. O engine escreve um journal append-only dos comandos aceitos em ordem de sequência, e o book em memória nada mais é do que o resultado de dobrar esse journal. Reconstruir depois de uma queda significa reproduzi-lo.

• Um comando é registrado no journal e persistido antes de ser casado, então uma ordem aceita não pode ser perdida por uma queda entre a confirmação e a execução
• O journal é a sequência de entrada, e não a de saída - as saídas são derivadas, e re-derivá-las é exatamente o que o replay faz
• Snapshots periódicos do book carregam o número de sequência em que foram tirados, então a recuperação carrega um snapshot e reproduz apenas a cauda do journal
• A concordância entre snapshot e replay é verificada, e não presumida: reproduzir a partir do snapshot anterior precisa reproduzir o seguinte
• O fluxo de eventos carrega os mesmos números de sequência, então os consumidores a jusante - risco, liquidação, dados de mercado - podem ser retomados de um ponto conhecido em vez de ressincronizados na mão

O engine escreve o journal, mas durabilidade é uma propriedade do caminho de armazenamento e de quantas máquinas têm o registro antes de a confirmação sair. Isso é uma decisão de replicação e de hardware, e é aí que o tempo de recuperação é de fato ganho ou perdido.

Testar é replay determinístico mais invariantes que precisam valer sempre

Determinismo é o que torna o engine testável. Como a mesma entrada dá a mesma saída, uma sessão capturada é um teste de regressão, e uma falha encontrada uma vez pode ser reproduzida exatamente em vez de caçada.

• Harness de replay: alimentar uma sequência de comandos gravada, comparar o fluxo de eventos emitido com o armazenado e falhar na primeira divergência, informando o número de sequência
• Checagens de invariantes após cada comando nos builds de teste - filas ordenadas por chegada, agregados de nível iguais à soma da sua fila, nenhum book cruzado, quantidade total conservada em cada negócio
• Testes baseados em propriedades que geram sequências de comandos aleatórias, porém bem formadas, e verificam os invariantes em vez de resultados específicos
• Um modelo de referência diferencial: uma implementação lenta e obviamente correta, com estruturas de dados ingênuas, executada sobre a mesma entrada, em que qualquer divergência é tratada como bug na versão rápida
• Fuzzing na fronteira do decodificador, onde entradas malformadas chegam de fora e onde um panic derrubaria a thread de casamento
• Medição de latência sob o formato de rajada que preocupa você, registrando a distribuição em vez de uma média, já que a cauda é o número que decide o design

O que Rust dá aqui, e o que não dá

Rust remove uma categoria de problema em vez de deixar o laço mais rápido por si só. Não há garbage collector, então nenhuma pausa é agendada pelas suas costas. O ownership faz da disciplina de escritor único algo que o compilador impõe, em vez de algo que a revisão de código precisa notar. Handles de slab e elos intrusivos, propensos a erro em uma linguagem sem lifetimes, aqui são verificáveis. Panics em overflow de inteiros nos builds de debug pegam uma classe de bug que corrompe um book silenciosamente.

O limite honesto é que a maior parte do que determina a latência de cauda não é a linguagem:

• Escalonamento do kernel, tratamento de interrupções, CPU pinning e gerenciamento de energia movem a cauda mais do que o código de casamento move
• A interface de rede, o kernel bypass ou sua ausência e o caminho físico até a venue definem um piso abaixo do qual o engine não desce
• A serialização e o protocolo de fio na fronteira são frequentemente o custo dominante, e não o casamento em si
• Semântica de casamento, tipos de ordem, regras de taxas e rebates e fases de mercado são decisões de negócio - uma regra errada implementada rápido continua errada
• Checagens de risco, limites de posição e o caminho de liquidação vivem fora do engine e têm sua própria latência e seus próprios modos de falha
• A operação - deploy, monitoramento, o runbook para um replay que falhou - decide se as garantias sobrevivem ao contato com um incidente em produção

Rust também cobra um preço. O borrow checker atrasa as primeiras semanas de um design que ainda está se movendo, o ecossistema para protocolos específicos de exchange é mais raso do que em linguagens mais antigas, e blocos unsafe em torno de estruturas lock-free exigem a mesma disciplina de revisão que o código equivalente em qualquer outro lugar. Escolhê-la é uma decisão sobre a cauda de latência e sobre segurança de memória em um núcleo de escritor único, não uma decisão sobre conforto do desenvolvedor.

A amBrain constrói infraestrutura de trading em Yerevan, na Armênia, desde 2019, com hot paths em Rust - dados de mercado entregues em menos de 5 ms, checagens de risco pré-negociação em menos de 1 ms. Se você está desenhando um matching engine e quer discutir a estrutura do book, o formato do journal ou o harness de replay, vale ter essa conversa antes da primeira linha do hot path.