Conflict-free Replicated Data Views

Overview

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 to better accommodate the target applications.

Unlike alternatives that encode Conflict-free Replicated Data Types (CRDTs) as blobs in a field and use custom code to read and write, CRDV enables a tight integration with the query language and optimizer, and makes it possible to use native secondary indexes.

Unlike alternatives that model tables as last-writer-wins maps, CRDV supports a wide range of types and resolution rules.

Architecture

CRDV is comprised of three layers:

History - stores local and remote writes, using a replicated table.
Present - filters the obsolete rows from the History layer, using a view with optional materialization.
Value - handles concurrent versions in the Present layer, using conflict-resolution rules defined with SQL views.

Schema

Consider a generic application schema k and v. In addition to these columns, the Present and History layer contain the following metadata:

op - whether the row was marked as added or removed.
site - the node where the row was created.
lts - logical timestamp, to track causality.
pts - physical timestamp, for last-writer-wins semantics.

Meanwhile, the Value layer contains only the data.

Writing

Inserts/Updates/Deletes sent to the Value layer are redirected using rules/triggers as Inserts to the History layer, with the new data and additional metadata. They are then stored and replicated to the remaining sites.

Writes can take advantage of the local transactional guarantees in order to modify multiple rows atomically, which are also atomically replicated on commit.

Here is an example of a rule that translates Updates (PostgreSQL syntax):

CREATE RULE update_rule AS
  ON UPDATE TO Value DO INSTEAD
  INSERT INTO History
  SELECT k, v, 'add', siteId(), t.lts, t.pts
  FROM nextTimestamp() AS t;

Filtering

The Present layer is responsible for removing rows that have been causally replaced, meaning they will not be included in the final result. This makes Value easier to implement, as it only has to focus on the concurrent present versions.

The following figure shows rows being filtered from History to Present. In this case, we have two different items, k1 and k2. Version [1, 1] in k1 is obsolete ([1, 1] < [2, 1] and [1, 1] < [1, 2]), while versions [2, 1] and [1, 2] are concurrent. As for item k2, version [2, 3] is obsolete ([2, 3] < [3, 3]).

**Figure 2:** Example showing how rows are filtered from History to Present.

Present can be implemented using three strategies, which can be changed based on the workload:

no-mat - Present is defined as a view over History that filters the rows at runtime. Trades off read performance for write performance. (Not used in practice, see the async strategy.)
sync - Present is defined as a table that is eagerly materialized on writes to History, using a trigger that runs in the same transaction. It also removes the obsolete rows from Present. Trades off write performance for read performance.
async - Present is defined as a view that combines recent History rows with a materialized snapshot. Periodically, History data gets merged into the snapshot. Like the no-mat strategy, it trades off read performance for write performance, but the periodic materialization helps keep read costs relatively lower.

Reading

Finally, the Value layer will merge concurrent Present rows based on resolution rules defined in SQL views, in order to support reads.

The following image shows an example of data in the Present layer, comprised of four different items:

k1 - one version, marked as added.
k2 - one version, marked as removed.
k3 - two versions, one marked as added and the other as removed.
k4 - two versions, both marked as added.

Example data in the Present layer — **Figure 3:** Example of rows in the Present layer.

Let's say we want to use the add-wins rule, which favors added rows over removed ones. This can be defined with the following SQL view:

CREATE VIEW ValueAw AS
  SELECT k, v
  FROM Present
  WHERE op = 'add';

Add-wins result set — **Figure 4:** Add-wins view.

In the example above, a concurrent add and remove conflict is solved by discarding the remove. However, we still need to deal with concurrent added rows. We can simply return all values, as done by the view above, or aggregate them into an array, i.e., multi-value register approach:

CREATE VIEW ValueAwMvr AS
  SELECT k, array_agg(v ORDER BY v) v
  FROM ValueAw
  GROUP BY k;

Add-wins + multi-value register result set — **Figure 5:** Add-wins + multi-value register view.

Notice how ValueAwMvr is built on top of the ValueAw view. Another option would be to return the average of the conflicting values instead, as shown in the example below.

CREATE VIEW ValueAwAvg AS
  SELECT k, avg(v)
  FROM ValueAw
  GROUP BY k;

