リアルタイム共同編集のアルゴリズム (Operational Transformation; OT) を理解する試み

Google Docsのように文書を複数人でリアルタイムに共同編集できるアプリケーションがあります。あのような機能は、多かれ少なかれ、Operational Transformation (OT; 操作変換) という考え方を使って実現されているようです。興味があったので、このOTについて調べてみました。

(追記: これからは OT でなく CRDT だという話 → I was wrong. CRDTs are the future)

なおGoogle Docsではいわゆる「リッチテキスト」を共同編集できますが、ここでは話を簡単にするために「プレーンテキスト」を共同編集することを想定します。

リアルタイム共同編集の流れ

共同編集システムの登場人物は次の通りです：

• サーバ x 1（各クライアントから届く編集操作をもとに、最新の文書を保持します）
• クライアント x N（文書を編集する側です）

そして、リアルタイム共同編集では以下のような処理が繰り返されます：

1. 各クライアントは、手元で文書が編集されたら、その編集操作の内容をサーバに送信します。
2. サーバは、各クライアントから送られてくる編集操作を、到着した順にサーバ上の文書に適用します（※ここでOTを使います。後述）。
3. 次にサーバは、他の全てのクライアントに編集操作の内容を送信します。
4. 各クライアントは、サーバから送られてきた（他のクライアントによる）編集操作を、手元の文書に反映します（※ここでもOTを使います。後述）。

ちなみにプレーンテキストにおいては、「編集操作」というのは文字列の単なる挿入と削除のことです。例えば「39文字目に文字列 “hello” を追加」とか「74文字目から8文字を削除」といったものです。

サーバは、各クライアントから届く編集操作を、到着順にサーバ上の文書に反映させていきます。これによってサーバ上の文書は次々と更新されていき、文書のリビジョン番号 (rev) は 0 → 1 → 2 → 3 → 4 → … と直線的に進んでいきます。サーバは、あるクライアントから届いた編集の内容を、他のクライアント全員にも送信することで、皆が同じ文書の状態を共有します。

…というのが基本ですが、現実はそう簡単ではありません。

遅延による難しさ

リアルタイム共同編集が難しいのはネットワーク等による遅延があるからです。遅延があるため、すべてのクライアントが常に最新のリビジョンを見ているとは限りません。あるクライアントは、古いリビジョンの内容に基づいて編集を行い、それをサーバに送信するかもしれません。また、同じリビジョンに対して複数のクライアントが同時に編集するという競合も起きるでしょう。具体例としては以下のようなことが発生します：

• シナリオ (1) 「サーバ側の文書はリビジョン rev:53 なのに、クライアントBにはまだ rev:51 までしか同期されていなかった。このクライアントBが文書を編集し、rev:51 に対する編集操作をサーバに送った。しかしサーバ側は既に rev:53 である。どうやって辻褄を合わせればいいのか？」
• シナリオ (2) 「クライアントCは rev:74 に対して文字列の追加を行なった。この操作をサーバに送ろうとする最中に、サーバから（他のクライアントによる編集で生じた）rev:74→75 の編集操作が送られてきた。このとき、クライアントCが手元で rev:74 を編集したあとの状態と、サーバから送られてきた rev:74→75 の操作は、どうやって辻褄を合わせればいいのか？」

この問題を解決する手法がOTです。

リビジョンが分岐してはならない

同時編集の目標は「遅延がありつつも結果的には皆が同じ文書を共有する」ということです。つまりリビジョンは分岐してはならず、ただ1つの正統な本流だけが存在すべきだということです。

この観点で見ると、先述したシナリオでは、「本流のリビジョンからの枝分かれの発生」によって問題が生じていることが分かります。

解決方法:「競合する2つの操作を、順不同な直列操作に変換する方法を定義する」

逆にいえば、一時的に編集結果が枝分かれしても、それをすぐに本流の状態へと軌道修正できれば、ただ1つの本流を皆で共有することができます。

そのための要件として、まず、少なくとも、分岐が生じた場合にそれを直列に直せなければなりません。

(図はまだ)

「同じリビジョンに対する（つまり競合する）opAとopB」を、「opAをしたあとで、opBに相当するop B’ をする」に変換できなければならないのです。

また、それぞれの立場によって opA, opB の発生順序が違うので、「opAをしたあとで、opBに相当するopB’ をする」と「opBをしたあとで、opAに相当するopA’ をする」とが同一の結果になるという性質も必要です。

(図はまだ)

プレーンテキストでの具体例を示しましょう。同じリビジョンに対して「opA: 4文字目から10文字を削除する」「opB: 8文字目に “hello” を追加する」という競合する操作が生じた場合、これらは2通りの直列な操作に変換できます：

• opA→opB’の順の場合 「opA: 4文字目から10文字を削除する。→ opB’: 4文字目に “hello” を追加する」
• opB→opA’の順の場合「opB: 8文字目に “hello” を追加する。→ opA’: 4文字目から4文字を削除し、13文字目から6文字を削除する」

