Conflict-free replicated data types#
競合のないレプリケートデータ型CRDTは、従来の解決のように行の1つを破棄するのではなく、同時に変更された行からの値のマージをサポートしています。
各CRDTタイプは、bdr.crdt_handlers
カタログに追加される追加のコールバックを備えた別のPostgreSQLデータタイプとして実装されます。マージプロセスは、適用側のPGDライタ内で発生し、ユーザーアクションは必要ありません。
- CRDTでは、
CLCD で説明しているように、テーブルで列レベルの競合解決を有効にする必要があります。
実行する必要がある唯一のアクションは、整数などの標準のビルトインデータ型ではなく、CREATE / ALTER TABLEで特定のデータ型を使用することです。たとえば、1つの通常の整数カウンターと単一の行を含む次のテーブルを検討します。
CREATE TABLE non_crdt_example (
id integer PRIMARY KEY,
counter integer NOT NULL DEFAULT 0
);
INSERT INTO non_crdt_example (id) VALUES (1);
2つのノードで次のSQLを同時に発行するとします。
UPDATE non_crdt_example
SET counter = counter + 1 -- "reflexive" update
WHERE id = 1;
両方の更新を適用した後、次のクエリを使用して結果の値を確認できます。
SELECT * FROM non_crdt_example WHERE id = 1;
id | counter
-----+-----------
1 | 1
(1 row)
このコードは、 update_if_newer
競合リゾルバーが原因でインクリメントの1つが失われたことを示しています。代わりにCRDTカウンターデータ型を使用する場合、結果は次のようになります。
CREATE TABLE crdt_example (
id integer PRIMARY KEY,
counter bdr.crdt_gcounter NOT NULL DEFAULT 0
);
ALTER TABLE crdt_example REPLICA IDENTITY FULL;
SELECT bdr.alter_table_conflict_detection(crdt_example,
column_modify_timestamp, cts);
INSERT INTO crdt_example (id) VALUES (1);
再度、2つのノードで次のSQLを同時に発行し、変更が適用されるまで待ちます。
UPDATE crdt_example
SET counter = counter + 1 -- "reflexive" update
WHERE id = 1;
SELECT id, counter FROM crdt_example WHERE id = 1;
id | counter
-----+-----------
1 | 2
(1 row)
この例は、CRDTが他の方法で競合する非同期同時更新に直面しても、アキュムレータ列が動作できることを示しています。
crdt_gcounter タイプは、例が示すように、 x = x + 1
などの再帰的UPDATE SQLでのみ動作する状態ベースのCRDTタイプの例です。
bdr.crdt_raw_value
構成オプションは、クエリが現在の値またはCRDTタイプの完全な内部状態を返すかどうかを決定します。デフォルトでは、現在の数値のみが返されます。
true
に設定されている場合、クエリーは完全な状態の表現を結果ます。特殊なハッシュ演算子
#
を使用して、特殊な演算子デフォルト動作を使用せずに現在の数値のみを要求できます。
bdr.crdt_raw_value = on
を使用して完全な状態がダンプされた場合、値はbdr.crdt_raw_value = on
でのみリロードできます。
注釈
bdr.crdt_raw_value は、クライアントに返されたデータ、つまり選択リストの単純な列参照のみのフォーマットを適用します。クエリーの他の部分の列参照たとえば`WHERE` 句またはselectリストの式などは、 # 演算子を使用する必要がある場合があります。
CRDTデータ型の別のクラスは、 delta CRDT タイプと呼ばれます。これらは、オペレーションベースのCRDTの特別なサブクラスです。
デルタCRDTでは、値の更新は、同じノード上の以前の値と比較されます。次に、変更は他のすべてのノードにデルタとして適用されます。
CREATE TABLE crdt_delta_example (
id integer PRIMARY KEY,
counter bdr.crdt_delta_counter NOT NULL DEFAULT 0
);
ALTER TABLE crdt_delta_example REPLICA IDENTITY FULL;
SELECT bdr.alter_table_conflict_detection(crdt_delta_example,
column_modify_timestamp, cts);
INSERT INTO crdt_delta_example (id) VALUES (1);
2つのノードで次のSQLを同時に発行するとします。
UPDATE crdt_delta_example
SET counter = 2 -- notice NOT counter = counter + 2
WHERE id = 1;
両方の更新を適用した後、次のクエリを使用して結果の値を確認できます。
SELECT id, counter FROM crdt_delta_example WHERE id = 1;
id | counter
-----+---------
1 | 4
(1 row)
通常のinteger 列の場合、結果は2
になります。ただし、デルタCRDTカウンターで行を更新する場合、古い行バージョンで開始し、新しい行バージョンを作成し、両方をリモートノードに送信します。そこで、そこにあるバージョンたとえばローカルバージョンなどと比較します。標準CRDTはNEWとLOCALバージョンをマージしますが、デルタCRDTはOLDとNEWバージョンを比較し、デルタをローカルバージョンに適用します。
CRDTタイプは、bdr の一部としてbdr
スキーマにインストールされます。便宜上、基本的な演算子+ 、#
、および! と多くの一般的な集計関数min 、max
、sum 、およびavg がpg_catalog
で作成されます。したがって、search_path を調整せずに使用できます。
重要な問題は、クエリのプランニングと最適化がこれらの新しいデータ型でどのように機能するかです。
CRDTタイプは透過的に処理されます。 ANALYZE
とオプティマイザーの両方が動作するため、他に何もせずに推定とクエリプランニングは正常に動作します。
状態ベースおよびオペレーションベースのCRDT#
[1]の表記に従って、オペレーションベースと状態ベースのCRDTの両方が実装されます。
オペレーションベースのCRDTタイプCmCRDT#
操作は明示的に転送されないが、リモートノードから受け取った古い行と新しい行から計算されるため、操作ベースの型の実装は簡単です。
現在、次のオペレーションベースのCRDTが実装されています。
crdt_delta_counter—bigintカウンターインクリメント/デクリメントcrdt_delta_sum—numericsumインクリメント/デクリメント
これらの型は、デルタを計算する少しのコードで既存のデータ型を活用します。たとえば、
crdt_delta_counter はbigint 上のドメインです。
このアプローチは、デルタを計算する方法が知られている型でのみ可能ですが、結果はシンプルで安価、スペースとCPUの両方の点で、いくつかの追加の利点があります。たとえば、基になるデータ型の演算子/構文を活用できます。
主な欠点は、非同期コンカレント環境ではこの値を確実にリセットできないことです。
注釈
カスタムデータタイプを作成し、状態と最後のオペレーションを保存することにより、より複雑なオペレーションベースのタイプを実装できます。すべての変更はデコードされて転送されるため、複数の操作は必要ありません。しかし、その時点で、主な利点単純さ、既存のデータ型の再利用などは、領域要件を除き、状態ベースの型たとえば、まだリセット機能と比較して利点を得ることなく失われます。ノードごとの状態は必要ありません。
状態ベースのCRDTタイプCvCRDT#
状態ベースの型は、より複雑な内部状態を必要とするため、操作ベースの型のように通常のデータ型を直接使用できません。
現在、4つの状態ベースのCRDTが実装されています。
crdt_gcounter—bigintカウンターインクリメント専用crdt_gsum—numericsum/counter インクリメントのみcrdt_pncounter—bigintカウンターインクリメント/デクリメントcrdt_pnsum—numericsum/counter インクリメント/デクリメント
内部状態には通常、ノードごとの情報が含まれるため、ディスク上のサイズは増加しますが、追加の利点が得られます。カスタムデータ型を実装する必要があるということは、より多くのコードin/outファンクションと演算子を意味します。
利点は、値を確実にリセットする機能、変更が失われた場合のある程度の自己修復性正常に動作するクラスターでは発生しません、およびソースノード以外のノードから変更を受信できる機能です。
たとえば、ノードAで値が変更され、変更はBにレプリケートされますが、AとC間のネットワークの問題によりCにレプリケートされません。 Bが値を変更し、この変更がCにレプリケートされる場合、それにはAからの元の変更。オペレーションベースのCRDTを使用すると、A-Cネットワーク接続が再び動作し始めるまで、ノードCは変更を受信しません。
CvCRDTの主な欠点は、ディスク領域とCPU使用率の面でコストが高いことです。クラスターから既に削除されたノードを含む、ノードごとに少しの情報が必要です。状態varlenaタイプにシリアル化の複雑な性質は、CPU使用量の増加を意味します。
ディスク領域の要件#
重要な考慮事項は、CRDTタイプ、特にディスク上のサイズに関連するオーバーヘッドです。
オペレーションベースの型の場合、型は他の型の上のドメインにすぎないため、これは簡単です。ノードの数に関係なく、必要なディスク領域は同じです。
crdt_delta_counter—bigintと同じ8バイトcrdt_delta_sum—numericと同じ変数、精度とスケールに依存します
操作ベースのCRDTタイプはノードごとの情報を保存しないため、ノードの数への依存関係はありません。
状態ベース型の場合、状況はより複雑です。すべてのタイプは可変長であり、基本的にbytea
列として保存され、ヘッダーと、値を変更した各ノードの特定の量のノードごとの情報で構成されています。
bigint
バリアントの場合、おおよそのサイズを計算する式は次のとおりです。
crdt_gcounter—32B (header) + N * 12B (per-node)crdt_pncounter-—48B (header) + N * 20B (per-node)
N は、この値を変更したノードの数を示します。
numeric
バリアントの場合、ヘッダー部分とノードごとの部分の両方にnumeric
可変長値が含まれるため、正確な式はありません。保持する必要があるこのような値の数を知るには
crdt_gsum固定
20B (header) + N * 4B (per-node)変数
(2 + N)numeric値
crdt_pnsum固定
20B (header) + N *4B (per-node)変数
(4 + 2* N)numeric値
注釈
複数のノードで値が更新されない場合、クラスター内のノードの数は関係ありません。また、更新が同時実行されたかどうか、競合が発生したかどうかも関係ありません。
さらに、これらのノードのうちのいくつがクラスターから既に削除されたかは関係ありません。状態を圧縮する方法はまだありません。
CRDTタイプと競合処理#
テーブルにはCRDT列と非CRDT列の両方を含めることができるため、ほとんどの列は非CRDTであることが予想されるため、通常の競合解決とCRDTマージの両方を行う必要があります。
競合の解決は最初に発生し、保持するタプルapplytupleと破棄するタプルを決定します。次にマージフェーズが発生し、CRDT列のデータを破棄タプルから適用タプルにマージします。
注釈
この処理により、毎回マージが発生する必要があるため、単純な競合解決に比べてCRDTタイプのコストが多少高くなります。これは、競合解決で高速パスのいずれか現在のトランザクションで変更されたパスなどを使用できる場合でも、当てはまります。
CRDTタイプと競合レポート#
デフォルトでは、検出された競合は個別に報告されます。 CRDTタイプがなければ、競合解決は本質的に使用可能な情報の半分を破棄するため、これは理にかなっています構成に応じてローカルまたはリモート行。これにより、データの損失が発生します。
CRDTタイプを使用すると、何も捨てずに情報の両方の部分を組み合わせることができ、データ損失の問題を排除します。このアプローチにより、競合報告が不要になります。
このため、CRDTマージによって競合を完全に解決できる場合、競合レポートはスキップされます。各列は、次の2つの条件の少なくとも1つを満たす必要があります。
ローカルタプルとリモートタプルの値が同じNULLまたは等しい。
CRDTデータ型を使用するため、マージできます。
注釈
CRDT列はないが、ローカル/リモートタプルのすべての値が等しい場合にも、競合レポートはスキップされます。
CRDT値のリセット#
CRDT値のリセットは可能ですが、特別な処理が必要です。クラスターの非同期の性質は、実装方法に関係なく、さまざまなノードが変更ストリームのさまざまな場所でリセット操作を認識する可能性があることを意味します。別のノードが同時にリセットを開始する場合があります。つまり、他のノードからリセットを観察する前に。
言い換えれば、リセット操作を正しく動作させるには、通常の操作に対して可換である必要があります。単一ノードでうまく機能する可能性のある値をリセットする多くの単純な方法は、この理由で失敗します。
たとえば、値をリセットする最も簡単なアプローチは次のとおりです。
UPDATE crdt_table SET cnt = 0 WHERE id = 1;
状態ベースのCRDTでは、これは機能しません。他のノードの状態を破棄しますが、ローカルでのみです。リモートノードのマージファンクションによって追加され、値の発散を引き起こし、最終的に他のノードでの変更によりそれを受信します。
オペレーションベースのCRDTでは、更新が-cnt
の減算として解釈されるため、これは機能するように見える場合があります。ただし、それは同時リセットがない場合にのみ機能します。
2つのノードが同時にリセットを実行しようとすると、デルタが2回適用され、負の値を取得しますリセットからは予想されません。
DELETE + INSERT
をリセットとして使用できるように見えるかもしれませんが、このアプローチにはいくつかの弱点もあります。行が同じキーで再挿入された場合、他のノードからの変更に関して操作ストリームの同じ位置ですべてのノードがそれを見るという保証はありません。
PGDは、コンカレントケースでデータ異常を引き起こす可能性があるため、同じ主キー値の再利用を特にお勧めしません。
状態ベースのCRDTタイプは、次のような特別な!
演算子を使用してリセットを確実に処理できます。
UPDATE tab SET counter = !counter WHERE ...;
「確実に」とは、値にマルチプルの同時リセットと発散という2つの問題がないことを意味します。
- オペレーションベースのCRDTタイプは、
Eager Replicationの効果一般 を使用してのみ確実にリセットできます。これは、マルチプルの同時リセットを回避するためです。
Eager Replicationを使用して、いずれかの種類のCRDTを特定の値に設定することもできます。
実装されたCRDTデータ型#
現在、6つのCRDTデータ型が実装されています。
Grow専用のカウンターと合計
ポジティブ/ネガティブカウンタと合計
デルタカウンターとサム
カウンタと合計は、カウンタタイプが整数ベースbigint
であるのに対し、sumタイプが10進数ベースnumeric
であることを除き、ほとんど同じ動作をします。
[1]で説明されている追加のCRDTタイプは、後で実装される可能性があります。
次のクエリーを使用して、現在実装されているCRDTデータ型をリストできます。
SELECT n.nspname, t.typname
FROM bdr.crdt_handlers c
JOIN (pg_type t JOIN pg_namespace n ON t.typnamespace = n.oid)
ON t.oid = c.crdt_type_id;
成長専用カウンター crdt_gcounter#
非負の値のインクリメントのみをサポート
value + intおよびcounter + bigint演算子。#演算子を使用するか、bigintにキャストすることにより、カウンターの現在値を取得できます。counter = valueのような単純な割り当てとは互換性がありません。これは、新しい値がアプリケーションのどこかで計算される場合の一般的なパターンです。!演算子counter = !counterを使用してカウンターを単純にリセットできます。crdt_gcounter_to_textを使用して内部状態を検査できます。
CREATE TABLE crdt_test (
id INT PRIMARY KEY,
cnt bdr.crdt_gcounter NOT NULL DEFAULT 0
);
INSERT INTO crdt_test VALUES (1, 0); -- initialized to 0
INSERT INTO crdt_test VALUES (2, 129824); -- initialized to 129824
INSERT INTO crdt_test VALUES (3, -4531); -- error: negative value
- - enable CLCD on the table
ALTER TABLE crdt_test REPLICA IDENTITY FULL;
SELECT bdr.alter_table_conflict_detection(crdt_test, column_modify_timestamp, cts);
- - increment counters
UPDATE crdt_test SET cnt = cnt + 1 WHERE id = 1;
UPDATE crdt_test SET cnt = cnt + 120 WHERE id = 2;
- - error: minus operator not defined
UPDATE crdt_test SET cnt = cnt - 1 WHERE id = 1;
- - error: increment has to be non-negative
UPDATE crdt_test SET cnt = cnt + (-1) WHERE id = 1;
- - reset counter
UPDATE crdt_test SET cnt = !cnt WHERE id = 1;
- - get current counter value
SELECT id, cnt::bigint, cnt FROM crdt_test;
- - show internal structure of counters
SELECT id, bdr.crdt_gcounter_to_text(cnt) FROM crdt_test;
Grow-only sum crdt_gsum#
負でない値のインクリメントのみをサポート
sum + numeric。#演算子を使用するか、numericにキャストすることにより、合計の現在値を取得できます。sum = valueのような単純な割り当てとは互換性がありません。これは、新しい値がアプリケーションのどこかで計算される場合の一般的なパターンです。!演算子sum = !sumを使用して合計を単純にリセットできます。crdt_gsum_to_textを使用して内部状態を検査できます。
CREATE TABLE crdt_test (
id INT PRIMARY KEY,
gsum bdr.crdt_gsum NOT NULL DEFAULT 0.0
);
INSERT INTO crdt_test VALUES (1, 0.0); -- initialized to 0
INSERT INTO crdt_test VALUES (2, 1298.24); -- initialized to 1298.24
INSERT INTO crdt_test VALUES (3, -45.31); -- error: negative value
- - enable CLCD on the table
ALTER TABLE crdt_test REPLICA IDENTITY FULL;
SELECT bdr.alter_table_conflict_detection(crdt_test, column_modify_timestamp, cts);
- - increment sum
UPDATE crdt_test SET gsum = gsum + 11.5 WHERE id = 1;
UPDATE crdt_test SET gsum = gsum + 120.33 WHERE id = 2;
- - error: minus operator not defined
UPDATE crdt_test SET gsum = gsum - 15.2 WHERE id = 1;
- - error: increment has to be non-negative
UPDATE crdt_test SET gsum = gsum + (-1.56) WHERE id = 1;
- - reset sum
UPDATE crdt_test SET gsum = !gsum WHERE id = 1;
- - get current sum value
SELECT id, gsum::numeric, gsum FROM crdt_test;
- - show internal structure of sums
SELECT id, bdr.crdt_gsum_to_text(gsum) FROM crdt_test;
ポジティブネガカウンター crdt_pncounter#
正と負の値の両方のインクリメントをサポート
counter + intおよびcounter + bigint演算子を介して。#演算子を使用するか、bigintにキャストすることにより、カウンターの現在値を取得できます。counter = valueのような単純な割り当てとは互換性がありません。これは、新しい値がアプリケーションのどこかで計算される場合の一般的なパターンです。!演算子counter = !counterを使用してカウンターを単純にリセットできます。crdt_pncounter_to_textを使用して内部状態を検査できます。
CREATE TABLE crdt_test (
id INT PRIMARY KEY,
cnt bdr.crdt_pncounter NOT NULL DEFAULT 0
);
INSERT INTO crdt_test VALUES (1, 0); -- initialized to 0
INSERT INTO crdt_test VALUES (2, 129824); -- initialized to 129824
INSERT INTO crdt_test VALUES (3, -4531); -- initialized to -4531
- - enable CLCD on the table
ALTER TABLE crdt_test REPLICA IDENTITY FULL;
SELECT bdr.alter_table_conflict_detection(crdt_test, column_modify_timestamp, cts);
- - increment counters
UPDATE crdt_test SET cnt = cnt + 1 WHERE id = 1;
UPDATE crdt_test SET cnt = cnt + 120 WHERE id = 2;
UPDATE crdt_test SET cnt = cnt + (-244) WHERE id = 3;
- - decrement counters
UPDATE crdt_test SET cnt = cnt - 73 WHERE id = 1;
UPDATE crdt_test SET cnt = cnt - 19283 WHERE id = 2;
UPDATE crdt_test SET cnt = cnt - (-12) WHERE id = 3;
- - get current counter value
SELECT id, cnt::bigint, cnt FROM crdt_test;
- - show internal structure of counters
SELECT id, bdr.crdt_pncounter_to_text(cnt) FROM crdt_test;
- - reset counter
UPDATE crdt_test SET cnt = !cnt WHERE id = 1;
- - get current counter value after the reset
SELECT id, cnt::bigint, cnt FROM crdt_test;
正負の和 crdt_pnsum#
sum + numericを介して正と負の値の両方のインクリメントをサポートします。then
#演算子を使用するか、numericにキャストすることにより、合計の現在値を取得できます。sum = valueのような単純な割り当てとは互換性がありません。これは、新しい値がアプリケーションのどこかで計算される場合の一般的なパターンです。!演算子sum = !sumを使用して合計を単純にリセットできます。crdt_pnsum_to_textを使用して内部状態を検査できます。
CREATE TABLE crdt_test (
id INT PRIMARY KEY,
pnsum bdr.crdt_pnsum NOT NULL DEFAULT 0
);
INSERT INTO crdt_test VALUES (1, 0); -- initialized to 0
INSERT INTO crdt_test VALUES (2, 1298.24); -- initialized to 1298.24
INSERT INTO crdt_test VALUES (3, -45.31); -- initialized to -45.31
- - enable CLCD on the table
ALTER TABLE crdt_test REPLICA IDENTITY FULL;
SELECT bdr.alter_table_conflict_detection(crdt_test, column_modify_timestamp, cts);
- - increment sums
UPDATE crdt_test SET pnsum = pnsum + 1.44 WHERE id = 1;
UPDATE crdt_test SET pnsum = pnsum + 12.20 WHERE id = 2;
UPDATE crdt_test SET pnsum = pnsum + (-24.34) WHERE id = 3;
- - decrement sums
UPDATE crdt_test SET pnsum = pnsum - 7.3 WHERE id = 1;
UPDATE crdt_test SET pnsum = pnsum - 192.83 WHERE id = 2;
UPDATE crdt_test SET pnsum = pnsum - (-12.22) WHERE id = 3;
- - get current sum value
SELECT id, pnsum::numeric, pnsum FROM crdt_test;
- - show internal structure of sum
SELECT id, bdr.crdt_pnsum_to_text(pnsum) FROM crdt_test;
- - reset sum
UPDATE crdt_test SET pnsum = !pnsum WHERE id = 1;
- - get current sum value after the reset
SELECT id, pnsum::numeric, pnsum FROM crdt_test;
デルタカウンター crdt_delta_counter#
bigintドメインとして定義されているため、bigint列とまったく同様に動作します。正と負の値の両方のインクリメントをサポートします。
counter = valueのような単純な割り当てと互換性があります。これは、新しい値がアプリケーションのどこかで計算される場合に一般的です。値を確実にリセットする簡単な方法はありません。
CREATE TABLE crdt_test (
id INT PRIMARY KEY,
cnt bdr.crdt_delta_counter NOT NULL DEFAULT 0
);
INSERT INTO crdt_test VALUES (1, 0); -- initialized to 0
INSERT INTO crdt_test VALUES (2, 129824); -- initialized to 129824
INSERT INTO crdt_test VALUES (3, -4531); -- initialized to -4531
- - enable CLCD on the table
ALTER TABLE crdt_test REPLICA IDENTITY FULL;
SELECT bdr.alter_table_conflict_detection(crdt_test, column_modify_timestamp, cts);
- - increment counters
UPDATE crdt_test SET cnt = cnt + 1 WHERE id = 1;
UPDATE crdt_test SET cnt = cnt + 120 WHERE id = 2;
UPDATE crdt_test SET cnt = cnt + (-244) WHERE id = 3;
- - decrement counters
UPDATE crdt_test SET cnt = cnt - 73 WHERE id = 1;
UPDATE crdt_test SET cnt = cnt - 19283 WHERE id = 2;
UPDATE crdt_test SET cnt = cnt - (-12) WHERE id = 3;
- - get current counter value
SELECT id, cnt FROM crdt_test;
デルタサム crdt_delta_sum#
numericドメインとして定義されるため、numeric列とまったく同様に動作します。正と負の値の両方のインクリメントをサポートします。
sum = valueのような単純な割り当てと互換性があります。これは、新しい値がアプリケーションのどこかで計算される場合に一般的です。値を確実にリセットする簡単な方法はありません。
CREATE TABLE crdt_test (
id INT PRIMARY KEY,
dsum bdr.crdt_delta_sum NOT NULL DEFAULT 0
);
INSERT INTO crdt_test VALUES (1, 0); -- initialized to 0
INSERT INTO crdt_test VALUES (2, 129.824); -- initialized to 129824
INSERT INTO crdt_test VALUES (3, -4.531); -- initialized to -4531
- - enable CLCD on the table
ALTER TABLE crdt_test REPLICA IDENTITY FULL;
SELECT bdr.alter_table_conflict_detection(crdt_test, column_modify_timestamp, cts);
- - increment counters
UPDATE crdt_test SET dsum = dsum + 1.32 WHERE id = 1;
UPDATE crdt_test SET dsum = dsum + 12.01 WHERE id = 2;
UPDATE crdt_test SET dsum = dsum + (-2.4) WHERE id = 3;
- - decrement counters
UPDATE crdt_test SET dsum = dsum - 7.33 WHERE id = 1;
UPDATE crdt_test SET dsum = dsum - 19.83 WHERE id = 2;
UPDATE crdt_test SET dsum = dsum - (-1.2) WHERE id = 3;
- - get current counter value
SELECT id, cnt FROM crdt_test;
[1] https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type