Conflict-free Replicated Data Views (CRDV) brings convergent replicated data to relational database systems using native features such as views and rules/triggers. This allows replicas to commit writes independently and later merge them with guarantees that they end up with the same state, using user-defined resolution rules in SQL.
This demo contains a small deployment with two sites, implemented with PGlite, a WebAssembly port of PostgreSQL. Read and write queries can be executed in each site by using the respective terminals, while the sync and merge are done manually by pressing the "Replicate and Merge" button. Each site already comes with views and functions to operate over common CRDTs, using generic data tables.
[Ctrl/⌘ + Enter] to run
[Ctrl/⌘ + Enter] to run
Both sites writing to different keys in map m:
Note: Press ▶︎ to run the code snippets directly in the respective sites.
When reading the map using, e.g., the Add-Wins + Multi-Value Register view, each site returns different values:
| id | data |
|---|---|
| m | (k1,{v1}) |
| id | data |
|---|---|
| m | (k2,{v2}) |
After the button is pressed, both sites will return the same data. In this case, the map contains two keys:
| id | data |
|---|---|
| m | (k1,{v1}) |
| m | (k2,{v2}) |
| id | data |
|---|---|
| m | (k1,{v1}) |
| m | (k2,{v2}) |
Both sites writing to the same key in map m:
After
, the Add-Wins + Multi-Value Register view returns the
conflicting values for k3:
| id | data |
|---|---|
| m | (k3,"{v3,v30}") |
| id | data |
|---|---|
| m | (k3,"{v3,v30}") |
To get just the last write based on physical time, we can use the Add-Wins + Last-Writer-Wins view. In this case, Site 2 made the last write:
| id | data |
|---|---|
| m | (k3,v30) |
| id | data |
|---|---|
| m | (k3,v30) |
Query Present to get the underlying rows:
| id | key | type | data | site | lts | op |
|---|---|---|---|---|---|---|
| m | k3 | m | v3 | 1 | {1,0} | a |
| m | k3 | m | v30 | 2 | {0,1} | a |
To model nested structures, we can store a pointer to the inner structure in the outer
structure. In the generic tables that we use in this demo, we can store it directly in
the data column. For example, the following code can be used to create a
map of sets:
To read the data, we just need to join using the map values:
| m | k | s | data |
|---|---|---|---|
| m1 | k1 | s1 | a |
| m1 | k1 | s1 | b |
| m1 | k2 | s2 | c |
| m1 | k2 | s2 | d |
Alternatively, we can use a query that outputs the result to JSON:
| id | data |
|---|---|
| m1 | {"k1":["a","b"],"k2":["c","d"]} |
In the map of sets nested structure of the previous example, consider adding an element
to set s1 in one site while concurrently deleting key k1 from
the map (ensure
is done first):
After , even though we have a conflict from a concurrent add and remove,
querying the nested structure will always exclude k1:
| m | k | s | data |
|---|---|---|---|
| m1 | k2 | s2 | c |
| m1 | k2 | s2 | d |
The problem is that the writes are done on different structures, even if they are
logically connected. To avoid this, we can force an add of k1 every time
there is an addition to s1, in the same transaction. The built-in
add_referential_integrity function creates a trigger that automatically
does this. First, let's add k1 back to the map:
Then, after
,
we will make adds to s1 trigger a write of k1 on
m1 (in this demo, it needs to be created in both sites):
Now, we can execute the concurrent add and remove again. Inspecting History
of Site 1 reveals the two yet-to-be-replicated rows:
| id | key | data | op |
|---|---|---|---|
| s1 | X | NULL | a |
| m1 | k1 | s1 | a |
After
, the add-wins view MapAwLww returns the updated set, while the
remove-wins MapRwLww does not:
| m | k | s | data |
|---|---|---|---|
| m1 | k1 | s1 | a |
| m1 | k1 | s1 | b |
| m1 | k1 | s1 | X |
| m1 | k2 | s2 | c |
| m1 | k2 | s2 | d |
| m | k | s | data |
|---|---|---|---|
| m1 | k2 | s2 | c |
| m1 | k2 | s2 | d |
Likewise, we can have a similar approach for removes, e.g., mark the elements in the set
as removed when we delete the key from the map.
Finally, to remove the referential integrity trigger, we can use the
rmv_referential_integrity function (e.g.,
rmv_referential_integrity('{m1, k1}', 's1')).
Documentation for these views and functions can be found at github/crdv#reading and github/crdv#utility-functions, respectively.
Map
Associates unique keys with values
Views
Functions
Set
Unordered collection of unique values
Views
Functions
Register
Single opaque value
Views
Functions
List
Ordered collection of values
Views
Functions
Counter
Numeric value that can be incremented or decremented
Views
Functions