A senior engineer’s perspective on building highly available distributed systems コンテンツテーブル 原題:Why Dynamo Changed Everything CAP Theorem Trade-offについて Core Architecture Components Consistent Hashing for Partitioning Replication Strategy (N, R, W) Vector Clocks for Versioning Sloppy Quorum and Hinted Handoff 紛争解決:ショッピングカートの問題 Read and Write Flow(フロー) Merkle Trees for Anti-Entropy(アンチエントロピー) メンバーシップと失敗検出 パフォーマンスの特徴:リアルナンバー Partitioning Evolution 戦略 Dynamoと近代システムの比較 Dynamoがあなたに与えることのないもの 実践実施例 システムデザインのための重要なレッスン Dynamo-Style システムを使用しない場合 結論 附属書:デザインの問題とアプローチ これは長い形式の参照 - 各セクションは独自に立っていますので、あなたにとって最も関連するものに直接ジャンプしてください。 これは長い形式の参照 - 各セクションは独自に立っていますので、あなたにとって最も関連するものに直接ジャンプしてください。 原題:Why Dynamo Changed Everything 2007年にAmazonがDynamoの論文を発表したとき、それは単なる学術的な練習ではなかった。大規模な実際の問題に対する戦闘テストされた解決策だった。私はこの論文を初めて読んだとき、分散システムについて考える方法を根本的に変えたことを覚えています。 ショッピングカートやセッション管理システムなどのAmazonの高トラフィックサービスをサポートするように設計されました. 二次的なインデックス、関連性、関係性のセマンティクスはありません - キーと値だけ、可用性とスケーラビリティに極めて焦点を当てています. それは、最高のクォーラム設定でさえ、線形化またはグローバルオーダーの保証を提供しません. あなたのシステムがそれらの属性を必要とする場合、Dynamoは適切なツールではありません。 Dynamo is a distributed key-value storage system. アマゾンが直面した核心的な問題は、単純に述べるが、残酷に解決するものであった。 ネットワークパーティションまたはサーバーの故障中に誰かが彼らのショッピングカートにアイテムを追加しようとすると、その書き込みを拒否することは受け入れられない。 How do you build a storage system that never says “no” to customers? The CAP Theorem Trade-off: Why Dynamo Chooses Availability について Dynamoがどのように機能するかを掘り下げる前に、その周りに設計されている根本的な制約を理解する必要があります。 CAP理論とは? CAP理論は、分散システムにおける根本的な妥協を説明します:ネットワークパーティションが発生すると、一貫性と可用性の間に選択しなければなりません。 統一性(C):すべてのノードが同時に同じデータを見る 可用性(A):すべてのリクエストに答えが与えられる(成功または失敗) Partition Tolerance(P):システムはネットワークの故障にもかかわらず動作し続けます。 一般的な略語は「Pick 2 of 3」ですが、これは過剰な単純化です。実践では、ネットワークパーティションはスケールで避けられないので、実際の決定は以下の通りです。 これが実際のデザインの選択です。 when partitions occur (and they will), do you sacrifice consistency or availability? : ネットワークパーティションが発生します. ケーブルが切断され、スイッチが故障し、データセンターが接続を失います. あなたはそれらを回避することはできませんので、あなたは選択しなければなりません: 一貫性または可用性? The harsh reality 従来のデータベースは一貫性を選択する : 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 選択可用性 : 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 THE TRADE-OFF VISUALIZED 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 本物のAmazonの例:ブラックフライデーショッピングカート ブラックフライデーだと思えば、何百万人もの顧客がショッピングをしている。 : 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) なぜこの選択が電子商取引に意味があるのか アマゾンは数学をやった: 書類を拒否するコスト:即時失われた販売(50〜200ドル) 矛盾した書き込みを受け入れるコスト:時々ショッピングカートを組み合わせる必要がある(めったに起こらず、簡単に修正可能) ビジネス意思決定:書き込みを受け入れ、希少な紛争に対処 : Types of data where Availability > Consistency ショッピングカート(Merging Conflicting Additions) セッションデータ(Last-Write-Wins is OK) ユーザーの好み(一貫性が受け入れられる場合) ベストセラーリスト (approximate is fine) : Types of data where Consistency > Availability 銀行口座の残高(対立した残高がない) Inventory counts (cann’t oversell) について トランザクションログ(注文しなければならない) したがって、Dynamoはすべてではありませんが、Amazonの電子商取引の使用ケースでは、強力な一貫性よりも可用性を選択することは正しい妥協でした。 重要なニュアンス:DynamoはしばしばAPシステムとして記述されるが、調整可能な一貫性システムと呼ぶのはより正確である。RおよびWクォーラム構成に応じて、CPに近づくことができます。 Dynamo はしばしば AP システムとして記述されるが、それを AP と呼ぶのはより正確である。 あなたのRおよびWクォーラム構成に応じて、CPに近づくことができます。APラベルは、電子商取引ワークロードに最適化されたデフォルト/推奨構成に適用されます。 Important nuance tunable consistency system コアアーキテクチャコンポーネント 1. Consistent Hashing for Partitioning(パーティションのための一貫したハッシュ) これを具体的な例で説明します、なぜなら、一貫したハッシュは、あなたがそれをアクションで見るまで魔法のように思える概念の1つだからです。 問題:伝統的なハッシュベースのシャーディング あなたが3つのサーバーを持っており、それらにデータを配布したいと想像してください。 # 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 これは、サーバーを追加または削除するまで機能します. 3 から 4 サーバーに移行するとどうなるかを見てみましょう: # 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!) : サーバーの数を変更すると、ほぼすべてのデータが再配布される必要があります。 The disaster ソリューション: Consistent Hashing 一貫したハッシュは、ハッシュスペースをサークル(0〜2^32−1)として扱って解決します。 Step 1: Place servers on the ring それぞれのサーバーにランダムな位置(「トークン」と呼ばれる)が割り当てられます。 Step 2: Place data on the ring データを保存したい場合、あなたは: Hash the key to get a position on the ring (リングに位置するためのキー) この位置から時刻通り歩く。 最初に出会ったサーバーにデータを保存する タグ : 完全指輪 キーは時刻通りに次のサーバーに進みます: キーはサーバーに到達するまで時計方向で動き、そのサーバーが鍵を所有している。 Simple rule : Examples user_123 at 30° → walking to 45° → Server A owns it user_456 at 150° → walks to 200° → Server C owns it cart_789 at 250° → walking to 280° → Server D owns it at 300° → walks past 360°, wraps to 0°, continues to 45° → product_ABC Server A owns it Who owns what range? Server A (45°): 281°から45°まですべてを所有する(周囲に包まれる) サーバーB(120°):46°から120°まですべてを所有 サーバーC(200°):121°から200°まですべてを所有 Server D (280°): 201°から280°まですべてを所有する The Magic: Adding a Server(サーバーを追加する) 次に、Server E を 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 : 121°～160°の範囲内のキーだけが移動する必要があります(CからEまで)。 Result 仮想ノードの最適化 基本的な一貫したハッシュングアプローチに重要な問題があります: . random distribution can be extremely uneven The Problem in Detail: サーバーごとにランダムに1つのポジションを割り当てると、基本的に円板にダルトを投げかけます。 具体的な例を紹介します: 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: Server D はすべてのデータの 50% を処理し、 Server B は 4% しか処理しません。 Server DのCPU、ディスク、ネットワークは最大化されます。 Server B is mostly idle (wasted capacity) (サーバーBはほとんど無職です。 99.9th percentile latency is dominated by Server D being overloaded. あなたの99.9th percentile latency is dominated by Server D being overloaded. あなたの99.9th percentile latency is dominated by Server D being overloaded. : When Server D becomes slow or fails: Hotspot cascading すべての50%の負荷がサーバーAに移行する(次の1つは時計方向) サーバーAが過剰に充電 システムのパフォーマンスが災害的に悪化 非効率なスケーリング:サーバーを追加することは、新しいサーバーが既に小さな範囲で着陸する可能性があるため、均等に役立ちません。 Visualizing the problem: 各物理サーバは複数の仮想ポジション(トークン)を取得します。 Dynamo’s solution サーバーごとに1つのダート投げ捨ての代わりに、多くのダートを投げ捨てます。 How Virtual Nodes Fix the Problem: 同じ4つのサーバーを取ろうが、今では各サーバーが1の代わりに3つの仮想ノード(トークン)を得ている。 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) 負荷は4%から50%の代わりに19%から31%の範囲にあります。 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: 論文では、時間とともに進化したさまざまな戦略を挙げています。 Early versions: 100-200 virtual nodes per physical server 後で最適化:ノードあたりQ/Sトークン(Q = total partitions、S = number of servers) 典型的な設定:各物理サーバーには、128～256の仮想ノードがある可能性があります。 The Trade-off: Balance vs Overhead より多くの仮想ノードは、より良い負荷配布を意味しますが、コストがあります。 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: : Each node maintains routing information Metadata size 1 サーバーあたりのトークン: Track 4 entries サーバーあたり 128 トークン:トラック 512 エントリ : Nodes exchange membership info periodically Gossip overhead More tokens = more data to sync between nodes. より多くのトークン=より多くのデータをノード間で同期する Every second, nodes gossip their view of the ring 再バランスをとる複雑性:Nodes join/leave より多くの仮想ノード=より多くのパーティション転送を調整する しかし、それぞれの転送はより小さい(実際にはブートストラップに良い) 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: ほとんどのDynamoデプロイメントでは、物理サーバーごとに128〜256の仮想ノードを使用しています。 負荷分布 10-15%の変動範囲内(十分) Metadata overhead under 100KB per node (negligible) 急速な故障回復(負荷が多くのノードに広がる) 128から512のトークンに移行すると、負荷バランスを2〜3%向上させますが、メタデータのサイズと噂トラフィックを倍増させます。 Why not more? 物理サーバー(トップ)は、リング上の複数の仮想位置(底部)にマップします. This distributes each server's load across different parts of the hash space. Key concept : Benefits More Load Distribution より When a server fails, its load is distributed across many servers (not just one neighbor) When a server joins, it steals a small amount from many servers Real-World Impact Comparison 実際の数字との違いを見てみましょう。 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 「Aha!」の瞬間 重要な洞察点は、これです。 Consistent hashing decouples the hash space from the number of servers. Traditional: server = hash(key) % num_servers ← num_servers is in the formula! consistent: server = ring.findNextClockwise(hash(key)) ← num_servers is not in the formula! このため、サーバーを追加/削除することは、データのほんのわずかな部分にしか影響を与えません. The hash values do not change—only which server “owns” which range changes, and only locally. 水道ステーション(サーバー)を含む円形の走行コースのように考えてください。新しい水道ステーションを追加する場合、ランナーは最寄りの旧ステーションと新しいステーションの間にある場合にのみステーションを変更します。 2. Replication Strategy (N, R, W) The Problem: Availability vs Consistency Trade-off アマゾンのショッピングカートを構築していると想像してください. A customer adds an item to their cart, but at that exact moment: One server is being rebooted for maintenance Another server has a network hiccup A third server is perfectly fine (一貫性の強さ): 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 This is unacceptable for e-commerce. Every rejected write is lost revenue. Dynamoのソリューション:Tunable Quorums Dynamoはあなたが望む正確なコントロールを調節するための3つのボタンを提供します: N:コピー数(データのコピー数) R: Read quorum (How many replicas must respond for a successful reading) : Write quorum (how many replicas must acknowledge for a successful write) W : いつ , you guarantee quorum overlap—meaning at least one node that received the write will be queried during any read. This overlap enables detection of the latest version, provided the reconciliation logic correctly identifies the highest vector clock. It does not automatically guarantee read-your-writes unless the coordinator properly resolves versions. The magic formula R + W > N なぜこれが現実のシナリオで重要なのかを示そう: シナリオ1:ショッピングカート(可用性優先) 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) シナリオ2:セッション状態(バランスのとれたアプローチ) 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 厳格な取引保証を必要とするシステムは通常、CPシステムを選択します。この構成は、Dynamoによって技術的にサポートされていますが、最初に使用を動機づける可用性の特性を犠牲にします。 Configuration Comparison Table 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 ↓↓↓↓↓↓ ⭐⭐ ショッピングカート、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 ↓↓↓↓↓↓↓↓↓↓↓↓ ⭐⭐⭐⭐ Product catalog, CDN metadata Write-Heavy 3 3 1 ↓↓↓↓↓↓↓↓↓↓↓↓ ⭐⭐⭐ Click tracking, メトリック 金融システムに関する注意: 強力な取引保証(例えば、銀行口座残高)を必要とするシステムは、通常、Dynamoを使用してはいけません。 金融システムに関する注意: 強力な取引保証(例えば、銀行口座残高)を必要とするシステムは、通常、Dynamoを使用してはいけません。 The Key Insight Most systems use なぜなら: N=3, R=2, W=2 耐久性: 永続的なデータ損失前に最大2回の複製故障を耐えられる(独立した故障を仮定し、関連する中断がない)。 : Tolerates 1 node failure for both reads and writes Availability : R + W > N guarantees that read and write quorums overlap, enabling read-your-writes behavior in the absence of concurrent writes. Consistency パフォーマンス:最も遅いノードを待たないでください(3つのうち2つだけが必要です) Real production numbers from the paper: Amazonのショッピングカートサービスはピーク(休日の季節): Configuration: N=3, R=2, W=2 数千万件の要請を処理 1日で300万件を超えるチェックイン No downtime, even with server failures (サーバの故障でさえ) この調整可能なアプローチは、Dynamoを革命的なものにしたものです. You are not stuck with one-size-fits-all. あなたは実際のビジネス要件に基づいてそれを調節します。 3. Vector Clocks for Versioning The Problem: Detecting Causality in Distributed Systems When multiple nodes can accept writes independently, you need to answer a critical question: 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! タグ: vector clocks ベクトル時計は、単純なデータ構造である:リスト どのノードがどのバージョンを見たかを追跡するペア。 (node_id, counter) The rules: When a node writes data, it increments its own counter When a node reads data, it gets the vector clock 2 ベクトル時計を比較する場合: If all counters in A ≤ counters in B → A is an ancestor of B (B is newer) If some counters in A > B and some B > A → A and B are concurrent (conflict!) Step-by-Step Example 複数の更新を通じてショッピングカートを追跡しましょう: 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. 現実世界の特徴 The Dynamo paper reports the following conflict distribution measured over 24 hours of Amazon’s production shopping cart traffic. These numbers reflect Amazon’s specific workload — high read/write ratio, mostly single-user sessions — and should not be assumed to generalize to all Dynamo deployments: 99.94% - Single version (no conflict) 0.00057% - 2 versions 0.00047% - 3 versions 0.00009% - 4 versions 実際には紛争は珍しい! Key insight Why conflicts happen: 通常、ネットワークの失敗からではなく、 主に共著者から(しばしば自動化プロセス/ボット) 人間のユーザーは、ネットワークの速度に比べて遅いため、紛争を起こすことはめったにありません。 サイズの問題 Vector clocks can grow unbounded if many nodes coordinate writes. Dynamo’s solution: once the clock exceeds a size threshold. 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?!" 😡 The problem: . If those specific nodes are down, the system becomes unavailable. 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 タグ : Sloppy Quorum Dynamo relaxes the quorum requirement: “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) Handoff がどのように機能するか ノードが失敗したノードを一時的に置き換えると、データと共に「ヒント」が保存されます。 Detailed Hinted Handoff Process 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}") なぜこれが素晴らしいのか 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 構成例 // 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 }; 現実世界の影響 From Amazon’s production experience: During normal operation: Hinted handoff rarely triggered(ヒントされたハンドフはめったに起動しない) Most writes go to preferred nodes. 大抵の書き込みは、好みのノードに移動します。 Hints database is mostly empty 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: 最大限の書き込み可用性 ✓ 失敗時に維持された耐久性 ✓ノードが戻ったときに自動回復 手動介入は不要 Costs: ✗ Temporary inconsistency (data not on “correct” nodes) ✗ Extra storage for hints database Hint Transferのためのバックグラウンド帯域幅 ✗ Slightly more complex code Hinted handoff は一時的な耐久性を提供し、永続的な複製ではありません。 代替ノード (D のような) がヒントを B に戻すことができる前に失敗する場合、現実の複製の数は状況が解決するまで N 以下に落ちます。 可用性の利点は、電子商取引のワークロードのコストをはるかに上回ります。 Amazon’s verdict: 紛争解決:ショッピングカートの問題 Let’s talk about the most famous example from the paper: the shopping cart. This is where rubber meets road. 紛争とは何ですか(そしてなぜ起こるのですか)。 A occurs when two writes happen to the same key on different nodes, without either write “knowing about” the other. This is only possible because Dynamo accepts writes even when nodes can’t communicate—which is the whole 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 アプリケーションに接続して、アプリケーションが何をすべきかを決めることができます。 both versions アプリケーションは、紛争に対して何をしますか? This is the crucial part that the paper delegates to you: Dynamo はすべての同時バージョンを提供します; あなたのコードはそれらを合併する方法を決定します。 the application must resolve conflicts using business logic ショッピングカートとして、AmazonはAを選びました。 : keep all items from all concurrent versions. The rationale is simple—losing an item from a customer’s cart (missing a sale) is worse than occasionally showing a stale item they already deleted. 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 以下、実際の和解コードです。 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) 同盟戦略には不快なエンドケースがあります: . 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. : 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 : 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 Read and Write Flow 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. 書く道 Step-by-step narration of a PUT request: クライアントは、リクエストを任意のノード(負荷バランサーを通じて)または直接調整者に送信します。 調整子が決定される — これはリング上のキーのハッシュ位置の好みリストの最初のノードです。 ベクター時計は更新されます - コマンドレーターは、ベクター時計に独自のカウンターを加算し、新しいバージョンを作成します。 , then fans out the write to the other N-1 nodes in the preference list simultaneously. The coordinator writes locally 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. W ACK が到着すると、コーディネーターはクライアントに 200 OK を返します。 : The client gets a success response as soon as W nodes confirm. The other (N – W) nodes will receive the write asynchronously. This is why the system is “eventually consistent”—all nodes データは、必ずしも同時に入手する必要はありません。 Key insight about the write path ウィル 読む道 Step-by-step narration of a GET request: クライアントは、そのキーのための調整者にリクエストを送信します。 in the preference list simultaneously (not just R). This is important — it contacts all N, but only needs R to respond. The coordinator sends read requests to all N nodes Rノードが答えを返すと、調整員は遅いノードを待つことなく、Rノードが答えを返す。 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 happens in the background: if the coordinator noticed any node returned a stale version, it sends the latest version to that node to bring it up to date. Read repair Dynamo は一般用途のストレージ エンジンなので、あなたがショッピング コート、ユーザー プロフィール、セッション トークンを保存しているかどうかはわかりません。 両方の矛盾するバージョンをビジネスに意味のある方法で組み合わせる方法を知っています. The coordinator handes you the raw concurrent versions along with the vector clock context, and you do the right thing for your use case. コラボレーターは、ベクトル時計の文脈と共に原始の同時バージョンをあなたに送信し、あなたはあなたの使用ケースのために正しいことをします。 Why does the client receive the conflict instead of the coordinator resolving it? your 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 未解決の紛争の上で書く。 The vector clock context is the key to closing the loop もう一 Merkle Trees for Anti-Entropy(アンチエントロピー) 問題: レプリカが同期されていないことをどのように知るのですか? After a node recovers from a failure, it may have missed some writes. After a network partition heals, two replicas might diverge. How does Dynamo detect and fix these differences? ブルートフォースのアプローチは、「ノードAの各キーを1時間ごとにノードBと比較し、異なるものを同期する」ですが、Amazonの規模では、1つのノードが何百万ものキーを格納する可能性があります。 コアアイデア:個々のキーを比較する代わりに、比較する . ハッシュが一致する場合、そのグループ全体が同一である - ジャンプします. Only drill down into groups where hashes differ. Dynamo uses Merkle trees to solve this efficiently. hashes of groups of keys 重要: Merkle tree sync はバックグラウンドのアンチエントロピーメカニズムです。それはホットリーディング/書き込みパスにありません. 通常の読書と書き込みは、バージョニングのためのベクトル時計とクォーラムを使用します. Merkle trees は、バックグラウンドで定期的に実行される修理プロセスで、スライスした不一致を捕まえます。 Merkle tree sync is a メカニズム. It is not on the hot read/write path. Normal reads and writes use vector clocks and quorums for versioning. Merkle trees are for the repair process that runs periodically in the background to catch any inconsistencies that slipped through. 通常の読書と書き込みは、バージョン化のためのベクトル時計とクォームを使用します. Merkle trees are for the repair process that runs periodically in the background to catch any inconsistencies that slipped through. Important background anti-entropy How a Merkle Tree Is Built Each node builds a Merkle tree over its data, organized by key ranges: 葉のノードには、実際のデータキーの小さな範囲のハッシュが含まれています(例えば、キーk1、k2、k3のすべての値のハッシュ)。 内部ノードには、子どものハッシュが含まれています。 is a single hash representing the data on the node. The root all 2 ノードが Merkle Tree を使用して同期する方法 Node A および Node B が同期しているかどうかを確認したい場合: : ルートハッシュを比較します. 同じ場合は、すべてが同じです. 完了しました! (データ自体のネットワークトラフィックはありません.) Step 1 : 根が異なる場合は、左の子供と比較してください. 同じ? キースペースの全体の半分を省略します。 Step 2 : あなたが葉のノードに到達するまで、ハッシュが異なるサブツリーにのみ下り続ける。 Step 3 : Sync only the specific keys in the differing leaf nodes. 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) Why This Is Efficient Merkleの木の力は、あなたが必要とするハッシュ比較の数が、 (ロガリズムはキーの数であって、キー自体の数ではない。 depth of the tree 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! そして、批判的に、もし2つのノードが (which is almost always true in a healthy cluster), the root hashes often match entirely and zero data needs to be transferred. The anti-entropy process is very cheap in the common case. mostly in sync メンバーシップと失敗検出 Dynamo はメンバーシップ管理のためのゴシップ プロトコルを使用しています. 各ノードは定期的にランダムな仲間とメンバーシップ 情報を交換しています. マスターノードはありません. すべての連携は完全に分散化されています. Gossip-Based Membership キーデザインポイント : 各ノードはクラスターメンバーシップの独自のビューを維持します. There is no central registry, so there is no single point of failure for membership data. No single coordinator : Dynamo uses an accrual-based failure detector (similar to Phi Accrual). Rather than a binary “alive/dead” judgment, nodes maintain a この値は、 peer が反応しないほど長くなります. This avoids false positives from transient network hiccups. Failure suspicion vs. detection 容疑レベル 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 : New nodes contact a seed node to join, then gossip spreads their presence to the rest of the cluster. Ring membership is eventually consistent—different nodes may have slightly different views of the ring momentarily, which is acceptable. Decentralized bootstrapping パフォーマンスの特徴:リアルナンバー The paper provides fascinating performance data. Let me break it down: LATENCE DISTRIBUTION Metric | Average | 99.9th Percentile --------------------|---------|------------------ Read latency | ~10ms | ~200ms Write latency | ~15ms | ~200ms Key insight: 99.9th percentile is ~20x the average! 99.9th percentile は: Why the huge gap? ゴミ収集休憩 Disk I/O variations ネットワークジッター Load imbalance このため、Amazon SLA は平均ではなく 99.9 番目のパーティイルで指定されています。 バージョン紛争 24時間のAmazonの生産ショッピングカートのトラフィックから(Dynamoの紙によると)。これらは、普遍的な基準ではなく、Amazonの特定のワークロードの特徴を反映しています。 99.94% - Saw exactly one version (no conflict) 0.00057% - Saw 2 versions 0.00047% - Saw 3 versions 0.00009% - Saw 4 versions 対立は実践では稀である! ほとんどの場合、失敗ではなく、共通の作家(ロボット)によって引き起こされる。 Takeaway Partitioning Evolution 戦略 Dynamoは3つの分割戦略を通じて進化し、この進化は重要な教訓を教えてくれます。 戦略1:ランダム・トークン(初期) Problem: Random token assignment → uneven load Problem: Adding nodes → expensive data scans Problem: Can't easily snapshot the system : ランダムトークン割り当てはエレガントに聞こえるが、実際には悪夢である. 各ノードはリング上にランダムな位置を占め、これは非常に異なるデータ所有範囲と不均衡な負荷分布を意味する。 Operational lesson Strategy 2: Equal-sized Partitions + Random Tokens Improvement: Decouples partitioning from placement Problem: Still has load balancing issues Strategy 3: Q/S Tokens Per Node — Equal-size Partitions + Deterministic Placement (Current) (ノードごとにQ/Sトークン) What Q and S mean: Q = リングが分割される固定パーティションの合計数(たとえば1024)。これらを、決して形を変えることのできないハッシュスペースの同じサイズの、事前に切断された切片として考える。 S = クラスター内の現時点での物理サーバー数(例えば8)。 Q/S = それぞれのサーバーがどれだけの固定部分を担当しているか(例えば、1024 / 8 =サーバーあたり128パーティション) 以前の戦略からの重要な転換:リングは現在Qの固定、同じサイズのパーティションに分かれています。 サーバーはもはやランダムな位置を取得しません - それぞれが正確にQ/Sパーティションを所有し、リングの周りに均等に配布しています。 まずは 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. この進化 - ランダムトークンからバランスのとれた所有権を持つ固定、同じサイズのパーティションに至るまで - は、Dynamoからの最も教訓的な操作学習の1つです。 Dynamoと近代システムの比較 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 インストール可能(N、R、W) タイムシリーズ、アナリスト Direct descendant - ダイナモのインスピレーションを強く受け、同じ一貫したハッシュとクォーラムコンセプトを使用 Riak タグ: vector clocks Key Value ストア 最も忠実なDynamo実装 Amazon DynamoDB 最終的にはデフォルトによる一貫性 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 トンネル LinkedInのデータストア オープンソース Dynamo Google Spanner 線形化 Global SQL Dynamo に反する選択 - TrueTime 時計同期を介して CP を優先 Redis Cluster Eventually consistent Caching, sessions 一貫したハッシュを使用する; より単純な紛争解決 DynamoDBの混乱:多くのエンジニアはAmazon DynamoDBとDynamoの紙を混同します。彼らは非常に異なります。DynamoDBは操作のシンプルさに最適化された管理サービスです。それはベクトル時計を露出しません、同じパーティションシステムを使用しません、独自の一貫性モデルを使用します。この紙はDynamoDBに先立つ内部Dynamoストレージエンジンについてです。 : 多くのエンジニアは、Amazon DynamoDB を Dynamo ペーパーと混同します。 彼らは非常に異なります。 DynamoDB は操作のシンプルさに最適化された管理サービスです。 ベクトル時計を露出しません、同じパーティション スケジュールを使用しません、独自の一貫性モデルを使用します。 The DynamoDB confusion Dynamoがあなたに与えることのないもの すべての高級エンジニアのブログは、制限について正直でなければなりません。 トランザクションなし: オペレーションは単鍵のみで、複数のキーを原子的に更新することはできません。 : You can only look up data by its primary key (at least in the original design). No secondary indexes : It’s a key-value store. There is no query language. No joins グローバル順序なし:異なるキー間のイベントには、保証される順序はありません。 No linearizability: Even at R=W=N, Dynamo does not provide linearizable readings. There is no global clock, no strict serializability. グローバル時計は存在しません。 自動紛争解決なし:システムは紛争を検出し、アプリケーションに表面化します。アプリケーションはそれらを解決しなければなりません。 規模の修理コスト:アンチエントロピープロセス(Merkle tree reconciliation)は無料ではありません。 Vector clock growth: In high-churn writing environments with many coordinators, vector clocks can grow large enough to require truncation, which introduces potential causality loss. Vector clocks can grow large enough to require truncation, which introduces potential causality loss. Vector clocks can grow large enough to require truncation, which introduces potential causality loss. Vector clocks can grow large enough to require truncation, which introduces potential causality loss. これらの制限を理解することは、生産におけるDynamoスタイルのシステムの成功に不可欠です。 実践実施例 それは意図的に単純化されています - 実際のネットワーキングなし、持続性なし - ですが、ベクトル時計、一貫したハッシュリング、クォーラム読み書き、紛争検出がどのように相互作用するかを忠実にモデリングします。 第1章 ベクター時計 The class is the foundation of version tracking. It’s just a dictionary mapping 二つの主要な作戦: 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})" Part 2: Versioned Value (バージョン) Every value stored in Dynamo is wrapped with its vector clock. This pairing is what allows the coordinator to compare versions during reads and detect conflicts. @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})" Part 3: Simulated Node 実際のDynamoでは、各ノードは別々のプロセスです. ここでは、メモリ内のオブジェクトとしてそれらをシミュレートします. 重要な詳細:各ノードには独自のローカルがあります dict. Nodes can be marked as 失敗をシミュレートする 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})" 第4部:一貫したハッシュリング We sort nodes by their token (position) and use a clockwise walk to find the coordinator and preference list for any key. 私たちは、ノードをそのトークン(位置)によって分類し、時計方向の歩きを用いて、任意のキーの調整者と好みリストを見つける。 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 第5章 ダイナモ・コマンドレーター これがシステムの核心であり、クライアントの要請を処理し、ファンが複製し、クォーラムを待つこと、紛争を検出する論理です。 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 Part 6: Putting It All Together — A Demo 完全なシナリオを実行しましょう:通常の書き込み/読書、そして2つのノードが分離し、アプリケーションがそれらを統合しなければならないシミュレーションされた紛争。 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']} シナリオ2では、コーディネーターが正しく識別する。 そして どちらも平等でなく、支配的な関係にあるわけではありません - どちらも互いの先祖ではありません - したがって、両方とも同時に表面に浮かびます。 What to notice: {'node-A': 2} {'node-A': 1, 'node-B': 1} システムデザインのための重要なレッスン 長年にわたりDynamoにインスピレーションを与えたシステムで働いた後、以下が私の主要な取り組みです。 1. Always-On Beats Strongly-Consistent ユーザー向けのアプリケーションでは、ほとんど常に可用性が勝利します。ユーザーは、少し遅いデータを見るのを許しません。 2. Application-Level Reconciliation is Powerful アプリケーションに紛争解決を押すことを恐れないでください. アプリケーションはビジネス論理を理解し、データベースよりも賢い意思決定を行うことができます。 3. Tunable Consistency is Essential ショッピングカートの追加には、高い可用性(W=1)が必要です。金融取引には、より強力な保証(W=N)が必要です。 4. The 99.9th Percentile Matters More Than Average あなたの最適化努力を尾の遅延に焦点を当てます. That's what users actually experience during peak times. 5. Gossip Protocols Scale Beautifully 冗談を通じて分散化された連携は、単一の失敗点と数千のノードのスケールを排除します。 Dynamo-Style システムを使用しない場合 コンパクトオフについて正直にしてください. このアプローチを使用しないでください: 強力な一貫性が必要です(金融取引、在庫管理) 複雑なクエリが必要です(レポート、分析、 joins) Transactions span multiple items (Dynamo is single-key operations only) (トランザクションは複数の項目をカバーします。 チームは最終的な一貫性を処理できない(開発者がベクトル時計や紛争解決を理解していない場合、問題が生じる) 結論 Dynamo represents a fundamental shift in how we think about distributed systems. By embracing eventual consistency and providing tunable trade-offs, it enables building systems that scale to massive sizes while maintaining high availability. この論文のレッスンは、分散データベースの全世代に影響を与えました。Cassandra、Riak、DynamoDBを使用しているかどうかにかかわらず、この論文で最初に発表された洞察から利益を得ています。 エンジニアとして、私たちの仕事はこれらの妥協を深く理解し、適切に適用することです Dynamoは私たちに強力なツールを提供しますが、どのツールと同様に、それはいつ、どのように使用するかについての私たちの理解と同じくらい良いです。 続きを読む オリジナルDynamo Paper:SOSP 2007 Werner Vogels’ Blog: All Things Distributed(ウェルナー・ヴォーゲルズ) Cassandra Documentation: Understanding How These Concepts are Implemented(カサンドラ文書化:これらの概念がどのように実装されているかを理解する) 「Data-Intensive Applications Design」 by Martin Kleppmann - Chapter 5 on Replication(マルティン・クレップマン) 附属書:デザインの問題とアプローチ システム設計インタビューや実際のエンジニアリング作業で浮かぶ3つのオープンエンドの問題。 Problem 1: Conflict Resolution for a Collaborative Document Editor (コラボレーションドキュメントエディターの紛争解決) : あなたは、Dynamo スタイルのストアでサポートされている Google ドキュメントのようなものを構築しています。同じ段落を同時に 2 人のユーザーが編集しています。 The problem : ショッピングカート戦略(すべてのアイテムの統合)は、アイテムの追加が交代的であるためだけに安全である。 ユーザーAが文を削除し、ユーザーBが文の真ん中を編集する場合、その変更の連合は無意味または矛盾する。 Why shopping cart union doesn’t work here {A} ∪ {B} = {B} ∪ {A} The right approach: Operational Transformation (OT) or CRDTs 業界のソリューションは、文書をテキストのブロブとしてではなく、操作の順序として表現し、両方の手順を紛争なく適用できるように並行する手順を変換することです。 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. Dynamo 層の紛争解決戦略は以下の通りです。 Store operations (not full document snapshots) as the value for each key. Conflict では、各バージョンのすべての同時操作リストを収集します。 OT を適用して、それらを 1 つの一貫した操作ログに統合します。 合併したロゴを文脈として合併したベクトル時計で書き戻します。 : 表示されたテキストではなく、ドキュメントセグメントあたりの操作ログです. This makes merges deterministic and lossless. What to store in Dynamo : This is essentially how Google Docs, Notion, and Figma work. Their storage layers use either OT or a variant of CRDTs (Conflict-free Replicated Data Types), which are data structures mathematically guaranteed to merge without conflicts regardless of operation ordering. Real-world reference 問題2:異なる用例のためのN、R、Wを選択する : (a) セッションストア、 (b) 製品カタログ、 (c) ユーザー プロフィールのためのどの構成を選択しますか? The problem これについて考える正しい方法は、より費用がかかるエラーモードを特定する - 失われた書き出し(データ喪失)または拒否された書き出し(不利用性)。 Session store — prioritize availability Sessions are temporary and user-specific. If a user's session is briefly stale or lost, they get logged out and log in again. That's annoying but not catastrophic. You never want to reject a session write. ユーザーのセッションが短期間に停止または失われた場合、彼らはログアウトされ、再びログアウトされます。 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 製品データはめったに書かれていませんが(OPSチームによって)毎日何百万回も読みます。 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 プロフィールデータ(名前、電子メール、好み)は適度に重要です. 固定されたプロフィールは不便ですが危険ではありません. 拒否された更新(例えば、ユーザーが電子メールを更新できない)は本当の問題です。 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) Max 可用性 1 1 セッション, ephemeral state, click tracking バランス 2 2 ユーザープロフィール、好み、ソフト状態 連続読書 2 3 カタログ、config、稀に書かれた参照データ 最高の一貫性 3 3 どこでも R+W > N を必要とし、ゼロの許容性で静止した読み出し(まだ線形化できない) 問題3: Partition Scenarios で Dynamo-Style システムをテストする : ノードが故障し、パーティションが発生した場合、システムが実際に正しく動作することを確認するにはどうすればよいですか? The problem これは、分散システムテストにおける最も困難な問題の1つであるため、バグは、決定的に複製しにくい共通の出来事の特定のインターレベルのうちにのみ現れる。 Layer 1: Unit tests for the logic in isolation 分散行動をテストする前に、ビルドブロックを独立して検証してください. Vector clock comparison logic, conflict detection, and reconciliation functions can all be tested with pure unit tests — no networking needed. Vector clock comparison logic, conflict detection, and reconciliation functions can all be tested with pure unit tests. Vector clock comparison logic, conflict detection, and reconciliation functions can all be tested with pure unit tests. 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 負荷テスト中に失敗が正しい順序で起こることを期待するのではなく、それを意図的に繰り返し注入してください。 is a simple version of this. In production systems, libraries like または インフラレベルでやります。 node.down = True ジェフソン 混沌の猿 Key scenarios to test: 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 Instead of writing individual test cases, define 常に数千のランダム操作セクションを保持し、生成し、それらを侵害しようとする必要があります。 変容者 # 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). ツール like (Python) では、これらの変数を表現し、自動的に対例を見つけることができます。 仮説 Layer 4: Linearizability checkers 最大の信頼性を得るために、各操作の開始時間、終了時間、およびエラーインジェクションテストの結果を記録し、その後、ストーリーを線形化検査機に送信します。 それは、観測された履歴が正しい連続実行と一致しているかどうかをあなたに伝えるでしょう - 最終的に一貫したシステムでさえ、その保証範囲内で動作します。 キノコ 分散システムのトランチから書かれた. 戦闘でテストされた洞察, ゼロの手の波動。 ノートリンク ノートリンク
