Sharding

1.1 Was ist Sharding?

Wenn man beharrlich googelt, stellt sich heraus, dass die Grenze zwischen dem sogenannten Partitioning und dem sogenannten Sharding eher fließend ist. Jeder nennt, was er will, was er will. Manche Leute unterscheiden zwischen horizontaler Partitionierung und Sharding. Andere sagen, Sharding sei eine bestimmte Art der horizontalen Partitionierung.

Ich habe keinen einzigen terminologischen Standard gefunden, der von den Gründervätern genehmigt und von der ISO zertifiziert worden wäre. Persönliche innere Überzeugung ist in etwa so: Aufteilung bedeutet im Durchschnitt, auf willkürliche Weise „die Basis in Stücke zu schneiden“.

• Vertikale Partitionierung – nach Spalte. Es gibt zum Beispiel eine riesige Tabelle mit ein paar Milliarden Datensätzen in 60 Spalten. Anstatt eine solche riesige Tabelle zu führen, führen wir 60 mindestens riesige Tabellen mit jeweils 2 Milliarden Datensätzen – und dabei handelt es sich nicht um eine Spaltenbasis, sondern um eine vertikale Partitionierung (als Beispiel für die Terminologie).
• Horizontale Partitionierung – wir schneiden Zeile für Zeile, möglicherweise innerhalb des Servers.

Der unangenehme Moment hier ist der subtile Unterschied zwischen horizontaler Partitionierung und Sharding. Ich kann in Stücke geschnitten werden, aber ich kann Ihnen nicht sicher sagen, was es ist. Man hat das Gefühl, dass Sharding und horizontale Partitionierung ungefähr dasselbe sind.

Sharding ist im Allgemeinen, wenn eine große Tabelle in Bezug auf Datenbanken oder eine Pro-Sammlung von Dokumenten, Objekten, wenn Sie keine Datenbank, sondern einen Dokumentenspeicher haben, genau nach Objekten zerschnitten wird. Das heißt, aus 2 Milliarden Objekten werden Stücke unabhängig von ihrer Größe ausgewählt. Die Objekte selbst in jedem Objekt werden nicht in Stücke geschnitten, wir legen sie nicht in separaten Spalten an, sondern legen sie stapelweise an verschiedenen Orten an.

Es gibt subtile terminologische Unterschiede. Relativ gesehen können Postgres-Entwickler beispielsweise sagen, dass eine horizontale Partitionierung vorliegt, wenn alle Tabellen, in die die Haupttabelle unterteilt ist, im selben Schema liegen, und wenn sie sich auf verschiedenen Computern befinden, handelt es sich bereits um Sharding.

Im Allgemeinen herrscht, ohne an die Terminologie einer bestimmten Datenbank und eines bestimmten Datenverwaltungssystems gebunden zu sein, das Gefühl, dass Sharding nur Zeile für Zeile, Dokument für Dokument usw. bedeutet – das ist alles.

Ich betone typisch. In dem Sinne, dass wir das alles nicht nur tun, um 2 Milliarden Dokumente in 20 Tabellen zu zerlegen, die jeweils besser zu verwalten wären, sondern um sie auf viele Kerne, viele Festplatten oder viele verschiedene physische oder virtuelle Server zu verteilen.

1.2 Teilen Sie das Unteilbare

Es versteht sich, dass wir dies so tun, dass jeder Shard – jedes Datenelement – ​​viele Male repliziert wird. Aber wirklich, nein.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Tatsächlich generieren Sie, wenn Sie eine solche Datenaufteilung durchführen und aus einer riesigen SQL-Tabelle auf MySQL auf Ihrem tapferen Laptop 16 kleine Tabellen generieren, ohne über einen einzigen Laptop, kein einziges Schema, keine einzige Datenbank usw. hinauszugehen . usw. - Das war's, Sie haben bereits Sharding.

Daraus ergibt sich Folgendes:

• Die Bandbreite erhöht sich.
• Die Latenz ändert sich nicht, das heißt, jeder, in diesem Fall Arbeiter oder Verbraucher, bekommt sozusagen sein eigenes. Verschiedene Anfragen werden etwa gleichzeitig bearbeitet.
• Oder beides, und noch etwas, und auch Hochverfügbarkeit (Replikation).

Warum Bandbreite? Wir können manchmal solche Datenmengen haben, die nicht auf 1 {Kernel | passen – es ist nicht klar, wo, aber sie passen nicht – Festplatte | Server | ...}. Es gibt einfach nicht genug Ressourcen, das ist alles. Um mit diesem großen Datensatz arbeiten zu können, müssen Sie ihn zerschneiden.

