Ho implementato l'algoritmo di consenso Raft (l'esempio per eccellenza degli algoritmi distribuiti) in Python. È un'implementazione piuttosto scadente! Ma anche (in parte) corretta.
Ecco alcuni appunti che condividerei con chiunque fosse interessato ad affrontare una sfida simile.
Col senno di poi, queste sono state le risorse più utili per conoscere Raft e implementarlo correttamente.
- L'articolo su Raft (leggi fino alla sezione 5 e fai spesso riferimento alla figura 2)
- Guida a Raft per studenti
- una delle implementazioni di Raft più utilizzate
- clona il repository, scorri rapidamente
raft.goe confrontati a più riprese con un LLM per capire la codebase e le scelte progettuali
- clona il repository, scorri rapidamente
- La serie di articoli sul blog di Eli Bendersky
Suggerirei di dedicare prima un'oretta alla lettura dell'articolo, per poi abbozzare il codice di un server UDP o TCP che legga i byte in arrivo e li aggiunga a un array. Ho poi seguito passo passo l'implementazione di Eli, aggiungendo funzionalità alla mia implementazione di Raft nello stesso ordine.
Dopo aver fatto funzionare qualcosa che assomigliava a un meccanismo di elezione, ho iniziato a cercare bug ed errori nella mia comprensione dell'algoritmo. Passavo continuamente dalla guida per studenti alla figura 2 dell'articolo su Raft e alla mia implementazione, riflettendo con attenzione sui punti in cui la mia implementazione corrispondeva all'algoritmo (o se ne discostava). Ho anche usato molto un LLM per rivedere questo codice, aggiungendo al contesto materiale tratto dalle risorse elencate sopra.
Ripeti il processo descritto sopra per la replica del log, la persistenza, ecc.
a proposito dell'implementazione
Ho fatto alcune scelte progettuali per semplificare la mia implementazione. Senza un ordine particolare:
- ogni nodo viene eseguito ed elabora i messaggi in un unico thread
- usare un "orologio logico" per tenere traccia del "tempo" locale nel sistema (ad esempio, chiamare
tick()e incrementare un contatore locale a ciascun nodo invece di usare l'ora di sistema) - "sporcare" l'implementazione mettendo tutto in un unico file, ad esempio il parsing dei dati di rete, l'archiviazione/persistenza, il nucleo dell'algoritmo Raft e le utilità/i comandi per controllare il nodo stesso
Il punto 2 sembra una scelta progettuale solida e corretta (gli orologi logici sono usati nell'implementazione di etcd). Il punto 3 è probabilmente preferibile ai fini dell'apprendimento/della didattica. È comodo avere tutto in un unico file, così da poterlo vedere tutto insieme, e ti dà una buona implementazione da smontare per capire quali astrazioni si adattano meglio all'algoritmo.
Il punto 1 mi sembra una scelta piuttosto discutibile. Rende effettivamente l'implementazione molto più semplice (devi preoccuparti meno dei deadlock e degli aggiornamenti atomici allo stato interno del nodo), ma finisci anche con qualcosa che non è proprio Raft. Per una prima implementazione, mi sembra accettabile. L'algoritmo è già abbastanza complesso, e credo che preferiresti dedicare il tuo tempo a risolvere errori logici nel nucleo dell'algoritmo Raft piuttosto che ad armeggiare con i mutex.
Considererei l'implementazione di Raft in questo modo un progetto da ~30 ore. La lettura iniziale dell'articolo su Raft e l'esame dei materiali correlati dovrebbero richiedere qualche ora. Ho scritto il grosso del codice in ~3 giorni durante le vacanze, lavorandoci per circa 6-8 ore al giorno. Nell'implementazione attuale ho ancora alcune cose da rifinire e migliorare (ad esempio, correggere alcuni bug poco evidenti), che potrebbero richiedere un'altra mezza giornata di lavoro.
Tutto sommato, niente male per capire uno degli algoritmi fondamentali che fa funzionare così tante infrastrutture.