Guide

Distributed systems

OR-sets and add-wins

Sets are where naive merges break. An observed-remove set tags every add with a unique ID, so a remove only deletes what its replica has seen. A concurrent add survives.

155 of 285 · 2 min read

A shopping cart is a set. Items get added and removed on different devices. Merging two sets by union is easy, but it cannot tell a deleted item from one that was never added. The observed-remove set (OR-set) fixes that, so deletes stay deleted.

Concept

Before you start. A tombstone is a marker that records a deleted item, so a late copy of that item is not revived. A grow-only set only supports adds, and merging it is a plain union. An OR-set is a set whose adds carry unique tags.

The big idea

Think of sticky notes. Each add writes a new note with a unique ID and sticks it on the item. A remove tears off only the notes its replica has seen. If another replica adds the same item at the same time, its new note was never seen by the remover, so it stays.

This gives add-wins semantics. A concurrent add beats a remove that did not know about it. An uncontested remove really removes the item.

Walking through it

Both replicas start with milk tagged t1.

Start:        both replicas have {milk#t1}
Replica A:    remove milk, tears off t1        -> A = {}
Replica B:    add milk again, new tag t2       -> B = {milk#t1, milk#t2}
Merge:        t1 was seen and removed by A, t2 was not
Result:       {milk#t2}, so milk is still in the cart

Contrast this with a union merge. The remove on A would be undone by the copy of milk#t1 on B, and the deleted item would come back. This is the cart problem from the Dynamo paper, where deleted items could reappear after a merge.

A two-phase set keeps an add-set and a remove-set. Once something is removed, it can never be added back. An OR-set avoids that by using fresh tags for every add.

Common mistakes

  • Using a union merge for a cart. Deleted items come back after the sync.
  • Using a two-phase set for data people remove and re-add. Once removed, the item is gone for good.
  • Assuming removes always win. In an OR-set, a concurrent add beats a remove. That is usually right, but you should choose it on purpose.

Check yourself

  1. Replica A removes milk while replica B adds milk again at the same time. What is the result? Milk stays, because B's new tag was not seen by A's remove. This is add-wins.
  2. Why can a two-phase set never re-add a removed item? Its remove-set keeps every removed element forever, so a later add is blocked.

Key takeaways

  • A union merge resurrects deleted items. Track removals explicitly.
  • Each OR-set add gets a unique tag, so removes only delete what was seen.
  • A concurrent add survives a remove, which gives add-wins semantics.
  • Libraries and databases such as Riak and Redis Enterprise offer add-wins sets built on this idea.

Further learning

Next, see how collaborative text merges with operational transformation and sequence CRDTs in text editing: OT vs sequence CRDTs.

For the cart example in context, see the distributed key-value store case study.

Conflict resolution and CRDTs

What to do when replicas accept concurrent writes. The options run from last-write-wins and siblings to CRDTs, operational transformation and the sync engines used by collaborative editors.

CRDT counters

A conflict-free replicated data type lets replicas update independently and still converge. A G-counter keeps one slot per replica and merges by taking the maximum, so no increment is lost or counted twice.

Case study: distributed key-value store

Build a Dynamo-style store from first principles. Consistent hashing places the data, quorums set the consistency, vector clocks detect conflicts, and hints and Merkle trees repair failures.