👵🏻 👨🏽‍🎓 👩🏾‍🤝‍👨🏼 Datenverteilung in Apache Ignite 🥝 ↩️ 🕡

Hallo! Dieser Beitrag ist eine leicht gekürzte Version meines gleichnamigen Vortrags beim Apache Ignite- Community-Meeting . Sie können die vollständige Videoversion mit Fragen und Antworten hier ansehen und die Folien hier herunterladen . In dem Bericht habe ich versucht, anhand von Beispielen zu zeigen, wie Daten in Apache Ignite verteilt werden.

Warum müssen Sie etwas verteilen?

Eine ziemlich normale Geschichte der Entwicklung eines Systems, das Datenspeicherung und -verarbeitung erfordert, ist das Erreichen einer bestimmten Obergrenze. Entweder gibt es viele Daten und sie werden nicht physisch auf dem Speichergerät abgelegt, oder die Last wächst so schnell, dass ein Server eine solche Anzahl von Anforderungen nicht mehr verarbeiten kann. Es gibt häufige Fälle, in denen beide auftreten.

In der Regel gibt es eine von zwei Lösungen: entweder das Sharding des vorhandenen Speichers oder das Wechseln zu einer verteilten Datenbank. Beide Lösungen haben eine Reihe gemeinsamer Merkmale, von denen das offensichtlichste die Verwendung von mehr als einem Knoten für die Arbeit mit Daten ist. Außerdem werde ich viele Knoten Topologie nennen.

Das Problem der Datenverteilung zwischen Topologieknoten kann als eine Reihe von Anforderungen formuliert werden, die unsere Verteilung erfüllen muss:

Es wird ein Algorithmus benötigt, mit dem alle Knoten der Topologie und der Clientanwendungen zu derselben Schlussfolgerung gelangen können, auf welchem Knoten oder welchen Knoten sich das bestimmte Objekt (oder der bestimmte Schlüssel) befindet.
Gleichmäßige Verteilung. Je gleichmäßiger die Daten auf die Knoten verteilt sind, desto gleichmäßiger wird die Belastung dieser Knoten verteilt. Hier gehe ich davon aus, dass unsere Knoten ungefähr die gleichen Ressourcen haben.
. , , . , , , .

Das Erreichen der ersten beiden Anforderungen ist ziemlich einfach.

Ein bekannter Ansatz, der häufig beim Lastausgleich zwischen funktional äquivalenten Servern verwendet wird, indem Modulo N geteilt wird, wobei N die Anzahl der Knoten in der Topologie ist und wir eine Eins-zu-Eins-Entsprechung zwischen der Knotennummer und ihrer Kennung haben. Dann müssen wir nur noch den Schlüssel des Objekts als numerischen Wert unter Verwendung einer Hash-Funktion darstellen und den Rest der Division durch N vom erhaltenen Wert nehmen.

Bild

Das Diagramm zeigt die Verteilung von 16 Schlüsseln auf 3 Knoten. Es ist ersichtlich, dass diese Verteilung einheitlich ist und der Algorithmus zum Erhalten des Knotens für das Objekt einfach ist und garantiert, dass, wenn alle Knoten der Topologie diesen Algorithmus verwenden, dasselbe Ergebnis für denselben Schlüssel und dasselbe N erhalten wird.

Aber was passiert, wenn wir den 4. Knoten in die Topologie einführen?

Bild

Unsere Funktion hat sich geändert, jetzt nehmen wir den Rest der Division durch 4, nicht durch 3. Und wenn sich die Funktion geändert hat, hat sich die Verteilung geändert, und sehr.

Hier wird die vorherige Position der Objekte für die vorherige Version der Topologie von drei Knoten rot angezeigt, und die Position der Objekte für die neue Version der Topologie von vier Knoten ist grün. Dies ist den üblichen Diff-Dateien sehr ähnlich, aber anstelle von Dateien haben wir Knoten.

