Bird
Raised Fist0

Design Google Docs - Collaborative Editing, Conflict Resolution, OT vs CRDT

HLDhardInterview freq: high
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🏗️
Design Google Docs - Collaborative Editing, Conflict Resolution, OT vs CRDT
Design a scalable collaborative document editing system with real-time conflict resolution using OT and CRDT
hardStorage and CollaborationFreq: high
Prerequisites:Operational TransformationConflict-free Replicated Data Types (CRDT)
⚙️
Functional Requirements
  • Real-time collaborative editing of documents by multiple users simultaneously
  • Conflict resolution to merge concurrent edits without data loss
  • Version history and undo/redo support per user
  • Offline editing with eventual synchronization
  • User presence and cursor position sharing
  • Document sharing and access control management
📊
Non-Functional Requirements
  • Support 2 billion daily active users globally
  • End-to-end latency for edit propagation under 100ms P99
  • System availability of 99.99% uptime
  • Consistency model: strong eventual consistency with low conflict rate
  • Support documents up to 1GB in size with incremental updates
❓
Clarifying Questions to Ask
  • What is the expected average and peak concurrency per document?
  • Should the system prioritize low latency or strong consistency?
  • Is offline editing mandatory or optional?
  • What is the expected document size distribution and max size?
  • How should user permissions and sharing be managed?
  • Are there any constraints on network bandwidth or client capabilities?
Out of Scope
✗ Full-text search within documents
✗ Rich media embedding and rendering (images, videos)
✗ Mobile app UI/UX design
✗ Third-party plugin or extension support
📌
Assumptions
  • 2 billion daily active users (DAU)
  • Each user generates 40 edit operations per day on average
  • Average edit operation size is 100 bytes
  • Peak write QPS is 5× average write QPS due to diurnal and regional spikes
  • Documents have an average retention period of 30 days for active editing data
⚡
QPS Calculation
write qps925926
peak write qps4629630
read qps9259260
💾
Storage Estimate
daily storageApproximately 8 TB/day (925,926 writes/sec × 100 bytes × 86400 sec)
retention storageApproximately 240 TB (8 TB/day × 30 days)
with replicationApproximately 720 TB total storage (240 TB × 3 replicas)
🖥️
Server Estimate
write servers463
read servers463
🏗️
Architecture Diagram
Architecture Diagram
          +-------------+
          |   Clients   |
          +------+------+
                 | WebSocket / gRPC (real-time edits)
          +------+------+
          |  API Gateway|
          +------+------+
                 |
          +------+------+
          |  Edit Router|  (shards by document_id)
          +------+------+
                 /             \
 +--------+             +--------+
 | OT     |             | CRDT   |
 | Service|             | Service|
 +--------+             +--------+
                 \             /
          +------+------+
          | Conflict    |
          | Resolver   |
          +------+------+
                 |
          +------+------+
          |  Storage    | (Cassandra + RocksDB)
          +------+------+
                 |
          +------+------+
          | Notification| (Redis Pub/Sub for presence, cursors)
          +-------------+
🧩
Components
API Gateway
Handles client connections, authenticates users, and routes requests to edit routers
Why thisEnvoy proxy supports gRPC and WebSocket with low latency, TLS termination, and advanced load balancing
Why notNginx lacks native gRPC-WebSocket support and is less efficient for long-lived connections
Edit Router
Shards incoming edit operations by document_id to appropriate backend service
Why thisConsistent hashing with Ketama ensures minimal remapping when scaling and even load distribution
Why notDNS-based routing is too coarse and causes uneven load distribution and higher latency
Operational Transformation (OT) Service
Processes concurrent edits using OT algorithms to transform and merge operations
Why thisOT provides low-latency conflict resolution with strong intention preservation for linear text editing, widely used in Google Docs
Why notCRDTs have higher metadata overhead and complexity for linear text editing, impacting performance
CRDT Service
Processes edits using CRDTs for data types where OT is complex or infeasible
Why thisCRDTs guarantee eventual consistency without central coordination, suitable for complex data types and offline edits
Why notOT cannot handle non-linear data structures or offline edits as robustly as CRDTs
Conflict Resolver
Merges outputs from OT and CRDT services, resolves edge conflicts, and orders operations
Why thisCentralized component ensures consistent global document state and causal ordering using vector clocks and timestamps
Why notFully decentralized merging risks divergent document states and complex reconciliation
Storage Layer
Stores document states, operation logs, and version history with high availability
Why thisApache Cassandra provides linear scalability, tunable consistency, and wide-column storage optimized for high write throughput
Why notRelational DBs like PostgreSQL do not scale linearly at 4.6M writes/sec and require manual sharding
Notification Service
Publishes real-time presence, cursor positions, and edit notifications to clients
Why thisRedis Pub/Sub offers sub-millisecond latency, native TTL for ephemeral presence data, and supports high fan-out
Why notKafka has higher latency and is not optimized for ephemeral presence updates requiring low latency
🔄
Data Flow
1
Client → API Gateway
Send edit operation via WebSocket/gRPC
Low-latency bi-directional channel for real-time edits
2
API Gateway → Edit Router
Route edit to shard based on document_id
Ensures all edits for a document go to same backend
3
Edit Router → OT or CRDT Service
Process edit with appropriate conflict resolution algorithm
OT for linear text, CRDT for complex data types
4
OT/CRDT Service → Conflict Resolver
Send transformed/merged operations for global ordering
Ensures consistent document state across replicas
5
Conflict Resolver → Storage Layer
Persist operations and updated document state
Durably store edits and version history
6
Conflict Resolver → Notification Service
Publish presence, cursor, and edit notifications
Notify clients for real-time UI updates
7
Notification Service → Clients
Push notifications via WebSocket/gRPC
Low-latency updates for collaborative experience

