Ist vor ein paar Tagen passiert . Die Jungs von der JUG.ru Group luden Traumredner ein (Leslie Lamport! Cliff Click! Martin Kleppmann!) und widmeten zwei Tage verteilten Systemen und Computern. Kontur war einer der drei Partner der Konferenz. Wir unterhielten uns am Stand, sprachen über unseren verteilten Speicher, spielten Bingo und lösten Rätsel.
Dies ist ein Beitrag mit einer Analyse der Aufgaben am Kontur-Stand vom Autor ihres Textes. Wer auf der Hydra war – das ist Ihr Grund, sich an das angenehme Erlebnis zu erinnern, wer nicht – eine Chance, Ihr Gehirn zu trainieren großes O.-Notation.
Es gab sogar Teilnehmer, die das Flipchart in Folien zerlegten, um ihre Entscheidung niederzuschreiben. Ich mache keine Witze – sie haben diesen Stapel Papier zur Überprüfung übergeben:
Insgesamt gab es drei Aufgaben:
- Informationen zur Auswahl von Replikaten nach Gewichten für den Lastausgleich
- Informationen zum Sortieren von Abfrageergebnissen anhand einer In-Memory-Datenbank
- zur Zustandsübertragung in einem verteilten System mit Ringtopologie
Aufgabe 1. ClusterClient
Es war notwendig, einen Algorithmus zur effizienten Auswahl von K aus N gewichteten Replikaten eines verteilten Systems vorzuschlagen:
Ihr Team hat die Aufgabe, eine Client-Bibliothek für einen massiv verteilten Cluster von N Knoten zu entwickeln. Die Bibliothek würde verschiedene Metadaten im Zusammenhang mit Knoten verfolgen (z. B. ihre Latenzen, 4xx/5xx-Antwortraten usw.) und ihnen Gleitkommagewichte W1..WN 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 – die Chance, ausgewählt zu werden, sollte proportional zur Gewichtung eines Knotens sein.
Schlagen Sie einen Algorithmus zur effizienten Auswahl von Knoten vor. Schätzen Sie die Rechenkomplexität mithilfe der Big-O-Notation.
Warum ist alles auf Englisch?
Weil in dieser Form die Konferenzteilnehmer mit ihnen kämpften und weil Englisch die offizielle Sprache von Hydra war. Die Aufgaben sahen so aus:
Nehmen Sie Papier und Bleistift, denken Sie nach, beeilen Sie sich nicht, sofort Spoiler zu öffnen 🙂
Analyse der Lösung (Video)
Ab 5:53, nur 4 Minuten:
Und so präsentierten die Jungs mit dem Flipchart ihre Lösung:
Analyse der Lösung (Text)
Die folgende Lösung liegt auf der Oberfläche: Summieren Sie die Gewichte aller Replikate, generieren Sie eine Zufallszahl von 0 bis zur Summe aller Gewichte und wählen Sie dann ein i-Replikat aus, sodass die Summe der Replikatgewichte von 0 bis (i-1) reicht ist kleiner als eine Zufallszahl und die Summe der Replikatgewichte von 0 bis i-th ist größer als sie. Es ist also möglich, ein Replikat auszuwählen, und um das nächste auszuwählen, müssen Sie den gesamten Vorgang wiederholen, ohne das ausgewählte Replikat zu berücksichtigen. Bei einem solchen Algorithmus beträgt die Komplexität der Auswahl eines Replikats O(N), die Komplexität der Auswahl von K Replikaten beträgt O(N K) ~ O(N2).
Quadratische Komplexität ist schlecht, kann aber verbessert werden. Dazu werden wir bauen für Gewichtssummen. Es entsteht ein Baum der Tiefe lg N, in dessen Blättern Replika-Gewichte und in den übrigen Knoten Teilsummen bis zur Summe aller Gewichte an der Wurzel des Baumes vorhanden sind. Als nächstes generieren wir eine Zufallszahl von 0 bis zur Summe aller Gewichtungen, suchen das i-te Replikat, entfernen es aus dem Baum und wiederholen den Vorgang, um die verbleibenden Replikate zu finden. Mit diesem Algorithmus beträgt die Komplexität des Aufbaus eines Baums O(N), die Komplexität des Findens des i-ten Replikats und seiner Entfernung aus dem Baum beträgt O(lg N), die Komplexität der Auswahl von K Replikaten beträgt O(N + K lg N) ~ O(N lg N) .
Linear-logarithmische Komplexität ist besser als quadratische Komplexität, insbesondere für große K.
Es ist dieser Algorithmus ClusterClient-Bibliotheken aus dem Projekt "". (Dort wird der Baum in O(N lg N) aufgebaut, dies hat jedoch keinen Einfluss auf die endgültige Komplexität des Algorithmus.)
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 fragmentierte In-Memory-Dokumentendatenbank zu entwickeln. Eine häufige Arbeitsbelastung besteht darin, die N-Top-Dokumente, sortiert nach einem beliebigen (nicht indizierten) numerischen Feld, aus einer Sammlung der Größe M (normalerweise N < 100 << M) auszuwählen. Eine etwas seltenere 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 Durchschnittsfall und im Worst-Case-Szenario.
Analyse der Lösung (Video)
Ab 34:50, nur 6 Minuten:
Analyse der Lösung (Text)
Oberflächenlösung: Sortieren Sie alle Dokumente (z. B. mit ), dann nehmen Sie N+S-Dokumente. In diesem Fall beträgt die Komplexität der Sortierung im Mittel O(M lg M), im schlimmsten Fall O(M2).
Es ist offensichtlich, dass es ineffizient ist, alle M-Dokumente zu sortieren und dann nur einen kleinen Teil davon zu übernehmen. Um nicht alle Dokumente zu sortieren, eignet sich ein Algorithmus , wodurch N + S der gewünschten Dokumente ausgewählt werden (sie können nach jedem Algorithmus sortiert werden). In diesem Fall wird die Komplexität im Mittel auf O(M) sinken, während der ungünstigste Fall gleich bleibt.
Sie können es jedoch noch effizienter machen – nutzen Sie den Algorithmus . In diesem Fall werden die ersten N+S-Dokumente zum Min- oder Max-Heap hinzugefügt (abhängig von der Sortierrichtung), und dann wird jedes nächste Dokument mit der Wurzel des Baums verglichen, die das aktuelle Minimum- oder Maximum-Dokument enthält. und wird bei Bedarf dem Baum hinzugefügt. . In diesem Fall beträgt die Komplexität im schlimmsten Fall, wenn man den Baum ständig neu aufbauen muss, O (M lg M), die Komplexität beträgt im Durchschnitt O (M), wie bei Quickselect.
Heap-Streaming erweist sich jedoch als effizienter, da in der Praxis die meisten Dokumente verworfen werden können, ohne den Heap nach einem einzigen Vergleich mit seinem Wurzelelement neu aufzubauen. Eine solche Sortierung ist in der in Kontur entwickelten und verwendeten Zebra In-Memory-Dokumentendatenbank implementiert.
Aufgabe 3. Staatentausch
Es war notwendig, den effizientesten Algorithmus zum Verschieben von Zuständen 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 Zustandswechsel, bei dem zwei Knoten ihre Zustände atomar austauschen. Es ist bekannt, dass ein Zustandswechsel M Millisekunden dauert. Jeder Knoten kann jederzeit an einem einzelnen Statuswechsel teilnehmen.
Wie lange dauert es, die Zustände aller Knoten in einem Cluster zu übertragen?
Analyse der Lösung (Text)
Oberflächenlösung: Vertauschen Sie die Zustände des ersten und zweiten Elements, 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 aufwenden.
Die lineare Zeit ist lang, daher können Sie die Zustände von Elementen paarweise austauschen: das erste mit dem zweiten, das dritte mit dem vierten und so weiter. Nach jedem Zustandsaustausch befindet sich jedes zweite Element an der richtigen Position. Sie müssen O(lg N) Permutationen durchführen und O(M lg N) Zeit aufwenden.
Es ist jedoch möglich, die Verschiebung noch effizienter zu gestalten – nicht in linearer, sondern in konstanter Zeit. Dazu müssen Sie im ersten Schritt den Zustand des ersten Elements mit dem letzten, des zweiten mit dem vorletzten usw. austauschen. Der Status des letzten Elements befindet sich an der richtigen Position. Und jetzt müssen wir den Zustand des zweiten Elements mit dem letzten, des dritten mit dem vorletzten usw. austauschen. Nach dieser Austauschrunde befinden sich die Zustände aller Elemente in der richtigen Position. Insgesamt wird es O(2M) ~ O(1) Permutationen geben.
Eine solche Lösung wird einen Mathematiker überhaupt nicht überraschen, der sich noch daran erinnert, dass eine Rotation eine Zusammensetzung zweier Achsensymmetrien ist. Übrigens wird es trivialerweise für eine Verschiebung nicht um eine, sondern um K < N Positionen verallgemeinert. (Schreiben Sie in die Kommentare, wie genau.)
Haben dir Rätsel gefallen? Kennen Sie andere Lösungen? Teilen Sie es in den Kommentaren.
Und hier sind zum Schluss noch einige nützliche Links:
- Lerne mehr über in der Kontur
- siehe Aufzeichnungen von internen über verteilte Systeme
- Sehen Sie sich die Videovortragsreihe an»
- Abonnieren Sie unsere
Source: habr.com