Validation et consensus distribués

Les protocoles de validation et de consensus distribués permettent à plusieurs nœuds de base de données de s'accorder de manière atomique sur le résultat d'une transaction et sur un ordre d'opérations cohérent, même en cas de défaillance des nœuds et des réseaux.

Definition

La validation atomique (atomic commitment) est le problème qui consiste à garantir que tous les nœuds participants à une transaction distribuée s'accordent pour la valider ou l'annuler ; le consensus est le problème plus général qui consiste à faire en sorte que des nœuds distribués s'accordent sur une valeur unique ou un journal ordonné malgré les défaillances, utilisé pour maintenir la cohérence des répliques de bases de données.

Scope

Ce sujet aborde la validation atomique (atomic commitment) des transactions inter-sites — le protocole de validation en deux phases (two-phase commit), sa faiblesse de blocage, et la validation en trois phases (three-phase commit) non bloquante — ainsi que les protocoles de consensus (Paxos, Raft) utilisés pour maintenir la cohérence des machines à états répliquées et des journaux de validation (commit logs). Il traite de ces mécanismes dans leur rôle de base de données, garantissant l'atomicité et l'accord des répliques. Il renvoie la théorie générale des systèmes distribués concernant le consensus, les modèles de défaillance et les résultats d'impossibilité aux sujets de l'informatique distribuée, les citant plutôt que de les dupliquer.

Core questions

• Comment la validation en deux phases (two-phase commit) réalise-t-elle la validation atomique (atomic commitment) entre les nœuds ?
• Pourquoi la validation en deux phases peut-elle se bloquer, et comment la validation en trois phases y remédie-t-elle ?
• Comment les protocoles de consensus tels que Paxos et Raft maintiennent-ils l'accord entre les répliques ?
• Comment le consensus se rapporte-t-il à la validation atomique dans les bases de données répliquées ?
• Comment les défaillances et les partitions réseau affectent-elles les garanties offertes par ces protocoles ?

Key concepts

• validation atomique (atomic commitment)
• validation en deux phases (2PC)
• coordinateur et participants
• blocage et le problème de défaillance du coordinateur
• validation en trois phases (3PC)
• Paxos
• Raft
• journal répliqué (replicated log) / réplication de machine à états (state machine replication)

Key theories

Validation en deux phases (Two-phase commit)

Un coordinateur demande à tous les participants de se préparer (voter) et ensuite, seulement si tous votent oui, leur indique de valider ; le protocole garantit l'atomicité mais se bloque si le coordinateur échoue alors que les participants sont incertains.

Validation non bloquante (Non-blocking commitment)

La validation en trois phases (three-phase commit) ajoute une phase de pré-validation afin que les participants puissent parvenir à une décision cohérente même si le coordinateur échoue, éliminant ainsi le comportement de blocage de la validation en deux phases sous certaines hypothèses de défaillance.

Consensus pour l'état répliqué

Paxos et Raft, plus compréhensible, permettent à un ensemble de répliques de s'accorder sur un journal ordonné d'opérations malgré les pannes, fournissant l'accord tolérant aux pannes que les bases de données modernes utilisent pour répliquer les décisions de validation et la configuration.

Clinical relevance

La validation et le consensus distribués sont ce qui rend les bases de données multi-nœuds fiables : ils garantissent qu'une transaction affectant plusieurs fragments (shards) est soit validée partout, soit nulle part, et que les systèmes répliqués ne divergent pas après des défaillances, ce qui est essentiel pour la correction des systèmes de données financiers et distribués mondialement.

History

La validation en deux phases (two-phase commit) fut la norme précoce pour l'atomicité distribuée ; Skeen et Stonebraker ont analysé son comportement de blocage en 1983 et ont motivé le développement de la validation en trois phases (three-phase commit). Paxos de Lamport (publié en 1998) a fourni un consensus tolérant aux pannes, et Raft (Ongaro et Ousterhout, 2014) a proposé une alternative plus compréhensible ; tous deux sous-tendent désormais la réplication dans les bases de données distribuées largement utilisées.

Debates

Validation atomique (atomic commitment) versus consensus pour les transactions répliquées

La validation en deux phases garantit l'atomicité mais se bloque en cas de défaillance du coordinateur, tandis que la réplication basée sur le consensus tolère les défaillances à un coût plus élevé ; les concepteurs de systèmes débattent de la manière de combiner validation et consensus pour obtenir à la fois l'atomicité et la disponibilité sur des données répliquées et partitionnées.

Key figures

• Leslie Lamport
• Dale Skeen
• Diego Ongaro
• John Ousterhout

Seminal works

• lamport1998
• skeen1983
• ongaro2014

Frequently asked questions

Pourquoi la validation en deux phases se bloque-t-elle, et est-ce un problème ?

Si le coordinateur échoue après que les participants ont voté pour valider mais avant qu'ils n'apprennent la décision, ces participants restent bloqués, détenant des verrous et ne peuvent pas valider ou annuler en toute sécurité par eux-mêmes. Ce blocage immobilise les ressources jusqu'à ce que le coordinateur se rétablisse, c'est pourquoi la validation en trois phases et les approches basées sur le consensus ont été développées pour le réduire ou l'éliminer.

En quoi le consensus diffère-t-il de la validation atomique ?

La validation atomique (atomic commitment) exige un accord unanime pour valider — tout vote négatif ou toute défaillance peut forcer une annulation. Le consensus ne requiert qu'une majorité pour s'accorder sur une valeur et peut progresser malgré une minorité de nœuds défaillants. Les bases de données utilisent la validation atomique pour les transactions inter-fragments (cross-shard) et le consensus pour maintenir la cohérence des répliques de chaque fragment.