Qual è la differenza tra Paxos e W + R> = N in Cassandra?

Question

I database dinamo-simili (ad esempio Cassandra) possono applicare la coerenza per mezzo del quorum, ovvero un numero di repliche scritte in modo sincrono (W) e un numero di repliche da leggere (R) dovrebbe essere scelto in modo tale da W + R> N dove N è un fattore di replicazione. D'altra parte, i sistemi basati su PAXOS come Zookeeper vengono anche utilizzati come memoria coerente con tolleranza agli errori.

Qual è la differenza tra questi due approcci? PAXOS fornisce garanzie che non sono fornite dallo schema W + R> N?

Answer 1

Paxos non è banale da implementare, e abbastanza costoso che molti sistemi che lo usano usano anche suggerimenti, o lo facciamo solo per le elezioni dei leader, o qualcosa del genere. Tuttavia, fornisce una coerenza garantita in presenza di guasti - naturalmente ai limiti del suo particolare modello di errore.

I primi sistemi basati sul quorum che ho visto presupponevano una sorta di infrastruttura leader o di transazione che garantisse una congruenza sufficiente da garantire che il meccanismo del quorum funzionasse. Questa infrastruttura potrebbe essere basata su Paxos.

Guardando descrizioni quali https://cloudant.com/blog/dynamo-and-couchdb-clusters/, sembrerebbe che la Dinamo è non sulla base di un'infrastruttura che garantisce la coerenza per il suo sistema legale - quindi non è che sia molto intelligente o angoli di taglio? Secondo il numero http://muratbuffalo.blogspot.co.uk/2010/11/dynamo-amazons-highly-available-key.html, "Il sistema Dynamo enfatizza la disponibilità al punto di sacrificare la coerenza." La Dinamo sacrifica la coerenza in determinati scenari di fallimento. In realtà, diventa chiaro che Dynamo sacrifica la coerenza anche in assenza di guasti: Dynamo potrebbe diventare incoerente in presenza di più richieste di scrittura simultanee poiché le repliche potrebbero divergere a causa di più coordinatori. " (fine citazione)

Quindi sembrerebbe che nel caso di quorum implementato in Dynamo, Paxos fornisca maggiori garanzie di affidabilità.

Answer 2

Paxos e il quorum W + R> N cercano di risolvere problemi leggermente diversi. Paxos viene solitamente descritto come un modo per replicare una macchina a stati, ma in realtà è più un log distribuito: ogni elemento scritto nel log riceve un indice e i diversi server alla fine conservano gli stessi elementi del registro + il loro indice. (La macchina a stati replicati può essere raggiunta scrivendo nel log gli input sulla macchina a stati e ogni server riproduce la macchina a stati sugli ingressi concordati in base al loro indice). Puoi leggere di più su Paxos in un post sul blog che ho scritto here.

Il quorum W + R> N risolve il problema della condivisione di un singolo valore tra più server. Nel mondo accademico è chiamato "registro condiviso". Un registro condiviso ha due operazioni: lettura e scrittura, dove ci aspettiamo che la lettura restituisca il valore della scrittura precedente.

Quindi, Paxos e il quorum W + R> N vivono in domini diversi e hanno proprietà diverse (ad esempio, Paxos salva un elenco ordinato di elementi). Tuttavia, Paxos può essere utilizzato per implementare un registro condiviso e un quorum W + R> N può essere utilizzato per implementare un registro distribuito (anche se in modo molto inefficiente).

Dicendo tutto quanto sopra, a volte i quorum W + R> N non sono implementati nel loro modo "completamente robusto", poiché richiederà più di un round di comunicazione. Pertanto, nei sistemi che richiedono bassa latenza, è possibile che la loro implementazione dei quorum W + R> N fornisca proprietà più deboli (ad esempio, possono coesistere valori in conflitto).

