Le jour où deux mairies enregistrent la même naissance

Une mairie tient un registre d'état civil. Une fiche par habitant, classée par numéro, retrouvée en trente secondes par un agent qui connaît le rangement.

La ville grandit. Un guichet unique ne suit plus, alors on ouvre des annexes d'arrondissement et on répartit les fiches entre elles. Chacune tient sa part du registre, et le service redevient supportable.

Puis vient le mardi matin où deux annexes enregistrent une modification sur la même fiche, chacune de son côté, sans se voir. La ville possède désormais deux vérités sur le même habitant, et personne n'a de règle écrite pour dire laquelle compte.

Un magasin clé-valeur distribué vit exactement cette histoire. On y range une valeur derrière une clé, on la relit par cette clé, et tout le reste du système consiste à répondre proprement quand la ville s'est mise à parler avec deux voix.

C'est la deuxième étude de cas de la série, et celle qui rassemble le palier 3 entier. Un magasin clé-valeur distribué n'invente rien : c'est du hachage cohérent, de la réplication, un quorum et une résolution de conflits, mis bout à bout.

Mécanisme La question à laquelle il répond
Partitionnement Sur quelle machine vit cette clé ?
Réplication Combien de copies, et rangées où ?
Quorum Combien de copies doivent répondre pour qu'on valide ?
Versionnage Laquelle des deux versions est la bonne ?
Rumeur et transmission différée Qui est vivant, et que fait-on des écritures d'un absent ?
Cinq mécanismes, dans cet ordre. Chacun résout le problème créé par le précédent, et le dernier existe uniquement parce que les quatre premiers ont accepté de vivre sans chef.

Les exigences

L'interface tient en deux opérations. C'est tout le contrat, et sa pauvreté est délibérée.

get(cle)          -> valeur
put(cle, valeur)  -> accusé

Pas de requête par intervalle, pas de jointure, pas de transaction sur plusieurs clés. On abandonne tout ce qui obligerait deux machines à se mettre d'accord pour répondre à une seule question. Le débat relationnel contre non-relationnel a été traité dans SQL ou NoSQL et on ne le rouvre pas ici : le choix est posé, on construit.

Trois objectifs de conception guident tout le reste.

Mise à l'échelle horizontale. On ajoute des machines pour absorber la croissance, sans interruption, et sans qu'une machine soit plus importante que les autres.

Décentralisation. Aucun nœud maître, aucun registre central de l'appartenance. Tout nœud sait faire ce que fait n'importe quel autre. Un maître, c'est un point de défaillance unique déguisé en simplification.

Cohérence à terme. L'écriture est acceptée immédiatement, la propagation vers les autres copies se fait ensuite. Une lecture peut donc renvoyer une valeur d'il y a quelques secondes.

Reste à dimensionner. Les hypothèses sont assumées, comme toujours : un milliard de clés, deux kilo-octets par valeur, trois copies de chaque donnée, un téraoctet de disque utile par machine.

1 000 000 000  clés
x 2 Ko         par valeur                =  2 000 Go  de données utiles
x 3            copies (N = 3)            =  6 000 Go  stockés
/ 1 000 Go     de disque utile / machine =        6   machines au minimum
x 2            marge de croissance       =       12   machines

Douze machines. Le chiffre n'a rien d'impressionnant, et c'est justement l'intérêt de le poser : il fixe l'échelle de tout ce qui suit, à commencer par le nombre de points à placer sur l'anneau.

Deux opérations, c'est le prix d'entrée de la mise à l'échelle. Chaque opération qu'on ajoute au contrat oblige deux machines à se coordonner, et la coordination est exactement ce qu'on cherche à supprimer.

Le partitionnement

Une ville qui ouvre des annexes doit décider quelle fiche va où. La règle doit tenir sur une ligne, sinon chaque agent l'appliquera à sa façon.

La première idée est une table de correspondance : une liste qui dit, pour chaque clé, sur quelle machine elle vit. Elle ne tient pas. Un milliard d'entrées à maintenir, à répliquer, à mettre à jour à chaque déplacement de clé, et un service central pour l'héberger. On a réintroduit le maître qu'on voulait éviter.

