コラボレーティブ編集についての嘘、第1部：オフライン編集のためのアルゴリズム
(moment.dev)- Momentが中核テキストエディタ向けのコラボレーティブ編集を評価した結果、CRDT系およびOT系アルゴリズムはオフラインでの直接衝突において、ユーザーがデータ破損とみなしうるマージ結果を生み出すことがある
- Aliceが文全体を削除し、Bobが
ColorをColourに変えるという単純なケースでも、最終文書に文字uだけが残るなど、人間が意図していない結果が発生する - Momentのユースケースでは、試した直接衝突の約**20〜30%**が受け入れがたいものであり、発生頻度と否定的な反応を踏まえると、プロダクト体験として正当化するのは難しいと判断した
- Yjs、ShareJS、Peritextはオフライン編集や長時間遅延したコラボレーション、独立コピーの自動マージをうたっているが、アルゴリズムはユーザーの意図や順序を知ることができず、ヒューリスティックに依存する
- オフラインのコラボレーティブ編集はアルゴリズムだけの問題ではなく、UI/UXの問題に近く、gitのマージUIやInk & Switchのcollaborative historyのように、人が読んで判断できるマージ体験が必要である
Momentのコラボレーティブ編集評価で明らかになった限界
- 2024年初頭、Momentは中核テキストエディタで使うコラボレーティブ編集システムの調査を始めた
- 複数のアルゴリズムは、オンラインでの同時編集だけでなく、ユーザーが時間制限なくオフラインで編集し、その後再びオンラインになったときに変更を自動マージするオフラインのケースまで解決すると主張している
- 論文や発表を見た当初は、コラボレーティブ編集コミュニティが問題全体に対する「正しい答え」に到達したのだと期待していた
- 評価の過程で、CRDT系およびOT系アルゴリズムは直接的な編集衝突を直感的でない形で解決し、ユーザーはその結果をデータ破損として受け取った
- オフライン編集では直接衝突の可能性が大きく高まるため、こうしたアルゴリズムだけではMomentが望むオフライン編集体験を作るのは難しかった
削除とスペル修正が衝突した単純なケース
- AliceとBobはどちらもオフラインの状態で同じ文書を編集している
- 文書には
The Color of Pomegranatesというテキストがある - Bobは
Colorの綴りをイギリス英語のColourに変え、Aliceはテキスト全体を削除する - 2人が後でオンラインになると、2つの編集は衝突し、システムはどちらの編集が先だったのか分からないまま調整しなければならない
- このケースでは、AliceとBobは最終的に文字
uだけが入った文書を得る- これは有効な文でも有効な単語でもない
- ユーザーはこのような結果を、Momentが自分のデータを破損させたものとして受け取る
直接衝突の異常な結果は珍しくない
- この衝突は些細で直接的な編集衝突だが、人気のあるコラボレーティブ編集アルゴリズムが対応していると見なせる範囲内にある
- 実際の結果は人が自分で書くことのない文書であり、Momentのプロダクトがデータを破損させたものと解釈された
- ユースケースごとに異なるが、Momentが試した直接衝突のおよそ**20〜30%**は、オフライン編集のユースケースでは受け入れがたい結果だった
- 否定的なフィードバックと発生頻度を合わせて考えると、このような結果をユーザーに説明し正当化するのは難しいと判断した
ツールがうたうオフライン編集対応
- 当初は、このような結果が出たことで、これらのツールが提供すると言っている意味を自分たちが誤解していたのだと思った
- しかし各プロジェクトの説明は、そのシナリオがサポート範囲内であると読めるものだった
- Momentは今もこの問題の解決策を探しているが、実際に見たエラーの頻度と種類をこうした主張と整合させるのは難しいと考えている
調整のないアルゴリズムの根本的な限界
- 評価が進むにつれて、これらのアルゴリズムはMomentが望む動作をしないという結論に達した
- 残る問いは、貢献によって修正できる問題なのか、それともアルゴリズムの根本的な限界なのかということだった
- 根本的な問題だと考える理由は3つある
- アルゴリズムはAliceとBobの意図を知ることができず、2人が何を望んでいたのかをメールで尋ねたり、GitHubのPull Request UIのようにレビューしたりできない
- Aliceの全文削除という提案とBobのスペル修正という提案を受け取り、ヒューリスティックで結果を決めなければならない
- 文字単位で動作し、出力に対しては非常に弱い保証しか提供しない
- AliceとBobは、相手が何をしているか知っていれば、編集するかどうかを違った形で判断していたかもしれない
- こうしたアルゴリズムは、因果的な順序に従えないという問題ともつながっている
オフライン編集はUI/UXの問題に近い
- Momentは、難解なアルゴリズムを実装すれば真のオフライン編集も副次的にサポートできるだろうと期待していたが、評価後はそうは考えにくくなった
- ユーザーがアルゴリズムの結果をデータ破損と見なしたのは妥当であり、異常な結果はアルゴリズムそのものに内在していて、十分な頻度で発生するため現実の問題になりうる
- 別の解釈としては、コラボレーティブ編集にかなりのUI/UXリソースを投入しなければならないということでもある
- アルゴリズムは問題を完全には解決できないが、解決策の一部としての役割は果たせる
gitのマージUIと研究の方向性
- すでに広く採用されている文書マージUIとして
gitがある - 研究上の問いは、この体験をどこまでより利用しやすく、理解しやすく、自動化できるかに近い
- 2009年ごろには、gitが変更を自動マージする際に使うアルゴリズムについて多くの議論があった
- gitはMyers O(ND) diff algorithmを採用しており、このアルゴリズムはもともと主に生物学者がBLAST系のシーケンス解析に使っていたものだった
- Bram Cohenはdiffの結果が直感的でないと考え、patience diff algorithmを作成し、これは現在は終了したgitの競合ツールbzrに採用された
- 当時の議論は人間が読むdiffを作ることに焦点があったが、現在の議論はアルゴリズムが人の介入なしにその結果を達成できるかどうかにより近い
- Ink & Switchのcollaborative historyのように、コラボレーティブ編集をUI/UXの問題として扱う研究が進んでいる
1件のコメント
Hacker Newsの意見
Eg-walkerとShareJSの作者です。記事は私の仕事に反対しているようなトーンに見えるかもしれませんが、実際には私は全面的に同意しており、HNでも数年前から同じ話をしてきました。
現在のリアルタイム共同編集ツールは、全員がオンラインで一緒に編集する場合にはうまく合いますが、ユーザーがオフラインや長期間維持されるブランチで編集するなら、マージ時に衝突表示と手動レビューの選択肢が必要です。特にコードではなおさらです。
幸い、egwalkerのようなアルゴリズムは、全ユーザーの文字単位の編集履歴と因果順序、つまりGit DAGのような変更順序を保存するため、Gitよりはるかに多くの情報を持っています。したがって、ブランチのマージ時に衝突範囲を検出して表示するCRDTを作れるはずで、ユーザーに手動で解決させることもできるはずです。
アルゴリズム的には興味深いものの、十分に解ける問題に見えますし、不思議なことにテキスト編集の分野ではまだほとんど誰も試みていないようです。この分野に独創的で価値ある貢献をしたいなら、CRDTエコシステムに欠けている重要なピースなので、誰かにやってみてほしいです。
[1] このコメントの下のほう: https://news.ycombinator.com/item?id=19889174
次に面白い課題は、衝突解決そのものをめぐる衝突が起きる場合です。
こうしたシステムを評価すること自体が十分に難しい技術課題なので、多くのチームが苦労するだろうと思います。だから実用的な助言を受ける資格がありますし、私たちももっと早く知っていればよかったと感じています。
難しいのは、衝突が解決済みだと示すことです。CRDTにフィールドを1つ追加する程度で済むかもしれませんが、そうなるとそれもアルゴリズム的な解法と見るべきかは分かりません。
[1] https://josephg.com/blog/crdts-go-brrr/
プログラムコードの編集なら、マージ結果が有効なプログラムであることを期待するため、はるかに深い沼になります。JetBrainsでASTベースのマージによってこの問題を解こうとしたプロジェクトがありましたが、はるかに深く掘り下げたあと、やる価値がないと判断したと聞きました。
人間が使う文書で許容する「オフライン編集」はコメント追加だけです。編集でもなく、自動マージもありません。
自動化対象であるソースコードの「オフライン編集」にはGitを使いますが、Gitはマージを解決すると装うことはせず、リビジョンを見せるだけです。マージは人間が監督するか、専門の自動化が最善の推測で行う作業であり、成功したかどうかの確認には依然としてレビューとテストが必要です。
機械的なマージアルゴリズムは、衝突の種類によって得手不得手がありますが、結局どんなCRDTも、マージされたテキストがユーザーの言いたかった内容かどうかを判断することはできません。
Upwellingの論文では、文章作成における意味的衝突と文法的衝突と呼ばれる違いをより詳しく扱っています: https://inkandswitch.com/upwelling/
本格的な共同作業は、結局は文書レビューの問題でもあると感じます。ジャーナリズムや科学出版では特にそうで、議事録ではたいてい無視してもよいかもしれません。
Upwellingにもリンクしようとしたのですが、名前を思い出せず、締め切りのため別のリンクで代用しました。
CRDT実装のもう一つの暗い側面はインフラ負荷です。以前この内容について深く書いたことがあり[0]、Supabaseも数年前のPostgres向けCRDT拡張の記事[1]で、私の経験的な結果と同じ結論に達していたと知ってうれしく思いました。
CRDTを使うならRedisのようなものを使うか、メモリ使用量を考えるだけでつらいですが、MyRocks[2]やRocksDB/LevelDBベースを使うほうがよいです。何をするにせよ、RDBMS、特にPostgresをバックエンドに置くべきではありません。
[0]: https://news.ycombinator.com/item?id=40834759
[1]: https://supabase.com/blog/postgres-crdt
[2]: http://myrocks.io
この記事の観察は正確です。CRDTは分散データ構造のための優れた形式モデルですが、すべての衝突を自動的に解決しなければならないという考え、名前の通り衝突のない複製データ型という発想にはずっと違和感がありました。
この記事が示しているように、これは見込みのない試みだと思います。必要なのは、衝突を共有し協働で解決できる、きちんとした構造的表現であり、ユーザーに制御権を返し、解決プロセスを支援することです。私の好きな論文の一つである “Turning Conflicts into Collaboration” [1] は、このアイデアを説得力のある形で扱っています。
進行中の博士課程研究として、格子理論に基づく構造的な衝突表現の形式モデルである “Lazy Merging: From a Potential of Universes to a Universe of Potentials” [2] を開発しました。偶然にもこれもCRDTですが、衝突を自動解決しようとはせず、協働文書の中に表現します。数学的にアプローチしたことで、繰り返しマージされた既存の衝突の後でも、マージの完全性、最小性、一意性といった強い性質を保証する単純な概念モデルに到達でき、マージ計算も非常に簡単です。
[1] https://doi.org/10.1007/s10606-012-9172-4
[2] https://doi.org/10.14279/tuj.eceasst.82.1226
衝突は複雑な概念であり、“conflict-free” は結果を記述する言葉としては技術的に正しいものの、この記事や上の内容から分かるように誤解を招き得ます。
可換性とは、Bobが [Bob, Alice] の順で変更を適用し、Aliceが [Alice, Bob] の順で適用しても、両者が同じ文書に到達するという性質です。より高い抽象レベルで、意味のある形で文書が「衝突なし」である、という意味ではありません。
複数の異なる主体が、リアルタイムの調整なしに同時に一つのデータ片に対する権限を持つという概念は、一般には解けないと思います。これは分散システムですでに学んだ教訓であり、文書の分散編集を考えると、この記事でもよく表れています。
飛行機のコックピットにおける二重入力、育児、そのほか思いつく別の例にも同じ原理が当てはまりそうです。
そしてこれを「解ける」と呼ぶのもおかしな話です。現時点では、地球上のかなりの部分が、LLMの混沌とした出力に計算の最終結果を決めさせることに近いことを考えているように見えるからです。
協働テキスト編集でよく使われるアルゴリズムであるCRDTとOTは、編集操作が何を行い、どのように相互作用するかについて、厳格な代数的要件を持っています。
そのため、サーバーが「Colour」の例をUX上合理的に処理できるほど賢かったとしても、楽観的なクライアント側編集のための対応するCRDT/OTを設計するのは非常に困難です。
CRDT/OTを使わなければ回避できます。たとえば、サーバーが受信順に操作を処理し、望ましいUXロジックを適用し、クライアントはその上で楽観的編集を許可するためにrebase/予測戦略を使う、という方式です。参考: https://doc.replicache.dev/concepts/how-it-works
これをテキスト編集に適用するうえでの難しさもありますが、ここで議論しているCRDT/OTの問題とは別です。
数学的・因果的・エントロピー的な衝突概念が、意味的衝突と混同されたために、こういうことが起きているのだと思います。私も以前、逆方向に同じ間違いをして、自分が何を言っているのか分かっていないとはっきり言われたことがあります。
ツリーを考え始めると、さらに厄介になります。たとえばyJSはJSON文書上で動作します。UIが浅いレベルだけを表示し、深いレベルを展開していない状態なら、ユーザーは削除された編集をまったく見られない可能性があります。
衝突を保持するCRDTの種類、記憶ではレジスターが複数の値を持てる場合が最も有望に見えます。ユーザーにはそうした衝突を提示する必要があり、完全に視覚的に見せることもできます。履歴をざっと確認できるようにすることも、奇妙なことがどう起きたのか、あるいは自分の変更がどう消えたのかをユーザーが把握できる実用的な代替案に見えます。
Torvalds 自身も、自動マージで達成できることについてはかなり悲観的だったと記憶している。そしてその判断は正しかった
Git は、十分に賢いアルゴリズムが自動的に正しいことをしてくれる形で、バージョン管理システムが「マージ問題を解決」できる、あるいはそうすべきだという考えを拒否した、と述べていた
オフライン編集が UI/UX の問題だという点には同意する。より深い原因は、古い解法を踏襲するコンピューティング業界の習慣と、「一般に 5 ポンド袋は 10 ポンド袋より扱いやすいのだから、10 ポンド分の物を 5 ポンド袋 1 つに入れるべきだ」という信念である
「テキストエディタ」の基本像は Mosaic textarea、MacWrite、あるいはその中間あたりなので、普通は最小限の変更でマージをその上に付け足そうとする。メニュー項目や小さなダイアログのいくつかのオプションで作る、という具合だ。メニューの奥深くに GUI のマージ支援があっても、プログラマ向けの diff/merge ホラー程度のものか、霧の中で船を操るような危うい取り消し線ベースのビューにとどまる
しかしオフライン協業のあるテキスト編集では、部分的な手動マージがプロセスの中心であり、エディタ設計の中心にもあるべきだ。残念ながら MacWrite は抜け出しにくい局所最適である
たとえば「カーゴカルト的な踏襲」や「古い解法」を語る人の次の言葉は、しばしば「コードをテキストとして編集するのではなく、構文木として編集せよ」だが、問題はそのままだ。「文字」を「文」に置き換えればよいだけである
Bob が
if文のelse分岐に 1 行を追加し、Alice がelse分岐ごと文全体を削除した場合、賢いシステムは何をすべきなのか？全体としては、このアプローチが正しいという点で同意しているようだ
質問やフィードバックを受け付ける。1〜2時間は会議に入っているが、こういう話をするのは好きだ。ここでもメールでも、都合のよい方に送ってほしい: alex@moment.dev
Git は明示的な同意なしにローカル変更を自動で混ぜ込まない。bzr もそんなことは夢にも思わなかったはずだ。しかし Google Docs のようなものは喜んでそうする
これまでの進展は素晴らしいし、早期アクセスプログラムもうまくいくことを願っている
differential sync(https://neil.fraser.name/writing/sync/) を実装した。他のものは理解できず、grugnotes.com アプリではこれが最も単純に見えたからだ
アプリはかなり粗く、完全なリアルタイムでもないが、例のマージは誰が先にオンラインに戻っても正しく処理する。削除が先にオンラインに来た場合、
colourバージョンは捨てられ、編集履歴にも保存されないもっと多くの問題があるだろうし、2 人を超えるユーザーの場合にどうなるかも分からないが、自分の用途には満足している