CRDTについて勉強したので纏めてみました。15分くらいでざっとわかったつもりになれる感じで纏めてみたつもりです。

全体スライド

Slideshareのスライドが埋め込めなかったので、↓からアクセスしてくださいm(-_-)m

CRDT in 15 minutes from Shingo Omura

下記はスライドの講演の書き下しのようになっているので、スライドだけ見るんじゃなくて、スライドを見ながら文章を読み進めたい方向けです。

CRDTとは

今回は、CRDTというデータ構造について紹介します。CRDTはそもそも2011年にSSS(Stabilization, Safety, and Security of Distributed Systems)という国際会議で、INRIA(フランス国立情報学自動制御研究所)のMarc Shapiro博士によって発表された、比較的新しいモノです。

CRDTは"Conflict-free Replicated Data Type"の略で、日本語で言うと、__コンフリクトしない複製可能なデータ__といった感じです。

CRDTには実現方法によって２種類の呼び方が存在します(それぞれの略もまたCRDTなのでややこしいですが)。

Commutative Replicated Data Type (Operation-Based)
Convergent Replicated Data Type (State-Based)

やり方には2種類あって、Operation Basedなやり方と、State Basedなやり方があります。コレについては後から説明します。

CRDTは、CAPにおける "A" と "P" の両立を実現しています。"A" は Availabilityの略で、データの可用性(いつでも読書できる性質), "P" は "Partition Tolerance"の略で、ネットワークが故障して一時的に不通になってしまうことです(永遠に壊れたら何もできなくなってしまうのは自明)。

おさらいCAP定理

CAP定理についておさらいしておきます。CAP定理は2000年に証明された分散システムにおける大きな成果の一つです。

ざっくり言ってしまえば、分散システム(プロセス同士がネットワークを介して協調するというシステム)において、

Partition Tolerance: ネットワークが故障しても
Consistency: データの整合性をもって
Availability: 読書が常にできる

というウマイ話は、__どうやっても無理__という定理です。「どうやっても無理」というところがこの定理のパワーですね。

で、CRDTはこの"A"と"P"を両立させるような仕組み、ということです。

"A"と"P"を両立するってどういうこと？

"C", "A", "P"の内 "C"(Consistency)はありません。つまり、

読めたとしてもそのデータは最新の(整合性が担保された)データとは限らない
運良くネットワークが安定していれば、そのうち整合性の担保されたデータが読める

ということです。

えーそんなの、使いものになるの？と思うかもしれないですが、ネットワークが断続的に切れてしまうような不安定な状況であればまだしも、いわゆるサーバーサイドな環境で、ネットワークがそんなに頻繁に切れてしまうような状況は、「時々起こる故障」という程度でしょう。そういう考えのもとでは、

CRDTの取っている"A"と"P"が結構意味を持ってくると思います。ちょっと乱暴な言い方かもしれませんが

ノードが生きていれば、ネットワークが死んでてもいつでも読書できる

という事です。CRDTの凄いところはこれだけじゃなくて、

ノードが故障しないかぎり、ネットワークが復帰しさいすれば、各ノードで行われた書込がいつか反映され、決してロストしない

というところです。

これって、結構凄いことだと思いませんか？データセンター間のレプリケーションの方法としてすごく魅力的だと思いませんか？

でも、どうやって？？？

わかった気になるCRDT

ここで、種明かしです。大まかな戦略はこうです。

ネットワーク上には、複数の異なるバージョンの複製(レプリカ)の存在を許容するようにします
- かつ、複数のレプリカには独立に変更操作を施して良いことにします
- 他ノードで行われた操作を非同期にやりとりして、後で「マージ」して結果整合性を保てるようにする

この「変更操作」がキモで、__可換な操作だけに限定する__んです。そうすると、

操作列が全部到達すれば、操作は可換なので、それを適用していけば、レプリカの状態は収束する！

というわけです。

イメージ的には、下図な感じで

f, gが可換な操作で、
各ノードの初期値が一緒だったら
いつか、f と gが施された状態に収束

しますよね、ということです。

「カウンター」というデータ構造を考えてみてください。別々のノードで足されたとしても"CountUp(n)"という操作の列を覚えておいて、それをやり取りできれば、最終的にカウンターの数値は全てのノードで等しくなることが期待できますよね？

違う変更操作の履歴をもつレプリカが、あとから難なくマージできる、というのが"Conflict-Free"という名前の由来です。

CRDTの2つのやり方

これまで、説明を簡単にするために"操作"をやり取りするという説明をしてきましたが、実はそれはやり方の一つでしかありません。大きく2つ提案されています。

