A evolución da arquitectura do sistema de negociación e compensación da Bolsa de Moscova. Parte 1

Ola a todos! Chámome Sergey Kostanbaev, na Bolsa estou a desenvolver o núcleo do sistema de negociación.

Cando as películas de Hollywood mostran a Bolsa de Nova York, sempre se ve así: multitude de persoas, todo o mundo está gritando algo, axitando papeis, está a suceder un caos total. Isto nunca ocorreu aquí na Bolsa de Moscova, porque a negociación realizouse electrónicamente desde o principio e baséase en dúas plataformas principais: Spectra (mercado de divisas) e ASTS (mercado de divisas, accións e diñeiro). E hoxe quero falar sobre a evolución da arquitectura do sistema de negociación e compensación ASTS, sobre varias solucións e descubrimentos. A historia será longa, así que tiven que dividila en dúas partes.

Somos unha das poucas bolsas do mundo que negocia activos de todas as clases e ofrece unha gama completa de servizos de intercambio. Por exemplo, o ano pasado ocupamos o segundo lugar mundial en volume de negociación de bonos, o posto 25 entre todas as bolsas de valores, o lugar 13 en capitalización entre as bolsas públicas.

Para os participantes comerciais profesionais, parámetros como o tempo de resposta, a estabilidade da distribución do tempo (jitter) e a fiabilidade de todo o complexo son críticos. Actualmente procesamos decenas de millóns de transaccións ao día. O procesamento de cada transacción polo núcleo do sistema leva decenas de microsegundos. Iso si, os operadores móbiles da noite de fin de ano ou os propios buscadores teñen unha carga de traballo superior á nosa, pero en canto a carga de traballo, unido ás características antes mencionadas, poucos se poden comparar con nós, paréceme. Ao mesmo tempo, é importante para nós que o sistema non se ralentice nin un segundo, funcione de forma absolutamente estable e todos os usuarios estean en igualdade de condicións.

Un pouco de historia

En 1994, o sistema australiano ASTS lanzouse na Bolsa de Moedas Interbancaria de Moscova (MICEX), e desde ese momento pódese contar a historia rusa do comercio electrónico. En 1998, a arquitectura do intercambio foi modernizada para introducir o comercio por Internet. Desde entón, a velocidade de implantación de novas solucións e cambios arquitectónicos en todos os sistemas e subsistemas non fixo máis que cobrar forza.

Naqueles anos, o sistema de intercambio funcionaba en hardware de alta gama: servidores HP Superdome 9000 ultra fiables (construídos PA-RISC), no que se duplicaba absolutamente todo: subsistemas de entrada/saída, rede, RAM (de feito, había unha matriz RAID de RAM), procesadores (intercambiables en quente). Era posible cambiar calquera compoñente do servidor sen parar a máquina. Confiamos nestes dispositivos e considerámolos practicamente seguros. O sistema operativo era un sistema HP UX parecido a Unix.

Pero desde aproximadamente 2010, xurdiu un fenómeno chamado negociación de alta frecuencia (HFT) ou negociación de alta frecuencia, simplemente, robots de bolsa. En só 2,5 anos, a carga dos nosos servidores aumentou 140 veces.

Era imposible soportar tal carga coa antiga arquitectura e equipamento. Había que adaptarse dalgún xeito.

Comezar

As solicitudes ao sistema de intercambio pódense dividir en dous tipos:

• Transaccións. Se queres comprar dólares, accións ou outra cousa, envías unha transacción ao sistema de negociación e recibes unha resposta sobre o éxito.
• Solicitudes de información. Se queres coñecer o prezo actual, consulta a carteira de pedidos ou os índices e, a continuación, envía solicitudes de información.

Esquemáticamente, o núcleo do sistema pódese dividir en tres niveis:

