Conflict-free Replicated Data Types (2011)
December 31, 2023オブジェクトのレプリカを複数のノードに分散するシステムにおいて、レプリカが非同期に更新された場合、後の同期で更新内容が衝突しうる。 Conflict-free Replicated Data Types (CRDTs) は、結び半束の関係にある状態をもつオブジェクトである。 オブジェクトに対する操作が非単調減少であれば、受理した操作の集合が等しいレプリカ同士を、受理した順番によらず同一の状態にでき、衝突を回避できる。
プロセス\(\prod=\{p_0,\dots ,p_{n-1}\}\)は、非同期なネットワークで接続され、ビザンチン故障はないと仮定する。 クラッシュしたプロセスはが回復しても、以降クラッシュしたままでもよい。
クライアントはオブジェクトに、クエリ\(q\), 更新\(u\), マージ\(m\)のいずれかの操作を実行できる。 クエリは副作用がなくオブジェクトの状態を変更せず、更新は状態を変更する。 マージは、別の1つのレプリカを引数にとり、自分の状態を変更する。 レプリカ\(i\)に対して引数\(a\)を渡した\(k\)番目の操作を\(f^k_i(a)\)とおき、 レプリカ\(i\)の初期状態を\(s_i^0\), \(k\)番目の操作後の状態を\(s_i^k\)とおくと、操作による状態遷移を\(s^{k-1}_i\bullet f^k_i(a)=s_i^k\)と表せる。 このとき\(f\)がクエリであれば、\(s\bullet q \equiv s\)になる。
CRDTsを定義する方法は、状態に着目する方法と操作に着目する方法の2通りがある。 状態に主眼を置く方法はState-based Convergent Replicated Data Type (CvRDT) といい、操作に沿うものをOp-based Commutative Replicated Data Type (CmRDT) という。 どちらの様式でもCRDTsとして備わる性質は変わらないため、定義しやすい方を採用してよい。
CvRDTの定義はマージ操作に着目する。 CRDTsの任意の2つの状態\(s, s’\)には上限\(s\sqcup s’\)が存在し、\(\sqcup\)は交換法則 \((s\sqcup s’ = s’\sqcup s)\), 羃等性 \((s \sqcup s = s)\), 結合法則\(((s\sqcup s’)\sqcup s’’ = s\sqcup (s’ \sqcup s’’))\) が成立する。 CvRDTは、マージ後に2つの状態の上限になり\((s\bullet m(s’)=s\sqcup s’)\), 更新によって半順序関係\(\le\)が単調減少することはない\((s\le s\bullet u)\)。 このとき、受理した更新の集合が等しいレプリカであれば、受理した更新の順序によらず、両者の状態は等しくなる。
CmRDTの定義は、更新を、副作用のない\(\textit{prepear-update}\) \((t)\)と副作用のある\(\textit{effect-update}\) \((u)\)のペア\((t, u)\)に分ける。 \(i\)において、\(t\)は\(u\)の直前の操作であり\(f^{k-1}_i=t\Rightarrow f^k_i=u\)が成立する。 \(u\)は全てのレプリカで実行され、任意の2つの\(\text{effect-update}\) \(u, u’\)について\(s\bullet u \bullet u’\equiv s\bullet u’\bullet u\)が成りたつとき、CvRDTと等しい整合性が成立する。
雑記
メッセージの配信がexactly onceでないと、重複して受信したメッセージを無視し、操作の集合を等しくしなければならない。