Operation-Based CRDT: Commutative Replicated Data Type(CmRDT)

こうした"操作"をやり取りする方法は__Operation-Based CRDT__と呼ばれ、別名__Commutative Replicated Data Type(CmRDT)__とも呼ばれます

先に説明したとおり、この方法では、操作が可換であることが必要です。名前にも"Commutative(可換な)"と入っているとおりです。

一般的に、データ自体のサイズが大きい時、よりもそれに施す操作のサイズのほうが小さいと思われるので、データ自体のサイズが大きい場合に有効だと思います。

State-Based CRDT: Convergent Replicated Data Type(CvRDT)

この方式では、操作を送り合うではなく、レプリカ(データの状態)自体を送り合います。これが"State-Based"と呼ばれる名前の由来です。

レプリカはそれまでの操作履歴を反映された状態とみなすことが出来ます。なので、2つレプリカを"マージ"する際に、それまでの2つの独立した歴史が両方反映した形でマージできるデータでないと行けません。

このタイプのCRDTに許されたマージ処理は、数学的には Join Semilattice¹ という構造を成さなければなりません。数学的な厳密さを無視してしまえば、いわゆる「可換なモノイド」だと思えばよいと思います。

例えば、「最大値」を保持したいような場合、2つの値の最大値をを取るという操作はJoin Semilatticeになるので、値を送信しあうことで、全ノードが同じ最大値を保持することが可能になる、という具合です。

"状態"を送り合って、最終的に同じ状態に"収束"する、というマージ処理を施すという意味で、"Convergent(収束する)"という名前がついています。

巨大なデータレプリカ同士を送り合うのは効率のよいことではないので、この方法は、レプリカ自体のサイズがあまり大きくない場合に有効と言えると思います。

典型的なCRDTの実例

今回は、典型的なCRDTの中でも、比較的説明が用意なデータ構造について紹介します。

まずはカウンタです。increment/decrementができるアレです。

カウンタ

カウンタを実装するCRDTはいくつか提案されています。

Operation Basedなカウンタ

Op-Counter

これは直感通りです。

各ノードが持つレプリカの構造: カウンタの値(初期値=0)
送り合う操作: increment/decrement
説明: increment/decrementは行われた数しか最終状態に影響を及ばさないので、受信した順に操作を施していくだけ

State-Based なカウンタ

G-Counter

これは足し算だけが出来る(Grow only的な？)カウンタです。

各ノードが持つレプリカの構造: {'node名', '値'}の配列(ベクトル)
マージ処理: 各ノード名毎に'Max'を取る
- 例: merge([{'node1', '3'}, {'node2', '5'}], [{'node1', '4'}, {'node2', '1'}]) ==> [{'node1', '4'}, {'node2', '5'}]
カウンタの状態: 各ノードの値の合計
説明: カウンタの値は減らないので、一番大きいのが最新だとわかる。Maxはjoin semilatticeを成す。

PN-Counter

足し算だけじゃなくて、引き算も可能にしたCRDTなカウンタです。足し算分(Positive分)、引き算分(Negative分)を別々に持っておけばいいです。引き算分だけaccumulationしておけば引き算分はマージするときに小さい方を取ればいいでしょう、という訳です。PNの由来はこの方法にあります。

各ノードが持つレプリカの構造: {'node名', 'Positive値', 'Negative値'}
- レプリカの状態計算: (Positive値) - (Negative値)
マージ処理: 各ノード毎に、PositveはMax, NegativeはMinを取る
カウンタの状態: 各ノードのレプリカの状態の和
説明: 上記参照

集合

カウンタより、もう少し汎用的なデータとして集合を見てみます。

State-Based

集合は、まずはState-Basedな方から紹介します。

G-Set

G-Counterと同じく、"追加"しかできない集合です。

レプリカの構造: 集合自身(初期値=空集合)
マージ処理: 和集合
説明: どこかで足された事実があるわけなので、全部和集合を取っていけばいい

2P-Set

追加、削除に対応した集合です。PN-Counterのアイデアと同じように「足された要素の集合」、「取り除かれた要素の集合」の2つを保持します。

レプリカの構造: 追加された要素の集合(A),削除された要素の集合(R)
レプリカの状態: A - R
マージ処理: A, Rそれぞれの和集合を取る
説明: 一度取り除いたデータは足せないので注意。つまりどこかのノードでremoveされてしまったら最後、どこで足しても、いつか取り除かれてしまうことになる。

Operation-Based

Op-based 2P-Set:

