Réplication par machine à états

La réplication par machine à états rend un service tolérant aux pannes en exécutant des répliques déterministes qui exécutent les mêmes commandes dans le même ordre, de sorte que les survivants masquent la défaillance des autres.

Definition

La réplication par machine à états est une technique dans laquelle un service est modélisé comme une machine à états déterministe et répliqué sur plusieurs serveurs qui appliquent tous la même séquence ordonnée de commandes client, garantissant que les répliques non défaillantes restent dans des états identiques et peuvent se substituer aux répliques défaillantes.

Scope

Ce sujet couvre le modèle de machine à états d'un service, l'exigence que les répliques soient déterministes, l'utilisation de la diffusion atomique (à ordre total) ou du consensus pour s'accorder sur la séquence de commandes, et le contraste avec la réplication primaire-secondaire (passive). Il aborde également la gestion du non-déterminisme, la reconfiguration des répliques et l'extension aux répliques byzantines.

Core questions

• Pourquoi les répliques doivent-elles être déterministes et traiter les commandes dans un ordre identique ?
• Comment l'ordre de commande convenu est-il produit à partir du consensus ou de la diffusion atomique ?
• En quoi la réplication active (par machine à états) diffère-t-elle de la réplication primaire-secondaire passive ?

Key theories

L'approche par machine à états

Tout service déterministe peut être rendu tolérant aux pannes en le répliquant et en alimentant chaque réplique avec le même flux de commandes ordonné ; à condition qu'un nombre de répliques inférieur au nombre toléré ne tombe en panne, le service reste correct et disponible.

Ordonnancement par consensus

L'ordre total requis sur les commandes est précisément une diffusion atomique, ce qui est équivalent au consensus, de sorte que les machines à états répliquées sont généralement construites sur un protocole de consensus tel que Paxos ou Raft.

Réplication par machine à états byzantine

L'extension de l'approche pour tolérer des pannes arbitraires nécessite un accord entre plus des deux tiers des répliques et un vote des résultats par les clients, comme cela est réalisé dans la réplication pratique tolérante aux pannes byzantines.

Clinical relevance

La réplication par machine à états est la méthode standard pour construire un service hautement disponible et fortement cohérent ; les journaux répliqués, les services de coordination et de nombreuses bases de données distribuées sont des machines à états pilotées par un flux de commandes ordonné par consensus.

History

L'article de Lamport sur les horloges logiques a esquissé l'idée de la machine à états répliquée en 1978 ; le tutoriel de Schneider de 1990 en a fait le cadre canonique pour les services tolérants aux pannes ; et le PBFT de Castro et Liskov de 1999 l'a étendu au contexte byzantin, une approche qui a ensuite influencé les conceptions de la blockchain.

Debates

Réplication active versus passive

La réplication active (par machine à états) exécute les commandes sur toutes les répliques pour une bascule rapide mais gaspille du travail et exige le déterminisme ; la réplication primaire-secondaire passive n'exécute les commandes que sur un primaire et transfère l'état, économisant du travail mais entraînant un délai de bascule et un point d'exécution unique.

Key figures

• Fred Schneider
• Leslie Lamport
• Miguel Castro
• Barbara Liskov

Seminal works

• schneider1990
• lamport1998
• castro1999

Frequently asked questions

Pourquoi le service répliqué doit-il être déterministe ?

Si les répliques pouvaient faire des choix différents sur la même entrée — en raison du hasard, du timing ou de l'ordonnancement des threads — leurs états divergeraient malgré la réception de commandes identiques. Le déterminisme garantit que le même flux de commandes ordonné produit le même état partout.