CRDTs(Conflict-free Replicated Data Types)とは、分散システムにおいて、理論的に実証された方法である集中型サーバを使用せずに、強い結果整合性(eventual consistency)を確保するアルゴリズムファミリである。Martin Kleppmann氏はQCon London 2018で行ったプレゼンテーションで、氏が調査した共有ドキュメント上で共同作業を可能にするアルゴリズムと、それらをデータ同期のために使用する方法について述べた。
ケンブリッジ大学の研究員であるKleppmann氏によれば、同じ文書を同時に編集する場合の問題については、1980年代後半から研究が行なわれている。目標はコンバージェンス(convergence)の達成 — 編集作業の終了時に、全員の画面に同じドキュメントを表示可能なアルゴリズムを見つけることだ。
アルゴリズムファミリのひとつはOT(Operational Transformation)である。いくつかのアルゴリズムが開発されているが、そのほとんどは失敗で、ドキュメント相互の同期が達成されていない。唯一の方法は集中型サーバを使用するもので、例えばGoogle Docsでもこれが採用されている。これは厳しい制限だとKleppmann氏は考えている — 隣り合わせのモバイルフォンとラップトップのデータを同期する場合であっても、必ずどこかのデータセンタを経由しなければならないのだ。
CRDTs(Conflict-Free Replicated Data Types)はもうひとつのアルゴリズムファミリで、Atomテキストエディタなどで使用されている。このアルゴリズムでは集中型サーバを使用せずに、ピアツーピアで競合を解決することによってコンバージェンスを保証する。オペレーション変換アルゴリズムに関わる問題を考えて、氏とその同僚は、極めて特殊なケースを含むあらゆる状況において、CRTDsが収束するものであることを正式に証明したいと考えていた。
コンバージェンスの証明には、ソフトウェアを証明する定理であるIsabelleを使用した。結果として氏らは、テスト対象のCRDTアルゴリズムが強い結果整合性(strong eventual consistency)と呼ばれる整合性特性を満足することの証明に成功した。さらに氏らは、極めて信頼性の低いネットワークのモデルを使った第2の証明レイヤを使って、アルゴリズムがすべての状況においてコンバージェンス保証を満たすことも証明した。
この氏らのアイデアを実装したものが、共同作業アプリケーション開発を構築可能なデータ構造ライブラリであるAutomergeだ。このライブラリは、通常のJSONドキュメントとして修正可能なJSON風のデータ構造あるいは抽象化を提供する。AutomergeはJavaScriptで記述されたオープンソースだが、Kleppman氏は、研究コードであって実用向けではない点を強調している。
まだ解決されていない理論的問題としては、変更のundoの扱いと、サブツリーをアトミックに移動する方法の2つがある。サブツリーの移動は、削除と再挿入とは同じではない、とKleppmann氏は指摘する。ある種のシナリオでは、重複が発生する可能性があるからだ。
重大な問題はメモリ空間のオーバーヘッドであり、Kleppmann氏が現在取り組んでいる領域のひとつだ。100,000字以内のドキュメントであれば問題なく処理できるが、それを越えるとヒープサイズの問題が発生する可能性がある。データをバイナリ形式で効率よく表現することで、オーバーヘッドをプレーンテキストの3分の1まで削減することができた。これにより、ほとんどの場合において、問題は解決されると氏は考えている。
Kleppmann氏のプレゼンテーションで使用されたスライドは、こちらからダウンロードできる。カンファレンスの主要なプレゼンテーションは録画されており、今後数ヶ月にわたってInfoQで公開される予定である。次回のQConカンファレンスであるQCon.aiは、AIとマシンラーニングに重点を置くもので、2018年4月9～11日にサンフランシスコで開催される。QCon London 2019は、2019年3月4～8日に予定されている。
この記事を評価
- 編集者評
- 編集長アクション