分散ストレージまたは任意のデータのエディターでは、ロックや競合のないオフラインでの変更のサポートが必要になることがよくあります。 これにはさまざまなアプローチが使用されます。そのうちの1つは、競合のない複製データ型（CRDT）アルゴリズムとデータ型です。

なんで？

読み取り専用レプリカの作成は簡単で、誰もがその方法を理解しています。 レプリカに書き込むことができるのは難しいことです。 このようなCAP定理があります。データの一貫性（持続性）、可用性（可用性）、分離への抵抗（パーティション許容度）-任意の2つを選択します。 CRDTでは、このタスクは強力な結果整合性（ SEC ）と状態の単調性を提供することによって達成されます。

強い結果整合性

何らかの方法で交換するレプリカに変更を加えることができるとします。 最終的な一貫性とは、相互作用とデータストレージのような組織であり、いずれかのレプリカに変更を加えた後、すべてのレプリカは最終的に同等の状態になります。

強い最終整合性には別の制限があります。同じ更新を受信するレプリカ（順序に関係なく）は、更新を受信するとすぐに同等の状態になります。

SECと順次整合性を混同しないでください。たとえば、要素を追加および削除できるリストでは、SECを満たすために追加と削除の順序を保証する必要はありません（たとえば、追加による削除の優先順位がある場合があります）。

対立と単調さ

ECシステムに競合がある可能性があります。 競合とは、異なるレプリカに適用されると、それらを一貫した状態に導く変更ですが、レプリカの状態が結合されると、特定のシステム不変条件に違反します。 競合は、状態のロールバックまたはその他の方法で解決されます。これには、ユーザーの操作も含まれる場合があります。

CRDTは、システムがSECを提供し、その状態が競合につながることなく単調に進行することを前提としています。 この意味での単調性は、ロールバックがないことを意味します。システムを以前の状態に戻すことで操作を元に戻すことはできません。 そのようなシステムの状態は、半順序関係によって接続されています。数学では、ユニオン操作が定義されたそのようなシステムは半格子と呼ばれます。

格子と半格子

半格子は、二項演算が可換でべき等である半群です（ ロシア語 、 さらに詳しくは英語ですが、ここでは数学を使用して 、Wikipediaに正式な説明があります ）。

半格子は、部分的に順序付けられたセットです。要素（必ずしもすべてではない）は、「フォロー」関係によって接続されます。

操作は半格子で定義されます：

• べき等：a⋁a = a
• 連想：（a⋁b）⋁c = a⋁（b⋁c）
• 可換：a⋁b = b⋁a

この操作は、上部（結合）半格子の正確な下限（LUB）、または下部（満たす）半格子の正確な下限（最大下限）のいずれかです。

木と半格子の違い：



これは完全なラティスであり、LUBとGLBの両方を同時に定義します。



上部半格子の例がKDPVに描かれています。 違いは、要素を結合するために共通の祖先が必要ないことです。 これらは現在私たちが興味を持っている代数構造です。



gitやsvnなど、バージョン管理システムの多くの状態は、ある意味では完全なラティスです。半順序関係が定義されており、リビジョンには共通の祖先があり、隣接している場合があります。 上部半格子の要素を使用して、結合操作を実行し、2つの要素を結合できます。

CvRDTとCmRDT

さまざまなタスクに対して、相互作用とデータストレージを整理するさまざまな方法が便利です。 CRDTは通常2つのクラスに分けられます。

• 可換（ c o m mutative、CmRDT、opベース）：リストがあると仮定します。 アイテムを追加する場合、この変更された状態（追加されたアイテム）のみをすべてのレプリカに送信します。 レプリカの状態が更新を受信する手順に依存しないように、操作は可換でなければなりません。
• ストレージベースの状態（ c on v ergent：CvRDT、状態ベース）：この場合、個別の更新は送信されませんが、データ構造全体（つまり、リストの場合はリスト全体）が送信されます。 データ構造は次の操作をサポートする必要があります。
  
  
  • クエリ-状態を変更せずに何かを読みます（例：リストにアイテムがありますか？）
  • 更新-構造の変更（例：リストへのアイテムの追加）
  • マージ-別のレプリカからの状態を凍結します。 この操作は、可換、連想、および内在的である必要があります。あらゆる方向の状態のヘッジは、システムを以前の状態に「戻し」ませんが、システムの状態を単調に増やします。 すべてのレプリカを結合すると、レプリカで行われたすべての変更を結合して、同等の状態になります。
  
  
  

視覚的比較：



クラスCvRDTとCmRDTは同等です（この定理の証明は、以下の「リンク」にあるMarc Shapiroの研究にあります）。 すべてのCRDT構造は、CvRDTとCmRDTの両方として表すことができます。

ただし、データ転送方法の要件の観点からは、それらは異なります：CmRDTはレプリカに通知を配信する何らかの方法を必要としますが、CvRDTが必要とするのは状態の書き込みと読み取りだけです（ただし、この状態は非常に大きい場合があります）。

CRDTの例と記録

アイテムを追加および削除できるリストを作成しましょう。 2Pセットと呼ばれます。

