「Dynamo: Amazon’s Highly Available Key-value Store」を読んだ
NoSQLの勉強をしていて、またDynamoDBを使う機会もあり、Dynamoの論文がNoSQLの原典的な存在らしく、1度読んでみたかったので読んだ。
全部理解できた訳ではないが、データ指向アプリケーションデザイン ―信頼性、拡張性、保守性の高い分散システム設計の原理やDatabase Internals: A Deep Dive into How Distributed Data Systems Work (English Edition)を以前読んだので、要点はまぁまぁ抑えれた気がする。
私はMySQLを使うことが多いので、コンフリクトを防ぐための書き込みのロック等は当たり前の存在だと思っていた。しかしDynamoは書き込みを優先させるために、読み込みの際にコンフリクトを解消するアプローチをしていて、技術で解決するとはこういうことかと思って面白かった。
他の方による日本語翻訳: Dynamo: Amazonの高可用性Key-value Store[和訳] · GitHub
気になったところのメモ
2. Background
2.1 System Assumptions and Requirements
ACID
ACIDを担保すると可用性が失われてしまうので、弱い一貫性(C)を提供し、分離性(I)も提供せず単一のキーのみの更新しか許可しない。
2.3 Design Considerations
RDBでは強一貫性を提供するために、同期的なレプリケーションを提供している。そのため可用性が落ちる。Dynamoでは、それを防ぐために結果整合性を持つように設計された。
それに伴って更新衝突を「いつ解決するのか、誰が解決するのか」という問題を解決しないといけない。RDBではwriteの実行中に解決してreadがシンプルになるように設計されている。そのため、writeのときにレプリカを更新しなければwriteは却下される。それに対して、Dynamoはwriteの可用性を優先させるために、readの段階で衝突解決を試みる。
「誰が解決するのか」という問題はデータストアかアプリケーションのどちらかになる。データストアはどれが正しいかを知るのは難しいため、last write winsのようなシンプルなポリシーになる。アプリケーション側での実装によって衝突をより適切に解決できる。
4. System Architecture
4.1 System Interface
getと putの2種類の命令のみをサポートする。シンプルなインターフェイスでkeyと関連づけられたオブジェクトをストアする。
4.2 Partitioning Algorithm
大容量のデータを扱えるように線形スケールしなければならない。そのため、ノード間の動的なパーティショニングができなければならない。コンシステント・ハッシングを採用して解決。
コンシステント・ハッシング
ノードの追加/削除の際に、隣接ノードのみに影響を留めることができる。
一般的なコンシステント・ハッシングの問題点としては、「各ノードのランダムな位置割り当てでは不均一なデータと負荷分散になってしまう」ことや、「ノードのパフォーマンスのばらつきが考慮されていない」ことが挙げられる。
それに対して、Dynamoでは「仮想ノード」の概念を使い、各ノードに1つ以上の「仮想ノード」を割り当てる。そうすることで、各ノードが環の複数の点に関連付けることができ、次のような利点がある。
- あるノードがダウンまたは削除されたら、このノードによって処理されていた負荷は残りの使用可能なノードに平等に分散できる
- ノードが復活したり追加されたら、新しいノードに対して他の使用可能なノードからおおよそ同じ量だけの負荷を受け入れられる
- ノードに割り当てられる仮想ノードの数は、その物理インフラのばらつきによるキャパシティから決定される
4.4 Data Versioning
Dynamoでは高い可用性を担保するためノード間で分断が起きたりして最新のアイテムが取得できない場合でも、書き込みを続ける。例えばカートの最新の状態が不明でも、カートの追加処理を行うなど。そうすると、複数のバージョンが発生してしまうが、アプリケーション側で適切に解決させる。
Dynamoではこの同一アイテムのバージョン管理のために vector clocksを導入している。 vector clocksはノードとカウンターのペアのリストである。書き込みの際には、どのバージョンに対して書き込むか（以前の読み込みの際の値）をコンテキストで指定させることで、バージョンの継承関係を管理する。読み込みの際にバージョンに衝突があった際は、すべてのありうるバージョンを返して、リコンサイルさせて新しいバージョンを作る。
バージョンがあまりに多いとパフォーマンス上の問題となるので、上限値を設定して、古いバージョンは削除するようにしている。
4.6 Handling Failures: Hinted Handoff
Dynamoでは伝統的なquorumの手法ではなく、可用性や永続性を担保するために「緩やかなquorum」を採用している。あるノードがダウンしてしまったら、そのノードが保存すべきデータは、本来そのデータを割り当てられてはいない他のノードが一時的に保存し、ダウンしていたノードが復活したらそのデータを渡すことで、レプリカ数を減らさずに処理を続行できる。
また、Dynamoでは異なるデータセンター間で保存することで、データセンター全体の障害によるデータ消失を防いでいる。
4.7 Handling permanent failures: Replica synchronization
仮想ノードごとに異なるマークル木を管理することで、差分の検知と同期のパフォーマンスを向上させている。
5. Implementation
read repair
リクエストコーディネーターがノードからレスポンスを受け取った際に、古いデータだった場合、内部で非同期的にwriteリクエストを送って最新の状態にする。
6. Experiences & Lessons Learned
6.1 Balancing Performance and Durability
Dynamoは永続性の保証とパフォーマンスのトレードオフ機能を提供している。この最適化では、各ストレージノードはメインメモリ内にオブジェクトバッファを保持する。各writeオペレーションをバッファに保存し、別のthreadで定期的にストレージに書き込む。read命令の際には、まず最初に要求されたキーがバッファに存在するかどうかを調べる。もしあれば、バッファから直接readする。
この手法では、バッファ中のwriteの書き込みが実行される前にサーバがダウンするとデータロストが発生しうる。そのリスクを軽減させるために、writeオペレーションはNレプリカのうちから durable writeを行うコーディネーターを持つように改良されている。コーディネーターはW個のレスポンスだけ待つので、 durable writeオペレーションのパフォーマンスの影響を受けない。
6.3 Divergent Versions: When and How Many?
データ管理には、アイテムのバージョンは最小限に抑えられた方がパフォーマンス的に良い。分岐は障害か、同じアイテムに対する大量の並列書き込みによって生じる。大量の並列書き込みは、通常ボットによるもので、ここでは詳細に触れない。
6.4 Client-driven or Server-driven Coordination
クライアントが、サーバ側のノード情報を取得して適切にノードへリクエストすることで、ロードバランサーが不要になり、また適切なノードへのリダイレクトする際のレイテンシーも節約できる。
6.5 Balancing background vs. foreground tasks
それぞれのノードはそれぞれの通常のフォアグラウンド put/get処理に加え、レプリカ同期やデータ受け渡しなど異なる種類のバックグラウンドタスクを実行しています。Admission controllerがフォアグラウンド処理の計測を行うことでリソースの可用性を評価して、バックグラウンド処理のスケジュール管理を行う。