Add-wins + average result set — **Figure 6:** Add-wins + average view.

Finally, as a last example, the following view applies the last-writer-wins rule, using a ranking window function to order the versions by physical timestamp for each item:

CREATE VIEW ValueLww AS
  SELECT k, v
  FROM (
    SELECT k, v, op, rank() OVER (
        PARTITION BY k
        ORDER BY pts DESC, site
      ) AS rank
    FROM Present
  )
  WHERE rank = 1 AND op = 'add';

Last-writer-wins result set — **Figure 7:** Last-writer-wins view.

Reproducing CRDTs & Nested Structures

Common CRDTs can be implemented with CRDV. Examples include:

registers - using single-row tables (however, they will usually be found inside maps).
maps - table with two columns, a key and value, like the examples previously shown.
sets - similar to maps, but without the value column.
lists - also uses two columns, with the key being used to order the values in the list. The LSEQ algorithm can be used to generate such keys.
counters - also use a key and a value. The key represents the origin site, while the value represents the partial sum. Each site can increment or decrement its respective row, while the local concurrency control ensures that there are no local concurrent versions. To read the final value, we just need to perform a sum.

We can also use foreign keys to represent nested structures, similarly to how we can add CRDTs inside CRDTs. To materialize the result, we just need to join the respective Value views. For example, consider a table that stores shopping carts. For every product in each cart, there is a foreign key to the quantity, modeled in a separate table as a counter. CartAw is a view that builds the shopping carts using the add-wins rule, while Quantity is a view that builds the counters. The final shopping carts can then be queried as such:

SELECT c.id, c.product_id, q.amount
FROM CartAw c
JOIN Quantity q ON q.id = c.quantity_id;

Alternatively, we can return the result set as JSON:

SELECT c.id, jsonb_object_agg(c.product_id, q.amount)
FROM CartAw c
JOIN Quantity q ON q.id = c.quantity_id
GROUP BY c.id;

One problem with this approach is that if we remove a product p from a cart while concurrently incrementing its quantity, the add-wins view will not select p, since it does not know of the add done on the quantity table. To ensure referential integrity, we can create a trigger that marks a product as added in the cart table when there is an update on the respective counter, "entangling" both structures.

Proof of Concept

We implemented a proof of concept of CRDV in PostgreSQL, using rules/triggers, views, procedures, and the built-in asynchronous logical replication.

The repository contains the code and instructions to test it.

Citation

Text

Nuno Faria and José Pereira. 2025. CRDV: Conflict-free Replicated Data Views. Proc. ACM Manag. Data 3, 1, Article 25 (February 2025), 27 pages. https://doi.org/10.1145/3709675

BibTeX

@article{crdv,
  author     = {Faria, Nuno and Pereira, José},
  title      = {CRDV: Conflict-free Replicated Data Views},
  year       = {2025},
  issue_date = {February 2025},
  publisher  = {Association for Computing Machinery},
  address    = {New York, NY, USA},
  volume     = {3},
  number     = {1},
  url        = {https://doi.org/10.1145/3709675},
  doi        = {10.1145/3709675},
  abstract   = {There are now multiple proposals for Conflict-free Replicated Data Types (CRDTs) in SQL databases aimed at distributed systems. Some, such as ElectricSQL, provide only relational tables as convergent replicated maps, but this omits semantics that would be useful for merging updates. Others, such as Pg_crdt, provide access to a rich library of encapsulated column types. However, this puts merge and query processing outside the scope of the query optimizer and restricts the ability of an administrator to influence access paths with materialization and indexes.Our proposal, CRDV, overcomes this challenge by using two layers implemented as SQL views: The first provides a replicated relational table from an update history, while the second implements varied and rich types on top of the replicated table. This allows the definition of merge semantics, or even entire new data types, in SQL itself, and enables global optimization of user queries together with merge operations. Therefore, it naturally extends the scope of query optimization and local transactions to operations on replicated data, can be used to reproduce the functionality of common CRDTs with simple SQL idioms, and results in better performance than alternatives.},
  journal    = {Proc. ACM Manag. Data},
  month      = feb,
  articleno  = {25},
  numpages   = {27},
  keywords   = {crdts, distributed databases, geo-replication, local-first software}
}