Share
Embed
わかった気になれる 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
Transcript
35 slides
-
1. OT シンプルなテキストを共同編集するために生まれた技術で、30 年ほどの歴史がある 簡単にいうと、何文字目にどういう操作をしたのかの履歴を持っておくことで、このタイミングで5 文字目に 文字を挿入したってことは、その後に3 文字挿入されているから8 文字目に挿入するのが正解だな、という計算 を行うこと
直感的で素直な実装だが、複雑なデータ構造や操作を扱おうとすると、どんどん実装が複雑になってしまう ( 基本的には中央サーバーが必要) Operational transformation -
2. CRDT そもそもコンフリクトしないようなデータ型を定義することで一貫性を保つ仕組み 10 年ほどの歴史の比較的新しい技術だが、データサイズや計算速度の懸念点があったが、技術とコンピューテ ィングの進化で実用的になった 汎用性が高く、複雑なデータにも対応しやすい ( 中央サーバーなしで P2P
でのやりとりが可能) データ構造の詳細などは、後ほど説明する Conflict-free replicated data type -
OT と CRDT の使い分け シンプルなテキストデータだけなら OT が最適 それ以外の複雑なデータが含まれる場合は CRDT を検討する価値がある
中央サーバーなしで、 P2P でやりとりしたければ CRDT Henry では、文書内に埋め込みできるデータがリッチであったり、多様なコンテンツを共同編集可能にしたか ったため、 CRDT を検討して採用した 一概に、こういう場合はこちらがいいとは言い切れないが、目安として -
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 は複数存在している -
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 }); -
ProseMirror WYSIWYG エディタのライブラリ エディタライブラリは様々あるが、 Yjs と使うなら binding が用意されているものがオススメ 他にも Quill
/ Slate / Lexical なども選択肢で、日本語 IME の対応、モバイル対応、API の使いやすさなど、プ ロトタイプしながら自身のアプリケーションの要件を満たすかを検討する Tiptap ProseMirror を React で使いやすくするためのライブラリ エディタ内に React や Vue の Component を埋め込めるようにするために便利だが、ProseMirror 自体を理解 していないと使うのは難しいので、必須ではない https://prosemirror.net/ https://tiptap.dev/ -
y-prosemirror Yjs と ProseMirror の状態を同期してくれるライブラリ これを使えば、基本的にはエディタの機能を開発するときは ProseMirror のことだけを考えれば良いが、以下 の点に注意する必要がある 両者の操作を相互に変換して適用するのではなくて、両者の差分を検知して埋めるアルゴリズムのため、実
際にエディタで操作したのとは違う形で Yjs に変更が加えられることがある ProseMirror と Yjs のデータ構造には完全な互換性はないので、同期すると壊れる可能性がある 例えば、同じ場所に同じ名前の Mark を複数つけることはできない https://github.com/yjs/y-prosemirror -
lib0 Yjs の作者が作っている便利ライブラリで、Yjs 内で主に encoding と decoding の用途に使われている 軽量化のために、ネットワークでやりとりされるデータや永続化するデータなどは、ほぼ全てこの lib0
で作ら れたバイナリ (Uint8Array) なので、パッとみたときにどういうデータがやりとりされているか分からなくてデ バッグに困ることがある 次のページの基本的な使い方と、後で紹介する Yjs でよく使われるデータの意味と構造を知っていれば、開発 しやすくなる https://github.com/dmonad/lib0 -
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 } -
ライブラリの関係性 Yjs / ProseMirror / y-prosemirror / lib0 の関係 周辺のライブラリと合わせて、
Yjs はどういう責務を担っているかを整理 -
CRDT の内部構造 エディタから見たらただの XML を操作しているように見えるが、その裏側に2 つの層がある 3 つの層のイメージ図 StructStore →
Tree → XML の3 層構造をイメージ -
中心の Tree 各要素が Parent / Left / Right への参照をもつ木構造 p
タグの先頭の "A" の次に "b" と入力したら、Parent に p タグが、 Left に文字 "A" が入る ( 効率化のために連続する文字が一つの要素に入る場合もある) Parent / Left / Right への参照をもつ木構造 一つ一つの操作をノード(=Item) とする木構造 -
StructStore にデータを蓄積 各 Item は ID = { clientID, clock
} を持つ クライアントごとに初期化時にランダムな数字で clientID が振られ、操作ごとに clock が1 ずつ増える Parent などは参照は、参照先の ID として持つ これを integrate することで、 Tree が得られる clientID = 111 の StructStore( 各要素がItem) Tree の各要素である Item をクライアントごとに順番に積み上げたもの -
追記の挙動 文字を入力した場所から Parent / Left / Right の ID を探して、入力内容を合わせて
Item を生成する StructStore の自身の clientID の配列に、作った Item を追加する Integrate して Tree を構築して、XML が更新される もし全く同じ Left に対して文字が挿入されたら、clientID が小さい方が先に Left に来るというルールを設ける ことで、一意に Tree の状態が決まる 文字の入力や YMap.set など、削除以外は全て追記 -
削除の挙動 効率性観点から、削除は追記でなく StructStore のデータに直接 deleted のフラグを立てる 自身の clientID 以外の Item
も直接変更して deleted にする 一度削除されたものがもう一度復活することはないので、削除の操作がコンフリクトすることはない Undo は同じ操作を追記する形で実装されている 削除した範囲を表すデータを DeleteSet と呼ぶ -
追記 + 削除 = 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 }); -
sync1 を送り sync2 を受け取るのを、両者で行う 差分同期 素直にやるなら両者の StructStore を merge すれば良いが、差分が小さい時には非効率的
自身がどこまでのデータを持っているかを表す軽量なデータである StateVector を使って、お互いの差分の みを送り合うことができる 初回の読み込み時や、再接続時に完全にデータを同期する効率的なプロトコル -
状態の永続化 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); -
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 が指す地点の状態を復元 -
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 } -
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); -
その他の注意点 ユーザーの一般的な操作に対して最適化されているので、変な操作をするロジックを書くとすごく時間がか かる場合がある 例えば、一度の transaction で大量の範囲を書き換えるなど 改行の操作は、行の後を削除して、次の行に追加する操作で、コストが高い move 操作の開発が進んでいるので改善されることを期待 連続する文字を一つのワードとして扱うことでの省スペース化されている
IME を使った入力では、追加と削除が繰り返されるため、英語よりデータ量が大きくなりがち 誰がどういう変更をしたかを知りたい場合は、clientID とアプリケーションのユーザーID を紐づけて、 DeleteSet もユーザーごとに管理する必要がある -
Yjs の未来 Yjs は基本的な機能はきっちり動くし、パフォーマンスも実用レベルだが、大きな StructStore に対して繰り返 し処理が行われるため v8 の最適化に依存して処理速度が大きく変更したりする 安定して高パフォーマンスが出せ、別の言語でも
binding できるように Rust (WebAssembly) 化が進んでいる https://github.com/y-crdt/y-crdt Yjs のバイナリと互換性があるので置き換えやすく、 Python や Ruby の binding も開発されているので、 CRDT を採用できる幅が広がることに期待 Rust (WebAssembly) 化が進行中 -
まとめ 単純なテキスト以上の複雑なデータを共同編集したい場合や、 P2P にしたい場合は、CRDT が有力な選択 肢になる CRDT のコアは、 Parent /
Left / Right への参照を持った木構造 Item / StructStore / DeleteSet / StateVector / Snapshot などのデータ構造と意味を理解して使いこなす Garbage Collection を有効にするかどうかは場面に応じて判断する Y CRDT の開発に期待