mmag

ハマったことメモなど

Vector ClockとCRDTについて調べた

CS Elixir

昨日 Vector ClockとCRDTsについて調べてるけどまだ上手く説明できない と泣き言を言った後、調べてなんとか書きました。actorの気持ちにはあんまりなってません。

言葉や概念の正確さが不安なので、詳しい方にぜひご教授頂きたいです。

Phoenix.Presence

Channelのトピックにプロセスの情報を登録でき、それをクラスタ内のノードにレプリケーションできる仕組み。 動画では、トピックへの接続者の一覧を表示する機能に使用されていた。

  • 単一障害点が無い
  • Single Source of Truthが無い
  • セルフヒーリング

という特徴がある。鍵となる技術として、CRDT(ORSWOT)があるとのことなので今回CRDTについて調べている。dockyardのブログに作者が記事を書いている[1]。

問題

ノードn1, n2, n3でクラスタを組んでいるとする。n1にuser1が接続してきて、それを他のノードに同期する。

f:id:Joe_noh:20160522193254p:plain

次にn2にuser2が接続してきて、それを他のノードに同期する。しかし、何らかの原因で、n2からn1へのメッセージが遅延したとする。

f:id:Joe_noh:20160522193300p:plain

次にn3がuser2を除き他のノードに同期する。

f:id:Joe_noh:20160522193305p:plain

この後に、先ほど遅延していたメッセージがn1に到着してしまうと、n1の内部状態は[user1, user2]になってしまい他のノードと矛盾する。

f:id:Joe_noh:20160522193310p:plain

このような問題を解決するのがCRDTで、今回のドメインに適したデータ型はORSWOTである。

Vector Clock

論文は[2]。各ノードに初期値0の論理クロックを持たせる。ノードが状態を更新したときに自身のクロックを+1する。他のノードにメッセージを送るときは、データと一緒に、その時点で知っている各ノードの論理クロック(ベクトル)も送る。メッセージを受け取ったら、自分の論理クロックを+1した後、同梱されていた論理クロックベクトルを見て各ノードのクロックの値を覚えておく。

受け取ったベクトルv_receivedと自身の持つベクトルv_localの対応する要素を比較して、全てv_received[i] =< v_local[i]、かつ1つ以上の要素がv_received[i] < v_local[i]ならば、送られてきた情報が古いものであることがわかる。

上の問題の例で説明すると、下図のように論理クロックがカウントアップされていく（青マルがイベント）。最後に遅延して届いたメッセージのベクトルは[1, 2, 0]、そのときのn1のベクトルは[2, 2, 3]、よって古い情報であると判断できる。

f:id:Joe_noh:20160522193242p:plain

CRDT (ORSWOT)

Conflict-free Replicated Data Typesの略。Strong Eventual Consistency（SEC, 強い結果整合性って呼んでいいのかな？）を実現するデータ型。2つのレプリカに対していくつかの更新を適用するとき、その更新内容が同じならば順序によらず同一の結果が得られることが保証される。Set, Graph, Mapなどいくつか種類があり、要素の追加・削除や2つの複製のマージ方法が定義されている。上の問題の例で各ノードにuserが接続したときに要素の追加・削除が行われ、他ノードとの同期の際にマージが行われる。

通常のOR-Setでは"add win"（別々のアクターで同一要素eが並行して追加・削除された後、その2つの集合をマージしたときにeが残るという性質）を実現するために、要素追加時にユニークなトークンを要素に付加にしておく。削除するときは、要素をTombstones（墓石）と呼ばれる集合に追加する。Tombstonesは要素追加とマージを行うときに使われる。Tombstonesに、要素とトークンのペアが既にある場合は追加せず、またマージの前にお互いが相手のTombstonesにある要素を自分のSetから取り除く。つまり墓石という名の通り、既に削除されて死んだ要素の判定に用いられる。

Tombstonesは要素の追加と削除を繰り返すうちに肥大化し、パフォーマンスを低下させるという問題がある。この問題をVector Clockの概念を導入して、いくつかの数値比較で判定ができるように最適化したものがORSWOT。ORSWOTはObserved Remove Set WithOut Tombstonesの略で、[3]の「4.2 Optimized Observed Remove Set」で解説されている。

asonge/loomに実装があったので動かしてみた。hex.pmにある最新版とmasterに差があるので注意。

alias Loom.AWORSet, as: S

def display(n1, n2, n3) do
  IO.puts "n1: #{n1 |> S.value |> inspect}"
  IO.puts "n2: #{n2 |> S.value |> inspect}"
  IO.puts "n3: #{n3 |> S.value |> inspect}"
end

n1 = S.new
n2 = S.new
n3 = S.new

IO.puts "n1がuser1を追加"
n1 = S.add(n1, :n1, "user1")
n2 = S.join(n2, n1)
n3 = S.join(n3, n1)

display(n1, n2, n3)

IO.puts "n2がuser2を追加"
n2 = S.add(n2, :n2, "user2")
n3 = S.join(n3, n2)
n2_delay = n2  # まだn1には届かない

display(n1, n2, n3)

IO.puts "n3がuser2を削除"
n3 = S.remove(n3, "user2")
n2 = S.join(n2, n3)
n1 = S.join(n1, n3)

display(n1, n2, n3)

IO.puts "遅延したメッセージがn1に到達"
n1 = S.join(n1, n2_delay)

display(n1, n2, n3)

n1がuser1を追加
n1: ["user1"]
n2: ["user1"]
n3: ["user1"]
n2がuser2を追加
n1: ["user1"]
n2: ["user1", "user2"]
n3: ["user1", "user2"]
n3がuser2を削除
n1: ["user1"]
n2: ["user1"]
n3: ["user1"]
遅延したメッセージがn1に到達
n1: ["user1"]
n2: ["user1"]
n3: ["user1"]

遅れてメッセージが到着してもノードの状態に矛盾が生まれず、データの一貫性が保たれている。

参考

  1. https://dockyard.com/blog/2016/03/25/what-makes-phoenix-presence-special-sneak-peek
  2. Timestamps in Message-Passing Systems That Preserve the Partial Ordering, Colin J. Fidge, 1988
  3. An Optimized Conflict-free Replicated Set, A. Bieniusa et. al., 2012