レプリカには2つのセットがあります。追加された要素（A）と削除された要素（R。このセットは廃棄標識セットと呼ばれることが多い）です。最初は空です。 要素を追加するとき、それをAに追加し、それを削除するときにRに追加します。セットに含めるかどうかの確認は、Rに要素があるかどうか、およびAにあるかどうかを確認することからなります。追加よりも削除が重要であることがわかります。その逆：要素はRおよびAから削除されません。

数学レコードは次のようになります。



これは、各操作の実行のためにリスト全体を渡すCvRDT構造です。 明らかな方法で、CmRDTに相当するものを変換できます。 簡単にするために、削除の前に常にaddが配信される非常に単純なケースを想定します。 CmRDT数学レコードは次のようになります。

その他の構造

よく知られ、作品で説明され、ライブラリに実装されているものには、次のような構造があります。

• Gカウンター：（成長のみ）単調に増加するカウンター
• PN-Counter：減らすことができる（正負）カウンター
• LWW-Register：（last-writer-wins）最後のエントリの原則で登録することの優先度が高い
• MV-Register：（複数値）複数値レジスタ
• Gセット：削除せずに多くのアイテム
• 2Pセット：優先削除あり
• PN-Set：enable-delete操作カウンターを使用します
• LWW-Set：優先操作時間
• ORセット：（observed-remove）識別子付きのリスト

リストに基づいてグラフ内の頂点と関係を記述する構造もあります。

CRDT最適化

CRDT構造を作成する通常の方法は、他からCRDT構造を組み立てることです。たとえば、2Pセットは、追加と削除の2つのリストで構成されます。 実際には、データ転送の操作または量に制限が課される場合があります。 この場合、いくつかの譲歩をすることができます。 たとえば、アイテムがリストに頻繁に追加および削除される場合、削除されたアイテムのリストは時間の経過とともに大きく拡大します。 削除されたものを何らかの合理的な条件で削除するガベージコレクタを作成できます。 たとえば、1年以上前に削除されたものや、すべてのレプリカによって通知が受信されたもの。

CRDTとOT

操作変換は、テキスト編集で一般的に使用されるアプローチです。 どちらのアプローチも一貫性（EC）を提供します。 OTには、より高いサーバー要件、より複雑で安定性の低いアルゴリズムがあります。 また、いくつかの研究は、実装で述べられているように、OTアルゴリズムが時々収束しない（収束する）ことを示しています。 しかし、明確に選択して「どちらが良い」と言うことは不可能です。 よく知られているテキスト編集CRDTには、たとえば、WOOT（Without Operational Transformation）、Treedoc、およびLogootがあります。

KeePassのCRDT

KeePassにはファイルのフリーズ機能があります。同期を使用して人間をオフラインにするには、 Webバージョンのマージに特別な注意を払わなければなりませんでした。 KeePassはすべてのオブジェクトに一意の識別子を割り当て、削除されたすべてのIDをDeletedObjectsに保存します。 ディレクトリグラフを同期するために、最後に位置が変更された日付（場所の変更日）が保存されます。

しかし、ニュアンスがあります。 レコードには、アイテムを削除できる変更履歴が残っています。 履歴エントリは時間によってのみ識別されます。 履歴から削除されたエントリは、同期中にどこにも保存されません。 これは何ですか？ ストーリーからレコードを削除して以前の状態にとどまると、魔法のように戻ります。 アプリケーションの主なシナリオとしての同期の条件では、ストーリーがしばしば戻ってくることがわかります。

どうする

なぜなら 他の顧客に影響を与えることはできません。制限を入力できます。 以下の仮定を考慮してください。

• ファイルはp2pではなく中央ストレージを介して同期されます
• ファイルとともに、メタデータをレプリカにいつでも保存できます

これに基づいて、削除および追加された履歴状態のリストを保持するために、ファイルに変更を加えた瞬間からリポジトリに変更が送信されるまで決定が行われました（ローカルトゥームストーンセット）。 同時に、もちろん、過去の任意のp2pファイルとの同期は依然として奇妙ですが、これは主なシナリオではありません。

リポジトリに変更を送信するには、クライアントは次のことを行う必要があります。

1. ファイルのリビジョン（versionTag）を最後に受信したものと比較します
2. 変更されている場合は、ロードしてフリーズします
3. ローカルに変更がある場合は、versionTagチェックでアップロードします
4. 競合する場合goto 2
5. ローカル状態のクリア（墓石セット）

参照資料

CRDT-ウィキペディア

CRDTの読み物 -多くの便利なCRDT出版物

CRDT-数学の少ない説明（GitHub） -数学のないCRDTの簡単な説明

crdt_notes（GitHub） -1ページに収集されたCRDTアルゴリズム

競合のない複製されたデータ型（ペーパー） -CRDTの概要

収束および可換複製データ型の包括的な研究（ペーパー） -数学と写真による詳細な説明、40ページ

最適化された競合のない複製セット -CRDT構造の最適化の例

kdbxweb（GitHub） -問題のセイウチのサポートでKeePass形式を操作するためのjs-lib