Mergeable replicated data types – Part I – the morning paper を読んだメモ
MRDT: Mergeable Replicated Data Types
CRDT(Conflict-free Replicated Data Type)と同じ感じ(背景の話?)
geo-replicated distributed systemsの文脈の論文
→地理的に複製されるとは?
低レイテンシ、HAを実現するためにローカルに独立した操作をデータ型上で扱いたい。
- replicated data types(sequentialと同じI/Fだけど、実装は複製状態を認識)
- concurrent revision strategies
- specification-first approach(複製がある条件下でアプリの正確性が何を意味するのか)
可逆なrelational specificationsがMRDTの中心
→データ型のdomainをrelational setsにマッピング
- versioned states
- explicit merging operations
最も古い祖先(LCA: lowest common ancestor)+2つの変更されたversionの3-way merge
→論文の焦点は、「任意の複雑かつ構成可能なデータ型定義で、正しいマージ関数を自動的に導出すること」
→意味のある有用な分散セマンティクスに帰着する
加法と乗法が定義されたカウンターを考える
(*2)と(-1)の演算に対して、初期状態: 5とする。
(*2)(-1)の順→最終状態: 9
(-1)(*2)の順→最終状態: 8
提案:
let merge l v1 v2 = l + (v1 - l) + (v2 - l)
→前者の結果(9)と一致するけど、どちらかというと乗算であっても、状態の差分として表現しているのが重要
v1 = l + delta v1
v2 = l + delta v2
だと思えば自然。
で、l = 5 なので、
v1 = 5 + (+5) <- (*2)が(+5)になった
v2 = 5 + (-1)
→状態の差分に落とし込むことで、状態に依存しない形に帰着できるので、順序性の依存をなくせる?
→linearizabilityは保証しないが、収束は保証できる
乗算で利息を計算する銀行業務アプリでは有用かもしれない。
型の値をrelational domainに写像する抽象化関数と、逆写像の具体化関数で構成される可逆的なrelational仕様
queueの例、pushとpopの順番によって最終的な結果が異なる
非決定性を持たせてすべての状態を記憶
実装は、有向グラフを構成し、トポロジ順序付けによってqueueを生成する
References