System Design · HLD Interview Questions — Hard

Answer: A ride-sharing system must track latitude/longitude updates for millions of active drivers and allow riders to search nearby regions instantly. Executing standard relational queries using WHERE lat BETWEEN x AND y results in full table scans ($O(N)$), crashing database processing under heavy traffic.

To solve this, we use Geospatial Indexing to map a 2D physical point into a 1D indexable sequence.

graph TD
    Geo[Geospatial Indexing] --> Geohash[Geohash: Base32 String]
    Geo --> Quadtree[Quadtree: Recursive 4-Quadrant Division]
    Geo --> S2[Google S2: Hilbert Curve Grid Cells]

• Geohashes:
  • Mechanism: Divides the Earth into grid zones, recursively splitting them into smaller regions. Each cell is encoded as a Base32 string (e.g., 9q8yy). Longer prefixes represent tighter boxes.
  • Edge/Boundary Problem: Two points right next to each other on a grid border can have completely different Geohash prefixes (e.g., one starts with 9 and the other with d), making prefix queries fail to capture immediate neighbors.
• Quadtrees:
  • Mechanism: A tree structure where each node has exactly four children (NW, NE, SW, SE). Nodes split recursively only when a quadrant exceeds capacity bounds (e.g., $\ge 100$ drivers).
  • Pros: Dynamically sizes cells (deep trees in New York, shallow in deserts).
  • Cons: Very complex to update, balance, and synchronize in real-time memory across a distributed cluster when drivers are moving fast.
• Google S2:
  • Mechanism: Projects the Earth's sphere onto a cube, mapping it to a 1D index using a mathematical Hilbert Curve. Divides the Earth into 31 hierarchical levels of cells.
  • Pros: Solves the boundary problem cleanly. Preserves spatial locality: points physically close in 2D space are highly likely to be adjacent on the 1D Hilbert index. The industry standard.

---

Answer: The CAP Theorem states that in the event of a network Partition ($P$), a system must choose between Consistency ($C$) and Availability ($A$).

Expansion to PACELC:

Partitions are rare in physical datacenters. PACELC models the system trade-offs during normal operations (when there is no partition).

$$\text{If Partition (P)} \longrightarrow \text{choose Availability (A) or Consistency (C)}$$ $$\text{Else (E)} \longrightarrow \text{choose Latency (L) or Consistency (C)}$$

graph TD
    PACELC{PACELC Theorem} --> P[If Partition: P]
    PACELC --> E[Else Normal: E]
    P --> P_A[Availability: PA]
    P --> P_C[Consistency: PC]
    E --> E_L[Latency: EL]
    E --> E_C[Consistency: EC]

• PA/EL System (e.g., MongoDB, DynamoDB): During partitions, prioritizes availability. During normal operations, prioritizes low latency by writing/reading locally and updating replicas asynchronously.
• PC/EC System (e.g., Google Spanner, standard RDBMS): Prioritizes consistency at all times. During normal operations, it blocks writes until synchronous replication across all nodes completes, increasing latency but preventing stale reads.

---

Answer: Consensus protocols guarantee that a cluster of nodes can agree on a sequence of state values, even if some nodes fail.

• Raft (Leader-Based Protocol):
  • States: Follower, Candidate, Leader.
  • Leader Election: If a follower stops receiving heartbeats (Election Timeout), it transitions to Candidate, increments the Term, votes for itself, and requests votes from peers. It becomes Leader if it receives a majority of votes ($\ge N/2 + 1$).
  • Log Replication: All writes go to the Leader. The Leader writes sequentially to its log and sends an AppendEntries RPC to followers. Once a majority of followers ACK the write, the Leader commits it and applies it to its local state machine.
  • Split-Brain Prevention: The majority requirement ensures only one candidate can secure enough votes to become Leader in any partition. If a partition heals, the leader with the lower Term is demoted to follower.
• Paxos (Leaderless/Multi-Leader):
  • Operates in two phases:
    1. Phase 1 (Prepare): Proposer sends a proposal number $N$ to acceptor nodes. Acceptors return their highest accepted value if they promise not to accept any future proposals numbered $< N$.
    2. Phase 2 (Accept): If a majority of acceptors agree, the proposer broadcasts the value to acceptors to finalize the write.

---

Answer: Standard physical clocks cannot be used to order events in distributed systems due to network latencies and inevitable clock drift.

• Lamport Timestamps:
  • Every node maintains a local integer counter, initialized to 0.
  • Before executing a local event, increment the counter: $L = L + 1$.
  • When sending a message, attach the local counter value.
  • When receiving a message, update local counter: $L_{\text{recv}} = \max(L_{\text{local}}, L_{\text{msg}}) + 1$.
  • Limitation: If $L(A) < L(B)$, we cannot conclude that event A caused event B; it only provides a total ordering, not causal history.
• Vector Clocks:
  • Every node maintains an array/vector of size $N$ (where $N$ is the cluster size).
  • When sending a message, Node $i$ increments its own element: $V_i[i] = V_i[i] + 1$ and attaches the vector.
  • When receiving a message from Node $j$, update local vector: $V_i[k] = \max(V_i[k], V_{\text{msg}}[k])$ for all $k$, and increment $V_i[i] = V_i[i] + 1$.
  • Causality: Event $A$ causally preceded $B$ if every element in $V(A) \le V(B)$ and at least one element is strictly smaller. If elements diverge (e.g., $V(A)$ has some higher values and $V(B)$ has others), a conflict is detected, requiring application-level resolution.

---

Answer: CRDTs are distributed data structures that can be updated independently and concurrently across replicas without coordination, guaranteeing eventual convergence without conflict resolution loops.

• State-Based (CvRDT):
  • Replicas sync by sending their entire local state to other replicas.
  • A merge function must be commutative ($A \sqcup B = B \sqcup A$), associative ($A \sqcup (B \sqcup C) = (A \sqcup B) \sqcup C$), and idempotent ($A \sqcup A = A$).
  • Use Case: PNCounter (Positive-Negative Counter), LWW-Element-Set (Last-Write-Wins Set).
• Operation-Based (CmRDT):
  • Replicas sync by broadcasting individual operation payloads (e.g., "Add 5", "Remove Item X").
  • Requires a reliable, causal, ordered network delivery channel to guarantee all replicas apply operations in compatible sequences.
  • Use Case: Collaborative real-time document editors (e.g., Figma, Google Docs).

---