Object Storage on CRAQ: High-throughput chain replication for read-mostly workloads

技術的なこと

何から、これを見てみたいと思ったか忘れたけど、Object Storage on CRAQ - USENIX 2009 - Part 1/3 - YouTubeにビデオ見てみたので、その時のメモ

背景
  • Eventual Consistencyはスループットが出せるが、アプリ開発者はこれまでと違うプログラミングを強いられる。
  • 2フェーズコミットは、強い一貫性を担保してくれるのでプログラミングは楽だけど、スケールしない。
  • ということで、スケールしつつもプログラミングしやすい手法を提案のが目標
Chain Replicationtという技術(OSDI2004で出ているみたい)

うーん、プレゼンが微妙にピンぼけしていて見づらいなあ。

  • ２フェーズコミットだとコーディネータが必要だが、レプリカを管理するプロセスをチェインとして並べて、ライト要求があったときには、そのチェインに従って、ライト要求を渡す。最期まで行くと今度は、Ackの連鎖をしていく。この時、コミットされていない情報を読み込ませないことで、強い一貫性を担保するみたい。
  • 良い点：強い一貫性、レプリカ作成処理が単純、ライトスループットがよく出る。
  • 悪い点：読み込みスループットが出ない。
  • あと、大抵の場合リード要求のほうが多いR:W=100:1ので、ライト
CRAQの提案
  • ２つの状態、cleanとdirtyをもつ。
    • cleanの場合、全てのレプリカは同じバージョン番号を持っている。この時にリードされた場合、値が返却される。
    • チェインは、headからtailに向けて更新要求が連鎖していく。tailに届く前の状態のライト要求を行っている場合、dirty状態が発生する。dirty状態が発生した場合に、リード要求があると、そのプロセスはtailに聴きにいって現状のバージョン番号iを聞く。ユーザには、iのバージョンの値を返却。tailでコミットされた場合、新しいバージョンが返却されるので強い一貫性を保つことがでいる。
    • なるほど、read committedレベルの一貫性を保証している感じかな。というか、key-valueストアならそれで十分か。
  • マルチキャストを利用した最適化
    • 強い一貫性は保証されるが、ライトのコミットレスポンスタイムは、チェインで情報をやりとりするから劣化する。そのため、マルチキャストを利用した最適化を行う。
    • tailからackを返却するときにマルチキャストで全員に、ackを返却。
    • headから大きなデータを更新するときには、まず、マルチキャストでデータだけ一気に転送する。もし1MBをチェインで送るとレスポンスタイムがかなり悪化するから。データを送った後で、小さいコミット用プロトコルだけチェイン間でやりとりする。
複数ロケーションでのCRAQを利用する話
  • 各ロケーションには、CRAQクラスタがあって、クラスタ間は、ネットワークで繋がっている。
    • まあ、いろいろな観点があるよねということだけ述べている。
実装
  • C++で3000line。Zookeeper利用。というか、かなり小さいな。
    • Zookeeperは、データセンタ間でノードの情報を共有するために利用している。各クラスタにひとつZookeeperがいるということ。
  • Tame extentionというライブラリを使っているらしい。
  • RPCは、Sun RPC (XDRとかのことかな？)。
  • ライブラリをうまく使うことで、かなりコード量を削減している様子。C++でもやり方が上手ければ、サクっと作れるということかな。
結果

まあ、いいや、だいたい分かった気がするので、ここまで。