Es ist leicht zu erkennen, dass die Daten nicht nur auf den neuen Knoten verschoben wurden, sondern auch ein Datenaustausch zwischen Knoten stattfand, die sich bereits in der Topologie befanden. Jene. Wir beobachten störenden Verkehr zwischen Knoten und die Anforderung einer minimalen Änderung der Verteilung ist nicht erfüllt.

Zwei beliebte Möglichkeiten zur Lösung des Problems der Datenverteilung unter Berücksichtigung der aufgeführten Anforderungen sind:

Konsistentes Hashing
Größter Zufallsgewichtsalgorithmus (HRW), auch als Rendezvous-Hashing bekannt.

Beide Algorithmen sind sehr einfach. Ihre Beschreibungen auf Wikipedia passen in mehrere Sätze. Obwohl es schwierig ist, sie als offensichtlich zu bezeichnen. Für Interessenten empfehle ich, die Originalartikel Consistent Hashing und Random Trees zu lesen : Distributed Caching Protocols zur Linderung von Hot Spots im World Wide Web und ein namensbasiertes Mapping-Schema für Rendezvous . Meiner Meinung nach wird in diesem Stanford-Kurs verständlicherweise die Idee eines konsistenten Hashing-Algorithmus vermittelt .

Schauen wir uns diese Algorithmen genauer an.

Konsequentes Hashing

Der Trick, der dem konsistenten Hashing-Algorithmus zugrunde liegt, besteht darin, sowohl Knoten als auch gespeicherte Objekte demselben Identifikatorraum zuzuordnen. Dies macht unsere scheinbar unterschiedlichen Entitäten, Objekte und Knoten vergleichbar.

Um eine solche Zuordnung zu erhalten, wenden wir einfach dieselbe Hash-Funktion auf die Schlüssel der Objekte und auf die Bezeichner der Knoten an. Das Ergebnis der Hash-Funktion für den Knoten wird als Token bezeichnet. Dies wird uns später nützlich sein.

Wir stellen unseren Identifikatorraum in Form eines Kreises dar, d.h. Wir nehmen einfach an, dass der maximale Bezeichnerwert unmittelbar auf den minimalen Bezeichnerwert folgt.

Um nun zu bestimmen, auf welchem Knoten sich das Objekt befindet, müssen Sie den Wert der Hash-Funktion von ihrem Schlüssel abrufen und sich dann einfach im Uhrzeigersinn um den Kreis bewegen, bis wir unterwegs auf das Token eines Knotens stoßen. Die Bewegungsrichtung ist unwichtig, muss aber festgelegt werden.

Die imaginäre Bewegung im Uhrzeigersinn entspricht funktional einer binären Suche in einem sortierten Array von Knoten-Token.

Bild

In dem Diagramm spiegelt jeder Sektor einer bestimmten Farbe den Identifizierungsraum wider, für den ein bestimmter Knoten verantwortlich ist.

Wenn wir einen neuen Knoten hinzufügen, wird ...

Bild

... einer der Sektoren in zwei Teile geteilt und die entsprechenden Schlüssel vollständig übernommen.

In diesem Beispiel hat Knoten 3 einen Teil der Schlüssel von Knoten 1 übernommen.

Wie Sie sehen können, führt dieser Ansatz zu einer ziemlich ungleichmäßigen Verteilung der Objekte auf die Knoten, weil Es hängt stark von den Kennungen der Knoten selbst ab. Wie kann dieser Ansatz verbessert werden?

Sie können Knoten mehr als ein Token zuweisen (normalerweise Hunderte). Dies kann zum Beispiel erreicht werden, indem viele Hash-Funktionen für den Knoten eingeführt werden (eine pro Token) oder wiederholt dieselbe Hash-Funktion auf das im vorherigen Schritt erhaltene Token angewendet wird. Aber wir dürfen die Kollisionen nicht vergessen. Es sollten nicht zwei Knoten mit demselben Token vorhanden sein.

Bild

In diesem Beispiel verfügt jeder Knoten über 4 Token.

