5000倍高速なCRDT：最適化の冒険
はじめに
- 数年前、フランスの研究者たちがリアルタイム共同編集アルゴリズムを比較した論文を発表した
- 複数のアルゴリズムを実装し、性能をベンチマークした
- 一部のアルゴリズムは、単純な貼り付け操作に3秒以上かかった
- 問題のアルゴリズムはShareJSで使われていたものだった
問題の原因
- 論文では大きなテキストを貼り付ける際、1000個の個別操作に分割して処理していた
- これはアルゴリズム自体の問題ではなく、実装の問題だった
CRDTの魅力
- CRDT（Conflict-Free Replicated Data Types）は、複数のユーザーが同時にデータを編集できるようにする
- ローカルで遅延なく作業でき、同期時には自動的に一貫性を維持する
- 中央サーバーなしでも動作可能
Automergeの問題点
- Automergeは共同編集のためのライブラリで、RGAアルゴリズムをベースにしている
- 各ドキュメントの文字を一意のIDで管理し、挿入時には親項目を指定する
- 性能上の問題により、260,000件の編集操作を処理するのに5分かかった
- メモリ使用量も非常に大きい
性能最適化
- Automergeの性能問題は、複雑なツリーベースのデータ構造とImmutablejsの使用に起因していた
- Yjsは単一のフラットなリストを使うことで性能を大幅に向上させた
- Yjsは挿入位置を見つけるためにキャッシュを使い、双方向連結リストを使って挿入を効率的に処理する
- Yjsは30倍高速で、メモリ使用量も少ない
Rustへの移行
- Rustはメモリレイアウトを制御できるため、性能をさらに向上させられる
- Diamond typesという新しいCRDT実装により、Yjsより5倍高速な性能を達成した
- Rustで実装されたDiamondは、260,000件の編集操作をわずか56ミリ秒で処理する
結論
- 最適化されたデータ構造と効率的なメモリ管理によって、CRDTの性能を大幅に向上できる
- Rustのような低レベル言語を使えば、さらに高速な性能を実現できる
GN⁺のまとめ
- CRDTは共同編集の未来であり、中央サーバーなしでも一貫性を維持できる強力なツールである
- Automergeの性能問題は、複雑なデータ構造と非効率なメモリ使用にあった
- YjsとDiamond typesは、単純で効率的なデータ構造を使って性能を大きく向上させている
- Rustのような低レベル言語を使えば、さらに高速な性能を実現できる
- 共同編集ツールを開発する際は、YjsとDiamond typesを検討する価値がある
1件のコメント
Hacker Newsのコメント
32個のエントリが最も効率的な理由は、キャッシュラインが64バイトだから
CRDTを使う実際のアプリケーションで、優れた体験を提供している例を見つけるのは難しい
CRDTは強力だが、履歴上の操作（または要素）を残してしまう欠点がある
現在のGitHub Readmeからの引用:
この記事は内容が難しくてもよく書かれていて、読むのをやめられなかった
階層構造を使っているのを見て、入れ子集合を代わりに使ったのか気になった
数年前にこの投稿を偶然見つけた
WASMがネイティブ実行より4倍遅い理由が気になる
AutomergeのRust実装が完了したので、更新されたベンチマークを見るのは興味深いだろう