Practice

(1/5)
1. A blob storage system must handle millions of small object writes per second with low latency and guarantee durability. Which component is primarily responsible for decoupling the high write throughput from the slower disk persistence layer?
easy
A. Use a single master node to serialize all writes
B. Use a relational database to store all object metadata synchronously
C. Use a CDN edge cache to absorb write bursts
D. Use a distributed write-ahead log (e.g., Kafka) to buffer writes before persistence

Solution

  1. Step 1: Identify the role of the distributed log

    The distributed write-ahead log buffers incoming writes asynchronously, decoupling high write throughput from slower disk persistence.

  2. Step 2: Eliminate other options

    Relational DBs synchronously block writes, CDN caches are read-optimized not write buffers, and a single master node creates a bottleneck.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Distributed log buffers writes asynchronously for durability and throughput [check]
Hint: Distributed log buffers writes before disk persistence [check]
Common Mistakes:
2. In the vector database request flow, at Step 4 the ANN Search Worker queries the HNSW index with a new vector. What state does the worker observe if the index is currently rebuilding due to a recent bulk insert?
easy
A. The worker returns stale search results from the previous index snapshot
B. The worker blocks until the rebuild completes before returning results
C. The worker returns an empty result set indicating no neighbors found
D. The worker queries a fallback brute-force scan of all vectors

Solution

  1. Step 1: Understand HNSW index rebuild behavior

    HNSW index rebuilds asynchronously; during rebuild, queries use the last consistent snapshot.

  2. Step 2: Analyze worker behavior at Step 4

    The ANN Search Worker returns results from the previous stable index snapshot, so stale but consistent results are served.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    HNSW queries serve last snapshot during rebuild, avoiding blocking [check]
Hint: HNSW queries serve last snapshot during rebuild, no blocking [check]
Common Mistakes:
3. In a relational database transaction flow, at Step 4 the transaction manager checks the lock table before committing. What happens if the lock is held by another transaction at this step?
easy
A. The transaction manager immediately aborts the transaction without retry
B. The transaction manager waits (blocks) until the lock is released or a timeout occurs
C. The transaction manager skips the lock check and commits anyway
D. The transaction manager escalates the lock to a global lock manager

Solution

  1. Step 1: Understand lock table role at Step 4

    The transaction manager uses the lock table to ensure no conflicting writes before commit.

  2. Step 2: Behavior on lock contention

    If the lock is held, the transaction manager blocks to maintain serializability, waiting or timing out rather than aborting immediately or skipping checks.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Lock contention causes blocking until release or timeout [check]
Hint: Lock held -> transaction blocks, no skipping or immediate abort [check]
Common Mistakes:
4. For a system requiring strict consistency on command handling but eventual consistency on query side, which architecture best fits?
medium
A. Use CQRS with event sourcing and asynchronous read model updates
B. Use a single monolithic database for both commands and queries
C. Use eventual consistency everywhere with no command validation
D. Use synchronous replication between command and query databases

Solution

  1. Step 1: Understand consistency requirements

    Strict consistency on commands requires immediate validation; eventual consistency on queries allows asynchronous updates.

  2. Step 2: Evaluate architectures

    CQRS with event sourcing separates command and query models, enabling strict command consistency and eventual query consistency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    CQRS + event sourcing -> strict command, eventual query consistency [check]
Hint: CQRS splits command and query for tailored consistency [check]
Common Mistakes:
5. At 10x scale, which component of a B-Tree index is most likely to become the bottleneck first, and why?
hard
A. The leaf nodes, because they grow linearly and cause large disk I/O for range scans
B. The root node, because it becomes a hotspot due to all searches starting there, causing contention
C. The internal nodes, because their fan-out decreases with scale, increasing tree height drastically
D. The buffer cache, because it cannot hold all index pages, causing frequent page faults

Solution

  1. Step 1: Understand B-Tree root node role

    All searches start at the root node, which must be accessed for every lookup, making it a hotspot under high concurrency.

  2. Step 2: Analyze scaling impact

    At 10x scale, root node contention increases as many threads compete to read/update it, limiting throughput before leaf or internal nodes become bottlenecks.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Root node hotspot causes contention first at scale [check]
Hint: Root node is single entry point, hotspot at scale [check]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard