PNUTS: Yahoo!'s Hosted Data Serving Platform の Timeline Consistency

技術的なこと

ちょっと、J. Rao,E. J. Shekita, S. Tata"Using Paxos to Build a Scalable, Consistent, and Highly Available Datastore," VLDB(2011).というのを呼んでいたら、Timeline Consistencyなるものを発見した。うーん、Eventual Consistencyは聴いたことあるけど、はて？ということで、Timeline Consistencyの提唱元は、Yahooで開発されているPNUTSらしいので、ちょっと論文を読んでみることにする。

Timeline Consistencyは、以下に述べるWebアプリケーションの特徴から出てきた概念。Webアプリケーションは、一度にひとつのレコードを操作します、一方で別のレコードは地理的な意味でのローカリティが別なところにあったりする。(ちょっと、私の中ではつながらないけど、)レコード単位のTimeline Consistencyは、ある一つのレコードのすべての複製を考えたときに、このレコードに対する更新順序が全ての複製にも同じ順番で適用されるというもの。Eventual Consistencyは、更新の順番は保証されず、単に最終結果がおなじになるというものなので、そこが違う。

2.2節の図を見ると分かりやすい。レコードに対しての更新・削除・追加があった場合に、どんどんバージョンを上げていくイメージ。各レプリカも同じようにTimeline上でレコードが操作されている。だから、あとで述べるように今までにないような面白いクエリを考えることが可能。閑話休題、どうやって実装するかというと、レプリカの一つがまずマスタとなる。このマスタは、レコードごとに独立して用意される(注：GFSでいうところの、リースみたいなものですかね)。レコードに更新がかかると、まず、マスタへその更新要求が転送される。マスタとなるレプリカは、負荷に応じて変更される、例えば、とあるレコードの更新要求の大半を受け付けるレプリカは、そのレコードのマスターとなったりする。レコードの更新時には、インクリメントされる数字も付与される。レコードのバージョンは、v1.2のように表されて、1はinsertされてdeleteされるまで変わらない。2は、更新がかかるたびにインクリメントされう。1は、insertされるとインクリメント。1のことをgeneration。2のことをversionと呼んでいる。注意するべきことは、各レプリカがある時点で保持できるのは、ひとつのversionのみ。このように実装されるtimeline consistencyを利用すると、以下に述べるようなAPIを定義することが可能。

  • Read-any: 古いバージョンのレコードを返却する可能性がある。でも、Timeline Consistencyに従っていれば、古いだけで妥当なレコードとも言うことができる(これは、Dynamoのように、レコードにブランチができてしまって、あとでユーザがマージして、結局ある時に見たデータが完全に否定されることがないと言っているのだと思う)。注意点としては、このAPIはいわゆるserializabilityを全く提供できないこと、例えば、ある書き込みが成功したにも書かわらず、古いバージョンのレコードを返却するかもしれない。ただし、このAPIはこれから述べるAPIに比べれば圧倒的にレスポンスタイムが短くなる。このAPIは、Consistencyなんかよりも、レスポンスタイム重視のアプリケーションで利用出来る。例えば、ソーシャルネットワーク分野で、ユーザのログイン状態を表示することを考えると、最新の情報を得ることより、とりあえずの状況を返したほうがユーザビリティがよくなる。
  • Read-critical(required_version):クエリの入力値に、要求するバージョンを入れる。そうすると、そのバージョン以上のデータを返却する。例えば、書き込みをしたときに、少なくとも変更された値を読み込みたいというような利用法がある。writeするAPIは、バージョンを返却する。ので、その書きこみ以降の情報が見たいのであれば、このAPIが利用出来る。
  • Read-latest:全ての成功した書き込みを反映した最新のレコードを返却する。もしも、ローカルに存在するレプリカが古くて、リモートに存在するレプリカのロケーション解決が必要になれば、read-anyに比べれば、とっても遅い。
  • Write:このAPIは、トランザクションとしてひとつの書き込みを行います。例えば、ユーザプロファイルの書き換えなどに利用出来る。
  • Test-and-set-write(required_version):もしも、引数として与えられたバージョンが等しければ、書き込みを実行する。このAPIは、一度値を読み込んで、その値をもとにして変更を行うようなトランザクションに利用可能。test-and-setでは、二つの並行したトランザクションが必ず直列化することを保証します。

読むときには、アプリケーションによってconsistencyに幅があるんだということが分かった。ただ、Read-anyの例がちょっと弱い気がする。別に、Eventual Consistencyでも良くないか？と思った。