Os nosos usuarios escriben mensaxes entre eles sen saber a fatiga.
Iso é bastante. Se te propuxes ler todas as mensaxes de todos os usuarios, levaríase máis de 150 mil anos. Sempre que sexa un lector bastante avanzado e non dedique máis dun segundo a cada mensaxe.
Con tal volume de datos, é fundamental que a lóxica para almacenalos e acceder a eles estea construída de forma óptima. Se non, nun momento non tan marabilloso, pode quedar claro que todo sairá mal pronto.
Para nós, este momento chegou hai ano e medio. Como chegamos a isto e que pasou ao final, contámosche por orde.
Fondo
Na primeira implementación, as mensaxes de VKontakte funcionaron nunha combinación de backend PHP e MySQL. Esta é unha solución completamente normal para un sitio web de estudantes pequenos. Non obstante, este sitio creceu sen control e comezou a esixir a optimización das estruturas de datos por si mesmo.
A finais de 2009, escribiuse o primeiro repositorio de motor de texto, e en 2010 trasladáronse mensaxes a el.
No motor de texto, as mensaxes almacenáronse en listas, unha especie de "caixas de correo". Cada lista deste tipo está determinada por un uid: o usuario que posúe todas estas mensaxes. Unha mensaxe ten un conxunto de atributos: identificador do interlocutor, texto, anexos, etc. O identificador da mensaxe dentro da "caixa" é local_id, nunca cambia e asígnase secuencialmente para novas mensaxes. As "caixas" son independentes e non están sincronizadas entre elas dentro do motor; a comunicación entre elas prodúcese a nivel PHP. Podes ver a estrutura de datos e as capacidades do motor de texto desde dentro .
Isto foi suficiente para a correspondencia entre dous usuarios. Adiviña o que pasou despois?
En maio de 2011, VKontakte introduciu conversas con varios participantes: multichat. Para traballar con eles, creamos dous novos grupos: chats de membros e membros de chat. O primeiro almacena datos sobre chats dos usuarios, o segundo almacena datos sobre usuarios por chats. Ademais das propias listas, isto inclúe, por exemplo, o usuario que invita e a hora en que se engadiron ao chat.
"PHP, imos enviar unha mensaxe ao chat", di o usuario.
"Vamos, {username}", di PHP.
Este esquema ten desvantaxes. A sincronización aínda é responsabilidade de PHP. Os grandes chats e os usuarios que simultáneamente lles envían mensaxes son unha historia perigosa. Dado que a instancia do motor de texto depende do uid, os participantes do chat poden recibir a mesma mensaxe en momentos diferentes. Poderíase vivir con isto se o progreso se parase. Pero iso non sucederá.
A finais de 2015, lanzamos mensaxes comunitarias e, a principios de 2016, lanzamos unha API para eles. Coa chegada dos grandes chatbots nas comunidades, foi posible esquecerse da distribución uniforme da carga.
Un bo bot xera varios millóns de mensaxes ao día; mesmo os usuarios máis faladores non poden presumir diso. Isto significa que algúns casos de motor de texto, nos que vivían tales bots, comezaron a sufrir ao máximo.
Os motores de mensaxes en 2016 son 100 instancias de membros de chat e chats de membros, e 8000 motores de texto. Estaban aloxados en mil servidores, cada un con 64 GB de memoria. Como primeira medida de emerxencia, aumentamos a memoria noutros 32 GB. Estimamos as previsións. Sen cambios drásticos, isto sería suficiente para un ano máis. Debe facerse co hardware ou optimizar as propias bases de datos.
Debido á natureza da arquitectura, só ten sentido aumentar o hardware en múltiples. É dicir, polo menos duplicar o número de coches; obviamente, este é un camiño bastante caro. Imos optimizar.
Novo concepto
A esencia central do novo enfoque é o chat. Un chat ten unha lista de mensaxes relacionadas con el. O usuario ten unha lista de chats.
O mínimo necesario son dúas novas bases de datos:
- motor de chat. Este é un repositorio de vectores de chat. Cada chat ten un vector de mensaxes que se relacionan con el. Cada mensaxe ten un texto e un identificador de mensaxe único dentro do chat: chat_local_id.
- motor de usuario. Este é un almacenamento de vectores de usuarios: ligazóns a usuarios. Cada usuario ten un vector de peer_id (interlocutores - outros usuarios, multi-chat ou comunidades) e un vector de mensaxes. Cada peer_id ten un vector de mensaxes que se relacionan con el. Cada mensaxe ten un chat_local_id e un único ID de mensaxe para ese usuario: user_local_id.
Os novos clústeres comunícanse entre si mediante TCP; isto garante que a orde das solicitudes non cambie. As solicitudes e as confirmacións das mesmas están rexistradas no disco duro, polo que podemos restaurar o estado da cola en calquera momento despois dun fallo ou reinicio do motor. Dado que o motor de usuario e o motor de chat son 4 fragmentos cada un, a cola de solicitudes entre os clústeres distribuirase uniformemente (pero en realidade non hai ningunha e funciona moi rápido).
O traballo co disco nas nosas bases de datos baséase na maioría dos casos nunha combinación dun rexistro binario de cambios (binlog), instantáneas estáticas e unha imaxe parcial na memoria. Os cambios durante o día escríbense nun binlog e créase periodicamente unha instantánea do estado actual. Unha instantánea é unha colección de estruturas de datos optimizadas para os nosos propósitos. Consta dunha cabeceira (metaíndice da imaxe) e un conxunto de metarchivos. A cabeceira almacénase permanentemente na memoria RAM e indica onde buscar os datos da instantánea. Cada metarchivo inclúe datos que probablemente sexan necesarios en momentos próximos, por exemplo, relacionados cun único usuario. Cando consulta a base de datos mediante a cabeceira da instantánea, lese o metarchivo necesario e, a continuación, téñense en conta os cambios no binlog que se produciron despois de crear a instantánea. Podes ler máis sobre os beneficios deste enfoque .
Ao mesmo tempo, os datos do propio disco duro cambian só unha vez ao día - a última hora da noite en Moscova, cando a carga é mínima. Grazas a isto (sabendo que a estrutura do disco é constante ao longo do día), podemos permitirnos o luxo de substituír vectores por matrices de tamaño fixo, e debido a iso, gañar en memoria.
O envío dunha mensaxe no novo esquema ten o seguinte aspecto:
- O backend de PHP contacta co motor de usuario cunha solicitude para enviar unha mensaxe.
- user-engine envía a solicitude á instancia desexada do motor de chat, que devolve ao user-engine chat_local_id - un identificador único dunha nova mensaxe dentro deste chat. O chat_engine emite entón a mensaxe a todos os destinatarios do chat.
- user-engine recibe chat_local_id de chat-engine e devolve user_local_id a PHP, un identificador de mensaxe único para este usuario. Este identificador úsase entón, por exemplo, para traballar con mensaxes a través da API.
Pero ademais de enviar mensaxes, debes implementar algunhas cousas máis importantes:
- As sublistas son, por exemplo, as mensaxes máis recentes que ves ao abrir a lista de conversas. Mensaxes sen ler, mensaxes con etiquetas (“Importante”, “Spam”, etc.).
- Comprimir mensaxes no chat-engine
- Almacenamento de mensaxes na caché no motor de usuario
- Busca (a través de todos os diálogos e dentro dun específico).
- Actualización en tempo real (Longpolling).
- Gardando o historial para implementar a caché en clientes móbiles.
Todas as sublistas son estruturas que cambian rapidamente. Para traballar con eles utilizamos . Esta elección explícase polo feito de que na parte superior da árbore ás veces almacenamos todo un segmento de mensaxes dunha instantánea; por exemplo, despois da reindexación nocturna, a árbore consta dunha parte superior, que contén todas as mensaxes da sublista. A árbore Splay facilita a inserción no medio de tal vértice sen pensar en equilibrar. Ademais, Splay non almacena datos innecesarios, o que nos aforra memoria.
As mensaxes implican unha gran cantidade de información, principalmente texto, que é útil para poder comprimir. É importante que poidamos desarquivar con precisión mesmo unha mensaxe individual. Úsase para comprimir mensaxes coas nosas propias heurísticas -por exemplo, sabemos que nas mensaxes as palabras alternan con "non palabras" -espazos, signos de puntuación- e tamén lembramos algunhas das características do uso de símbolos para a lingua rusa.
Dado que hai moitos menos usuarios que chats, para gardar solicitudes de disco de acceso aleatorio no chat-engine, almacenamos as mensaxes na caché no user-engine.
A busca de mensaxes implícase como unha consulta diagonal desde o motor de usuario a todas as instancias do motor de chat que conteñan chats deste usuario. Os resultados combínanse no propio motor de usuario.
Ben, todos os detalles foron tidos en conta, só queda cambiar a un novo esquema -e preferiblemente sen que os usuarios se dean conta.
Migración de datos
Entón, temos un motor de texto que almacena mensaxes por usuario e dous grupos de membros de chat e chats de membros que almacenan datos sobre salas de chat múltiple e os usuarios nelas. Como pasar deste ao novo motor de usuario e motor de chat?
os chats de membros no esquema antigo utilizáronse principalmente para optimizar. Trasladamos rapidamente os datos necesarios aos membros do chat, e despois xa non participou no proceso de migración.
Fila para os membros do chat. Inclúe 100 instancias, mentres que o motor de chat ten 4 mil. Para transferir os datos, cómpre poñelos en conformidade; para iso, os membros do chat dividíronse nas mesmas 4 mil copias e, a continuación, habilitouse a lectura do binlog dos membros do chat no motor de chat.
Agora chat-engine sabe sobre o multichat dos membros do chat, pero aínda non sabe nada sobre os diálogos con dous interlocutores. Estes diálogos sitúanse no motor de texto con referencia aos usuarios. Aquí tomamos os datos "de cabeza": cada instancia do motor de chat preguntou a todas as instancias do motor de texto se tiñan o diálogo necesario.
Genial: o motor de chat sabe que chats multichat hai e sabe que diálogos hai.
Debes combinar mensaxes en chats multichat para que acabes cunha lista de mensaxes en cada chat. En primeiro lugar, chat-engine recupera de texto todas as mensaxes dos usuarios deste chat. Nalgúns casos hai bastantes (ata centos de millóns), pero salvo raras excepcións, o chat encaixa completamente na memoria RAM. Temos mensaxes sen orde, cada unha en varias copias; despois de todo, todas son extraídas de diferentes instancias de motor de texto correspondentes aos usuarios. O obxectivo é ordenar as mensaxes e desfacerse das copias que ocupan espazo innecesario.
Cada mensaxe ten unha marca de tempo que contén a hora en que foi enviada e un texto. Usamos o tempo para ordenar: colocamos punteiros ás mensaxes máis antigas dos participantes en multichat e comparamos os hash do texto das copias previstas, avanzando para aumentar a marca de tempo. É lóxico que as copias teñan o mesmo hash e marca de tempo, pero na práctica non sempre é así. Como lembras, a sincronización no esquema antigo foi realizada por PHP e, en casos raros, o tempo de envío da mesma mensaxe difería entre os diferentes usuarios. Nestes casos, permitímonos editar a marca de tempo, normalmente nun segundo. O segundo problema é a diferente orde de mensaxes para os distintos destinatarios. Nestes casos, permitimos a creación dunha copia adicional, con diferentes opcións de pedido para diferentes usuarios.
Despois diso, os datos sobre as mensaxes en multichat envíanse ao motor de usuario. E aquí vén unha característica desagradable das mensaxes importadas. No funcionamento normal, as mensaxes que chegan ao motor ordénanse estrictamente en orde ascendente por user_local_id. As mensaxes importadas do motor antigo ao motor de usuario perderon esta propiedade útil. Ao mesmo tempo, para a comodidade das probas, cómpre poder acceder a eles rapidamente, buscar algo neles e engadir outros novos.
Usamos unha estrutura de datos especial para almacenar mensaxes importadas.
Representa un vector de tamaño onde están todos - son diferentes e están ordenados en orde descendente, cunha orde especial de elementos. En cada segmento con índices os elementos están ordenados. Buscar un elemento nunha estrutura deste tipo leva tempo través procuras binarias. A adición dun elemento amortizarase .
Entón, descubrimos como transferir datos de motores antigos a outros novos. Pero este proceso leva varios días, e é improbable que durante estes días os nosos usuarios renuncien ao hábito de escribirse entre eles. Para non perder mensaxes durante este tempo, cambiamos a un esquema de traballo que utiliza clústeres antigos e novos.
Os datos escríbense para os membros do chat e o motor de usuario (e non para o motor de texto, como no funcionamento normal segundo o esquema antigo). user-engine envía a solicitude a chat-engine e aquí o comportamento depende de se este chat xa se fusionou ou non. Se o chat aínda non se fusionou, o motor de chat non escribe a mensaxe para si mesmo e o seu procesamento só ocorre no motor de texto. Se o chat xa se fusionou con chat-engine, devolve chat_local_id ao user-engine e envía a mensaxe a todos os destinatarios. user-engine envía todos os datos ao motor de texto, de xeito que se ocorre algo, sempre podemos retroceder, tendo todos os datos actuais no motor antigo. text-engine devolve user_local_id, que o usuario-motor almacena e volve ao backend.
Como resultado, o proceso de transición ten o seguinte aspecto: conectamos clústeres baleiros de motor de usuario e de chat. chat-engine le todo o binlog dos membros do chat, despois comeza o proxy segundo o esquema descrito anteriormente. Transferimos os datos antigos e obtemos dous clústeres sincronizados (antigo e novo). Todo o que queda é cambiar a lectura de motor de texto a motor de usuario e desactivar o proxy.
Descubrimentos
Grazas ao novo enfoque, melloráronse todas as métricas de rendemento dos motores e resolvéronse os problemas coa coherencia dos datos. Agora podemos implementar rapidamente novas funcións nas mensaxes (e xa comezamos a facelo: aumentamos o número máximo de participantes no chat, implementamos unha busca de mensaxes reenviadas, lanzamos mensaxes fixadas e aumentamos o límite do número total de mensaxes por usuario) .
Os cambios na lóxica son realmente enormes. E gustaríame sinalar que isto non sempre significa anos enteiros de desenvolvemento por parte dun equipo enorme e infinidade de liñas de código. chat-engine e user-engine xunto con todas as historias adicionais como Huffman para a compresión de mensaxes, árbores Splay e estrutura para as mensaxes importadas ten menos de 20 mil liñas de código. E foron escritos por 3 desenvolvedores en só 10 meses (non obstante, convén ter en conta que - campións do mundo ).
Ademais, en lugar de duplicar o número de servidores, reducimos o seu número á metade; agora o motor de usuario e o motor de chat viven en 500 máquinas físicas, mentres que o novo esquema ten un gran espazo de carga. Aforramos moito diñeiro en equipos: uns 5 millóns de dólares + 750 mil dólares ao ano en gastos operativos.
Esforzámonos por atopar as mellores solucións para os problemas máis complexos e a gran escala. Temos moitos deles, e por iso buscamos desenvolvedores talentosos no departamento de bases de datos. Se che gusta e sabes como resolver este tipo de problemas, tes un excelente coñecemento de algoritmos e estruturas de datos, convidámoste a unirte ao equipo. Contacta co noso para os detalles.
Aínda que esta historia non sexa sobre ti, ten en conta que valoramos as recomendacións. Cóntalle a un amigo , e se completa con éxito o período de proba, recibirá unha bonificación de 100 mil rublos.
Fonte: www.habr.com