Nos utilisateurs s’écrivent des messages sans connaître la fatigue.
C'est beaucoup. Si vous décidiez de lire tous les messages de tous les utilisateurs, cela prendrait plus de 150 XNUMX ans. À condition que vous soyez un lecteur assez avancé et que vous ne consacriez pas plus d’une seconde à chaque message.
Avec un tel volume de données, il est essentiel que la logique de stockage et d’accès soit construite de manière optimale. Sinon, à un moment pas si merveilleux, il pourrait devenir évident que tout va bientôt mal tourner.
Pour nous, ce moment est arrivé il y a un an et demi. Comment nous en sommes arrivés là et ce qui s'est passé à la fin - nous vous le disons dans l'ordre.
Contexte
Lors de la toute première implémentation, les messages VKontakte fonctionnaient sur une combinaison de backend PHP et MySQL. C’est une solution tout à fait normale pour un petit site étudiant. Cependant, ce site s'est développé de manière incontrôlable et a commencé à exiger une optimisation des structures de données pour lui-même.
Fin 2009, le premier référentiel de moteur de texte a été écrit et en 2010 les messages y ont été transférés.
Dans le moteur de texte, les messages étaient stockés dans des listes - des sortes de « boîtes aux lettres ». Chacune de ces listes est déterminée par un uid - l'utilisateur qui possède tous ces messages. Un message possède un ensemble d'attributs : identifiant de l'interlocuteur, texte, pièces jointes, etc. L'identifiant du message à l'intérieur de la « boîte » est local_id, il ne change jamais et est attribué séquentiellement pour les nouveaux messages. Les « boîtes » sont indépendantes et ne sont pas synchronisées entre elles à l’intérieur du moteur ; la communication entre elles se fait au niveau PHP. Vous pouvez examiner la structure des données et les capacités du moteur de texte de l'intérieur .
C'était largement suffisant pour la correspondance entre deux utilisateurs. Devinez ce qui s'est passé ensuite ?
En mai 2011, VKontakte a introduit des conversations avec plusieurs participants : le multi-chat. Pour travailler avec eux, nous avons créé deux nouveaux clusters : les chats membres et les membres du chat. Le premier stocke les données sur les chats par les utilisateurs, le second stocke les données sur les utilisateurs par chats. En plus des listes elles-mêmes, cela inclut, par exemple, l'utilisateur invitant et l'heure à laquelle il a été ajouté au chat.
"PHP, envoyons un message au chat", dit l'utilisateur.
"Allez, {username}", dit PHP.
Ce schéma présente des inconvénients. La synchronisation reste sous la responsabilité de PHP. Les grands chats et les utilisateurs qui leur envoient simultanément des messages sont une histoire dangereuse. Étant donné que l'instance du moteur de texte dépend de l'UID, les participants au chat peuvent recevoir le même message à des moments différents. On pourrait vivre avec cela si les progrès s’arrêtaient. Mais cela n'arrivera pas.
Fin 2015, nous avons lancé des messages communautaires et début 2016, nous avons lancé une API pour eux. Avec l'avènement des grands chatbots dans les communautés, il était possible d'oublier la répartition uniforme de la charge.
Un bon bot génère plusieurs millions de messages par jour – même les utilisateurs les plus bavards ne peuvent pas s'en vanter. Cela signifie que certaines instances du moteur de texte sur lequel vivaient ces robots ont commencé à souffrir pleinement.
Les moteurs de messages en 2016 sont constitués de 100 instances de membres de chat et de chats de membres, et de 8000 64 moteurs de texte. Ils étaient hébergés sur un millier de serveurs dotés chacun de 32 Go de mémoire. Comme première mesure d'urgence, nous avons augmenté la mémoire de XNUMX Go supplémentaires. Nous avons estimé les prévisions. Sans changements radicaux, cela suffirait pour encore environ un an. Vous devez soit vous procurer du matériel, soit optimiser les bases de données elles-mêmes.
En raison de la nature de l’architecture, il est logique d’augmenter le matériel par multiples. C'est-à-dire au moins doubler le nombre de voitures - c'est évidemment une voie assez coûteuse. Nous allons optimiser.
Nouveau concept
L'essence centrale de la nouvelle approche est le chat. Un chat contient une liste de messages qui s'y rapportent. L'utilisateur dispose d'une liste de discussions.
Le minimum requis est de deux nouvelles bases de données :
- moteur de chat. Il s'agit d'un référentiel de vecteurs de discussion. Chaque chat dispose d'un vecteur de messages qui s'y rapportent. Chaque message a un texte et un identifiant de message unique dans le chat - chat_local_id.
- moteur utilisateur. Il s'agit d'un stockage de vecteurs d'utilisateurs - liens vers les utilisateurs. Chaque utilisateur dispose d'un vecteur de peer_id (interlocuteurs - autres utilisateurs, multi-chat ou communautés) et d'un vecteur de messages. Chaque peer_id possède un vecteur de messages qui lui sont liés. Chaque message a un chat_local_id et un ID de message unique pour cet utilisateur - user_local_id.
Les nouveaux clusters communiquent entre eux via TCP, ce qui garantit que l'ordre des requêtes ne change pas. Les demandes elles-mêmes et leurs confirmations sont enregistrées sur le disque dur - nous pouvons donc restaurer l'état de la file d'attente à tout moment après une panne ou un redémarrage du moteur. Étant donné que le moteur utilisateur et le moteur de discussion contiennent chacun 4 XNUMX fragments, la file d'attente des requêtes entre les clusters sera répartie uniformément (mais en réalité, il n'y en a pas du tout - et cela fonctionne très rapidement).
L'utilisation du disque dans nos bases de données repose dans la plupart des cas sur une combinaison d'un journal binaire des modifications (binlog), d'instantanés statiques et d'une image partielle en mémoire. Les modifications apportées au cours de la journée sont écrites dans un journal binaire et un instantané de l'état actuel est périodiquement créé. Un instantané est un ensemble de structures de données optimisées pour nos besoins. Il se compose d'un en-tête (métaindex de l'image) et d'un ensemble de métafichiers. L'en-tête est stocké en permanence dans la RAM et indique où rechercher les données de l'instantané. Chaque métafichier comprend des données susceptibles d'être nécessaires à des moments rapprochés, par exemple liées à un seul utilisateur. Lorsque vous interrogez la base de données à l'aide de l'en-tête de l'instantané, le métafichier requis est lu, puis les modifications apportées au journal binaire survenues après la création de l'instantané sont prises en compte. Vous pouvez en savoir plus sur les avantages de cette approche .
Dans le même temps, les données sur le disque dur lui-même ne changent qu'une fois par jour - tard dans la nuit à Moscou, lorsque la charge est minime. Grâce à cela (sachant que la structure sur le disque est constante tout au long de la journée), on peut se permettre de remplacer les vecteurs par des tableaux de taille fixe - et de ce fait, gagner en mémoire.
L'envoi d'un message dans le nouveau schéma ressemble à ceci :
- Le backend PHP contacte le moteur utilisateur avec une demande d'envoi d'un message.
- Le moteur utilisateur transmet la demande à l'instance de moteur de chat souhaitée, qui renvoie à chat_local_id du moteur utilisateur - un identifiant unique d'un nouveau message dans ce chat. Le chat_engine diffuse ensuite le message à tous les destinataires du chat.
- user-engine reçoit chat_local_id de chat-engine et renvoie user_local_id à PHP - un identifiant de message unique pour cet utilisateur. Cet identifiant est ensuite utilisé, par exemple, pour travailler avec des messages via l'API.
Mais en plus d’envoyer des messages, vous devez mettre en œuvre quelques éléments plus importants :
- Les sous-listes sont, par exemple, les messages les plus récents que vous voyez lors de l'ouverture de la liste de conversations. Messages non lus, messages avec balises (« Important », « Spam », etc.).
- Compression des messages dans le moteur de chat
- Mise en cache des messages dans le moteur utilisateur
- Rechercher (dans toutes les boîtes de dialogue et dans une boîte de dialogue spécifique).
- Mise à jour en temps réel (Longpolling).
- Sauvegarde de l'historique pour implémenter la mise en cache sur les clients mobiles.
Toutes les sous-listes changent rapidement de structure. Pour travailler avec eux, nous utilisons . Ce choix s'explique par le fait qu'en haut de l'arborescence on stocke parfois tout un segment de messages d'un instantané - par exemple, après réindexation nocturne, l'arborescence se compose d'un seul sommet, qui contient tous les messages de la sous-liste. L'arbre Splay permet de s'insérer facilement au milieu d'un tel sommet sans avoir à penser à l'équilibrage. De plus, Splay ne stocke pas de données inutiles, ce qui nous permet d'économiser de la mémoire.
Les messages impliquent une grande quantité d’informations, principalement du texte, qu’il est utile de pouvoir compresser. Il est important que nous puissions désarchiver avec précision ne serait-ce qu'un seul message individuel. Utilisé pour compresser les messages avec notre propre heuristique - par exemple, nous savons que dans les messages les mots alternent avec des « non-mots » - espaces, signes de ponctuation - et nous nous souvenons également de certaines des particularités de l'utilisation de symboles pour la langue russe.
Puisqu'il y a beaucoup moins d'utilisateurs que de chats, pour enregistrer les demandes de disque à accès aléatoire dans le moteur de chat, nous mettons en cache les messages dans le moteur d'utilisateur.
La recherche de messages est implémentée sous la forme d'une requête diagonale depuis le moteur de l'utilisateur vers toutes les instances du moteur de discussion contenant les discussions de cet utilisateur. Les résultats sont combinés dans le moteur utilisateur lui-même.
Eh bien, tous les détails ont été pris en compte, il ne reste plus qu'à passer à un nouveau schéma - et de préférence sans que les utilisateurs ne s'en aperçoivent.
Migration de données
Nous avons donc un moteur de texte qui stocke les messages par utilisateur, et deux clusters de membres de discussion et de membres de discussion qui stockent des données sur les salles de discussion multiples et les utilisateurs qui y figurent. Comment passer de ceci au nouveau moteur d'utilisateur et au nouveau moteur de discussion ?
Les discussions entre membres de l’ancien système étaient principalement utilisées à des fins d’optimisation. Nous avons rapidement transféré les données nécessaires aux membres du chat, puis il n'a plus participé au processus de migration.
File d'attente pour les membres du chat. Il comprend 100 instances, tandis que le moteur de chat en compte 4 4. Pour transférer les données, vous devez les mettre en conformité - pour cela, les membres du chat ont été divisés en XNUMX XNUMX exemplaires, puis la lecture du journal binaire des membres du chat a été activée dans le moteur de chat.
Désormais, le moteur de chat connaît le multi-chat des membres du chat, mais il ne sait encore rien des dialogues avec deux interlocuteurs. Ces dialogues sont situés dans le moteur de texte en référence aux utilisateurs. Ici, nous avons pris les données « de front » : chaque instance de moteur de discussion a demandé à toutes les instances de moteur de texte si elles avaient le dialogue dont elles avaient besoin.
Génial - le moteur de chat sait quels sont les chats multi-chats et quels dialogues il existe.
Vous devez combiner les messages dans les discussions multi-chats afin d'obtenir une liste de messages dans chaque chat. Tout d'abord, le moteur de chat récupère du moteur de texte tous les messages utilisateur de ce chat. Dans certains cas, il y en a un grand nombre (jusqu'à des centaines de millions), mais à de très rares exceptions près, le chat s'intègre entièrement dans la RAM. Nous avons des messages non ordonnés, chacun en plusieurs exemplaires - après tout, ils sont tous extraits de différentes instances de moteur de texte correspondant aux utilisateurs. Le but est de trier les messages et de se débarrasser des copies qui prennent de la place inutilement.
Chaque message possède un horodatage contenant l'heure à laquelle il a été envoyé et le texte. Nous utilisons le temps pour le tri - nous plaçons des pointeurs vers les messages les plus anciens des participants multichat et comparons les hachages du texte des copies prévues, en augmentant l'horodatage. Il est logique que les copies aient le même hachage et le même horodatage, mais en pratique ce n'est pas toujours le cas. Comme vous vous en souvenez, la synchronisation dans l'ancien schéma était effectuée par PHP - et dans de rares cas, l'heure d'envoi du même message différait selon les utilisateurs. Dans ces cas-là, nous nous sommes permis de modifier l’horodatage – généralement en une seconde. Le deuxième problème réside dans l’ordre différent des messages selon les destinataires. Dans de tels cas, nous avons autorisé la création d’une copie supplémentaire, avec différentes options de commande pour différents utilisateurs.
Après cela, les données sur les messages multichat sont envoyées au moteur utilisateur. Et voici une fonctionnalité désagréable des messages importés. En fonctionnement normal, les messages arrivant au moteur sont classés strictement par ordre croissant par user_local_id. Les messages importés de l'ancien moteur vers le moteur utilisateur ont perdu cette propriété utile. Dans le même temps, pour la commodité des tests, vous devez pouvoir y accéder rapidement, y rechercher quelque chose et en ajouter de nouveaux.
Nous utilisons une structure de données spéciale pour stocker les messages importés.
Il représente un vecteur de taille Où est tout le monde - sont différents et ordonnés par ordre décroissant, avec un ordre particulier des éléments. Dans chaque segment avec indices les éléments sont triés. La recherche d'un élément dans une telle structure prend du temps à travers recherches binaires. L'ajout d'un élément est amorti sur .
Nous avons donc compris comment transférer les données des anciens moteurs vers les nouveaux. Mais ce processus prend plusieurs jours - et il est peu probable que pendant ces jours nos utilisateurs abandonnent l'habitude de s'écrire. Afin de ne pas perdre de messages pendant cette période, nous passons à un schéma de travail utilisant à la fois les anciens et les nouveaux clusters.
Les données sont écrites dans les membres du chat et dans le moteur utilisateur (et non dans le moteur texte, comme en fonctionnement normal selon l'ancien schéma). user-engine transmet la demande à chat-engine - et ici le comportement dépend du fait que ce chat a déjà été fusionné ou non. Si le chat n'a pas encore été fusionné, le moteur de chat ne s'écrit pas le message et son traitement a lieu uniquement dans le moteur de texte. Si le chat a déjà été fusionné dans chat-engine, il renvoie chat_local_id au user-engine et envoie le message à tous les destinataires. Le moteur utilisateur transmet toutes les données au moteur de texte - de sorte que si quelque chose se produit, nous pouvons toujours revenir en arrière, en ayant toutes les données actuelles dans l'ancien moteur. text-engine renvoie user_local_id, que le moteur utilisateur stocke et renvoie au backend.
En conséquence, le processus de transition ressemble à ceci : nous connectons des clusters de moteur d'utilisateur et de moteur de discussion vides. chat-engine lit l'intégralité du journal binlog des membres du chat, puis le proxy démarre selon le schéma décrit ci-dessus. Nous transférons les anciennes données et obtenons deux clusters synchronisés (ancien et nouveau). Il ne reste plus qu'à passer la lecture du moteur de texte au moteur utilisateur et à désactiver le proxy.
résultats
Grâce à la nouvelle approche, toutes les mesures de performances des moteurs ont été améliorées et les problèmes de cohérence des données ont été résolus. Nous pouvons désormais implémenter rapidement de nouvelles fonctionnalités dans les messages (et nous avons déjà commencé à le faire - nous avons augmenté le nombre maximum de participants au chat, mis en œuvre une recherche de messages transférés, lancé des messages épinglés et augmenté la limite du nombre total de messages par utilisateur) .
Les changements de logique sont vraiment énormes. Et je voudrais souligner que cela ne signifie pas toujours des années entières de développement par une immense équipe et des myriades de lignes de code. Le moteur de discussion et le moteur utilisateur ainsi que toutes les histoires supplémentaires comme Huffman pour la compression des messages, les arbres Splay et la structure des messages importés représentent moins de 20 3 lignes de code. Et ils ont été écrits par 10 développeurs en seulement XNUMX mois (cependant, il convient de garder à l'esprit que - champions du monde ).
De plus, au lieu de doubler le nombre de serveurs, nous avons réduit leur nombre de moitié - désormais le moteur d'utilisateur et le moteur de discussion fonctionnent sur 500 machines physiques, tandis que le nouveau système dispose d'une grande marge de charge. Nous avons économisé beaucoup d'argent sur l'équipement - environ 5 millions de dollars + 750 XNUMX dollars par an en dépenses de fonctionnement.
Nous nous efforçons de trouver les meilleures solutions aux problèmes les plus complexes et les plus importants. Nous en avons beaucoup - et c'est pourquoi nous recherchons des développeurs talentueux pour le département bases de données. Si vous aimez et savez résoudre de tels problèmes, avez une excellente connaissance des algorithmes et des structures de données, nous vous invitons à rejoindre l'équipe. Contactez notre pour plus de détails.
Même si cette histoire ne vous concerne pas, veuillez noter que nous apprécions les recommandations. Parlez-en à un ami , et s'il termine avec succès la période probatoire, vous recevrez une prime de 100 XNUMX roubles.
Source: habr.com