Nuestros usuarios se escriben mensajes entre sí sin sentir fatiga.
Eso es bastante. Si nos propusiéramos leer todos los mensajes de todos los usuarios, tardaríamos más de 150 mil años. Siempre que seas un lector bastante avanzado y no dediques más de un segundo a cada mensaje.
Con tal volumen de datos, es fundamental que la lógica para almacenarlos y acceder a ellos se construya de manera óptima. De lo contrario, en un momento no tan maravilloso, puede quedar claro que pronto todo saldrá mal.
Para nosotros, este momento llegó hace un año y medio. Cómo llegamos a esto y qué pasó al final, te lo contamos en orden.
Fondo
En la primera implementación, los mensajes de VKontakte funcionaban en una combinación de backend PHP y MySQL. Esta es una solución completamente normal para un sitio web de estudiantes pequeños. Sin embargo, este sitio creció descontroladamente y empezó a exigir la optimización de las estructuras de datos.
A finales de 2009, se escribió el primer repositorio de motor de texto y en 2010 se transfirieron mensajes a él.
En el motor de texto, los mensajes se almacenaban en listas, una especie de "buzones de correo". Cada una de estas listas está determinada por un uid: el usuario propietario de todos estos mensajes. Un mensaje tiene un conjunto de atributos: identificador del interlocutor, texto, archivos adjuntos, etc. El identificador de mensaje dentro del “cuadro” es local_id, nunca cambia y se asigna secuencialmente para mensajes nuevos. Las “cajas” son independientes y no están sincronizadas entre sí dentro del motor, la comunicación entre ellas se produce a nivel de PHP. Puede observar la estructura de datos y las capacidades del motor de texto desde adentro. .
Esto fue suficiente para la correspondencia entre dos usuarios. ¿Adivina qué pasó después?
En mayo de 2011, VKontakte introdujo conversaciones con varios participantes: el chat múltiple. Para trabajar con ellos, creamos dos nuevos grupos: chats de miembros y miembros de chat. El primero almacena datos sobre los chats de los usuarios, el segundo almacena datos sobre los usuarios por chats. Además de las listas en sí, esto incluye, por ejemplo, el usuario que invita y la hora en que se agregó al chat.
“PHP, enviemos un mensaje al chat”, dice el usuario.
"Vamos, {nombre de usuario}", dice PHP.
Este esquema tiene desventajas. La sincronización sigue siendo responsabilidad de PHP. Los chats grandes y los usuarios que les envían mensajes simultáneamente son una historia peligrosa. Dado que la instancia del motor de texto depende del uid, los participantes del chat podrían recibir el mismo mensaje en diferentes momentos. Se podría vivir con esto si el progreso se detuviera. Pero eso no sucederá.
A finales de 2015 lanzamos mensajes comunitarios y, a principios de 2016, lanzamos una API para ellos. Con la llegada de los grandes chatbots a las comunidades, fue posible olvidarse de la distribución uniforme de la carga.
Un buen bot genera varios millones de mensajes al día; ni siquiera los usuarios más conversadores pueden presumir de ello. Esto significa que algunas instancias del motor de texto, en el que vivían estos bots, comenzaron a sufrir al máximo.
Los motores de mensajes en 2016 son 100 instancias de miembros de chat y chats de miembros, y 8000 motores de texto. Estaban alojados en mil servidores, cada uno con 64 GB de memoria. Como primera medida de emergencia, aumentamos la memoria en otros 32 GB. Estimamos las previsiones. Sin cambios drásticos, esto sería suficiente para aproximadamente un año más. Necesita hacerse con el hardware u optimizar las bases de datos.
Debido a la naturaleza de la arquitectura, sólo tiene sentido aumentar el hardware en múltiplos. Es decir, al menos duplicar el número de coches; obviamente, este es un camino bastante caro. Optimizaremos.
Nuevo concepto
La esencia central del nuevo enfoque es el chat. Un chat tiene una lista de mensajes relacionados con él. El usuario tiene una lista de chats.
El mínimo requerido son dos nuevas bases de datos:
- motor de chat. Este es un repositorio de vectores de chat. Cada chat tiene un vector de mensajes relacionados con él. Cada mensaje tiene un texto y un identificador de mensaje único dentro del chat: chat_local_id.
- motor de usuario. Este es un almacenamiento de vectores de usuarios: enlaces a usuarios. Cada usuario tiene un vector de peer_id (interlocutores - otros usuarios, multichat o comunidades) y un vector de mensajes. Cada peer_id tiene un vector de mensajes relacionados con él. Cada mensaje tiene un chat_local_id y un ID de mensaje único para ese usuario: user_local_id.
Los nuevos clústeres se comunican entre sí mediante TCP; esto garantiza que el orden de las solicitudes no cambie. Las solicitudes en sí y sus confirmaciones se registran en el disco duro, por lo que podemos restaurar el estado de la cola en cualquier momento después de una falla o un reinicio del motor. Dado que el motor de usuario y el motor de chat tienen 4 mil fragmentos cada uno, la cola de solicitudes entre los clústeres se distribuirá de manera uniforme (pero en realidad no hay ninguna, y funciona muy rápidamente).
Trabajar con disco en nuestras bases de datos en la mayoría de los casos se basa en una combinación de un registro binario de cambios (binlog), instantáneas estáticas y una imagen parcial en la memoria. Los cambios durante el día se escriben en un binlog y periódicamente se crea una instantánea del estado actual. Una instantánea es una colección de estructuras de datos optimizadas para nuestros propósitos. Consta de un encabezado (metaindex de la imagen) y un conjunto de metarchivos. El encabezado se almacena permanentemente en la RAM e indica dónde buscar datos de la instantánea. Cada metarchivo incluye datos que probablemente se necesitarán en momentos cercanos (por ejemplo, relacionados con un solo usuario). Cuando consulta la base de datos utilizando el encabezado de la instantánea, se lee el metarchivo requerido y luego se tienen en cuenta los cambios en el binlog que ocurrieron después de que se creó la instantánea. Puede leer más sobre los beneficios de este enfoque. .
Al mismo tiempo, los datos del disco duro cambian solo una vez al día, a altas horas de la noche en Moscú, cuando la carga es mínima. Gracias a esto (sabiendo que la estructura del disco es constante a lo largo del día), podemos permitirnos reemplazar los vectores con matrices de un tamaño fijo y, gracias a esto, ganar memoria.
Enviar un mensaje en el nuevo esquema se ve así:
- El backend de PHP se pone en contacto con el motor de usuario con una solicitud para enviar un mensaje.
- user-engine envía la solicitud a la instancia de chat-engine deseada, que regresa a user-engine chat_local_id, un identificador único de un nuevo mensaje dentro de este chat. Luego, chat_engine transmite el mensaje a todos los destinatarios del chat.
- user-engine recibe chat_local_id de chat-engine y devuelve user_local_id a PHP, un identificador de mensaje único para este usuario. Este identificador se utiliza, por ejemplo, para trabajar con mensajes a través de la API.
Pero además de enviar mensajes, debes implementar algunas cosas más importantes:
- Las sublistas son, por ejemplo, los mensajes más recientes que ves al abrir la lista de conversaciones. Mensajes no leídos, mensajes con etiquetas (“Importante”, “Spam”, etc.).
- Comprimir mensajes en el motor de chat
- Almacenamiento en caché de mensajes en el motor de usuario
- Buscar (a través de todos los cuadros de diálogo y dentro de uno específico).
- Actualización en tiempo real (Longpolling).
- Guardar historial para implementar el almacenamiento en caché en clientes móviles.
Todas las sublistas son estructuras que cambian rápidamente. Para trabajar con ellos utilizamos . Esta elección se explica por el hecho de que en la parte superior del árbol a veces almacenamos un segmento completo de mensajes de una instantánea; por ejemplo, después de la reindexación nocturna, el árbol consta de una parte superior, que contiene todos los mensajes de la sublista. El árbol Splay facilita la inserción en el medio de dicho vértice sin tener que pensar en el equilibrio. Además, Splay no almacena datos innecesarios, lo que nos ahorra memoria.
Los mensajes implican una gran cantidad de información, mayoritariamente texto, que resulta útil poder comprimir. Es importante que podamos desarchivar con precisión incluso un mensaje individual. Se utiliza para comprimir mensajes. con nuestra propia heurística; por ejemplo, sabemos que en los mensajes las palabras se alternan con "no palabras" (espacios, signos de puntuación) y también recordamos algunas de las características del uso de símbolos para el idioma ruso.
Dado que hay muchos menos usuarios que chats, para guardar solicitudes de disco de acceso aleatorio en el motor de chat, almacenamos en caché los mensajes en el motor de usuario.
La búsqueda de mensajes se implementa como una consulta diagonal desde el motor de usuario a todas las instancias del motor de chat que contienen chats de este usuario. Los resultados se combinan en el propio motor de usuario.
Bueno, se han tenido en cuenta todos los detalles, solo queda cambiar al nuevo esquema, y preferiblemente sin que los usuarios se den cuenta.
Migración de datos
Entonces, tenemos un motor de texto que almacena mensajes por usuario y dos grupos de miembros de chat y chats de miembros que almacenan datos sobre salas de chat múltiple y los usuarios en ellas. ¿Cómo pasar de esto al nuevo motor de usuario y motor de chat?
Los chats de miembros en el esquema anterior se usaban principalmente para optimización. Rápidamente transferimos los datos necesarios a los miembros del chat y luego ya no participó en el proceso de migración.
Cola para miembros del chat. Incluye 100 instancias, mientras que el motor de chat tiene 4 mil. Para transferir los datos, es necesario ponerlos en conformidad; para esto, los miembros del chat se dividieron en las mismas 4 mil copias y luego se habilitó la lectura del binlog de los miembros del chat en el motor de chat.
Ahora el motor de chat conoce el chat múltiple de los miembros del chat, pero aún no sabe nada sobre los diálogos con dos interlocutores. Estos diálogos se encuentran en el motor de texto con referencia a los usuarios. Aquí tomamos los datos “de frente”: cada instancia del motor de chat preguntó a todas las instancias del motor de texto si tenían el diálogo que necesitaban.
Genial: el motor de chat sabe qué chats de chat múltiple hay y qué diálogos hay.
Debes combinar mensajes en chats de múltiples chats para terminar con una lista de mensajes en cada chat. Primero, el motor de chat recupera del motor de texto todos los mensajes de usuario de este chat. En algunos casos hay bastantes (hasta cientos de millones), pero con muy raras excepciones el chat cabe completamente en la RAM. Tenemos mensajes desordenados, cada uno en varias copias; después de todo, todos se extraen de diferentes instancias del motor de texto correspondientes a los usuarios. El objetivo es ordenar los mensajes y deshacerse de las copias que ocupan espacio innecesario.
Cada mensaje tiene una marca de tiempo que contiene la hora en que se envió y el texto. Usamos el tiempo para ordenar: colocamos punteros a los mensajes más antiguos de los participantes del multichat y comparamos hashes del texto de las copias deseadas, avanzando hacia una marca de tiempo cada vez mayor. Es lógico que las copias tengan el mismo hash y marca de tiempo, pero en la práctica no siempre es así. Como recordará, la sincronización en el esquema antiguo se realizaba mediante PHP y, en casos raros, el momento de enviar el mismo mensaje difería entre diferentes usuarios. En estos casos, nos permitimos editar la marca de tiempo, normalmente en un segundo. El segundo problema es el orden diferente de los mensajes para distintos destinatarios. En tales casos, permitimos que se creara una copia adicional, con diferentes opciones de pedido para diferentes usuarios.
Después de esto, los datos sobre los mensajes en multichat se envían al motor de usuario. Y aquí viene una característica desagradable de los mensajes importados. En funcionamiento normal, los mensajes que llegan al motor se ordenan estrictamente en orden ascendente según user_local_id. Los mensajes importados del motor antiguo al motor de usuario perdieron esta útil propiedad. Al mismo tiempo, para facilitar las pruebas, es necesario poder acceder a ellos rápidamente, buscar algo en ellos y agregar otros nuevos.
Utilizamos una estructura de datos especial para almacenar mensajes importados.
Representa un vector de tamaño. donde está todo el mundo - son diferentes y ordenados en orden descendente, con un orden especial de elementos. En cada segmento con índices. Los elementos están ordenados. Buscar un elemento en una estructura de este tipo lleva tiempo a través de búsquedas binarias. La incorporación de un elemento se amortiza en .
Entonces, descubrimos cómo transferir datos de motores antiguos a otros nuevos. Pero este proceso lleva varios días y es poco probable que durante estos días nuestros usuarios abandonen la costumbre de escribirse entre sí. Para no perder mensajes durante este tiempo, cambiamos a un esquema de trabajo que utiliza clústeres nuevos y antiguos.
Los datos se escriben en los miembros del chat y en el motor de usuario (y no en el motor de texto, como en el funcionamiento normal según el esquema anterior). user-engine envía la solicitud a chat-engine, y aquí el comportamiento depende de si este chat ya se ha fusionado o no. Si el chat aún no se ha fusionado, el motor de chat no se escribe el mensaje a sí mismo y su procesamiento se produce únicamente en el motor de texto. Si el chat ya se ha fusionado con el motor de chat, devuelve chat_local_id al motor de usuario y envía el mensaje a todos los destinatarios. user-engine envía todos los datos al motor de texto, de modo que si sucede algo, siempre podemos retroceder y tener todos los datos actuales en el motor anterior. text-engine devuelve user_local_id, que user-engine almacena y devuelve al backend.
Como resultado, el proceso de transición se ve así: conectamos grupos vacíos de motor de usuario y motor de chat. chat-engine lee todo el binlog de los miembros del chat y luego comienza el proxy de acuerdo con el esquema descrito anteriormente. Transferimos los datos antiguos y obtenemos dos clústeres sincronizados (antiguo y nuevo). Todo lo que queda es cambiar la lectura del motor de texto al motor de usuario y desactivar el proxy.
resultados
Gracias al nuevo enfoque, se mejoraron todas las métricas de rendimiento de los motores y se resolvieron los problemas con la coherencia de los datos. Ahora podemos implementar rápidamente nuevas funciones en los mensajes (y ya hemos comenzado a hacerlo: aumentamos el número máximo de participantes en el chat, implementamos una búsqueda de mensajes reenviados, lanzamos mensajes fijados y aumentamos el límite en el número total de mensajes por usuario) .
Los cambios en la lógica son verdaderamente enormes. Y me gustaría señalar que esto no siempre significa años enteros de desarrollo por parte de un gran equipo y miles de líneas de código. El motor de chat y el motor de usuario junto con todas las historias adicionales como Huffman para la compresión de mensajes, árboles de Splay y estructura para mensajes importados tienen menos de 20 mil líneas de código. Y fueron escritos por 3 desarrolladores en solo 10 meses (sin embargo, vale la pena tener en cuenta que - campeones del mundo ).
Además, en lugar de duplicar el número de servidores, los redujimos a la mitad: ahora el motor de usuario y el motor de chat viven en 500 máquinas físicas, mientras que el nuevo esquema tiene un gran margen de carga. Ahorramos mucho dinero en equipos: alrededor de 5 millones de dólares + 750 dólares al año en gastos operativos.
Nos esforzamos por encontrar las mejores soluciones para los problemas más complejos y de mayor escala. Tenemos muchos de ellos y por eso buscamos desarrolladores talentosos en el departamento de bases de datos. Si amas y sabes cómo resolver este tipo de problemas, tienes un excelente conocimiento de algoritmos y estructuras de datos, te invitamos a unirte al equipo. Contacta con nuestro para detalles.
Incluso si esta historia no es sobre usted, tenga en cuenta que valoramos las recomendaciones. Cuéntale a un amigo sobre , y si completa con éxito el período de prueba, recibirá una bonificación de 100 mil rublos.
Fuente: habr.com