Was noch wichtig zu erwähnen ist: Wenn wir die Sicherheit von Daten für den Fall gewährleisten möchten, dass ein Knoten die Topologie verlässt, müssen wir die Schlüssel auf mehreren Knoten speichern (sogenannte Replikate oder Backups). Im Fall des konsistenten Hashing-Algorithmus sind die Replikate die folgenden N-1-Knoten auf dem Kreis, wobei N der Replikationsfaktor ist. Natürlich sollte die Reihenfolge der Knoten durch ein bestimmtes Token (zum Beispiel durch das erste) bestimmt werden, weil Wenn für jeden von ihnen mehrere Token verwendet werden, kann die Anordnung der Knoten unterschiedlich sein. Beachten Sie das Schema: Es gibt kein klares Muster für die Wiederholung von Knoten.

Das Erfordernis einer minimalen Änderung der Verteilung beim Ändern der Topologie ist erfüllt, da die gegenseitige Reihenfolge der Knoten auf dem Kreis unverändert bleibt. Jene. Durch Entfernen eines Knotens aus der Topologie wird die Ordnungsbeziehung zwischen den verbleibenden Knoten nicht geändert.

Rendezvous-Hashing

Der Rendezvous-Hashing-Algorithmus scheint noch einfacher zu sein als konsistentes Hashing. Der Algorithmus basiert auf dem gleichen Prinzip der Invarianz von Ordnungsbeziehungen. Anstatt Knoten und Objekte vergleichbar zu machen, machen wir nur Knoten für ein bestimmtes Objekt vergleichbar. Jene. Wir bestimmen die Ordnungsbeziehung zwischen Knoten für jedes Objekt unabhängig.

Auch hier hilft uns das Hashing. Um nun das Gewicht des Knotens N für ein gegebenes Objekt O zu bestimmen, mischen wir nun die Kennung des Objekts mit der Kennung des Knotens und nehmen den Hash aus dieser Mischung. Nachdem wir diese Operation für jeden Knoten ausgeführt haben, erhalten wir eine Reihe von Gewichten, nach denen wir die Knoten sortieren.

Der Knoten, der sich als der erste herausstellte und für das Speichern des Objekts verantwortlich ist.

Da alle Knoten der Topologie dieselben Eingabedaten verwenden, ist das Ergebnis für sie identisch. Welches erfüllt die erste Anforderung.

Bild

Betrachten Sie ein Beispiel. Hier haben wir eine Ordnungsbeziehung zwischen drei Knoten für vier verschiedene Schlüssel. Gelb zeigt den Knoten mit dem höchsten Gewicht an, d.h. der Knoten, der letztendlich für einen bestimmten Schlüssel verantwortlich ist.

Fügen Sie der Topologie einen weiteren Knoten hinzu.

Bild

Ich habe es absichtlich auf die Diagonale gelegt, um alle möglichen Optionen zu berücksichtigen. Hier trat der grün dargestellte Knoten 3 in die Topologie ein. Daher hat sich die Gewichtsverteilung der Knoten für jeden der Schlüssel geändert. Rot zeigt die Knoten an, die ihre Position in der Liste für einen bestimmten Schlüssel geändert haben, weil Die Gewichte dieser Knoten waren geringer als das Gewicht des hinzugefügten Knotens. Diese Änderung betraf jedoch nur einen der Schlüssel, K3.

Lassen Sie uns einen Knoten auf verräterische Weise aus einer Topologie ableiten.

Bild

Die Änderungen betrafen erneut nur einen Schlüssel, diesmal K1. Die restlichen Objekte waren nicht betroffen. Der Grund ist, wie im Fall von konsistentem Hashing, die Invarianz der Ordnungsbeziehung zwischen einem Knotenpaar. Jene. Die Anforderung einer minimalen Änderung der Verteilung ist erfüllt und es gibt keinen störenden Verkehr zwischen Knoten.

