2.1 Wie kann man N-mal fragmentieren und verlangsamen?

Sie können genau N-mal so sharden und verlangsamen:

  • Senden Sie docs00...docs15-Anfragen nacheinander , nicht parallel.
  • Treffen Sie bei einfachen Abfragen eine Auswahl nicht nach Schlüssel , sondern WHERE Something=234.

In diesem Fall nimmt der serialisierte Teil (seriell) in modernen Datenbanken nicht 1 % und nicht 5 %, sondern etwa 20 % ein. Sie können auch 50 % des serialisierten Teils erhalten, wenn Sie über ein äußerst effizientes Binärprotokoll auf die Datenbank zugreifen oder sie als dynamische Bibliothek in ein Python-Skript einbinden.

Der Rest der Bearbeitungszeit einer einfachen Anfrage wird mit nicht parallelisierbaren Vorgängen wie dem Analysieren der Anfrage, der Vorbereitung des Plans usw. in Anspruch genommen. Das heißt, das Nichtlesen der Aufzeichnung verlangsamt die Geschwindigkeit.

Wenn wir die Daten in 16 Tabellen aufteilen und nacheinander ausführen, wie es beispielsweise in der Programmiersprache PHP üblich ist (sie ist nicht sehr gut darin, asynchrone Prozesse zu starten), dann kommt es zu einer 16-fachen Verlangsamung. Und vielleicht sogar noch mehr, denn auch Netzwerk-Roundtrips werden hinzukommen.

Plötzlich ist beim Sharding die Wahl der Programmiersprache wichtig.

Denken Sie an die Wahl der Programmiersprache, denn wenn Sie Abfragen nacheinander an die Datenbank (oder den Suchserver) senden, woher kommt dann die Beschleunigung? Vielmehr wird es eine Verlangsamung geben.

2.2 Über Halbautomatik

An manchen Stellen löst die Verfeinerung der Informationstechnologie chthonischen Horror aus. MySQL verfügte beispielsweise standardmäßig nicht über die Implementierung von Sharding auf bestimmte Versionen, jedoch wachsen die Größen der im Kampf verwendeten Datenbanken auf unanständige Werte an.

Die leidende Menschheit angesichts einzelner DBAs wird seit Jahren gequält und schreibt mehrere schlechte Sharding-Lösungen, die auf nichts basieren. Danach wird eine mehr oder weniger anständige Sharding-Lösung namens ProxySQL geschrieben (MariaDB/Spider, PG/pg_shard/Citus, ...). Dies ist ein bekanntes Beispiel für genau diesen Fleck.

Insgesamt ist ProxySQL natürlich eine vollwertige Enterprise-Lösung für Open Source, Routing und mehr. Aber eine der zu lösenden Aufgaben ist das Sharding für eine Datenbank, die an sich kein Sharding auf menschliche Weise durchführen kann. Sie sehen, es gibt keinen „Shards = 16“-Schalter. Sie müssen entweder jede Anfrage in der Anwendung neu schreiben, und es gibt an einigen Stellen viele davon, oder Sie müssen eine Zwischenschicht zwischen der Anwendung und der Datenbank einfügen, die aussieht: „Hmm ... * AUS Dokumenten AUSWÄHLEN? Ja, es muss in 16 kleine SELECT * FROM server1.document1, SELECT * FROM server2.document2 aufgeteilt werden – zu diesem Server mit einem solchen Login/Passwort, zu diesem mit einem anderen. Wenn einer nicht geantwortet hat, dann ...“, usw. Genau dies kann durch Zwischenflecken erreicht werden. Sie sind etwas geringer als bei allen Datenbanken. Soweit ich weiß, gilt für PostgreSQL:

Die Konfiguration jedes einzelnen Patches ist ein separates Riesenthema, das nicht in einen Bericht passt, daher werden wir nur die Grundkonzepte besprechen. Lassen Sie uns besser ein wenig über die Theorie des Buzz sprechen.

2.3 Absolut perfekte Automatisierung?

