Ich habe mich gefragt, was wäre die richtige Antwort für Frage 2- 44 in Skienas Algorithm Design Manual (2. Aufl.)
Die Frage ist die folgende:
Wir haben 1.000 Datenelemente zum Speichern auf 1.000 Knoten. Jeder Knoten kann speichern Kopien von genau drei verschiedenen Artikeln. Schlagen Sie ein Replikationsschema vor um den Datenverlust zu minimieren, wenn Knoten ausfallen. Was ist die erwartete Anzahl von Dateneinträge, die verloren gehen, wenn drei zufällige Knoten ausfallen?
Ich dachte über Knoten n mit Datenelement aus n, n + 1 & amp; n + 2.
Wenn also 3 aufeinanderfolgende Knoten verloren gehen, verlieren wir 1 Gegenstand.
Gibt es eine bessere Lösung?
Der Ansatz, den Sie vorschlagen, ist nicht schlecht, aber werfen Sie auch einen Blick hier . Die in RAID verwendeten Ideen können Ihnen einige Ideen geben. Wenn Sie zum Beispiel 2 Datenelemente haben, dann haben Sie Speicher für 3 Elemente, die Sie wiederherstellen können, wenn das andere fehlschlägt. Die Idee ist ziemlich einfach - Sie speichern die Elemente in 2 Knoten und die Xor ihrer Bits im dritten Element. Ich glaube, wenn Sie diese Idee verwenden, können Sie mehr als 3 Backups eines einzelnen Datenelements haben (d. H. Mehr als 3 Knoten müssen fehlschlagen, um die Information zu verlieren).
Ich habe an Methoden wie RAID-Levels gedacht, aber Skiena sagt: "Jeder Knoten kann Kopien von genau drei verschiedenen Elementen speichern." Obwohl XOR'Red-Bit-Muster von zwei separaten Daten in der gleichen Menge an Speicherplatz gespeichert werden können, dachte ich nicht, dass es etwas war, nach dem das Problem suchte.
Also begann ich mit dem, was der OP dachte: Speichern Sie die drei Kopien jeder Daten auf die nächsten zwei Nachbarn in einer gestreiften Art und Weise. Beispielsweise gilt Folgendes für N == 6 und die Daten sind die Ganzzahlen von 0 bis 5 (4 und 5 werden umbrochen und verwenden die Knoten 0 und 1):
%Vor%Von allen 20 Kombinationen von Fehlern mit drei Knoten gibt es sechs, die genau ein Stück Daten verlieren. Beispielsweise; Wenn die Knoten 1, 2 und 3 ausfallen, gehen die Daten 1 verloren:
%Vor%Ähnlich wie bei den anderen Daten, so dass 6 der 20 Kombinationen Daten verlieren. Da Skiena nicht beschreibt, was "Datenverlust" für die Anwendung bedeutet: Bedeutet der Verlust eines einzelnen Datenpunkts, dass die gesamte Sammlung verschwendet wird, oder ist das Verlieren eines einzelnen Datenpunkts akzeptabel und besser als zwei?
Wenn der Verlust von nur einem Datenpunkt bedeutet, dass die gesamte Sammlung verschwendet wird, können wir es besser machen. Drei mal besser! :)
Anstatt die Datenkopien streifenweise an die rechten Knoten zu verteilen, definieren Sie Gruppen von drei Knoten, die Daten gemeinsam nutzen. Beispiel: 0, 1 und 2 teilen ihre Daten und 3, 4 und 5 teilen ihre Daten:
%Vor%Dieses Mal gibt es nur zwei der 20 Kombinationen, die Datenverluste verursachen. Die Daten 0, 1 und 2 gehen zusammen verloren, wenn die Knoten 0, 1 und 2 fehlschlagen:
%Vor%Und die Daten 3, 4 und 5 gehen zusammen verloren, wenn die Knoten 3, 4 und 5 fehlschlagen:
%Vor%Das sind nur zwei der 20 Kombinationen von Ausfällen mit drei Knoten. Wenn dieselben Knoten dieselben Daten verwenden, werden die Datenverluste effektiv in weniger Kombinationen zusammengefasst.
Ali
Lassen Sie
%Vor%Mein Replikationsmodell hat die folgenden Annahmen:
1- Jedes Datenelement muss während der Initialisierung mindestens in einem bestimmten Knoten gespeichert werden. I .:
%Vor%2- Aus (1) ist zur Initialisierungszeit die Wahrscheinlichkeit, dass d_i in einem gegebenen Knoten ist, mindestens 1 / n. I.e .:
%Vor%Angesichts der problematischen Aussage wollen wir diese Verteilung für den Datensatz einheitlich gestalten.
3. Schließlich sollte die Wahrscheinlichkeit, dass ein Datenelement d_i in einem gegebenen Knoten n ist, zwischen Datenelementen unabhängig sein. I .:
%Vor%Dies liegt daran, dass wir nicht davon ausgehen, dass die Wahrscheinlichkeit eines Knotenfehlers zwischen benachbarten Knoten unabhängig ist (z. B. in Datenzentren, benachbarte Knoten teilen sich den gleichen Netzwerkschalter usw.).
Aus diesen Annahmen habe ich das folgende Replikationsmodell vorgeschlagen (für die Probleminstanz, wobei d = n ist und jeder Knoten genau drei verschiedene Datenelemente speichert).
(1) Führen Sie eine zufällige Permutation des Datensatzes durch. (2) Unter Verwendung eines gleitenden Fensters der Länge 3 und Schritt 1, rotiere über den gemischten Datensatz und ordne die Datenelemente jedem Knoten zu.
%Vor%Das zufällige Mischen sorgt für eine unabhängige (3) und gleichmäßige Verteilung (2). Während das Schiebefenster von Schritt 1 garantiert (1).
Bezeichnen wir das Gleitfenster eines gegebenen Knotens n_k als die geordnete Menge w_k = {w_k1, w_k2, w_k3}. n_k wird als Master-Knoten für w_k1 (erstes Element von w_k) bezeichnet. Jeder andere Knoten n_j, der w_k1 enthält, ist ein Replikknoten. N.B .: Das vorgeschlagene Replikationsmodell garantiert nur einen Masterknoten für jedes d_i, während die Anzahl der Replikknoten von der Fensterlänge abhängt.
Im obigen Beispiel: n_1 ist der Master-Knoten für C- und n_3- und n_4-Replikknoten.
Zurück zum ursprünglichen Problem, angesichts dieses Schemas, können wir die Wahrscheinlichkeit eines Datenverlusts als Verlust des Master-Knotens und aller Replikate für ein gegebenes Datenelement angeben.
P (d_i ist verloren) = P (Master-Knoten für d_i schlägt fehl und Replikat 1 schlägt fehl und Replikat 2 schlägt fehl).
ohne formellen Beweis würde eine unvoreingenommene zufällige Permutation in Schritt (1) oben resultieren
P (d_i ist verloren) = P (Masterknoten für d_i schlägt fehl) * P (Replikat 1 schlägt fehl) * P (Replikat 2 schlägt fehl).
ist die zufällige Permutation eine Heuristik, um die gemeinsame Verteilung für Knotenfehler zu abstrahieren.
Aus den Annahmen (2) und (3) ist P (d_i ist verloren) = c, für jedes d_i, zur Initialisierungszeit.
Das heißt für d = n = 1000 und den Replikationsfaktor von 3 (d.h. die Fensterlänge ist gleich 3).
P (d_i ist verloren) = 1/1000 * 1/999 * 1/998 ~ 10 ^ -9
Ihr Ansatz scheint im Wesentlichen korrekt zu sein, kann jedoch von einer Failover-Strategie profitieren. Beachten Sie, dass Prof. Skiena gebeten hat, "den Datenverlust beim Ausfall von Knoten zu minimieren", was darauf hindeutet, dass fehlerhafte Knoten häufig vorkommen.
Sie können sich das konsistente Hashing ansehen.
Außerdem gibt es einen tollen Post von reddit engineers über die Gefahren, keine konsistenten Hashing zu verwenden (stattdessen mit einem festen MOD Hashing).