Die Verteilung für Rendezvous sieht ziemlich gut aus und erfordert keine zusätzlichen Tricks im Vergleich zu konsistentem Hashing wie Token.

Wenn wir die Replikation unterstützen möchten, ist der nächste Knoten in der Liste das erste Replikat für das Objekt, der nächste Knoten das zweite Replikat usw.

Wie Rendezvous-Hashing in Apache Ignite verwendet wird

Die sogenannte Affinitätsfunktion ist für die Verteilung von Daten in Apache Ignite verantwortlich (siehe die AffinityFunction- Schnittstelle ). Die Standardimplementierung ist Rendezvous-Hashing (siehe RendezvousAffinityFunction- Klasse ).

Das erste, worauf Sie achten müssen, ist, dass Apache Ignite gespeicherte Objekte nicht direkt Topologieknoten zuordnet. Stattdessen wird ein zusätzliches Konzept eingeführt - Partition.

Eine Partition ist ein Container für Objekte und eine Replikationseinheit. Darüber hinaus wird die Anzahl der Partitionen für einen bestimmten Cache (dies ist ein Analogon zur Tabelle in den bekannten Datenbanken) in der Konfigurationsphase festgelegt und ändert sich während des Cache-Lebenszyklus nicht.

Auf diese Weise können wir Objekte auf Partitionen mithilfe einer effektiven Modulo-Division anzeigen und mithilfe von Rendezvous-Hashing Partitionen auf Knoten anzeigen.

Bild

weil Die Anzahl der Partitionen für den Cache ist eine Konstante. Dann können wir die Partitionsverteilung nach Knoten einmal berechnen und das Ergebnis zwischenspeichern, bis die Topologie geändert wird.

Jeder Knoten berechnet diese Verteilung unabhängig, aber auf allen Knoten mit denselben Eingabedaten ist diese Verteilung identisch.

Partition kann mehrere Kopien haben, wir nennen sie Backups. Die primäre Partition wird als primäre Partition bezeichnet.

Für die beste Verteilung von Schlüsseln zwischen Partitionen und Partitionen nach Knoten muss die folgende Regel erfüllt sein: Die Anzahl der Partitionen sollte erheblich größer sein als die Anzahl der Knoten. Die Anzahl der Schlüssel sollte wiederum erheblich größer sein als die Anzahl der Partitionen.

Caches in Ignite werden partitioniert und repliziert.

In einem partitionierten Cache wird die Anzahl der Sicherungen in der Phase der Cacheerstellung festgelegt. Partitionen - Primär- und Sicherungen - werden gleichmäßig auf die Knoten verteilt. Ein solcher Cache eignet sich am besten für die Arbeit mit Betriebsdaten, wie z Bietet die beste Schreibleistung, die direkt von der Anzahl der Sicherungen abhängt. Je mehr Backups vorhanden sind, desto mehr Knoten müssen im Allgemeinen den Schlüsseldatensatz bestätigen.

Bild

In diesem Beispiel verfügt der Cache über eine Sicherung. Jene. Wir können einen Knoten verlieren und keine Daten verlieren, weil Partitionssicherungen werden niemals auf demselben Knoten wie die primäre Partition oder ihre andere Sicherung gespeichert.

Im replizierten Cache entspricht die Anzahl der Sicherungen immer der Anzahl der Topologieknoten minus 1. Das heißt, Jeder Knoten enthält immer Kopien aller Partitionen.

Bild

Ein solcher Cache eignet sich am besten für die Arbeit mit selten geänderten Daten (z. B. Verzeichnissen) und bietet die höchste Verfügbarkeit Wir können N-1-Knoten (in diesem Fall 3) verlieren, ohne Daten zu verlieren. Auch bei dieser Option erhalten wir maximale Leseleistung, wenn wir das Lesen von Daten sowohl von primären Partitionen als auch von Sicherungen zulassen.

Datenkolokation in Apache Ignite

