Diseñar un matching engine en Rust: prioridad precio-tiempo sin pausas de GC

El matching engine de un exchange spot tiene un trabajo acotado. Toma un flujo ordenado de comandos - nueva orden, cancelación, reemplazo -, los aplica a un libro de órdenes bajo prioridad precio-tiempo y emite un flujo ordenado de eventos: operaciones, actualizaciones del libro, rechazos y acuses de recibo.

Todo lo difícil viene de tres restricciones apiladas sobre ese trabajo: el resultado debe ser idéntico en cada replay de la misma entrada, el remanente de una orden parcialmente ejecutada debe conservar su lugar en la cola, y la latencia de cola no debe moverse cuando llega una ráfaga.

El libro de órdenes es un índice ordenado de niveles de precio sobre colas FIFO

El libro son dos lados, cada uno una colección de niveles ordenada por precio. Un nivel no es un número: es una cola de órdenes en reposo a ese precio, en orden de llegada. El emparejamiento toca el mejor nivel constantemente y los niveles profundos rara vez, así que la estructura se elige por ese patrón de acceso y no por elegancia.

• Los precios son enteros en ticks, nunca coma flotante: un tick es la unidad del instrumento, y la comparación y la aritmética con enteros son exactas
• Cada lado mantiene sus niveles ordenados por precio, con el mejor precio accesible sin búsqueda: el top of book se lee en cada comando
• Un nivel mantiene una cola FIFO de órdenes en reposo, más la cantidad agregada en reposo, de modo que el agregado no tiene que recalcularse recorriendo la cola
• Las órdenes se guardan en un slab preasignado y se referencian por handles de índice, y la cola es intrusiva: los enlaces siguiente y anterior viven dentro del propio registro de la orden
• Un mapa aparte del client order id al handle del slab convierte cancel y replace en una búsqueda directa, así que una cancelación nunca recorre el libro
• La eliminación de una cola se hace por handle, no por búsqueda: cancelar una orden en reposo profunda cuesta lo mismo que cancelar en el top of book

La consecuencia de las colas intrusivas y los handles de índice es que una orden en reposo nunca se mueve en memoria mientras vive. Su posición en la cola es una propiedad de sus enlaces, no del lugar donde esté ubicada, y eso es lo que abarata las ejecuciones parciales después.

La prioridad precio-tiempo es un bucle sobre niveles y luego sobre una cola

Una orden agresiva entrante recorre el lado opuesto desde el mejor precio hacia dentro. En cada nivel recorre la cola FIFO desde el frente. Se detiene cuando el precio del nivel deja de ser aceptable para la orden entrante o cuando la cantidad entrante llega a cero.

• Tomar el mejor nivel opuesto; si su precio no cruza el precio límite entrante, parar
• Tomar la orden del frente de la cola de ese nivel: es la más antigua a ese precio, y la prioridad temporal implica que se ejecuta primero
• La cantidad negociada es la menor de las dos cantidades restantes; el precio de la operación es el precio de la orden en reposo, porque la orden en reposo fijó los términos
• Decrementar ambos remanentes, emitir el evento de operación y decrementar el agregado del nivel
• Si el remanente de la orden en reposo llega a cero, desenlazarla de la cola y devolver su slot del slab; si el nivel queda vacío, eliminar el nivel
• Repetir hasta que la cantidad entrante sea cero o no quede ningún nivel aceptable

La semántica de los tipos de orden se decide en la frontera de este bucle, no dentro de él. Immediate-or-cancel descarta el remanente en lugar de dejarlo en reposo. Fill-or-kill hace primero una pasada en seco y o ejecuta entera o rechaza. Post-only rechaza si la orden cruzaría al llegar. Mantener esto fuera del bucle hace que el bucle siga siendo el único sitio donde cambia el estado del libro.

La prevención de self-trade, las cantidades mínimas y la validación de tick y lote también van antes del bucle. Una orden que llega al emparejamiento ya está probada como bien formada, así que el bucle no tiene ramas de error que lo ralenticen o sobre las que discrepar.

El determinismo es lo que hace predecible la latencia de cola, y la asignación de memoria es lo que la rompe

La latencia media rara vez es el problema. El problema es la peor observación durante una ráfaga, que es cuando el engine más importa y cuando es más probable que caiga una pausa stop-the-world. Bajo un runtime gestionado con garbage collector, esa pausa la programa el recolector y no tú, y aterriza en mitad de la ráfaga que generó la basura.

La asignación manual es una versión menor del mismo problema. Un asignador de propósito general puede recorrer free lists, tomar un lock o pedir más memoria al kernel, y la llamada que lo hace es la que aparece en la cola. La solución es la misma en ambos casos: no asignar memoria en el hot path.

• Los registros de órdenes, los registros de nivel y los búferes de eventos salen de arenas dimensionadas al arranque: en régimen estacionario el número de asignaciones en la ruta de emparejamiento es cero
• Los slots liberados vuelven a una free list dentro de la arena, así que un instrumento activo recicla la misma memoria durante toda la sesión
• Las estructuras tienen forma y tamaño fijos, y los límites de capacidad se aplican como un rechazo en lugar de como un evento de crecimiento
• Los eventos salientes se escriben en un ring buffer preasignado que vacía otro hilo: el hilo de emparejamiento nunca se bloquea por un consumidor
• El hilo de emparejamiento es un único escritor sobre el libro, así que no hay lock sobre el estado del libro ni ambigüedad de orden que resolver
• Las entradas se secuencian antes de llegar al engine, y el número de secuencia, no la hora de llegada, decide el orden