La deuxième idée est le modulo : hash(cle) % 12. Elle fonctionne parfaitement jusqu'au jour où on passe à treize machines. Là, presque toutes les clés changent de nœud, puisque le reste de la division change pour tout le monde sauf pour environ une clé sur treize. Douze clés sur treize déménagent, soit près de 92 % des données à recopier pendant que le service tourne.

Le hachage cohérent règle ce point. Serveurs et clés sont projetés sur un même anneau, et la règle devient : une clé appartient au premier nœud rencontré en tournant dans le sens horaire. Ajouter ou retirer un nœud ne déplace en moyenne qu'une fraction 1/n des clés, soit un peu plus de 8 % avec douze machines, contre 92 % avec le modulo.

Les nœuds virtuels corrigent son défaut de jeunesse. Douze points sur un anneau tombent rarement à intervalles réguliers, donc certains nœuds héritent d'un arc trois fois plus large que leur voisin. En attribuant 128 positions à chaque machine, on obtient 1 536 points, une répartition beaucoup plus plate, et surtout un départ de machine dont la charge se redistribue sur toutes les autres au lieu de tomber sur un seul voisin. Le mécanisme complet, calculs compris, est détaillé dans Sharding et hachage cohérent.

Le hachage cohérent ne rend pas le déplacement de données gratuit. Il le rend proportionnel au changement, ce qui est la seule propriété qui compte quand on ajoute une machine un mardi de production.

La réplication

Aucune mairie sérieuse ne garde un exemplaire unique de son registre dans une seule cave. On recopie, et on range les copies dans des bâtiments différents, de préférence pas dans la même rue.

Le magasin applique la même règle. Chaque clé est répliquée sur N nœuds. Une fois la position de la clé calculée sur l'anneau, on prend simplement les N nœuds suivants dans le sens horaire : c'est la liste de préférence de cette clé.

Deux précautions rendent la liste utile. D'abord, on saute les positions virtuelles qui retombent sur une machine physique déjà retenue, sinon trois copies peuvent finir sur le même serveur. Ensuite, on construit la liste de façon à couvrir plusieurs centres de données, pour que la perte d'un site n'emporte pas les trois copies.

