Atom の共同編集機能を支える技術について調べてみた #ATOM

キーワード
- 分散システム、一貫性モデル、CRDT、結果整合性

はじめに

Atomエディタの共同編集機能を支える技術に関する論文¹ ²を読んでみました
- ざっくりメモを残そうと思います
- 理解が不十分な部分や省略があり、詳細は元ネタ要参照です

Teletype (beta) for Atomとは

Atom用の共同編集用プラグインです
Google Docsのように、複数ユーザーが1つの文書をリアルタイムで編集できるようになります

オンラインエディタの動作

オンラインエディタは内部的に下記のフェイズからなると思います
- 編集フェイズ
  - ローカルでの挿入・削除
- 反映フェイズ
  - リモート（別編集者のエディタ）へ反映

編集フェイズ

Site1: 1が挿入され a1b に。
Site2: 2が挿入され a2b に。
各編集内容がネットワーク経由でやり取りされます

反映フェイズ

Site1: 2 の挿入が反映され a21b に。
Site2: 1 の挿入が反映され a21b に。

オンラインエディタの何が難しいか

UXにおける難しさ

なめらかに編集できるべき
- データの同期でいちいち通信したり、処理がブロックされたりはNG
- NW障害があっても使えてほしい、NWが遅くても使えてほしいです

それを実現する分散システムとしての難しさ

挿入・削除操作のやり取りが、遅延したり、順序が入れ替わったり、複数回送信されたり
（実装を工夫しないと）各ユーザーが見ているものが異なったり、意図しない編集になったり

そこで

オンラインエディタはCCI³ ⁴という一貫性モデルを満たしているべきらしい

CCIとは？

Convergence （収束性）
Causality Preservation （因果関係の保存）
Intention Preservation （意図の保存）

Convergence （収束性）

同じデータを全員が見える必要があります
NG：各人の見えているものが違っています
- Site1: AB → A21B
- Site2: AB → A12B
- NGなケースをDivergenceともいいます
  - シュタインズ・ゲート！？

Causality Preservation

NG：因果関係が維持されていません
- Site1: AB→A1B→AB (1挿入→削除）
- Site2: AB→AB→A1B
  - ⇒ 削除がスキップされてしまっています

NG？

Site1 : A → AB → ABC
Site2 : A → AC → ABC
- Cが見えてからBが見える
- この挙動は許容できるかも？
- 「質問とその回答」みたいな場合、回答が先に見えてしまうのは変かも

Intention Preservation

NG：意図が異なってしまっている
- Site1 : ABC → A1BC → ABC
  - 2文字目（1）を削除
- Site2 : ABC → AC → A1C
  - 2文字目（B）を削除

NG
- Site1: A → AB → AB1
- Site2: A → AB → A1B
- Convergence（収束性）違反でもある

Teletype for Atom (beta)での実現方法

いくつかの論文を参考にして実装されています
ここでは基本となっているWOOT¹ ² について、ざっくりメモを残そうと思います

WOOTとは？

Without Operation Transformationの略
- （Operation Transformation → 後述）
CRDTというデータ型を使う

CRDT とは？（知っているかもですが）

Conflict-free (or Commutable) replicated data typeの略
同時編集をうまくマージできるデータ型
- Set（例:ショッピングカート）など
- 数値カウンターなど

AppleのNoteアプリ(で使われているという噂)
- 複数デバイスでの編集を同期
ブックメーカー、ゲームのオンラインチャット
- RedisやRiakのCRDTデータ型を使用

では具体的にどのように実現するかですが

文字の挿入/削除の「操作の集合」から文字列を構成してユーザーに見せます

この各文字を表すときW-characterというデータで表しています

id: その文字のID
- 例: (site1,2) ← 編集者&連番
α: 実際の文字 (a, 1など)
visible: その文字が見えるかどうか True | False
id_cp: 操作対象の文字に先行する文字（Prev）
id_cn: 操作対象の文字の後続の文字（Next）

文字列を表現するにはW-characterのリスト(=W-string)を使います

A1Bのような文字列は：
- {(s1,7), 'A', True, cb, (s2,7)}
- {(s1,8),'1',True,(s1,7),(s2,7)}
- {(s2,7), 'B', True, (s1,7), ce}

cb, ce は特殊なW-characterです
- 先頭と終端（begin / end）を表します
なので前述のA1Bは実際は cb A 1 B ce となっています

挿入・削除の操作

削除処理は簡単です

ローカルでの削除処理は
- visible を False にするだけです
- Tombstone⁵ (墓石)として残ります

リモートへの削除処理の反映も同じで
- visible を False にするだけです
- 同時に複数編集者が削除した場合でも問題ないです
  - True→Falseにしかならないためです

ローカルでの挿入

例えば、AB の間にsite1で 1を挿入したいとします

挿入では、下記のように先行文字（id_cp）と後続文字(id_cn)を指すように 1のW-characterを用意します：
- {(s1,7), 'A', True, cb, (s2,7)}
- {(s2,7), 'B', True, (s1,7), ce}
- {(s1,8),'1',True,(s1,7),(s2,7)}

リモートの編集の反映

文字列 AB にほぼ同時に編集があって

Site1では AとBの間に 1 を挿入
Site2では AとBの間に 2 を挿入
- これはどのように相手に反映されるのでしょうか？

この場合、A12B, A21Bのように異なる文字列になってしまう懸念があります
- → Convergence（収束性）違反

WOOTではどうしているのでしょうか？

W-characterのIDの大小で順序づけします：

「1のID」と「2のID」を比較して
- 例えば (s1,8) < (s2,8)だったら A12B が得られます
  - ※ s1 < s2とします
論文ではもっといろいろなケースについて記載されています

（WOOTの正しさ）

（TODO: 論文では、証明やTLA+など形式手法使ってCCI一貫性モデルを満たしていることを検証しています）

デモ

デモを作ってみました:
- https://github.com/raiich/go-woot

オンラインエディタ実現方法いろいろ

実装パターン: システム構成の観点

P2Pのパターン
クライアント/サーバーのパターン

クライアント/サーバーのパターンのさらなる分類

シングルリーダー
- リーダーの持っているデータを正とする。
- クライアントとリーダーが同期して動く必要があると、もたつき感が出るかも
マルチリーダー
- P2Pと仕組みは似そう

Teletype for AtomはP2Pです
- （ただしピアの把握用サーバーは存在しているようです）

実装パターン: 他の観点

アルゴリズム/データ構造の観点で下記のパターンがあります:

CRDTのパターン
OT（Operational Transformation/操作変換)のパターン