Die gesamte Theorie, wie man im Fall von Sharding high wird, ist in diesem Buchstaben F() . Das Grundprinzip ist in etwa immer das gleiche: shard_id = F(object).

Sharding – worum geht es? Wir haben 2 Milliarden Datensätze (oder 64). Wir wollen sie in mehrere Teile zerlegen. Es stellt sich eine unerwartete Frage: Wie? Nach welchem ​​Prinzip sollte ich meine 2 Milliarden Datensätze (oder 64) auf 16 mir zur Verfügung stehende Server verteilen?

Der latente Mathematiker in uns sollte vorschlagen, dass es am Ende immer eine magische Funktion gibt, die für jedes Dokument (Objekt, Zeile usw.) bestimmt, in welches Stück es eingefügt wird.

Geht man tiefer in die Mathematik, hängt diese Funktion immer nicht nur vom Objekt selbst (der Zeile selbst) ab, sondern auch von externen Einstellungen wie der Gesamtzahl der Shards. Eine Funktion, die für jedes Objekt angeben muss, wo es abgelegt werden soll, kann keinen Wert zurückgeben, mehr als es Server im System gibt. Und die Funktionen sind etwas anders:

Java university 
shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

Aber wir werden uns nicht weiter mit dieser Wildnis einzelner Funktionen befassen, sondern nur darüber sprechen, was magische Funktionen F() sind.

2.4 Was sind F()?

Sie können sich viele unterschiedliche Implementierungsmechanismen einfallen lassen. Beispielzusammenfassung:

  • F = rand() % nums_shards
  • F = somehash(object.id) % num_shards
  • F = object.date % num_shards
  • F = object.user_id % num_shards
  • ...
  • F = shard_table [ somehash() |… object.date |… ]

Eine interessante Tatsache – Sie können natürlich alle Daten zufällig verteilen – wir werfen den nächsten Datensatz auf einen beliebigen Server, auf einen beliebigen Kern, in eine beliebige Tabelle. Das wird nicht viel Freude bereiten, aber es wird funktionieren.

Es gibt etwas intelligentere Methoden zum Shard nach einer reproduzierbaren oder sogar konsistenten Hash-Funktion oder zum Shard nach einem bestimmten Attribut. Lassen Sie uns jede Methode durchgehen.

F = rand()

Herumstreuen ist keine sehr korrekte Methode. Ein Problem: Wir haben unsere 2 Milliarden Datensätze willkürlich auf tausend Server verteilt und wissen nicht, wo sich der Datensatz befindet. Wir müssen user_1 herausholen, wissen aber nicht, wo es ist. Wir gehen zu tausend Servern und sortieren alles – irgendwie ist das ineffizient.

F = somehash()

Lassen Sie uns Benutzer auf erwachsene Weise verteilen: Berechnen Sie die reproduzierbare Hash-Funktion aus user_id, dividieren Sie den Rest durch die Anzahl der Server und kontaktieren Sie sofort den gewünschten Server.

Warum machen wir das? Und dann, dass wir eine hohe Auslastung haben und nichts anderes mehr auf einen Server passt. Wenn es passen würde, wäre das Leben so einfach.

Großartig, die Situation hat sich bereits verbessert. Um einen Datensatz zu erhalten, gehen wir im Voraus zu einem bekannten Server. Aber wenn wir einen Bereich von Schlüsseln haben, müssen wir in diesem gesamten Bereich alle Werte der Schlüssel durchgehen und im Grenzfall entweder zu so vielen Shards gehen, wie wir Schlüssel im Bereich haben, oder sogar zu Jeder Server. Die Situation hat sich natürlich verbessert, aber nicht bei allen Anfragen. Einige Abfragen sind betroffen.

Natürliches Sharding (F = object.date % num_shards)

Manchmal, also oft, sind 95 % des Datenverkehrs und 95 % der Last Anfragen mit einer Art natürlichem Sharding. Beispielsweise betreffen 95 % der bedingten sozialanalytischen Abfragen nur Daten für den letzten 1 Tag, 3 Tage, 7 Tage und die restlichen 5 % beziehen sich auf die letzten Jahre. Aber 95 % der Anfragen sind somit naturgemäß nach Datum fragmentiert, das Interesse der Systemnutzer konzentriert sich auf die letzten Tage.

