System Design · HLD Interview Questions — Medium

Answer: In traditional hashing, keys are mapped to servers using node_index = hash(key) % N (where $N$ is the cluster size).

• The Problem: If $N$ changes (due to a node crash or addition), almost all keys are mapped to completely different indices. This triggers a massive, immediate cache miss storm, crashing databases.
• Consistent Hashing: Maps both keys and physical servers onto a circular 32-bit integer ring space ($0$ to $2^{32}-1$).

graph TD
    subgraph Hash Ring
        Ring[Circle 0 to 2^32-1]
        NodeA[Server A] -->|Clockwise Next| NodeB[Server B]
        NodeB -->|Clockwise Next| NodeC[Server C]
        NodeC -->|Clockwise Next| NodeA
    end
    Key[Key: hash=1200] -->|Move Clockwise| NodeB

• Routing Mechanism: A key's hash is placed on the ring. Move clockwise until the first server hash is reached; store the key on that server.
• Node Addition/Removal: Only keys located between the modified node and its counter-clockwise neighbor need re-mapping. All other nodes remain untouched.
• Virtual Nodes (VNodes): Maps a physical node to dozens of virtual positions across the ring (e.g., Server_A_1, Server_A_2). This ensures keys are distributed uniformly, preventing hot-spots on single machines.

---

Answer: Sharding splits a large database horizontally, storing different subsets of rows (shards) across distinct database servers.

graph LR
    User[User ID] --> Router{Shard Router}
    Router -->|ID: 1-100| Shard1[(Shard 1)]
    Router -->|ID: 101-200| Shard2[(Shard 2)]

• Range-Based Sharding:
  • Data is split based on ranges of a key attribute (e.g., IDs $0-10,000$ go to Shard 1, $10,001-20,000$ go to Shard 2).
  • Risk: Severe hotspots (e.g., if new users are highly active and get higher IDs).
• Key-Based (Hash-Based) Sharding:
  • Uses a hash function on the sharding key to select the shard: shard_id = hash(key) % total_shards.
  • Risk: Hard to scale total shards without re-sharding all existing data (mitigated by Consistent Hashing).
• Directory-Based Sharding:
  • Maintains a lookup table/directory indicating which shard contains what key.
  • Risk: The lookup table itself becomes a single point of failure (SPOF) and query bottleneck.
• Main Challenges:
  • Cross-Shard Joins: Performing JOIN queries across multiple servers is incredibly expensive and slow.
  • Referential Integrity: Enforcing foreign keys across shards is practically impossible.
  • Re-sharding: Splitting an existing, overloaded shard during active traffic is extremely complex.

---

Answer: The CAP Theorem states that a distributed system can guarantee at most two of the following three properties simultaneously in the event of a network partition:

graph TD
    C[Consistency - Strong CP] --- A[Availability - Highly AP]
    A --- P[Partition Tolerance - Vital]
    P --- C

• Consistency (C): Every read receives the most recent write or an error.
• Availability (A): Every non-failing node returns a non-error response (without guaranteeing it contains the most recent write).
• Partition Tolerance (P): The system continues to operate despite arbitrary packet loss or network splits between nodes.
• The Trade-off: Network partitions ($P$) are physical facts. Therefore, during a partition, a system must choose:
  • CP (Consistency over Availability): Reject writes or block reads until network splits heal, guaranteeing data correctness but degrading availability.
  • AP (Availability over Consistency): Accept reads and writes on both split sides, keeping the system fully available but risking split-brain data conflicts.

---

Answer: A Message Queue (MQ) decouples message producers and consumers, buffering request bursts.

• RabbitMQ (AMQP Push-Model):
  • Broker Internals: Messages are pushed to exchanges, routed to queues based on routing keys, and pushed to active consumers.
  • Message State: Tracked by the broker. Once a message is acknowledged, it is deleted from disk.
  • Use Case: Complex routing, transaction flows, and short-lived message processing.
• Apache Kafka (Log-Based Pull-Model):
  • Broker Internals: An append-only commit log. Messages are written sequentially to partitions.
  • Message State: Tracked by consumers via an offset marker. Messages persist on disk after consumption (immutable history).
  • Use Case: High-throughput event streaming, log aggregation, real-time analytics.

---

Answer: Throttling engines used to enforce system-wide fair-use limits.

• Token Bucket:
  • Tokens are added to a bucket at a fixed rate. Requests consume tokens. If empty, requests are dropped.
  • Pros: Natural handling of short traffic bursts.
• Leaky Bucket:
  • Requests enter a queue. The queue drips (dispatches) requests at a constant, smooth rate.
  • Pros: Smooths out traffic, preventing downstream spikes.
• Fixed Window Counter:
  • Counts requests within fixed time windows (e.g., 100/min from 12:00 to 12:01).
  • Cons: Allows double the limit at window boundaries (e.g., 100 requests at 11:59:59 and 100 at 12:00:01).
• Sliding Window Log:
  • Saves exact timestamps of all requests in a sorted set (like Redis ZSET). Evicts timestamps older than (Current Time - Window Size).
  • Cons: Extremely high memory consumption because every single request timestamp must be stored.
• Sliding Window Counter:
  • Hybrid approach. Computes a weighted sum of request counts from the current and previous windows to estimate instantaneous rate.
  • Pros: Memory efficient; smooths boundary spikes.

---