Un engine es determinista cuando la misma secuencia de entrada produce la misma secuencia de salida, byte a byte, en otra máquina y un año después. Cualquier cosa dentro de la ruta de emparejamiento que lea el reloj de pared, la planificación de hilos o el orden de iteración de un hash rompe esa propiedad.

Por tanto, las marcas de tiempo son una entrada, no algo que el engine lea por su cuenta. El secuenciador sella un comando cuando lo acepta, y el bucle de emparejamiento trata el sello como un dato. La aleatoriedad, si hace falta alguna, viene de un generador con semilla, y esa semilla forma parte del journal.

El journal es el estado del engine, y el libro es una caché de él

La recuperación no es una funcionalidad añadida después de que el emparejamiento funcione. El engine escribe un journal append-only de comandos aceptados en orden de secuencia, y el libro en memoria no es más que el resultado de plegar ese journal. Reconstruir tras una caída significa reproducirlo.

• Un comando se registra en el journal y es duradero antes de emparejarse, así que una orden aceptada no puede perderse por una caída entre el acuse de recibo y la ejecución
• El journal es la secuencia de entrada, no la de salida: las salidas son derivadas, y volver a derivarlas es exactamente lo que hace el replay
• Los snapshots periódicos del libro llevan el número de secuencia en el que se tomaron, así que la recuperación carga un snapshot y reproduce solo la cola del journal
• La concordancia entre snapshot y replay se comprueba en vez de darse por supuesta: reproducir desde el snapshot anterior debe reproducir el siguiente
• El flujo de eventos lleva los mismos números de secuencia, así que los consumidores aguas abajo - riesgo, liquidación, datos de mercado - pueden reanudarse desde un punto conocido en lugar de resincronizarse a mano

El engine escribe el journal, pero la durabilidad es una propiedad de la ruta de almacenamiento y de cuántas máquinas tienen el registro antes de que salga el acuse de recibo. Esa es una decisión de replicación y de hardware, y ahí es donde realmente se gana o se pierde el tiempo de recuperación.

Las pruebas son replay determinista más invariantes que deben cumplirse siempre

El determinismo es lo que hace testeable el engine. Como la misma entrada da la misma salida, una sesión capturada es un test de regresión, y un fallo encontrado una vez puede reproducirse exactamente en lugar de perseguirse.

• Arnés de replay: alimentar una secuencia de comandos grabada, comparar el flujo de eventos emitido con el almacenado y fallar en la primera divergencia indicando el número de secuencia
• Verificaciones de invariantes tras cada comando en las builds de test: colas ordenadas por llegada, agregados de nivel iguales a la suma de su cola, libro sin cruzar, cantidad total conservada en cada operación
• Tests basados en propiedades que generan secuencias de comandos aleatorias pero bien formadas y comprueban los invariantes en lugar de resultados concretos
• Un modelo de referencia diferencial: una implementación lenta y obviamente correcta, con estructuras de datos ingenuas, ejecutada sobre la misma entrada, donde cualquier discrepancia se trata como un fallo de la rápida
• Fuzzing en la frontera del decodificador, donde llega entrada malformada desde fuera y donde un panic tumbaría el hilo de emparejamiento
• Medición de latencia bajo la forma de ráfaga que te preocupa, registrando la distribución en lugar de una media, ya que la cola es la cifra que decide el diseño

Qué te da Rust aquí y qué no

Rust elimina una categoría de problema en lugar de hacer el bucle más rápido por sí mismo. No hay garbage collector, así que no se programa ninguna pausa a tus espaldas. La propiedad convierte la disciplina de un solo escritor en algo que impone el compilador en vez de algo que una revisión de código tiene que detectar. Los handles de slab y los enlaces intrusivos, propensos a errores en un lenguaje sin lifetimes, aquí son verificables. Los panics por desbordamiento de enteros en las builds de debug atrapan una clase de fallo que corrompe un libro en silencio.

El límite honesto es que la mayor parte de lo que determina la latencia de cola no es el lenguaje:

• La planificación del kernel, el manejo de interrupciones, el pinning de CPU y la gestión de energía mueven la latencia de cola más que el propio código de emparejamiento
• La interfaz de red, el kernel bypass o su ausencia y la ruta física hasta el venue fijan un suelo por debajo del cual el engine no puede bajar
• La serialización y el protocolo de cable en la frontera son con frecuencia el coste dominante, no el emparejamiento en sí
• La semántica de emparejamiento, los tipos de orden, las reglas de comisiones y rebates y las fases de mercado son decisiones de negocio: una regla equivocada implementada rápido sigue estando equivocada
• Las verificaciones de riesgo, los límites de posición y la ruta de liquidación viven fuera del engine y tienen su propia latencia y sus propios modos de fallo
• Las operaciones - despliegue, monitorización, el runbook para un replay fallido - deciden si las garantías sobreviven al contacto con un incidente en producción

Rust también cuesta algo. El borrow checker frena las primeras semanas de un diseño que todavía se mueve, el ecosistema de protocolos específicos de exchanges es más pobre que en lenguajes más antiguos, y los bloques unsafe alrededor de estructuras lock-free necesitan la misma disciplina de revisión que el código equivalente en cualquier otro sitio. Elegirlo es una decisión sobre la latencia de cola y sobre la seguridad de memoria en un núcleo de un solo escritor, no una decisión sobre la comodidad del desarrollador.

amBrain construye infraestructura de trading en Ereván, Armenia, desde 2019, con los hot paths en Rust: datos de mercado entregados en menos de 5 ms, verificaciones de riesgo pre-trade en menos de 1 ms. Si estás diseñando un matching engine y quieres repasar la estructura del libro, el formato del journal o el arnés de replay, esa conversación vale la pena antes de escribir la primera línea del hot path.