Distributed systems
Part 3 of 6 · CRDTsSets & Maps — G-Set, 2P-Set, OR-Set, OR-Map
G-Set only adds. 2P-Set removes forever. An observed-remove set tags each add with a dot so a later add can win. An OR-Map nests a CRDT under each key.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
Why can a 2P-Set not re-add an element?
Answer
The remove-set is a G-Set. Once the element is in it, lookup excludes it forever. There is no per-add identity to resurrect.
L2
What does observed-remove mean?
Answer
A remove deletes only the add-dots this replica has already seen. A concurrent add minted a new dot. That dot is not in the remover's tombstone set, so the element stays after the merge.
L3
What goes wrong if remove only deletes local dots and merge unions them?
Answer
The other replica still holds the old dots. Union puts them back. The remove never travels. Tombstones have to travel with the merge.
L4
When can you drop an observed-remove tombstone?
Answer
When the removed dot is causally stable: every replica that is still a member of the cluster has observed it. That needs membership and acknowledgements, not a timer alone.
L5
Which set is a shopping cart line?
Answer
An OR-Set of SKUs, or an OR-Map from SKU to a PN-Counter quantity. Checkout still checks a linearizable inventory. The cart is not the stock count.
L6
How is an OR-Map different from a JSON object?
Answer
Each key's membership is observed-remove, and each value is a nested CRDT. A nested last-writer-wins register still drops concurrent edits of that field. The map does not upgrade a bad value type.
L7
How is this different from a Redis SET on one primary?
Answer
A single-primary set is a linearizable key on that primary. An Active-Active set is a CRDT with its own add and remove rule. Cache-aside does not merge membership at all.
Failure modes
2P-Set used as a toggle
The user removes a tag and adds it again. The remove-set still contains it. The UI says the add succeeded on one device and the merge deletes it.
Remove that does not travel
Merge unions live dots and forgets that another replica deleted them. The element resurrects from any replica that still has the old dot.
Unbounded dots and tombstones
Every add mints a dot and every remove keeps it until causal stability. Churn without a stability oracle fills memory and sync payloads.
Client clocks that rewind
A client actor reuses a counter and mints a dot that is already a tombstone, or collides with a dot still in use. Server-assigned dots, or a protected actor id, close that hole.
Misconceptions
Add-wins means the element is back even if everyone removed the same dot.
Add-wins is about a new dot the remover had not seen. Once every replica has tombstoned a dot, that dot stays out.
A map of last-writer-wins fields is an OR-Map.
The key membership can be observed-remove while each field still drops concurrent edits. The value type is the policy.
Garbage collection is deleting old rows on a timer.
A tombstone dropped before a lagging replica syncs lets that replica's stale add resurrect the element.
Interviewer traps
Use a 2P-Set for the cart because removes are simpler.
Say the user will add the SKU again. That is an OR-Set or an OR-Map. Permanence is a product decision, not a storage shortcut.
The set CRDT is the inventory count.
The cart converges. The last unit is a linearizable decrement or a reservation. Point at the production page and stop.
Design scenario
Same prompt for every reader.
Requirements
Cart lines and photo tags can return after a remove. The denylist cannot. Checkout must not treat the cart as proof of stock.
Traffic / scale
Cart edits are interactive. The denylist changes a few times a day. Tag edits are bursty and small.
Latency
A cart edit is local. Sync can lag while a device is offline.
Consistency
Strong eventual consistency for cart and tags. The denylist must not resurrect. Stock is linearizable at checkout.
Availability
An offline device can edit the cart. It cannot complete checkout until it reaches the inventory store.
Failure assumptions
- One device removes milk after seeing it, while the other adds milk again.
- A replica is offline across the remove and would otherwise resurrect the SKU.
- Tombstones are still required for the life of that offline replica.
Constraints
- Do not use one set type for the cart and the denylist.
- Do not decrement warehouse stock inside the cart CRDT.
Prompt
Shoppers add and remove SKUs from a cart on two devices, including offline. Tags on a photo can be removed and added again. A fraud denylist must never let a removed account back in.
API
Which calls are add and remove on the cart, and which call is the checkout reservation?
Data
Where are the dots, where is the remove-set, and where is the nested quantity?
Architecture
What has to be true before a tombstone can be dropped?
Remove, then add the same element
Prefer
Observed-remove when toggle is the product
Each add mints a dot. Remove tombstones dots this replica has seen. A concurrent add carries a new dot the remover never tombstoned.
- Cart lines and tags come back after a remove.
- A remove still sticks when there is no concurrent add, because the tombstone travels.
- Metadata grows until those dots are causally stable.
Alternative
2P-Set when remove is forever
The remove-set is grow-only. Re-adding the element does not take it out of the remove-set.
- A denylist wants this. A cart does not.
- The implementation is two G-Sets and a subtraction.
- Calling it simpler does not change the product rule.
Pick the set from the remove rule
The boolean you wish you had is not a join. The policy is.
- 1
Ask whether anything is ever removed
If membership only grows, a G-Set and a union are the whole type. Seen-user-ids and append-only facts live here. - 2
Ask whether a removed element may return
If it must not, a 2P-Set records the remove forever. Say that to the product owner before you ship it. - 3
Mint a dot for every add
A dot is an actor id plus a counter. Remove tombstones only the dots already observed. Merge unions dots and tombstones, then subtracts. - 4
Nest a real CRDT under a key
An OR-Map's key is observed-remove membership. The value is a counter, a register, a set, or another map. A nested last-writer-wins field still drops edits.
Which set
Decisions
- 1
1 Need a replicated set
- next2 Removes allowed?
- ?
2 Removes allowed?
- never3 G-Set, union only
- yes4 Re-add after remove?
- 3
3 G-Set, union only
- ?
4 Re-add after remove?
- no5 2P-Set, remove wins
- yes6 OR-Set, add wins
- 5
5 2P-Set, remove wins
- 6
6 OR-Set, add wins
Lesson map
Sets & Maps — G-Set, 2P-Set, OR-Set, OR-Map
G-Set only adds. 2P-Set removes forever. An observed-remove set tags each add with a dot so a later add can win. An OR-Map nests a CRDT under each key.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1 Need a replicated set"] b["2 Removes allowed?"] c["3 G-Set, union only"] d["4 Re-add after remove?"] a -->|1 Need a replicated set| b b -->|never| c b -->|yes| d
Add-wins on the last branch means a new dot, not "an add always beats every remove in history." If you also need a value per key, the OR-Set of keys becomes an OR-Map. A last-writer-wins element set is the other re-add option: each element stores an add timestamp and a remove timestamp, and the greater one wins. It has the same clock hazards as a last-writer-wins register. Prefer observed-remove when "I removed what I had seen" matches the product better than "whoever has the later clock."
G-Set
The state is a set. Add inserts locally. Merge is union. There is no remove. That is the right type for "we have ever observed this id," and the wrong type for anything a user can undo.
2P-Set
A is the add G-Set. R is the remove G-Set. Lookup is "in A and not in R." Remove inserts into R. In the usual formulation the element is removed only if it was already in A. Once it is in R, a later add still leaves it in R, so lookup stays false.
The type is easy to implement and hostile to tags, carts, and favorites. People reach for it because two sets feel simpler than dots. The product then files a bug titled "I added it back and it disappeared." That is the datatype, working.
Observed-remove set
Each add allocates a dot (actor, counter). The element is present while it has at least one live dot. Remove takes the dots this replica currently has for that element and moves them to a tombstone set. Merge unions the live dots, unions the tombstones, and drops any live dot that appears in the tombstones. Clocks merge with max so the next add does not reuse a counter.
Concurrent add and remove: the adder's new dot was not in the remover's observed set, so it is not in the tombstone set. The element remains. That is add-wins. A remove with no concurrent add tombstones the only dots, the tombstones travel, and the element stays out. Both outcomes are the same function.
Flow
- 1
1 Add mints a new dot
- next2 Remove tombs seen dots
- 2
2 Remove tombs seen dots
- next3 Merge unions, then subtract
- 3
3 Merge unions, then subtract
- next4 Unseen dot still wins
- 4
4 Unseen dot still wins
A teaching shortcut unions live dots and does not ship tombstones. It fails the second outcome. Any replica that still holds the old dot unions it back, so a remove does not survive contact with a replica that missed the remove. Production observed-remove sets keep the tombstones. Bieniusa and colleagues' optimized OR-Set is that design, plus a version vector so a late message cannot resurrect a dot the cluster has already deleted. The sandbox below includes the tombstones. Without them the merge is not the type this page describes.
Causal stability is the garbage-collection rule. A tombstoned dot may be forgotten only when every replica still in the cluster has seen it. A timer is not that proof. An offline client that returns after you dropped the tombstone can reintroduce the old dot. Open membership makes the proof harder. Epochs, snapshots, and a server that defines the member set are the usual escapes. The dissemination page is the stability machinery.
OR-Map
Keys use the observed-remove rule. The value under a key is a nested CRDT: a counter, a register, a set, or another map. Removing a key tombstones the observed context of that nested value so a lagging update does not resurrect the key with a stale child. Riak's maps are this idea as a JSON-shaped document that merges field by field.
Composition does not save a bad field type. A nested last-writer-wins register still drops one of two concurrent edits of that field. If the field is a collaborative string, it is not a register. If the field is a quantity, it is a PN-Counter from the previous page, and checkout still validates it against a linearizable stock count.
Which membership
| Type | Re-add after remove | Concurrent add and remove | Metadata |
|---|---|---|---|
| G-Set | No remove | Both adds remain | The elements themselves |
| 2P-Set | Impossible | The remove-set wins forever | Tombstones that never shrink |
| OR-Set | Yes, with a new dot | Add-wins for an unseen dot | Dots plus tombstones |
| LWW-element set | Yes, if the add clock wins | The timestamp wins | A clock, and skew |
| OR-Map | Yes, per key | The value type's own rule | Nested state on top of the key dots |
Sandbox
The Python snippet is the policy choice: union, remove-forever, and observed-remove with tombstones that travel. The TypeScript snippet is the same observed-remove merge, including a remove that sticks when nobody added a new dot.
ProblemUnion two grow-only sets. Re-add an element on a 2P-Set. Then merge an observed-remove set where one side removes milk and the other adds it again, and a second case where nobody adds it again.
ExpectedThe G-Set contains both elements. The 2P-Set stays without the tag. Milk survives the concurrent re-add and stays gone when the only dots were tombstoned.
Edge cases
- A G-Set merge with itself does not duplicate.
- A tombstone without a new dot keeps the element out.
- Concurrent re-add uses a new counter.
- Test: G-Set unions
gset.value() == {'x', 'y'} - Test: 2P-Set cannot re-add
'tag' not in twop.value() - Test: concurrent re-add survives
'milk' in add_wins.value() - Test: observed remove sticks
'milk' not in stuck.value() - Test: OR-Set merge commutes
left_wins.value() == right_wins.value()
Press Run. Snippets must be self-contained — no network, files, or native modules.
ProblemReplica A adds milk, replica B observes it and removes it, and the merge must keep milk out. A second run adds a new dot on A after B's remove.
ExpectedThe stuck merge is empty. The concurrent re-add merge still contains milk.
Edge cases
- Removing an absent element is a no-op.
- The clock merge keeps the higher counter.
- Test: remove without a new dot sticks
stuck.value().size === 0 - Test: new dot survives
addWins.value().has('milk') - Test: clock survived the merge
mergedClock === 2
Press Run. Snippets must be self-contained — no network, files, or native modules.
Clients as actors
If the actor id is a browser, the counter has to survive restarts and must not rewind. A rewound counter reuses a dot. If that dot is already tombstoned, the add vanishes. If it is still live, you have two meanings for one identity. Sign actor ids, or allocate dots on a server that owns the counter. The set will not notice a lie in the clock.
Interview Q&A
Why can a 2P-Set not re-add?
Answer
The remove-set only grows. Membership is "added and not removed." Putting the element in the add-set again does not take it out of the remove-set. There is no per-add identity that a later add could mint. If the product needs that identity, this is the wrong type.
What does observed-remove mean?
Answer
The remover can only delete adds it has observed. Those dots become tombstones and the tombstones merge by union. An add that happened concurrently allocated a new dot. That dot is absent from the tombstone set, so the element is still a member. Add-wins is that sentence, not a slogan that adds always beat removes.
Why do tombstones have to be in the merge?
Answer
Live dots are not a complete history. Replica A still holds dot 1 after replica B deletes it. A union of live dots puts dot 1 back. The tombstone is the evidence that dot 1 was removed. Drop the evidence before every replica has seen it, and the next sync resurrects the element.
How do you garbage-collect observed-remove tombstones?
Answer
When the dot is causally stable. Every replica in the current membership has acknowledged it. Then no legal future message carries that dot as a new add, and the tombstone can go. Membership changes, offline clients, and a missing acknowledgement keep the tombstone. The dissemination page is how the acknowledgements travel.
Which set is a shopping cart?
Answer
An OR-Set of SKUs, or an OR-Map from SKU to a PN-Counter if quantity matters. The shopper will remove milk and add it again. A 2P-Set will not allow that. At checkout, re-check the quantity against a linearizable inventory service. The cart converging is not the warehouse decrementing once.
How does an OR-Map differ from merging JSON?
Answer
JSON merge that walks fields and picks a winner is usually last-writer-wins in disguise, and it is rarely associative. An OR-Map gives each key an observed-remove membership and each value a real CRDT. Nested registers still lose concurrent edits. You annotate the field. You do not hope the object merges.
What about a Redis set?
Answer
SADD on one primary is not a CRDT. It is one key with one order. Redis Active-Active sets are CRDTs with a documented conflict rule across regions. Cache-aside does not merge a set. It fills a key from a database and tries not to stampede.
When is a G-Set the right answer?
Answer
When the product has no remove. "User ids we have ever seen," "feature flags that only turn on" if you truly never turn them off, and other monotone facts. The moment someone asks for undo, you are on a 2P-Set or an OR-Set, and you should make that choice in the design doc.
Pitfalls
- Shipping a 2P-Set for a toggle and discovering it in production.
- Union-merging live dots and calling the result observed-remove.
- Dropping tombstones on a schedule.
- Letting clients pick actor counters that can go backward.
- Nesting last-writer-wins under an OR-Map and claiming concurrent field edits survive.
- Treating the cart CRDT as the inventory ledger.
Take "emails we have ever bounced," "accounts banned for fraud," and "SKUs in this cart." Assign G-Set, 2P-Set, or OR-Set. For the cart, say what a concurrent remove and add become, and where the stock check lives.
Go Deeper
- Set constructions in Shapiro et al..
- Bieniusa, Zawirski, Preguiça, Shapiro, and Baquero, An Optimized Conflict-free Replicated Set.
- Redis Active-Active for the production set types that are not
SADDon one primary.