In diesem Fall können Sie die Daten nach Datum aufteilen, beispielsweise nach einem Tag, und die Antwort auf die Anforderung eines Berichts für einen Tag oder ein Objekt von diesem Tag bis zu diesem Shard verfolgen und loslegen.

Das Leben verbessert sich – wir kennen jetzt nicht nur den Standort eines bestimmten Objekts, sondern auch die Reichweite. Wenn wir nicht nach einer Reihe von Daten, sondern nach einer Reihe anderer Spalten gefragt werden, müssen wir natürlich alle Scherben durchgehen. Aber nach den Spielregeln haben wir nur 5 % solcher Anfragen.

Es scheint, dass wir für alles eine ideale Lösung gefunden haben, aber es gibt zwei Probleme:

  • Diese Lösung ist auf einen bestimmten Fall zugeschnitten, wenn 95 % der Anfragen nur die letzte Woche betreffen.
  • Da 95 % der Anfragen die letzte Woche betreffen, werden sie alle auf einen Shard fallen, der diese letzte Woche bedient. Dieser Splitter wird schmelzen, während alle anderen während dieser Zeit untätig bleiben. Gleichzeitig darf man sie nicht wegwerfen, auch Archivdaten müssen gespeichert werden.

Das soll nicht heißen, dass dies ein schlechtes Sharding-Schema ist – wir schneiden heiße Daten ab, dennoch muss etwas mit dem heißesten Shard gemacht werden.

Das Problem wird durch Possen, Sprünge und Umschläge gelöst, das heißt, eine Erhöhung der Anzahl der Repliken für den brennenden aktuellen Tag, dann eine allmähliche Verringerung der Anzahl der Repliken, wenn dieser Tag zur Vergangenheit wird und ins Archiv gelangt. Es gibt keine ideale Lösung namens „Sie müssen die Daten nur mit einer magischen Hash-Funktion falsch über den Cluster verteilen“.

2.5 Zu zahlender Preis

Formal wissen wir jetzt, dass wir „alles“ wissen. Es stimmt, wir kennen keinen großen Kopfschmerz und zwei kleinere Kopfschmerzen.

1. Einfacher Schmerz: stark verschmiert

Dies ist ein Beispiel aus einem Lehrbuch, das fast nie im Kampf vorkommt, sondern plötzlich.

  • Als Beispiel mit Datum, nur ohne Datum!
  • Unbeabsichtigte ungleichmäßige (wahrnehmbare) Verteilung.

Sie haben sich für den Sharding-Mechanismus entschieden und/oder die Daten haben sich geändert, und natürlich hat der PM die Anforderungen (wir haben keine Fehler im Code, der PM meldet die Anforderungen immer nicht) und die Verteilung nicht übermittelt wurde ungeheuer ungleichmäßig. Das heißt, sie haben das Kriterium verfehlt.

Zum Fangen müssen Sie auf die Größe der Scherben achten. Wir werden das Problem auf jeden Fall in dem Moment sehen, in dem einer unserer Shards entweder überhitzt oder 100-mal größer als die anderen wird. Sie können das Problem einfach beheben, indem Sie den Schlüssel oder die Sharding-Funktion austauschen.

Das ist ein einfaches Problem, um ehrlich zu sein, ich glaube nicht, dass mindestens einer von hundert Menschen im Leben damit konfrontiert wird, aber plötzlich wird es zumindest jemandem helfen.

2. „Unbesiegbarer“ Schmerz: Aggregation, Vereinigung

Wie trifft man eine Auswahl, die eine Milliarde Datensätze aus einer Tabelle mit einer Milliarde Datensätzen aus einer anderen Tabelle verbindet?

  • Wie kann man „schnell“ berechnen... WO randcol ZWISCHEN aaa UND bbb?
  • Wie kann man „intelligent“ tun... Users_32shards JOIN posts_1024 Shards?