• O nivel do cliente, no que traballan os corredores e os clientes. Todos eles interactúan cos servidores de acceso.
• Os servidores de pasarela son servidores de caché que procesan localmente todas as solicitudes de información. Queres coñecer o prezo das accións de Sberbank? A solicitude vai ao servidor de acceso.
• Pero se queres comprar accións, a solicitude vai ao servidor central (Trade Engine). Hai un servidor deste tipo para cada tipo de mercado, xogan un papel vital, é para eles para que creamos este sistema.

O núcleo do sistema de negociación é unha intelixente base de datos en memoria na que todas as transaccións son transaccións de intercambio. A base estaba escrita en C, as únicas dependencias externas eran a biblioteca libc e non había ningunha asignación de memoria dinámica. Para reducir o tempo de procesamento, o sistema comeza cun conxunto estático de matrices e cunha reubicación de datos estáticos: primeiro, todos os datos do día actual cárganse na memoria e non se realiza ningún acceso ao disco, todo o traballo realízase só na memoria. Cando se inicia o sistema, todos os datos de referencia xa están ordenados, polo que a busca funciona de forma moi eficiente e leva pouco tempo en execución. Todas as táboas están feitas con listas e árbores intrusivas para estruturas de datos dinámicas para que non necesiten asignación de memoria no tempo de execución.

Imos repasar brevemente a historia do desenvolvemento do noso sistema de negociación e compensación.
A primeira versión da arquitectura do sistema de negociación e compensación construíuse sobre a chamada interacción Unix: utilizáronse memoria compartida, semáforos e colas, e cada proceso constaba dun único fío. Este enfoque foi xeneralizado a principios dos anos noventa.

A primeira versión do sistema contiña dous niveis de Gateway e un servidor central do sistema de negociación. O fluxo de traballo foi así:

• O cliente envía unha solicitude, que chega á pasarela. Comproba a validez do formato (pero non os propios datos) e rexeita as transaccións incorrectas.
• Se se enviou unha solicitude de información, execútase localmente; se estamos a falar dunha transacción, entón é redirixido ao servidor central.
• A continuación, o motor de negociación procesa a transacción, modifica a memoria local e envía unha resposta á transacción e á propia transacción para a súa replicación mediante un motor de replicación separado.
• A pasarela recibe a resposta do nodo central e envíaa ao cliente.
• Despois dun tempo, a Pasarela recibe a transacción a través do mecanismo de replicación, e esta vez execútaa localmente, cambiando as súas estruturas de datos para que as seguintes solicitudes de información mostren os datos máis recentes.

De feito, describe un modelo de replicación no que a Pasarela replicou completamente as accións realizadas no sistema de negociación. Unha canle de replicación separada garantiu que as transaccións se executasen na mesma orde en varios nodos de acceso.

Dado que o código era dun só fío, utilizouse un esquema clásico con forks de proceso para servir a moitos clientes. Non obstante, era moi custoso fornear toda a base de datos, polo que se utilizaron procesos de servizo lixeiros que recollían paquetes das sesións TCP e os trasladaban a unha cola (SystemV Message Queue). Gateway e Trade Engine só funcionaban con esta cola, tomando transaccións desde alí para a súa execución. Xa non era posible enviarlle unha resposta, porque non estaba claro que proceso de servizo debía lelo. Así que recorremos a un truco: cada proceso bifurcado creaba unha cola de respostas por si mesmo e, cando unha solicitude entraba na cola de entrada, engadíase inmediatamente unha etiqueta para a cola de respostas.

A copia constante de grandes cantidades de datos de cola en cola creou problemas, especialmente os típicos para as solicitudes de información. Por iso, empregamos outro truco: ademais da cola de respostas, cada proceso tamén creaba memoria compartida (SystemV Shared Memory). Os propios paquetes colocáronse nel e só se gardou unha etiqueta na cola, o que permitía atopar o paquete orixinal. Isto axudou a almacenar datos na caché do procesador.

SystemV IPC inclúe utilidades para ver o estado da cola, a memoria e os obxectos semáforos. Utilizamos isto activamente para comprender o que estaba a suceder no sistema nun momento determinado, onde se acumulaban os paquetes, que estaba bloqueado, etc.

Primeiras modernizacións

