Construir un motor de casación de órdenes con latencia inferior al microsegundo en C++20
Cómo una estructura de datos de tres capas permite cancelaciones O(1) y latencia inferior al microsegundo.
El sistema central de cada bolsa
Toda bolsa electrónica, como NYSE, NASDAQ o CME, tiene un motor de casación en su centro. Empareja órdenes de compra y venta al mejor precio disponible. Construirlo a nivel de sistemas exige comprender la prioridad precio-tiempo, la asignación de memoria en la ruta crítica y la ingeniería de latencia inferior al microsegundo.
NanoMatch es mi implementación desde cero en C++20 moderno: procesa 1M+ órdenes por segundo en un benchmark sintético de un solo hilo, con latencia inferior al microsegundo.
La estructura de datos de tres capas
Una implementación sencilla podría usar una sola cola de prioridad. Puede encontrar el mejor precio en O(1), pero cancelar lleva O(n). En esta implementación, un índice de búsqueda directo y una cola de órdenes por nivel de precio permiten cancelar en O(1).
NanoMatch utiliza tres estructuras que cooperan:
| Capa | Estructura | Propósito |
|---|---|---|
| Niveles de precio | std::map<Price, PriceLevel> | Ordenados por precio. std::greater para compras (mayor primero), std::less para ventas (menor primero). Inserción O(log M), mejor precio O(1) mediante begin(). |
| Cola de órdenes | std::list<Order> por nivel | FIFO en cada precio. Añadir O(1), eliminar mediante iterador O(1). |
| Índice de búsqueda | std::unordered_map<OrderID, Iterator> | Cancelación O(1): la búsqueda hash devuelve un iterador de lista y el borrado es constante. |
Precios enteros para evitar errores de coma flotante
Los precios se guardan como int32_t en céntimos ($101.50 = 10150). La comparación en coma flotante (==) no es fiable por los errores de representación. En un motor de casación puede mantener separados niveles que deberían fusionarse, o cruzar órdenes al precio incorrecto. La aritmética entera hace exacta y determinista la comparación.
El asignador de memoria por pool
Cada malloc / free en la ruta crítica puede provocar llamadas al núcleo, contención de bloqueos y contaminación de caché. NanoMatch usa un asignador personalizado por pool con lista libre:
- Preasigna un
std::vector<T>contiguo de capacidad fija allocate()= extraer la cabeza de la lista libre = O(1), sin llamadas al sistemadeallocate()= añadir a la cabeza = O(1), sin llamadas al sistema- Toda la memoria reside en un único bloque contiguo favorable para la caché
El benchmark muestra que el pool elimina la variación de asignación responsable de los picos de latencia de cola.
Semántica correcta de los tipos de órdenes
Cuatro tipos de órdenes con semántica adecuada para producción:
- Limit: ejecutar lo que puede cruzarse y dejar el resto en el libro
- Market: fijar el precio en
MAX/MINpara garantizar el cruce; nunca permanece en el libro - IOC (ejecución inmediata o cancelación): como una orden limitada, pero se cancela el resto no ejecutado
- FOK (ejecución total o cancelación): una comprobación atómica con
can_fill_completely()recorre los niveles cruzables antes de ejecutar. Si falta liquidez, no se ejecuta ninguna parte
La modificación se implementa cancelando y volviendo a añadir. La orden modificada pierde su prioridad temporal, como ocurriría en NYSE o NASDAQ.
Perfil de latencia
| Percentil | Latencia |
|---|---|
| p50 | 84 ns |
| p99 | 625 ns |
| p99.9 | 1250 ns |
El resultado p99.9 es unas 15 veces el de p50. En este benchmark, los picos se debieron al reequilibrado del árbol rojo-negro al insertar un nivel de precio, a órdenes que recorren varios niveles y a fallos de caché en niveles fríos.