Schreiben Sie die VKontakte-Nachrichtendatenbank von Grund auf neu und überleben Sie

Unsere Benutzer schreiben einander Nachrichten, ohne Müdigkeit zu bemerken.

Das ist ziemlich viel. Wenn man sich vorgenommen hätte, alle Nachrichten aller Benutzer zu lesen, würde das mehr als 150 Jahre dauern. Vorausgesetzt, Sie sind ein ziemlich fortgeschrittener Leser und verbringen nicht mehr als eine Sekunde mit jeder Nachricht.

Bei einem solchen Datenvolumen ist es von entscheidender Bedeutung, dass die Logik für die Speicherung und den Zugriff darauf optimal aufgebaut ist. Andernfalls könnte in einem nicht ganz so schönen Moment klar werden, dass bald alles schief gehen wird.

Für uns kam dieser Moment vor anderthalb Jahren. Wie es dazu kam und was am Ende passiert ist, erzählen wir euch der Reihe nach.

Anamnese

In der allerersten Implementierung funktionierten VKontakte-Nachrichten auf einer Kombination aus PHP-Backend und MySQL. Dies ist eine völlig normale Lösung für eine kleine Studenten-Website. Diese Seite wuchs jedoch unkontrolliert und begann für sich selbst eine Optimierung der Datenstrukturen zu fordern.

Ende 2009 wurde das erste Text-Engine-Repository geschrieben, in das 2010 Nachrichten übertragen wurden.

In der Text-Engine wurden Nachrichten in Listen gespeichert – einer Art „Mailboxen“. Jede dieser Listen wird durch eine UID bestimmt – den Benutzer, der alle diese Nachrichten besitzt. Eine Nachricht verfügt über eine Reihe von Attributen: Gesprächspartner-ID, Text, Anhänge usw. Die Nachrichtenkennung in der „Box“ lautet „local_id“, sie ändert sich nie und wird sequentiell für neue Nachrichten zugewiesen. Die „Boxen“ sind unabhängig und innerhalb der Engine nicht miteinander synchronisiert; die Kommunikation zwischen ihnen erfolgt auf PHP-Ebene. Sie können die Datenstruktur und die Funktionen der Text-Engine von innen betrachten hier.

Für die Korrespondenz zwischen zwei Benutzern reichte dies völlig aus. Ratet mal, was als nächstes geschah?

Im Mai 2011 führte VKontakte Gespräche mit mehreren Teilnehmern ein – Multi-Chat. Um mit ihnen zusammenzuarbeiten, haben wir zwei neue Cluster eingerichtet – Mitglieder-Chats und Chat-Mitglieder. Der erste speichert Daten über Chats von Benutzern, der zweite speichert Daten über Benutzer von Chats. Dazu gehören neben den Listen selbst beispielsweise auch der einladende Benutzer und der Zeitpunkt, zu dem er zum Chat hinzugefügt wurde.

„PHP, lass uns eine Nachricht an den Chat senden“, sagt der Benutzer.
„Komm schon, {Benutzername}“, sagt PHP.

Dieses Schema hat Nachteile. Die Synchronisierung liegt weiterhin in der Verantwortung von PHP. Große Chats und Benutzer, die ihnen gleichzeitig Nachrichten senden, sind eine gefährliche Geschichte. Da die Text-Engine-Instanz von der UID abhängt, könnten Chat-Teilnehmer dieselbe Nachricht zu unterschiedlichen Zeiten erhalten. Damit könnte man leben, wenn der Fortschritt stagnieren würde. Aber das wird nicht passieren.

Ende 2015 haben wir Community-Nachrichten gestartet und Anfang 2016 haben wir eine API dafür eingeführt. Mit dem Aufkommen großer Chatbots in Communities konnte die gleichmäßige Lastverteilung vergessen werden.

Ein guter Bot generiert mehrere Millionen Nachrichten pro Tag – damit können sich selbst die gesprächigsten Nutzer nicht rühmen. Dies bedeutet, dass einige Instanzen der Text-Engine, auf denen solche Bots lebten, vollständig zu leiden begannen.

