より高速なCRDTのための最適化

• 既存のCRDTライブラリの問題点を見つけて解決し、より高速化していく過程を説明した記事

→ テストベンチマーク: 18万文字入力、7万文字削除、10万回のカーソル移動

→ Automerge比で5000倍高速（5分 vs. 56ms）

• Automergeが遅い理由は?

→ ドキュメントが大きくなるほど内部のツリーベースのデータ構造も大きくなり、遅くなる

→ ImmutableJSを多用しているが、機能は優れている一方で遅く、メモリ使用量も多い

→ 入力された各文字をそれぞれ別個のアイテムとして処理

→ Automergeは現在、性能を改善したRust版を別途実装中

• YjsライブラリはAutomergeよりはるかに高速

→ データ構造を改善

• Diamond Types: RustベースのCRDT実装

→ 言語をRustに変更し、Yjsのようにデータ構造を改善してさらに高速化

→ リンクドリストの代わりに、Range Treeを利用

→ Wasmで実行すると、JSでの文字列変更より3倍高速（0.19s、Automergeより1500倍）

→ Rust Nativeで実行時は0.056sで5000倍高速

付録A - 自分のアプリでCRDTを使うなら何を選べばよいか?

• 文書ベースの協業ツールを作るなら「Yjsを推奨」。高性能でメモリ使用量も少ない。さらに高速化される予定

• もちろんAutomergeも優秀。おそらく今年さらに速くなる

• Diamondは本当に速いが、まだ多くの機能追加が必要

• 文書セマンティクスよりDBセマンティクスを求めるなら、OTベースだがShareDBを推奨

• Redwoodに期待中

[xguru]

この記事は、下記記事の著者である Google Wave 開発者 Joseph Gentle の最新記事です。まず読んでおくとよいでしょう。

• 私が間違っていました。CRDT が未来です。 https://ja.news.hada.io/topic?id=2962

[alstjr7375]

Xi Editorの開発者であるRaph Levienの文章も参考になります。

https://github.com/xi-editor/xi-editor/…