Increments × cyma (Ateam Inc.) Advent Calendar 2020 の23日目は
Increments株式会社の @phigasui が担当します。
同時編集のシステムのコアである
- 競合解消のための操作変換(Operational Transform)の説明
- クライアント、サーバーで操作の管理と送受信についての説明
を行っていきます。
Operational Transformation の有名なOSSとして ot.js が存在しています。実は、JavaScript のみならず、Python, Haskell, Coq, Lua での実装例が用意されています。
それぞれの読みやすい言語で読み解けるためありがたいです。
https://github.com/Operational-Transformation
また、Visualization of OT with a central server でOperational Transformation のビジュアライゼーションも公開しているため、試しながら見ていくと納得感が高まると思います。
競合解消のための操作変換(Operational Transform)
考え方は非常にシンプルです。
ですが実現するための実装は複雑です。
まず初めに、複数のユーザーが同時に編集する場合に発生する問題は編集の競合です。
例えば、AさんとBさんが同じテキストを編集していて
Lorem ipsum
というテキストがあった時に、Aさんは Lの文字の後にxの文字を追加します
Lxorem ipsum
Bさんは i の文字の後に y の文字を追加します
Lorem iypsum
この時、それぞれ編集の情報として、追加した文字列と追加した位置 を送信します。
例えば Aさんの処理であれば ["x", 1]、Bさんの処理であれば ["y", 7] という具合になります。
お互いに送信された処理の情報を取り込むとBさんの方では
Lxorem iypsum
と期待通りの変更になりますが、Aさんの方ではAさんが挿入した xの文字によってズレが発生しているため
Lxorem yipsum
となってしまい AさんとBさんが見ている状態に差が生まれてしまいます。
そこで Operational Transformation で行う操作の変換によって、当たり前ですが
AさんのエディタではAさんの操作を行った後にBさんの操作を適用して意図した結果になるようにBさんの操作を変換、BさんのエディタではBさんの操作を行った後にAさんの操作を適用して意図した結果になるようにAさんの操作を変換します。
抽象化して表現すると、競合する2操作 $O_a$ と $O_b$ から 別の操作 $O_a'$, $O_b'$ に変換します。
- $O_a'$ は $O_b$ 適用後に同じ結果になるような操作
- $O_b'$ は $O_a$ 適用後に同じ結果になるような操作
先ほどの例でいくと、Aさんの操作["x", 1]はBさんの操作位置よりも前の位置のため ["x", 1] のまま、Bさんの操作["y", 7]はAさんの挿入よりも後よりの位置のためAさんの挿入した1文字分ずらした ["y", 8] に変換されます。
操作の種類は主に二つで基本的な変換の作用はシンプルです。
- 挿入
- これよりも後の位置の操作の場合、カーソルの位置を進める
- 削除
- これよりも後の位置の操作の場合、カーソルの位置を後退させる
ただし、削除の範囲が別の操作と重複すると変換がややこしくなってきます。
削除 と 削除
削除の操作が重複する場合、打ち消し合います。
例えば
Lorem ipsum
に対し
Aさんは oを削除し
Lrem ipsum
へ変更、Bさんも同じく o を削除し
Lrem ipsum
とした場合、
Lrem ipsum
という結果を期待します。
そのために Aさんのエディタでは Bさんの操作を受け取るとその操作は削除
Bさんのエディタでも同様にその操作は削除されます。
削除 と 挿入
削除する範囲が他の操作の挿入位置を含んでいた場合はどうでしょうか。
例えば
Lorem ipsum
にたいし Aさんは em ip を削除し
Lorsum
と変更します。
Bさんは Lorem の後に x を追加し
Loremx ipsum
と変更します。
その時期待される結果は下記の通りです。
Lorxsum
Aさんの操作は ["delete", 3, "em ip"] から ["delete", 3, "em"]と["delete", 4, " ip"]
Bさんの操作は ["insert", 5, "x"] から ["insert", 3, "x"]
と変換されます。
Aさんの操作は展開すると ["delete", 3, "e"] ["delete", 3, "m"]["delete", 3, " "]["delete", 3, "i"]["delete", 3, "p"] から ["delete", 3, "e"] ["delete", 3, "m"]["delete", 4, " "]["delete", 4, "i"]["delete", 4, "p"]
と同等です。
Bさんの操作位置は5なので最初の削除2文字適用されると位置は3に移動します。
そうすると3つめの削除と挿入の操作のカーソル位置が重複するため挿入操作分、以降の削除操作位置は一文字分進みます。
そのため上記のような変換の結果になります。
サーバーとクライアント
サーバーとクライアントではそれぞれ、どの操作が Operational Transformation を行うべき操作か判断する必要があります。
クライアント
クライアントでは下記のコントロールをします。
- 自身の操作の送信
- サーバーから ACK を返してもらって完了
- サーバーから受信した他者の操作の取り込み
- リビジョン数(どのタイミングのテキストを操作しているのか)の管理
- このリビジョン数を見てサーバーでどの操作が競合しているのか区別できます
また、これらを管理するために3つのステートを持って、それぞれのステータスで必要な処理を行います。
送受信の状況に応じた3つのステートの遷移
3つのステートはそれぞれ下記の状態を表します。
- Synchronized
- 同期が取れている状態
- Awaiting Confirm
- 送信した操作の ACK 待ち
- Awaiting With Buffer
- Awaiting Confirm + 以降の操作をバッファにためている状態
それぞれのステートは下記の通り、隣り合ったステートにのみ遷移します。
Synchronized <-> Awaiting Confirm <-> Awaiting With Buffer
各ステートでの処理についてです。
Synchronized
- 操作送信時
- 自分の操作を直ちにサーバーに送信し、Awaiting Confirm になる
- 操作受信時
- サーバーから受信した他者の操作を直ちに取り込む
- リビジョンの更新
- ACK 受信時
- リビジョンの更新
Awaiting Confirm
- 操作送信時
- ACK 待ちのため、バッファーに追加して Awaiting With Buffer になる
- 操作受信時
- 受信した操作を確認待ちの操作の影響を加味した操作に変換して取り込む(Operational Transoformation)
- リビジョンの更新
- ACK 受信時
- Synchronized になる
- リビジョンの更新
Awaiting With Buffer
- 操作送信時
- バッファーに操作を追加する
- 操作受信時
- 受信した操作を確認待ちの操作の影響を加味した操作に変換して取り込む(Operational Transoformation)
- バッファないの操作を受信して変換した操作の影響を加味した操作に変換する(Operational Transoformation)
- リビジョンの更新
- ACK 受信時
- バッファの操作を直ちに送信して Awaiting Confirm になる
- リビジョンの更新
バッファを活用してどのリビジョンで自身の操作を行っているのかサーバーと同期をとりながら操作の送受信を行って整合性を維持しています。
サーバー
クライアントからリビジョンの値と操作の情報がセットで送信されます。
サーバーではリビジョンをもとに受け取った操作と競合する他者の操作を確認し、存在していれば操作変換を適用します。
そのため必要な操作は下記の通りです。
- クライアントの操作を受け取って、そのリビジョンよりも新しい操作があれば、その操作の影響を加味した操作に変換する (Operational Transformation)
- 操作を新しいリビジョンの操作として保存
- 他のクライアントへ操作をブロードキャストする
クライアントと異なり、ステート管理を必要としないためシンプルです。
以上の競合解消のロジックとサーバー、クライアントの操作管理によって同時編集のコアが作られています。
かなり難しそうなイメージですが、こうしてみると非常にシンプルなロジックだと思います。
JavaScript以外での実装はここで説明している範囲の実装なので理解しやすいです。
アドベントカレンダー明日の告知
Increments × cyma (Ateam Inc.) Advent Calendar 2020の24日目、クリスマスイブは@mano_shunsukeがお送りします！！