Conflict-free replicated data types¶
競合のないレプリケートデータ型(CRDT)は、従来の解決のように行の1つを破棄するのではなく、同時に変更される行の値のマージをサポートします。
各CRDT型は、 bdr.crdt_handlers
カタログに追加された追加のコールバックを備えた個別のPostgreSQLデータ型として実装されます。マージプロセスは、ユーザーの操作を必要とせずに、適用側のBDRライタ内で発生します。
CLCD に記載されているように、CRDTでは、テーブルで列レベルの競合解決を有効にする必要があります。
必要なアクションは、CREATE/ALTER TABLEで整数などの標準の組み込みデータ型ではなく、特定のデータ型を使用することです。たとえば、1つの通常の整数カウンターと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 句や選択リスト内の式など)での列参照は、引き続き # 演算子を使用する必要があります。
CRDTデータ型の別のクラスは、デルタ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バージョンを比較し、デルタをLOCALバージョンに適用します。
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—numeric合計/カウンター(インクリメントのみ)crdt_pncounter—bigintカウンター(インクリメント/デクリメント)crdt_pnsum—numericsum/counter(インクリメント/デクリメント)
通常、内部状態にはノードごとの情報が含まれるため、オンディスクサイズは増加しますが、追加の利点があります。カスタムデータ型を実装する必要性は、より多くのコード(イン/アウト関数と演算子)を意味します。
利点は、値を確実にリセットできること、変更が失われた場合の自己修復性(適切に動作するクラスターでは発生しません)、およびソースノード以外から変更を受信できることです。
たとえば、ノードAで値が変更され、AとC間のネットワーク問題が原因でCではなくBに変更がレプリケートされるとします。 Bが値を変更し、この変更がCにレプリケートされる場合、 Aからの元の変更。操作ベースのCRDTでは、ノードCはA-Cネットワーク接続が再び機能し始めるまで変更を受け取りません。
CvCRDTの主な欠点は、ディスク領域とCPU使用率のコストが高いことです。クラスターから既に削除されたノードを含む、各ノードに関する少しの情報が必要です。状態の複雑な性質(varlenaタイプにシリアル化)は、CPU使用率の増加を意味します。
ディスク領域の要件¶
重要な考慮事項は、CRDTタイプ、特にディスク上のサイズに関連するオーバーヘッドです。
操作ベースのタイプの場合、これは簡単です。タイプは他のタイプの上の単なるドメインであり、ノードの数に関係なく同じディスク領域要件があるためです。
crdt_delta_counter—bigintと同じ(8バイト)crdt_delta_sum—numericと同じ(精度と位取りに応じて可変)
操作ベースのCRDTタイプはノードごとの情報を保存しないため、ノード数に依存しません。
状態ベースの型の場合、状況はより複雑です。すべての型は可変長(基本的にbytea
列として保存)であり、ヘッダーと、値を変更した各ノードの一定量のノードごとの情報で構成されます。
bigint
バリアントの場合、おおよそのサイズを計算する式は次のとおりです(N
は、この値を変更したノードの数を示します)。
crdt_gcounter—32B (header) + N * 12B (per-node)crdt_pncounter-—48B (header) + N * 20B (per-node)
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列のデータがapplytupleにマージされます。
注釈
この処理により、マージは毎回発生する必要があるため、単純な競合解決と比較して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
をリセットとして使用できるように見えるかもしれませんが、このアプローチにはいくつかの弱点もあります。行が同じキーで再挿入された場合、他のノードからの変更に関して、すべてのノードが操作のストリーム内の同じ位置でそれを見ることは保証されません。
BDRは、同時発生のデータ異常につながる可能性があるため、同じ主キー値の再利用を特にお勧めしません。
状態ベースのCRDT型は、次のような特別な!
演算子を使用してリセットを確実に処理できます。
UPDATE tab SET counter = !counter WHERE ...;
「信頼できる」とは、値に複数の同時リセットと発散の2つの問題がないことを意味します。
操作ベースのCRDTタイプは、 Eager Replication を使用してのみ確実にリセットできます。これにより、複数の同時リセットが回避されます。 Eager Replicationを使用して、いずれかの種類のCRDTを特定の値に設定することもできます。
実装されたCRDTデータ型¶
現在、6つのCRDTデータ型が実装されています。
成長専用のカウンターと合計
正負のカウンターと合計
デルタカウンターと合計
カウンターと合計の動作はほとんど同じですが、カウンターの型は整数ベース(bigint
)であり、合計の型は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;
成長のみの合計(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