Aller au contenu

Conception d'un key-value store : partitionnement, réplication et quorums

Concevez pas à pas un key-value store de style Dynamo : anneau de hachage, réplication, quorums R + W > N, résolution de conflits, hinted handoff, gossip et moteur LSM.

· Fondateur et développeur

Publié le

Six serveurs, A à F, sont sur un anneau ; la clé k est hachée juste avant A. Un service de panier envoie put(k, ctx, v) à A, qui réplique vers B (ack) et C (en panne). Une écriture avec indice, en pointillés, va à D, qui la rend à C. Panneaux : N = 3, W = 2, R = 2, écriture LSM.

Votre service de panier écrit à chaque clic, et en décembre il ne peut pas refuser un seul ajout au panier. Pendant le pic, un disque va tomber, un switch de rack va osciller, peut-être qu'un datacenter va disparaître du réseau. Une base primaire unique transforme chacun de ces incidents en panne.

L'article Dynamo d'Amazon, publié en 2007, décrivait un store qui continue d'accepter des écritures malgré tout cela ; Cassandra et Riak KV ont repris la plupart de ses idées de clustering. Cet article conçoit un store de style Dynamo, de l'API au moteur de stockage, compare des systèmes réels et dessine le résultat.

Exigences et API

L'interface de Dynamo comporte deux opérations :

get(key)                 -> [value, ...], context
put(key, context, value) -> ok

get peut renvoyer des versions en conflit ainsi qu'un contexte opaque ; le put suivant le renvoie pour indiquer quelles versions il remplace. Les exigences :

  • Toujours inscriptible, même avec des nœuds ou des liens en panne.
  • Latence de queue prévisible. Le SLA d'exemple de l'article est de 300 ms pour 99,9 % des requêtes à un pic de 500 requêtes par seconde.
  • Petites valeurs, clés uniques : objets généralement sous 1 Mo, aucune opération multi-clés.
  • Montée en charge incrémentale, un nœud à la fois.

Dimensionnement, avec des valeurs de 1 Ko et des disques à moitié pleins pour garder de la marge à la compaction : 1 milliard de clés font 1 To, 3 To avec trois copies, donc six nœuds de 1 To, comme l'anneau du diagramme. À 30 000 écritures par seconde, trois copies font 90 000 écritures de réplica, soit 15 000 par nœud.

CAP et PACELC en bref

CAP dit que pendant une partition réseau, un store doit refuser certaines requêtes ou risquer des lectures périmées ; Dynamo reste disponible. Le PACELC de Daniel Abadi (2012) ajoute que, sans partition, on échange encore de la latence contre de la cohérence ; il classe les configurations par défaut de Dynamo, Cassandra et Riak comme PA/EL.

Partitionnement avec un anneau de hachage et des nœuds virtuels

Dynamo hache chaque clé avec MD5 vers une position de 128 bits sur un anneau, et la clé appartient au premier nœud dans le sens horaire. Quand un nœud arrive ou part, seules les plages voisines bougent, au lieu de presque toutes les clés comme avec hash(key) % N ; le diagramme de consistent hashing montre comment.

Une seule position par nœud répartit mal les données, donc chaque nœud en prend beaucoup, appelées nœuds virtuels ou tokens. Cassandra 5.0 est livré avec 16 tokens par nœud ; l'anneau de Riak compte 64 partitions par défaut. Vous renoncez aux scans de plages : des clés voisines atterrissent sur des nœuds différents, comme l'explique le diagramme de sharding de base de données.

Réplication et listes de préférence

Chaque clé vit sur N nœuds : le coordinateur (le premier nœud dans le sens horaire) et les N − 1 nœuds physiques distincts suivants. La liste de préférence de la clé se poursuit au-delà, de sorte que des remplaçants existent quand un réplica est en panne. Répartissez les réplicas sur des domaines de panne : Dynamo répartissait chaque liste sur plusieurs datacenters, et la NetworkTopologyStrategy de Cassandra les répartit sur des racks. Chaque réplica accepte les écritures, contrairement aux montages à leader du diagramme de réplication de base de données.