Kurze Antwort: Auf keinen Fall, leiden!

Wenn Sie in der ersten Tabelle eine Milliarde Datensätze auf tausend Server verteilen, damit diese schneller arbeiten, und das Gleiche in der zweiten Tabelle tun, dann sollten natürlich tausend bis tausend Server paarweise miteinander kommunizieren. Eine Million Verbindungen werden nicht gut funktionieren. Wenn wir Anfragen an die Datenbank (Suche, Speicherung, Dokumentenspeicher oder verteiltes Dateisystem) stellen, die nicht gut zum Sharding passen, werden diese Anfragen stark verlangsamt.

Ein wichtiger Punkt ist , dass einige Anfragen immer erfolglos abgewiesen werden und langsamer werden . Es ist wichtig, ihren Prozentsatz zu minimieren. Infolgedessen besteht keine Notwendigkeit, gigantische Verknüpfungen mit einer Milliarde mal einer Milliarde Datensätzen durchzuführen. Wenn es möglich ist, eine kleine Tabelle, relativ zu der Sie eine riesige gemeinsame Tabelle hinzufügen, auf alle Knoten zu replizieren, sollten Sie dies tun. Wenn die Verknüpfungen tatsächlich in irgendeiner Weise lokal sind, ist es beispielsweise möglich, den Benutzer und seine Beiträge nebeneinander zu platzieren, sie auf die gleiche Weise zu teilen und alle Verknüpfungen auf demselben Computer durchzuführen – genau das müssen Sie tun .

Dies ist ein separater Vorlesungskurs für drei Tage. Kommen wir also zum letzten höllischen Schmerz und den verschiedenen Algorithmen, um damit umzugehen.

2.6. Komplexer/lang anhaltender Schmerz: Resharding

Machen Sie sich bereit: Wenn Sie Ihre Daten zum ersten Mal in Ihrem Leben fragmentiert haben, werden Sie sie im Durchschnitt noch fünfmal teilen.

Unabhängig davon, wie viele Cluster Sie konfigurieren, müssen Sie dennoch ein Resharding durchführen.

Wenn Sie sehr schlau sind und Glück haben, dann machen Sie mindestens einmal einen Overshard. Aber sobald Sie sicher sind, denn in dem Moment, in dem Sie denken, dass 10 Einheiten für den Benutzer ausreichen, schreibt jemand in diesem Moment eine Anfrage für 30 und plant, eine Anfrage für 100 Einheiten unbekannter Ressourcen zu haben. Scherben sind nie genug. Mit dem ersten Sharding-Schema werden Sie auf jeden Fall etwas verpassen – Sie müssen immer entweder die Anzahl der hinzuzufügenden Server erhöhen oder etwas anderes tun – im Allgemeinen die Daten irgendwie neu verpacken.

Es ist gut, wenn wir schöne Zweierpotenzen haben: Es gab 16 Server-Shards, jetzt sind es 32. Es macht mehr Spaß, wenn es 17 wäre, es sind 23 – zwei vasimale Primzahlen. Wie machen Datenbanken das? Vielleicht steckt in ihnen eine Art Magie?

Die richtige Antwort lautet: Nein, in ihnen steckt keine Magie, in ihnen steckt die Hölle.

Als nächstes überlegen wir, was „von Hand“ gemacht werden kann, vielleicht verstehen wir es „als Automat“.

Auf der Stirn #1. Alles verlagern

Für alle Objekte betrachten wir NewF(object) und verschieben es auf einen neuen Shard.

Die Wahrscheinlichkeit, dass NewF()=OldF() übereinstimmt, ist gering.

Lassen Sie uns fast alles abdecken.

Oh.

Ich hoffe, dass es nicht so schlimm wird, alle 2 Milliarden Datensätze von alten Shards auf neue zu übertragen. Der naive Ansatz ist verständlich: Es gab 17 Maschinen, 6 Maschinen wurden zum Cluster hinzugefügt, 2 Milliarden Datensätze wurden aussortiert, sie wurden von 17 Maschinen auf 23 Maschinen verschoben. Alle 10 Jahre können Sie es wahrscheinlich sogar tun. Aber insgesamt ist es ein schlechter Schachzug.

