１人用Local-first softwareで使うCRDTとYjs
CRDTとは
CRDTとはConflict-free Replicated Data Typesのことで、ものすごくざっくり説明するならオンライン同時編集機能をアプリケーション実装依存せず、データ構造レベルで競合なく実現させてしまおうという欲張りな技術である。
CRDT自体についてはこの記事ではそこまで深煎りしない予定なので深煎りしたい人向けの役立ちリンクはこのあたり。
Yjsとは
CRDT自体はただの理論や考え方であって、その理論をソフトウェアとして実装としたものの１つがYjsである。
他にも有力・有名なCRDT実装はいくつかあり、例えばAutomergeもよく名前が挙がる。
作った（作っている）アプリ
Draw.ioみたいな作図ツール。この記事で紹介するYjsの使い方はほぼ全てこのアプリケーションを作ることを前提に検証と実践をしてきたものであることに注意。いくらCRDTがアプリケーションに依存しないとはいえ、それをどう活用するかは結局のところアプリケーション次第で、その用途目的によって千差万別となる。
アプリ自体のことについては以前記事にしたのでここではリンクだけ。
当初の導入理由
おそらくほとんどの場合でYjsの導入するモチベーションはCRDTによる同時編集機能の実現にあると思われる。今回のアプリでは同時編集機能の優先度は相当下げていて未だに着手目処も立っていない状態だが、将来的に導入する可能性を踏まえてYjsをコアに導入しておくメリットは大きいだろうと判断していた。
もう１つ大きな理由は、ファイルベースの保存機能を前提としつつもネットワーク越しのコラボレーションも実現してしまおうというLocal-first softwareを目指してみたかったから。
同時編集機能は既に述べたように優先度は高くない。しかしネットワーク越しのコラボレーションは時間差でも発生し得る。特に自分同士の時間差コラボレーションは個人が複数端末を使いこなす現代では頻出である
常に最新版データを端末に同期してから作業し、作業結果を最新版として常にクラウドストレージに同期することを徹底できるなら自分同士の時間差コラボレーションはただのファイルベースでも機能する。ただし残念なことにこの約束を守り続けるのは我々人間には難しすぎて、必ずどこかで枝分かれしたファイルが発生する。終わりである。
この枝分かれしたファイルの存在に対してCRDTの「競合なく一貫性のあるマージが可能」という特性が輝いてくれる。この特性により、散々に枝分かれしたファイルをどんな順番でマージしようとも競合は発生しないし結果も一意に定まる。アプリケーションの実装に依らず、データ構造レベルでこの特性が担保されている。すごい。使ってみたすぎるということで採用。
データ構造
Y.Docの分割
今回のアプリは１つのプロジェクトデータを複数のY.Docに分割している。シェイプデータを含むシートをそれぞれ別のY.Docに、そしてシートの名前や並び順などプロジェクト全体を構成するデータをさらに別のY.Docとしている。
実はYjsにはSubdocumentsという仕組みがあり、Y.Doc自体を他のY.Doc内のデータとして管理して非同期にロードしたりできるという強力な機能が用意されている。しかし今回はこの機能は利用せず、分割したY.Docは自前でそれぞれ別のファイルとして管理している。利用しなかった理由は、この機能は強力故にややこしく、さらにデータ永続化を担うadapterも全てがこの機能に対応しているわけではないという注意書きが非常に気になったから。
Not all providers support subdocuments yet.
ただでさえファイルベースのY.Doc分割管理という情報が全然出てこないことをやろうとしている状況で、Yjsのプロたちでさえ未だ持て余していそうな機能をデータ構造の中核に導入するのは気が引けてしまった。仮にSubdocumentsに頼らなかったとしても、ファイルの境界はシート毎と明確なので自前実装のイメージも十分にあり、ブラックボックスも減るだろうということで使わないことを選択。
今のところこの選択は正解だったように思う。Subdocumentsの理解度は浅いので比較はしにくいものの、分割したY.Docの管理で大きく詰まった箇所はなかったはず。React.jsのhooksと折り合いを付けることが最大の難関だった可能性が高い。
各Y.Docをファイルに保存するときはその時点での状態を丸ごと保存している。DBに保存するときと同じように更新差分を都度ファイルにappendモードで書き込めたら無駄がなくクールではないかと期待したがそもそもブラウザのFile System APIにはappendモードが存在していなかったので断念。さすがに毎操作ごとに保存を実行するのは気が引けたので操作頻度に応じてある程度まとめて保存を実行するようにはしている。
GCの挙動
YjsにはGCが搭載されていて、CRDTの実現に必須ではない情報はGCによって削除される。例えばY.Mapで要素を削除するとそのvalueは保持されないことになっているが、実際にはGC発動まで保持されている。Undo/Redo機能があるのでこの挙動には納得性がある。ただ厄介なのが、GCは「Y.applyUpdateが実行されたタイミング」で発動するようになっている。Y.encodeStateAsUpdateで得られるデータにはGCが発動していない。
なぜこういう挙動になっているのかは正直なところ分かっていない。リアルタイムにY.Docの差分を交換し合っているような状況ではY.applyUpdateするまでGC発動なしのフルデータが必要なのかもしれないが本アプリには搭載されていないため未検証。
多分そうだろうという期待と、実際にGC発動（空のY.Docに一度Y.applyUpdateしてから再度Y.encodeStateAsUpdate）してからファイルに保存->それを開いたりマージしても挙動に変化がなさそうだったので本アプリではGC発動後のY.encodeStateAsUpdateを丸ごとファイルに保存している。特に大量のデータを削除した後ではGC発動のありなしでデータ量が相当に変化するので、自動保存で頻繁にファイル保存を行う本アプリではGCを発動して可能な限りデータ量を削減しておきたい。
リアルタイムコラボレーション機能を実装する段になったらこの部分はまた見直しが必要だろうと思われる。少なくともYjsがそこをGC発動タイミングとして選んでいるのだからきっと何かしらの理由は存在するはず。
分割されたY.DocとY.UndoManager
Y.Docを分割してことに関連して考慮不足だったことは、Y.UndoManagerは複数のY.Docを跨っての利用ができなかったこと。例えばシート内データであるシェイプの編集をY.UndoManagerに担当させた場合、シート外データであるシート並び順の変更はそのY.UndoManagerに担当させることができない。
実装時は複数Y.Docを跨がせるような設定をY.UndoManagerに与えても何もエラーは出ずただサイレントにUndo/Redoに失敗していたのでこの制限に気づくのにやや時間がかかってしまった。これは確かその後改善されて今は警告なりが表示されるようになっていた気がする。
もちろん複数のY.UndoManagerを用意すればそれぞれのY.DocにUndo/Redoの搭載が可能ではあるが、１つの画面にUndo/Redoのスタックが２種類存在する状況は認知不可が高すぎるだろうということで採用せず。今回のアプリでは妥協案として、Undo/Redo操作は「シェイプに対してのみ可能」で、「シートを切り替えるとクリアされる」挙動となっている。なので例えば「シェイプ編集 -> シート名変更 -> Undo」と操作しても、「シート名変更」部分はUndoも/Redoもされない。あくまでも妥協案にすぎないが、引き換えに得られるシンプルさは非常に大きい。シートの追加や削除などY.Doc自体の増減が絡む操作の履歴管理を放棄する絶好の口実になった可能性も高い。
仮にSubdocumentsを使っていたらY.Doc横断履歴管理ができていたのかは調査していないので不明。できるのかもしれないが、永続化されたデータとの兼ね合いを考えるといずれにせよややこしいだろうとは予想している。もし全ての操作を絶対に履歴として管理したいんだという場合、やはりY.Docの分割はせず１つの巨大なY.Docに全てを記録していく方法が最善と思われる。
entity storeとしてのY.Map
シートやシェイプのようなentityはY.Mapで保存している。Y.Mapの一番の利点はやはりその分かりやすさにある。Yjs側の実装はほぼ完全に隠蔽されているため、アプリケーションからはMap同等の使い心地になる。
一方でY.Mapにはデータ量が膨れやすいという明確なデメリットがある。一見ただのMapなのだから保存されているデータ量もその分だけに見えてしまうが、内部的にはkey毎にY.Arrayを保持する形で実装されていたりと複雑めな構造となっている。
第一に、Y.Mapはkeyを削除してもそのkeyは削除フラグと共に保持され続ける。value側は廃棄されるので個別の増加量は少なめだが、一度でもsetしたkey分の容量が単調増加し続けるという状況はあまり気持ちの良いものではない。
第二に、Y.Mapはset回数に応じてデータ量が増える。当たり前にも聞こえるが、これは「新規のset」だけでなく「既存keyに対するset」でも増える。つまり普通のMap気分でランダムアクセスしながらsetを繰り返すようなユースケースでは思わぬデータ量増大に遭遇する可能性が非常に高い。
この事実は当初把握していなかったものの、幸いなことに今回はY.Mapに保存するentityそれぞれもY.Mapとして各プロパティ単位で変更する構造を採用していたためある程度は回避できている。
この構成だと全体のY.Mapに対するsetはシェイプを新規作成したときだけ行われる。シェイプのプロパティを変更した場合は、全体のY.Mpaではなく個別entityのY.Mapに対してsetが行われる。もちろん個別entityのY.Mapにてsetの度にデータ量増大が起こることになるが、少なともここのkey数は予め定めたシェイプのプロパティ数に収まっているため大きな問題には繋がりにくい（多分）。ちなみにこの構造は「シェイプのプロパティ単位で同時編集可能」を実現するために採用したもので、それが問題回避に役立ったのは完全に偶然だったりする。たとえば別々の環境で同じシェイプの位置とサイズをそれぞれ変更しても、マージときには両方の変更が消えることなく統合される。Y.Mapをネストせずシェイプをそのままvalueとして持っていた場合は「シェイプ」が同時編集の最小単位となるためいずれかの編集が消滅する。
Yjs作者もY.Mapに大量のkeyをsetすることを推奨しておらず、そのケースにはY.Arrayの利用を促している（2021年のforum情報）。
Y.Mapのこうした問題を軽減した改良版としてYKeyValueがutilityとして提供されているので検討余地がある。Y.Arrayを独自にwrappしてY.Map相当のインタフェースを自作するという手もある。
データ量増大はもちろん回避したいのでY.Mapからこうした代替手段への乗り換えも検討したが未だ採用には至っていない。いくら代替とはいえやはり100%互換ではなく、データ変更を通知してくれるobserveハンドラの便利さなどがY.Mapに及ばない。削除されたentityが持っていたidがどうにも分からないなどの問題が確かあった覚えがあるが記憶は若干怪しい。今回のようにY.Mapをネストしたいようなユースケースに対応できるかどうかも怪しそうだった覚えがある。そして何よりY.Mapという（使い手から見た）構造の分かりやすさが捨て難い。将来的にデータ構造変更とそれに伴うマイグレーションの手間がかかってしまったとしても、現状ベストアンサーがないのなら素直に標準として提供されているY.Mapを使っておくでいいだろうと考えそのまま使っている。少なくとも不特定多数のkeyが不特定多数回setされる状況は回避できているので許容範囲だろうと思われる。
データ量が膨大になった場合に備えてアプリケーションの特性を活かした回避手段も用意できている。例えばY.Docはシート毎に別れているので、新規シートにシェイプを丸ごとコピペすれば内部に溜まった不要データは全てクリアされる。他にもシートを切り替えることなく、既存シートの不要データをクリアする機能をアプリ内に用意している。Y.Doc自体にはクリア機能がないので、新規にY.Docを作成してデータをまるっと移し替える実装がアプリ側で必要であった。もちろんこれらの操作でCRDTを実現しているメタデータも削除されて派生データとの競合なき一貫したマージは不可能となる。なのであまりにもデータが膨大になったとき用の避難ハッチ扱いである。
Y.Mapの是非についてまとめるとこのようになる。繰り返しになるが今回のアプリケーション特有の事情も多く関わっているので鵜呑みには注意。
- データ量が増え続けるのは気になるが許容できる範囲
- あまりにもデータ量が増えた場合に備えて避難ハッチを用意できる
- 代替手段よりも
Y.Mapの使いやすさと分かりやすさに利がある - 将来的に素晴らしい代替手段が登場したら頑張ってマイグレートすればいい
Fractional indexingによるentity順序制御
Yjsに搭載されている機能ではないが同時編集を前提とするデータ構造として関わりがあるのでFractional indexingの利用について紹介する。Fractional indexing自体についてはFigmaから素晴らしい記事が出ているのでそちらを参照。
前述のようにentityはMapで保存しているのでそこにはentity同士の順序が保存されない。そこでentityそれぞれにindexのようなプロパティを持たせてそれの大小を比較することで順序を復元することになる。Fractional indexingはシンプルに言ってしまえばそのindexを（なるべく）重複なく効率的に生成してくれる仕組みである。
単純にfloatな数値を1/2にしていく方法もFractional indexingの実装の１つである。この方法はfloat精度の上限に意外と早く到達してしまうらしい。今回採用したのはテキストベースのFractional indexing、例えばAaとAcの中間としてAbを生成するような手法で、こちらではfloat版が持つ精度上限デメリットが改善されている。もちろんキー長に応じた容量を食うので文字通り無限のFractionalというわけにはいかないものの、人間の操作を前提とした用途では十分だと思われる。
当初は名前の通りfractional-indexingというライブラリを採用していた。
しかし素朴なFractional indexingは入力に対して出力が一定で、それは当たり前なのだが、アプリケーションの汚い世界では出力が綺麗すぎる故に同じインデックスを持つentityがどうしても生まれてしまう。
同じ入力に対してFractional indexingを満たしつつ多少のランダム性を付与してくれるような都合の良い仕組みはないものかと他人任せに日々を過ごしていたらなんとあった。しかも先に導入していたfractional-indexingリスペクトのインタフェースを用意してくれているので移行もお手軽。
ランダム性が付与されたことでさらに重複は発生しにくくなるものの可能性がゼロになるわけではない。ただ今回のアプリでは重複が発生して多少entityの順序が不定になったとしてもきっと橋は崩壊しないので特に対策はしていない。できないわけではないのでもちろんやるべきなのだがさぼっている、いつかやる。自動での重複解消が厳しいとしても「ここ重複してるよ」的な表示をして手動での解消を促しておくべだろう、いつかやる。
Y.Arrayベースでentityを保存した場合にFractional indexingが必要になるかどうかは不明。Arrayなので要素同士にはもちろん順序があって利用可能だが、CRDTのArrayは要素の入れ替えに弱いことが多々ある。Y.Arrayも例外ではなく要素の「追加」と「削除」で実装されているため、要素の入れ替えは実質「追加」と「削除」の組み合わせになる。ここに同時編集が発生すると「追加」が複数回認識されて要素が重複する。深く検証はしていないがY.Arrayにも特有の難しさやテクニックがあると思われるので同じくFractional indexingを導入した方が綺麗にまとまるのかもしれない。
テキストはY.Textに
一部シェイプにはテキストを書き込むことが可能で、そのテキストはシェイプとは別の場所にY.Textとして保存している。
Y.Textを利用することでテキスト部分もYjsの力によってCRDTが適用される。Y.TextはQuill Deltaに対応しているためリッチテキストエディタの実装にもピッタリである。嬉しいことにQuill Deltaの標準的なオペレーションを内蔵してくれているのでアプリケーションからQuillに依存する必要もない。
Y.UndoManagerはもちろんY.Textの変更も追跡してくれる。captureTimeoutを指定することで特定時間内に行われた操作を１まとまりのUndo/Redo対象とみなしてくれるため、テキスト編集中は1000msにしてある程度の操作をまとめ、それ以外では0msにして操作と１対１対応させるといった柔軟な使い方ができる。
さらにYjsにはY.RelativePositionという編集中のカーソル位置をいい感じに保存復元するための機能が存在する。例えばリアルタイムコラボレーションな状況で、他の誰かが同じテキストを編集したとしても自分のカーソルを「テキスト内の相対的に同じ位置」にキープすることができる。当初これはリアルタイムコラボレーションを搭載しない場合には不要な機能と思っていたが、実は同じ状況がY.UndoManagerでUndo/Redoしたときにも発生し、Y.RelativePositionでカーソル位置を管理していなかった場合は容赦なくカーソル位置がずれてしまう。幸いにも機能として用意してくれているので、リアルタイムコラボレーションがなかったとしてもこれは最初から組み込んでおいたほうがよい。
今更だがこのあたりはテキストエディタを自作するときの話題であって、何かしらリッチテキストエディタライブラリにYjsをbindingして使う場合には気にしないでいい可能性は高い。
テキスト保存場所としてシェイプとは別のY.Mapを用意したことにはやや後悔がある。前述のようにY.Mapは追加したkeyが残り続けてしまうため、１つのシェイプに対して実質key２つ分のデータが永続化されてしまう。シェイプ自体がY.Mapになっていることからも、その中のプロパティとしてY.Textを用意しておく構造にしても大きな問題はなかったと考えている。FirebaseのRealtimeDB的にネストはとりあえず浅くした方がいいだろうと当時はあまり深く考えておらず、ここは後悔ポイントの１つ。
また１つのシェイプに対して１つのY.Textという構造も実は不十分だった可能性が浮上している。例えばtitleとdescriptionの２種類のテキストを持つ単体のシェイプを作りたくなった場合にこの構造では対応できない。将来的に大規模なデータ構造変更を行うとしたらまずここがまず候補に挙がる可能性が高い。
CRDT活用例
せっかくなので本アプリケーションの数少ないCRDTならでは機能を紹介。
ワークスペースをエクスポートすることが可能となっているため、例えばGoogle Driveをクラウドストレージとして以下のようなマルチデバイス間コラボレーションが可能。
デバイスAで作成したワークスペースを作成。
ワークスペースをGoogle Driveにエクスポート。デバイスBにてGoogle Driveからワークスペースを開き、それをローカルファイルとしてエクスポート。
デバイスAとBそれぞれでワークスペースを更新。この時点では各ワークスペースは同期されておらず、「マスター」に相当するものは存在しない。
デバイスAでワークスペースを再度Google Driveにエクスポートし、続けてデバイスBでもエクスポート。エクスポート先にワークスペースが存在する場合はマージが実行される。このマージはCRDTの名のもとに行われるためGoogle Driveには両デバイスで行われた更新が競合なくマージされている。
以降は同様で、Google Driveとデバイスのワークスペースはエクスポートを通してその都度一貫性を保ったまま最新化されている。仮に最新化されていないワークスペースを編集してしまったとしても（そもそも最新のワークスペースという概念がほぼないのだが）、どこかのタイミングでエクスポートしてマージすれば全ての変更は消滅することなく合流する。
中央集権的なサーバーが存在しない都合上、クラウドストレージへのエクスポートがほぼ同じタイミングで実行されると一方のエクスポートはキャンセルされる形となってしまう。同一ユーザーが同一タイミングでそのような操作をするケースは概ね考えられないのとはいえ、ここはサーバーレスなLocal-first software故の妥協点でもある。
まとめ
リアルタイムコラボレーションを搭載しないアプリケーションでYjsを使う利点があるのかがおそらく本記事最大のテーマであるが、ここまで様々書いてきたように十分に利点があったと考えている。特にテキスト編集関連の実装はYjsの機能に大きく助けられていて、仮にコラボレーション要素が一切ないアプリケーションだったとしてもテキスト編集機能が存在する（そして自作する）なら導入価値が十分にあるかもしれない。
そしてリアルタイムコラボレーション機能は現状搭載していないというだけで、Websocketやら何やらを用意すればアプリケーション側には大きな変更なく導入することが可能なはずである。そうした実装の心配を全て先送りにしてまずはアプリケーションとしての機能実装に集中できているのはやはりYjsの存在が大きい。
ちなみに記事中の図たちは当のアプリケーションにてさくっと作成している。CRDTやYjsという重厚な仕組みはそれはそれとして、こういったちょっと作図したいんだけどな用途にこそうってつけなツールなので是非とも試してみほしい。
Discussion