Quorums : R + W > N

Le coordinateur envoie chaque écriture aux N réplicas et répond après W accusés de réception ; une lecture répond après R réponses. Si R + W > N, tout ensemble de lecture et tout ensemble d'écriture acquittée partagent au moins un nœud.

N, R, W R + W > N Ce que vous obtenez Ce que vous payez
3, 2, 2 Oui Les lectures voient la dernière écriture acquittée ; un réplica peut tomber Chaque requête attend la deuxième réponse la plus rapide
3, 1, 3 Oui Lectures rapides depuis n'importe quel réplica Les écritures attendent les trois
3, 1, 1 Non Latence minimale, disponibilité maximale Les lectures peuvent être périmées
5, 3, 3 Oui Deux réplicas peuvent tomber Cinq copies de chaque valeur

La configuration courante de l'article Dynamo était (3, 2, 2), et les services à forte lecture comme le catalogue de produits utilisaient R = 1, W = N. Cassandra définit un niveau de cohérence par requête, de ONE à ALL ; QUORUM en lecture et en écriture donne R + W > N.

Le chevauchement n'est pas la linéarisabilité. Une écriture qui atteint un réplica puis échoue peut apparaître dans une lecture et disparaître à la suivante ; le read repair bloquant par défaut de Cassandra l'empêche pour les lectures à quorum. Le compare-and-set demande du consensus, comme dans les lightweight transactions de Cassandra ou dans un store basé sur Raft.

Conflits : last write wins, vector clocks ou CRDTs

Des écritures concurrentes via des réplicas différents laissent deux versions. Trois issues :

Stratégie Comment elle résout Peut-elle perdre des mises à jour ? Utilisée par
Last write wins Le plus grand timestamp l'emporte Oui, silencieusement ; le décalage d'horloge désigne le gagnant Cassandra, DynamoDB global tables, Riak si configuré
Vector clocks Garde les versions concurrentes ; le client fusionne Non, mais chaque client doit fusionner Dynamo, Riak (dotted version vectors)
CRDTs Types de données dont les fusions convergent toujours Non, pour les types pris en charge Compteurs, sets et maps de Riak

Une vector clock est une liste de paires (nœud, compteur). Une version dont tous les compteurs sont inférieurs ou égaux à ceux d'une autre est un ancêtre et peut disparaître ; sinon les deux sont conservées. Le service de panier fusionnait les paniers en conflit, donc les articles ajoutés n'étaient jamais perdus, même si des articles supprimés pouvaient revenir. Les conflits étaient rares : sur 24 heures, 99,94 % des requêtes de panier ont vu exactement une version. Les CRDT déplacent la fusion dans le type de données lui-même ; les éditeurs collaboratifs fondés sur les CRDT appliquent la même idée au texte partagé.

Gestion des pannes : hinted handoff, repair et gossip

Sloppy quorum et hinted handoff. Dynamo utilise les N premiers nœuds sains de la liste de préférence : si C est en panne, D prend la copie de C avec un indice et la rend quand C revient. Les écritures continuent de fonctionner, mais une lecture depuis B et le C rétabli peut alors manquer une écriture que seuls A et D ont acquittée. Cassandra garde des quorums stricts : les hints ne comptent pour le niveau de cohérence qu'avec ANY et s'arrêtent après qu'un nœud est resté en panne 3 heures (max_hint_window).

Read repair et anti-entropy. Quand les réponses divergent, le coordinateur réécrit la version la plus récente sur les réplicas périmés. Pour les données froides, les réplicas comparent des arbres de Merkle par plage de clés et ne synchronisent que les plages qui diffèrent. La documentation de Cassandra recommande d'exécuter nodetool repair sur chaque nœud au moins tous les 7 jours : les tombstones sont purgés après gc_grace_seconds (10 jours par défaut), et un réplica non réparé peut ramener des données supprimées.