Auf der Stirn #2. Hälfte verschieben

Die nächste naive Verbesserung – lassen Sie uns solch einen dummen Plan aufgeben – wird verhindern, dass 17 Autos in 23 umgewandelt werden, und wir werden immer 16 Autos in 32 Autos umwandeln! Dann müssen wir theoretisch genau die Hälfte der Daten verschieben, was in der Praxis auch möglich ist.

Für alle Objekte betrachten wir NewF(object) und verschieben es auf einen neuen Shard.

Es war ausschließlich 2^N, jetzt sind es ausschließlich 2^(N+1) Shards.

Die Wahrscheinlichkeit, dass NewF()=OldF() übereinstimmt, beträgt 0,5.

Lassen Sie uns etwa 50 % der Daten übertragen.

Optimal, funktioniert aber nur für Zweierpotenzen.

Im Prinzip ist alles in Ordnung, bis auf die Bindung an die Zweierpotenz bei der Anzahl der Autos. Dieser naive Ansatz kann seltsamerweise funktionieren.

Bitte beachten Sie, dass die zusätzliche Aufteilung des Clusters durch Zweierpotenzen in diesem Fall ebenfalls optimal ist. In jedem Fall müssen wir beim Hinzufügen von 16 Maschinen zu einem Cluster von 16 Maschinen die Hälfte der Daten verschieben – genau die Hälfte und verschieben.

Okay, aber hat die Menschheit wirklich nichts anderes erfunden – die Frage stellt sich ein neugieriger Geist.

Mehr Spaß #3. Konsistentes Hashing

Hier ist natürlich ein Bild mit einem Kreis zum Thema konsistentes Hashing erforderlich.

Wenn Sie „konsistentes Hashing“ googeln, wird auf jeden Fall ein Kreis angezeigt. Alle Ergebnisse werden mit Kreisen gefüllt.

Idee: Zeichnen wir Shard-IDs (Hashes) auf einen Kreis und markieren Sie die gehashten Server-IDs oben. Wenn Sie einen Server hinzufügen müssen, setzen wir einen neuen Punkt auf den Kreis und verschieben das, was sich als nahe daran herausstellte (und nur das, was sich als nahe daran herausstellte).

Beim Hinzufügen eines Shards: Wir durchsuchen nicht alles, sondern nur 2 „Nachbarn“, wir verschieben im Durchschnitt 1/n.

Beim Löschen eines Shards: Wir betrachten nur den Shard, der gelöscht wird, wir verschieben nur ihn. Irgendwie optimal.

Sehr effektiv im Hinblick auf die Minimierung des Datenverkehrs beim Hinzufügen eines Shards und absolut widerlich im Hinblick auf den normalen Datenausgleich. Denn wenn wir alle diese Objekte, die wir an eine große Anzahl von Maschinen verteilen, hashen, machen wir das relativ ungleichmäßig: Die Punkte um den Kreis herum sind ungleichmäßig verteilt und die Last jedes einzelnen Knotens kann sich stark von der der anderen unterscheiden.

Dieses Problem wird durch die letzte Zeile des virtuellen Knotens gelöst. Jeder Knoten, jeder Server im Kreis wird durch mehr als einen Punkt gekennzeichnet. Durch das Hinzufügen eines Servers, eines Shards usw. fügen wir einige Punkte hinzu. Jedes Mal, wenn wir etwas entfernen, entfernen wir entsprechend ein paar Punkte und verschieben einen kleinen Teil der Daten.

Ich spreche von diesem Raum mit Kreisen, weil sich zum Beispiel ein solches Schema in Cassandra befindet. Das heißt, wenn sie anfängt, Datensätze zwischen Knoten zu jagen, wissen Sie, dass der Kreis Sie ansieht und wahrscheinlich nicht zustimmt.

Im Vergleich zu den ersten Methoden hat sich das Leben jedoch verbessert – beim Hinzufügen/Entfernen eines Shards durchsuchen wir bereits nicht alle Datensätze, sondern nur einen Teil und verschieben nur einen Teil.

