CRDT は、「Conflict-free Replicated Data Types」の略称であり、日本語では「無衝突複製データ型」と翻訳されます。これは、複数のデバイスやノード間でデータ構造を複製および同期するための方法であり、複雑な競合解決を必要としません。CRDT は、分散システムにおけるいくつかの難しい問題、特にネットワークの分断や遅延が発生する可能性がある場合に対処するために設計されています。
まず、一般的な問題を考えてみましょう：複数の人が同じドキュメントをオンラインで共同編集する（たとえば、Google ドキュメントなど）。各人は自分のデバイスで編集を行い、これらの変更を他のすべての人のデバイスに同期する必要があります。しかし、2 人がほぼ同時に同じ場所で編集した場合、どのように処理すればよいでしょうか？これは典型的な競合の問題です。
従来の解決方法は、ロックメカニズムや競合解決戦略を使用することですが、これらの方法はシステムを複雑にし、ネットワークの遅延や切断の状況ではパフォーマンスが低下することがよくあります。
CRDT は、より優れた解決策を提供します。CRDT の設計思想は、すべての可能な操作が交換可能であるようなデータ構造を設計できれば（つまり、操作の順序に関係なく結果が同じになる）、競合を回避できるというものです。そのため、各デバイスは自由に、待つことなく、ロックすることなく操作を行い、これらの操作を他のデバイスに同期することができます。すべての操作が最終的にすべてのデバイスに到達すれば、すべてのデバイス上のデータの状態は一致します。
CRDT は、分散データストレージシステムやマルチユーザーアプリケーションを簡素化するためのデータ構造です。多くのシステムでは、特定のデータのコピーを複数のコンピュータ（つまり、コピー）に保存する必要があります。これには、次のようなシステムが含まれます。
- データをローカルデバイスに保存し、そのデータを同じユーザーの他のデバイスに同期する必要があるモバイルアプリケーション（カレンダー、ノート、連絡先、リマインダーなど）。
- 同じデータセンターまたは異なる場所にデータの複数のコピーを維持する分散データベース。これにより、いくつかのコピーがオフラインになった場合でもシステムが正常に動作し続けることができます。
- Google ドキュメント、Trello、Figma などのオンラインの共同編集ソフトウェア。複数のユーザーが同じファイルやデータを同時に変更できます。
- 大規模なデータストレージおよび処理システム。これらのシステムは、データを複製してグローバルスケーラビリティを実現します。
これらのすべてのシステムは、データが異なるコピーで同時に変更される可能性がある場合に対処する必要があります。大まかに言えば、このようなデータ変更を処理する方法は 2 つあります。
- 強い一貫性の複製
コピーはお互いと協力して変更を適用するタイミングと方法を決定します。この方法は、直列化可能なトランザクションやリニアライズなどの強い一貫性モデルをサポートします。ただし、この調整を待つことは、これらのシステムのパフォーマンスを低下させます。さらに、CAP 定理によれば、コピーがシステムの残りの部分から切断された場合（ネットワークの分断や一時的な接続の問題など）、そのコピーにはデータの変更ができません。 - 楽観的な複製
ユーザーは、オフラインまたは他のコピーとの接続が切断されている場合でも、任意のコピー上のデータを独立して変更できます。この方法は、最大のパフォーマンスと可用性を実現しますが、複数のクライアントやユーザーが同じデータを同時に変更すると競合が発生する可能性があります。そのため、コピー間の通信時にこれらの競合を解決する必要があります。
CRDT は、楽観的な複製システムで競合を解決するために使用されます。 CRDT は、異なるコピーで行われたデータの変更に関係なく、データを一貫した状態にマージできることを保証します。このマージは、CRDT が自動的に実行し、特別な競合解決コードやユーザーの介入は必要ありません。
さらに、CRDT の重要な特徴の 1 つは、分散動作をサポートすることです。つまり、単一のサーバーを使用しないことを前提としており、ピアツーピアネットワークやその他の分散環境で使用できます。この点で、CRDT は Google ドキュメント、Trello、Figma などで使用されるアルゴリズムとは異なり、これらのツールではユーザー間のすべての通信がサーバーを介して行われる必要があります。
これを実現するために、CRDT はデータの変更に特別な処理を行う必要があります。たとえば、CRDT セットの場合、追加および削除操作には他のデバイスで同期する際に競合を正しく処理できるように、いくつかの追加情報を覚えておく必要があります。その中でも一般的なタイプの 1 つが「Grow-only Set（増加のみの集合）」です。このタイプの CRDT では、集合に要素を追加することはできますが、要素を集合から削除することはできません。この設計の利点は、追加操作が交換可能であることです。つまり、要素をどのような順序で追加しても、最終的な結果は同じです。
しかし、現実の世界では、集合から要素を削除する必要があることがよくあります。この問題を解決するために、もう 1 つの CRDT である「Two-phase Set（2 段階集合）」があります。このタイプの CRDT では、各要素には 2 つの状態があります：追加と削除。初期状態は追加であり、要素を削除すると状態が削除に変わります。したがって、他のデバイスが同じ要素を同時に追加しても、1 つのデバイスがその要素を削除とマークした場合、その要素は削除されたと見なされます。つまり、この集合では削除操作に優先順位があります。このような設計により、異なるデバイス間で同期する際に競合を正しく処理できるようになります。
全体として、CRDT の設計は、特定の処理によって操作が異なるデバイスで並行して行われ、マージ時にデータの一貫性を維持するようにすることで、データ変更を処理します。このような設計により、CRDT は分散システムやマルチユーザーアプリケーションに非常に適しており、並行操作やネットワークの遅延による複雑な問題を処理できます。
CRDT には 2 つのタイプがあり、強い最終的な一貫性を提供できます：操作ベースの CRDT と状態ベースの CRDT。
状態ベースの CRDT は通常、設計と実装が容易です。通信の基礎となる唯一の要件は、ある種のゴシッププロトコルです。欠点は、各 CRDT の完全な状態が最終的に他のすべてのコピーに転送される必要があることで、これには大きなコストがかかる可能性があります。一方、操作ベースの CRDT は、通常、更新操作のみを転送するため、通常は非常に小さなサイズです。ただし、操作ベースの CRDT では、通信ミドルウェアが保証する必要があります。他のコピーに転送される操作が破棄されたり、重複したりせず、因果的な順序で転送されることができます。
-
CmRDT
操作ベースの CRDT は、交換可能な複製データ型（commutative replicated data types）とも呼ばれます。CmRDT コピーは、状態を伝播するために更新操作のみを転送します。たとえば、単一の整数の CmRDT では、操作（+10）や（-20）をブロードキャストすることができます。コピーは更新を受け取り、これらの更新をローカルで適用します。これらの操作は交換可能です。ただし、必ずしも冪等ではありません。したがって、通信インフラストラクチャは、すべての操作が他のコピーに配信され、重複しないことを保証する必要がありますが、どの順序で転送されてもかまいません。 -
CvRDT
状態ベースの CRDT は、収束複製データ型（convergent replicated data types）とも呼ばれます。CmRDT とは異なり、CvRDT は完全なローカル状態を他のコピーに送信し、これらのコピーで状態を交換可能で結合可能で冪等な関数でマージする必要があります。マージ関数は、任意の 2 つのコピーの状態を結合するための接続を提供し、すべての状態の集合が半束を形成します。更新関数は、内部状態を半束と同じ偏序規則で単調に増加させる必要があります。関数は内部状態に基づいて、半束と同じ偏序規則に従っています。