Gossip et détection de pannes. Chaque seconde, chaque nœud échange l'état d'appartenance et de tokens avec un pair aléatoire ; des nœuds seed connus de tous empêchent l'anneau de se scinder. Le détecteur phi accrual de Cassandra marque un pair comme en panne quand le soupçon dépasse phi_convict_threshold (8 par défaut).

Le chemin d'écriture : commit log, memtable, SSTables

Le moteur de stockage de Cassandra est un arbre log-structured merge (LSM) optimisé pour l'écriture :

  1. Ajouter l'écriture au commit log. Par défaut (periodic), Cassandra acquitte immédiatement et synchronise toutes les 10 secondes, donc un crash peut perdre cette fenêtre.
  2. L'insérer dans la memtable, une structure triée en mémoire.
  3. Vider une memtable pleine dans une SSTable immuable et triée sur disque.
  4. Compacter les SSTables en arrière-plan, en gardant les versions les plus récentes et en supprimant les tombstones expirés.

Les lectures consultent la memtable, puis les SSTables, et un filtre de Bloom par SSTable évite les fichiers qui ne peuvent pas contenir la clé : avec 10 bits par clé et 7 fonctions de hachage, le taux de faux positifs est (1 − e^(−0,7))^7, soit environ 0,8 %. La size-tiered compaction est la valeur par défaut ; Cassandra 5.0 recommande sa stratégie unified pour les nouvelles charges.

Systèmes réels et article d'origine

Dynamo (2007) Amazon DynamoDB Cassandra 5.0 Riak KV
Partitionnement Anneau MD5, partitions égales Plages qui se scindent selon la taille ou le trafic Anneau Murmur3, 16 tokens par nœud Anneau 160 bits, 64 partitions
Réplication Sans leader, N par clé 3 réplicas sur plusieurs AZ, leader Multi-Paxos Sans leader, par datacenter Sans leader, n_val 3
Cohérence Sloppy quorum Éventuelle par défaut ; lectures fortes depuis le leader Niveau de cohérence par requête Sloppy quorum, pr et pw
Conflits Vector clocks Le leader ordonne les écritures ; last writer wins entre Régions Last write wins Siblings ou CRDTs
Stockage Berkeley DB, MySQL B-tree plus write-ahead log LSM tree Bitcask, LevelDB

DynamoDB partage le nom, pas la conception : selon son article USENIX de 2022, le leader de partition acquitte une écriture dès que deux réplicas sur trois l'ont journalisée. Les global tables utilisent par défaut last writer wins entre Régions ; au moment de la rédaction (novembre 2026), elles offrent aussi une cohérence forte multi-Région dans exactement trois Régions.

Le diagramme du key-value store de style Dynamo

Six serveurs, A à F, sont sur un anneau ; la clé k est hachée juste avant A. Un service de panier envoie put(k, ctx, v) à A, qui réplique vers B (ack) et C (en panne). Une écriture avec indice, en pointillés, va à D, qui la rend à C. Panneaux : N = 3, W = 2, R = 2, écriture LSM.

21 composants · 8 connexions

Ouvrir dans Archboard
Contenu du diagramme
  • Node B
  • Node A
  • Node C
  • Node F
  • Node D
  • Node E
  • Cart service
  • Inside every node: LSM write path
  • Commit log
  • Memtable
  • SSTables
  • put(k, ctx, v)
  • replica 2: ack
  • replica 3: no reply
  • hinted write for C: ack
  • hand off when C recovers
  • then insert
  • flush when full
  • gossip
La clé k est hachée vers un point d'un anneau de six nœuds. Node A coordonne le put et réplique vers B et C. C est en panne, donc D garde une copie avec indice et la restitue plus tard. Les panneaux latéraux listent N, R, W et le chemin d'écriture de chaque nœud.

