Logo

Demo of Conflict-free Replicated Data Views

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.

More Information
Paper Code Website
Site 1 Site 2
Site 1
idb://pg-site-1:

[Ctrl/⌘ + Enter] to run

Site 2
idb://pg-site-2:

[Ctrl/⌘ + Enter] to run


Example Usage

Both sites writing to different keys in map m:

Site 1 SELECT mapAdd('m', 'k1', 'v1')
Site 2 SELECT mapAdd('m', 'k2', 'v2')

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:

Site 1 SELECT * FROM mapAwMvr
id data
m (k1,{v1})
Site 2 SELECT * FROM mapAwMvr
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:

Site 1 SELECT * FROM mapAwMvr
id data
m (k1,{v1})
m (k2,{v2})
Site 2 SELECT * FROM mapAwMvr
id data
m (k1,{v1})
m (k2,{v2})

Both sites writing to the same key in map m:

Site 1 SELECT mapAdd('m', 'k3', 'v3')
Site 2 SELECT mapAdd('m', 'k3', 'v30')

After , the Add-Wins + Multi-Value Register view returns the conflicting values for k3:

Site 1 SELECT * FROM mapAwMvr
id data
m (k3,"{v3,v30}")
Site 2 SELECT * FROM mapAwMvr
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:

Site 1 SELECT * FROM mapAwLww
id data
m (k3,v30)
Site 2 SELECT * FROM mapAwLww
id data
m (k3,v30)

Query Present to get the underlying rows:

Site 1 SELECT id, key, type, data, site, lts, op FROM Data
id key type data site lts op
m k3 m v3 1 {1,0} a
m k3 m v30 2 {0,1} a

Nested Structures and Referential Integrity

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:

Site 1 SELECT setAdd('s1', 'a'); SELECT setAdd('s1', 'b'); SELECT setAdd('s2', 'c'); SELECT setAdd('s2', 'd'); SELECT mapAdd('m1', 'k1', 's1'); SELECT mapAdd('m1', 'k2', 's2');

To read the data, we just need to join using the map values:

Site 1 SELECT t0.id AS m, (t0.data).key AS k, t1.id AS s, t1.data AS data FROM MapAwLww t0 JOIN SetAw t1 ON t1.id = (t0.data).value WHERE t0.id = 'm1'
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:

Site 1 SELECT id0 id, jsonb_object_agg(key0, data) AS data FROM ( SELECT id0, key0, id1, jsonb_agg(data) AS data FROM ( SELECT t0.id AS id0, (t0.data).key AS key0, t1.id AS id1, t1.data AS data FROM MapAwLww t0 JOIN SetAw t1 ON t1.id = (t0.data).value ) t GROUP BY 1, 2, 3 ) t WHERE id0 = 'm1' GROUP BY 1
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):

Site 1 SELECT setAdd('s1','X')
Site 2 SELECT mapRmv('m1','k1')

After , even though we have a conflict from a concurrent add and remove, querying the nested structure will always exclude k1:

Site 1 SELECT t0.id AS m, (t0.data).key AS k, t1.id AS s, t1.data AS data FROM MapAwLww t0 JOIN SetAw t1 ON t1.id = (t0.data).value WHERE t0.id = 'm1'
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:

Site 1 SELECT mapAdd('m1', 'k1', 's1')

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

Site 1 SELECT add_referential_integrity('{m1, k1}','s1','mapAdd')
Site 2 SELECT add_referential_integrity('{m1, k1}','s1','mapAdd')

Now, we can execute the concurrent add and remove again. Inspecting History of Site 1 reveals the two yet-to-be-replicated rows:

Site 1
SELECT setAdd('s1', 'X')
SELECT id, key, data, op FROM Shared
id key data op
s1 X NULL a
m1 k1 s1 a
Site 2 SELECT mapRmv('m1','k1')

After , the add-wins view MapAwLww returns the updated set, while the remove-wins MapRwLww does not:

Site 1
SELECT t0.id AS m, (t0.data).key AS k, t1.id AS s, t1.data AS data FROM MapAwLww t0 JOIN SetAw t1 ON t1.id = (t0.data).value WHERE t0.id = 'm1'
m k s data
m1 k1 s1 a
m1 k1 s1 b
m1 k1 s1 X
m1 k2 s2 c
m1 k2 s2 d
SELECT t0.id AS m, (t0.data).key AS k, t1.id AS s, t1.data AS data FROM MapRwLww t0 JOIN SetAw t1 ON t1.id = (t0.data).value WHERE t0.id = 'm1'
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')).


Available Views and Functions

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

  • MapAwMvr
  • MapAwLww
  • MapRwLww
  • MapRwMvr
  • MapLww

Functions

  • map[AwMvr|AwLww|RwMvr|Lww]Get(id)
  • map[AwMvr|AwLww|RwMvr|Lww]Value(id, key)
  • map[AwMvr|AwLww|RwMvr|Lww]Contains(id, key)
  • mapAdd(id, key, value)
  • mapRmv(id, key)
  • mapClear(id)

Set

Unordered collection of unique values

Views

  • SetAw
  • SetRw
  • SetLww

Functions

  • set[Aw|Rw|Lww]Get(id)
  • set[Aw|Rw|Lww]Contains(id, elem)
  • setAdd(id, elem)
  • setRmv(id, elem)
  • setClear(id)

Register

Single opaque value

Views

  • RegisterMvr
  • RegisterLww

Functions

  • register[Mvr|Lww]Get(id)
  • registerSet(id, value)

List

Ordered collection of values

Views

  • List

Functions

  • listGet(id)
  • listGetAt(id, index)
  • listGetFirst(id)
  • listGetLast(id)
  • listAdd(id, i, elem)
  • listAppend(id, elem)
  • listPrepend(id, elem)
  • listRmv(id, i)
  • listPopFirst(id)
  • listPopLast(id)
  • listClear(id)

Counter

Numeric value that can be incremented or decremented

Views

  • Counter

Functions

  • counterGet(id)
  • counterInc(id, delta)
  • counterDec(id, delta)