Warum Latenz? Auf einem Kern ist das Scannen einer Tabelle mit 2 Milliarden Zeilen 20-mal langsamer als das parallele Scannen von 20 Tabellen auf 20 Kernen. Daten werden auf einer einzelnen Ressource zu langsam verarbeitet.

Warum Hochverfügbarkeit? Oder wir schneiden die Daten, um beides gleichzeitig zu tun, und gleichzeitig mehrere Kopien jedes Shards – die Replikation sorgt für eine hohe Verfügbarkeit.

1.3 Ein einfaches Beispiel „wie man es von Hand macht“

Bedingtes Sharding kann mithilfe der Testtabelle test.documents für 32 Dokumente ausgeschnitten werden und aus dieser Tabelle 16 Testtabellen generiert werden, jeweils etwa 2 Dokumente test.docs00, 01, 02, ..., 15.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Warum ungefähr? Da wir a priori nicht wissen, wie die IDs verteilt sind, gibt es von 1 bis einschließlich 32 jeweils genau 2 Dokumente, andernfalls nicht.

Wir machen es hier warum. Nachdem wir 16 Tische erstellt haben, können wir uns 16 von dem „schnappen“, was wir brauchen. Unabhängig davon, was wir erreichen, können wir diese Ressourcen parallelisieren. Wenn beispielsweise nicht genügend Speicherplatz vorhanden ist, wäre es sinnvoll, diese Tabellen auf separate Festplatten zu verteilen.

Das alles ist leider nicht kostenlos. Ich vermute, dass es im Fall des kanonischen SQL-Standards (ich habe den SQL-Standard schon lange nicht mehr gelesen, vielleicht wurde er schon lange nicht mehr aktualisiert) keine offizielle standardisierte Syntax für die Aussage zu einem SQL-Server gibt : „Lieber SQL-Server, mache mir 32 Shards und teile sie auf 4 Festplatten auf. Aber in einzelnen Implementierungen gibt es oft eine spezifische Syntax, um im Grunde dasselbe zu tun. PostgreSQL hat Mechanismen zur Partitionierung, MySQL hat MariaDB, Oracle hat das alles wahrscheinlich schon vor langer Zeit gemacht.

Wenn wir es jedoch von Hand, ohne Datenbankunterstützung und im Rahmen des Standards machen, dann bezahlen wir bedingt mit der Komplexität des Datenzugriffs . Wo es ein einfaches SELECT * FROM Documents WHERE id=123 gab, jetzt 16 x SELECT * FROM docsXX. Und es ist gut, wenn wir versuchen würden, die Aufzeichnung per Schlüssel zu erhalten. Viel interessanter wäre es, wenn wir versuchen würden, eine frühe Auswahl an Datensätzen zu erhalten. Nun (wenn wir, das betone ich, sozusagen Dummköpfe sind und im Rahmen des Standards bleiben), müssen die Ergebnisse dieser 16 SELECT * FROM in der Anwendung kombiniert werden.

Welche Leistungsveränderung können Sie erwarten?

• Intuitiv - linear.
• Theoretisch - sublinear, weil Amdahl-Gesetz.
• Praktisch, vielleicht fast linear, vielleicht auch nicht.

Tatsächlich ist die richtige Antwort unbekannt. Mit einer cleveren Anwendung der Sharding-Technik können Sie eine erhebliche superlineare Verschlechterung der Leistung Ihrer Anwendung erreichen, und selbst der DBA wird mit einem glühenden Schürhaken ins Rennen gehen.

Mal sehen, wie dies erreicht werden kann. Es ist klar, dass es nicht interessant ist, einfach die Einstellung auf PostgreSQL shards=16 zu setzen und dann von selbst loszulegen. Lassen Sie uns darüber nachdenken, wie wir sicherstellen können, dass wir das Sharding um das 16-fache um das 32-fache verlangsamen. Dies ist unter dem Gesichtspunkt interessant, wie wir dies nicht tun können.

Unsere Versuche, schneller oder langsamer zu werden, werden immer auf die Klassiker stoßen – das gute alte Amdahl-Gesetz, das besagt, dass es keine perfekte Parallelisierung einer Anfrage gibt, sondern immer einen konsistenten Teil.

1.4 Amdahl-Gesetz

Es gibt immer einen serialisierten Teil.

Es gibt immer einen Teil der Abfrageausführung, der parallelisiert ist, und es gibt immer einen Teil, der nicht parallelisiert ist. Auch wenn Sie den Eindruck haben, dass es sich um eine vollkommen parallele Abfrage handelt, ist immer zumindest die Sammlung der Ergebniszeilen vorhanden, die Sie aus den von jedem Shard empfangenen Zeilen an den Client senden, und sie ist immer sequentiell.

