工場長のブログ

日々思ったことを書いてます。

AmazonのDynamoの論文を読んでみた(1/3)

NoSQL Amazon

Amazonが社内で開発し、サービスで利用しているDynamoというストレージサービスがあるのだけど、これについての論文が公開されていたので読んだのでまとめてみる。

この論文を書いたメンバーにはAmazonのCTOであるWerner Vogelsや、AWSでDynamoDBやElastiCache、SQS、SNSなどの製品のマネージメントをしているSwami Sivasubramanianらが含まれている。

Dynamoをひとことで表すと分散型でKey Valueストレージで、データの一貫性に関しては結果整合性を保証するサービスだ。なお、AWSで提供されているDynamoDBとは別物なので注意。

原文はこちらから参照できる。今回のポスト中の引用(図や文問わず)はすべてこちらから引用している。
また、既に日本語訳をされている方もいらっしゃるので原文をそのまま日本語でよみたい人はこちらを参照のこと！


論文は以下の7つのパートに分かれているのだが、結構長いので今回は3章まで読んでのまとめにする。
たぶん、全部で3回くらいになりそう。

1. Abstract(概要)
2. Background(経緯)
3. Related Work(参考にしたシステムやサービス)
4. System Architecture(アーキテクチャ)
5. Implementation(実装)
6. Experiences & Lessons Learned(開発や運用を経てのラーニング)
7. Conclusions(結論)

ここから今回のポストの本編。長くなるので先にまとめを書いておく。

先にまとめ

  • コンセプトをひとことでいうと100%書き込み可能でスケーラブルな分散型NoSQL。
  • DynamoはAmazonの一部のサービスで利用するために開発された。リレーショナルデータベースは使ってきたしこれからも使っていくが、「可用性が必要でデータへのアクセスがキーバリューで要件が満たせるところ」に利用されている。
  • Dynamoのゴールは"高い拡張性"、"高い可用性"、"低い運用負荷"の3点を満たすことにある。CAPの定理でいうと、A(可用性)とP(分断耐性)に重点を起き、C(一貫性)を諦めている。これにS(拡張性)を足したもの、というイメージ。ACID特性に関して言うとAtomicとIsolationは明示的に要件から除外されている
  • アーキテクチャとしては分散ハッシュテーブル型のP2Pネットワークの上に構築されており、攻撃などを想定せずにすむ、ひとつの閉じたネットワーク上に配置されることを前提としている。

ここから先は論文に沿って読みながら解説しながらという感じ。

1. Abstract

Dynamoは"Always-on"のユーザー体験を実現するためにいくつかのアマゾンのコアサービスでも利用されている。このサービスレベルを実現するために、Dynamoは様々な障害が起こることを前提において、そのなかで一貫性を保ったサービスを提供できるように設計されている。

ご存知のとおりAmazonは世界中で多数のユーザーに利用されているので信頼性や拡張性がとても重要なシステム要件になっているという話。AWSでもそうなんだけど、障害率を下げようというアプローチではなく、障害が起こることを前提に、障害に強いアーキテクチャをデザインしようというコンセプトがDynamoでも採用されている。そのために、中心となるマスタサーバーなどをもたずに、互いに対称で同等な責任をもつサーバー群から構成される疎結合なシステムデザインに重点をおいている。

また、Dynamoはデータアクセスインターフェイスとしてキーバリューアクセスのみを提供している。Amazonでも多数のリレーショナルデータベースを利用しているが、いっぽう、多数のシステム（例えばベストセラーリスト、ショッピングカート、ユーザー設定、セッション管理、売り上げランキングなど）はキーバリューアクセスのみでシステムを実現できるものもあり、こういったところがDynamoのターゲット。決してRDBの置き換えをしようという話ではない。

Dynamoが目指すのは"高い拡張性"と"高い可用性"、"最小限の管理コスト"の3点であり、これらを実現するために採用している技術をサマリすると以下のとおり。

  • コンシステントハッシングによるデータパーティショニング
  • オブジェクトのバージョニングによる一貫性/整合性の保証
  • 分散ノード間での対称なレプリカ同期とsloppy(薄い) quorumによる一貫性/整合性の保証
  • gossipベースのノード探索/障害検知

