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 with Conflict Resolution
45 min · senior
senior

Design a collaborative document editing platform serving 50 million daily active users (DAU) with real-time multi-user editing, offline support, and end-to-end encryption. The system must maintain P99 latency under 200ms for edit propagation and conflict resolution. Users can edit simultaneously from multiple devices, and edits must be merged consistently with minimal user-visible conflicts.

Constraints
  • End-to-end encryption of document content in transit and at rest
  • Support offline editing with seamless sync upon reconnection
  • P99 edit propagation latency under 200ms globally
  • Support up to 100 concurrent editors per document
  • Conflict resolution must guarantee eventual consistency with minimal user disruption
📋
Guided Steps
1/5
Step 1
Choosing the Real-Time Sync Protocol
Which protocol and data structure would you use to enable real-time collaborative editing with conflict resolution?
💡 Hint
Consider Operational Transformation (OT) vs Conflict-free Replicated Data Types (CRDT) and their trade-offs in latency and complexity.
Key Decision
Use CRDT (Conflict-free Replicated Data Types) implemented with Automerge or Yjs libraries for client-side conflict resolution and real-time sync, enabling offline edits and eventual consistency without central coordination.
Interviewer Expectation
Mid: Names OT or CRDT and basic differences. Senior: Explains CRDT's advantage in offline support, no central server bottleneck, and how OT requires complex transformation functions and central ordering.
⚠️Common Wrong Answer
Choosing OT without considering offline support - OT requires central server ordering, causing high latency and poor offline experience.
Step 2
Designing the Messaging Backbone
What messaging infrastructure would you use to propagate edits between clients and servers at scale with ordering guarantees?
💡 Hint
Think about partitioning by document ID and ensuring ordered delivery for consistency.
Key Decision
Use Apache Kafka with document_id as the partition key to guarantee ordered, scalable, and durable edit event streams per document, enabling efficient replay and recovery.
Interviewer Expectation
Mid: Names Kafka for messaging. Senior: Explains why document_id partition key ensures all edits for a document go to the same partition, preserving order and simplifying conflict resolution.
⚠️Common Wrong Answer
Using RabbitMQ or generic message queues without partitioning - leads to unordered delivery and inconsistent document states at scale.
Step 3
Data Storage for Document State and History
Which storage system would you choose to persist document states and edit histories for fast reads and writes at scale?
💡 Hint
Consider storage optimized for high write throughput and range queries for version history.
Key Decision
Use Cassandra with document_id as partition key and timestamp clustering key to store document versions and edit history, enabling linear scalability and efficient range scans for syncing.
Interviewer Expectation
Mid: Names Cassandra or similar NoSQL. Senior: Explains Cassandra's LSM-tree write optimization, partition key choice for locality, and how it supports efficient incremental sync.
⚠️Common Wrong Answer
Using relational databases like MySQL - causes write bottlenecks and poor horizontal scalability for high QPS.
Step 4
Ensuring End-to-End Encryption and Access Control
How would you design encryption and access control to protect document content in transit and at rest without sacrificing real-time collaboration?
💡 Hint
Think about client-side encryption keys and how to enable server-side conflict resolution without decrypting content.
Key Decision
Implement client-side encryption with keys managed per document; use homomorphic encryption or encrypted CRDTs to allow conflict resolution on encrypted data, combined with TLS for transport security.
Interviewer Expectation
Mid: Mentions TLS and encryption at rest. Senior: Explains client-side encryption key management, challenges of conflict resolution on encrypted data, and trade-offs of encrypted CRDTs.
⚠️Common Wrong Answer
Encrypting only at rest or in transit - exposes data on servers and breaks end-to-end encryption guarantees.
Step 5
Handling Offline Editing and Sync
How would you design the system to support offline editing and seamless synchronization upon reconnection?
💡 Hint
Consider local state storage and conflict resolution mechanisms that work without server coordination.
Key Decision
Use CRDTs on the client to allow local edits offline; upon reconnection, clients send their CRDT deltas to the server, which merges them using CRDT merge functions ensuring eventual consistency.
Interviewer Expectation
Mid: Mentions offline caching. Senior: Explains CRDT merge semantics, delta sync optimization, and how this avoids complex OT transformations or manual conflict resolution.
⚠️Common Wrong Answer
Relying on server-side OT for conflict resolution - offline edits cause conflicts and require complex reconciliation.
🔌
API Design Challenge
Sketch 3 core API endpoints for the collaborative editing system: how clients send edits, sync document state, and acknowledge received updates.
Hints
  • How does the client send incremental edits to the server?
  • How does the client synchronize document state after offline periods?
  • How does the client acknowledge received updates to ensure reliable delivery?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Use of CRDT over OT for offline support and conflict resolution
  • Kafka with document_id partition key for ordered event streaming
  • Cassandra for scalable document state and history storage
  • Client-side encryption ensuring end-to-end security
Good to Have - 30%
  • WebSocket for real-time bidirectional communication
  • Redis for presence and ephemeral session management
  • Delta sync optimization for bandwidth efficiency
Bonus - 10%
  • Homomorphic encryption or encrypted CRDTs for conflict resolution on encrypted data
  • Global multi-region Kafka clusters for low latency worldwide
Anti-patterns to Avoid
Using OT without offline support - causes high latency and poor user experience during network partitions because OT requires central server ordering, which blocks edits when offline.
Generic message queues without partitioning - leads to unordered edits and inconsistent document states at scale due to lack of ordering guarantees per document.
Relational databases for high write throughput - causes write bottlenecks and poor horizontal scalability, unable to handle high QPS and large document version histories efficiently.
✅
Model Answer
▼ Reveal

This design uses CRDTs (e.g., Automerge or Yjs) for client-side conflict resolution enabling offline editing and eventual consistency without central coordination. Apache Kafka with document_id partition key provides ordered, scalable messaging for edit propagation. Cassandra stores document states and edit histories with partitioning by document_id and clustering by timestamp for efficient sync. Client-side encryption with per-document keys and TLS ensures end-to-end security while allowing encrypted CRDT operations. Offline edits are merged via CRDT deltas upon reconnection. WebSocket and Redis optimize real-time collaboration experience.

Key Decisions
  • Use CRDTs (Automerge/Yjs) for offline support and decentralized conflict resolution
  • Use Apache Kafka with document_id as partition key to guarantee ordered event streams per document
  • Use Cassandra with document_id partition key and timestamp clustering key for scalable storage and efficient incremental sync
  • Implement client-side encryption with per-document keys and encrypted CRDTs to maintain end-to-end encryption without sacrificing conflict resolution
  • Use TLS for transport security and WebSocket for real-time communication
  • Use Redis for presence and ephemeral session management to enhance collaboration experience
  • CRDT libraries like Automerge or Yjs enable decentralized conflict resolution and offline editing support.
  • Apache Kafka with document_id partition key ensures ordered, scalable edit event streaming per document.
  • Cassandra with document_id partition key and timestamp clustering key supports high write throughput and efficient version history queries.
  • Client-side encryption with key management per document preserves end-to-end encryption while enabling conflict resolution on encrypted data.
  • TLS secures data in transit between clients and servers to prevent man-in-the-middle attacks.
  • CRDT delta synchronization minimizes bandwidth and latency during offline-to-online state merges.
  • Use WebSocket connections for low-latency, bidirectional communication between clients and servers.
  • Implement Redis for ephemeral session state and presence detection to optimize real-time collaboration experience.

Practice

(1/5)
1. In the request flow of a real-time ML inference system, at Step 4 the Model Router receives a prediction request. What happens if the system is currently in shadow mode with a new model deployed?
easy
A. The Model Router sends the request to both the production and shadow models but returns only the production model's prediction.
B. The Model Router forwards the request only to the new shadow model and returns its prediction.
C. The Model Router queues the request until the shadow model finishes training before forwarding.
D. The Model Router rejects the request to avoid inconsistent predictions during shadow testing.

