How do you use CRDTs in collaborative apps (set/counter/map)?

Collaborative apps like Google Docs, Notion, or Figma rely on consistent state across multiple devices editing at the same time. Conflict-free replicated data types (CRDTs) make this possible by ensuring that all replicas converge to the same state without coordination. They’re perfect for systems that prioritize offline edits and low-latency synchronization.

Why It Matters

In system design interviews, CRDTs often come up when discussing real-time collaboration, offline-first design, or multi-region synchronization. Understanding them shows mastery of distributed consistency models. In real-world systems, CRDTs eliminate the need for central conflict resolution logic and make collaboration seamless even under network partitions.

How It Works (Step-by-Step)

1. Choose the replication model

   • State-based CRDTs periodically exchange their entire state and merge using a mathematically safe join function.
   • Operation-based CRDTs propagate only operations and rely on causal delivery.
   • Delta-based CRDTs send minimal incremental state for efficiency.

2. Assign replica identity and timestamps Each device (replica) has a unique ID. Every operation is tagged with a logical or hybrid timestamp to order events deterministically.

3. Select the CRDT type

   • Sets

     • Grow-only Set (G-Set) allows only additions.
     • Two-phase Set (2P-Set) supports add and remove but disallows re-addition after removal.
     • Observed-Remove Set (OR-Set) allows re-addition by tracking tags for adds/removes.
     • Last-Writer-Wins (LWW) Set uses timestamps to decide which operation wins.

   • Counters

     • G-Counter maintains a per-replica counter that only increments.
     • PN-Counter tracks both increments and decrements using two G-Counters.

   • Maps

     • LWW-Map uses timestamps for each key-value pair.
     • OR-Map attaches CRDTs (like sets or counters) to keys and merges them recursively.

4. Merge deterministically Merges must be associative, commutative, and idempotent so the final state converges regardless of update order. For example, counters merge using the element-wise max of replica values.

5. Gossip and anti-entropy Nodes periodically exchange state through gossip. Each side merges updates, guaranteeing eventual consistency even under message loss or duplication.

6. Handle deletes and compaction Sets and maps maintain tombstones (metadata for removed items). These are compacted periodically once all replicas have seen the removal to prevent unbounded growth.

7. Persist and recover safely Store per-replica state so restarts don’t lose causality. This ensures resumed devices merge correctly after downtime.

Real-World Example

• Google Docs uses CRDT-like structures to allow users to edit text collaboratively without locking.
• Redis CRDTs (in Redis Enterprise) enable active-active multi-region databases.
• Figma applies CRDT variants to sync vector graphics edits from multiple clients in real time.

Common Pitfalls or Trade-offs

1. Clock skew in LWW CRDTs Systems relying on timestamps (like LWW-Set or LWW-Map) can lose updates if device clocks drift. Hybrid logical clocks mitigate this risk.

2. Unbounded metadata growth OR-Sets and OR-Maps can accumulate a large number of tags and tombstones. Regular compaction or pruning is necessary for production systems.

3. High memory overhead Tracking per-replica or per-element metadata increases memory usage. This trade-off buys you coordination-free safety.

4. Not ideal for strict ordering CRDTs provide eventual convergence but not total order. For text editors, you need sequence CRDTs (like RGA or LSEQ) to preserve user intent.

5. Membership management Counters with per-replica slots can leak state if old replicas never retire. You need a mechanism for replica cleanup.

Interview Tip

If the interviewer mentions “real-time collaboration” or “offline editing,” mention CRDTs early. Walk through one data type (like OR-Set) and explain its merge logic. Bonus points for noting trade-offs like metadata growth or clock skew.

Key Takeaways

• CRDTs guarantee convergence across replicas without locks or coordination.

• Sets, counters, and maps are the core building blocks for collaborative features.

• LWW CRDTs are simpler but risk clock-based inconsistencies.

• Tombstone management and compaction are key for scalability.

• Always design CRDT merges to be associative, commutative, and idempotent.

Comparison Table

FAQs

Q1. What is a CRDT and why is it useful?

A CRDT (Conflict-free Replicated Data Type) is a data structure that ensures all replicas in a distributed system eventually reach the same state, even with concurrent updates and no coordination.

Q2. How do CRDTs differ from operational transforms?

CRDTs rely on mathematical merge properties, while OT depends on transforming concurrent operations based on order. CRDTs are simpler for distributed, offline systems.

Q3. Which CRDT is best for counters or likes?

Use a PN-Counter, which maintains a grow-only counter for increments and another for decrements, ensuring safe concurrent updates.

Q4. What CRDT type fits a shared todo list?

An OR-Set works best since it allows re-adding deleted items by assigning unique identifiers to each addition.

Q5. How do you reduce CRDT memory overhead?

Compact old tombstones or tags once all replicas have seen the update. Delta-based CRDTs also help by syncing smaller incremental states.

Q6. Are CRDTs eventually consistent or strongly consistent?

They provide eventual consistency. All replicas converge without coordination but may temporarily differ after concurrent updates.

Further Learning

Learn the fundamentals of distributed consistency in Grokking System Design Fundamentals. For deeper concepts like conflict resolution and replication strategies, explore Grokking Scalable Systems for Interviews.

To practice applying these ideas in mock interview scenarios, enroll in Grokking the System Design Interview.