codejump
MediumPro challengePythonJavaScriptTypeScript

System Design — PN-Counter (CRDT)

System DesignDistributed SystemsCRDT

A shared "likes" counter replicated in several data centres that must accept writes while
partitioned and still converge — without locks or a leader. That is a CRDT (conflict-free
replicated data type).

A PN-counter keeps two grow-only maps per replica: p (increments) and n (decrements),
each mapping a replica name to a count. A replica only ever increases its own entry.
value = sum(p) - sum(n). Merging two replicas takes the element-wise maximum of both maps,
which is commutative, associative and idempotent — so replicas converge in any merge order.

solve(args, ops) builds new PNCounter(replicas) — args = [replicas], the list of replica
names, every replica starting empty — and replays ops:

  • inc(replica, n) / dec(replica, n) — that replica counts n more increments / decrements.

Return nothing.

  • merge(dst, src) — dst absorbs src's state (src is unchanged). Returns nothing.
  • value(replica) — the replica's current value.

Example — replicas ["a","b"]

inc(a,5) inc(b,3) value(a) → 5   merge(a,b) value(a) → 8   dec(a,2) value(a) → 6

Sample tests

Test #1Concurrent updates converge
Input: [[["a","b"]],[["inc","a",5],["inc","b",3],["value","a"],["value","b"],["merge","a","b"],["value","a"],["dec","a",2],["value","a"],["merge","b","a"],["value","b"],["merge","b","a"],["value","b"],["dec","b",1],["inc","a",1],["merge","a","b"],["merge","b","a"],["value","a"],["value","b"]]]
Output: [null,null,5,3,null,8,null,6,null,6,null,6,null,null,null,null,6,6]
Test #2Three replicas gossip
Input: [[["x","y","z"]],[["inc","x",1],["inc","y",2],["inc","z",3],["merge","x","y"],["merge","x","z"],["merge","y","x"],["merge","z","y"],["value","x"],["value","y"],["value","z"]]]
Output: [null,null,null,null,null,null,null,6,6,6]
Test #3The value can go negative
Input: [[["a"]],[["dec","a",4],["value","a"],["inc","a",1],["value","a"]]]
Output: [null,-4,null,-3]
← All challenges