概要

Google Documentのような共同編集システムの仕組みについて調べました。完全に自分用のメモなので不適切な個所が多々あるかもしれませんが悪しからず><

気になっていたポイントは主に下記二つで、このレポートではこれらのポイントに対する解をまとめています。

１．リアルタイムでのクライアント・サーバー間同期が必要なはずである。どのような通信手段によってこれが成り立っているのか？

２．Google Documentのようなサービスでは、リアルタイムで複数のユーザが同じ場所を編集してもGitでいうところのマージコンフリクトのような状態にはならない。これはなぜか。

記事執筆の目的

調査内容を記事の形でアウトプットすることで自身の学習効率を高めることが目的です。

一点目：リアルタイムでのクライアント・サーバー間同期方法

これはアプリケーションによって異なるとは思いますが、今回はGoogle Documentについてのみ調べてみました。

かなり古いStack OverflowのQ&Aになりますが、下記のようなPostがありました。

https://stackoverflow.com/questions/35070217/what-technology-does-google-drive-use-to-get-real-time-updates

こちらのAccepted Answerによると、

クライアントからサーバへ、コンテンツの更新を連携する場合はシンプルにPOSTリクエストを用いる。
サーバからクライアントへは、ストリーム通信によって他ユーザによる更新が連携されている。

ようです。

二点目：競合の回避方法

共同編集システムは、OT(Operational Transformation)やCRDT(Conflict-free Replicated Date Type)といった技術によって編集競合を回避しているらしいです。

OTとCRDTは異なる技術で、システムによってOTとCRDTどちらを採用しているか異なります。

例えばGoogle DocumentはOTを採用していて、Appleのメモ帳はCRDTを採用しています。

OT

OTについてはこちらの記事で丁寧に解説してくださっています。

https://qiita.com/phigasui/items/d68bbc7c8023ab11af92

以下、自分用のまとめです。

OTにおいては、

「何文字目に、こういう操作をした」というOperation情報をサーバーを介して作業者間で共有しあう。
サーバは作業者から受け取ったOperation情報をほかの作業者に伝播させる。
各作業者が生成するOperationにはRevisionという連番が降られており、これは作業者全体で整合がとれている必要がある。このRevisionはコンフリクト検出の役割を果たす。もし作業者Aと作業者BそれぞれのOperationのRevisionが重複していれば、それらのOperationが重複していることを意味する。
サーバは作業者間のOperationが競合した場合には自動で競合解消を行う（このコンフリクト解消行為がOperational Transformation）。
作業者もサーバから受けとった他作業者のOperationが、自分のOperationとコンフリクトした場合には自分の手元でコンフリクトを解消する。具体的には自分が生成したOperationの内容を修正する。

CRDT

CRDT（Conflict-free Replicated Data Type）は分散コンピューティングにおいて、リアルタイムで同期をせずとも各ノードでの更新が最終的に競合することなく一貫した状態に収束するようなデータ構造です。

参照元の論文: https://pages.lip6.fr/Marc.Shapiro/papers/RR-7687.pdf

なお論文曰く、ここでいう「競合」というのは個別には「正しいかもしれないが組み合わせるとある不変条件に違反する同時更新の組み合わせのこと。」という意味だそうです。

不変条件どうこうの部分がちょっとわかりづらいですが、自分は下記のように解釈しました。


例えば、AさんとBさんが両者ともに同じ文字列の2文字目にX,Yという文字を挿入する。その後、同期をとった場合にAさんの手元とBさんの手元で異なるデータの状態になってしまう場合、これは競合である。

逆に、同じ場所を更新していたとしても、同期をとった結果Aさん、Bさんの手元のデータが必ず同じ状態になるのであればこれは競合ではない。

（自分は、このメモを書く前は「各ノードが同じ場所を更新していること自体を”競合”と呼ぶのであり、仮に何かしらのアルゴリズムにしたがうことで最終的に一貫して同じ状態になるとしても、それはアルゴリズムによって競合を適切に自動解消しているだけで、競合自体が発生していないわけではない」という気持ちがあったので、この部分の解釈に少し時間がかかってしまいました。）

CRDTとしてカテゴライズされるデータ構造には様々ありますが、今回はLSeqというデータ構造について調べてみました。

LSeq

参照したサイトは下記です。

https://www.bartoszsypytkowski.com/operation-based-crdts-arrays-1/

LSeqはバイトシーケンスとレプリカID（レプリカデータに対する識別子）の複合キーをデータのポインタとして利用することで、競合を回避しているようです。

まずは、編集者が一人のケースで説明します。

Aさんが’Example’という文字列を編集するケースを考えましょう。ここでAさんの持つレプリカデータにはレプリカIDとして’A’が割り当てられているものとします。

初期状態として‘Example’には、E: [1] A, x: [2] A….e: [7] Aといった具合に、文字数に応じたバイトシーケンスとレプリカIDを組み合わせたポインタが割り当てられています。

ここで、二文字目に’n’ という文字を挿入した場合、この文字にはn: [1, 1] Aのように、バイトシーケンス部分が前の文字より大きく、後の文字よりも小さくなるように割り当てられます。

では、この仕組みによってどのように競合が回避されるのかも確認しましょう。

AさんとBさんが別々の箇所を編集するケース

’Example’という文字列があったとして、同期のとれていないAさん（レプリカID: ‘A’）、Bさん（レプリカID: ‘B’）がそれぞれ下記のような操作を行う。

Aさんは2文字目（’E’,’x’の間）に’n’を挿入する。
Bさんは7文字目（’l’,’e’の間）に’m’を挿入する。

このとき、それぞれに割り当てられるポインタは下記の通りです。

n: [1,1] A
m: [6,1] B

このポインタであれば、どのような順番でマージしてもバイトシーケンス部分によって文字を挿入すべき箇所が明確で、’Enxamplme’というデータに収束します。

（これが、例えばポインタが単純な整数で表す仕組みになっていると、マージ順によって挿入位置が変わってしまう。）

AさんとBさんが同じ箇所を編集するケース

’Example’という文字列があったとして、同期のとれていないAさん（レプリカID: ‘A’）、Bさん（レプリカID: ‘B’）がそれぞれ下記のような操作を行う。

Aさんは2文字目（’E’,’x’の間）に’n’を挿入する。
Bさんは2文字目（’l’,’e’の間）に’m’を挿入する。

このとき、それぞれに割り当てられるポインタは下記の通りです。

n: [1,1] A
m: [1,1] B

この場合、二つ目のキーであるレプリカIDが役に立ちます。ここでは、レプリカIDが辞書的に若いほうが先に来るアルゴリズムであると仮定します。

よって、どのような順番でマージしても’Enmxample’というデータに収束します。