Comment le lire :

  • L'anneau. En parcourant le sens horaire depuis hash(k), le point, on obtient la liste de préférence A à F.
  • L'écriture. Le service de panier envoie put(k, ctx, v) au coordinateur A, qui réplique vers B et C.
  • La panne. C est en panne, donc D prend la copie de C avec un indice (pointillés ambre) et la rend plus tard. Avec W = 2, le put revient dès que A et B l'ont.
  • Le gossip (pointillé) circule entre des paires de nœuds aléatoires.
  • Les panneaux listent N, R, W et le chemin d'écriture de chaque nœud.

Dessiner clairement des diagrammes de key-value store

  • Suivez une seule clé. Marquez son hash, écrivez sa liste de préférence et placez N, R et W à côté ; un anneau sans clé n'explique rien.
  • Dessinez la panne. Un nœud rouge et une arête de repli en pointillés expliquent un sloppy quorum plus vite que du texte.
  • Montrez les domaines de panne : colorez les réplicas par rack ou zone pour que les relecteurs puissent vérifier que deux copies ne partagent jamais le même.
  • Réservez les détails internes d'un nœud à un seul encart. Le cluster passe d'abord.

Une erreur fréquente : des flèches du client vers chaque réplica et aucun coordinateur, ce qui cache qui décide qu'une écriture a réussi. La méthode pas à pas de conception de système traite de la mise en page et des chiffres.

Le construire dans Archboard

  1. Connectez-vous avec Google ou GitHub et créez un diagramme.
  2. Ajoutez une grande Ellipse grise depuis le pack Base pour l'anneau de tokens.
  3. Placez six nœuds Serveur du pack Réseau sur l'anneau, de Node A à Node F dans le sens horaire. Colorez A et B en vert, C en rouge et D en ambre, et étiquetez leurs rôles avec des notes Texte de Base.
  4. Ajoutez une petite Ellipse sur l'anneau juste avant Node A pour hash(k), avec une étiquette Texte.
  5. Ajoutez un Conteneur du pack Modèle C4 pour le service de panier, avec une arête put(k, ctx, v) vers Node A.
  6. Tracez les arêtes : A vers B en trait plein vert, A vers C en pointillés rouges avec une pointe de flèche en croix, A vers D et D vers C en pointillés ambre (écriture avec indice, puis handoff), et une arête gossip pointillée entre F et E avec une note Texte.
  7. Ajoutez un bloc Markdown du pack Base avec N, R, W et le scénario.
  8. Ajoutez un Cadre du pack Base avec trois nœuds Composant du pack Modèle C4, Commit log, Memtable et SSTables, reliés de haut en bas, et une note Texte sur les filtres de Bloom.

L'exemple utilise 14 nœuds de diagramme et reste dans les limites de l'offre Free.

FAQ

Comment concevoir un key-value store distribué ? Partitionnez avec du consistent hashing, répliquez chaque clé sur N nœuds, réglez R et W, choisissez une stratégie de conflits, ajoutez le hinted handoff et la réparation anti-entropy, et exécutez un LSM tree par nœud.

Que signifie R + W > N ? Sur N réplicas, une écriture en attend W et une lecture en attend R. Si R + W dépasse N, chaque lecture atteint au moins un réplica qui détient la dernière écriture acquittée.

DynamoDB est-il basé sur l'article Dynamo ? Seulement en partie : chaque partition a trois réplicas avec un leader Multi-Paxos et un stockage B-tree, pas des sloppy quorums ni des vector clocks.

Qu'est-ce que le hinted handoff ? Un autre nœud stocke l'écriture d'un réplica injoignable avec un indice et la livre quand le réplica revient. Cassandra cesse par défaut de stocker des hints pour un nœud après 3 heures de panne.

Dois-je utiliser last write wins ou les vector clocks ? Last write wins convient aux données pour lesquelles perdre une mise à jour concurrente est acceptable, comme les sessions. Utilisez des vector clocks ou des CRDTs quand chaque mise à jour compte, comme pour les paniers et les compteurs.

Commencez gratuitement — un siège, sans carte bancaire.

Articles associés

← Retour au blog

Ouvrez un canevas en une minute

Connectez-vous avec Google ou GitHub. Gratuit pour un siège. Passez à un forfait supérieur quand l’équipe vous rejoint.