BT

QCon London: CRDTsを使って分散システムでデータ一貫性を保証する

| 作者: Jan Stenberg フォローする 33 人のフォロワー , 翻訳者 h_yoshida フォローする 1 人のフォロワー 投稿日 2018年4月16日. 推定読書時間: 3 分 |

原文(投稿日:2018/03/12)へのリンク

読者の皆様へ: 皆様のご要望にお応えするべく、ノイズを削減する機能セットを開発しました。皆様が関心をお持ちのトピックを、EメールとWeb通知で受け取ることができます。新機能をぜひお試しください。

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日に予定されている。

 
 

この記事を評価

採用ステージ
スタイル
 
 

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

あなたの意見をお聞かせください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする
コミュニティコメント

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

このスレッドのメッセージについてEmailでリプライする

ディスカッション

特集コンテンツ一覧

.NETの派生を理解する

Wayne Citrin 2018年7月18日 午前3時44分

ASP.NET Core - シンプルの力

Chris Klug 2018年6月4日 午前3時26分

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT