このブログ記事では、ProseMirrorで使用されている共同編集技術について説明します。ProseMirrorの紹介については、こちらをご覧ください。
共同編集の問題点
リアルタイム共同編集システムでは、複数のユーザーが同時に同じドキュメントを編集する可能性があります。このシステムは、ドキュメントが同期状態を保つことを保証します。つまり、あるユーザーが行った変更が他のユーザーに送信され、彼らのドキュメントに反映されます。
ネットワークを介した変更の伝送には時間がかかるため、この種のシステムの複雑さは、同時発生する更新をどのように処理するかにあります。一つの解決策は、ユーザーがドキュメント（またはその一部）をロックして、他のユーザーが同時に編集できないようにすることです。しかし、このメカニズムではユーザーはロックについて常に意識する必要があり、ロックを取得できない場合（他のユーザーが編集中の場合）は待機しなければなりません。私たちはこれを望んでいません。
同時更新を許可すると、ユーザーAとユーザーBが同時にドキュメントを変更し、互いの変更を認識しない状況が発生します。この場合、最終的なドキュメントの更新方法を調整する必要があります。AとBの行動は互いに影響しない場合（例えばドキュメントの異なる部分を編集する場合）もあれば、相互に影響する場合（同じ単語を変更しようとする場合）もあります。
操作変換（OT: Operational Transformation）
この問題に関する研究は数多く存在します。私は多くの論文を読みましたが、この研究を完全に理解しているとは言えず、もし誤解や興味深い参考文献の欠落に気づかれた場合は、ぜひメールでお知らせください。
この問題に関する研究の多くは、実際には分散システムに関するものです。つまり、中央制御ノードを持たず、ノード同士がメッセージを交換するシステムです。この問題を解決する古典的な方法は「操作変換」と呼ばれる分散アルゴリズムです。これは変更を記述する方法を定義し、次の2つの特性を持ちます：
-
他の変更に対して変更を変換できる。例えば、ユーザーAが親要素のオフセット1に文字「O」を挿入し、同時にユーザーBがオフセット10に文字「T」を挿入した場合、ユーザーAはBの変更を自分の変更に対して変換でき、結果として「T」はオフセット11に挿入されます。これはBの変更位置の前に追加の文字が挿入されたためです。
-
変更がドキュメントに適用される順序に関わらず、最終的に全員が同じドキュメントを持つ。これにより、Aは自分の変更に対してBの変更を変換でき、Bも同様にAの変更を変換できるため、両ユーザーが異なるドキュメントを得ることはありません。
OTシステムは、ローカルの変更を即座にローカルドキュメントに適用し、その後変更を他のユーザーにブロードキャストします。他のユーザーは、ブロードキャストされた変更を受信し、変換して適用します。リモートの変更をどのローカル変更に対して変換すべきかを正確に知るために、システムは変更をブロードキャストする際にドキュメント状態の表現も送信する必要があります。
このプロセスは一見単純に聞こえますが、実装は悪夢です。一度「挿入」や「削除」のような複数の基本的な変更をサポートすると、どの順序で変更を適用しても同じドキュメントが生成されることを保証することが極めて困難になります。
Google Waveで働いていたエンジニア、Joseph Gentleはこう述べています…
残念ながら、OTを実装するのは非常に厄介です。何百万ものアルゴリズムがあり、それらのほとんどは学術論文にしか存在しません。これらのアルゴリズムを正しく実装するのは非常に困難で時間がかかります。
集中化
OTメカニズムの設計上の複雑さの多くは、変更をどのように配布するかという要件に由来します。分散システムは、実際的にも理論的にも素晴らしい特性を持ち、開発において非常に興味深いものです。
しかし、「変更を処理する中心」を導入することで、複雑さを大幅に減らすことができます。正直なところ、GoogleがGoogle Docs（集中型システム）でOTを使用していることは、私には非常に不思議です。
ProseMirrorのアルゴリズムは集中型です。すべてのユーザーが接続する単一の変更処理センターが、変更を適用する順序を決定します。これにより、共同編集システムの実装が比較的容易で理解しやすくなります。
実際、この「集中化」特性がOTアルゴリズムを分散的に実行する上で非常に大きな障害になると私は考えていません。[Raft](https://en.wikipedia.org/wiki/Raft_(computer_science)のような合意アルゴリズムを使用して、中央集権的なサービスではなくアービターを選出することもできます（ただし、私は実際にこの方法を試したことはありません）。
ProseMirrorの共同編集アルゴリズム
OTと同様に、ProseMirrorも変更ベースの語彙を使用し、変更を相互に変換します。ただしOTとは異なり、異なる順序で変更を適用しても同じドキュメントが生成されることを保証しようとはしません。
集中化されたサービスを利用することで、すべてのクライアントが同じ順序で変更を適用することも容易に実現できます。コードのバージョン管理システムで使用されるメカニズムと同様の仕組みを採用できます。クライアントが変更を持っている場合、その変更をサーバーに push しようと試みます。サーバーがその変更が最新バージョンに基づいていると判断した場合、変更は受け入れられます。そうでない場合、クライアントはまず他のクライアントの変更を pull し、サーバーへのプッシュを再試行する前に自分の変更を rebase する必要があります。
gitとは異なり、このモデルではドキュメントの履歴は線形であり、ドキュメントの特定のバージョンは単純に整数を使用して表現できます。
さらにgitと異なる点は、すべてのクライアントが常にドキュメントの新しい変更をプル（またはプッシュして監視）し、ネットワークが許す限り迅速にサーバーの状態を追跡することです。
唯一難しい部分は、他の人の変更を自分の変更にrebaseすることです。これはOTが行う変換と非常に似ています。ただし、これはクライアント自身の変更に対して行われ、リモートサーバーの変更に対してではありません。
位置マッピング
しかし、OTは他人の変更に対して変換を行うのに対し、ProseMirrorは_position map_（位置マッピング）と呼ばれる派生データ構造を使用して変換を行います。ドキュメントに変更を適用するたびに、新しいドキュメントと前述のマッピングが得られ、これを使用して古いドキュメントの位置を新しいドキュメントの対応する位置に変換できます。マッピングの最も顕著な使用例は、カーソル位置を調整して同じ「概念的」位置に留めることです。もしカーソルの前に文字が挿入された場合、カーソルは周囲のテキストとともに1つ前（右）に移動する必要があります。
変更の変換は完全に位置マッピングに基づいて行われます。これは実際に良いことであり、特定の変更タイプの変換コードを書く必要がないことを意味します。各変更には、from、to、atとして表現される1つから3つの位置情報が関連付けられています。与えられた他の変更に対して変更を変換する場合、これらの位置は他の変更の位置マッピングを通じてマッピングされます。
たとえば、位置5に文字が挿入された場合、その挿入に対して変換を行うと、「位置10から14を削除」する変更は「位置11から15を削除」する変更に変わります。
各変更の位置は、最初に適用されたドキュメントバージョンが同じ場合にのみ意味を持ちます。位置マッピングは、変更前後の2つのドキュメントバージョン間の位置のマッピングを定義します。異なるバージョンに変更を適用するためには、自身のバージョンとターゲットバージョン間の変更を通じて段階的にマッピングする必要があります。
（簡単にするため、例では位置表現として整数を使用します。ProseMirrorの実際の位置は、段落内の整数オフセットに加えて、ドキュメントツリー内のその段落のパスで構成されます）
位置のリベース
クライアントがリモートにプッシュされていない複数のローカル変更を持っている場合、興味深いことが起こります（朱一旦風に）。この時点で他の人の変更が入ってくると、すべての未送信のローカル変更をこれらの変更に基づいて変換する必要があります。ローカル変更_L1_と_L2_を持ち、それらをリモート変更_R1_と_R2_にリベースすると仮定します。ここで_L1_と_R1_は同じドキュメントバージョンからの変更です。
まず、R1とR2を元のバージョンのドキュメントに適用します（クライアントは、現在表示しているドキュメントバージョン（未プッシュの変更を含む）と、これらの変更がまだ含まれていない元のバージョンを追跡する必要があります）。この操作により、2つのマッピング_mR1_と_mR2_が作成されます。
訳者注：以下の部分は理解が難しいため、図を描くとより直感的かもしれません。簡単に言えば、L2はL1によるドキュメントの変更を位置マッピング（位置調整）した後にドキュメントを変更したものです。L2を正しくリベースするためには、まずL1およびL1以前（つまりR1とR2）のドキュメントへの変更を影響を受ける位置にすべてマッピング（調整）する必要があります。これによりL2は正しい位置マッピングを取得し、正しい位置でドキュメントの変更を開始できます。
L1_を_mR1_と_mR2_を通じてマッピングしたバージョンである*L1*に単純に前方マッピングできます。しかし、L2は初期ドキュメントバージョンに_L1_を適用した後のドキュメントに基づいて変更されているため、L2に対しては（注：ここで_L1_に対しては前述の単純なマッピングで十分ですが、_L2_の処理には以下の手順が必要です）、まずL2*を_mL1（_L1_を適用して作成されたマッピング）で後方マッピング（つまり履歴をロールバックし、_mL1_の逆操作を行います）する必要があります。これによりドキュメントは_R1_開始時のドキュメントと同じになり、mR1_と_mR2_を通じて_L2_をマッピングし、最後に_mL1**（前述の単純な_L1*_適用によって生成されたマッピング）を通じてマッピングできます。これでL2*が得られ、_L1*_を適用した後のドキュメントに適用できます。これで、2つの変更を他の2つの変更にリベースできました。
訳者注：以下の段落において、「位置5に2文字を挿入」は前述のL1に相当し、「2文字の間（位置6）にさらに挿入」はL2に相当します。したがって、L2をリベースする際には、まずmL1を通じてL2の挿入位置を元のドキュメントにロールバックする必要がありますが、この時点ではドキュメントにL2がマッピングできる位置が存在しません。なぜなら、その位置はまだ存在していないからです。
削除操作のマッピングと後方マッピング（履歴ロールバック–訳者注）による挿入操作は情報を失います。位置5に2文字を挿入し、その後別の人物が位置6（先に挿入された文字の間）に挿入した場合、後方マッピング（履歴ロールバック、前述のL2–訳者注）を行い、その後最初の挿入操作を通じて前方マッピングすると、挿入した2文字の前または後の位置に移動することになります。なぜなら、これらの2文字の間の位置は、まだそれらが存在しないドキュメントでは表現できないからです（まだ挿入されていない文字の正確な位置をどのように表現するか？–訳者注）。
訳者注：以下の段落は本記事の核心部分です。マッピング時に追加の逆マッピング情報を提供することで、後方マッピング（履歴ロールバック）時に存在しない位置にマッピングする必要が生じた場合、まずその位置の内容を復元し（そのマッピングのミラーを使用）、マッピングを行います。それ以前のマッピングが完了した後、このマッピングをスキップします（内容の復元時にマッピングが既に完了しているため）。マッピングのミラーとマッピング内容が同じサイズを維持していることが必須です（当然ですが、そうでないと位置計算が誤ります）。
この問題を修正するため、ProseMirrorの協調編集システムはマッピングパイプラインを使用します。これらは単なる一連のマッピングではなく、どのマッピングが互いのミラーであるかという情報も保持しています。ある位置がこれらのパイプラインを通過する際に、その位置周辺の内容を削除するマッピングに遭遇した場合、システムはパイプラインを前方（つまり、その位置にまだ遭遇していない以前のマッピング–訳者注）にスキャンし、そのマッピングのミラーを探します。そのようなマッピングが見つかった場合、その位置に前方マッピングジャンプ（通常の位置調整–訳者注）を行い、削除された内容内の相対オフセットを使用して、そのマッピングが挿入した内容内の位置を復元します。削除操作のマッピングミラーは、挿入操作のマッピングミラーと同じ内容サイズを維持する必要があります。
マッピングの方向
内容が挿入されるたびに、この明確な挿入点を2つの異なる位置（どちらも意味のある位置）にマッピングできます：挿入内容の前、または後です。前者が適切な場合もあれば、後者が適切な場合もあります。ProseMirrorの位置マッピングシステムは、開発者が好みの方向を選択できるようにしています。
訳者注：以下の説明では、ドキュメントが
abcで、aの後、bの前の位置に文字xを挿入すると仮定しています。この場合、変更されたfromとtoはどちらも1になります。挿入内容の後、fromは前方（左方向）にマッピングされても1のまま変わらず、toは後方（右方向）にマッピングされると2になります。
これが、変更に関連する位置に複数の異なる位置情報が含まれる理由です。変更がfromとtoの位置情報を持つ場合、例えばドキュメントの内容を削除したりスタイルを設定したりする場合、その位置の前または後に内容がある場合、それらの内容は変更に含まれないべきです（これらの内容は変更発生後に位置をマッピングするだけでよい–訳者注）。したがって、from位置は前方（左方向）にマッピングされるべきであり、to位置は後方（右方向）にマッピングされるべきです）。
変更がそれを完全に含むマッピングを通じてマッピングされるとき、例えば位置5に文字を挿入し、その後その位置が2から10を削除して作成された変更を通じてマッピングされると、位置5に文字を挿入するという操作全体が単純に破棄されます。そのコンテキストが存在しなくなるからです。
変更のタイプ
ProseMirrorにおいて、原子的な変更は_step_（ステップ）と呼ばれます。ユーザーの視点では単一の変更に見えるものでも、実際には複数のステップに分解される場合があります。例えば、テキストを選択してEnterキーを押すと、エディタは選択テキストを削除する_delete_ステップを生成し、その後現在の段落を分割する_split_ステップを生成します。
以下はProseMirrorに存在するステップのタイプです：
addStyleとremoveStyleはドキュメントにインラインスタイルを追加または削除します。splitはノードを2つに分割します。例えば、ユーザーがEnterキーを押したときに段落を分割するために使用できます。単一のat位置情報のみが必要です。joinは隣接する2つのノードを結合します。この操作は同じタイプのコンテンツを含むノードに対してのみ有効です。結合する2つのノードの末尾と開始位置を指すために、fromとtoの位置情報が必要です（これは意図したノードを正しく結合するためです。もし同時にこれらのノードにコンテンツが挿入された場合、結合操作は無視されます）。ancestorはノードのタイプを変更したり、祖先を追加/削除するために使用されます。リストをラップしたり、段落を見出しに変換する場合などに使われます。ノードの開始位置と終了位置を指すfromとtoの位置が必要です。replaceはドキュメントの一部を0個以上のノードで置き換え、必要に応じて互換性のあるノードを切り口で縫合します。削除範囲を定義するfromとtoの位置、および新しいノードを挿入する位置を指定するatの位置が必要です。
上記のタイプの中で、最後のものが最も複雑です。当初はこれを削除と挿入の2つのステップタイプに分割しようと考えました。しかし、置換ステップで作成される位置マッピングはステップをアトミックに扱う必要があるため（位置は_すべて_の置換コンテンツから導出されなければなりません）、単一のステップとして扱うことでより良い結果を得ました。
操作の意図
リアルタイム共同編集システムの必須特性は、変更の_意図_を保持しようとすることです。変更の「マージ」はユーザーの介入なしに自動的に行われるため、ドキュメントへの変更がリベースされて意図しない結果になることは非常に煩わしいものです。
これらの編集ステップとそのリベース方法を定義する際、リベース時に不自然にならないように努めました。ほとんどの場合、変更は互いに上書きされず、介入も不要です。しかし、変更が重複する場合、マージ結果が適切であることを保証しなければなりません。
時には、変更を単純に破棄しなければならない場合もあります。段落に入力している間に他のユーザーがその段落を削除した場合、入力の意味のあるコンテキストが失われ、その位置への挿入は無意味なドキュメントフラグメントを作成します。
2つのリストを結合しようとしても、他のユーザーがリストの間に段落を挿入した場合、操作は実行不可能（隣接していないノードは結合できません）なので破棄されます。
他のシナリオでは、変更が修正されても意味を保つ場合があります。位置5から10の文字を太字にし、他のユーザーが位置7に文字を挿入した場合、最終的には位置5から11が太字になります。
最後に、変更が重複しても互いに影響しない場合があります。単語をハイパーリンクに設定し、他のユーザーが同じ単語を太字にした場合、両方の変更が元のドキュメントに適用されます。
オフライン編集
リアルタイム共同編集では、変更を静かに修正したり破棄したりすることは問題ありません。この場合、フィードバックはほぼ即時です——編集している段落が消えたのを見れば、誰かが削除したことが分かり、自分の変更も消えたとわかります。
オフライン編集（中央サーバーに接続せずに編集を続ける場合）やブランチワークフローの場合、大量の編集を行った_後で_、その間に他のユーザーが編集したドキュメントにマージする場合（他のユーザーがどのように編集、削除、大量のコンテンツを挿入し、その後最初のコンテンツを削除したかなど）、ここで説明したモデルは役に立ちません（OTも同様です）。このシナリオでは、（このモデルとOTは同様に）編集のコンテキストが既に削除されている場合、多くの編集作業が静かに削除されるか、2人のユーザーが同じ文を異なる方法で編集した場合に奇妙なテキストの組み合わせが作成される可能性があります。
このような場合、差分ベースの実装の方が適しているかもしれません。自動マージはできない可能性があります——衝突を識別し、ユーザーに解決を任せる必要があります。例えば、gitがユーザーに行わせるように。
取り消し履歴
共同編集システムでは、取り消し履歴をどのように実装すべきでしょうか？広く受け入れられている答えは、単一の共有履歴を_決して_使用すべきではないということです。編集を取り消す場合、ドキュメントの最後の編集ではなく、_あなた_が行った最後の編集操作を取り消すべきです。
これは、単純に以前の状態にロールバックしてドキュメント履歴を実装する方法が機能しないことを意味します。変更を取り消す（その間に他のユーザーも変更を加えている場合）ことは、これまでに見たことのない新しい状態を生み出します（つまり、ドキュメント履歴のどの状態でもありません）。
これを実現するためには、反転可能な変更（複数のステップ）を定義する必要があり、その反転は元のステップを打ち消す変更を表す新しいステップを生成します。
ProseMirrorの取り消し履歴は、反対のステップを蓄積し、現在のドキュメントバージョンとの間のすべての位置マッピングも追跡します。現在のドキュメントバージョンに逆マッピングするためには、これが必要です。
しかし、不利な点として、ユーザーが変更を加えた後に操作を中断し、その間に他の人がドキュメントを変更した場合、そのユーザーの変更を現在のバージョンのドキュメントにマッピングする位置情報が無制限に蓄積されてしまいます。この問題を解決するため、履歴は定期的に_圧縮_され、逆方向の変更を前方にマッピングして、再度現在のドキュメントから編集を開始できるようにします。これにより、中間過程の位置マッピングは破棄されます。
ブログ主より：
人生の重要な選択に直面したとき、最善の方法を誰かが教えてくれて、貴重な時間を無駄にせずに済めばと、私はよく願っています。だからこそ、自分の経験を踏まえて頻繁にブログを書き、広大なインターネットのこの小さな片隅に、私にとって一度きりの人生経験を記録し、助けを求める人々の力になれればと思っています。