2. Background

2.1. 前提条件とシステム要件

クエリモデル

ユニークなキーで識別されるオブジェクトへのreadオペレーションとwriteオペレーションを提供する。複数のオブジェクトをまたがるクエリやリレーションは提供されない。オブジェクトはバイナリで保存され、それぞれのサイズは1MB以内を想定する。

ACID特性について

Dynamoは高い可用性を実現するため、強一貫性ではなく、結果整合性の保証を提供している。また、一切の独立性・分離性を持ったトランザクションは提供せず、一度にひとつのキーのアップデートのみを許可する。

環境

Dynamoはコモディティハードウェアの上で動くこと、攻撃などを想定せずにすむ、ひとつの閉じたネットワーク環境の上で動作させることを前提とする。

2.2 SLA

Amazonのサービス志向インフラストラクチャの中ではSLAが非常に重要な役割を持つ。なぜならAmazonでは例えば1つのページをレンダリングするために複数階層で150以上のサービスへのリクエストが実行されることがあるためだ。下記の図は1つのWebページリクエストに対して様々なサブシステムへのリクエストが発生する様子を表している。そしてそれぞれのサブシステムがSLAを持ち、それを守っていれば、最終的にページレンダリングがユーザーに対して十分によい経験として提供される、という話。

f:id:imai-factory:20131103214759p:plain

AmazonのSLAの特徴としては、一般的にはSLAには平均値や中間値を利用することが多いが、そうではなくパーセンタイルを採用していることがある。このほうがより多くのユーザーに対して高い満足度を提供することになる。（これは勉強になる。今後はそういう考え方を取り入れていこうとおもった。）

2.3 設計のポイント

一般的なリレーショナルデータベースのデータレプリケーションの多くは同期型のものであった。しかし、この方式ではネットワークの問題が起こるとデータが利用不能になってしまう。これは、一貫性を保つためにすべてのレプリカを比較・検証し、データが完全であることを確認しなければならなかったりするためだ。こういった事情から、強一貫性と高可用性は同時には実現できない。サーバーやネットワークの障害が起こりうる環境では楽観的レプリケーションを利用したほうが可用性をあげやすいが、データのコンフリクトが発生するのでこれを発見して修正する必要が出てくる。

前述のとおりDynamoは結果整合性型なのでこのコンフリクトの問題を解決してやる必要がある。論文では”いつ”、”誰が”これをやるのかを決めるのが重要だと書いている。

まず、”いつ”についてだが、これまでの多くのシステムではデータ書き込み時にこの処理を行っていたという話。これは読み込み処理をシンプルに保つためにこういった方式が取られてきたとのこと。しかしDynamoは前述のとおり"Always Writable"であることが重要なので、逆に読み込み時にこの処理を行うことにより、書き込み処理をシンプルにしている。結果として、ネットワーク障害やサーバー障害が起こった際にも、ユーザーが商品をカートに入れられないような事態が発生しないようになっているらしい。

次に"誰が"の話。これには「アプリケーション」もしくは「データストア（システム）」の2つの選択肢がある。データストアにこれを行わせる場合、Last Write Winsなどの非常に単純な方式しか選択することができない。一方、アプリケーション側でこれをハンドリングするのであれば多くのロジックの選択肢を持つことができるが、これを実装するのを好まない開発者は多く、Last Write Winsが採用されているケースが多く見られるとのこと。まあ確かにアプリケーションエンジニアは手間が増えるので嫌がるだろうし、データストアというかシステムの中に、このロジックを隠蔽してほしいよねという気持ちはすごくわかる気がする。ちなみにDynamoでは、後半の章に出てくるが、基本的にはDynamo側で解決するが、どうしても解決できないようなときは強制的にシステム側で一定の条件に沿って決めてしまうか、アプリケーション側に委ねるかを選ぶことができるようになっている模様。

その他の重要な技術的ファクターは以下のとおり。

継続的な拡張性

