Cassandra - A Decentralized Structured Storage System を読んだ

Cassandra - A Decentralized Structured Storage Systemを読んだ時のメモ。

どんなもの？

分散ストレージシステム
大規模データを多数の一般的なサーバに分散させることで可用性を高めて、SPOFを無くす
ソフトウェア側で可用性とスケーラビリティをコントロールしている
read efficiencyを犠牲にすることなくwrite throughputを高めている
FacebookのInbox Searchのストレージのニーズを満たすために作られた

先行研究とくらべて何がすごい？

Scale Incrementaly
低latencyでかつ、writeのスループットが高い

技術や手法の肝は？

DataModel
- Table
  - 1つのkeyでindexされた多次元マップ
  - valueは高度に構造化されたobject
  - row keyはsize limitのないstring(16~36byte)
  - 1つのrow key下での全ての操作はどれだけ多くのカラムが読み書きされていようがレプリカ単位でatomic
  - カラムはカラムファミリと呼ばれる単位でグルーピングされる
  - カラムを時間もしくは名前でソートできる
API
- insert(table,key,rowMutation)
- get(table,key,columnName)
- delete(table,key,columnName)
System Architecture
- Partitioning
  - scale incrementaly(線形にスケールすること？)が設計のキー
    - クラスタ内のNodeをまたいで動的にデータをパーティショニングする必要がある
  - consistent hashingを利用
    - Dynamoとは異なり、リング状の負荷情報を解析して負荷を軽減させるために、負荷の軽いノードを移動させる
      - 設計と実装がシンプルになった
Replication
- Coordinator Nodeにk個のkeyが割り当てられ、それをN-1個のホストにレプリケーションする
  - Rack Unaware, Rack Aware, Datacenter Awareなどのpolicyがある
- zookeeperを用いてリーダーの選出を行う
- リーダがどのレンジをレプリケートするかを伝える
- どのノードがどのレンジを受け持つかのメタデータは、各ノードのlocalとzookeeper内にキャッシュされる
- 全てのノードは他のノードのことを知っている
Membership
- anti-entropy Gossip base protocolにもとづいている
Failure Detection
- Φ Accrual Failure Detectorを修正したものを使っている
  - ノードの生死をboolean値で送るのではなく、suspection levelを送る
    - Φ=1の時に我々が間違っている尤度は約10%
Bootstrapping
- ノードが起動するときにリング上の自分の位置に関するランダムトークンを選択する
  - このmappingは耐障害性のためにlocalとzookeeperにも保存される
- トークン情報はcluster中に伝搬されていく
  - 我々が全ノードとそれらのリング上での位置を知る方法
  - どのノードでもキーのリクエストを正しいノードにルーティングできるようにする
Scaling the Cluster
- 新しいノードは負荷の高いノードの負荷を軽減するトークンが割り当てられる
  - 他のノードが担当していたレンジを新しいノードが分割して担当するということ
Local Persisitence
- 典型的なwrite
  - 永続性とリカバリのためにcommit logに書き込みが成功した後、in memoryのデータを更新する
  - commit logの書き込みはシーケンシャルなので、diskのthroughputを最大化させるために専用のdiskを使っている
  - in memoryのデータが一定の閾値を超えた時に、diskにダンプされる
  - ファイルがdiskに沢山存在するように成るので、バックグラウンドでマージ処理が走る
    - Bigtableのcompactionと似ている
- 典型的なread
  - disk上のファイルを探す前にin memoryのデータから探す
  - 新しいものから古いものへと順に検索される
  - disk上の複数のファイルから探すことになったときのために、bloom filterがデータとともに保存されており、in memoryにも存在する
  - disk上の全てのカラムをスキャンすることを避けるために、カラムインデックスを保持する