2P-Setはそれぞれのデータを送り合うと、非常にデータサイズが大きくなる場合がある、そこで'add(e)'/'remove(e)'という操作を送り合うようにすればいい。

レプリカの構造: 追加された要素の集合(A),削除された要素の集合(R)
レプリカの状態: A - R
送り合う操作: 'add(e)'/'remove(e)'
説明: 各要素に対するaddは何度やっても可換、というか冪等。removeも同じ。なので、これらの操作を送り合うだけで良い

カウンタ、集合以外にも色々できる

A comprehensive study of Convergent and Commutative
Replicated Data Typesを見ると、カウンタ、集合以外にも、Map(Key-Value), Register, Graphといった複雑なデータもCRDTに出来ることが証明されているので、参考にしてください。

CRDTが実装されているOSS達

こうしたCRDTは既に実用的なOSSで実装されてきています。主なところで言うと、

Riak by Basho
- 多分いちばん早い？2013年のバージョン2.0で入っている
Roshi by SoundCloud
Akka by Akka Team

RiakにおけるCRDT

よく使いそうなデータには対応していて、httpインターフェースがあるので簡単に使うことが出来そうです。実装方式を選択することは出来ないようです。

使い方とかは、Riak 2.0のCRDTで遊ぶや、公式ドキュメントを参照してください。

RoshiにおけるCRDT

RoshiはSoundCloudによって開発されたCRDT用のサーバです。Goで書かれています。なぜ彼らがRoshiを必要としたかは

Roshi: a CRDT system for timestamped events

にまとまっているので参照してください。

Roshiは、バックエンドストレージとしてRedisに依存していて、RedisのSorted Setを使っているようです。Roshiが対応しているCRDTは"LWW-element-set"と呼ばれるものだけで、

この"LWW-element-set"は「最後」にaddされるかremoveされたかで要素の所属が決まる集合です。"LWW"は"Last Writer Wins"の省略形です。

何をもって「最後」とするか、ですが、timestampベースのようです。Redisにtimestamp付きで操作が保存されているらしく、"任意の時点での集合"が復元できるのが強みのようです。

サーバのインターフェースはHTTPなのでRiakと同じように色んな所に簡単に組み込む事ができそうです。

AkkaにおけるCRDT

AkkaはScala/Javaで利用可能な、並行分散アプリケーション用のツールキットです。コアとしてアクターモデルによるプログラミングをサポートしていることが最大の特徴です。

AkkaにおけるCRDTは、Akkaの1モジュールであるDistributed Dataというモジュールで提供されています。Akkaはクラスターを構成する機能を提供しており、そのAkkaクラスターのメンバー間で操作や状態をやり取りするようなCRDTになります。

データ構造のサポートとしては、一番手厚く、今回紹介しきれなかった様々なCRDTの実装も含まれています。

Riak, Roshiと異なる最大の特徴は、ライブラリとして提供されていることもあって、

アプリケーションノード上でCRDTが利用できる

というのが特徴だと思います。RoshiやRiakはデータストレージサーバがCRDTのノードになっていて、そこへアプリケーションノードからアクセスして状態を問い合わせるという形になってしまう一方で、Akka Distributed Dataを使った場合は、アプリケーションノード同士がCRDTのノードになれます。

CRDTおさらい

色々見てきましたが、ここでおさらいです。CRDTは

高いAvailabilityとPartition 耐性をもち、
➔ ノードが生きてれば、ネットワーク死んでても、常に読み書きできてほしくて、
Consistencyは期待できないけど、

➔ 一時的に読めても整合性が無いことが許容できて
結果整合性だけが期待できる
➔ ネットワークが正常ならそのうち正しい値に収まる(書込がロストしてほしくない)

ようなデータを実現したい時に使えるデータ構造です。

参考文献

Wikipedia: CRDT
A comprehensive study of Convergent and Commutative
Replicated Data Types
- コレ読むのが確実
Riak 2.0のCRDTで遊ぶ
- Basho 上西さんのブログ
- スライドも図入りで丁寧に説明されている
Akka Distributed Dataの参考文献
Riak
Roshi
Roshi: a CRDT system for timestamped events
Akka
Akka Distributed Data

ごめんなさい

15分じゃ終われないかもしれないです。m(-_-)m

任意の部分集合に対して最小上界(Least Upper Bound)を持つ半順序集合のことを言います(Wikipedia: Semilattice)。数学的に言うと、有界なJoin Semilatticeは可換モノイドとみなすことが出来ます。 ↩

CRDT (Conflict-free Replicated Data Type)を15分で説明してみる