読者です 読者をやめる 読者になる 読者になる

"Cassandra - A Decentralized Structured Strage System" を読んだ

Cassandra(Apache Cassandra)はFacebookによって開発された分散データベース。
分散型のデータベースとしては、マスターが存在しない(単一障害点が存在しない)ことが大きな特徴。

データ構造

  • 検索は文字列であるキーで行う。
  • 行(row)は複数のカラム(column)から成る。
  • 行に対する操作はアトミックであることが保証されている。
  • カラムはcolumn familyと呼ばれるカラムの集合に分けられる。

データの分散

  • Consistent Hashingをもとにデータを分散させる。
  • 通常のConsistent Hashingだとデータの分散に偏りが生じる恐れがあるので、必要に応じてノードのハッシュ値を調整し、負荷をバランスさせる。

データの複製

  • データの複製の義務はConsistent Hashingによりキーを割り当てられたノードが負う。
  • アプリケーションは複製のポリシーを選択できる。("Rack Unaware"、"Rack Aware"、"Datacenter Aware")
  • "Rack Unaware"ポリシーの場合、Consistent Hashのリング上のN-1個前までのノードにデータを複製する。
  • "Rack Aware"ポリシーや"Datacenter Aware"ポリシーの場合、ZooKeeperによってクラスター中から一つリーダーを決定し、リーダーが複製先を決定する。
  • 複製先の情報はZooKeeperと複製の義務を負うノードのローカルディスクに保存される。
  • データセンターのダウンに耐えられるよう、データの複製は必ず複数のデータセンターにまたがるよう行われる。

起動

  • ノードは一番最初、起動時にConsistent Hashingのトークンを割り当てられる。
  • その後、この割り当て情報はクラスター上の他のノードへ伝えられ(gossipされ)る。
  • これにより、全てのノードは他のノードの情報を得ることができ、あるキーのリクエストが来た時そのリクエストを適切なノードに回すことができる。

ローカルでのデータ保持

  • データを書き込むときは、ノードはまずディスク中のcommit logにログを書き込み、それが成功してからメモリ中のデータ構造へ書き込みを行う。
  • メモリ中のデータ構造の容量がしきい値を超えた場合、それをディスクに書き出す。
  • これを繰り返すと、ファイルが複数できるので時折複数のファイルを一つのファイルにまとめる処理を行う。
  • データを読み込むときは、まずメモリ中に要求するデータがあるか確認し、なかったらディスクを見に行く。
  • ディスクを見に行くときは、ディスクをみる前にメモリ中のbloom filterでデータの存在を確認してから見に行く。

Consistent Hashingって初めて知ったけど、面白い。
結構簡単に実装できそうなので実装してみたい。

(一貫性を保つため、)読み込み、書き込みに際して、合議を取るっぽいことがさらっと書いてあったけど、あそこら辺もっと踏み込んで欲しかったな。

ZooKeeperってよく聞くけど、どういうソフトウェアなのかいまいち理解してない。
Gissip Protocolもちゃんと勉強した方が良さげ。