akka-crdt

  • Jonas Boner氏(Typesafe CTO、Akkaの作者)が一ヶ月くらい前に公開
  • Boner氏はAkka専門だし、忙しいからあまりコード書いていないのでは?
  • というわけで興味を持った

CRDTとは?

  • 分散データの更新と一貫性の話
  • Convergent and Commutative Replicated Data Types
  • 直訳すると「収束する、または、可換な複製されたデータ型」
  • 2009年ころからINRIAからいくつか論文が出ている

CAP定理

  • Consistency (一貫性)、Availability (可用性)、Partition-tolerance (分断耐性)
  • この三つのうち、二つしか同時に保証することができないという話
  • 近年のNoSQLブームを支えた理論で、良くも悪くも色々言われているが、深くは立ち入らない
  • AとPを優先しCをどう解決するかという前提は同じ

ACID vs BASE

  • ACIDはAtomicity (原子性)、Consistency (一貫性)、Isolation (独立性)、Durability (永続性)の略
  • ACIDはDBMSのトランザクションが持つべき性質
  • BASEはBasically Available (基本的に可用性がある)、Soft-state (柔らかい状態)、Eventual consistency (結果整合性)
  • 分散システムではACIDが難しいからBASEで行こうという話が3、4年前に流行ったらしい

Eventual consistency

  • Strong consistency(更新された直後の値を読んだら更新された値が返ってくる)は分散システムでは難しい
  • Eventual consistencyでは更新されて、ある程度の時間(inconsistency windowと呼ぶ)が過ぎた後では整合性が保証される
  • ばらばらに分散されたノードで更新されたデータの整合性をどう取るのか
  • その解法の一つがCRDT

CvRDTとCmRDT

  • CvRDT: Convergent Replicated Data Types
  • CmRDT: Commutative Replicated Data Types
  • CvRDTは状態ベース、CmRDTは操作ベース

CvRDT: Convergent Replicated Data Types

  • 分散された状態をマージしたいけど、何も考えないとコンフリクトする
  • 状態とマージの性質を半束(semi-lattice)で定義する
  • 半束は任意の二つの要素に対して最小上界(least upper bound)が必ずある半順序集合
  • 最小上界を求める演算(join)をマージとする
  • joinの例: 部分集合の集合上の和、自然数上のmaxなど
  • 結果として状態を単調増加(monotonic)なものにする
  • たとえば数値の増減でも足し算と引き算に分けることで単調増加なものにできる

CvRDTの例: Grow-only counter

  • Facebookのいいね!のようなカウンタ(いいね!は減りもするけど)
  • AとBの二つのノードがある
  • カウンタの数字はAとBで別々に管理する
  • マージ処理はノードごとに数値のmaxをとる
  • { A: 10, B: 5 }と{ A: 8, B: 7 }をマージすると{ A: 10, B: 7 }になる
  • 一般的にノードはどんどん増えるので状態が肥大化するという問題がある

CmRDT: Commutative Replicated Data Types

  • CmRDTでは状態の更新(操作)をブロードキャストする
  • 届いた操作の時系列は保証されないので、操作は可換(Commutative)でなければならない
  • CvRDTに比べて状態の肥大化は起きない
  • しかしノード間の通信は信頼できるものでなければならない

CRDTの性質

  • CRDTのデータ構造を組み合わせたものもCRDTである
  • CvRDTとCmRDTは本質的に同じ(互いをエミュレートできる)

CRDTのデータ構造

  • G-Counter
  • PN-Counter
  • G-Set
  • 2P-Set
  • 他にも色々グラフなどもある

akka-crdt

  • 今のところCvRDTのみの実装、CmRDTはまだ
  • 実装されているデータ構造はG-Counter、PN-Counter、G-Set、2P-Set
  • Akka Clusterを使っている(ノードの追加削除などの管理をしてくれる)
  • Multi Nodeテストがsbt-multi-jvmを使っていて面白い

<Thank You!>