Per riassumere, in teoria, Paxos e W + R> N possono raggiungere gli stessi obiettivi. In pratica, sarebbe molto inefficiente, e ognuno è migliore per qualcosa di leggermente diverso. Ancora più praticamente, W + R> N non è sempre implementato completamente, quindi scarificare alcune proprietà di coerenza per la velocità.

Aggiornamento: Paxos supporta un modello di errore molto generale: i messaggi possono essere eliminati, i nodi possono bloccarsi e riavviarsi. Lo schema del quorum W + R> N ha implementazioni dfferent, molte delle quali assumono fallimenti meno generali. Quindi, la differenza tra i due dipende anche dall'ipotesi sui possibili errori supportati.

Answer 3

Sì, Paxos fornisce garanzie che non sono fornite dai sistemi tipo Dynamo e dai loro quorum di lettura-scrittura. La differenza è come vengono gestiti i guasti e cosa succede durante una scrittura. Dopo una scrittura riuscita, entrambi i tipi di sistemi si comportano in modo simile. I dati saranno salvati e disponibili per la lettura successiva (fino a quando non vengono sovrascritti o cancellati) e così via.

La differenza appare durante una scrittura e dopo i guasti. Finché non si ottiene una risposta corretta dai nodi W quando si scrive qualcosa sui sistemi eventualmente coerenti, i dati potrebbero essere stati scritti su alcuni nodi e non su altri e non vi è alcuna garanzia che l'intero sistema accetti il ​​valore corrente. Se si tenta di leggere i dati a questo punto, alcuni client potrebbero recuperare i nuovi dati e alcuni vecchi dati. In altre parole, il sistema non è immediatamente coerente. Questo perché le scritture non sono atomiche tra i nodi in questi sistemi. Di solito ci sono meccanismi per "curare" un'incoerenza come questa e "alla fine" il sistema tornerà consistente (cioè le letture torneranno sempre lo stesso valore, fino a quando non verrà scritto qualcosa di nuovo). Questo è il motivo per cui vengono spesso definiti "alla fine coerenti". Le incoerenze possono (e lo faranno) apparire, ma alla fine saranno sempre trattate e riconciliate.

Con Paxos, le scritture possono essere rese atomiche attraverso i nodi e le incoerenze tra i nodi sono quindi possibili da evitare. L'algoritmo Paxos consente di garantire che i nodi non difettosi non siano mai in disaccordo sul risultato di una scrittura, in qualsiasi momento. O la scrittura è riuscita ovunque o da nessuna parte. Non ci saranno mai letture incoerenti in qualsiasi momento (se è correttamente implementato e se tutte le ipotesi valgono, ovviamente). Questo ha un costo, tuttavia. Principalmente, il sistema potrebbe dover ritardare alcune richieste e non essere disponibile quando, per esempio, troppi nodi (o la comunicazione tra loro) non funzionano. Ciò è necessario per garantire che non vengano fornite risposte incoerenti.

In sintesi: la differenza principale è che i sistemi di Dynamo-come possono restituire risultati inconsistenti durante la scrittura o dopo i guasti per qualche tempo (ma alla fine recuperare da esso), mentre i sistemi basati su Paxos può garantire che non ci sono mai tali incoerenze a volte non essendo disponibili e ritardando invece le richieste.

Answer 4

Non c'è differenza. La definizione di un quorum dice che l'intersezione di due quorum non è vuota. Il quorum a maggioranza semplice è un esempio NON una definizione. Dai uno sguardo al successivo articolo del Dott. Lamport "Vertical Paxos", dove ha dato qualche altra possibile configurazione dei quorum.

Protocollo paxos multi-decreto (Multi-Paxos AKA), nello stato stazionario è solo un commit a due fasi. Le modifiche al numero del ballot sono necessarie solo quando il leader fallisce.

Il protocollo di replica di Zookeeper (ZAB) e RAFT sono tutti basati su Paxos. Le differenze sono nel rilevamento dei guasti e nella transizione dopo un errore del leader.