Counters and Sets That Merge
What it is
Teams often run the same service on several machines, each keeping its own copy of the data, so one machine going down doesn't take everything with it. The copies drift apart while they aren't talking to each other, and later need to merge back into one answer. A small family of data built exactly for this is often called a CRDT, short for "conflict-free replicated data type". This challenge has you build two counters and a set, all three built so a merge between any two copies, run any number of times, in any order, always lands on the same final answer.
The core idea
A merge pulls one copy's changes into another. It only goes one way, so updating both copies takes two merges, one in each direction. A correct merge has two properties: merging the same two copies more than once changes nothing after the first time, and merging a group of copies in a different order still ends at the same final answer.
For a counter, this is simple: keep each copy's own running total separate, and a merge takes the bigger of the two numbers for each copy it knows about, never the sum. Adding instead of taking the bigger number would double count the same change if the same merge ever happened twice.
For a set, removing is the hard part. A copy can only remove the additions it has actually seen. If one copy adds a number and a different copy removes that same number without ever having seen the add, the add must survive once the two copies meet. The set remembers which exact additions were removed, instead of just removing the number outright. A set built this way is sometimes called an OR-Set, short for "observed-remove set", and the rule that a same-time add survives a remove is often called "add-wins".
Example: add and remove at the same time
Copy A adds the number 7 and tells copy B about it through a merge. Copy B removes 7. At the same time, copy C adds the number 7 too, with no idea what A or B did. When C's add reaches B through another merge, 7 is present again on B. B's remove could only erase the addition it had actually seen, A's, never C's, which it had not seen at all.
Why removing needs more than "just delete it"
If a remove just deleted the number from a plain set, there would be no way to tell "this number was removed, so a later add should win" apart from "this number was never added here yet". The fix is to keep a record of exactly which additions were removed, instead of letting a remove erase the number outright. People call this a deleted marker, or a tombstone. It means a copy remembers what it removed, even once the number itself is gone from view.
Where you meet this
- Redis Active-Active databases (Redis Software) accept writes in several regions at once and use only CRDTs, so conflicting writes merge in a predictable way. (Active-Active Redis)
- Riak data types include counters and sets. Its docs say that for sets, "If an element is concurrently added and removed, the add will win", and that counters keep every copy's increments and decrements. (Riak data types)
- Automerge and Yjs are libraries for apps where several people edit the same document. Edits made on different devices, even offline, merge without a central server. (Automerge, Yjs)
When to choose it: every copy must keep taking writes even when it cannot reach the others, and "everyone ends up with the same answer" is good enough.
When not to: you need a rule that all copies must respect at every moment, like "this balance never goes below zero" or "only one person gets the last seat". Two copies that cannot talk can both say yes. These types also keep extra data, like a tag for every add, which grows over time.
Common bugs
- Summing a counter's known totals during a merge instead of taking the bigger one, which double counts a repeat merge.
- Clamping a counter that can go negative back up to zero.
- Removing a number from a set by its value, which blocks a later, honest add of the same number forever.
- Merging only the additions and forgetting the removed markers, so a remove never reaches another copy.
- Reusing the same identifying detail for two different additions, so one looks like a repeat of the other.
- Letting a merge change the copy it is merging from, not just the one it is merging into.
Check it yourself
Write down, for one number, every add and every remove that happened to it, and which copy saw which. A remove is only real if the copy doing it had already seen the matching add. After merging everything together, the number should be present if any add survives every remove that actually saw it, and absent otherwise.
Keep it fast
A merge should only look at what the two copies actually hold, never scan one copy's whole history once for every item in the other. Keeping each copy's own additions indexed by the number they're about, rather than as one long unordered list, keeps both a remove and a merge fast as the data grows.
Learn more
Marc Shapiro and others' paper on convergent and commutative replicated data types is the one that introduced this idea and proved it works. Riak's data types, Redis Active-Active databases, and libraries for offline-first apps use data built this way to keep working without a live connection to every other copy.