Upgrade to Pro — share decks privately, control downloads, hide ads and more …

わかった気になれる CRDT を使った共同編集

Kento Moriwaki
September 13, 2022

わかった気になれる CRDT を使った共同編集

Yjs を使った CRDT による共同編集の入門スライドです。

このプレゼンテーションは、2022-09-13 に行われた [【VideoTouch & Henry】とあるフロントエンド勉強会](https://henry.connpass.com/event/258484/) で発表されたものです

Author [KentoMoriwaki](https://twitter.com/kento_trans_lu)

Kento Moriwaki

September 13, 2022
Tweet

More Decks by Kento Moriwaki

Other Decks in Programming

Transcript

  1. OT と CRDT の使い分け シンプルなテキストデータだけなら OT が最適 それ以外の複雑なデータが含まれる場合は CRDT を検討する価値がある

    中央サーバーなしで、 P2P でやりとりしたければ CRDT Henry では、文書内に埋め込みできるデータがリッチであったり、多様なコンテンツを共同編集可能にしたか ったため、 CRDT を検討して採用した 一概に、こういう場合はこちらがいいとは言い切れないが、目安として
  2. CRDT を使った事例 CodeSandbox コードエディタ部分は OT で、ファイルシステムなどは CRDT と、模範的な使い分け Figma 独自実装の

    CRDT を使っている https://www.figma.com/ja/blog/how-figmas-multiplayer-technology-works/ JupyterLab 今回紹介する Yjs を使った CRDT で共同編集を実装 Redis 地理分散システムに CRDT が使われている https://redis.com/blog/diving-into-crdts/ CRDT を使った分散 DB は複数存在している
  3. Yjs CRDT の JavaScript 実装の一つで、Map / Array / XML など汎用的なデータ型が提供されている

    内部の構造や挙動は後のページで紹介する Yjs のサンプルコード https://docs.yjs.dev/ 1 import * as Y from "yjs"; 2 3 const ydoc = new Y.Doc(); // ドキュメントの作成 4 5 ydoc.on("update", (update: Uint8Array) => { 6 // 変更イベントを受け取り、変更内容をサーバーや他のクライアントに送ることができる 7 }); 8 9 const map = ydoc.getMap("foo"); // Top-level に foo という名前の Map を定義する 10 11 ydoc.transact(() => { // 複数の変更をひとまとめにするための Transaction の発行 12 map.set("one", 1); // "one" のキーに、 1 の値を設定 13 map.set("two", new Y.Array()); // "two" のキーに、配列の値を設定 14 map.get("two").push(2); // "two" のキーに、 2 を push 15 });
  4. ProseMirror WYSIWYG エディタのライブラリ エディタライブラリは様々あるが、 Yjs と使うなら binding が用意されているものがオススメ 他にも Quill

    / Slate / Lexical なども選択肢で、日本語 IME の対応、モバイル対応、API の使いやすさなど、プ ロトタイプしながら自身のアプリケーションの要件を満たすかを検討する Tiptap ProseMirror を React で使いやすくするためのライブラリ エディタ内に React や Vue の Component を埋め込めるようにするために便利だが、ProseMirror 自体を理解 していないと使うのは難しいので、必須ではない https://prosemirror.net/ https://tiptap.dev/
  5. y-prosemirror Yjs と ProseMirror の状態を同期してくれるライブラリ これを使えば、基本的にはエディタの機能を開発するときは ProseMirror のことだけを考えれば良いが、以下 の点に注意する必要がある 両者の操作を相互に変換して適用するのではなくて、両者の差分を検知して埋めるアルゴリズムのため、実

    際にエディタで操作したのとは違う形で Yjs に変更が加えられることがある ProseMirror と Yjs のデータ構造には完全な互換性はないので、同期すると壊れる可能性がある 例えば、同じ場所に同じ名前の Mark を複数つけることはできない https://github.com/yjs/y-prosemirror
  6. lib0 Yjs の作者が作っている便利ライブラリで、Yjs 内で主に encoding と decoding の用途に使われている 軽量化のために、ネットワークでやりとりされるデータや永続化するデータなどは、ほぼ全てこの lib0

    で作ら れたバイナリ (Uint8Array) なので、パッとみたときにどういうデータがやりとりされているか分からなくてデ バッグに困ることがある 次のページの基本的な使い方と、後で紹介する Yjs でよく使われるデータの意味と構造を知っていれば、開発 しやすくなる https://github.com/dmonad/lib0
  7. lib0 lib0 のサンプルコード JSON と違って、エンコードする側とデコードする側の両方が、どういう順序でどういう型のデータが入って いるかを知っている必要がある 1 import encoding from

    "lib0/encoding"; 2 import decoding from "lib0/decoding"; 3 4 const data = ["foo", "bar", "baz"]; // 今回エンコードしたいデータ 5 6 const encoder = encoding.createEncoder(); // encoder を作る 7 encoding.writeVarUint(encoder, data.length); // 最初に data の長さを詰めておく 8 for (const str of data) { 9 encoding.writeVarString(encoder, str); // 前から順番に、文字列を詰めていく 10 } 11 const message = encoding.toUint8Array(encoder); // バイナリ(Uint8Array) を出力する 12 // 他のクライアントに message を渡すことを想定 13 const decoder = decoding.createDecoder(message); // 受け取ったバイナリから decoder を作る 14 const length = decoding.readVarUint(decoder); // 最初に data 配列の長さを読み取る 15 for (const i = 0; i < length; i++) { // 読み取った長さ分だけループする 16 const str = decoding.readVarString(decoder); // 文字列を読み取る 17 assert(str === data[i]); // 元の配列を同じデータが入っていることを確認 18 }
  8. 中心の Tree 各要素が Parent / Left / Right への参照をもつ木構造 p

    タグの先頭の "A" の次に "b" と入力したら、Parent に p タグが、 Left に文字 "A" が入る ( 効率化のために連続する文字が一つの要素に入る場合もある) Parent / Left / Right への参照をもつ木構造 一つ一つの操作をノード(=Item) とする木構造
  9. StructStore にデータを蓄積 各 Item は ID = { clientID, clock

    } を持つ クライアントごとに初期化時にランダムな数字で clientID が振られ、操作ごとに clock が1 ずつ増える Parent などは参照は、参照先の ID として持つ これを integrate することで、 Tree が得られる clientID = 111 の StructStore( 各要素がItem) Tree の各要素である Item をクライアントごとに順番に積み上げたもの
  10. 追記の挙動 文字を入力した場所から Parent / Left / Right の ID を探して、入力内容を合わせて

    Item を生成する StructStore の自身の clientID の配列に、作った Item を追加する Integrate して Tree を構築して、XML が更新される もし全く同じ Left に対して文字が挿入されたら、clientID が小さい方が先に Left に来るというルールを設ける ことで、一意に Tree の状態が決まる 文字の入力や YMap.set など、削除以外は全て追記
  11. 削除の挙動 効率性観点から、削除は追記でなく StructStore のデータに直接 deleted のフラグを立てる 自身の clientID 以外の Item

    も直接変更して deleted にする 一度削除されたものがもう一度復活することはないので、削除の操作がコンフリクトすることはない Undo は同じ操作を追記する形で実装されている 削除した範囲を表すデータを DeleteSet と呼ぶ
  12. 追記 + 削除 = Update Update が他のクライアントに反映されるまでの流れは以下のよう 一回の操作 (Transaction) で生成された

    Update を lib0/encoding でエンコードして、バイナリデータを生 成 そのデータを中央サーバーに、もしくは P2P なら接続中の全てのクライアントに送る 受け取ったクライアントはそれをデコードして、StructStore に Item を追記してから、DeleteSet が示す範 囲に削除フラグを立てる Y.logUpdate を使えば、Update の中身を確認できる 送信側( 左) と受信側( 右) のコード例 Items と DeleteSet をまとめて Update と呼ぶ ` ` 1 ydoc.on("update", (update: Uint8Array) => { 2 Y.logUpdate(update); 3 ws.send(update); 4 }); 1 ws.on("message", (message) => { 2 const update = new Uint8Array(message.data); 3 Y.logUpdate(update); 4 Y.applyUpdate(ydoc, update); 5 });
  13. sync1 を送り sync2 を受け取るのを、両者で行う 差分同期 素直にやるなら両者の StructStore を merge すれば良いが、差分が小さい時には非効率的

    自身がどこまでのデータを持っているかを表す軽量なデータである StateVector を使って、お互いの差分の みを送り合うことができる 初回の読み込み時や、再接続時に完全にデータを同期する効率的なプロトコル
  14. 状態の永続化 StructStore に入っているすべての Item と、そこから抜き出した DeleteSet を含む Update をエンコードす るだけ。逆にリストアは、その

    Update を適用すれば良い ブラウザ上なら、IndexedDB に保存しておけばオフライン状態でもデータを失うことはない localStorage だと容量的に厳しいかも サーバーなら、S3 などのオブジェクトストレージに突っ込んでもいいし、高速にアクセスできる Redis に 入れるなど、要件に応じて自由に決められる 内容を全文検索したい場合などは、Yjs から好みのデータに変換するコードを書く 状態の永続化とリストアのコード例 1 // State をエンコードして、S3 に保存 2 const update: Uint8Array = Y.encodeStateAsUpdate(ydoc); 3 await s3.upload(id, update); 4 5 // S3 から読み込んだデータを、空の YDoc に適用することで、復元完了 6 const ydoc = new Y.Doc(); 7 const update = await s3.get(id) 8 Y.applyUpdate(ydoc, update);
  15. Snapshot による編集履歴 StructStore には全ての変更内容が蓄積されているため、理論的にはあらゆる地点の状態に戻れる どの地点かを表すデータを Snapshot と呼び、 StateVector と DeleteSet

    で構成されている StateVector だけではどの Item が削除されたか分からないので、DeleteSet が必要 地点を表すだけで内容を含まないので軽量 Snapshot の利用例 1 const snapshot = Y.snapshot(ydoc); // ある地点の snapshot を作成 2 await db().saveSnapshot(Y.encodeSnapshot(snapshot), new Date()); // DB などに時間と共に保存する 3 4 // 履歴の復元 5 const snapshot = Y.decodeSnapshot(encodedSnapshot); // 保存された snapshot をデコード 6 const ydoc2 = Y.createDocFromSnapshot(ydoc, snapshot); // snapshot が指す地点の状態を復元
  16. Garbage Collection ブラウザのようなで揮発性が高い場合は、GC を使わなくてもよい Undo に必要なデータは GC が有効でも保持されるので、GC の効果が小さい サーバーサイドで永続化するようなデータに関しては

    GC を有効にすべきだが、 Snapshot は使えない Snapshot も同時に使いたいなら、オンデマンド実行がおすすめ 普段は GC を無効にしておいて、永続化の前に GC を有効にした YDoc を通してエンコードする Snapshot から復元する際、別で保存しておいた GC 実行する前のデータに対して適用する GC のオンデマンド実行の例 処理速度・メモリ使用量・転送速度・利便性のトレードオフ 1 function gc(ydoc: Y.Doc): Uint8Array { 2 assert(!ydoc.gc); 3 const tmpDoc = new Y.Doc({ gc: true }); 4 Y.applyUpdate(tmpDoc, Y.encodeStateAsUpdate(ydoc)); 5 return Y.encodeStateAsUpdate(tmpDoc); 6 }
  17. Format v1/v2 基本的にはより効率化された v2 フォーマットを使えばよい バイナリのフォーマットが違うだけで、それを取り込んだ内部の StructStore や Tree は同じ状態になるの

    で、共存することは可能 ただし v1 のフォーマットを v2 用のメソッドで読み込むとエラーになるので、どちらでエンコード・デコ ードすべきかは決めておく 相互に変換する関数も用意されているがコストがかかるので、ちゃんと揃えておく デフォルトは v1 で、何も考えずにサンプルや関連ライブラリを使うと v1 を使うことになるので気をつけ る V2 suffix がついた関数を使う Item のバイナリのフォーマットが2 バージョン存在している 1 const v1 = Y.encodeStateAsUpdate(ydoc); 2 const v2 = Y.encodeStateAsUpdateV2(ydoc); 3 Y.applyUpdate(ydoc, v1); 4 Y.applyUpdateV2(ydoc, v2);
  18. Yjs の未来 Yjs は基本的な機能はきっちり動くし、パフォーマンスも実用レベルだが、大きな StructStore に対して繰り返 し処理が行われるため v8 の最適化に依存して処理速度が大きく変更したりする 安定して高パフォーマンスが出せ、別の言語でも

    binding できるように Rust (WebAssembly) 化が進んでいる https://github.com/y-crdt/y-crdt Yjs のバイナリと互換性があるので置き換えやすく、 Python や Ruby の binding も開発されているので、 CRDT を採用できる幅が広がることに期待 Rust (WebAssembly) 化が進行中
  19. まとめ 単純なテキスト以上の複雑なデータを共同編集したい場合や、 P2P にしたい場合は、CRDT が有力な選択 肢になる CRDT のコアは、 Parent /

    Left / Right への参照を持った木構造 Item / StructStore / DeleteSet / StateVector / Snapshot などのデータ構造と意味を理解して使いこなす Garbage Collection を有効にするかどうかは場面に応じて判断する Y CRDT の開発に期待