私が間違っていました。CRDTこそ未来です。

 (josephg.com)
24 ポイント 投稿者 xguru 2020-10-05 | 10件のコメント | WhatsAppで共有

Google Waveの開発者が語る、Conflict-free Replicated Data Types の話

→ CRDT : リアルタイム協業ツールで同時編集をサポートするデータ構造

  • WaveはOT(Operational Transform)ベース : すべての変更に対する時系列リストを保存。リアルタイムの git-rebase と同じ

  • OTの問題の一つは、中央集権的なサーバー/DBが必要だということ

→ Google Docs（これもOTベース）で文書に人が殺到したときに「この文書は過負荷のため編集できません」と表示される理由も、おそらくこれでは？

→ 文書を分割したり、DBトランザクションにリトライループを入れたりして回避は可能（シリアライゼーション問題をDBに移してしまう）

→ しかし完璧ではない。Waveは複数人が同時編集してもよく動いてはいたが、バグが多かった。複雑すぎる

  • CRDT の台頭

→ Waveが使っていたアルゴリズムは1995年に発明されたもの。OTがうまく動くよう研究は続けられてきたが、CRDTのほうがより有望

→ CRDTは別のアプローチを取り、中央DBなしでリアルタイム編集が可能

→ 以前問題とされていた速度/容量/機能/複雑さがすべて改善された

  • 速度 : 最近のCRDT（Automerge / RGA or y.js / YATA）では log(n) レベルの参照が可能

  • 容量 : Martin の Columnar エンコーディングでは、文書サイズの1.5〜2倍程度で保存可能

  • 機能 : 理論上は Rewinding および replaying が可能。もちろん、まだ実装した人はいない

  • 複雑さ : 実装のサイズはOTよりCRDTのほうが大きいだろうが、大差はない

→ 上記の改善点は Automerge でまもなく提供される予定

  • リアルタイム編集においては、残念ながらOTとその関連作業はもはや必要なくなるだろう

→ OTのすべての機能はCRDTに入れられるが、その逆は不可能

→ OTの利点は中央集権的なソフトウェアに向いていることだが、分散アルゴリズムは中央集権方式でもうまく動く

→ WASMで実行される高品質なCRDTは、JSのOT実装より速くなるはず

  • 今こそ、軽量で高速なCRDTを作るべき時期

→ 学術的な部分はほぼ完成しており、今は優れた実装（kick-ass）が必要な段階

関連記事

10件のコメント

 
hackerwins 2020-10-05

Yorkieプロジェクトを開発しているホン・ヨンテクと申します。

同時編集アプリ向けのドキュメントストアであるYorkieも、CRDTをベースに作っています。

https://github.com/yorkie-team/yorkie
 
iolothebard 2020-10-05

私が間違っていました。CRDTこそ未来です。

OTならundo/redoを楽に実装できるのに……CRDTはsnapshot以外に方法がない……
 
xguru 2020-10-05

Automerge の場合、ライブラリ自体が undo/redo をサポートしてくれます。実装する人は大変でしょうが、ライブラリを使う立場としてはまあ（笑）
 
ffdd270 2020-10-05

https://www.notion.so/sihawn/CRDT-1dc1af26d60144c09eadd178e0ae6e0d

全文を翻訳していたのですが、投稿するのを忘れていました ;_; いったんPapagoベースで読みながら、不自然な部分だけ修正しました。全体的な雰囲気がどんな感じか？ 読んでみたい方は上のリンクをご確認ください〜

コメント欄に載せるには……長すぎるので ;_; Notionのリンクで共有します。
 
ffdd270 2020-10-05

考えてみると、Notion も CRDT を使っているのかもしれませんね！
 
xguru 2020-10-05

OTを使っているのは Google Wave/Google Docs/MS Office365

CRDTを使っているのは Figma/Apple Notes および Riak/Redis など
 
xguru 2020-10-05

私が間違っていました。CRDTが未来です。

Figma のマルチユーザー技術はどのように動作するのか https://ja.news.hada.io/topic?id=814
 
xguru 2020-10-05

記事にリンクされている Automerge 開発者 Martin Kleppmann の動画「CRDTs: The Hard Parts」は、本当に説明がうまいですね。

序盤では OT と CRDT をうまく比較しながら説明してくれます。後半は CRDT の実装に関する深い話です。

https://www.youtube.com/watch?v=x7drE24geUw

JS でコラボレーションツールを作るときに使う CRDT ライブラリ
 
xguru 2020-10-05

私が間違っていました。CRDTが未来です。

コラボレーションシステムへ向けて: OTアルゴリズムからCRDTシステムへ

https://deview.kr/2013/detail.nhn?topicSeq=66

国内の発表では、CRDTの話を扱ったほぼ唯一の内容ですね。
 
hackerwins 2020-10-06

この発表をされたヒョンゴルさんは、本文で述べられているRGAを作られました。

Yorkieも、リスト型データタイプをRGAをベースに実装しました。

https://github.com/yorkie-team/yorkie/issues/2