Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Summary of "Dynamo: Amazon’s Highly Available K...

Summary of "Dynamo: Amazon’s Highly Available Key-value Store"

- "Designing Data-Intensive Applications"
- ACID
- BASE
- Replication
- Partitioning
- Consistent Hashing
- Vector Clocks
- Sloppy Quorum & hinted handoffs
- the Merkle Trees
- Gossip-based membership protocols

Ken Wagatsuma

January 18, 2019
Tweet

More Decks by Ken Wagatsuma

Other Decks in Programming

Transcript

  1. “Data-Intensive Application” - data-intensive vs compute-intensive - the complexity of

    data is bottleneck - e.g. database, cache, search index, stream/batch processing
  2. Image Area Image Area Image Area 信頼性 ハードの故障 ソフトの故障 人為的ミス

    拡張性 高負荷 高パフォーマンス 高トラフィック 保守性 運用 エラー検知 自己修復 3 Key Factors when Designing Data-Intensive Applications Reliability Scalability Maintainabi lity
  3. From “ACID” to “BASE” - ACID - Atomicity(原子性) - Consistency(一貫性)

    - Isolation(独立性) - Durability(永続性) - BASE - Basically Available(基本的可用性) - 「殆どの場合、機能性は損なわれずに使える」 - Soft state(柔軟な状態変化) - 「システムの状態は頻繁に変わりうる、そしてそれを許容する」 - Eventual consistency(結果整合性) - 「最終的に整合性が取れていれば、一時的に不整合な状態も許容する」
  4. But, how? - Replication - single-leader/multi-leader/leaderless - synchronous/asynchronous/semi-synchronous - Partitioning

    - secondary indexes - rebalancing/request-routing - Transactions - two-phase locking/predicate locks/index range locks - MVCC (multi-version concurrency control) - Consensus - quorum/membership services
  5. “Dynamo: Amazon’s Highly Available KVS” - Amazon において高可用性・拡張性を兼ね備え た分散 KVS

    として開発 - ショッピングカート機能のバックエンドなどに利用 - AWS DynamoDB は、Dynamo をもとに開発され た AWS のサービス
  6. Problems Problem Why? Partitioning 世界中の複数リージョンでデータを分散させたい High Availability for Writes ショッピングカートの性質上、書き込みは必ず成功させたい(ユー

    ザーに何度も購買ボタンをクリックさせたくない) Handling temporary failures 一時的にノードが死んでも、いい感じに複製したい Recovering from permanent failures 完全にノードが死んでも、システム全体で可用性を保ちたい Membership & failure detection 中央集権サーバーを持たずに、障害を検知したい
  7. Features Problem Technique Why? Partitioning Consistent Hashing 徐々に scale-in/scale-out できる拡

    張性を担保する High Availability for Writes Vector clocks with reconciliation during reads 書き込みを必ず保証し、結果整合性 を保証する Handling temporary failures Sloppy Quorum & hinted handoff 一部のノードが死んでもシステム全 体の機能性を確保する Recovering from permanent failures Anti-entropy using Merkle trees バックグラウンドでデータを複製する Membership & failure detection Gossip-based membership protocol 中央集権サーバー不要で各ノード の障害検知をする(P2P-like)
  8. When Node Added... nodeX nodeY nodeW a a b b

    c d d e e f f g g h h nodeU c
  9. Virtual Node nodeX nodeY nodeW a a b b c

    d d e e f f g g h h nodeU c VNodeW
  10. Vector Clocks (a.k.a. Version Vectors) - Eventual Consistency な Dynamo

    では、オブジェクトを Versioning すること によって各変更を保存しておく - このとき、オブジェクト間の因果律(変更の原因と結果)をもとに、最終的には あるべき状態になるように各 Version の変更を適用していく手法が、Vector Clocks
  11. Vector Clocks nodeX nodeY nodeX nodeY α:1 β:0 γ:0 α:2

    β:0 γ:0 α:0 β:1 γ:0 α:2 β:1 γ:0 α:2 β:1 γ:0
  12. Sloppy Quorum and hinted handoff - Sloppy Quorumm = “いいかげんな”クォーラム

    - 書き込みの可用性を高めるために使われる - ネットワークが疎通されていなくても、ローカルのストレージに書き込みをして「成 功」とみなす。ネットワークが再開されたら、 hinted handoff を付与して他のノード に書き込み済みのオブジェクト情報を送信する - hinted handoff = ヒント付き引き継ぎ - ネットワークが疎通されていたら、ローカルに書き込まれているオブジェクトは本 来どのノードに渡されていたかを記録しておくメタデータみたいなもの
  13. Dynamo and Merkle trees - “To detect the inconsistencies between

    replicas faster and and to minimize the amount of transferred data, Dynamo uses Merkle tree” - [Pros] Hash 値だけ検証すればいいので、レプリカ間の整合性チェック がデータ全体を比較するよりも速い - [Pros] Hash 値だけを転送すればいいので、ネットワーク転送効率も高 い
  14. How Dynamo uses Merkle trees for anti-entropy 1. Each node

    maintains a separate Merkle tree for each key range 2. Two nodes exchange the root of the Merkle tree (corresponding to the key ranges that they host in common) 3. Traverse the tree and find if there are any differences 4. If any differences found, start replication