Primeiro de todo, desfixémonos da pasarela dun só proceso. O seu inconveniente importante era que podía xestionar unha transacción de replicación ou unha solicitude de información dun cliente. E a medida que aumenta a carga, Gateway tardará máis en procesar as solicitudes e non poderá procesar o fluxo de replicación. Ademais, se o cliente enviou unha transacción, só tes que comprobar a súa validez e reenviala. Polo tanto, substituímos o proceso de pasarela único por varios compoñentes que poden executarse en paralelo: información multiproceso e procesos de transacción que se executan de forma independente uns dos outros nunha área de memoria compartida mediante o bloqueo RW. E ao mesmo tempo introducimos procesos de despacho e replicación.

Impacto do comercio de alta frecuencia

A versión anterior da arquitectura existiu ata 2010. Mentres tanto, xa non estabamos satisfeitos co rendemento dos servidores HP Superdome. Ademais, a arquitectura PA-RISC estaba practicamente morta; o vendedor non ofreceu ningunha actualización significativa. Como resultado, comezamos a pasar de HP UX/PA RISC a Linux/x86. A transición comezou coa adaptación dos servidores de acceso.

Por que tivemos que cambiar de novo a arquitectura? O feito é que o comercio de alta frecuencia cambiou significativamente o perfil de carga no núcleo do sistema.

Digamos que temos unha pequena transacción que causou un cambio significativo de prezo: alguén comprou medio billón de dólares. Despois dun par de milisegundos, todos os participantes no mercado notan isto e comezan a facer unha corrección. Por suposto, as solicitudes alíñanse nunha enorme cola, que o sistema tardará moito en borrar.

Neste intervalo de 50 ms, a velocidade media é de aproximadamente 16 mil transaccións por segundo. Se reducimos a xanela a 20 ms, obtemos unha velocidade media de 90 mil transaccións por segundo, con 200 mil transaccións no pico. Noutras palabras, a carga non é constante, con ráfagas bruscas. E a cola de solicitudes sempre debe ser procesada rapidamente.

Pero por que hai unha cola? Así, no noso exemplo, moitos usuarios notaron o cambio de prezo e enviaron transaccións en consecuencia. Chegan a Gateway, serialízaos, establece unha determinada orde e envíaos á rede. Os enrutadores barallan os paquetes e reenvíaos. Cuxo paquete chegou primeiro, esa transacción "gañaba". Como resultado, os clientes de intercambio comezaron a notar que se se envía a mesma transacción desde varias pasarelas, as posibilidades de procesamento rápido aumentaron. Pronto, os robots de intercambio comezaron a bombardear Gateway con solicitudes e xurdiu unha avalancha de transaccións.

Unha nova rolda de evolución

Despois de extensas probas e investigacións, cambiamos ao núcleo do sistema operativo en tempo real. Para iso escollemos RedHat Enterprise MRG Linux, onde MRG significa reixa de mensaxes en tempo real. A vantaxe dos parches en tempo real é que optimizan o sistema para a execución máis rápida posible: todos os procesos están aliñados nunha cola FIFO, os núcleos pódense illar, sen expulsións, todas as transaccións son procesadas nunha secuencia rigorosa.

Vermello - traballando cunha cola nun núcleo normal, verde - traballando nun núcleo en tempo real.

Pero conseguir unha baixa latencia en servidores normais non é tan sinxelo:

• O modo SMI, que na arquitectura x86 é a base para traballar con periféricos importantes, interfire moito. O procesamento de todo tipo de eventos de hardware e a xestión de compoñentes e dispositivos realízao o firmware no modo chamado SMI transparente, no que o sistema operativo non ve o que fai o firmware. Como regra xeral, todos os principais provedores ofrecen extensións especiais para servidores de firmware que permiten reducir a cantidade de procesamento SMI.
• Non debería haber control dinámico da frecuencia do procesador, isto leva a tempo de inactividade adicional.
• Cando se limpa o rexistro do sistema de ficheiros, ocorren certos procesos no núcleo que causan atrasos imprevisibles.
• Debes prestar atención a cousas como CPU Affinity, Interrupt afinity, NUMA.