Solution

  1. Step 1: Understand shadow mode request routing

    Shadow mode runs new models in parallel without affecting live traffic. So, requests are sent to both models.

  2. Step 2: Identify response behavior

    Only the production model's prediction is returned to the client; shadow model predictions are logged for evaluation.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Shadow mode duplicates requests but returns production output [check]
Hint: Shadow mode duplicates requests; only production output returned [OK]
Common Mistakes:
2. A company wants to decouple rapid feature deployments from the risk of impacting the entire system. Which architectural approach best supports this requirement?
easy
A. A microservices architecture with independently deployable services
B. A layered monolith with a shared database and common deployment
C. A monolithic architecture with modular codebase and feature flags
D. A serverless architecture with tightly coupled functions

Solution

  1. Step 1: Identify deployment isolation needs

    Decoupling feature deployments requires independent service lifecycles, which microservices provide.

  2. Step 2: Evaluate alternatives

    Monoliths (A and C) share deployment units, risking system-wide impact. Serverless (D) can be tightly coupled if functions share state or deployment.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Microservices enable independent deploys and reduce blast radius [check]
Hint: Independent deploys need microservices, not just modular code [check]
Common Mistakes:
3. A web API must limit incoming requests to 100 per second with bursts allowed up to 200 requests. Which component best enforces this rate limiting with burst handling?
easy
A. A fixed window counter that resets every second
B. A simple request queue that drops requests when full
C. A leaky bucket algorithm that processes requests at a fixed rate without bursts
D. A token bucket algorithm that refills tokens at a steady rate with a maximum bucket size

Solution

  1. Step 1: Identify rate limiting with burst support

    The token bucket algorithm allows tokens to accumulate up to a max bucket size, enabling bursts beyond the steady refill rate.

  2. Step 2: Eliminate other options

    Fixed window counters cause spikes at window boundaries and don't handle bursts well. Leaky bucket smooths traffic but disallows bursts. Simple queues drop excess requests without rate control.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Token bucket allows bursts by token accumulation [check]
Hint: Token bucket = steady refill + burst capacity [OK]
Common Mistakes:
4. If the Kafka event queue used to stream code updates to the vector index is down, what exactly breaks in the AI Code Assistant's update pipeline?
medium
A. The code generator fails to produce completions due to missing context embeddings
B. The vector index update worker blocks waiting for new events, delaying embedding refreshes but serving existing queries
C. The Retriever immediately returns stale embeddings without any fallback
D. The system loses all code update events permanently, causing data loss

Solution

  1. Step 1: Understand Kafka's role in update pipeline

    Kafka streams code updates to vector index workers; if down, updates stop flowing.

  2. Step 2: Trace impact on components

    Retriever can still serve existing embeddings (A and B incorrect); system does not lose all events permanently due to Kafka's durability (D incorrect).

  3. Step 3: Identify generator failure

    Without fresh embeddings, generator lacks up-to-date context, causing failures or degraded completions (C correct).

  4. Final Answer:

    Option A -> Option A

  5. Quick Check:

    Kafka down blocks embedding updates, generator lacks context [check]
Hint: Kafka down stalls embedding updates, generator lacks fresh context [check]
Common Mistakes:
5. At 10x traffic scale, which component in a system using a Reverse Proxy, API Gateway, and Load Balancer is most likely to become the bottleneck first, and why?
hard
A. API Gateway, because it performs CPU-intensive tasks like authentication and request transformation on every request
B. Load Balancer, because it maintains stateful TCP connections that cannot be easily sharded
C. Reverse Proxy, because it caches responses and runs out of memory under high load
D. DNS load balancing, because it cannot dynamically adjust to rapid traffic changes

Solution

  1. Step 1: Analyze component scaling characteristics

    Load Balancers typically handle stateless TCP connections and can be scaled horizontally; Reverse Proxies cache but can be scaled with eviction policies; DNS load balancing is not a runtime bottleneck.

  2. Step 2: Identify CPU-intensive bottleneck

    API Gateway performs authentication, rate limiting, and transformations per request, which are CPU and memory intensive and harder to scale linearly.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    API Gateway CPU load scales with request complexity, causing bottleneck [check]
Hint: API Gateway CPU-heavy tasks cause first bottleneck 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