Es gibt immer einen konsistenten Teil. Es kann winzig sein, vor dem allgemeinen Hintergrund völlig unsichtbar, es kann gigantisch sein und dementsprechend die Parallelisierung stark beeinflussen, aber es existiert immer.

Darüber hinaus ändert sich sein Einfluss und kann erheblich zunehmen. Wenn wir beispielsweise unsere Tabelle – erhöhen wir den Einsatz – von 64 Datensätzen auf 16 Tabellen mit 4 Datensätzen reduzieren, wird sich dieser Teil ändern. Angesichts dieser gigantischen Datenmengen arbeiten wir natürlich mit einem Mobiltelefon und einem 2-MHz-86-Prozessor und haben nicht genügend Dateien, die gleichzeitig geöffnet bleiben können. Anscheinend öffnen wir bei solchen Eingaben jeweils eine Datei.

• Es war Total = Serial + Parallel . Dabei ist beispielsweise parallel die gesamte Arbeit in der Datenbank und seriell das Senden des Ergebnisses an den Client.
• Wurde Total2 = Serial + Parallel/N + Xserial . Wenn beispielsweise die gesamte ORDER BY, Xserial>0.

Mit diesem einfachen Beispiel versuche ich zu zeigen, dass etwas Xserial erscheint. Neben der Tatsache, dass es immer einen serialisierten Teil gibt und der Tatsache, dass wir versuchen, parallel mit Daten zu arbeiten, gibt es einen zusätzlichen Teil, der dieses Daten-Slicing ermöglicht. Grob gesagt benötigen wir möglicherweise:

• Finden Sie diese 16 Tabellen im internen Wörterbuch der Datenbank.
• offene Dateien;
• Speicher zuweisen;
• Speicherzuordnung aufheben;
• Ergebnisse zusammenführen;
• Synchronisierung zwischen Kernen.

Es treten immer noch einige asynchrone Effekte auf. Sie können unbedeutend sein und ein Milliardstel der Gesamtzeit einnehmen, aber sie sind immer ungleich Null und immer vorhanden. Mit ihrer Hilfe können wir nach dem Sharding dramatische Leistungseinbußen hinnehmen.

Dies ist ein Standardbild über Amdahls Gesetz. Wichtig dabei ist, dass die Linien, die idealerweise gerade sein und linear wachsen sollten, in eine Asymptote laufen. Da die Grafik aus dem Internet aber unleserlich ist, habe ich meiner Meinung nach eher anschauliche Tabellen mit Zahlen erstellt.

Nehmen wir an, wir haben einen serialisierten Teil der Anforderungsverarbeitung, der nur 5 % in Anspruch nimmt: serial = 0.05 = 1 / 20 .

Intuitiv scheint es, dass bei einem serialisierten Teil, der nur 1/20 der Anforderungsverarbeitung in Anspruch nimmt, die Anforderungsverarbeitung für 20 Kerne parallelisiert wird und sie etwa 20-mal, im schlimmsten Fall sogar 18-mal schneller wird.

Tatsächlich ist Mathematik eine herzlose Sache :

Wand = 0,05 + 0,95/num_cores, Beschleunigung = 1 / (0,05 + 0,95/num_cores)

Es stellt sich heraus, dass bei sorgfältiger Berechnung bei einem serialisierten Teil von 5 % die Beschleunigung das Zehnfache (10,3) beträgt, was 51 % im Vergleich zum theoretischen Ideal entspricht.

Wenn wir 20 Kerne (20 Festplatten, wenn Sie so wollen) für die Aufgabe verwenden, an der früher einer gearbeitet hat, werden wir theoretisch nie eine Beschleunigung von mehr als dem 20-fachen erreichen, in der Praxis jedoch viel weniger. Darüber hinaus nimmt die Ineffizienz mit zunehmender Anzahl von Parallelen stark zu.

Wenn nur noch 1 % der serialisierten Arbeit übrig bleibt und 99 % parallelisiert sind, verbessern sich die Beschleunigungswerte etwas:

Für eine perfekt thermonukleare Abfrage, deren Fertigstellung natürlich Stunden in Anspruch nimmt und die Vorbereitungsarbeiten und die Zusammenstellung des Ergebnisses nur sehr wenig Zeit in Anspruch nehmen (seriell = 0,001), werden wir bereits eine gute Effizienz feststellen:

Bitte beachten Sie, dass wir nie 100 % sehen werden . In besonders guten Fällen sieht man beispielsweise 99,999 %, aber nicht genau 100 %.