Operational Transformation(操作変換)とは？

同時発生した編集内容をうまく変換することで、全部のサイトで見える文字列を同じにする仕組みです

OTのローカルでの挿入

site1で2文字目に1を挿入したことをサーバーに通知します
site2で2文字目に2を挿入したことをサーバーに通知します

サーバーで変換＆site1へ通知します

サーバーは編集内容を変換してsite1に通知します
- 「３文字目に2を挿入」というように変換します
site1でこれを反映して、文字列 a12b を得ます

サーバーで変換＆site2へ通知します

サーバーは編集内容を変換してsite2に通知します
- 「2文字目に1を挿入」というように変換します
site2でこれを反映して、文字列 a12b を得ます

このような変換をするのが操作変換（OT : Operation Transformation）です
この変換がないと
- 間違った位置に挿入されたり
- 間違った文字が消されたりします

OTとCRDTの関係・比較、その周辺

まず歴史の流れですが

1980年台後半　OTが出てきます
2006年　WOOTの論文が発表されます
- CRDTベースの共同編集の幕開けとなります
- 以降色々なCRDTベースのアルゴリズムが出てきます
2011年 CRDTという単語が出てきます

OTの特徴、CRDTの特徴

OTの特徴ですが

以前からある (1980年代-)
多くで使われています
- Google Docs / Google Wave, ...
実装が難しいらしいです
- 同時に起きた操作を適切に変換する必要があります

CRDTの特徴ですが

新しめの手法です
NW障害が絡んでも変な状態にならない（はず）で、結果整合性を保てます
「良い」と評判ですが、エディタでの本格的な実装は少ない（論文は多い）ようです

CRDT（というかWOOT）の課題ですが

例えば今回のデモプログラムでは文字列を構成するとき連結リスト使っています
- 挿入箇所や削除対象の文字を先頭から探す必要があり、非効率です
もっと効率のいいWOOTでない実装も出ているようです⁶ ⁷ ⁸

（性能）

（TODO: アルゴリズムごとに挿入・削除の性能、O(N)とかのせてどのくらいの性能か示したい）

このように挿入・削除したい文字のIDの特定に時間かかり、WOOTは効率が悪いです
そこでTeletype for Atomでは改善する手法を組み合わせているようです
- 文字のIDの検索を木構造で高速化しているようです⁹

感想

「CRDTはOTの大変な部分を別の場所に移し替えてるだけ」という意見あるようですが・・・

ただ分散システムはちゃんと実装すると難しいと思います
- 「本当は恐ろしい分散システムの話」¹⁰など...

ですが実はCRDTなら分散システムを簡単にできます
- CALM定理¹¹ ¹²
  - ある性質が成り立っているとデータの一貫性を保つことが簡単になる、という定理です
- いわば「本当は簡単な分散システム」です

OTは分散システムとして正しそうかのテスト（リーダー選出など）が大変な気がします
- (Jepsen¹³でさらされるやつ)
また「ちゃんと動作するOT=実はCRDT」みたいな噂も…？

CRDTは問題の難しさを別の場所に棚上げしてるだけ？
- → 開発は楽になりそうです
  - 分散システムの難しさを避けて、難しさを単一マシンの表示の問題に落とせそうです
    - 操作の集合から文字列を構成できるかテストすれば良く、楽そうです

調べたモチベーション

オンラインエディタの仕組みはいろいろな分散システム（例えばオンラインゲームなど）で役に立つかもしれないと思い、調査しました。

オンラインエディタの特徴

複数人の編集、簡単そうだけど実は難しいです
- データ同期でいちいち通信したり、通信でブロックしたりしてはダメです
- NW障害や遅いNWでも使える必要があります

何も仕組みがないときー

例えばリーダーフォロワー形式で組むと、システム全体が同期して動く必要があり、リーダーノードとの通信が頻繁に発生してしまいます

なにかするたびにNWの遅延に影響を受けてもたつき、操作性が悪いです
操作性を良くするには、NWの高速化が必要です

また障害に弱いです
- マスターノードにアクセスできないと何もアクションできない
- マスターノードのフェイルオーバーの時間分は待たされる

何か仕組みがあるときー

NW遅延に敏感でなくなります
- クイックな操作性を実現できます
  - ローカルでの操作＋非同期でやり取り
- 遅いNWでもサービスを使えます
- 遅いNWや一時的なNW障害が起きてもUXを損なわずにサービスを提供できます

またマルチマスター構成も可能で障害に強くなります

オンラインゲームで考えると

遅いNWでもプレイできる
障害に強くすることもできる
マルチマスターにすればマスターが単一障害点でなくなる
- プレイを引き継ぐことができる

ただ実際はハードル高いかもです…

対戦ゲームだと、相手をkillしたら攻撃を受けない仕様が多い
- 相手のマシンで相手が生きているなら、その仕様を実現できない
シュタインズ・ゲートみたく、世界線変動のような見え方になるかも

Atom の 共同編集機能 を支える技術について調べてみた