Achtung, die Frage ist: Kann es noch verbessert werden? Und auch die Einheitlichkeit beim Laden von Shards verbessern? Sie sagen, es ist möglich!

Mehr Spaß #4. Rendezvous/HRW

Die nächste einfache Idee (das Material ist lehrreich, also nichts Kompliziertes): shard_id = arg max hash(object_id, shard_id).

Warum es Rendezvous-Hashing heißt, weiß ich nicht, aber ich weiß, warum es „Highest Random Weight“ heißt. Man kann es sich ganz einfach so vorstellen:

Wir haben zum Beispiel 16 Shards. Für jedes Objekt (String), das irgendwo abgelegt werden muss, berechnen wir je nach Objekt 16 Hashes aus der Shard-Nummer. Wer den höchsten Hashwert hat, gewinnt.

Dabei handelt es sich um das sogenannte HRW-Hashing, auch Rendezvous-Hashing genannt. Blödsinnig ist das Schema zur Berechnung der Scherbenzahl einerseits optisch schonender als Kreise und ergibt andererseits eine gleichmäßige Belastung.

Das einzig Negative ist, dass das Hinzufügen eines neuen Shards für uns zu einer Verschlechterung geführt hat. Es besteht das Risiko, dass wir beim Hinzufügen eines neuen Shards noch einige Hashes haben, die sich ändern, und es möglicherweise notwendig ist, alles zu überprüfen. An der Shard-Entfernungstechnologie hat sich nicht viel geändert.

Ein weiteres Problem besteht darin, dass es bei einer großen Anzahl von Shards rechenintensiv ist.

Mehr Spaß #5. Weitere Techniken

Interessanterweise steht die Forschung nicht still und Google veröffentlicht jedes Jahr neue Weltraumtechnologien:

  • Jump Hash – Google '2014.
  • Multi Probe – Google '2015.
  • Magnetschwebebahn-Google '2016.

Wenn Sie sich für das Thema interessieren, können Sie viele Dissertationen lesen. Ich präsentiere diese Daten, um deutlich zu machen, dass das Problem nicht gelöst ist, es keine Superlösung gibt, die in allen Datenbanken implementiert werden kann. Bisher verteidigen Menschen ihre Dissertationen.

Schlussfolgerungen

Es gibt eine wichtige Grundtechnik namens Sharding, benannt nach Gallius Julius Caesar: „Teile und herrsche, herrsche und teile!“. Sollten die Daten nicht auf einen Server passen, ist eine Aufteilung auf 20 Server erforderlich.

Nachdem man das alles gelernt hat, sollte man den Eindruck gewinnen, dass es besser wäre, nicht zu splittern. Wenn Sie entscheiden, dass es besser wäre, nicht zu splittern, dann ist das das richtige Gefühl. Wenn Sie für 100 US-Dollar Speicher zum Server hinzufügen können, ohne etwas zu teilen, dann sollten Sie es tun. Beim Sharding entsteht ein komplexes verteiltes System, bei dem Daten hin und her übertragen und Daten an einem Ort gestapelt werden, von dem niemand weiß, wo. Wenn es vermieden werden kann, muss es vermieden werden.

Es ist besser, dies nicht manuell zu tun, es ist besser, dass die „Basis“ (Suche, DFS, ...) sich selbst fragmentieren kann. Auf jeden Fall wird es früher oder später zu einer hohen Belastung kommen und die Daten müssen irgendwie aufgeteilt werden. Es ist keine Tatsache, dass Sie keine Probleme haben, selbst wenn die Basis dies selbst tun kann. Denken Sie an den algorithmischen Fundamentalismus – Sie müssen verstehen, wie alles im Inneren funktioniert.

Wenn Sie Sharding zum ersten Mal einrichten, wählen Sie F() sorgfältig aus und denken Sie über Anfragen, Netzwerk usw. nach. Aber machen Sie sich bereit, Sie müssen wahrscheinlich zweimal auswählen und mindestens einmal alles wiederholen.