Counting Without Coordination
Imagine a "Likes" counter on a social media post. The post is replicated across three data centers. Users in each data center click "Like." How do you count the total likes without routing every click through a single central server?
A naive approach — each server stores a single integer and increments it — fails immediately. If Server A has count=5 and Server B has count=3, and they sync, what's the merged value? You can't just take max(5, 3) = 5 because that loses Server B's 3 likes. You can't add them (5 + 3 = 8) because some of those likes might already be counted on both servers.
The G-Counter (Grow-Only Counter)
The G-Counter solves this by giving each replica its own "lane" in a vector:
Each replica stores a map: { replica_id → count }
Server A: { A: 5, B: 0, C: 0 }
Server B: { A: 0, B: 3, C: 0 }
Server C: { A: 0, B: 0, C: 2 }
Rules:
- A replica can only increment its own lane. Server A can only increment A.
- Merge = take the element-wise maximum across all lanes.
- Value = sum all lanes.
Merge example:
Merge(A, B) = { A: max(5,0), B: max(0,3), C: max(0,0) }
= { A: 5, B: 3, C: 0 }
Value = 5 + 3 + 0 = 8 ✅
Why max() is safe: Counts only go up (grow-only). If Server A has already seen its own count of 5, taking max(5, 5) = 5 correctly handles duplicate sync messages (idempotency). No count is ever double-counted.
The PN-Counter (Positive-Negative Counter)
G-Counters only go up. For a counter that supports both increment and decrement (like a shopping cart item quantity), use a PN-Counter.
A PN-Counter is simply two G-Counters:
- P (Positive): Tracks all increments.
- N (Negative): Tracks all decrements.
Value = sum(P) - sum(N)
Example:
P = { A: 10, B: 5 } # 15 total increments
N = { A: 3, B: 2 } # 5 total decrements
Value = 15 - 5 = 10
Merge is the same as G-Counter: element-wise max on both P and N independently.
The constraint: Each replica still only modifies its own lane in P and N. This prevents double-counting while allowing full increment/decrement semantics.
Key Point: The G-Counter's insight — partition the state space so each replica owns a disjoint slice — is a general pattern in CRDT design. When you can assign ownership of a state partition to a single writer, you eliminate write conflicts entirely. This same pattern appears in distributed sequence CRDTs (like Logoot and LSEQ) used for collaborative text editing.