Teoria:
Si tratta di elezione leader, che è una forma di Consensus Problem, talvolta chiamato anche The Two Generals Problem. Sotto alcune serie di assunzioni (completamente asincrona e messaggi possono essere persi) è stato dimostrato impossibile, e la dimostrazione è particolarmente elegante.
L'intuizione di questo problema è: immagina che esista un algoritmo che consenta di raggiungere un consenso in un numero fisso di messaggi. Poiché i guasti sono tollerati, possiamo rilasciare un messaggio dal protocollo e dovrebbe comunque funzionare. Possiamo ripetere questo processo fino a quando non ci sono messaggi, chiaramente impossibile.
In pratica superiamo questo problema utilizzando i rilevatori di guasti per simulare un sistema sincrono.
L'algoritmo più noto che risolve il consenso è Paxos, che può tollerare il fallimento di metà dei nodi partecipanti. Paxos ha la reputazione di essere molto difficile da implementare in quanto anche i piccoli malintesi dei dettagli del protocollo ne distruggono la correttezza.
Soluzioni pratiche:
Mentre il problema in generale è abbastanza difficile, ottenendo sistemi che lavorano su è molto più facile. Esistono implementazioni off-line di Paxos o algoritmi equivalenti disponibili. Apache Zookeeper è il migliore di cui sono a conoscenza. Per il tuo problema specifico, sono abbastanza sicuro che sarà il tuo percorso più veloce. Altre implementazioni di Paxos sono in giro, e potrebbe anche essere possibile creare qualcosa su strumenti ip virtuali di ridondanza di rete come Wackamole. Credo che le versioni di fascia alta della maggior parte dei database commerciali offrano funzionalità di quorum come un'opzione (costosa).
Inoltre, per molte applicazioni è accettabile indebolire leggermente la correttezza o altrimenti regolare il problema per consentire soluzioni molto più semplici.
Ad esempio, se un singolo punto di errore è tollerabile perché è probabile che il ripristino sia rapido, il problema è banale: basta fare un lavoro con un nodo speciale.
Un altro approccio potrebbe essere quello di costruire il sistema attorno a azioni identi- ficative, in modo che l'elaborazione duplicata diventi tollerabile.
Infine, è possibile partizionare il carico di lavoro in un pool di sistemi non ridondanti: qui gli errori ritardano l'elaborazione fino al ripristino, ma solo per gli elementi su quel nodo, non per l'intero carico di lavoro.
Questi tipi di compromessi sono molto più semplici e spesso rappresentano una scelta migliore. Bisogna valutare l'utilità di una soluzione completa contro la complessità di implementarlo e vedere se c'è davvero un valore. Questo è il motivo per cui così tanti sistemi pratici usano solo 2 Phase o 3 Phase Commit, anche se bloccano in alcuni scenari: la disponibilità ridotta è tollerabile rispetto alla complessità di un sistema di quorum completo.
Grazie per questa spiegazione dettagliata e i riferimenti. Concordo sul fatto che il rilassamento dei vincoli per consentire una soluzione più semplice sia una strada da esplorare. [Ora posso echeggiare l'epitaffio di Spike Milligan quando torno alla squadra "Vedi, ti ho detto che era difficile!"]. – djna
Per chiarezza, Zookeeper implementa ZAB "Zookeeper Atomic Broadcast" che corrisponde a Paxos astratto ma differisce dai Paxos classici in modo tale che i messaggi mantengano l'ordine primario che è molto importante in molti scenari. – gertas