競合のない複製データ型 (CRDT) は、分散システムでのシームレスなコラボレーションとデータ同期を可能にするデータ構造のクラスであり、競合することなく共同で更新できるようにします。 CRDT は、データの複数のレプリカ間で最終的な一貫性を達成するように設計されており、更新が個別に発生した場合でも、複雑な競合解決メカニズムを必要とせずにすべてのレプリカが同じ状態に収束します。

このブログ投稿では、JavaScript と強力な Yjs ライブラリに焦点を当てて、CRDT とは何か、その用途と種類を詳しく調べ、CRDT がどのように機能するかを理解し、実装方法を学びます。

CRDT の使用例

CRDT は、リアルタイムのコラボレーションとオフライン サポートが重要なシナリオで特に役立ちます。

1. 共同テキスト エディタ: Google ドキュメント、Notion、Etherpad は、リアルタイム編集に CRDT のような構造を使用します。
2. コラボレーティブ デザイン ツール: 人気のある Web ベースのデザイン ツールである Figma は、CRDT を使用してデザイン プロジェクトでのリアルタイムのコラボレーションを可能にします。複数のデザイナーが同じファイルで同時に作業でき、変更はすべてのユーザー間でシームレスに同期されます。
3. 分散データベース: RxDB と Riak は競合のないレプリケーションに CRDT を使用します。
4. マルチプレイヤー ゲーム: プレイヤー間で一貫したゲーム状態を維持するため。

CRDTの種類

CRDT には主に 2 つのタイプがあります:

1. 状態ベースの CRDT: これらはデータ構造の状態全体を複製します。マージは、異なるレプリカの状態を比較して調整することによって行われます。
2. オペレーションベースの CRDT: これらは、データ構造に対して実行されるオペレーションを複製します。マージは、異なるレプリカからの操作を可換的に適用することによって行われます。

CRDT の仕組み

CRDT (Conflict-free Replicated Data Types) は、更新が同時に行われた場合やネットワークの分断が発生した場合でも、データのすべてのレプリカ間で最終的な整合性を確保する原則に基づいて動作します。メカニズムをさらに詳しく見てみましょう:

主要なプロパティ

1. 可換性: このプロパティは、演算の順序が最終結果に影響を与えないことを保証します。たとえば、カウンター CRDT では、2 ずつインクリメントしてから 3 ずつインクリメントすると、3 ずつインクリメントしてから 2 ずつインクリメントするのと同じ結果が得られます。
2. 連想性: これは、操作のグループ化は重要ではないことを意味します。反例を再度使用すると、(1 2) 3 は 1 (2 3) と同じです。
3. 冪等性: 同じ演算を複数回適用すると、1 回適用した場合と同じ効果があります。これは、分散システムで重複メッセージを処理するために非常に重要です。

紛争の解決

CRDT は設計により競合を自動的に解決します:

• 状態ベースの CRDT (CvRDT) の場合、これは 2 つのレプリカの状態を結合するマージ関数によって実現されます。このマージ関数は、可換性、結合性、べき等性である必要があります。
• 操作ベースの CRDT (CmRDT) の場合、操作は可換になるように設計されており、どの順序で適用しても同じ最終状態になることが保証されます。

論理クロック

多くの CRDT 実装では、論理クロック (バージョン ベクトルやドット付きバージョン ベクトルなど) を使用して、操作の因果関係の履歴を追跡します。これは、同時操作の順序を決定したり、レプリカがすでに認識した更新を特定したりするのに役立ちます。

Yjs を使用した JavaScript での CRDT の使用

CRDT を最初から実装するのは複雑になる場合があります。ただし、プロセスを簡素化するライブラリが利用可能です。 JavaScript の場合、最も人気のある CRDT ライブラリの 1 つは Yjs です。これは、さまざまなデータ型をサポートする高性能 CRDT 実装です。 Yjs を使用して、複数のユーザーがメモリ内の同じドキュメントで作業していることをシミュレートする、単純な ToDo リスト アプリケーションを作成しましょう。

Yjs を使用して共有 ToDo リストを実装する方法の例を次に示します:

作成した ydocs を使ってみましょう:

この例では、2 つの Yjs ドキュメント (ydoc1 と ydoc2) を作成して、2 人のユーザーが同じ ToDo リストで作業していることをシミュレートします。各ドキュメントには、todo 用の独自の共有マップがあります。

todo を追加、更新、削除する関数と、2 つのドキュメント間の状態を手動で同期する syncDocs 関数を定義します。これは、クライアント間で更新が交換されるネットワーク環境で何が起こるかをシミュレートします。

結論

CRDT は、オンラインでもオフラインでもシームレスに動作できる、協調的な分散アプリケーションを構築するための強力なソリューションを提供します。基礎となる概念は複雑になる可能性がありますが、Yjs のようなライブラリを使用すると、開発者はアプリケーションで CRDT の機能を簡単に活用できます。分散システムがさらに普及するにつれて、CRDT を理解して利用することは、開発者にとってますます貴重なスキルになるでしょう。

役立つリンク

1. Yjs
2. CRDT
3. Tiptap - 共同作業用テキストエディタ