Ich habe den Raft-Konsensalgorithmus (das Paradebeispiel für verteilte Algorithmen) in Python implementiert. Es ist eine ziemlich schlechte Implementierung! Aber auch (einigermaßen) korrekt.
Hier sind ein paar Notizen, die ich allen mitgeben würde, die sich einer ähnlichen Herausforderung stellen möchten.
Rückblickend waren dies die nützlichsten Ressourcen, um Raft kennenzulernen und korrekt zu implementieren.
- Das Raft-Paper (bis Abschnitt 5 lesen und Abbildung 2 häufig zurate ziehen)
- Raft-Leitfaden für Studierende
- eine der am weitesten verbreiteten Raft-Implementierungen
- das Repository klonen,
raft.goüberfliegen und sich mit einem LLM austauschen, um die Codebasis und die Entwurfsentscheidungen zu verstehen
- das Repository klonen,
- Eli Benderskys Blogserie
Ich würde empfehlen, zuerst ungefähr eine Stunde lang das Paper zu lesen und dann ein erstes Codegerüst für einen UDP- oder TCP-Server zu schreiben, der eingehende Bytes liest und sie einem Array hinzufügt. Danach habe ich mich an Elis Implementierung orientiert und meiner Raft-Implementierung die Funktionen in derselben Reihenfolge hinzugefügt.
Nachdem ich etwas am Laufen hatte, das nach Leader-Wahlen aussah, habe ich angefangen, nach Bugs und Fehlern in meinem Verständnis des Algorithmus zu suchen. Dabei wechselte ich immer wieder zwischen dem Leitfaden für Studierende, Abbildung 2 im Raft-Paper und meiner Implementierung und überlegte genau, wo meine Implementierung damit übereinstimmte (oder davon abwich). Außerdem habe ich ausgiebig ein LLM zur Überprüfung dieses Codes eingesetzt und Material aus den oben genannten Ressourcen in den Kontext aufgenommen.
Den obigen Ablauf für Log-Replikation, Persistenz usw. wiederholen.
zur Implementierung
Ich habe bei meiner Implementierung einige vereinfachende Entwurfsentscheidungen getroffen. In keiner bestimmten Reihenfolge:
- jeder Knoten läuft in einem einzigen Thread und verarbeitet dort Nachrichten
- eine „logische Uhr“ verwenden, um die lokale „Zeit“ im System zu erfassen (z. B.
tick()aufrufen und einen lokalen Zähler pro Knoten erhöhen, anstatt die Systemzeit zu verwenden) - die Implementierung dadurch „unsauber“ machen, dass alles in einer Datei steckt, z. B. das Parsen von Netzwerkdaten, Speicherung/Persistenz, der eigentliche Raft-Algorithmus und Hilfsfunktionen/Befehle zur Steuerung des Knotens selbst
2 scheint eine solide und korrekte Entwurfsentscheidung zu sein (logische Uhren kommen in der Implementierung von etcd zum Einsatz). 3 ist zum Lernen bzw. aus didaktischer Sicht wohl besser. Es ist praktisch, alles in einer Datei zu haben, sodass man alles auf einmal überblicken kann, und so hat man eine gute Implementierung, die man auseinandernehmen kann, um zu sehen, welche Abstraktionen am besten zum Algorithmus passen.
1 halte ich für eine ziemlich fragwürdige Entscheidung. Das macht die Implementierung zwar deutlich einfacher (man muss sich weniger Gedanken über Deadlocks und atomare Aktualisierungen des internen Zustands des Knotens machen), aber am Ende kommt dabei auch etwas heraus, das nicht ganz Raft ist. Für eine erste Implementierung scheint mir das in Ordnung zu sein. Der Algorithmus ist komplex genug, und ich denke, man verbringt seine Zeit lieber damit, logische Fehler im eigentlichen Raft-Algorithmus zu finden und zu beheben, als sich mit Mutexen herumzuschlagen.
Raft auf diese Weise zu implementieren, würde ich als ein Projekt mit etwa 30 Stunden Aufwand einschätzen. Das erste Lesen des Raft-Papers und das Durchsehen der zugehörigen Materialien sollten ein paar Stunden dauern. Den Großteil des Codes habe ich über die Feiertage in etwa 3 Tagen geschrieben und dabei ungefähr 6-8 Stunden pro Tag daran getüftelt. An der bestehenden Implementierung muss ich noch ein paar Dinge ausfeilen und verbessern (z. B. einige subtile Bugs beheben), was noch einmal einen halben Tag Arbeit bedeuten könnte.
Alles in allem gar nicht schlecht, um einen der zentralen Algorithmen zu verstehen, auf denen so viel Infrastruktur aufbaut.