Zu den Nachrichten-Engines im Jahr 2016 zählen 100 Instanzen von Chat-Mitgliedern und Mitglieder-Chats sowie 8000 Text-Engines. Sie wurden auf tausend Servern mit jeweils 64 GB Speicher gehostet. Als erste Notmaßnahme haben wir den Speicher um weitere 32 GB erhöht. Wir haben die Prognosen geschätzt. Ohne drastische Änderungen würde dies für etwa ein weiteres Jahr reichen. Sie müssen sich entweder Hardware besorgen oder die Datenbanken selbst optimieren.

Aufgrund der Natur der Architektur ist es nur sinnvoll, die Hardware um ein Vielfaches zu erhöhen. Das heißt, die Anzahl der Autos mindestens zu verdoppeln – das ist natürlich ein ziemlich teurer Weg. Wir werden optimieren.

Neues Konzept

Der zentrale Kern des neuen Ansatzes ist der Chat. Ein Chat verfügt über eine Liste mit Nachrichten, die sich auf ihn beziehen. Der Benutzer verfügt über eine Liste von Chats.

Das erforderliche Minimum sind zwei neue Datenbanken:

• Chat-Engine. Dies ist ein Repository für Chat-Vektoren. Jeder Chat verfügt über einen Vektor mit Nachrichten, die sich auf ihn beziehen. Jede Nachricht hat einen Text und eine eindeutige Nachrichtenkennung innerhalb des Chats – chat_local_id.
• Benutzer-Engine. Dies ist eine Speicherung von Benutzervektoren – Links zu Benutzern. Jeder Benutzer verfügt über einen Vektor von peer_id (Gesprächspartner – andere Benutzer, Multi-Chat oder Communities) und einen Vektor von Nachrichten. Jede peer_id verfügt über einen Vektor von Nachrichten, die sich auf sie beziehen. Jede Nachricht hat eine chat_local_id und eine eindeutige Nachrichten-ID für diesen Benutzer – user_local_id.

Neue Cluster kommunizieren untereinander über TCP – so wird sichergestellt, dass sich die Reihenfolge der Anfragen nicht ändert. Die Anfragen selbst und deren Bestätigungen werden auf der Festplatte aufgezeichnet – so können wir den Zustand der Warteschlange jederzeit nach einem Ausfall oder Neustart der Engine wiederherstellen. Da die Benutzer-Engine und die Chat-Engine jeweils aus 4 Shards bestehen, wird die Anforderungswarteschlange zwischen den Clustern gleichmäßig verteilt (aber in Wirklichkeit gibt es überhaupt keine – und es funktioniert sehr schnell).

Die Arbeit mit Festplatten in unseren Datenbanken basiert in den meisten Fällen auf einer Kombination aus einem binären Änderungsprotokoll (Binlog), statischen Snapshots und einem Teilbild im Speicher. Änderungen im Laufe des Tages werden in ein Binlog geschrieben und in regelmäßigen Abständen wird ein Snapshot des aktuellen Status erstellt. Ein Snapshot ist eine Sammlung von Datenstrukturen, die für unsere Zwecke optimiert sind. Es besteht aus einem Header (Metaindex des Bildes) und einer Reihe von Metadateien. Der Header wird dauerhaft im RAM gespeichert und gibt an, wo nach Daten aus dem Snapshot gesucht werden soll. Jede Metadatei enthält Daten, die wahrscheinlich zu bestimmten Zeitpunkten benötigt werden – beispielsweise im Zusammenhang mit einem einzelnen Benutzer. Wenn Sie die Datenbank mithilfe des Snapshot-Headers abfragen, wird die erforderliche Metadatei gelesen und anschließend Änderungen im Binlog berücksichtigt, die nach der Erstellung des Snapshots aufgetreten sind. Erfahren Sie mehr über die Vorteile dieses Ansatzes hier.

Gleichzeitig ändern sich die Daten auf der Festplatte selbst nur einmal am Tag – spät in der Nacht in Moskau, wenn die Belastung minimal ist. Dadurch (in dem Wissen, dass die Struktur auf der Festplatte den ganzen Tag über konstant ist) können wir es uns leisten, Vektoren durch Arrays fester Größe zu ersetzen – und dadurch Speicher zu gewinnen.