Ein wichtiges Konzept für die beste Leistung ist die Kollokation. Colocation ist die Platzierung von Objekten an derselben Stelle. In unserem Fall sind Objekte Entitäten, die im Cache gespeichert sind, und ein Ort ist ein Knoten.

Wenn Objekte auf Partitionen derselben Affinitätsfunktion verteilt sind, ist es logisch, dass Objekte mit demselben Affinitätsschlüssel in dieselbe Partition und daher auf denselben Knoten fallen. In Ignite wird dies als Affinitätskolokation bezeichnet.

Standardmäßig ist ein Affinitätsschlüssel der Primärschlüssel eines Objekts. In Ignite können Sie jedoch jedes andere Feld eines Objekts als Affinitätsschlüssel verwenden.

Durch die Kollokation wird die Datenmenge, die zwischen Knoten gesendet wird, um Berechnungen oder SQL-Abfragen durchzuführen, erheblich reduziert, was natürlich zu einer Verringerung des Zeitaufwands für diese Aufgaben führt. Betrachten Sie dieses Konzept anhand eines Beispiels.

Lassen Sie unser Datenmodell aus zwei Entitäten bestehen: order (Order) und order position (OrderItem). Eine Bestellung kann vielen Artikeln entsprechen. Die Bestell- und Artikelkennungen sind unabhängig, aber der Artikel verfügt über einen Fremdschlüssel, der auf die entsprechende Bestellung verweist.

Angenommen, wir müssen eine Aufgabe ausführen, nämlich Berechnungen für die Positionen dieser Bestellung für jede Bestellung durchzuführen.

Standardmäßig ist ein Affinitätsschlüssel ein Primärschlüssel. Daher werden Befehle und Positionen gemäß ihren Primärschlüsseln, die, wie ich mich erinnere, unabhängig voneinander auf die Knoten verteilt werden.

Bild

Im Diagramm werden Ordnungen durch Quadrate und Positionen in Kreisen dargestellt. Farbe zeigt an, dass der Artikel zur Bestellung gehört.

Bei dieser Datenverteilung wird unsere hypothetische Aufgabe an den Knoten gesendet, an dem sich die gewünschte Reihenfolge befindet. Anschließend müssen die Positionen aller anderen Knoten gelesen oder eine Unteraufgabe an diese Knoten gesendet werden, um das Berechnungsergebnis zu erhalten. Dies ist eine unnötige Netzwerkinteraktion, die vermieden werden kann und sollte.

Was ist, wenn wir Ignite mitteilen, dass Bestellpositionen auf denselben Knoten wie die Bestellungen selbst platziert werden müssen, d. H. Daten sammeln?

Als Affinitätsschlüssel für die Position verwenden wir den Fremdschlüssel OrderId. Dieses Feld wird bei der Berechnung der Partition verwendet, zu der der Datensatz gehört. Darüber hinaus können wir unser Objekt innerhalb der Partition immer anhand des Primärschlüssels finden.

Bild

Wenn nun beide Caches (Order und OrderItem) dieselbe Affinitätsfunktion mit denselben Parametern verwenden, befinden sich unsere Daten in der Nähe und wir müssen nicht mehr im Netzwerk nach Bestellartikeln suchen.

Affinitätskonfiguration in Apache Ignite

In der aktuellen Implementierung ist ein Affinitätsfunktionsobjekt ein Cache-Konfigurationsparameter.

Die Affinitätsfunktion selbst verwendet beim Erstellen die folgenden Argumente:

Anzahl der Partitionen;
Die Anzahl der Sicherungen (tatsächlich ist dies auch der Konfigurationsparameter des Caches);
Sicherungsfilter;
Flag excludeNeighbors.

Diese Einstellungen können nicht geändert werden.

Mit der Anzahl der Partitionen und Backups scheint alles klar zu sein. Ich werde etwas später über den Sicherungsfilter und das excludeNeighbors-Flag sprechen.