Dynamoは既存のシステムやシステム内のノードへの影響を最小限に抑えながらストレージノードの追加ができる必要がある。

対称性

Dynamoのシステム内のすべてのノードは等しい責任を持つ。特別な役割や責任を持ったノードを持つとシステムは複雑化する。

中心のないアーキテクチャ

対称性を持ったシステムを更に突き詰め、中心をもたないP2Pベースのアーキテクチャを目指す。中心を持つことは耐障害性を下げる。逆に中心がないことにより、システムはよりシンプルで可用性の高い、拡張性の高いものとなる。

不均質性

システムを構成する各サーバーはスペックが必ずしも一致していなくても問題なく動作できること。

3. Related Work(参考にしたシステムやサービス)

拡張性と可用性を併せ持つ分散型ストレージ・システムをデザインする上で参考にしたシステムなどが紹介されている。比較の観点としては

  • IPネットワークの上に、システムを構成するためのオーバーレイ・ネットワークをどう構築するか
  • そのネットワーク上でどうやってストレージシステムを構築するか
  • 分散されたノード間でのレプリカの共有や一貫性の保持方法

などに基いて比較・検討されている。結構、知らないシステムやミドルウェアなどがたくさんでてきて面白かった。

P2Pネットワーク

  • Gnutella(http://rfc-gnutella.sourceforge.net/index.html), Freenet (https://freenetproject.org/)
    • これらは非構造型P2PネットワークやPure P2Pネットワークと呼ばれ、ピア同士で任意にリンクが構成される。非構造型なので探索クエリはネットワーク中にフラッディングされる。Gnutellaなつかしい・・・、これが流行った当時、P2Pという言葉を聞くのが初めてだったなぁ。
  • Pastry(http://www.freepastry.org/), Chord(https://github.com/sit/dht/wiki)
    • これらは構造型P2Pネットワークや分散ハッシュテーブル型のネットワークと呼ばれ、Pastryã‚„Chordと言ったアルゴリズムは限られたhop数で目的のノードに到達できることを保証している。ちゃんとアーキテクチャとか確認していないけど、それぞれのノード、もしくはマスタノードがネットワークのトポロジを管理している形式。IPのルーティングのようなイメージ。前述のPure P2Pネットワークよりも高いネットワーク効率が期待できる。

P2Pストレージ

  • Ocenstore (http://oceanstore.cs.berkeley.edu/)
    • 多数の複製されて多重化されたデータに対してシリアルなアップデートをサポートするトランザクショナルで永続的なストレージサービス。Oceanstoreは多数の並列書き込みによる発生するコンフリクトを解決するために、それぞれの書き込みに対する統一的な順序付けを利用していて、システムは非構造型P2Pネットワーク上に構成される。
  • PAST (http://research.microsoft.com/en-us/um/people/antr/PAST/)
    • 対してPASTは構造型P2PネットワークであるPastry上に構成され、オブジェクトを変更不可能な形で保存するらしい。どうやらマイクロソフトのプロジェクトの模様。前述のとおりオブジェクトは変更不可なので、アプリケーションやライブラリ側でオブジェクトのバージョニングによるファイルの更新っぽいものを実装して使う前提のものらしい。

3.2 分散ファイルシステムと分散データベース

P2Pストレージシステムでは基本的にはフラットなネームスペースしかサポートされないのに対し、典型的な分散ファイルシステムは階層型のネームスペースをサポートする。

これらのシステムのうち、BayouとCodaそしてFicusはネットワークパーティションやネットワーク障害への耐性を備えている。CodaとFicusはシステム側でのコンフリクト解決を図り、Bayouはアプリケーション側でのコンフリクト解決を図る設計になっており、それぞれ方式は異なるが結果整合性を保証している。Dynamoもこれらと同様にネットワークに関連する問題への耐性を備える。

  • FAB(http://web.mit.edu/prentice/PUBLIC_OLD/6.824/papers/FAB04.pdf)
    • この分散ブロックストレージは大きなファイルを複数の小さなオブジェクトに分割する。こういったケースにおいてはKey Valuesストアは元々比較的小さなオブジェクトを保存するように意図されているので有利らしい。ちなみにこれの開発には日本の方が携わっている模様。HPのプロジェクト？
  • Antiquity(http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.165.1416)
    • Antiquityは広域分散型のストレージシステムであり、レプリカやサーバーが信頼出来ることを確認するためにセキュアログという仕組みが組み込まれているらしい。が、Dynamoはこういった方式は採用していない。なぜなら、信頼出来るネットワーク内に構築されることを前提としているから。2007年って結構新しい。
  • Bigtable(http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/ja//archive/bigtable-osdi06.pdf)
    • sparseなソート済み多次元マップを格納し、アプリケーションに対して多様なアトリビュートを利用したデータアクセスを提供する。と書かれると難しいけど、いわゆる分散型のNoSQL。HBaseの開発時に参考にしているらしい。GFS -> HDFS, MapReduce -> Hadoopに加えてBigtable -> HBaseを整理するとわかりやすいかも。前述のとおりかなり柔軟なクエリができるようになっているのが特徴。対してDynamoは高可用性とAlways Wrirtableに主眼をおいているのと、もともとKVS的な要件のアプリを前提に考えられているのでKey Valueアクセスのみを提供する。
  • リレーショナルデータベース
    • トラディショナルなリレーショナルデータベースは強い一貫性をもち、プログラマに対して非常に明快で簡潔なプログラミングモデルを提供してくれるけど、拡張性と可用性の面で劣る。これらのシステムは強一貫性を提供するために可用性やネットワークパーティションへの耐性を犠牲にしている。実際、例えばMySQLを振り返ってみると、そもそも1台構成だと可用性が落ちるし、シャーディングしたとしてもそれぞれの責任範囲が別になっているのでネットワークパーティションへの耐性も低い。そのかわりトランザクショナルだしデータの整合性を気にしなくていいよね。ACID！

3.3. Discussion

ここまでに出てきた、Dynamoのデザイン要件をまとめると下記の5つ。

  • Always Writableであること。並列書き込みに対してもすべての書き込みを受け付けること。
  • 信頼出来るネットワーク内にシステムが構成されること
  • 複雑なスキーマは提供せず、Key Valueアクセスのみを提供すること
  • アクセスの99.9%に対し数百ms以内の低いレイテンシでレスポンスを提供すること
    • ちなみにこの項目でちょっと面白いことが書いてあったのだけど、"DynamoはZero-hopな分散ハッシュテーブル型ストレージと言っていい"と書いてあった。実際この後の章で述べられているのだけど、各ノードが等しい役割を持ち、オブジェクトのロケーションへの直接のルーティング情報を保持するアーキテクチャになっている。

マスタサーバーなどを持つと可用性が低くなるしシステムも複雑になるので各ノードが等しい責任範囲をもつ自律型のP2Pシステムにしたい。しかし非構造型のP2Pではデータの位置が保証されないので、データアクセスレイテンシが保証できないので構造型のP2P(分散ハッシュテーブル型)を採用しよう、という流れでいまのアーキテクチャに辿り着いたのではないかなと想像。


長くなってきたので今日のポストはここまで。
このあとはSystem ArchitectureやImplementationなど、実際のDynamoのデザインや実装の話に入っていくお。
たとえば以下のような話に言及して行く予定。

課題 採用技術 利点
データパーティショニング コンシステントハッシング 継続的拡張性
書き込み可用性 ベクタークロックと読み込み時のコンフリクト解決 バージョニングによるデータサイズ増大の抑制
一時的な問題のハンドリング Sloppy(薄い) Quorumとヒント付きハンドオーバー 一部のノードやネットワーク断が起こった際の耐障害性
永続的な問題のハンドリング マークル木を利用したアンチエントロピーの実現 発散するレプリカをバックグラウンドで同期できる
メンバーノードの探索/発見や障害検知 gossipベースのメンバー検知、障害検知プロトコル 中心のないアーキテクチャの実現とノード情報の交換

という感じで中身の話にはいっていきます。
お楽しみに！