A senior engineer’s perspective on building highly available distributed systems Table de contenu Introduction : Pourquoi Dynamo a tout changé Le théorème du trade-off Core Architecture Components Consistent Hashing for Partitioning Replication Strategy (N, R, W) Vector Clocks for Versioning Sloppy Quorum and Hinted Handoff Résolution des conflits : le problème du panier d’achat Lire et écrire le flux Les arbres de Merkle pour anti-entropie Détection d’adhésion et d’échec Caractéristiques : Nombres réels Évolution de la stratégie de partitionnement Comparer Dynamo aux systèmes modernes Ce que Dynamo ne vous donne pas Exemple de mise en œuvre pratique Les leçons clés pour la conception de systèmes Quand ne pas utiliser les systèmes Dynamo-Style Conclusion Appendice : Problèmes de conception et approches Il s'agit d'une référence de longue forme - chaque section se distingue d'elle-même, alors n'hésitez pas à sauter directement sur ce qui vous intéresse le plus. This is a long-form reference — every section stands on its own, so feel free to jump directly to whatever is most relevant to you. Introduction : Pourquoi Dynamo a tout changé Quand Amazon a publié le journal Dynamo en 2007, ce n’était pas seulement un autre exercice académique.C’était une solution testée par la bataille aux problèmes réels à grande échelle.Je me souviens de la première fois que j’ai lu ce document – il a fondamentalement changé la façon dont je pensais aux systèmes distribués. Il a été conçu pour soutenir les services à haut trafic d’Amazon tels que le panier et les systèmes de gestion de session. Il n’y a pas d’indices secondaires, pas de joints, pas de sémantique relationnelle – juste des clés et des valeurs, avec un accent extrême sur la disponibilité et l’évolutivité. Il ne fournit pas de garanties de linéarisation ou de commande globale, même dans les plus hauts paramètres de quorum. Dynamo is a distributed key-value storage system. Le problème de base rencontré par Amazon était simple à affirmer mais brutal à résoudre : Lorsque quelqu'un essaie d'ajouter un élément à son panier lors d'une fracture réseau ou d'une défaillance du serveur, le refus de l'écrire n'est pas acceptable. How do you build a storage system that never says “no” to customers? Le théorème du trade-off du CAP : pourquoi Dynamo choisit la disponibilité Avant de vous plonger dans la façon dont Dynamo fonctionne, vous devez comprendre la contrainte fondamentale autour de laquelle il est conçu. Qu’est-ce que le CAP Theorem ? Le théorème CAP décrit un compromis fondamental dans les systèmes distribués : quand une partition réseau se produit, vous devez choisir entre la cohérence et la disponibilité. Consistance (C): Tous les nœuds voient les mêmes données en même temps Disponibilité (A): Chaque demande reçoit une réponse (succès ou échec) Tolérance de partition (P): le système continue de fonctionner malgré les pannes réseau Une abréviation commune est "pick 2 of 3", mais c'est une simplification excessive. Dans la pratique, les partitions réseau sont inévitables à l'échelle, donc la véritable décision est: C’est le vrai choix de design. when partitions occur (and they will), do you sacrifice consistency or availability? Les câbles sont coupés, les commutateurs échouent, les centres de données perdent la connectivité. Vous ne pouvez pas les éviter, vous devez donc choisir: Consistance ou Disponibilité? The harsh reality Les bases de données traditionnelles choisissent la cohérence : Traditional approach Database: "I can't guarantee all replicas are consistent, so I'll reject your write to be safe." Result: Customer sees error, cart is empty Impact: Lost revenue, poor experience Dynamo choisit la disponibilité : Dynamo’s approach Dynamo: "I'll accept your write with the replicas I can reach. The unreachable replica will catch up later." Result: Customer sees success, item in cart Impact: Sale continues, happy customer Le commerce visualisé When a partition occurs: Traditional Database: Choose C over A → Sacrifice Availability - ✓ All replicas always have same data - ✓ No conflicts to resolve - ❌ Rejects writes during failures - ❌ Poor customer experience - ❌ Lost revenue Dynamo: Choose A over C → Sacrifice Strong Consistency - ✓ Accepts writes even during failures - ✓ Excellent customer experience - ✓ No lost revenue - ❌ Replicas might temporarily disagree - ❌ Application must handle conflicts Exemple réel d’Amazon : panier de shopping du Black Friday Imaginez que c’est le Black Friday. Des millions de clients font du shopping. Un câble réseau est coupé entre les centres de données. : With traditional database Time: 10:00 AM - Network partition occurs Result: - All shopping cart writes fail - "Service Unavailable" errors - Customers can't checkout - Twitter explodes with complaints - Estimated lost revenue: $100,000+ per minute : With Dynamo Time: 10:00 AM - Network partition occurs Result: - Shopping cart writes continue - Customers see success - Some carts might have conflicts (rare) - Application merges conflicting versions - Estimated lost revenue: $0 - A few edge cases need conflict resolution (acceptable) Pourquoi ce choix a du sens pour le commerce électronique Amazon a fait les mathématiques : Coût du rejet d'une écriture: Vente perdue immédiate ($ 50-200) Coût de l'acceptation d'une écriture contradictoire: Il est parfois nécessaire de fusionner des paniers d'achat (c'est rare, facile à fixer) Décision d'affaires: Accepter les écrits, gérer les conflits rares : Types of data where Availability > Consistency Cartes d’achat (additions contradictoires de fusion) Données de session (last-write-wins est bien) Préférences de l’utilisateur (consistance éventuelle acceptable) Liste des meilleurs vendeurs (approximatif est bon) : Types of data where Consistency > Availability Balances de compte bancaire (ne peut pas avoir des soldes en conflit) Comptes d'inventaire (ne peut pas être survendu) Logs de transactions (doit être commandé) C’est pourquoi Dynamo n’est pas pour tout – mais pour les cas d’utilisation du commerce électronique d’Amazon, choisir la disponibilité par rapport à une forte cohérence était le bon compromis. Nuance importante: Bien que Dynamo soit souvent décrit comme un système AP, il est plus précis de l'appeler un système de cohérence ajustable.En fonction de votre configuration de quorum R et W, il peut se comporter plus près de CP. L'étiquette AP s'applique à sa configuration par défaut / recommandée optimisée pour les charges de travail du commerce électronique. : Alors que Dynamo est souvent décrit comme un système AP, il est plus précis de l'appeler un En fonction de votre configuration de quorum R et W, il peut se comporter plus près de CP. L'étiquette AP s'applique à sa configuration par défaut/recommandée optimisée pour les charges de travail de commerce électronique. Important nuance tunable consistency system Core Architecture Components Hashing cohérent pour le partitionnement Permettez-moi d’expliquer cela avec un exemple concret, car le hashing cohérent est l’un de ces concepts qui semble magique jusqu’à ce que vous le voyiez en action. Le problème : le sharding traditionnel basé sur le hash Imaginez que vous avez 3 serveurs et que vous voulez distribuer des données à travers eux. # Traditional approach - DON'T DO THIS def get_server(key, num_servers): hash_value = hash(key) return hash_value % num_servers # Modulo operation # With 3 servers: get_server("user_123", 3) # Returns server 0 get_server("user_456", 3) # Returns server 1 get_server("user_789", 3) # Returns server 2 Cela fonctionne... jusqu’à ce que vous ajoutiez ou supprimiez un serveur. # Before (3 servers): "user_123" → hash % 3 = 0 → Server 0 "user_456" → hash % 3 = 1 → Server 1 "user_789" → hash % 3 = 2 → Server 2 # After (4 servers): "user_123" → hash % 4 = 0 → Server 0 ✓ (stayed) "user_456" → hash % 4 = 1 → Server 1 ✓ (stayed) "user_789" → hash % 4 = 2 → Server 2 ✓ (stayed) # But wait - this is lucky! In reality, most keys MOVE: "product_ABC" → hash % 3 = 2 → Server 2 "product_ABC" → hash % 4 = 3 → Server 3 ✗ (MOVED!) Lorsque vous changez le nombre de serveurs, presque TOUS vos données doivent être redistribuées. Imaginez déplacer des téraoctets de données pour ajouter un seul serveur! The disaster La solution : le hashing cohérent Le hachage cohérent résout cela en traitant l’espace hachage comme un cercle (0 à 2^32 – 1, enveloppant autour). Step 1: Place servers on the ring Chaque serveur est affecté à une position aléatoire sur l’anneau (appelé un « jeton »). Step 2: Place data on the ring Lorsque vous souhaitez stocker des données, vous: Hash the key to get a position on the ring Marchez à l'horloge de cette position Stockez les données sur le premier serveur que vous rencontrez Étiquette : anneau complet Voici l'anneau placé dans l'ordre. Les clés vont en direction de l'horloge au serveur suivant: Une clé marche en direction de l'horloge jusqu'à ce qu'elle atteigne un serveur. Simple rule : Examples user_123 à 30° → marche à 45° → le serveur A le possède user_456 à 150° → marche à 200° → le serveur C le possède cart_789 à 250° → marche à 280° → Server D le possède produit_ABC à 300° → passe au-delà de 360°, enveloppe à 0°, continue à 45° → Server A le possède Who owns what range? Serveur A (45°): possède tout de 281° à 45° (enveloppe autour) Serveur B (120°): possède tout de 46° à 120° Server C (200°): possède tout de 121° à 200° Serveur D (280°): possède tout de 201° à 280° La magie : ajouter un serveur Maintenant, voyons pourquoi c'est brillant.Nous ajoutons Server E à la position 160°: BEFORE: Server A (45°) → owns 281°-45° Server B (120°) → owns 46°-120° Server C (200°) → owns 121°-200° ← THIS RANGE WILL SPLIT Server D (280°) → owns 201°-280° AFTER: Server A (45°) → owns 281°-45° ← NO CHANGE Server B (120°) → owns 46°-120° ← NO CHANGE Server E (160°) → owns 121°-160° ← NEW! Takes part of C's range Server C (200°) → owns 161°-200° ← SMALLER range Server D (280°) → owns 201°-280° ← NO CHANGE : Seules les clés dans la plage de 121°-160° doivent être déplacées (de C à E). Result Optimisation des nœuds virtuels Il y a un problème critique avec l'approche de base du hashing cohérent: . random distribution can be extremely uneven The Problem in Detail: Lorsque vous attribuez au hasard une position par serveur, vous lancez essentiellement des darts sur un tableau circulaire.Parfois, les darts se regroupent, parfois ils se dispersent. Je vais vous montrer un exemple concret : Scenario: 4 servers with single random tokens Server A: 10° } Server B: 25° } ← Only 75° apart! Tiny ranges Server C: 100° } Server D: 280° ← 180° away from C! Huge range Range sizes: - Server A owns: 281° to 10° = 89° (25% of ring) - Server B owns: 11° to 25° = 14° (4% of ring) ← Underutilized! - Server C owns: 26° to 100° = 74° (21% of ring) - Server D owns: 101° to 280° = 179° (50% of ring) ← Overloaded! Real-world consequences: Charge inégale : Server D traite 50% de toutes les données tandis que Server B ne traite que 4%. La CPU, le disque et le réseau du serveur D sont maximisés Le serveur B est principalement vide (capacité gaspillée) Votre latence de 99,9e percentile est dominée par la surcharge de Server D Hotspot Cascading : Lorsque le serveur D devient lent ou échoue : Tous ses déplacements de charge de 50% vers Server A (le prochain en direction de l'horloge) Le serveur A est maintenant surchargé La performance du système se dégrade catastrophiquement Échauffement inefficace : l’ajout de serveurs n’aide pas de manière uniforme car de nouveaux serveurs pourraient atterrir dans des zones déjà petites Visualizing the problem: Chaque serveur physique reçoit plusieurs positions virtuelles (tokens). Dynamo’s solution Au lieu de lancer un dart par serveur, lancez plusieurs darts. Plus vous lancez, plus la distribution devient (loi des grands nombres). How Virtual Nodes Fix the Problem: Let’s take the same 4 servers, but now each server gets 3 virtual nodes (tokens) instead of 1: Physical Server A gets 3 tokens: 10°, 95°, 270° Physical Server B gets 3 tokens: 25°, 180°, 310° Physical Server C gets 3 tokens: 55°, 150°, 320° Physical Server D gets 3 tokens: 75°, 200°, 340° Now the ring looks like: 10° A, 25° B, 55° C, 75° D, 95° A, 150° C, 180° B, 200° D, 270° A, 310° B, 320° C, 340° D Range sizes (approximately): - Server A total: 15° + 55° + 40° = 110° (31% of ring) - Server B total: 30° + 20° + 30° = 80° (22% of ring) - Server C total: 20° + 30° + 20° = 70° (19% of ring) - Server D total: 20° + 70° + 20° = 110° (31% of ring) Load ranges from 19% to 31% instead of 4% to 50%. Much better! Why this works: : With more samples (tokens), the random distribution averages out. This is the law of large numbers in action. Statistics : When a server fails, its load is distributed across many servers, not just one neighbor: Granular load distribution Server A fails: - Its token at 10° → load shifts to Server B's token at 25° - Its token at 95° → load shifts to Server C's token at 150° - Its token at 270° → load shifts to Server B's token at 310° Result: The load is spread across multiple servers! : When adding a new server with 3 tokens, it steals small amounts from many servers instead of a huge chunk from one server. Smooth scaling Real Dynamo configurations: The paper mentions different strategies evolved over time. In production: Early versions: 100-200 virtual nodes per physical server Plus tard optimisé pour : Q/S tokens par nœud (où Q = partitions totales, S = nombre de serveurs) Configuration typique : Chaque serveur physique peut avoir 128-256 nœuds virtuels The Trade-off: Balance vs Overhead More virtual nodes means better load distribution, but there’s a cost. What you gain with more virtual nodes: With 1 token per server (4 servers): Load variance: 4% to 50% (±46% difference) ❌ With 3 tokens per server (12 virtual nodes): Load variance: 19% to 31% (±12% difference) ✓ With 128 tokens per server (512 virtual nodes): Load variance: 24% to 26% (±2% difference) ✓✓ What it costs: Taille des métadonnées : chaque nœud conserve les informations de routage 1 token per server: Track 4 entries 128 jetons par serveur: Suivre 512 entrées Gossip overhead: Nodes échangent périodiquement des informations d'adhésion Plus de jetons = plus de données à synchroniser entre les nœuds Toutes les secondes, les nœuds racontent leur vision de l'anneau Complexité de rééquilibrage : lorsque les nœuds se joignent / quittent More virtual nodes = more partition transfers to coordinate Mais chaque transfert est plus petit (ce qui est en fait bon pour le bootstrapping) Dynamo’s evolution: The paper describes how Amazon optimized this over time: Strategy 1 (Initial): - 100-200 random tokens per server - Problem: Huge metadata (multiple MB per node) - Problem: Slow bootstrapping (had to scan for specific key ranges) Strategy 3 (Current): - Q/S tokens per server (Q=total partitions, S=number of servers) - Equal-sized partitions - Example: 1024 partitions / 8 servers = 128 tokens per server - Benefit: Metadata reduced to KB - Benefit: Fast bootstrapping (transfer whole partition files) Real production sweet spot: La plupart des déploiements Dynamo utilisent 128-256 nœuds virtuels par serveur physique. Distribution de la charge dans une variance de 10 à 15% (bien assez) Metadata overhead under 100KB per node (negligible) Récupération rapide de défaillance (la charge se propage à travers de nombreux nœuds) Diminishing returns. Going from 128 to 512 tokens only improves load balance by 2-3%, but doubles metadata size and gossip traffic. Why not more? Les serveurs physiques (en haut) cartographient plusieurs positions virtuelles (en bas) sur l'anneau. Key concept : Benefits Encore plus de distribution Lorsqu'un serveur échoue, sa charge est distribuée sur de nombreux serveurs (pas seulement un voisin) Lorsqu'un serveur se joint, il vole une petite quantité de plusieurs serveurs Real-World Impact Comparison Voyons la différence avec les nombres réels : Traditional Hashing (3 servers → 4 servers): - Keys that need to move: ~75% (3 out of 4) - Example: 1 million keys → 750,000 keys must migrate Consistent Hashing (3 servers → 4 servers): - Keys that need to move: ~25% (1 out of 4) - Example: 1 million keys → 250,000 keys must migrate With Virtual Nodes (150 vnodes total → 200 vnodes): - Keys that need to move: ~12.5% (spread evenly) - Example: 1 million keys → 125,000 keys must migrate - Load is balanced across all servers The “Aha!” Moment The key insight is this: Consistent hashing decouples the hash space from the number of servers. Traditionnel: server = hash(key) % num_servers ← num_servers est dans la formule! Consistant: server = ring.findNextClockwise(hash(key)) ← num_servers n'est pas dans la formule! This is why adding/removing servers only affects a small portion of the data. The hash values don’t change—only which server “owns” which range changes, and only locally. Pensez-y comme à une piste circulaire avec des stations d’eau (serviteurs). Si vous ajoutez une nouvelle station d’eau, les coureurs ne changent de stations que s’ils sont entre l’ancienne station la plus proche et la nouvelle. 2. Replication Strategy (N, R, W) Le problème : la disponibilité versus la cohérence Imagine you’re building Amazon’s shopping cart. A customer adds an item to their cart, but at that exact moment: One server is being rebooted for maintenance Un autre serveur a un hiccup réseau Un troisième serveur est parfait (La cohérence est très forte) Traditional database approach Client: "Add this item to my cart" Database: "I need ALL replicas to confirm before I say yes" Server 1: ✗ (rebooting) Server 2: ✗ (network issue) Server 3: ✓ (healthy) Result: "Sorry, service unavailable. Try again later." : 😡 “I can’t add items to my cart during Black Friday?!” Customer experience Ceci est inacceptable pour le commerce électronique. Chaque écriture rejetée est une perte de revenus. Dynamo’s Solution: Tunable Quorums Dynamo vous donne trois boutons pour ajuster le compromis exact que vous voulez: N : nombre de répliques (combien de copies des données) R : Quorum de lecture (combien de répliques doivent répondre pour une lecture réussie) W : Écrire le quorum (combien de répliques doivent être reconnues pour une écriture réussie) • Quand , vous garantissez la superposition du quorum - ce qui signifie qu'au moins un nœud qui a reçu l'écriture sera interrogé pendant toute lecture. Cette superposition permet la détection de la dernière version, à condition que la logique de réconciliation identifie correctement l'horloge vectorielle la plus élevée. The magic formula R + W > N Laissez-moi vous montrer pourquoi cela compte avec des scénarios réels: Scénario 1 : panier d’achat (prioriser la disponibilité) N = 3 # Three replicas for durability R = 1 # Read from any single healthy node W = 1 # Write to any single healthy node # Trade-off analysis: # ✓ Writes succeed even if 2 out of 3 nodes are down # ✓ Reads succeed even if 2 out of 3 nodes are down # ✓ Maximum availability - never reject customer actions # ✗ Might read stale data # ✗ Higher chance of conflicts (but we can merge shopping carts) What happens during failure: Client: "Add item to cart" Coordinator tries N=3 nodes: - Node 1: ✗ Down - Node 2: ✓ ACK (W=1 satisfied!) - Node 3: Still waiting... Result: SUCCESS returned to client immediately Node 3 eventually gets the update (eventual consistency) Scénario 2 : État de session (approche équilibrée) N = 3 R = 2 # Must read from 2 nodes W = 2 # Must write to 2 nodes # Trade-off analysis: # ✓ R + W = 4 > N = 3 → Read-your-writes guaranteed # ✓ Tolerates 1 node failure # ✓ Good balance of consistency and availability # ✗ Write fails if 2 nodes are down # ✗ Read fails if 2 nodes are down Why R + W > N enables read-your-writes: Write to W=2 nodes: [A, B] Later, read from R=2 nodes: [B, C] Because W + R = 4 > N = 3, there's guaranteed overlap! At least one node (B in this case) will have the latest data. The coordinator detects the newest version by comparing vector clocks. This guarantees seeing the latest write as long as reconciliation picks the causally most-recent version correctly. Scenario 3: Financial Data (Prioritize Consistency) N = 3 R = 3 # Must read from ALL nodes W = 3 # Must write to ALL nodes # Trade-off analysis: # ✓ Full replica quorum — reduces likelihood of divergent versions # ✓ Any read will overlap every write quorum # ✗ Write fails if ANY node is down # ✗ Read fails if ANY node is down # ✗ Poor availability during failures Les systèmes nécessitant des garanties transactionnelles strictes choisissent généralement des systèmes CP. Cette configuration est techniquement prise en charge par Dynamo mais sacrifie les propriétés de disponibilité qui motivent son utilisation en premier lieu. Table de comparaison de configuration Config N R W Availability Consistency Use Case High Availability 3 1 1 ⭐⭐⭐⭐⭐ ⭐⭐ Shopping cart, wish list Balanced 3 2 2 ⭐⭐⭐⭐ ⭐⭐⭐⭐ Session state, user preferences Full Quorum 3 3 3 ⭐⭐ ⭐⭐⭐⭐⭐ High-stakes reads (not linearizable) Read-Heavy 3 1 3 ⭐⭐⭐ (reads) ⭐⭐⭐⭐ Product catalog, CDN metadata Write-Heavy 3 3 1 ⭐⭐⭐ (writes) ⭐⭐⭐ Click tracking, metrics High Availability 3 1 1 ⭐⭐⭐⭐⭐ ⭐⭐ Carton d'achat, liste de souhaits Balanced 3 2 2 ⭐⭐⭐⭐ ⭐⭐⭐⭐ État de session, préférences de l'utilisateur Full Quorum 3 3 3 ⭐⭐ ⭐⭐⭐⭐⭐ Lectures de hautes mises (non linéaires) Read-Heavy 3 1 3 ⭐⭐⭐⭐ Product catalog, CDN metadata Write-Heavy 3 3 1 ⭐⭐⭐ (écriture) ⭐⭐⭐ Click tracking, metrics Remarque sur les systèmes financiers: Les systèmes nécessitant de fortes garanties transactionnelles (par exemple, les soldes de comptes bancaires) ne devraient généralement pas utiliser Dynamo. Remarque sur les systèmes financiers: Les systèmes nécessitant de fortes garanties transactionnelles (par exemple, les soldes de comptes bancaires) ne devraient généralement pas utiliser Dynamo. The Key Insight La plupart des systèmes utilisés because: N=3, R=2, W=2 Durabilité : peut tolérer jusqu'à 2 défaillances de réplique avant la perte permanente de données (en supposant des défaillances indépendantes et aucune interruption corrélée). : Tolerates 1 node failure for both reads and writes Availability Conséquence : R + W > N garantit que les quorum de lecture et d'écriture se superposent, permettant un comportement de lecture-écriture en l'absence d'écriture concomitante. Performances: Ne pas attendre le nœud le plus lent (seulement besoin de 2 sur 3) Real production numbers from the paper: Amazon’s shopping cart service during peak (holiday season): Configuration: N=3, R=2, W=2 Handled tens of millions of requests Over 3 million checkouts in a single day Pas de temps d'arrêt, même avec des pannes de serveur Cette approche ajustable est ce qui a rendu Dynamo révolutionnaire.Vous n'êtes pas coincé avec une taille unique - vous l'ajustez en fonction de vos exigences commerciales réelles. 3. Vector Clocks for Versioning Le problème : détecter la causalité dans les systèmes distribués Lorsque plusieurs nœuds peuvent accepter des écrits indépendamment, vous devez répondre à une question critique: Are these two versions of the same data related, or were they created concurrently? Why timestamps don’t work: Scenario: Two users edit the same shopping cart simultaneously User 1 at 10:00:01.500 AM: Adds item A → Writes to Node X User 2 at 10:00:01.501 AM: Adds item B → Writes to Node Y Physical timestamp says: User 2's version is "newer" Reality: These are concurrent! Both should be kept! Problem: - Clocks on different servers are NEVER perfectly synchronized - Clock skew can be seconds or even minutes - Network delays are unpredictable - Physical time doesn't capture causality What we really need to know: Version A happened before Version B? → B can overwrite A Version A and B are concurrent? → Keep both, merge later Version A came from reading Version B? → We can track this! The Solution: Vector Clocks A vector clock is a simple data structure: a list of les paires qui suivent quels nœuds ont vu quelles versions. (node_id, counter) The rules: Lorsqu'un nœud écrit des données, il augmente son propre compteur Lorsqu'un nœud lit des données, il obtient l'horloge vectorielle When comparing two vector clocks: Si tous les compteurs dans A ≤ compteurs dans B → A est un ancêtre de B (B est plus récent) If some counters in A > B and some B > A → A and B are concurrent (conflict!) Exemple étape par étape Let’s trace a shopping cart through multiple updates: Breaking down the conflict: D3: [Sx:2, Sy:1] vs D4: [Sx:2, Sz:1] Comparing: - Sx: 2 == 2 ✓ (equal) - Sy: 1 vs missing in D4 → D3 has something D4 doesn't - Sz: missing in D3 vs 1 → D4 has something D3 doesn't Conclusion: CONCURRENT! Neither is an ancestor of the other. Both versions must be kept and merged. Caractéristiques du monde réel Ces chiffres reflètent la charge de travail spécifique d'Amazon - le ratio de lecture/écriture élevé, principalement des sessions d'un seul utilisateur - et ne doivent pas être supposés généraliser à tous les déploiements de Dynamo: 99.94% - Single version (no conflict) 0.00057% - 2 versions 0.00047% - 3 versions 0.00009% - 4 versions : Conflicts are RARE in practice! Key insight Why conflicts happen: En général, les échecs du réseau Principalement des écrivains concurrents (souvent des processus automatisés / robots) Human users rarely create conflicts because they’re slow compared to network speed Le problème de taille Vector clocks can grow unbounded if many nodes coordinate writes. Dynamo’s solution: Une fois que l'horloge dépasse un seuil. truncate the oldest entries // When vector clock exceeds threshold (e.g., 10 entries) // Remove the oldest entry based on wall-clock timestamp vectorClock = { 'Sx': {counter: 5, timestamp: 1609459200}, 'Sy': {counter: 3, timestamp: 1609459800}, 'Sz': {counter: 2, timestamp: 1609460400}, // ... 10 more entries } // If size > 10, remove entry with oldest timestamp // ⚠ Risk: Dropping an entry collapses causality information. // Two versions that were causally related may now appear // concurrent, forcing the application to resolve a conflict // that didn't actually exist. In practice, Amazon reports // this has not been a significant problem — but it is a // real theoretical risk in high-churn write environments // with many distinct coordinators. 4. Sloppy Quorum and Hinted Handoff The Problem: Strict Quorums Kill Availability Traditional quorum systems are rigid and unforgiving. Traditional strict quorum: Your data is stored on nodes: A, B, C (preference list) Write requirement: W = 2 Scenario: Node B is down for maintenance Coordinator: "I need to write to 2 nodes from {A, B, C}" Tries: A ✓, B ✗ (down), C ✓ Result: SUCCESS (got 2 out of 3) Scenario: Nodes B AND C are down Coordinator: "I need to write to 2 nodes from {A, B, C}" Tries: A ✓, B ✗ (down), C ✗ (down) Result: FAILURE (only got 1 out of 3) Customer: "Why can't I add items to my cart?!" 😡 Le problème : Si ces nœuds spécifiques sont bas, le système devient indisponible. Strict quorums require specific nodes Real scenario at Amazon: Black Friday, 2:00 PM - Datacenter 1: 20% of nodes being rebooted (rolling deployment) - Datacenter 2: Network hiccup (1-2% packet loss) - Traffic: 10x normal load With strict quorum: - 15% of write requests fail - Customer support phones explode - Revenue impact: Millions per hour Résultats pour : Sloppy Quorum Dynamo relâche l’exigence de quorum : “Write to the first N healthy nodes in the preference list, walking further down the ring if needed.” Preference list for key K: A, B, C But B is down... Sloppy Quorum says: "Don't give up! Walk further down the ring: A, B, C, D, E, F, ..." Coordinator walks until N=3 healthy nodes are found: A, C, D (D is a temporary substitute for B) Comment fonctionne Handoff When a node temporarily substitutes for a failed node, it stores a “hint” with the data. Processus Handoff détaillé Step 1: Detect failure and substitute def write_with_hinted_handoff(key, value, N, W): preference_list = get_preference_list(key) # [A, B, C] healthy_nodes = [] for node in preference_list: if is_healthy(node): healthy_nodes.append((node, is_hint=False)) # If we don't have N healthy nodes, expand the list if len(healthy_nodes) < N: extended_list = get_extended_preference_list(key) for node in extended_list: if node not in preference_list and is_healthy(node): healthy_nodes.append((node, is_hint=True)) if len(healthy_nodes) >= N: break # Write to first N healthy nodes acks = 0 for node, is_hint in healthy_nodes[:N]: if is_hint: # Store with hint metadata intended_node = find_intended_node(preference_list, node) success = node.write_hinted(key, value, hint=intended_node) else: success = node.write(key, value) if success: acks += 1 if acks >= W: return SUCCESS return FAILURE Step 2: Background hint transfer # Runs periodically on each node (e.g., every 10 seconds) def transfer_hints(): hints_db = get_hinted_replicas() for hint in hints_db: intended_node = hint.intended_for if is_healthy(intended_node): try: intended_node.write(hint.key, hint.value) hints_db.delete(hint) log(f"Successfully transferred hint to {intended_node}") except: log(f"Will retry later for {intended_node}") Why This Is Brilliant Durability maintained: Even though B is down: - We still have N=3 copies: A, C, D - Data won't be lost even if another node fails - System maintains durability guarantee Availability maximized: Client perspective: - Write succeeds immediately - No error message - No retry needed - Customer happy Traditional quorum would have failed: - Only 2 nodes available (A, C) - Need 3 for N=3 - Write rejected - Customer sees error Eventual consistency: Timeline: T=0: Write succeeds (A, C, D with hint) T=0-5min: B is down, but system works fine T=5min: B recovers T=5min+10sec: D detects B is back, transfers hint T=5min+11sec: B has the data, D deletes hint Result: Eventually, all correct replicas have the data Configuration Example // High availability configuration const config = { N: 3, // Want 3 replicas W: 2, // Only need 2 ACKs to succeed R: 2, // Read from 2 nodes // Sloppy quorum allows expanding preference list sloppy_quorum: true, // How far to expand when looking for healthy nodes max_extended_preference_list: 10, // How often to check for hint transfers hint_transfer_interval: 10_seconds, // How long to keep trying to transfer hints hint_retention: 7_days }; Real-World Impact D’après l’expérience d’Amazon : During normal operation: Handoff rarement déclenché Most writes go to preferred nodes La base de données Hints est en grande partie vide During failures: Scenario: 5% of nodes failing at any time (normal at Amazon's scale) Without hinted handoff: - Write success rate: 85% - Customer impact: 15% of cart additions fail With hinted handoff: - Write success rate: 99.9%+ - Customer impact: Nearly zero During datacenter failure: Scenario: Entire datacenter unreachable (33% of nodes) Without hinted handoff: - Many keys would lose entire preference list - Massive write failures - System effectively down With hinted handoff: - Writes redirect to other datacenters - Hints accumulate temporarily - When datacenter recovers, hints transfer - Zero customer-visible failures The Trade-off Benefits: ✓ Maximum write availability ✓ Durability maintained during failures Récupération automatique lorsque les nœuds reviennent Pas d’intervention manuelle nécessaire Costs: ✗ Temporary inconsistency (data not on “correct” nodes) ✗ Extra storage for hints database bande passante d'arrière-plan pour les transferts d'indices ✗ Slightly more complex code ✗ If a substitute node (like D) fails before it can transfer its hint back to B, the number of true replicas drops below N until the situation resolves. This is an important edge case to understand in failure planning. Hinted handoff provides temporary durability, not permanent replication. The availability benefits far outweigh the costs for e-commerce workloads. Amazon’s verdict: Résolution des conflits : le problème du panier d’achat Let’s talk about the most famous example from the paper: the shopping cart. This is where rubber meets road. Qu’est-ce qu’un conflit (et pourquoi cela se produit) ? à Cela se produit lorsque deux écrits se produisent à la même clé sur des nœuds différents, sans que l’un ou l’autre écrive « en connaissant » l’autre.Cela n’est possible que parce que Dynamo accepte les écrits même lorsque les nœuds ne peuvent pas communiquer – ce qui est le point! conflict Here’s a concrete sequence of events that creates a conflict: Timeline: T=0: Customer logs in. Cart has {shoes} on all 3 nodes. T=1: Network partition: Node1 can't talk to Node2. T=2: Customer adds {jacket} on their laptop → goes to Node1. Cart on Node1: {shoes, jacket} ← Vector clock: [N1:2] T=3: Customer adds {hat} on their phone → goes to Node2. Cart on Node2: {shoes, hat} ← Vector clock: [N2:2] T=4: Network heals. Node1 and Node2 compare notes. Node1 says: "I have version [N1:2]" Node2 says: "I have version [N2:2]" Neither clock dominates the other → CONFLICT! Neither version is “wrong”—both represent real actions the customer took. Dynamo’s job is to detect this situation (via vector clocks) and surface l'application afin que l'application puisse décider ce qu'il faut faire. both versions What Does the Application Do With a Conflict? Voici la partie cruciale que le document vous délégue : . Dynamo gives you all the concurrent versions; your code decides how to merge them. the application must resolve conflicts using business logic Pour le panier, Amazon a choisi un Le raisonnement est simple – perdre un article du panier d’un client (perdre une vente) est pire que d’afficher occasionnellement un article stable qu’ils ont déjà supprimé. union merge Conflict versions: Version A (from Node1): {shoes, jacket} Version B (from Node2): {shoes, hat} Merge strategy: union Merged cart: {shoes, jacket, hat} ← All items preserved Here’s the actual reconciliation code: from __future__ import annotations from dataclasses import dataclass, field class VectorClock: def __init__(self, clock: dict[str, int] | None = None): self.clock: dict[str, int] = clock.copy() if clock else {} def merge(self, other: "VectorClock") -> "VectorClock": """Merged clock = max of each node's counter across both versions.""" all_keys = set(self.clock) | set(other.clock) merged = {k: max(self.clock.get(k, 0), other.clock.get(k, 0)) for k in all_keys} return VectorClock(merged) def __repr__(self): return f"VectorClock({self.clock})" @dataclass class ShoppingCart: items: list[str] = field(default_factory=list) vector_clock: VectorClock = field(default_factory=VectorClock) @staticmethod def reconcile(carts: list["ShoppingCart"]) -> "ShoppingCart": if len(carts) == 1: return carts[0] # No conflict, nothing to do # Merge strategy: union of all items (never lose additions). # This is Amazon's choice for shopping carts. # A different application might choose last-write-wins or something else. all_items: set[str] = set() merged_clock = VectorClock() for cart in carts: all_items.update(cart.items) # Union: keep everything merged_clock = merged_clock.merge(cart.vector_clock) return ShoppingCart(items=sorted(all_items), vector_clock=merged_clock) # Example conflict scenario cart1 = ShoppingCart(items=["shoes", "jacket"], vector_clock=VectorClock({"N1": 2})) cart2 = ShoppingCart(items=["shoes", "hat"], vector_clock=VectorClock({"N2": 2})) # Dynamo detected a conflict and passes both versions to our reconcile() reconciled = ShoppingCart.reconcile([cart1, cart2]) print(reconciled.items) # ['hat', 'jacket', 'shoes'] — union! The Deletion Problem (Why This Gets Tricky) La stratégie de l'Union a un cas d'avantage désagréable: . deleted items can come back from the dead T=0: Cart: {shoes, hat} T=1: Customer removes hat → Cart: {shoes} Clock: [N1:3] T=2: Network partition — Node2 still has old state T=3: Some concurrent write to Node2 Clock: [N2:3] T=4: Network heals → conflict detected T=5: Union merge: {shoes} ∪ {shoes, hat} = {shoes, hat} Result: Hat is BACK! Customer removed it, but it reappeared. Amazon explicitly accepts this trade-off. A “ghost” item in a cart is a minor annoyance. Losing a cart addition during a Black Friday sale is lost revenue. Note de profondeur de l'ingénierie: La logique de fusion doit être spécifique au domaine et soigneusement conçue. L'ajout d'éléments est commutatif (l'ordre n'a pas d'importance) et facile à fusionner. La suppression d'éléments n'est pas - une suppression dans une branche concomitante peut être silencieusement ignorée lors d'une fusion basée sur un syndicat. Ceci est un compromis intentionnel dans la conception de Dynamo, mais cela signifie que l'application doit raisonner soigneusement sur la sémantique d'ajout vs. suppression. Si vos données ne prennent pas naturellement en charge les fusion (par exemple, un compteur, l'adresse d'un utilisateur), vous avez besoin d'une autre stratégie - telle que : Merge logic must be domain-specific and carefully designed. Adding items is commutative (order doesn’t matter) and easy to merge. Removing items is not—a deletion in one concurrent branch may be silently ignored during a union-based merge. This is an intentional trade-off in Dynamo’s design, but it means the application must reason carefully about add vs. remove semantics. If your data doesn’t naturally support union merges (e.g., a counter, a user’s address), you need a different strategy—such as CRDTs, last-write-wins with timestamps, or simply rejecting concurrent writes for that data type. Engineering depth note Lire et écrire le flux The diagrams above show the high-level flow, but let’s walk through what actually happens step-by-step during a read and a write. Understanding this concretely will make the earlier concepts click. Écrire le chemin Step-by-step narration of a PUT request: to any node (via a load balancer) or directly to the coordinator. Client sends the request Le coordinateur est déterminé – c’est le premier nœud de la liste de préférences pour la position de hachage de la clé sur l’anneau. L'horloge vectorielle est mise à jour - le coordinateur accroît son propre compteur dans l'horloge vectorielle, créant une nouvelle version. Le coordinateur écrit localement, puis les fans envoient l'écriture aux autres nœuds N-1 de la liste de préférences simultanément. It does NOT wait for all N — just the first W to respond. The remaining nodes that haven’t responded yet will get the write eventually (or via hinted handoff if they’re down). The coordinator waits for W acknowledgments. to the client. From the client’s perspective, the write is done. Once W ACKs arrive, the coordinator returns 200 OK : Le client obtient une réponse réussie dès que les nœuds W sont confirmés. Les autres nœuds (N – W) recevront l’écriture asynchroniquement. have the data, just not necessarily at the same moment. Key insight about the write path Will Lire le chemin Step-by-step narration of a GET request: Le client envoie la demande au coordinateur pour cette clé. Le coordinateur envoie des demandes de lecture à tous les nœuds N de la liste de préférences simultanément (pas seulement R). The coordinator returns as soon as R nodes have replied, without waiting for the slower ones. Wait for R responses. The coordinator checks all the vector clocks: Compare the versions returned. If all versions are identical → return the single version immediately. If one version’s clock dominates the others (it’s causally “newer”) → return that version. If versions are concurrent (neither clock dominates) → return to the client, which must merge them. all versions La réparation de lecture se produit en arrière-plan : si le coordinateur remarque qu’un nœud renvoie une version stable, il envoie la dernière version à ce nœud pour la mettre à jour. Because Dynamo is a general-purpose storage engine. It doesn’t know whether you’re storing a shopping cart, a user profile, or a session token. Only sait comment fusionner deux versions contradictoires d'une manière qui donne du sens aux affaires.Le coordinateur vous donne les versions concurrentes brutes ainsi que le contexte horloger vectoriel, et vous faites la bonne chose pour votre cas d'utilisation. Why does the client receive the conflict instead of the coordinator resolving it? Votre application : when the client writes the merged version back, it must include the context (the merged vector clock). This tells Dynamo that the new write has “seen” all the concurrent versions, so the conflict is resolved. Without this context, Dynamo might think it’s Il s’agit d’écrire au-dessus du conflit encore non résolu. The vector clock context is the key to closing the loop Autre Les arbres de Merkle pour anti-entropie The Problem: How Do You Know When Replicas Are Out of Sync? Après qu'un nœud se rétablisse d'une défaillance, il a peut-être manqué quelques écrits. Après qu'une partition de réseau a guéri, deux répliques peuvent diverger. Comment Dynamo détecte et corrige ces différences? The brute-force approach would be: “Every hour, compare every key on Node A against Node B, and sync anything that’s different.” But at Amazon’s scale, a single node might store hundreds of millions of keys. Comparing them all one by one would be so slow and bandwidth-intensive that it would interfere with normal traffic. L’idée fondamentale : au lieu de comparer les clés individuelles, comparer . If the hash matches, that whole group is identical—skip it. Only drill down into groups where hashes differ. Dynamo uses Merkle trees to solve this efficiently. hashes of groups of keys Important : Merkle tree sync est un mécanisme anti-entropie en arrière-plan. Il n'est pas sur le chemin de lecture/écriture chaude. Les lectures et les écritures normales utilisent des horloges vectorielles et des quorum pour la version. Important : Merkle tree sync est un mécanisme anti-entropie en arrière-plan. Il n'est pas sur le chemin de lecture/écriture chaude. Les lectures et les écritures normales utilisent des horloges vectorielles et des quorum pour la version. Comment un arbre de Merkle est construit Chaque nœud construit un arbre Merkle sur ses données, organisées par des rangs clés : contain the hash of a small range of actual data keys (e.g., hash of all values for keys k1, k2, k3). Leaf nodes Les nœuds internes contiennent le hash des hashes de leurs enfants. La racine est un hash unique représentant toutes les données sur le nœud. Comment deux nœuds synchronisent à l'aide d'arbres Merkle Lorsque Node A et Node B veulent vérifier s’ils sont synchronisés : : Compare root hashes. If they’re the same, everything is identical. Done! (No network traffic for the data itself.) Step 1 Si les racines diffèrent, comparez leurs enfants de gauche. Step 2 : Keep descending only into subtrees where hashes differ, until you reach the leaf nodes. Step 3 Synchroniser uniquement les clés spécifiques dans les différents nœuds de feuille. Step 4 Example: Comparing two nodes Node A root: abc789 ← differs from Node B! Node B root: abc788 Compare left subtrees: Node A left: xyz123 Node B left: xyz123 ← same! Skip entire left half. Compare right subtrees: Node A right: def456 Node B right: def457 ← differs! Go deeper. Compare right-left subtree: Node A right-left: ghi111 Node B right-left: ghi111 ← same! Skip. Compare right-right subtree: Node A right-right: jkl222 Node B right-right: jkl333 ← differs! These are leaves. → Sync only the keys in the right-right leaf range (e.g., k10, k11, k12) Instead of comparing all 1 million keys, we compared 6 hashes and synced only 3 keys! : Synchronization process in code def sync_replicas(node_a, node_b, key_range): """ Efficiently sync two nodes using Merkle trees. Instead of comparing all keys, we compare hashes top-down. Only the ranges where hashes differ need actual key-level sync. """ tree_a = node_a.get_merkle_tree(key_range) tree_b = node_b.get_merkle_tree(key_range) # Step 1: Compare root hashes first. # If they match, every key in this range is identical — nothing to do! if tree_a.root_hash == tree_b.root_hash: return # Zero data transferred — full match! # Step 2: Recursively find differences by traversing top-down. # Only descend into subtrees where hashes differ. differences = [] stack = [(tree_a.root, tree_b.root)] while stack: node_a_subtree, node_b_subtree = stack.pop() if node_a_subtree.hash == node_b_subtree.hash: continue # This whole subtree matches — skip it! if node_a_subtree.is_leaf: # Found a differing leaf — these keys need syncing differences.extend(node_a_subtree.keys) else: # Not a leaf yet — recurse into children for child_a, child_b in zip(node_a_subtree.children, node_b_subtree.children): stack.append((child_a, child_b)) # Step 3: Sync only the specific keys that differed at leaf level. # This might be a handful of keys, not millions. for key in differences: sync_key(node_a, node_b, key) Pourquoi c’est efficace La puissance des arbres de Merkle est que le nombre de comparaisons de hachage dont vous avez besoin évolue avec le (logarithmic in the number of keys), not the number of keys themselves. La profondeur de l'arbre Node with 1,000,000 keys: Naive approach: Compare 1,000,000 keys individually Cost: 1,000,000 comparisons Merkle tree: Compare O(log N) hashes top-down Tree depth ≈ 20 levels Cost: 20 comparisons to find differences Then sync only the differing leaves (~few keys) Speedup: ~50,000x fewer comparisons! Et critiquement, si deux nœuds sont (ce qui est presque toujours vrai dans un cluster sain), les hashes racines correspondent souvent entièrement et les données zéro doivent être transférées. mostly in sync Membership and Failure Detection Dynamo utilise un protocole de rumeur pour la gestion de l'adhésion. Chaque nœud échange périodiquement des informations d'adhésion avec des pairs aléatoires. Il n'y a pas de nœud maître - toute la coordination est entièrement décentralisée. L’adhésion basée sur le gossip Les principaux points de design : Chaque nœud maintient sa propre vue de l'adhésion au cluster. Il n'y a pas de registre central, donc il n'y a pas de point d'échec unique pour les données d'adhésion. No single coordinator Dynamo utilise un détecteur d'échec basé sur l'accumulation (similaire à Phi Accrual). Au lieu d'un jugement binaire « vivant / mort », les nœuds maintiennent un that rises the longer a peer is unresponsive. This avoids false positives from transient network hiccups. Failure suspicion vs. detection Niveaux de suspicion Node A's view of Node B: - Last heartbeat: 3 seconds ago → Suspicion low → Healthy - Last heartbeat: 15 seconds ago → Suspicion rising → Likely slow/degraded - Last heartbeat: 60 seconds ago → Suspicion high → Treat as failed : Les nouveaux nœuds contactent un nœud de graine pour se joindre, puis la rumeur répand leur présence sur le reste du cluster. L'appartenance à l'anneau est finalement cohérente - les différents nœuds peuvent avoir des vues légèrement différentes de l'anneau momentanément, ce qui est acceptable. Decentralized bootstrapping Caractéristiques : Nombres réels Le document fournit des données de performance fascinantes. Latency Distribution Metric | Average | 99.9th Percentile --------------------|---------|------------------ Read latency | ~10ms | ~200ms Write latency | ~15ms | ~200ms Key insight: 99.9th percentile is ~20x the average! Le 99.9ème percentile est affecté par : Why the huge gap? Collecte de poubelles en pause Variations de disque I/O Réseau Jitter Load imbalance C’est pourquoi les SLA d’Amazon sont spécifiés au 99,9e percentile, pas en moyenne. Version de conflit À partir des 24 heures du trafic du panier d'achat de production d'Amazon (par le papier Dynamo). Notez que ces caractéristiques reflètent les caractéristiques spécifiques de la charge de travail d'Amazon, pas une base universelle: 99.94% - Saw exactly one version (no conflict) 0.00057% - Saw 2 versions 0.00047% - Saw 3 versions 0.00009% - Saw 4 versions : Conflicts are rare in practice! Most often caused by concurrent writers (robots), not failures. Takeaway Évolution de la stratégie de partitionnement Dynamo a évolué à travers trois stratégies de partitionnement. Cette évolution nous enseigne des leçons importantes: Stratégie 1 : Tokens aléatoires (initiales) Problem: Random token assignment → uneven load Problem: Adding nodes → expensive data scans Problem: Can't easily snapshot the system : L'attribution de jetons aléatoires semble élégante mais est un cauchemar dans la pratique. Chaque nœud obtient une position aléatoire sur l'anneau, ce qui signifie des gammes de propriété de données très différentes et une répartition inégale de la charge. Operational lesson Stratégie 2: Partitions de taille égale + jetons aléatoires Improvement: Decouples partitioning from placement Problem: Still has load balancing issues Stratégie 3: Q/S Tokens par nœud – Partitions de taille égale + Placement déterministe (Current) What Q and S mean: Q = le nombre total de partitions fixes dans lesquelles l'anneau est divisé (par exemple 1024).Pensez à ces partitions comme à des tranches de taille égale, pré-cutées de l'espace de hachage qui ne changent jamais de forme. S = le nombre de serveurs physiques actuellement dans le cluster (par exemple 8). Q/S = combien de ces tranches fixes chaque serveur est responsable (par exemple 1024 / 8 = 128 partitions par serveur). Le changement clé par rapport aux stratégies précédentes: l'anneau est maintenant divisé en partitions fixes de taille égale Q Les serveurs n’obtiennent plus de positions aléatoires – ils possèdent chacun exactement des partitions Q/S, répartis uniformément autour de l’anneau. first Example: Q=12 partitions, S=3 servers Ring divided into 12 equal slices (each covers 30° of the 360° ring): Partition 1: 0°– 30° → Server A Partition 2: 30°– 60° → Server B Partition 3: 60°– 90° → Server C Partition 4: 90°–120° → Server A Partition 5: 120°–150° → Server B Partition 6: 150°–180° → Server C ...and so on, round-robin Each server owns exactly Q/S = 12/3 = 4 partitions → perfectly balanced. When a 4th server joins (S becomes 4): New Q/S = 12/4 = 3 partitions per server. Each existing server hands off 1 partition to the new server. Only 3 out of 12 partitions move — the rest are untouched. Cette évolution – des jetons aléatoires aux partitions fixes de taille égale avec une propriété équilibrée – est l’un des apprentissages opérationnels les plus instructifs de Dynamo. Comparer Dynamo aux systèmes modernes System Consistency Model Use Case Dynamo Influence Cassandra Tunable (N, R, W) Time-series, analytics Direct descendant — heavily inspired by Dynamo, uses same consistent hashing and quorum concepts Riak Tunable, vector clocks Key-value store Closest faithful Dynamo implementation Amazon DynamoDB Eventually consistent by default Managed NoSQL DynamoDB is a completely different system internally, with no vector clocks and much simpler conflict resolution. Shares the name and high-level inspiration only. ⚠️ Not the same as Dynamo! Voldemort Tunable LinkedIn's data store Open-source Dynamo implementation Google Spanner Linearizable Global SQL Opposite choice to Dynamo — prioritizes CP via TrueTime clock synchronization Redis Cluster Eventually consistent Caching, sessions Uses consistent hashing; much simpler conflict resolution Cassandra Téléchargeable (N, R, W) Horaires, Analyse Descendant direct - fortement inspiré par Dynamo, utilise les mêmes concepts de hachage et de quorum cohérents Riak Horloge, horloge vectorielle Boutique de valeur clé La mise en œuvre la plus fidèle de Dynamo Amazon DynamoDB cohérente par défaut Gestion de NoSQL DynamoDB est un système complètement différent en interne, sans horloges vectorielles et avec une résolution de conflit beaucoup plus simple. ⚠️ Not the same as Dynamo! Voldemort Tunéo La boutique de données de LinkedIn Implémentation de Dynamo Open Source Google Spanner linéaire Le Global SQL Option opposée à Dynamo – prioritise CP via la synchronisation de l'horloge TrueTime Redis Cluster Finalement cohérente Caching, sessions Utilisation d’un hashing cohérent ; résolution de conflits beaucoup plus simple La confusion DynamoDB: De nombreux ingénieurs confondent Amazon DynamoDB avec le papier Dynamo. Ils sont très différents. DynamoDB est un service géré optimisé pour la simplicité opérationnelle. Il n'expose pas les horloges vectorielles, n'utilise pas le même schéma de partitionnement et utilise un modèle de cohérence propriétaire. Le papier concerne le moteur de stockage interne Dynamo qui précède DynamoDB. : De nombreux ingénieurs confondent Amazon DynamoDB avec le papier Dynamo. Ils sont très différents. DynamoDB est un service géré optimisé pour la simplicité opérationnelle. Il n'expose pas les horloges vectorielles, n'utilise pas le même schéma de partitionnement et utilise un modèle de cohérence propriétaire. The DynamoDB confusion Ce que Dynamo ne vous donne pas Chaque blog d'ingénieur supérieur devrait être honnête au sujet des limites. Voici ce que Dynamo négocie explicitement: Aucune transaction : les opérations ne sont effectuées qu’avec une seule clé. Vous ne pouvez pas mettre à jour de manière atomique plusieurs clés. Aucun index secondaire : vous ne pouvez rechercher les données que par sa clé primaire (au moins dans la conception originale). Aucun joins: Il s'agit d'un magasin de valeur clé. Il n'y a pas de langage de requête. Pas d'ordre global : les événements entre différentes clés n'ont pas d'ordre garanti. : Even at R=W=N, Dynamo does not provide linearizable reads. There is no global clock, no strict serializability. No linearizability : The system detects conflicts and surfaces them to the application. The must resolve them. If your engineers don’t understand this, you will have subtle data bugs. No automatic conflict resolution application Coûts de réparation à l'échelle: Le processus anti-entropie (reconciliation de l'arbre de Merkle) n'est pas gratuit. Croissance de l'horloge vectorielle: Dans les environnements d'écriture à haute intensité avec de nombreux coordinateurs, les horloges vectorielles peuvent devenir suffisamment grandes pour nécessiter une truncation, ce qui introduit une perte potentielle de causalité. Comprendre ces limites est essentiel pour que les systèmes de style Dynamo fonctionnent avec succès dans la production. Exemple de mise en œuvre pratique Il est intentionnellement simplifié – pas de réseau réel, pas de persistance – mais il modèle fidèlement comment les horloges vectorielles, l’anneau de hachage cohérent, le quorum lit/écrit et la détection de conflits interagissent. Chapitre 1 : Horloge vectorielle Le class est la base du suivi des versions. c'est juste une cartographie de dictionnaire Deux opérations clés : VectorClock node_id → counter — bump our own counter when we write increment(node) — check if one clock is causally “after” another; if neither dominates, the writes were concurrent (conflict) dominates(other) from __future__ import annotations from dataclasses import dataclass, field from typing import Optional class VectorClock: """ Tracks causality across distributed writes. A clock like {"nodeA": 2, "nodeB": 1} means: - nodeA has coordinated 2 writes - nodeB has coordinated 1 write - Any version with these counters has "seen" those writes """ def __init__(self, clock: dict[str, int] | None = None): self.clock: dict[str, int] = clock.copy() if clock else {} def increment(self, node_id: str) -> "VectorClock": """Return a new clock with node_id's counter bumped by 1.""" new_clock = self.clock.copy() new_clock[node_id] = new_clock.get(node_id, 0) + 1 return VectorClock(new_clock) def dominates(self, other: "VectorClock") -> bool: """ Returns True if self is causally AFTER other. self dominates other when: - Every counter in self is >= the same counter in other, AND - At least one counter in self is strictly greater. Meaning: self has seen everything other has seen, plus more. """ all_keys = set(self.clock) | set(other.clock) at_least_one_greater = False for key in all_keys: self_val = self.clock.get(key, 0) other_val = other.clock.get(key, 0) if self_val < other_val: return False # self is missing something other has seen if self_val > other_val: at_least_one_greater = True return at_least_one_greater def merge(self, other: "VectorClock") -> "VectorClock": """ Merge two clocks by taking the max of each counter. Used after resolving a conflict to produce a new clock that has "seen" everything both conflicting versions saw. """ all_keys = set(self.clock) | set(other.clock) merged = {k: max(self.clock.get(k, 0), other.clock.get(k, 0)) for k in all_keys} return VectorClock(merged) def __repr__(self): return f"VectorClock({self.clock})" Partie 2 : Valeur de version Chaque valeur stockée dans Dynamo est enveloppée avec son horloge vectorielle. Cette paire est ce qui permet au coordinateur de comparer les versions pendant les lectures et de détecter les conflits. @dataclass class VersionedValue: """ A value paired with its causal history (vector clock). When a client reads, they get back a VersionedValue. When they write an update, they must include the context (the vector clock they read) so Dynamo knows what version they're building on top of. """ value: object vector_clock: VectorClock def __repr__(self): return f"VersionedValue(value={self.value!r}, clock={self.vector_clock})" Partie 3 : Node simulé Dans Dynamo réel, chaque nœud est un processus distinct. Ici, nous les simulons comme des objets de mémoire. Le détail clé: chaque nœud a son propre local Les nœuds peuvent être marqués comme Simuler les échecs. storage down class DynamoNode: """ Simulates a single Dynamo storage node. In production this would be a separate server with disk storage. Here it's an in-memory dict so we can demo the logic without networking. """ def __init__(self, node_id: str, token: int): self.node_id = node_id self.token = token # Position on the consistent hash ring self.storage: dict[str, list[VersionedValue]] = {} self.down = False # Toggle to simulate node failures def write(self, key: str, versioned_value: VersionedValue) -> bool: """ Store a versioned value. Returns False if the node is down. We store a LIST of versions per key, because a node might hold multiple concurrent (conflicting) versions until they are resolved by the application. """ if self.down: return False # In a real node this would be written to disk (e.g. BerkeleyDB) self.storage[key] = [versioned_value] return True def read(self, key: str) -> list[VersionedValue] | None: """ Return all versions of a key. Returns None if the node is down. A healthy node with no data for the key returns an empty list. """ if self.down: return None return self.storage.get(key, []) def __repr__(self): status = "DOWN" if self.down else f"token={self.token}" return f"DynamoNode({self.node_id}, {status})" Partie 4 : Anneau hash cohérent Nous trions les nœuds par leur token (position) et utilisons une marche horlogère pour trouver le coordinateur et la liste de préférences pour toute clé. import hashlib class ConsistentHashRing: """ Maps any key to an ordered list of N nodes (the preference list). Nodes are placed at fixed positions (tokens) on a conceptual ring from 0 to 2^32. A key hashes to a position, then walks clockwise to find its nodes. This means adding/removing one node only rebalances ~1/N of keys, rather than reshuffling everything like modulo hashing would. """ def __init__(self, nodes: list[DynamoNode]): # Sort nodes by token so we can do clockwise lookup efficiently self.nodes = sorted(nodes, key=lambda n: n.token) def _hash(self, key: str) -> int: """Consistent hash of a key into the ring's token space.""" # Use MD5 for a simple, evenly distributed hash. # Real Dynamo uses a more sophisticated hash (e.g., SHA-1). digest = hashlib.md5(key.encode()).hexdigest() return int(digest, 16) % (2**32) def get_preference_list(self, key: str, n: int) -> list[DynamoNode]: """ Return the first N nodes clockwise from key's hash position. These are the nodes responsible for storing this key. The first node in the list is the coordinator — it receives the client request and fans out to the others. """ if not self.nodes: return [] key_hash = self._hash(key) # Find the first node whose token is >= key's hash (clockwise) start_idx = 0 for i, node in enumerate(self.nodes): if node.token >= key_hash: start_idx = i break # If key_hash is greater than all tokens, wrap around to node 0 else: start_idx = 0 # Walk clockwise, collecting N unique nodes preference_list = [] for i in range(len(self.nodes)): idx = (start_idx + i) % len(self.nodes) preference_list.append(self.nodes[idx]) if len(preference_list) == n: break return preference_list Partie 5 : Le coordinateur Dynamo C’est le cœur du système – la logique qui gère les demandes des clients, les fans en répliques, attend le quorum et détecte les conflits. class SimplifiedDynamo: """ Coordinates reads and writes across a cluster of DynamoNodes. Any node can act as coordinator for any request — there's no dedicated master. The coordinator is simply whichever node receives the client request (or the first node in the preference list, if using partition-aware routing). Configuration: N = total replicas per key R = minimum nodes that must respond to a read (read quorum) W = minimum nodes that must acknowledge a write (write quorum) """ def __init__(self, nodes: list[DynamoNode], N: int = 3, R: int = 2, W: int = 2): self.N = N self.R = R self.W = W self.ring = ConsistentHashRing(nodes) # ------------------------------------------------------------------ # # WRITE # # ------------------------------------------------------------------ # def put(self, key: str, value: object, context: VectorClock | None = None) -> VectorClock: """ Write a key-value pair to N replicas, wait for W ACKs. The 'context' is the vector clock from a previous read. Always pass context when updating an existing key — it tells Dynamo which version you're building on top of, so it can detect whether your write is concurrent with anything else. Returns the new vector clock, which the caller should store and pass back on future writes to this key. Raises: RuntimeError if fewer than W nodes acknowledged. """ preference_list = self.ring.get_preference_list(key, self.N) if not preference_list: raise RuntimeError("No nodes available") # The coordinator is always the first node in the preference list. coordinator = preference_list[0] # Increment the coordinator's counter in the vector clock. # If no context was provided (brand new key), start a fresh clock. base_clock = context if context is not None else VectorClock() new_clock = base_clock.increment(coordinator.node_id) versioned = VersionedValue(value=value, vector_clock=new_clock) # Fan out to all N replicas. # In a real system these would be concurrent RPC calls. # Here we call them sequentially for simplicity. ack_count = 0 for node in preference_list: success = node.write(key, versioned) if success: ack_count += 1 # Only need W ACKs to declare success. # The remaining replicas are updated asynchronously (or via # hinted handoff if they were down). if ack_count < self.W: raise RuntimeError( f"Write quorum not met: got {ack_count} ACKs, needed {self.W}" ) print(f"[PUT] key={key!r} value={value!r} clock={new_clock} " f"({ack_count}/{self.N} nodes wrote)") return new_clock # ------------------------------------------------------------------ # # READ # # ------------------------------------------------------------------ # def get(self, key: str) -> list[VersionedValue]: """ Read a key from N replicas, wait for R responses, reconcile. Returns a LIST of VersionedValues: - Length 1 → clean read, no conflict - Length >1 → concurrent versions detected; application must merge After reading, the caller should: 1. If no conflict: use the single value normally. 2. If conflict: merge the values using application logic, then call put() with the merged value and the merged vector clock as context. This "closes" the conflict. Read repair happens in the background: any replica that returned a stale version is silently updated with the latest version. """ preference_list = self.ring.get_preference_list(key, self.N) # Collect responses from all N nodes all_versions: list[VersionedValue] = [] responding_nodes: list[tuple[DynamoNode, list[VersionedValue]]] = [] for node in preference_list: result = node.read(key) if result is not None: # None means the node is down all_versions.extend(result) responding_nodes.append((node, result)) if len(responding_nodes) < self.R: raise RuntimeError( f"Read quorum not met: got {len(responding_nodes)} responses, needed {self.R}" ) # Reconcile: discard any version that is strictly dominated # (i.e., is a causal ancestor of) another version. # What remains is the set of concurrent versions. reconciled = self._reconcile(all_versions) # Background read repair: if any node returned something older # than the reconciled result, send it the latest version. # (Simplified: only meaningful when there's a single winner.) if len(reconciled) == 1: latest = reconciled[0] for node, versions in responding_nodes: if not versions or versions[0].vector_clock != latest.vector_clock: node.write(key, latest) # Repair silently in background status = "clean" if len(reconciled) == 1 else f"CONFLICT ({len(reconciled)} versions)" print(f"[GET] key={key!r} status={status} " f"({len(responding_nodes)}/{self.N} nodes responded)") return reconciled # ------------------------------------------------------------------ # # INTERNAL: VERSION RECONCILIATION # # ------------------------------------------------------------------ # def _reconcile(self, versions: list[VersionedValue]) -> list[VersionedValue]: """ Remove any version that is a causal ancestor of another version. If version A's clock is dominated by version B's clock, then B is strictly newer — A adds no new information and can be dropped. Whatever remains after pruning are CONCURRENT versions: writes that happened without either "knowing about" the other. The application must merge these using domain-specific logic. Example: versions = [clock={A:1}, clock={A:2}, clock={B:1}] {A:2} dominates {A:1} → drop {A:1} {A:2} and {B:1} are concurrent → both survive result = [{A:2}, {B:1}] ← conflict! application must merge """ dominated = set() for i, v1 in enumerate(versions): for j, v2 in enumerate(versions): if i != j and v2.vector_clock.dominates(v1.vector_clock): dominated.add(i) # v1 is an ancestor of v2, discard v1 survivors = [v for i, v in enumerate(versions) if i not in dominated] # De-duplicate: identical clocks from different replicas are the same version seen_clocks: list[VectorClock] = [] unique: list[VersionedValue] = [] for v in survivors: if not any(v.vector_clock.clock == s.clock for s in seen_clocks): unique.append(v) seen_clocks.append(v.vector_clock) return unique if unique else versions Partie 6 : Putting It All Together – Une démo Passons à travers un scénario complet : l’écriture / la lecture normale, puis un conflit simulé où deux nœuds divergent et l’application doit les fusionner. def demo(): # ── Setup ────────────────────────────────────────────────────────── # # Five nodes placed at evenly spaced positions on the hash ring. # In a real cluster these would span multiple datacenters. nodes = [ DynamoNode("node-A", token=100), DynamoNode("node-B", token=300), DynamoNode("node-C", token=500), DynamoNode("node-D", token=700), DynamoNode("node-E", token=900), ] dynamo = SimplifiedDynamo(nodes, N=3, R=2, W=2) print("=" * 55) print("SCENARIO 1: Normal write and read (no conflict)") print("=" * 55) # Write the initial shopping cart ctx = dynamo.put("cart:user-42", {"items": ["shoes"]}) # Read it back — should be a clean single version versions = dynamo.get("cart:user-42") print(f"Read result: {versions[0].value}\n") # Update the cart, passing the context from our earlier read. # The context tells Dynamo "this write builds on top of clock ctx". ctx = dynamo.put("cart:user-42", {"items": ["shoes", "jacket"]}, context=ctx) versions = dynamo.get("cart:user-42") print(f"After update: {versions[0].value}\n") print("=" * 55) print("SCENARIO 2: Simulated conflict — two concurrent writes") print("=" * 55) # Write the base version base_ctx = dynamo.put("cart:user-99", {"items": ["hat"]}) # Now simulate a network partition: # node-A and node-B can't talk to each other. # We model this by writing directly to individual nodes. pref_list = dynamo.ring.get_preference_list("cart:user-99", 3) node_1, node_2, node_3 = pref_list[0], pref_list[1], pref_list[2] # Write 1: customer adds "scarf" via node_1 (e.g., their laptop) clock_1 = base_ctx.increment(node_1.node_id) node_1.write("cart:user-99", VersionedValue({"items": ["hat", "scarf"]}, clock_1)) # Write 2: customer adds "gloves" via node_2 (e.g., their phone) # This write also descends from base_ctx, not from clock_1. # Neither write knows about the other → they are concurrent. clock_2 = base_ctx.increment(node_2.node_id) node_2.write("cart:user-99", VersionedValue({"items": ["hat", "gloves"]}, clock_2)) # Read — coordinator sees two concurrent versions and surfaces the conflict versions = dynamo.get("cart:user-99") if len(versions) > 1: print(f"\nConflict detected! {len(versions)} concurrent versions:") for i, v in enumerate(versions): print(f" Version {i+1}: {v.value} clock={v.vector_clock}") # Application-level resolution: union merge (Amazon's shopping cart strategy) # Merge items: take the union so no addition is lost all_items = set() merged_clock = versions[0].vector_clock for v in versions: all_items.update(v.value["items"]) merged_clock = merged_clock.merge(v.vector_clock) merged_value = {"items": sorted(all_items)} print(f"\nMerged result: {merged_value}") # Write the resolved version back with the merged clock as context. # This "closes" the conflict — future reads will see a single version. final_ctx = dynamo.put("cart:user-99", merged_value, context=merged_clock) versions = dynamo.get("cart:user-99") print(f"\nAfter resolution: {versions[0].value}") assert len(versions) == 1, "Should be a single version after merge" if __name__ == "__main__": demo() Expected output: ======================================================= SCENARIO 1: Normal write and read (no conflict) ======================================================= [PUT] key='cart:user-42' value={'items': ['shoes']} clock=VectorClock({'node-A': 1}) (3/3 nodes wrote) [GET] key='cart:user-42' status=clean (3/3 nodes responded) Read result: {'items': ['shoes']} [PUT] key='cart:user-42' value={'items': ['shoes', 'jacket']} clock=VectorClock({'node-A': 2}) (3/3 nodes wrote) [GET] key='cart:user-42' status=clean (3/3 nodes responded) After update: {'items': ['shoes', 'jacket']} ======================================================= SCENARIO 2: Simulated conflict — two concurrent writes ======================================================= [PUT] key='cart:user-99' value={'items': ['hat']} clock=VectorClock({'node-A': 1}) (3/3 nodes wrote) [GET] key='cart:user-99' status=CONFLICT (2 versions) (3/3 nodes responded) Conflict detected! 2 concurrent versions: Version 1: {'items': ['hat', 'scarf']} clock=VectorClock({'node-A': 2}) Version 2: {'items': ['hat', 'gloves']} clock=VectorClock({'node-A': 1, 'node-B': 1}) Merged result: {'items': ['gloves', 'hat', 'scarf']} [PUT] key='cart:user-99' value={'items': ['gloves', 'hat', 'scarf']} ... (3/3 nodes wrote) [GET] key='cart:user-99' status=clean (3/3 nodes responded) After resolution: {'items': ['gloves', 'hat', 'scarf']} Dans le scénario 2, le coordinateur identifie correctement et ne sont ni égaux ni dans une relation de domination - ni n'est un ancêtre de l'autre - de sorte que les deux sont surfacés comme simultané. What to notice: {'node-A': 2} {'node-A': 1, 'node-B': 1} Les leçons clés pour la conception de systèmes After working with Dynamo-inspired systems for years, here are my key takeaways: 1. Always-On Beats Strongly-Consistent Pour les applications orientées vers l’utilisateur, la disponibilité gagne presque toujours.Les utilisateurs toléreront de voir des données légèrement obsolètes.Ils ne toléreront pas « Service indisponible ». 2. Application-Level Reconciliation is Powerful N’ayez pas peur de pousser la résolution des conflits vers l’application. L’application comprend la logique des affaires et peut prendre des décisions plus intelligentes que la base de données ne pourrait jamais. 3. Tunable Consistency is Essential Les ajouts au panier nécessitent une disponibilité élevée (W = 1).Les transactions financières ont besoin de garanties plus fortes (W = N). 4. The 99.9th Percentile Matters More Than Average Concentrez vos efforts d’optimisation sur les latences de queue.C’est ce que les utilisateurs ressentent réellement pendant les heures de pointe. 5. Gossip Protocols Scale Beautifully La coordination décentralisée via les rumeurs élimine les points de défaillance uniques et les échelles à des milliers de nœuds. When NOT to Use Dynamo-Style Systems Soyez honnête sur les compromis. n'utilisez pas cette approche lorsque: Une forte cohérence est requise (transactions financières, gestion des stocks) Des requêtes complexes sont nécessaires (rapports, analyses, joins) Les transactions couvrent plusieurs éléments (Dynamo est uniquement des opérations à clé unique) Votre équipe ne peut pas gérer la cohérence éventuelle (si les développeurs ne comprennent pas les horloges vectorielles et la résolution des conflits, vous aurez des problèmes) Conclusion Dynamo représente un changement fondamental dans la façon dont nous pensons aux systèmes distribués.En acceptant la cohérence éventuelle et en fournissant des compromis ajustables, il permet de construire des systèmes qui atteignent des dimensions massives tout en maintenant une disponibilité élevée. The paper’s lessons have influenced an entire generation of distributed databases. Whether you’re using Cassandra, Riak, or DynamoDB, you’re benefiting from the insights first published in this paper. En tant qu’ingénieurs, notre travail est de comprendre ces compromis en profondeur et de les appliquer de manière appropriée. Dynamo nous donne un outil puissant, mais comme tout outil, il n’est que aussi bon que notre compréhension de quand et comment l’utiliser. Lire plus Papiers Dynamo originaux : SOSP 2007 Le blog de Werner Vogels : All Things Distributed Cassandra Documentation: Comprendre comment ces concepts sont mis en œuvre "Designing Data-Intensive Applications" de Martin Kleppmann - Chapitre 5 sur la réplication Appendice : Problèmes de conception et approches Trois problèmes ouverts qui apparaissent dans les interviews de conception de systèmes et le travail d'ingénierie réel. Problème 1: Résolution des conflits pour un éditeur de document collaboratif : Vous construisez quelque chose comme Google Docs soutenu par un magasin de style Dynamo. Deux utilisateurs modifient le même paragraphe simultanément. The problem La stratégie du panier (union de tous les articles) n'est sûre que parce que l'ajout d'articles est commutatif - Si l'Utilisateur A efface une phrase et que l'Utilisateur B l'édite au milieu de celle-ci, l'union de leurs modifications est sans signification ou contradictoire. Why shopping cart union doesn’t work here {A} ∪ {B} = {B} ∪ {A} The right approach: Operational Transformation (OT) or CRDTs The industry solution is to represent the document not as a blob of text, but as a sequence of operations, and to transform concurrent operations so they can both be applied without conflict: User A's operation: delete(position=50, length=20) User B's operation: insert(position=60, text="new sentence") Without OT: B's insert position (60) is now wrong because A deleted 20 chars. With OT: Transform B's operation against A's: B's insert position shifts to 40 (60 - 20). Both operations now apply cleanly. La stratégie de résolution des conflits pour la couche Dynamo serait: Stockez les opérations (pas les snapshots complets du document) en tant que valeur pour chaque clé. En cas de conflit, collectez toutes les listes d'opérations concurrentes de chaque version. Appliquez OT pour les fusionner en un seul journal d'opération cohérent. Écrivez le journal fusionné avec l'horloge vectorielle fusionnée comme contexte. : Le journal d'opération par segment de document, pas le texte rendu.Cela rend les fusions déterministes et sans perte. What to store in Dynamo Leurs couches de stockage utilisent soit OT, soit une variante de CRDT (Conflict-free Replicated Data Types), qui sont des structures de données mathématiquement garanties de fusionner sans conflits indépendamment de l'ordre de l'opération. Real-world reference Problème 2: Choisir N, R, W pour différents cas d'utilisation Quelle configuration choisiriez-vous pour (a) un magasin de session, (b) un catalogue de produits, (c) des profils d’utilisateur ? The problem La bonne façon de penser à cela: identifiez le mode d'échec qui coûte plus cher - une écriture manquée (perte de données) ou une écriture rejetée (indisponibilité). Session store — prioritize availability Les sessions sont temporaires et spécifiques à l'utilisateur. Si la session d'un utilisateur est brièvement arrêtée ou perdue, ils sont déconnectés et se connectent à nouveau. N=3, R=1, W=1 Rationale: - W=1: Accept session writes even during heavy failures. A user can't log in if their session write is rejected. - R=1: Read from any single node. Stale session data is harmless. - N=3: Still replicate to 3 nodes for basic durability. Trade-off accepted: Stale session reads are possible but inconsequential. Product catalog — prioritize read performance and consistency Les données sur les produits sont rarement écrites (par des équipes d'options) mais lues des millions de fois par jour.Les prix ou les descriptions fixes sont problématiques. N=3, R=2, W=3 Rationale: - W=3: All replicas must confirm a catalog update before it's live. A price change half-published is worse than a brief write delay. - R=2: Read quorum overlap with W=3 guarantees fresh data. Acceptable: catalog writes are rare, so write latency doesn't matter. - N=3: Standard replication for durability. Trade-off accepted: Writes are slow and fail if any node is down. Acceptable because catalog updates are infrequent. User profiles — balanced Les données de profil (nom, e-mail, préférences) sont modérément importantes. Un profil stable est ennuyeux mais pas dangereux. Une mise à jour rejetée (par exemple, un utilisateur ne peut pas mettre à jour son e-mail) est un vrai problème. N=3, R=2, W=2 Rationale: - The classic balanced configuration. - R + W = 4 > N = 3, so quorums overlap: reads will see the latest write. - Tolerates 1 node failure for both reads and writes. - Appropriate for data that matters but doesn't require strict consistency. Trade-off accepted: A second simultaneous node failure will cause errors. Acceptable for non-critical user data. Decision framework summary: Priority R W When to use Max availability 1 1 Sessions, ephemeral state, click tracking Balanced 2 2 User profiles, preferences, soft state Consistent reads 2 3 Catalogs, config, rarely-written reference data Highest consistency 3 3 Anywhere you need R+W > N with zero tolerance for stale reads (still not linearizable) Disponibilité max 1 1 Sessions, état éphémère, suivi des clics équilibré 2 2 Profils d'utilisateur, préférences, état doux Une lecture cohérente 2 3 Catalogues, config, données de référence rarement écrites La plus grande cohérence 3 3 Partout où vous avez besoin de R+W > N avec tolérance zéro pour les lectures stables (encore pas linéarisable) Problème 3: Tester un système Dynamo-Style sous les scénarios de partition Comment vérifiez-vous que votre système se comporte correctement lorsque les nœuds échouent et que des partitions se produisent? The problem C'est l'un des problèmes les plus difficiles dans les tests de systèmes distribués, car les bugs n'apparaissent que dans des interlignes spécifiques d'événements concomitants difficiles à reproduire déterministiquement. Layer 1: Unit tests for the logic in isolation Avant de tester le comportement distribué, vérifiez les blocs de construction de manière indépendante.La logique de comparaison d'horloge vectorielle, la détection de conflits et les fonctions de réconciliation peuvent toutes être testées avec des tests d'unité pure - aucun réseau n'est nécessaire. def test_concurrent_clocks_detected_as_conflict(): clock_a = VectorClock({"node-A": 2}) clock_b = VectorClock({"node-B": 2}) assert not clock_a.dominates(clock_b) assert not clock_b.dominates(clock_a) # Both survive reconciliation → conflict correctly detected def test_ancestor_clock_is_discarded(): old_clock = VectorClock({"node-A": 1}) new_clock = VectorClock({"node-A": 3}) assert new_clock.dominates(old_clock) # old_clock should be pruned during reconciliation Layer 2: Deterministic fault injection Plutôt que d'espérer que les échecs se produisent dans le bon ordre pendant le test de charge, injectez-les délibérément et à plusieurs reprises. est une version simple de cela. Dans les systèmes de production, les bibliothèques ou Et cela au niveau de l’infrastructure. node.down = True japonais Chaos au singe Scénarios clés à tester : Scenario A: Write succeeds with W=2, third replica is down. → Verify: the data is readable after the down node recovers. → Verify: no data loss occurred. Scenario B: Two nodes accept concurrent writes to the same key. → Verify: the next read surfaces exactly 2 conflicting versions. → Verify: after the application writes a merged version, the next read is clean. Scenario C: Node goes down mid-write (wrote to W-1 nodes). → Verify: the write is correctly rejected (RuntimeError). → Verify: no partial writes are visible to readers. Scenario D: All N nodes recover after a full partition. → Verify: no data was lost across the cluster. → Verify: vector clocks are still meaningful (no spurious conflicts). Layer 3: Property-based testing Au lieu d'écrire des cas de test individuels, définissez qui doit toujours tenir et générer des milliers de séquences d'opération aléatoires pour essayer de les violer : invariants # Invariant: after any sequence of writes and merges, a final get() # should always return exactly one version (no unresolved conflicts). # Invariant: a value written with a context derived from a previous read # should never produce a conflict with that read's version # (it should dominate it). # Invariant: if R + W > N, a value written successfully should always # be visible in the next read (read-your-writes, absent concurrent writes). Des outils comme (Python) vous permet d'exprimer ces invariants et de trouver automatiquement des contre-exemples. Hypothèse Layer 4: Linearizability checkers Pour la plus grande confiance, enregistrez l'heure de début, l'heure de fin et le résultat de chaque opération lors d'un test d'injection de défaut, puis envoyez l'historique à un vérificateur de linéarisation tel que Il vous dira si tout historique observé est cohérent avec une exécution séquentielle correcte - même pour un système éventuellement cohérent fonctionnant dans les limites de ses garanties déclarées. Knossos Écrit à partir des tranchées des systèmes distribués. connaissances testées par la bataille, zéro ondulation de la main. Télécharger Link Télécharger Link