Das Versenden einer Nachricht im neuen Schema sieht folgendermaßen aus:

1. Das PHP-Backend kontaktiert die Benutzer-Engine mit der Bitte, eine Nachricht zu senden.
2. user-engine leitet die Anfrage an die gewünschte Chat-Engine-Instanz weiter, die an user-engine chat_local_id zurückgibt – eine eindeutige Kennung einer neuen Nachricht in diesem Chat. Anschließend sendet die chat_engine die Nachricht an alle Empfänger im Chat.
3. user-engine empfängt chat_local_id von chat-engine und gibt user_local_id an PHP zurück – eine eindeutige Nachrichtenkennung für diesen Benutzer. Dieser Identifikator wird dann beispielsweise verwendet, um mit Nachrichten über die API zu arbeiten.

Doch neben dem eigentlichen Versenden von Nachrichten müssen Sie noch ein paar weitere wichtige Dinge umsetzen:

• Unterlisten sind beispielsweise die neuesten Nachrichten, die Sie beim Öffnen der Konversationsliste sehen. Ungelesene Nachrichten, Nachrichten mit Tags („Wichtig“, „Spam“ usw.).
• Komprimieren von Nachrichten in der Chat-Engine
• Zwischenspeichern von Nachrichten in der Benutzer-Engine
• Durchsuchen (in allen Dialogen und innerhalb eines bestimmten).
• Echtzeit-Update (Longpolling).
• Speichern des Verlaufs, um Caching auf mobilen Clients zu implementieren.

Bei allen Unterlisten handelt es sich um sich schnell verändernde Strukturen. Um mit ihnen zu arbeiten, verwenden wir Spreizbäume. Diese Wahl erklärt sich aus der Tatsache, dass wir an der Spitze des Baums manchmal ein ganzes Nachrichtensegment aus einem Snapshot speichern – zum Beispiel besteht der Baum nach der nächtlichen Neuindizierung aus einer Spitze, die alle Nachrichten der Unterliste enthält. Der Splay-Baum erleichtert das Einführen in die Mitte eines solchen Scheitelpunkts, ohne an das Ausbalancieren denken zu müssen. Darüber hinaus speichert Splay keine unnötigen Daten, was uns Speicherplatz spart.

Nachrichten enthalten eine große Menge an Informationen, meist Text, deren Komprimierung nützlich ist. Es ist wichtig, dass wir auch nur eine einzelne Nachricht genau entarchivieren können. Wird zum Komprimieren von Nachrichten verwendet Huffman-Algorithmus mit unseren eigenen Heuristiken – wir wissen zum Beispiel, dass sich in Nachrichten Wörter mit „Nicht-Wörtern“ abwechseln – Leerzeichen, Satzzeichen – und wir erinnern uns auch an einige Besonderheiten der Verwendung von Symbolen für die russische Sprache.

Da es viel weniger Benutzer als Chats gibt, speichern wir Nachrichten in der Benutzer-Engine zwischen, um Festplattenanfragen mit wahlfreiem Zugriff in der Chat-Engine zu speichern.

Die Nachrichtensuche wird als diagonale Abfrage von der Benutzer-Engine zu allen Chat-Engine-Instanzen implementiert, die Chats dieses Benutzers enthalten. Die Ergebnisse werden in der User-Engine selbst zusammengeführt.

Nun, alle Details sind berücksichtigt, es bleibt nur noch die Umstellung auf ein neues Schema – und das am besten, ohne dass der Nutzer es merkt.

Datenmigration

Wir haben also eine Text-Engine, die Nachrichten nach Benutzern speichert, und zwei Cluster, Chat-Mitglieder und Mitglieder-Chats, die Daten über Multi-Chat-Räume und die Benutzer darin speichern. Wie kommt man von hier aus zur neuen User-Engine und Chat-Engine?

Mitglieder-Chats im alten Schema wurden hauptsächlich zur Optimierung verwendet. Wir haben die notwendigen Daten schnell von dort an die Chat-Mitglieder übertragen, und dann hat es nicht mehr am Migrationsprozess teilgenommen.