flowchart LR K["Clé habitant-4711
position sur l'anneau"] subgraph L["Liste de préférence, N = 3"] P1["Nœud A
centre de données 1"] P2["Nœud D
centre de données 2"] P3["Nœud G
centre de données 3"] end K --> P1 P1 --> P2 P2 --> P3 P3 -.-> S["Nœud H
remplaçant temporaire si A ne répond pas"] classDef cle fill:#b5651d,stroke:#8a4d16,color:#f5f2ec; classDef rep fill:#ede9e1,stroke:#8a4d16,color:#1f2428; classDef sec fill:#d89253,stroke:#8a4d16,color:#1f2428; class K cle; class P1,P2,P3 rep; class S sec;

La liste est en général plus longue que N, précisément pour contenir des remplaçants. Quand un nœud de tête ne répond pas, on descend d'un cran : c'est ce qui permet à l'écriture d'aboutir malgré la panne, et c'est le point de départ de la transmission différée décrite plus bas.

La liste de préférence est calculée, jamais stockée. N'importe quel nœud la recalcule à partir de la clé et de sa vue de l'anneau, ce qui évite d'avoir un annuaire à tenir à jour.

Le quorum

Combien d'annexes doivent avoir confirmé l'enregistrement avant que l'acte soit considéré comme valable ? Une seule, et l'acte part vite mais peut disparaître. Toutes, et il suffit qu'un bâtiment soit fermé pour bloquer la ville.

Trois lettres suffisent à régler le curseur. N est le nombre de copies. W est le nombre d'accusés d'écriture attendus avant de répondre au client. R est le nombre de réponses de lecture attendues avant de lui rendre une valeur.

La relation utile est R + W > N. Elle garantit que l'ensemble des nœuds lus et l'ensemble des nœuds écrits se recouvrent d'au moins un nœud, donc qu'une lecture voit forcément la dernière écriture confirmée.

N = 3    copies par clé
W = 2    accusés d'écriture attendus
R = 2    réponses de lecture attendues
R + W = 2 + 2 = 4,  et 4 > 3
intersection minimale = R + W - N = 2 + 2 - 3 = 1 nœud commun

Un seul nœud commun suffit : c'est lui qui porte la version la plus récente, et le versionnage se charge de la reconnaître parmi les réponses.

N, W, R Ce que ça garantit Pannes tolérées Le prix
3, 1, 1 rien, R + W = 2 ne dépasse pas N 2 nœuds en lecture comme en écriture lectures périmées fréquentes
3, 1, 3 intersection garantie, 1 + 3 = 4 2 en écriture, 0 en lecture la lecture tombe dès qu'un nœud tombe
3, 3, 1 intersection garantie, 3 + 1 = 4 0 en écriture, 2 en lecture l'écriture tombe dès qu'un nœud tombe
3, 2, 2 intersection garantie, au moins 1 nœud commun 1 nœud, des deux côtés latence du deuxième nœud le plus rapide
3, 3, 3 toutes les copies à jour en permanence 0 disponibilité minimale

La latence se lit dans le tableau sans calcul supplémentaire : le coordinateur attend le W-ième accusé, donc le temps de réponse est celui du W-ième nœud le plus rapide. Passer W de 2 à 3 revient à s'aligner sur la machine la plus lente des trois, celle qui est en train de compacter ses fichiers.

R et W règlent d'abord le comportement en panne, la performance ne vient qu'ensuite. Les fixer, c'est écrire à l'avance ce que l'application affichera le jour où une machine ne répond plus.

Les opérations

Un habitant se présente au guichet le plus proche. L'agent qui le reçoit ne détient pas forcément la fiche : il devient le coordinateur de la demande, interroge les annexes concernées, et rend le résultat.

Tout nœud peut jouer ce rôle pour n'importe quelle clé, puisque tous savent recalculer la liste de préférence. Reste à choisir comment le client atteint son coordinateur.

Stratégie Ce qu'elle apporte Ce qu'elle coûte
Répartiteur de charge générique client trivial, aucune connaissance de l'anneau un saut réseau supplémentaire quand le nœud tiré au sort n'est pas dans la liste de préférence
Bibliothèque cliente consciente du partitionnement requête envoyée directement à un nœud qui détient la clé le client doit tenir à jour sa vue de l'appartenance

L'écriture puis la lecture, vues depuis le coordinateur, avec N = 3 et W = R = 2.

sequenceDiagram participant CL as Client participant CO as Coordinateur participant A as Réplique A participant D as Réplique D participant G as Réplique G CL->>CO: put habitant-4711 CO->>A: écrire la nouvelle version CO->>D: écrire la nouvelle version CO->>G: écrire la nouvelle version A-->>CO: accusé 1 D-->>CO: accusé 2 CO-->>CL: écriture confirmée dès le deuxième accusé G-->>CO: accusé 3, en retard CL->>CO: get habitant-4711 CO->>A: lire CO->>D: lire A-->>CO: version v1 D-->>CO: version v2 concurrente CO-->>CL: deux versions remontées au client

Le troisième accusé arrive après la réponse au client. Il n'est pas ignoré pour autant : il termine la propagation en arrière-plan, et c'est précisément ce décalage qui définit la cohérence à terme.

Le dernier échange est le cas intéressant. Le coordinateur a reçu deux valeurs qui ne descendent pas l'une de l'autre. Il ne tranche pas tout seul.

Le coordinateur est un rôle, tenu le temps d'une requête, par le nœud qui a reçu l'appel. Le rôle disparaît avec la requête, donc il n'y a jamais de bascule à organiser.

Le versionnage

Deux annexes ont modifié la même fiche le même matin. Aucune n'a tort, aucune n'a raison : elles n'ont simplement pas eu connaissance l'une de l'autre. Un horodatage ne suffit pas à départager, parce que les horloges des deux bâtiments ne sont pas à la même minute.

L'horloge vectorielle règle ce problème sans horloge. À chaque version, on attache une liste de couples serveur et compteur. Le serveur qui coordonne l'écriture incrémente son propre compteur, et laisse les autres tels quels.

D1  [Sx:1]                écriture initiale, coordonnée par Sx
D2  [Sx:2]                mise à jour, toujours par Sx
D3  [Sx:2, Sy:1]          mise à jour coordonnée par Sy
D4  [Sx:2, Sz:1]          mise à jour concurrente coordonnée par Sz
D5  [Sx:3, Sy:1, Sz:1]    version réconciliée, réécrite après fusion

La comparaison est mécanique. Si tous les compteurs de la version A sont inférieurs ou égaux à ceux de la version B, alors A est un ancêtre de B : on jette A sans état d'âme. Sinon, aucune des deux ne descend de l'autre, les écritures sont concurrentes, et le magasin conserve les deux.

Sur l'exemple, D3 et D4 sont concurrentes : D3 connaît Sy:1 que D4 ignore, D4 connaît Sz:1 que D3 ignore. Le magasin les renvoie toutes les deux à la lecture suivante, et la fusion produit D5.

Résolution Qui décide Le risque assumé
Renvoyée au client l'application, avec sa logique métier l'application doit savoir fusionner, et le code de fusion se teste mal
Dernière écriture gagne le magasin, sur horodatage une écriture est silencieusement perdue quand les horloges dérivent

Le premier choix est le plus honnête et le plus coûteux. Le second est acceptable quand la donnée est jetable, une préférence d'affichage par exemple, et catastrophique sur un solde.

Une horloge vectorielle ne résout aucun conflit. Elle fait bien mieux : elle prouve qu'il y en a un, là où un horodatage aurait écrasé une écriture sans rien dire à personne.

Le protocole de rumeur

Aucune préfecture ne tient la liste des annexes ouvertes. Chaque annexe raconte à une autre, prise au hasard, ce qu'elle sait de l'état du réseau, et l'information finit par circuler partout.

C'est le protocole de rumeur. Chaque nœud contacte périodiquement un pair au hasard et échange avec lui sa vue de l'appartenance : qui est présent, avec quelles positions sur l'anneau, depuis quand. La propagation d'un changement à n nœuds demande de l'ordre de log(n) tours, ce qui reste très rapide même sur des centaines de machines.

La détection de panne suit le même principe, en local. Un nœud qui ne répond plus à son voisin est marqué indisponible par ce voisin, sans vote, sans consensus global. La panne est une opinion locale qui se propage, pas une décision centrale.

Un détail sauve le mécanisme : quelques nœuds d'amorçage, connus de tous par configuration, évitent que l'anneau se scinde en deux groupes qui s'ignorent parce qu'aucun n'a jamais entendu parler de l'autre.

Reste à traiter les écritures adressées à un nœud absent. La transmission différée (hinted handoff) les accepte quand même : le coordinateur descend la liste de préférence, confie la donnée au nœud suivant avec une indication du destinataire réel, et ce remplaçant la range à part. Dès que le nœud légitime revient, il reçoit son colis et le remplaçant efface sa copie.

Ce mécanisme rend le quorum souple : les W accusés ne viennent pas forcément des N nœuds prévus. La disponibilité en écriture y gagne beaucoup, la garantie d'intersection y perd, et il faut le savoir avant de promettre une cohérence forte à qui que ce soit.

Pour les pannes longues, celles où le remplaçant tombe à son tour, on compare les répliques en arrière-plan avec des arbres de Merkle : chaque nœud calcule un arbre de hachages sur sa plage de clés, deux nœuds comparent leurs racines, et ne descendent dans l'arbre que là où les hachages diffèrent. Seules les clés réellement divergentes transitent sur le réseau.

Un système sans maître ne supprime pas le besoin de savoir qui est vivant. Il remplace la certitude centrale par une rumeur cohérente à terme, ce qui est exactement le compromis déjà accepté sur les données.

Ce qu'on a arbitré

Le conseil municipal a tranché, point par point. Chaque ligne est une décision assumée, avec sa contrepartie visible par l'utilisateur.

Ce qu'on voulait Ce qu'on a choisi Ce que l'utilisateur constate
Écrire même pendant une coupure réseau la disponibilité plutôt que la cohérence pendant la partition aucune écriture refusée, mais une lecture peut renvoyer une valeur d'il y a quelques secondes
Aucun point de défaillance unique anneau symétrique, appartenance par rumeur rien à attendre quand une machine tombe, pas de bascule
Ajouter des machines sans coupure hachage cohérent avec nœuds virtuels une fraction des clés se déplace, le reste ne bouge pas
Ne rien perdre pendant une panne courte quorum souple et transmission différée l'écriture est acceptée, elle rejoint sa réplique plus tard
Détecter les écritures concurrentes horloges vectorielles, résolution côté client deux versions peuvent remonter jusqu'à l'application
Régler le curseur au cas par cas N, W et R configurables par usage même magasin, garanties différentes selon la donnée

La première ligne est la plus lourde. C'est un choix AP au sens du théorème CAP, détaillé dans Le théorème CAP, ACID et BASE : face à la partition, on préserve la disponibilité et on accepte de servir une donnée périmée.

Le tableau ci-dessus vaut plus que le schéma d'architecture. Un schéma montre ce qu'on a construit ; ce tableau montre ce qu'on a accepté de perdre, et c'est cette page-là qu'on relit à trois heures du matin.

Scénario B : le papier Dynamo

Rien de ce qui précède n'est une reconstitution. L'ensemble vient d'un texte public et daté : Dynamo: Amazon's Highly Available Key-value Store, présenté par une équipe d'Amazon au symposium SOSP en octobre 2007.

Le papier décrit un magasin conçu pour des services internes qui manipulent des objets relativement petits, en dessous du mégaoctet, accessibles par clé primaire uniquement. Il énumère les techniques retenues et le problème que chacune résout : hachage cohérent pour le partitionnement, horloges vectorielles avec réconciliation à la lecture pour la disponibilité en écriture, quorum souple et transmission différée pour les pannes temporaires, arbres de Merkle pour les pannes durables, protocole de rumeur pour l'appartenance et la détection de pannes. Les sections de ce billet suivent ce découpage, dans le même ordre : c'est le plan du papier.

Deux points méritent d'être cités tels quels. La configuration (N, R, W) la plus courante, employée par plusieurs instances de Dynamo, y est donnée comme (3, 2, 2), exactement le réglage déroulé plus haut. Et les objectifs de service y sont exprimés en centile élevé plutôt qu'en moyenne : le papier prend pour exemple une exigence de 300 millisecondes au 99,9e centile pour une charge de pointe de 500 requêtes par seconde.

Le cas d'usage qui a rendu ce texte célèbre est le panier d'achat. La règle métier posée par Amazon est qu'un ajout au panier ne doit jamais être rejeté, même pendant une panne. Les versions divergentes sont donc conservées et fusionnées à la lecture, ce qui préserve tous les ajouts. Le papier assume la conséquence noir sur blanc : un article supprimé peut réapparaître dans le panier. Un client qui retrouve un article qu'il avait retiré est agacé ; un client qui ne peut pas ajouter d'article ne commande pas.

Le papier mentionne aussi une politique alternative de réconciliation, la dernière écriture gagne sur horodatage, utilisée par des services dont la donnée le tolère, comme la gestion des sessions. Et il rapporte, sur une période de vingt-quatre heures en production, que plus de 99,9 % des requêtes ne voyaient qu'une seule version : les conflits existent, ils sont rares, et le coût de les détecter reste faible.

Le vocabulaire du billet est aujourd'hui celui de toute une famille de magasins. La documentation Apache Cassandra parle des mêmes objets, sous les mêmes noms ou presque : facteur de réplication, niveaux de cohérence réglables, rumeur, transmission différée.

Un système distribué qui a bientôt vingt ans et dont on peut encore lire le raisonnement complet est une chance rare. Le papier Dynamo ne décrit pas seulement des mécanismes, il décrit les arbitrages commerciaux qui les ont imposés.

Points clés

  • Un magasin clé-valeur distribué est un assemblage, pas une invention : hachage cohérent, liste de préférence, quorum, versionnage et rumeur, chacun traité ailleurs dans la série.
  • R + W > N garantit qu'au moins un nœud est commun entre lecture et écriture, et R + W - N donne la taille minimale de cette intersection. Avec (3, 2, 2), c'est un nœud.
  • La liste de préférence se calcule, elle ne se stocke pas, et elle couvre des machines et des centres de données distincts.
  • L'horloge vectorielle ne tranche pas les conflits, elle les rend visibles. Le choix suivant, résolution métier ou dernière écriture gagne, appartient à l'application.
  • Le quorum souple et la transmission différée achètent de la disponibilité en écriture au prix de la garantie d'intersection. Le savoir avant de promettre une cohérence forte évite une conversation pénible.

Dans la série

Palier 3 : Tenir les registres. Domaine : Études de cas.

Pour aller plus loin