Debo dicir que o tema da configuración de hardware e núcleo de Linux para o procesamento en tempo real merece un artigo aparte. Pasamos moito tempo experimentando e investigando antes de conseguir un bo resultado.

Ao pasar dos servidores PA-RISC a x86, practicamente non tivemos que cambiar moito o código do sistema, só adaptámolo e reconfiguramos. Ao mesmo tempo, corriximos varios erros. Por exemplo, as consecuencias do feito de que PA RISC fose un sistema Big endian e x86 un sistema Little endian, xurdiron rapidamente: por exemplo, os datos foron lidos incorrectamente. O erro máis complicado foi que usa PA RISC consistente coherente (Secuencialmente consistente) acceso á memoria, mentres que x86 pode reordenar as operacións de lectura, polo que o código que era absolutamente válido nunha plataforma rompeuse noutra.

Despois de cambiar a x86, o rendemento aumentou case tres veces, o tempo medio de procesamento da transacción diminuíu a 60 μs.

Vexamos agora que cambios clave se fixeron na arquitectura do sistema.

Épica de reserva quente

Ao cambiar aos servidores de produtos básicos, eramos conscientes de que eran menos fiables. Polo tanto, á hora de crear unha nova arquitectura, asumimos a priori a posibilidade de falla dun ou máis nodos. Polo tanto, era necesario un sistema de espera en quente que puidese cambiar moi rapidamente ás máquinas de copia de seguridade.

Ademais, había outros requisitos:

• En ningún caso debes perder transaccións procesadas.
• O sistema debe ser absolutamente transparente para a nosa infraestrutura.
• Os clientes non deberían ver as conexións caídas.
• As reservas non deben introducir un atraso significativo porque este é un factor crítico para o intercambio.

Ao crear un sistema de espera en quente, non consideramos tales escenarios como fallos dobres (por exemplo, a rede dun servidor deixou de funcionar e o servidor principal conxelouse); non considerou a posibilidade de erros no software porque se identifican durante as probas; e non considerou o funcionamento incorrecto do hardware.

Como resultado, chegamos ao seguinte esquema:

• O servidor principal interactuou directamente cos servidores Gateway.
• Todas as transaccións recibidas no servidor principal replicáronse instantáneamente no servidor de copia de seguridade a través dunha canle separada. O árbitro (Gobernador) coordinou o cambio se xurdía algún problema.

  

• O servidor principal procesou cada transacción e esperou a confirmación do servidor de copia de seguridade. Para manter a latencia ao mínimo, evitamos esperar a que se completase a transacción no servidor de copia de seguranza. Dado que o tempo que tardou unha transacción en viaxar pola rede era comparable ao tempo de execución, non se engadiu ningunha latencia adicional.
• Só puidemos comprobar o estado de procesamento dos servidores principais e de reserva para a transacción anterior e descoñecíase o estado de procesamento da transacción actual. Dado que aínda estabamos usando procesos dun só fío, a espera dunha resposta de Backup ralentizaría todo o fluxo de procesamento, polo que fixemos un compromiso razoable: comprobamos o resultado da transacción anterior.

O esquema funcionou do seguinte xeito.

Digamos que o servidor principal deixa de responder, pero as pasarelas continúan comunicándose. Prodúcese un tempo de espera no servidor de copia de seguridade, contacta co gobernador, que lle asigna o papel do servidor principal e todas as pasarelas cambian ao novo servidor principal.

Se o servidor principal volve estar en liña, tamén activa un tempo de espera interno, porque non houbo chamadas ao servidor desde a pasarela durante un tempo determinado. Despois recorre tamén ao Gobernador, e exclúeo do esquema. Como resultado, o intercambio funciona cun servidor ata o final do período de negociación. Dado que a probabilidade dun fallo do servidor é bastante baixa, este esquema considerouse bastante aceptable; non contiña lóxica complexa e era fácil de probar.

Continuar.

Fonte: www.habr.com