Zur Laufzeit empfängt die Eingabe-Affinitätsfunktion die aktuelle Cluster-Topologie - im Wesentlichen eine Liste von Cluster-Knoten - und berechnet die Partitionsverteilung nach Knoten anhand der Beispiele, die ich gezeigt habe, als ich über den Rendezvous-Hashing-Algorithmus gesprochen habe.

Der Sicherungsfilter ist ein Prädikat, mit dem Sie verhindern können, dass Affinitätsfunktionen Sicherungspartitionen einem Knoten zuweisen, für den das Prädikat false zurückgegeben hat.

Angenommen, unsere physischen Knoten - Server - befinden sich im Rechenzentrum in verschiedenen Racks. Normalerweise hat jedes Rack seine eigene unabhängige Leistung ...

Bild

... und wenn wir das Rack verlieren, verlieren wir die Daten.

Bild

In diesem Beispiel haben wir die Hälfte der Partitionen verloren.

Wenn wir jedoch den richtigen Sicherungsfilter einstellen, ändert sich die Verteilung so, dass bei einem

Bild

Verlust des Racks kein Datenverlust auftritt und diese weiterhin verfügbar sind.

Bild

Das Flag excludeNeighbors erfüllt eine ähnliche Funktion, und tatsächlich ist es eine Abkürzung für einen bestimmten Fall.

Oft werden mehrere Ignite-Knoten auf demselben physischen Host ausgeführt. Dieser Fall ist dem Beispiel mit Racks im Rechenzentrum sehr ähnlich. Erst jetzt bekämpfen wir den Datenverlust mit dem Verlust des Hosts, nicht der Racks.

Bild

Der Rest ist der gleiche. Sie können dieses Verhalten mithilfe eines Sicherungsfilters implementieren. Diese Flagge ist ein historisches Erbe und kann in der nächsten Hauptversion von Ignite entfernt werden.

Es scheint, dass ich über die Affinitätsfunktion und Datenverteilung alles gesprochen habe, was ein Entwickler, der Apache Ignite verwendet, wissen muss.

Lassen Sie uns abschließend ein Beispiel für die Verteilung von 16 Partitionen gemäß der Topologie von 3 Knoten betrachten. Der Einfachheit und Klarheit halber glauben wir, dass Partitionen keine Backups haben.

Ich habe gerade einen kleinen Test gemacht, der mir die tatsächliche Verteilung gebracht hat:

Bild

Wie Sie sehen können, ist die Gleichmäßigkeit der Verteilung nicht ideal. Der Fehler wird jedoch mit zunehmender Anzahl von Knoten und Partitionen merklich geringer sein. Die Hauptregel, die beachtet werden muss, ist, dass die Anzahl der Partitionen erheblich größer ist als die Anzahl der Knoten. In Ignite beträgt die Standardanzahl der Partitionen für einen partitionierten Cache 1024.

Fügen Sie der Topologie nun einen neuen Knoten hinzu.

Bild

Ein Teil der Parteien zog zu ihm. Gleichzeitig wurde die Anforderung einer minimalen Änderung der Verteilung eingehalten: Der neue Knoten erhielt einen Teil der Partitionen, während die anderen Knoten keine Partitionen austauschten.

Wir entfernen aus der Topologie den Knoten, der im Anfangsstadium darin vorhanden war:

Bild

Jetzt wurden alle Partitionen, die dem Nullknoten zugeordnet waren, auf andere Knoten der Topologie verteilt, ohne unsere Verteilungsanforderungen zu verletzen.

Wie Sie sehen können, basiert die Lösung komplexer Probleme häufig auf ziemlich trivialen, wenn auch nicht ganz offensichtlichen Ideen. Die beschriebenen Lösungen werden in den meisten verteilten Datenbanken verwendet und leisten gute Arbeit. Diese Entscheidungen sind jedoch zufällig und daher ist die Gleichmäßigkeit der Verteilung alles andere als ideal. Kann die Gleichmäßigkeit verbessert werden, ohne die Leistung und andere Verteilungsanforderungen zu beeinträchtigen? Die Frage bleibt offen.