CRDTはレプリカを分岐させながらもロックなしで収束させる

複数ユーザーによる編集には根本的な問題がある。二人が同じ文書をオフラインや異なる接続で編集すると、両方のコピーが変化し、誰かがそれらを調停しなければならない。従来のアプローチは、文書の一部をロックして協働を妨げるか、状態の組み合わせが爆発し正しさの証明が難しいことで知られる操作変換を用いるかのいずれかだった。

2011年、Marc Shapiroと同僚たちは競合しない複製データ型（CRDT）を提案した。これは並行更新が可換となるように設計されたデータ構造である。すべての更新が可換でマージが結合的であれば、分岐したレプリカはどの順序でマージしても同一の状態に収束し、中央コーディネータも競合ダイアログも不要となる。レジスタ、カウンタ、集合、テキストエディタはすべてこの方法で構築できる。

理論はその後数年間で固まった。Martin Kleppmannと同僚たちによる2018年のOpSets論文は、複製データ型アルゴリズムを機械的に検証する実行可能なフレームワークを構築し、協調的テキストの正しさの性質を明らかにして、いくつかの公表済みアルゴリズムがそれを違反していたことを示し、従来はロックなしでは不可能と考えられていたアトミックな移動操作を仕様化した。

実運用システムがこのアイデアを採用した。FigmaのマルチプレイヤーエンジンはCRDT研究に明示的に触発されており、そのサーバー権威型のプロパティ単位設計は最後の書き手が勝つレジスタのように機能し、同社が操作変換を不必要に複雑として却下した後に選ばれた。Redis、Riak、Cosmos DBはCRDTベースのデータ型を提供し、AppleのNotesはCRDTを用いてデバイス間でオフライン編集を同期する。

データ型を設計によりマージ可換にする

可換なマージにより結果が更新順序から独立する

レプリカはオフラインで編集し、中央権威なしで収束できる

機械的検証が手弁当の正しさの証明に取って代わった

Figma流の製品はOTの複雑さなしにリアルタイム協働を手に入れた

調整がボトルネックなら、調整が不要になるようにデータを再設計せよ。結果が順序に依存しない操作を選べば、並行ユーザーは無償で一貫性を得る。

CRDTは今やオフラインファーストの協働と複製の標準的な答えである。Figmaのマルチプレイヤー同期、Apple Notes、RedisとRiakのデータ型、ピアツーピア編集ツールがこのアイデアの上に構築されており、研究の系譜はテキスト編集、ツリー移動、ビザンチン設定といった難所へと続いている。