Distributed systems
Part 2 of 6 · CRDTsCounters & Registers — G-Counter, PN-Counter, LWW & MV-Register
G-Counter and PN-Counter merge per-replica counts with a component-wise max. Last-writer-wins drops a concurrent value. The multi-value register keeps it.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
Why is max the merge for a G-Counter entry?
Answer
Each replica's own entry only grows. Max is the least upper bound on the natural numbers, so the merge is commutative, associative, and idempotent, and it never forgets a higher observed count.
L2
Why is a shared integer increment not a CRDT?
Answer
The increment is a read, a modify, and a write of one number. Two replicas that both observed 0 both write 1. Exchanging the integers with overwrite keeps 1.
L3
What is a PN-Counter?
Answer
Two G-Counters. Increments go in P, decrements go in N, and the value is P minus N. Merge joins each vector on its own.
L4
Can a PN-Counter keep a balance non-negative?
Answer
No. Concurrent decrements both stick. Use a reservation plus a linearizable commit, or accept a soft limit and reconcile.
L5
Last-writer-wins or multi-value for a display name?
Answer
Last-writer-wins if the product accepts one silent winner. Multi-value if two offline renames must both be shown. That is a product call, not a default.
L6
Which clock belongs on a last-writer-wins register?
Answer
A hybrid logical clock, or a Lamport clock with an actor tie-break. Wall clocks skew, and a bare millisecond timestamp is not a deterministic total order.
L7
How is this different from Redis INCR on one primary?
Answer
Single-primary INCR is linearizable on that primary. Active-Active counters follow the G-Counter or PN-Counter rule across regions and are only strongly eventually consistent.
Failure modes
Overwrite of two increments
Both replicas start at 0, both store 1, and the exchanged integer is 1. One like disappeared.
PN-Counter as a wallet
Two regions decrement together. The merge is negative. The datatype did what it promises.
Wall-clock last-writer-wins
A laptop with a fast clock beats a later edit from a laptop with a slow clock. The tie-break is an accident of NTP.
Actor id that never changes and always wins
A fixed tie-break such as a lexicographic replica name makes one writer win every equal-timestamp collision. Say that out loud if you rely on it.
Misconceptions
Max on the whole counter is the same as max per replica.
Max of the two summed values drops an increment. Max of each replica's entry, then a sum, keeps both.
A PN-Counter can reset to zero by deleting history.
The vectors remain. A true reset needs a new identity or a causal-stability garbage collection you have actually specified.
Last-writer-wins is fine for collaborative text if the timestamp is precise.
Precision does not keep both edits. The whole value is one register. Text needs a sequence CRDT.
Interviewer traps
Implement Paxos to explain a like count.
Draw two maps, merge with max, and sum. Mention Raft only as the tool you refused for this field.
Use Date.now() as the last-writer-wins clock and call it done.
Name skew. Prefer a hybrid logical clock or Lamport plus actor. Equal timestamps still need the actor tie-break.
Design scenario
Same prompt for every reader.
Requirements
Likes never lose an increment after sync. A display-name collision is either one deterministic winner or both values shown. The score may be briefly stale. The wallet is out of scope.
Traffic / scale
Tens of thousands of likes per second, spread across regions. Display-name edits are rare. Score updates are steady.
Latency
A like is a local increment. Cross-region merge can lag by seconds.
Consistency
Strong eventual consistency for all three fields. The display name must not flicker between two winners after both updates have arrived.
Availability
A region partitioned from the others still accepts likes and renames.
Failure assumptions
- Two regions increment the same like before either syncs.
- Two devices rename the profile while offline.
- One region's clock is minutes ahead.
Constraints
- Do not use one shared integer.
- Do not use the like counter as the account balance.
Prompt
A multi-region app counts likes, lets a profile display name change from two devices, and shows a score that can go up or down. None of these are the wallet.
API
Which call is an increment, which is an assign, and which one returns a set of values?
Data
What is stored per replica for the like, and what timestamp sits on the name?
Architecture
Where do you refuse to replicate the wallet with the same mechanism?
One number, two replicas
Prefer
A vector of contributions
Each replica increments only its own slot. Merge takes max per slot and sums. Both likes remain.
- Retransmitting a replica's count does not add it twice.
- A stale lower count loses to the higher one.
- The value can differ across replicas until both vectors arrive. That is strong eventual consistency.
Alternative
Read, add one, write the integer
Both replicas observed 0. Both store 1. The merge of two integers by overwrite is 1.
- Nothing in the payload records who incremented.
- The lost update does not throw.
- A lock or a single primary would have serialized it, at the cost of the offline write.
From a lost increment to a value you can show
The state is the vector. The number on screen is a query.
- 1
Give every replica its own slot
An increment at replica i adds only to counts[i]. Other slots stay untouched. - 2
Merge with max, then sum
For each replica id, keep the larger count. The displayed value is the sum of the slots. - 3
Put decrements in a second vector
A PN-Counter subtracts the N vector from the P vector. Concurrent decrements both apply. The result may be negative. - 4
Decide whether a register may drop a value
Last-writer-wins keeps one timestamp. A multi-value register keeps every version vector that nobody dominates.
Why a shared integer loses an update
Two replicas each increment once from 0. If they exchange the final integers and overwrite, both end at 1. One increment is gone. The CRDT remembers who incremented so the merge can add the contributions instead of picking a winner.
Decisions
- 1
1 Both replicas read 0
- next2 Each increments once
- 2
2 Each increments once
- next3 How do they merge?
- ?
3 How do they merge?
- overwrite4 One increment lost
- per replica max5 Sum keeps both
- 4
4 One increment lost
- 5
5 Sum keeps both
Lesson map
Counters & Registers — G-Counter, PN-Counter, LWW & MV-Register
G-Counter and PN-Counter merge per-replica counts with a component-wise max. Last-writer-wins drops a concurrent value. The multi-value register keeps it.
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 Both replicas read 0"] b["2 Each increments once"] c["3 How do they merge?"] d["4 One increment lost"] a -->|1 Both replicas read 0| b b -->|2 Each increments once| c c -->|overwrite| d
The overwrite branch is what a naive replicated integer does. The max branch is a G-Counter. Same user action, different payload.
G-Counter
State is a map from replica id to a non-negative count. Increment at replica i adds to counts[i]. Merge, for each key, keeps max(a[k], b[k]). The value is the sum of the entries.
Each entry is monotonic. Max is the least upper bound on the natural numbers, so the pointwise merge is a join. Increments commute. A merge never moves a slot backward. Summing after the merge is a query, not a second merge rule. If you max the sums instead of the slots, you are back on the overwrite branch.
A replica that has only seen its own increment reports a smaller value than a replica that has merged both. That skew is allowed. Strong eventual consistency promises they match after both updates have been delivered, not before.
PN-Counter
Keep two G-Counters. P records increments. N records decrements. The value is P minus N. Merge joins P with P and N with N.
You can represent a value that goes down without a distributed lock. You can also go negative, because nothing in the join checks the current value before a decrement. You cannot delete history by writing zero. The slots remain until you garbage-collect them under causal stability, which is a cluster-membership problem, not a one-line reset.
This is the right shape for a score or an approximate stock figure you are willing to reconcile. It is the wrong shape for a wallet. Concurrent decrements both survive. A reservation plus a linearizable commit, or an explicit compensation, is the money path. That commit is Raft or a single database, not a third vector.
Last-writer-wins register
State is a value, a timestamp, and an actor id. Assign proposes a new triple. Merge keeps the greater timestamp. If the timestamps tie, a deterministic actor order picks the winner so both sides agree.
The state is tiny, which is why config flags use it. Concurrent writes have a silent loser. The loser is not a conflict the user can see. Wall clocks make the loser depend on skew and on which laptop synced NTP. Prefer a hybrid logical clock, or a Lamport clock plus the actor id. Do not use this register as the document body. The sequence page is that refusal in detail.
Decisions
- 1
1 Two concurrent assigns
- next2 Keep both values?
- ?
2 Keep both values?
- no3 LWW drops one
- yes4 MV-Register keeps both
- 3
3 LWW drops one
- 4
4 MV-Register keeps both
Multi-value register
Keep every value whose version vector is concurrent with the others. A vector dominates another when it is greater or equal in every actor and strictly greater in one. Merge unions the candidates and drops dominated ones. The application shows a conflict, or it applies a domain rule and writes a new value that dominates both.
Nothing is dropped silently. The set grows until a later write dominates the old vectors. Production code stores dotted values the same way an observed-remove set stores dots. The sketch below is the dominance rule, not a full replica protocol.
Which type
| Type | Concurrent updates | Metadata | Use when | Refuse when |
|---|---|---|---|---|
| G-Counter | Every increment kept | One integer per replica | Likes, view counts | You need decrement |
| PN-Counter | Increments and decrements kept | Two G-Counters | Scores, soft inventory | The value must not go negative |
| LWW-Register | One value kept | Value, timestamp, actor | Rarely edited flags | Collaborative fields, or any silent loss you cannot explain |
| MV-Register | All concurrent values kept | Version vectors | The user must see the clash | You wanted an automatic single value |
Sandbox
The Python snippet is the three small types: a G-Counter that keeps both increments, a PN-Counter that goes negative, and a last-writer-wins register that keeps the greater timestamp. The TypeScript snippet is the multi-value rule: concurrent version vectors both stay, and a later vector drops only the value it dominates.
ProblemTwo replicas increment a shared integer and a G-Counter. A PN-Counter decrements on both sides from zero. Two registers merge on timestamp, then on actor.
ExpectedThe overwritten integer is 1. The G-Counter is 3. The PN-Counter merge is -2. The later timestamp wins, and an equal timestamp breaks toward the greater actor id.
Edge cases
- Merging a counter with itself does not double it.
- A lower slot never replaces a higher one.
- Equal timestamps still pick one actor.
- Test: overwrite loses an increment
lost == 1 - Test: G-Counter keeps both replicas
g.value() == 3 - Test: G-Counter merge commutes
a.merge(b).counts == b.merge(a).counts - Test: G-Counter merge is idempotent
g.merge(g).counts == g.counts - Test: stale slot does not win
a.merge(g).value() == 3 - Test: PN-Counter can go negative
pn.value() == -2 - Test: later timestamp wins
r1.merge(r2).value == 'blue' - Test: actor tie-break is deterministic
tie_a.merge(tie_b).actor == 'B'
Press Run. Snippets must be self-contained — no network, files, or native modules.
ProblemTwo offline assigns produce incomparable version vectors. A later assign on one actor dominates that actor's previous value and leaves the other actor's value in place.
ExpectedThe first merge keeps red and blue. After green at A:2, red is gone and blue remains.
Edge cases
- A vector does not dominate itself.
- An actor missing from a vector counts as zero.
- Test: concurrent values both stay
concurrent.length === 2 - Test: green dominates red only
afterGreen.length === 2 - Test: red is the dominated value
afterGreen.every((entry) => entry.value !== 'red') - Test: blue is still concurrent with green
afterGreen.some((entry) => entry.value === 'blue')
Press Run. Snippets must be self-contained — no network, files, or native modules.
The multi-value dedupe in the sandbox treats the value string as the identity of a candidate. A production register keys candidates by the version vector, so two different values with the same vector cannot both be "concurrent" unless your assign path minted them that way. The dominance rule is the part to defend in an interview.
Single-primary INCR is not this
INCR on one Redis primary is a linearizable update of one key on that primary. Replicas that lag are a replication delay, not a merge. Redis Active-Active counters are the CRDT: increments from several regions join instead of racing on one integer. Cache-aside Redis, the stampede page, is a third thing. It does not merge writes. The production page draws that line again so the modes do not collapse into "we use Redis."
Interview Q&A
Why is max the merge for a G-Counter entry?
Answer
Each replica only increases its own entry. Max is the least upper bound on that natural number. The pointwise max is commutative, associative, and idempotent, and a slot never moves backward. You sum after the merge. Max of the two totals would drop whoever had the smaller sum.
Can a PN-Counter enforce a non-negative balance?
Answer
No. A decrement does not read the global value first. Two replicas can each decrement once from zero and the merge is -2. If the product cannot accept that, take a reservation and commit it on a linearizable store, or accept the soft number and reconcile. Do not add a check that only runs on one replica and call the result a CRDT.
Last-writer-wins or multi-value for a display name?
Answer
If the product can live with one silent winner, last-writer-wins is the smaller state. If two devices rename the user while offline and support must see both strings, keep the multi-value register and make the UI resolve it. Picking last-writer-wins and then promising "we never lose edits" is the bug.
What timestamp should last-writer-wins use?
Answer
A hybrid logical clock, or a Lamport timestamp with an actor id as the tie-break. Date.now() skews, jumps, and is not a total order across regions. Equal timestamps still need the actor comparison or the two sides can keep different values.
How does this relate to Redis INCR?
Answer
One primary's INCR linearizes that key on the primary. Active-Active counters behave like these CRDT counters across regions: the merged value is strongly eventual, and a read can be stale until sync. Do not describe both as "Redis increment" in a design review.
Does merging a G-Counter with itself double the count?
Answer
No. Max of a slot with the same slot is the slot. That is why a gossip retransmit is safe. If your "merge" adds the remote value to the local value, you built a bug that looks like a CRDT until the first retry.
What grows in these types?
Answer
The G-Counter and PN-Counter grow with the number of replica ids, not with the number of increments. A register grows with concurrent versions until something dominates them. Replica-id cardinality is the capacity plan. A client-generated id that changes every launch will exhaust it.
When do you leave this page for a set or a sequence?
Answer
When the payload is membership rather than a number or a single value, go to sets and maps. When the payload is ordered text, a register will discard one of the strings. Go to sequences.
Pitfalls
- Maxing the displayed totals instead of the per-replica slots.
- Using a PN-Counter as a bank balance or a hard stock count.
- Resetting a counter by deleting keys that another replica will merge back.
- Last-writer-wins on a document, a cart, or any field where the loser matters.
- Trusting wall clocks, then blaming the user whose laptop was ahead.
- Calling single-primary
INCRa CRDT.
Write replica A as {A: 1} and replica B as {B: 2}. Merge them. Then decrement once on each side of a fresh PN-Counter and merge that. Then assign "red" at time 1 from A and "blue" at time 1 from B. Say which register keeps both, and which one picks B because the actor id sorts higher.
Go Deeper
- The counter and register sections of Shapiro et al..
- Redis Active-Active application notes on increments that join across regions.
- Kleppmann's hard parts for the last-writer-wins hazards that survive a careful clock.
Next: Sets and maps.