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

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

---

## はじめに

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

---

### [Teletype (beta) for Atom](https://teletype.atom.io/)とは

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

---

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

---

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

---

#### 編集フェイズ

![同時編集.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148979/0172393a-674e-cb26-ae2c-f90a9643a139.png)

---

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

---

#### 反映フェイズ

![同時編集反映.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148979/8f150ad5-fdc4-f4ba-953f-a3a7653029eb.png)

---

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

---

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

---

#### UXにおける難しさ

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


---

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

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


---

#### そこで

- オンラインエディタはCCI[^consistency] [^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] [^WOOT0] について、ざっくりメモを残そうと思います

---

## WOOTとは？

---

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

---

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

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

---

- AppleのNoteアプリ(で使われているという噂)
	- 複数デバイスでの編集を同期

- ブックメーカー、ゲームのオンラインチャット
	- RedisやRiakのCRDTデータ型を使用

---

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

---

- 文字の挿入/削除の「操作の集合」から文字列を構成してユーザーに見せます
![set-to-string.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148979/d62c2f50-9eb5-3734-0751-409c8414836e.png)

---

#### この各文字を表すとき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[^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 

<script id="asciicast-4H8lNF91p0MdqkfarUXoKCXMY" src="https://asciinema.org/a/4H8lNF91p0MdqkfarUXoKCXMY.js" async></script>

[![asciicast](https://asciinema.org/a/4H8lNF91p0MdqkfarUXoKCXMY.svg)](https://asciinema.org/a/4H8lNF91p0MdqkfarUXoKCXMY)

---

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

---

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

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

---

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

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

---

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

--- 

#### 実装パターン: 他の観点

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

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

---

## Operational Transformation(操作変換)とは？

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

---

#### OTのローカルでの挿入

![OT2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148979/d8808081-a297-9ffb-7cfe-da63ecdfaf0d.png)

---

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

---

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

![OT3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148979/2fcb7d0e-b74b-793b-0bb7-2c550990527b.png)

---

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

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

![OT4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/148979/3401217a-2766-3c0b-6db9-3995687882b2.png)

---

- サーバーは編集内容を変換して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でない実装も出ているようです[^RGA] [^Logoot] [^alchemy-book]

---

#### （性能）

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

---

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

---

## 感想

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

---

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

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

---

- OTは分散システムとして正しそうかのテスト（リーダー選出など）が大変な気がします
    - (Jepsen[^Jepsen]でさらされるやつ)

- また「ちゃんと動作するOT=実はCRDT」みたいな噂も…？

---

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

---

## 調べたモチベーション

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

---

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

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

---

### 何も仕組みがないときー

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

---

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

---

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

---

### 何か仕組みがあるときー

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

---

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


---

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

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

---

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

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

[^WOOT0]: [Real time group editors without Operational transformation](https://hal.inria.fr/file/index/docid/71240/filename/RR-5580.pdf)
[^WOOT]: [Data consistency for P2P Collaborative Editing](https://doi.org/10.1145/1180875.1180916) 
[^undo]: [Supporting String-Wise Operations and Selective Undo for Peer-to-Peer Group Editing](https://doi.org/10.1145/2660398.2660401) 
[^responsiveness]: [High Responsiveness for Group Editing CRDTs](https://doi.org/10.1145/2957276.2957300) 
[^consistency]: [Operational transformation - Wikipedia](https://en.wikipedia.org/wiki/Operational_transformation#Consistency_models)

[^CCI]: [Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems](http://www.cs.cityu.edu.hk/~jia/research/reduce98.pdf)
[^CALM]: [Keeping CALM: When Distributed Consistency is Easy](https://arxiv.org/abs/1901.01930)
[^RGA]: RGAという手法
[^Logoot]: Logootという手法
[^alchemy-book]: Logootを使った実装： https://github.com/rudi-c/alchemy-book
[^Jepsen]: [Jepsen](https://aphyr.com/tags/jepsen)
[^kumagi]: [本当は恐ろしい分散システムの話](https://www.slideshare.net/kumagi/ss-81368169)
[^CALM]: [An Overview of the CALM Theorem - RISE Lab](https://rise.cs.berkeley.edu/blog/an-overview-of-the-calm-theorem/)
[^CALM0]: [1901.01930 Keeping CALM: When Distributed Consistency is Easy](https://arxiv.org/abs/1901.01930)
[^Tombstone]: [Tombstone (data store) - Wikipedia](https://en.wikipedia.org/wiki/Tombstone_(data_store))