Vor einigen Tagen gab es eine Hydra-Konferenz . Die Jungs von der JUG.ru Group luden die Traumredner ein (Leslie Lampport! Cliff Click! Martin Kleppmann!) Und widmeten sich zwei Tage lang verteilten Systemen und Computern. Contour war einer der drei Konferenzpartner. Wir sprachen am Stand, sprachen über unsere verteilten Lagereinrichtungen, spielten Bingo und lösten Probleme.
Dies ist ein Beitrag mit einer Analyse der Aufgaben am Contour-Stand des Autors ihres Textes. Wer auf Hydra war, ist Ihr Grund, sich an angenehme Eindrücke zu erinnern, wer nicht - eine Chance, die große O- Note Ihres Gehirns zu dehnen.
Es gab sogar Teilnehmer, die das Flipchart in Folien zerlegten, um ihre Entscheidung aufzuzeichnen. Ich scherze nicht - sie haben dieses Papierpaket zur Überprüfung übergeben:
Insgesamt gab es drei Aufgaben:
- über die Auswahl von Replikaten für Gewichte für den Lastausgleich
- Informationen zum Sortieren der Ergebnisse einer Abfrage in eine In-Memory-Datenbank
- zur Zustandsübertragung in einem verteilten System mit einer Ringtopologie
Aufgabe 1. ClusterClient
Es war notwendig, einen Algorithmus für die effektive Auswahl von K aus N gewichteten Repliken eines verteilten Systems vorzuschlagen:
Ihr Team hat die Aufgabe, eine Clientbibliothek für einen massiv verteilten Cluster von N Knoten zu entwickeln. Die Bibliothek würde verschiedene Metadaten verfolgen, die Knoten zugeordnet sind (z. B. ihre Latenzen, 4xx / 5xx-Antwortraten usw.) und ihnen Gleitkommagewichte W 1 ..W N zuweisen. Um die Strategie der gleichzeitigen Ausführung zu unterstützen, sollte die Bibliothek in der Lage sein, K von N Knoten zufällig auszuwählen - eine Chance, ausgewählt zu werden, sollte proportional zum Gewicht eines Knotens sein.
Schlagen Sie einen Algorithmus vor, um Knoten effizient auszuwählen. Schätzen Sie die Rechenkomplexität mithilfe der großen O-Notation.
Warum ist alles auf Englisch?Weil in dieser Form die Teilnehmer der Konferenz mit ihnen kämpften und weil Englisch die offizielle Sprache von Hydra war. Die Aufgaben sahen folgendermaßen aus:
Nehmen Sie Papier und Bleistift, denken Sie, beeilen Sie sich nicht, um die Spoiler sofort zu öffnen :)
Nachbesprechung (Video)Ab 5:53 nur 4 Minuten:
Und so haben die Jungs mit einem Flipchart ihre Entscheidung getroffen:
Analyse der Entscheidung (Text)An der Oberfläche gibt es eine solche Lösung: Summieren Sie die Gewichte aller Replikate, generieren Sie eine Zufallszahl von 0 bis zur Summe aller Gewichte und wählen Sie dann eine i-Replik, sodass die Summe der Replikatgewichte von 0 bis zum (i-1) -ten kleiner als die Zufallszahl ist, und die Summe der Replikatgewichte von 0 bis zum i-ten - mehr als es. Es stellt sich heraus, dass Sie ein Replikat auswählen müssen. Um das nächste auszuwählen, müssen Sie den gesamten Vorgang wiederholen, ohne das ausgewählte Replikat zu berücksichtigen. Mit einem solchen Algorithmus ist die Komplexität der Auswahl eines Replikats O (N), die Komplexität der Auswahl von K Replikaten ist O (N · K) ~ O (N 2 ).
Die quadratische Komplexität ist schlecht, kann aber verbessert werden. Erstellen Sie dazu einen Segmentbaum für die Gewichtssummen. Dies erzeugt einen Baum mit einer Tiefe von log N, in dessen Blättern sich Replikatgewichte befinden, und in den verbleibenden Knoten Teilsummen bis zur Summe aller Gewichte in der Wurzel des Baumes. Als nächstes generieren wir eine Zufallszahl von 0 bis zur Summe aller Gewichte, suchen das i-te Replikat, löschen es aus dem Baum und wiederholen den Vorgang, um nach den verbleibenden Replikaten zu suchen. Mit einem solchen Algorithmus ist die Komplexität des Konstruierens eines Baums O (N), die Komplexität des Findens des i-ten Replikats und des Entfernens aus dem Baum ist O (log N), die Komplexität der Auswahl von K Replikaten ist O (N + K log N) ~ O (N log N) .
Die linear-logarithmische Komplexität ist insbesondere bei großen K besser als die quadratische Komplexität.
Dieser Algorithmus ist im Code der ClusterClient-Bibliothek aus dem Vostok- Projekt implementiert .
Aufgabe 2. Zebra
Es war notwendig, einen Algorithmus zum effizienten Sortieren von Dokumenten im Speicher nach einem beliebigen nicht indizierten Feld vorzuschlagen:
Ihr Team hat die Aufgabe, eine gespeicherte In-Memory-Dokumentendatenbank zu entwickeln. Eine übliche Arbeitslast wäre die Auswahl der Top-N-Dokumente, sortiert nach einem beliebigen (nicht indizierten) numerischen Feld aus einer Sammlung der Größe M (normalerweise N <100 << M). Eine etwas geringere Arbeitsbelastung wäre die Auswahl von Top N nach dem Überspringen von Top S-Dokumenten (S ~ N).
Schlagen Sie einen Algorithmus vor, um solche Abfragen effizient auszuführen. Schätzen Sie die Rechenkomplexität mithilfe der Big-O-Notation im Durchschnitt und im schlimmsten Fall.
Nachbesprechung (Video)Start um 34:50, nur 6 Minuten:
Analyse der Entscheidung (Text)Die Lösung liegt auf der Oberfläche: Sortieren Sie alle Dokumente (z. B. mithilfe von Quicksort ) und nehmen Sie dann N + S-Dokumente. In diesem Fall beträgt die Komplexität der Sortierung im Durchschnitt O (M lg M), im schlimmsten Fall O (M 2 ).
Offensichtlich ist es ineffizient, alle M-Dokumente zu sortieren, um dann nur einen kleinen Teil davon aufzunehmen. Um nicht alle Dokumente zu sortieren, ist der Schnellauswahlalgorithmus geeignet , der N + S der erforderlichen Dokumente auswählt (sie können nach jedem Algorithmus sortiert werden). In diesem Fall nimmt die Komplexität im Durchschnitt auf O (M) ab, und der schlimmste Fall bleibt der gleiche.
Sie können dies jedoch noch effizienter tun - verwenden Sie den binären Heap-Streaming- Algorithmus. In diesem Fall werden die ersten N + S-Dokumente zum Min- oder Max-Heap hinzugefügt (abhängig von der Sortierrichtung). Anschließend wird jedes nachfolgende Dokument mit dem Stamm des Baums verglichen, der derzeit das minimale oder maximale Dokument enthält, und bei Bedarf zum Baum hinzugefügt . In diesem Fall ist die Komplexität im schlimmsten Fall, wenn Sie den Baum ständig neu erstellen müssen - O (M lg (N + S)), die durchschnittliche Komplexität ist O (M), wie bei der Schnellauswahl.
Heap-Streaming ist jedoch effektiver, da in der Praxis die meisten Dokumente nach einem einzigen Vergleich mit seinem Stammelement verworfen werden können, ohne den Heap neu zu erstellen. Eine solche Sortierung ist in der speicherinternen Zebra-Dokumentendatenbank implementiert, die in der Schaltung entwickelt und verwendet wird.
Aufgabe 3. State Swaps
Es war notwendig, den effizientesten Algorithmus für die Zustandsverschiebung vorzuschlagen:
Ihr Team hat die Aufgabe, einen ausgefallenen Zustandsaustauschmechanismus für einen verteilten Cluster von N Knoten zu entwickeln. Der Zustand des i-ten Knotens sollte auf den (i + 1) -ten Knoten übertragen werden, der Zustand des N-ten Knotens sollte auf den ersten Knoten übertragen werden. Die einzige unterstützte Operation ist der Zustandstausch, wenn zwei Knoten ihre Zustände atomar austauschen. Es ist bekannt, dass ein Zustandstausch M Millisekunden dauert. Jeder Knoten kann jederzeit an einem einzelnen Statusaustausch teilnehmen.
Wie lange dauert es, die Zustände aller Knoten in einem Cluster zu übertragen?
Analyse der Entscheidung (Text)Eine Lösung an der Oberfläche: Tauschen Sie die Zustände des ersten und zweiten Elements aus, dann des ersten und dritten, dann des ersten und vierten und so weiter. Nach jedem Austausch befindet sich der Zustand eines Elements an der gewünschten Position. Sie müssen O (N) -Permutationen durchführen und O (N · M) -Zeit verbringen.
Die lineare Zeit ist eine lange Zeit, sodass Sie die Zustände von Elementen paarweise austauschen können: die erste mit der zweiten, die dritte mit der vierten und so weiter. Nach jedem Austausch befindet sich der Zustand jedes zweiten Elements an der gewünschten Position. Wir müssen O (log N) -Permutationen durchführen und O (M log N N) -Zeit verbringen.
Sie können die Verschiebung jedoch noch effektiver gestalten - nicht linear, sondern in konstanter Zeit. Dazu müssen Sie im ersten Schritt den Status des ersten Elements gegen das letzte, das zweite gegen das vorletzte Element usw. austauschen. Der Zustand des letzten Elements befindet sich an der gewünschten Position. Und jetzt müssen Sie den Zustand des zweiten Elements gegen das letzte, das dritte gegen das vorletzte usw. austauschen. Nach dieser Austauschrunde befinden sich die Zustände aller Elemente in der richtigen Position. Insgesamt werden O (2M) ~ O (1) -Permutationen durchgeführt.
Eine solche Lösung wird einen Mathematiker nicht überraschen, der sich immer noch daran erinnert, dass Rotation eine Zusammensetzung zweier axialer Symmetrien ist. Übrigens ist es trivial verallgemeinert, nicht um eins, sondern um K <N Positionen zu verschieben. (Schreiben Sie in den Kommentaren genau wie.)
Magst du Rätsel? Kennen Sie andere Lösungen? Teilen Sie in den Kommentaren.
Und hier sind einige nützliche Links am Ende: