Conflict-free Replicated Data Types¶

Conflict-free replicated data types (CRDT) support merging valuesfrom concurrently modified rows, instead of discarding one of the rows(which is what traditional conflict resolution does).

Each CRDT type is implemented as a separate PostgreSQL data type, withan extra callback added to the bdr.crdt_handlers catalog. The mergeprocess happens inside the BDR writer on the apply side; no additional useraction is required.

CRDTs require the table to have column-level conflict resolution enabledas documented in the CLCD chapter.

The only action taken by the user is the use of a particular data typein CREATE/ALTER TABLE, rather than standard built-in data types such asinteger; e.g. consider the following table with one regular integercounter and a single row:

CREATE TABLE non_crdt_example (
   *   id      integer              PRIMARY KEY,
   *   counter integer              NOT NULL DEFAULT 0
);

INSERT INTO non_crdt_example (id) VALUES (1);

If we issue the following SQL on two nodes at same time:

UPDATE non_crdt_example
   *  SET counter = counter + 1    -- "reflexive" update
 WHERE id = 1;

… the resulting values can be seen using this query, after bothupdates are applied:

SELECT * FROM non_crdt_example WHERE id = 1;
   *  id |   counter
 -----+-----------
   *   1 |         1
(1 row)

…showing that we’ve lost one of the increments, due to the update_if_newerconflict resolver. If you use the CRDT counter data type instead,you should observe something like this:

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);

Again we issue the following SQL on two nodes at same time,then wait for the changes to be applied:

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)

This shows that CRDTs correctly allow accumulator columns to work, evenin the face of asynchronous concurrent updates that otherwise conflict.

The crdt_gcounter type is an example of state-based CRDT types, thatwork only with reflexive UPDATE SQL, such as x = x + 1, as shown above.

The bdr.crdt_raw_value configuration option determines whether queriesreturn the current value or the full internal state of the CRDT type. Bydefault only the current numeric value is returned. When set to true,queries return representation of the full state - the special hash operator(#) may be used to request only the current numeric value without using thespecial operator (this is the default behavior). If the full state isdumped using bdr.crdt_raw_value = on then the value would only be ableto be reloaed with bdr.crdt_raw_value = on.

Note: The bdr.crdt_raw_value applies only formatting of data returnedto clients; i.e. simple column references in the select list. Any columnreferences in other parts of the query (e.g. WHERE clause or evenexpressions in the select list) may still require use of the # operator.

Another class of CRDT data types exists, which we refer to as “delta CRDT”types (and are a special subclass of operation-based CRDTs, as explainedlater).

With delta CRDTs, any update to a value is automatically compared to theprevious value on the same node and then a change is applied as a deltaon all other nodes.

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);

If we issue the following SQL on two nodes at same time:

UPDATE crdt_delta_example
   *  SET counter = 2          -- notice NOT counter = counter + 2
 WHERE id = 1;

The resulting values can be seen using this query, after both updatesare applied:

SELECT id, counter FROM crdt_delta_example WHERE id = 1;
   *  id | counter
 -----+---------
   *   1 |       4
(1 row)

With a regular integer column the result would be 2, of course. Butwhen we UPDATE the row with a delta CRDT counter, we start with the OLDrow version, make a NEW row version and send both to the remote node,where we compare them with the version we find there (let’s call thatthe LOCAL version). Standard CRDTs merge the NEW and the LOCAL version,while delta CRDTs compare the OLD and NEW versions and apply the deltato the LOCAL version.

The CRDT types are installed as part of bdr into the bdr schema.For convenience, the basic operators ( +, # and ! ) and a numberof common aggregate functions (min, max, sum and avg) arecreated in pg_catalog, to make them available without having to tweaksearch_path.

An important question is how query planning and optimization works with thesenew data types. CRDT types are handled transparently - both ANALYZE andthe optimizer work, so estimation and query planning works fine, withouthaving to do anything else.

!!! Note * This feature is currently only available on EDB Postgres Extended and EDB Postgres Advanced.

State-based and operation-based CRDTs¶

Following the notation from [1], we do implement both operation-basedand state-based CRDTs.

Operation-based CRDT Types (CmCRDT)¶

The implementation of operation-based types is quite trivial, becausethe operation is not transferred explicitly but computed from the oldand new row received from the remote node.

Currently, we implement these operation-based CRDTs:

`crdt_delta_counter` - `bigint` counter (increments/decrements)

`crdt_delta_sum` - `numeric` sum (increments/decrements)

These types leverage existing data types (e.g. crdt_delta_counter isa domain on a bigint), with a little bit of code to compute the delta.

This approach is possible only for types where we know how to computethe delta, but the result is very simple and cheap (both in terms ofspace and CPU), and has a couple of additional benefits (e.g. we canleverage operators / syntax for the under-lying data type).

The main disadvantage is that it’s not possible to reset this value reliablyin an asynchronous and concurrent environment.

Note: We could also implement more complicated operation-based types bycreating custom data types, storing the state and the last operation (wedecode and transfer every individual change, so we don’t need multipleoperations). But at that point we lose the main benefits (simplicity,reuse of existing data types) without gaining any advantage compared tostate-based types (still no capability to reset, …), except for thespace requirements (we don’t need a per-node state).

State-based CRDT Types (CvCRDT)¶

State-based types require a more complex internal state, and so can’tuse the regular data types directly the way operation-based types do.

Currently, we implement four state-based CRDTs:

`crdt_gcounter` - `bigint` counter (increment-only)

`crdt_gsum` - `numeric` sum/counter (increment-only)

`crdt_pncounter` - `bigint` counter (increments/decrements)

`crdt_pnsum` - `numeric` sum/counter (increments/decrements)

The internal state typically includes per-node information, increasingthe on-disk size but allowing additional benefits. The need to implementcustom data types implies more code (in/out functions and operators).

The advantage is the ability to reliably reset the values, a somewhatself-healing nature in the presence of lost changes (which should nothappen in properly-operated cluster), and the ability to receive changesfrom other than source nodes.

Consider for example that a value is modified on node A, and the changegets replicated to B, but not C (due to network issue between A and C).If B modifies the value, and this change gets replicated to C, it willinclude even the original change from A. With operation-based CRDTs thenode C would not receive the change until the A-C network connectionstarts working again.

The main disadvantages of CvCRDTs are higher costs, both in terms ofdisk space - we need a bit of information for each node, including nodesthat have been already removed from the cluster). The complex nature ofthe state (serialized into varlena types) means increased CPU usage.

Disk-Space Requirements¶

An important consideration is the overhead associated with CRDT types,particularly the on-disk size.

For operation-based types this is rather trivial, because the typesare merely domains on top of other types, and so have the same diskspace requirements (no matter how many nodes are there).

`crdt_delta_counter` - same as `bigint` (8 bytes)

`crdt_delta_sum` - same as `numeric` (variable, depending on precision

and scale)

There is no dependency on the number of nodes, because operation-basedCRDT types do not store any per-node information.

For state-based types the situation is more complicated. All the typesare variable-length (stored essentially as a bytea column), and consistof a header and a certain amount of per-node information for each nodethat modified the value.

For the bigint variants, formulas computing approximate size are ( Ndenotes the number of nodes that modified this value):

`crdt_gcounter` - `32B (header) + N * 12B (per-node)`

`crdt_pncounter` - `48B (header) + N * 20B (per-node)`

For the numeric variants there is no exact formula, because both theheader and per-node parts include numeric variable-length values. Togive you an idea of how many such values we need to keep:

```
`crdt_gsum`
```
- - fixed: 20B (header) + N * 4B (per-node)
- - variable: (2 + N) numeric values
```
`crdt_pnsum`
```
- - fixed: 20B (header) + N * 4B (per-node)
- - variable: (4 + 2 * N) numeric values
- Note*: It does not matter how many nodes are in the cluster, if the values are never updated on multiple nodes. It also does not matter if the updates were concurrent (causing a conflict) or not.
- Note*: It also does not matter how many of those nodes were already removed from the cluster. There is no way to compact the state yet.

CRDT Types vs Conflicts Handling¶

As tables may contain both CRDT and non-CRDT columns (in fact, mostcolumns are expected to be non-CRDT), we need to do both the regularconflict resolution and CRDT merge.

The conflict resolution happens first, and is responsible for decidingwhich tuple to keep (applytuple) and which one to discard. The mergephase happens next, merging data for CRDT columns from the discardedtuple into the applytuple.

Note*: This makes CRDT types somewhat more expensive compared to plain conflict resolution, because the merge needs to happen every time, even when the conflict resolution can use one of the fast-paths (modified in the current transaction, etc.).

CRDT Types vs. Conflict Reporting¶

By default, detected conflicts are written into the server log. WithoutCRDT types this makes perfect sense, because the conflict resolutionessentially throws away one half of the available information (local orremote row, depending on configuration). This presents a data loss.

CRDT types allow both parts of the information to be combinedwithout throwing anything away, eliminating the data loss issue. This makesthe conflict reporting unnecessary.

For this reason, we skip the conflict reporting when the conflict can befully-resolved by CRDT merge, that is if each column meets at least oneof these two conditions:

the values in local and remote tuple are the same (NULL or equal)
it uses a CRDT data type (and so can be merged)
- Note*: This means we also skip the conflict reporting when there are no CRDT columns, but all values in local/remote tuples are equal.

Resetting CRDT Values¶

Resetting CRDT values is possible but requires special handling.The asynchronous nature of thecluster means that different nodes may see the reset operation (nomatter how it’s implemented) at different places in the change stream.Different nodes may also initiate a reset concurrently; i.e. beforeobserving the reset from the other node.

In other words, to make the reset operation behave correctly, it needs tobe commutative with respect to the regular operations. Many naive waysto reset a value (which may work perfectly well on a single-node) failfor exactly this reason.

For example, the simplest approach to resetting a value might be:

UPDATE crdt_table SET cnt = 0 WHERE id = 1;

With state-based CRDTs this does not work - it throws away the state for theother nodes, but only locally. It will be added back by merge functionson remote nodes, causing diverging values, and eventually receiving itback due to changes on the other nodes.

With operation-based CRDTs, this may seem to work because theupdate is interpreted as a subtraction of -cnt. But it only works in theabsence of concurrent resets. Once two nodes attempt to do a reset atthe same time, we’ll end up applying the delta twice, getting a negativevalue (which is not what we expected from a reset).

It might also seem that DELETE + INSERT can be used as a reset, but thishas a couple of weaknesses too. If the row is reinserted with the samekey, it’s not guaranteed that all nodes will see it at the same position inthe stream of operations (with respect to changes from other nodes).BDR specifically discourages re-using the same Primary Key value sinceit can lead to data anomalies in concurrent cases.

State-based CRDT types can reliably handle resets,using a special ! operator like this:

UPDATE tab SET counter = !counter WHERE ...;

By “reliably” we mean the values do not have the two issues illustratedabove - multiple concurrent resets and divergence.

Operation-based CRDT types can only be reset reliably usingEager Replication, since this avoids multiple concurrent resets.Eager Replication can also be used to set either kind of CRDT to a specificvalue.

Implemented CRDT data types¶

Currently there are six CRDT data types implemented - grow-only counterand sum, positive-negative counter and sum, and delta counter and sum.The counters and sums behave mostly the same, except that the “counter” typesare integer-based (bigint), while the “sum” types are decimal-based(numeric).

Additional CRDT types, described at [1], may be implemented later.

The currently implemented CRDT data types can be listed with thefollowing query:

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;

grow-only counter (`crdt_gcounter`)¶

supports only increments with non-negative values ( `value + int`

and counter + bigint operators)

current value of the counter can be obtained either using `#` operator

or by casting it to bigint

```
is not compatible with simple assignments like `counter = value`
```
- (which is common pattern when the new value is computed somewhere in
- the application)

allows simple reset of the counter, using the `!` operator

( counter = !counter )

internal state can be inspected using `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`)¶

supports only increments with non-negative values ( `sum + numeric` )

current value of the sum can be obtained either by using `#` operator

or by casting it to numeric

```
is not compatible with simple assignments like `sum = value`
```
- (which is the common pattern when the new value is computed somewhere in
- the application)

allows simple reset of the sum, using the `!` operator ( `sum = !sum` )

internal state can be inspected using `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;

positive-negative counter (`crdt_pncounter`)¶

supports increments with both positive and negative values (through

counter + int and counter + bigint operators)

current value of the counter can be obtained either by using `#` operator

or by casting to bigint

```
is not compatible with simple assignments like `counter = value`
```
- (which is the common pattern when the new value is computed somewhere in
- the application)

allows simple reset of the counter, using the `!` operator

( counter = !counter )

internal state can be inspected using `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;

positive-negative sum (`crdt_pnsum`)¶

supports increments with both positive and negative values (through

sum + numeric )

current value of the sum can be obtained either by using `#` operator

or by casting to numeric

```
is not compatible with simple assignments like `sum = value`
```
- (which is the common pattern when the new value is computed somewhere in
- the application)

allows simple reset of the sum, using the `!` operator ( `sum = !sum` )

internal state can be inspected using `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;

delta counter (`crdt_delta_counter`)¶

is defined a `bigint` domain, so works exactly like a `bigint` column

supports increments with both positive and negative values

```
is compatible with simple assignments like `counter = value`
```
- (common when the new value is computed somewhere in the application)

no simple way to reset the value (reliably)

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;

delta sum (`crdt_delta_sum`)¶

is defined as a `numeric` domain, so works exactly like a `numeric` column

supports increments with both positive and negative values

```
is compatible with simple assignments like `sum = value`
```
- (common when the new value is computed somewhere in the application)

no simple way to reset the value (reliably)

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

Conflict-free Replicated Data Types¶

State-based and operation-based CRDTs¶

Operation-based CRDT Types (CmCRDT)¶

State-based CRDT Types (CvCRDT)¶

Disk-Space Requirements¶

CRDT Types vs Conflicts Handling¶

CRDT Types vs. Conflict Reporting¶

Resetting CRDT Values¶

Implemented CRDT data types¶

grow-only counter (`crdt_gcounter`)¶

grow-only sum (`crdt_gsum`)¶

positive-negative counter (`crdt_pncounter`)¶

positive-negative sum (`crdt_pnsum`)¶

delta counter (`crdt_delta_counter`)¶

delta sum (`crdt_delta_sum`)¶

Previous topic

Next topic

Table of Contents

Conflict-free Replicated Data Types¶

State-based and operation-based CRDTs¶

Operation-based CRDT Types (CmCRDT)¶

State-based CRDT Types (CvCRDT)¶

Disk-Space Requirements¶

CRDT Types vs Conflicts Handling¶

CRDT Types vs. Conflict Reporting¶

Resetting CRDT Values¶

Implemented CRDT data types¶

grow-only counter (crdt_gcounter)¶

grow-only sum (crdt_gsum)¶

positive-negative counter (crdt_pncounter)¶

positive-negative sum (crdt_pnsum)¶

delta counter (crdt_delta_counter)¶

delta sum (crdt_delta_sum)¶

grow-only counter (`crdt_gcounter`)¶

grow-only sum (`crdt_gsum`)¶

positive-negative counter (`crdt_pncounter`)¶

positive-negative sum (`crdt_pnsum`)¶

delta counter (`crdt_delta_counter`)¶

delta sum (`crdt_delta_sum`)¶