Warteschlange für Chat-Mitglieder. Es umfasst 100 Instanzen, während die Chat-Engine 4 hat. Um die Daten zu übertragen, müssen Sie sie in Übereinstimmung bringen. Dazu wurden die Chat-Mitglieder in jeweils 4 Kopien aufgeteilt und anschließend wurde das Lesen des Binlogs der Chat-Mitglieder in der Chat-Engine aktiviert.

Jetzt kennt die Chat-Engine Multi-Chat von Chat-Mitgliedern, aber noch nichts über Dialoge mit zwei Gesprächspartnern. Solche Dialoge befinden sich in der Text-Engine mit Bezug auf Benutzer. Hier haben wir die Daten „frontal“ betrachtet: Jede Chat-Engine-Instanz fragte alle Text-Engine-Instanzen, ob sie über den benötigten Dialog verfügten.

Großartig – die Chat-Engine weiß, welche Multi-Chat-Chats es gibt und welche Dialoge es gibt.
Sie müssen Nachrichten in Multi-Chat-Chats kombinieren, sodass Sie in jedem Chat eine Liste mit Nachrichten erhalten. Zunächst ruft die Chat-Engine alle Benutzernachrichten aus diesem Chat von der Text-Engine ab. In einigen Fällen sind es ziemlich viele davon (bis zu Hunderten von Millionen), aber mit sehr seltenen Ausnahmen passt der Chat vollständig in den RAM. Wir haben ungeordnete Nachrichten, jede in mehreren Kopien – schließlich werden sie alle aus verschiedenen Text-Engine-Instanzen abgerufen, die den Benutzern entsprechen. Ziel ist es, Nachrichten zu sortieren und Kopien zu entfernen, die unnötigen Platz beanspruchen.

Jede Nachricht verfügt über einen Zeitstempel, der den Zeitpunkt des Versands und den Text enthält. Wir nutzen die Zeit zum Sortieren – wir platzieren Zeiger auf die ältesten Nachrichten der Multichat-Teilnehmer und vergleichen Hashes aus dem Text der beabsichtigten Kopien, um so den Zeitstempel zu erhöhen. Es ist logisch, dass die Kopien denselben Hash und Zeitstempel haben, aber in der Praxis ist dies nicht immer der Fall. Wie Sie sich erinnern, wurde die Synchronisierung im alten Schema von PHP durchgeführt – und in seltenen Fällen unterschied sich der Zeitpunkt des Sendens derselben Nachricht zwischen verschiedenen Benutzern. In diesen Fällen haben wir uns erlaubt, den Zeitstempel zu bearbeiten – meist innerhalb einer Sekunde. Das zweite Problem ist die unterschiedliche Reihenfolge der Nachrichten für verschiedene Empfänger. In solchen Fällen haben wir die Erstellung einer zusätzlichen Kopie mit unterschiedlichen Bestelloptionen für verschiedene Benutzer zugelassen.

Danach werden Daten über Nachrichten im Multichat an die User-Engine gesendet. Und hier kommt ein unangenehmes Merkmal importierter Nachrichten. Im Normalbetrieb werden Nachrichten, die an die Engine kommen, streng in aufsteigender Reihenfolge nach user_local_id sortiert. Nachrichten, die von der alten Engine in die Benutzer-Engine importiert wurden, haben diese nützliche Eigenschaft verloren. Gleichzeitig müssen Sie zur Vereinfachung des Testens schnell auf sie zugreifen, darin etwas suchen und neue hinzufügen können.

Wir verwenden eine spezielle Datenstruktur, um importierte Nachrichten zu speichern.

Es stellt einen Größenvektor dar , wo sind alle - sind unterschiedlich und in absteigender Reihenfolge geordnet, mit einer besonderen Reihenfolge der Elemente. In jedem Segment mit Indizes Elemente werden sortiert. Die Suche nach einem Element in einer solchen Struktur braucht Zeit durch Binäre Suchen. Die Hinzufügung eines Elements wird abgeschrieben .

Also haben wir herausgefunden, wie wir Daten von alten Engines auf neue übertragen können. Dieser Vorgang dauert jedoch mehrere Tage – und es ist unwahrscheinlich, dass unsere Benutzer in diesen Tagen die Gewohnheit aufgeben, sich gegenseitig zu schreiben. Um in dieser Zeit keine Nachrichten zu verlieren, wechseln wir zu einem Arbeitsschema, das sowohl alte als auch neue Cluster verwendet.

