OTに対するCRDTの利点

この記事は、ヌーラボブログリレー2024 for Tech Advent Calendar 2024の19日目の記事です。

Backlogのドキュメント機能が9月10日にリリースされました。そこでドキュメント機能の開発を担当しドキュメント機能で使う技術としてCRDTを採用しましたのでCRDTのOTに対する利点について書いていこうと思います。

今回私は最終的にはCRDTを選んだのですが、最初にCRDTを選ぶきっかけは技術的な理由ではなくエディタの選定の結果でした。現在Webエディタは数多くありますが、最初に私が検討していたのはQuillエディタでした。このエディタはコンパクトでシンプルなのに差分としてOTのDeltaフォーマット(文字の装飾やスタイルもマージできるように設計されたOT)が出力できると言うすごいエディタです。もちろん、これを使うのが最初から頭にあったのですが、実際にプロトタイプを作って共同編集してみると日本語IME(日本語というかCJK IME)の不具合が多くあり共同編集できない問題にぶつかります。そこで私は日本語IMEに強いエディタを探した結果、ProseMirrorにいきつきました。このエディタは実は数年前に個人開発でも使ったり、Backlogの課題機能のエディタでも使われています。ただ、ProseMirrorを使うとなるとOTの実装がなく、自分で作る必要があります。というのもありProseMirrorにも対応しているCRDTの実装yjsを使うことにしました。

サーバー負荷

ここからはCRDTとOTの理論的な比較ではなく実際の実装であるyjsとの比較ということで書いていきます。まず、CRDTのメリットとしてサーバーの負荷の軽さがあります。OTはあるユーザーの操作(文字を入力したり削除したり装飾したりの情報)があると、その操作に対してこれまで蓄積した全操作を取ってきて全操作とこれから適用する操作を計算して(文字の位置をずらしたりする)これを操作変換というわけですが、最終的に計算仕上がった操作がリストに追加されオンラインユーザーに配信されることになります。これが一文字入力されるごとに起こるので大変です。(正確には計算された操作が返ってくるまでの操作がクライアントで合成され、それがサーバーに送られることで効率よくできている部分もあります。)

それに対してyjsは操作を積むだけなのです。リストをロードする必要すらなく、リストに積んでオンラインユーザーに配信して終わりです。では、計算(マージ)はどこで行う？となりますが、これはクライアントで行われます。(もちろんサーバーで行っても問題ありません。)こうなるとサーバーはNode.jsなどyjsを直接使える言語を使う必要すらありませんね。

耐障害性

共同編集ではサーバーが落ちる、ネットワークが切れる、ファイアウォールやVPNによって通信できないなど面倒な問題がたくさんありますが、yjsではネットワークがないときに(ある時でも)操作をブラウザのindexedDBに蓄積することができ、ネットワークができた時にサーバーとローカルの差分を計算し、サーバーに存在しない操作を送信することで同期を回復することができます。つまり、電車に乗って共同編集していたとして、トンネルに入ってネットワークが切れてもトンネルを出てネットワークが回復するとシームレスに共同編集を再開できます。

可換性

可換性とは何かといいますと、これは操作の適用される順序がどういう順序でもOKという意味です。Aが適用されてBが適用されるでもOK、Bが適用されてAが適用されてもOKということです。

これが何を意味するかというと最近のサーバーはKubernetesなどで複数サーバーで動いていることが多いと思いますが、OTでたまたま2つのサーバーでほとんど同時に処理が行われサーバー1でAという操作が発行され、サーバー2でBという操作が発行された場合、A → Bという順序で発行されたとしてもサーバー2の方が配信が早くBを先に配信してしまうとOTではアプリケーションがエラーになったり、整合性がなくなる場合があります。

これに対してCRDTはAという操作とBという操作がどちらが先に来てもマージできます。この点サーバーの構成にあまり制約がなく優れています。

リッチな内容の共同編集

昔の共同編集では、Markdownを使い装飾などもプレインテキストで扱うことで共同編集していましたが、最近はWYSIWYGを使ったエディタで装飾などのリッチな内容をそのまま共同編集したいということがあると思います。

OTの場合これをDeltaフォーマットという操作をJSON化しこれをやりとりして実現することができますが、新たな表現を使いたいというときに(例えばBacklogのドキュメント機能でいうと課題の埋め込みだったり)既存の操作と合成可能か整合性を検証したり、変換ルールを拡張する必要があるか検討する必要が出てきてかなり面倒です。

これに対してyjsは技術的にエディタで表現できることは、自動的に対応できるので新たなリッチな表現ができたとしても簡単に共同編集に組み込むことができるようになっています。

操作ごとの容量はCRDTの方が大きい

yjs(CRDT)の欠点として1つの操作のメタデータ、つまりコンテンツそのものとは関係のないデータがOTと比べて多いというのがあります。これに対してyjsは圧縮、解凍することで対応していますが、基本的にはOTより保存するデータ容量は多くなります。

まとめ

今回、ドキュメント機能を作るにあたりCRDTを採用する選択をしましたが、今のところデメリットよりもメリットの方が大きく、採用して良かったと感じております。今後もBacklogドキュメントは機能がどんどん追加されていきますのでぜひご活用ください！