テキストエディタの共同編集機能はどのように実装されているのか

Webページに簡単に埋め込むことができるオープンソースのテキストエディタであるCKEditorの開発元が、リアルタイム共同編集機能を実装するにあたってのこだわりや工夫について公式ブログに投稿しています。

Lessons learned from creating a rich-text editor with real-time collaboration
https://ckeditor.com/blog/Lessons-learned-from-creating-a-rich-text-editor-with-real-time-collaboration/

CKEditorは以下のような見た目のツールです。

共同編集機能を実装するにあたり、CKEditorでは以下の点にこだわったとのこと。

・コンテンツをロックしない
同時に複数人が同じ段落や表、リストなどを編集できるようにする。

・自動で競合を解消してくれる
同じ場所が編集された場合に自動でうまく競合を解消してくれる。

・全ての機能が使える
共同編集中はテーブルが使えなくなったり、リストが入れ子にできなくなったりというように基本機能しか使えなくなるということがない。

・意図をくんだ競合解消
ユーザーの意図した通りに競合が解消される。

ブログによると、「同じ部分を同時に複数人が編集した場合の挙動をどうするか」が共同編集機能の問題のほぼ全てであるとのこと。たとえば、2人のユーザーが同じ段落の一部を削除したと考えてみます。下図では元の文「LOREM IPSUM」からユーザーAが「ORE」、ユーザーBが「IP」を削除した時の様子が表されています。どの文字を削除したのかを「2文字目から3文字を削除」や「7文字目から2文字削除」というような形式でやり取りすると、編集によって元の文からズレてしまっているため別の文が表示されてしまいます。

上記のような競合を解消するには「オペレーショナル・トランスフォーメーション(OT)」「コンフリクト・フリー・レプリケート・データ・タイプ」という2つの手法が有力な候補です。これらの手法を利用することで操作の順序に関係なくエディタを同じ内容にすることができます。このうち、CKEditorでは前者の「OT」を採用したとのこと。ただし、基本的なOTはプレーンテキストを表現するのに使われる線形データモデルでの使用が想定されており、HTMLなどのツリーベースな文章でOTを使用するには工夫が必要であったそうです。

線形データモデルは以下のようなもの。普通のテキストファイルに太字や段落など多少の装飾が施されています。

ツリー構造の文章は以下のようなもので、より高度な構造を扱うことができます。

OTをツリー構造の文章に適用するにあたっては以下のような場合に問題が発生したとのこと。

1. ユーザーAがリスト項目タイプを箇条書きから番号に変更すると同時にBが項目を分割する時

2. 複数ユーザーが同時に同じ段落で改行を行う時

3. ユーザーAが段落に「引用」を適用すると同時にBが改行を行う時

4. ユーザーAが文をリンク化すると同時にBがその間に文字を挿入した時

5. ユーザーAが文をリンク化すると同時にBがその間の文字を削除した時

こうした問題に対処するため、開発チームはOTの基本操作である「挿入」「削除」「属性をセット」に加えて、新たに段落をリストに変更するなどの「要素をリネーム」、ユーザーの意図を明確にするための「分割・結合・包括・排出」という操作をOTに導入したそうです。さらに要素の挿入とテキストの挿入を別の操作に分割したり、「マーカー」操作を導入したりもしたとのこと。

新たな操作を導入したことで、操作の細かい違いに対応できるようになり、ユーザーの意図通りに文章が変更されるようになりました。このようにしてCKEditorはユーザー体験を損なうことなく共同編集機能を追加できたとのことです。