Daten werden an Chat-Mitglieder und User-Engine geschrieben (und nicht an Text-Engine, wie im normalen Betrieb nach dem alten Schema). user-engine leitet die Anfrage an chat-engine weiter – und hier hängt das Verhalten davon ab, ob dieser Chat bereits zusammengeführt wurde oder nicht. Wenn der Chat noch nicht zusammengeführt wurde, schreibt die Chat-Engine die Nachricht nicht an sich selbst und ihre Verarbeitung erfolgt nur in der Text-Engine. Wenn der Chat bereits in die Chat-Engine eingebunden wurde, gibt er chat_local_id an die User-Engine zurück und sendet die Nachricht an alle Empfänger. Die Benutzer-Engine leitet alle Daten an die Text-Engine weiter. Wenn also etwas passiert, können wir jederzeit einen Rollback durchführen und alle aktuellen Daten in der alten Engine haben. Die Text-Engine gibt user_local_id zurück, die die User-Engine speichert und an das Backend zurückgibt.

Infolgedessen sieht der Übergangsprozess wie folgt aus: Wir verbinden leere User-Engine- und Chat-Engine-Cluster. Die Chat-Engine liest das gesamte Binlog der Chat-Mitglieder und startet dann das Proxying gemäß dem oben beschriebenen Schema. Wir übertragen die alten Daten und erhalten zwei synchronisierte Cluster (alt und neu). Es bleibt nur noch, das Lesen von der Text-Engine auf die User-Engine umzustellen und das Proxying zu deaktivieren.

Ergebnisse

Dank des neuen Ansatzes wurden alle Leistungskennzahlen der Engines verbessert und Probleme mit der Datenkonsistenz behoben. Jetzt können wir schnell neue Funktionen in Nachrichten implementieren (und haben bereits damit begonnen – wir haben die maximale Anzahl der Chat-Teilnehmer erhöht, eine Suche nach weitergeleiteten Nachrichten implementiert, angeheftete Nachrichten gestartet und das Limit für die Gesamtzahl der Nachrichten pro Benutzer erhöht). .

Die Veränderungen in der Logik sind wirklich enorm. Und ich möchte anmerken, dass dies nicht immer ganze Entwicklungsjahre durch ein riesiges Team und unzählige Codezeilen bedeutet. Chat-Engine und User-Engine zusammen mit allen zusätzlichen Storys wie Huffman für die Nachrichtenkomprimierung, Splay-Bäume und Struktur für importierte Nachrichten sind weniger als 20 Zeilen Code. Und sie wurden von drei Entwicklern in nur 3 Monaten geschrieben (das sollte man jedoch im Hinterkopf behalten). alle drei Entwickler - Weltmeister in der Sportprogrammierung).

Darüber hinaus haben wir die Anzahl der Server nicht verdoppelt, sondern um die Hälfte reduziert – jetzt laufen die Benutzer-Engine und die Chat-Engine auf 500 physischen Maschinen, während das neue Schema einen großen Spielraum für die Auslastung bietet. Wir haben viel Geld bei der Ausrüstung gespart – etwa 5 Millionen US-Dollar + 750 US-Dollar pro Jahr an Betriebskosten.

Wir sind bestrebt, die besten Lösungen für die komplexesten und umfangreichsten Probleme zu finden. Davon haben wir jede Menge – und deshalb sind wir auf der Suche nach talentierten Entwicklern in der Datenbankabteilung. Wenn Sie solche Probleme lieben und wissen, wie man sie löst, und über ausgezeichnete Kenntnisse von Algorithmen und Datenstrukturen verfügen, laden wir Sie ein, dem Team beizutreten. Kontaktieren Sie uns HRfür Details.

Auch wenn es in dieser Geschichte nicht um Sie geht, beachten Sie bitte, dass wir Empfehlungen schätzen. Erzählen Sie einem Freund davon Stellenangebote für Entwickler, und wenn er die Probezeit erfolgreich abschließt, erhalten Sie eine Prämie von 100 Rubel.

Source: habr.com