Bird
Raised Fist0

Database Sharding Strategies - Range, Hash, Directory-Based

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
▶
Request Trace
Step 1/5
Query Router / Proxy

Receives client query

Accepts incoming query and prepares to route

Protocol:HTTP
BeforeClient query not yet processed by system
AfterQuery Router holds query, ready to resolve shard
Shard Metadata Store

Lookup shard for query key

Returns shard ID based on hash of query key

Protocol:RPC
BeforeQuery Router lacks shard location info
AfterQuery Router knows target shard ID for query
Shard DB Nodes

Execute query on primary shard node

Processes read or write on shard data

Protocol:SQL over TCP
BeforeShard DB Node idle or processing other queries
AfterShard DB Node has executed query and updated data if write
Replica Sets

Serve read requests from replicas

Replica nodes respond to read queries for load balancing

Protocol:SQL over TCP
BeforeReplica nodes have up-to-date replicated data
AfterReplica nodes have served query results to router
Shard Rebalancer Service

Monitor shard load and rebalance

Triggers shard migration commands via Kafka events

Protocol:Kafka
BeforeShard distribution may be uneven
AfterShard Rebalancer initiates shard migration to balance load
🏗️
Architecture Diagram
Architecture Diagram
┌───────────────────────┐
│  Query Router / Proxy │
└─────────────┬─────────┘
              │ HTTP Request (Client Query)
              ▼
┌───────────────────────┐
│  Shard Metadata Store │
└─────────────┬─────────┘
              │ Metadata Lookup (Shard Map)
              ▼
┌───────────────────────┐
│    Shard DB Nodes     │
└─────────────┬─────────┘
              │ Read/Write Query
              ▼
┌───────────────────────┐
│     Replica Sets      │
└─────────────┬─────────┘
              │ Replicated Data Read
              ▼
┌─────────────────────────┐
│ Shard Rebalancer Service │
└─────────────────────────┘
              ▲
              │ Rebalance Commands
              │ (Kafka Events)
              │
              └───────────────┐
Design Rationale

This architecture demonstrates how a client query is routed through a Query Router that consults the Shard Metadata Store to determine the correct shard using a hash-based strategy. The query is then executed on the Shard DB Nodes, with Replica Sets serving read requests to improve scalability and fault tolerance. The Shard Rebalancer Service monitors shard load and triggers rebalancing via Kafka events to maintain even data distribution. This vertical flow ensures efficient routing, data consistency, and scalability in a sharded database system.

Primary Focus

✓

Practice

(1/5)
1. A distributed counter system must handle millions of increments per second with minimal coordination and tolerate network partitions. Which component best supports this requirement?
easy
A. A centralized relational database with strong consistency guarantees
B. A message queue that batches increments before applying them synchronously
C. A distributed lock service to serialize all increments
D. A CRDT-based sharded counter replicated asynchronously across nodes

Solution

  1. Step 1: Identify the need for high write throughput and partition tolerance

    A centralized DB (A) and distributed lock (C) impose coordination and reduce availability. Message queue batching (D) adds latency and synchronous bottlenecks.

  2. Step 2: Recognize CRDT sharded counters allow concurrent increments without coordination and eventual consistency

    CRDTs replicate asynchronously and merge without conflicts, fitting the scale and partition tolerance needs.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    CRDTs enable concurrent, partition-tolerant increments [check]
Hint: CRDTs merge concurrent updates without coordination [check]
Common Mistakes:
2. In the web crawler's request flow, at Step 5 the Duplicate Detection component receives a URL. What happens if this URL has been seen before?
easy
A. The URL is discarded and not sent to the Scheduler to avoid redundant crawling
B. The URL is immediately re-queued to the Scheduler for crawling again
C. The URL is marked for delayed re-crawl but still sent to the Scheduler
D. The URL is sent to the Politeness Policy Manager to check domain delays

Solution

  1. Step 1: Understand Duplicate Detection behavior at Step 5

    If the URL has been seen before, it is filtered out to prevent redundant crawling.

  2. Step 2: Eliminate other options

    Re-queuing duplicates wastes resources; marking for delayed re-crawl is a separate process; Politeness Policy Manager handles timing, not duplication.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Duplicate Detection discards seen URLs to avoid redundancy [check]
Hint: Duplicate Detection discards duplicates before scheduling [OK]
Common Mistakes:
3. For a real-time multiplayer game backend requiring low latency and consistent player state, which architecture is more appropriate and why?
medium
A. Stateful servers storing player state only in a distributed cache without persistence
B. Stateless microservices with external database for player state
C. Stateless servers with client-side state management and server validation
D. Stateful game servers maintaining player state in memory with periodic persistence

Solution

  1. Step 1: Analyze latency and consistency needs

    Real-time games require fast access to player state with strong consistency.

  2. Step 2: Evaluate architecture trade-offs

    Stateful servers with in-memory state reduce latency and allow immediate state updates; periodic persistence balances durability.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Stateful in-memory state + persistence -> low latency, consistent [check]
Hint: In-memory stateful servers best for real-time consistency [check]
Common Mistakes:
4. At 10x scale, which component is most likely to become the first bottleneck in the stock exchange system, and why?
hard
A. The network layer, because TCP connections for order submission exceed server socket limits
B. The Market Data Feed, because broadcasting to millions of subscribers saturates network bandwidth
C. The Order Book storage, because the relational database cannot handle the write throughput
D. The Matching Engine, because partitioned order books require cross-partition coordination for large orders

Solution

  1. Step 1: Analyze scaling challenges

    Matching Engine partitions order books per stock symbol, but large cross-symbol or large orders require coordination, causing latency and bottlenecks at scale.

  2. Step 2: Evaluate other components

    Market Data Feed scales with multicast or sharding; Order Book storage uses scalable Kafka or NoSQL; network layer scales with load balancers and horizontal scaling.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Cross-partition coordination -> Matching Engine bottleneck at scale [check]
Hint: Cross-partition coordination bottlenecks matching engine [check]
Common Mistakes:
5. At 10x scale, which component of the Snowflake ID generation system is most likely to become the bottleneck first, and why?
hard
A. The timestamp source, because clock synchronization across machines becomes impossible at scale.
B. The network bandwidth, because ID generation requires frequent coordination between machines.
C. The sequence number, because generating more than its max IDs per millisecond causes blocking delays.
D. The machine ID allocation, because limited machine ID bits cause ID collisions as machines increase.

Solution

  1. Step 1: Analyze timestamp and network constraints

    Timestamp synchronization (A) is challenging but tolerable with NTP; network coordination (D) is minimal as IDs are generated locally.

  2. Step 2: Evaluate sequence number limits

    Sequence number (B) limits per millisecond can cause blocking but can be mitigated by load balancing or sharding.

  3. Step 3: Identify machine ID allocation bottleneck

    Machine ID bits are fixed (e.g., 10 bits), limiting the number of unique machines. At 10x scale, running out of unique machine IDs causes collisions or requires complex reallocation.

  4. Final Answer:

    Option D -> Option D

  5. Quick Check:

    Fixed machine ID bits limit scale -> collisions or reconfiguration needed [check]
Hint: Fixed machine ID bits limit scale before sequence or timestamp issues [OK]
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