という直列な操作に変換することができます。いずれも同じ結果が得られます。

これが「操作変換 (OT)」です。このような操作変換が定義できれば、分岐の発生を修正して常に本流のリビジョンだけが存在するようにできます。

プレーンテキストにおける操作と操作変換の例

ここで一旦、プレーンテキストに対する操作を見ておきましょう。プレーンテキストに対する操作 (operation) は、以下の3つの基本操作の列として記述することが多いようです。

• insert(s) — 文字列sを挿入する
• delete(n) — n文字を削除する
• retain(n) — 既存のn文字を維持する

例えば、20文字の文書において、opA「4文字目から10文字を削除する」と、opB「8文字目に “hello” を追加する」いう操作は以下のように記述できます。

• opA = [retain(4), delete(10), retain(6)]
• opB = [retain(8), insert(“hello”), retain(12)]

そして、これを操作変換 transform(opA, opB) -> (opA', opB') すると以下が得られます。

• opB' = [retain(4), insert(“hello”), retain(6)]（opA→opB’ の順に適用する場合にopBに相当する操作）
• opA' = [retain(4), delete(4), retain(5), delete(6), retain(6)]（opB→opA’ の順に適用する場合にopAに相当する操作）

プレーンテキストの操作についての操作変換 transform(opA, opB) -> (opA’, opB’) の具体的な実装についてはここでは割愛しますが、プレーンテキストに関しては、それほど難しい処理ではありません。

また、上記の transform のほかに、2つの直列なopを合成する compose(op1, op2) -> op も定義しておきます。これも詳細は省略。

サーバ側での処理

サーバは以下の状態をもっています：

• 最新の文書（途中から参加するクライアントに配布する）
• 現在のリビジョン番号
• 過去に適用してきたopsの履歴（全てではなく直近のものだけ保持すればOK。保持する量を増やすほど遅延に耐えられるようになる）。適用時のリビジョン番号と紐付けて保持します。

サーバは、クライアントから編集操作が送られてくるたびに、次の処理を行います。（なおクライアントから送られてくるメッセージには、編集操作のほかに、クライアント側のリビジョン番号も含まれています。）

1. クライアント側とサーバ側とでリビジョン番号が異なる場合は、クライアント側から送られてきた op に操作変換を適用して、サーバ上の最新のリビジョンに適用できる op’ に変換します。具体的には、サーバ上にあるopsの履歴を用いて操作変換を必要なだけ繰り返します。例えばクライアント側が rev:30 でサーバ側が rev:33 の場合は、サーバに記録されている rev:31 から rev:33 までの3つのopsを相手にして、 opã‚’3回transformします。これを op’ とします。
2. クライアント側とサーバ側でリビジョン番号が同一の場合は上記の変換は不要です。
3. 編集操作 op’ をサーバの文書に適用し、リビジョン番号をインクリメントします。また、op’ をサーバ上の履歴に追加します。
4. 編集操作を送ってきたクライアントにACKを返します。このACKには、サーバ上で確定したリビジョン番号を含めます。
5. その他の全クライアントに編集操作を反映させるため、op’ と最新のリビジョン番号を送信します。

クライアント側での処理

クライアント側は以下の状態をもっています：

• 現在の文書
• リビジョン番号（現時点でどのリビジョンまで同期しているかを表します）
• outstanding op（手元での編集によって一時的に分岐した操作のうち、サーバに送信済みだがまだACKが返ってきていないもの）
• buffered op（手元での編集によって一時的に分岐した操作のうち、送信待機中のもの）

クライアントでは、各イベントにおいて以下の処理を行います。

文書が編集されたとき

1. outstanding op がない場合は (=ACK待ち中でない場合は)、編集操作 op を outstanding op にセットしつつ、サーバに送信します。
2. outstanding op がある場合は (=ACK待ち中の場合は)、buffered op に op をセットして送信待ちにします。buffered op が既に存在する場合は、その buffered op に op を合成します。

ACKが返ってきたとき

1. ACKに含まれる revision番号で手元のリビジョン番号を更新します。
2. outstanding op を空にします。
3. buffered op がある場合は、それを outstanding op に移しつつ、サーバに送信します。

opを受信したとき

1. outstanding op がある場合は、(outstanding_op, op') := transform(outstanding_op, op) という更新をします。
2. さらに buffered op がある場合は、(buffered_op, op') := transform(buffered_op, op') という更新をします。
3. outstanding opã‚‚buffered opもない場合は、opをそのまま使います（つまり op' := op とします）。
4. クライアント側の文書に操作 op’ を適用します。

おわりに

実用的なテキストエディタを作る場合は以下のようなトピックも検討しなければいけない気がします。

• カーソルの動きもOTの対象にする
• operation をベースにしたUndo/Redoの実装
• サーバ側でどのようにスケーラビリティを得るか
• HTML5 の contenteditable と日本語IMEによって発生しそうな地獄との戦い

参考文献

• http://operational-transformation.github.io