Bird
Raised Fist0

Database Sharding Strategies - Range, Hash, Directory-Based

HLDmediumInterview freq: common
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Database Sharding Strategies - Range, Hash, Directory-Based
45 min · senior
senior

You are building the backend data storage layer for a 50 million daily active user (DAU) social media startup. The system must support low-latency user profile and activity data access with P99 latency under 200ms. Data must be encrypted at rest and in transit. The workload includes heavy read and write traffic with skewed access patterns (some hot users). The system must support offline data delivery and efficient resharding as user base grows. Design the database sharding strategy to meet these constraints.

Constraints
  • P99 latency under 200ms for read/write requests
  • Data encrypted at rest and in transit (TLS + disk encryption)
  • Support offline data delivery with eventual consistency
  • Handle skewed user access patterns with hot keys
  • Enable online resharding with minimal downtime
📋
Guided Steps
1/5
Step 1
Choosing the Sharding Key and Strategy
Which sharding strategy and key would you choose to distribute user data across nodes?
💡 Hint
Consider workload skew, query patterns, and range vs hash trade-offs.
Key Decision
Use consistent hashing with MurmurHash on user_id as shard key to evenly distribute load and avoid hotspotting; reject range sharding due to skewed user ID distribution causing uneven load.
Interviewer Expectation
Mid: Names consistent hashing and user_id as shard key. Senior: Explains why range sharding fails with hot users and how consistent hashing enables balanced load and easier resharding.
⚠️Common Wrong Answer
Using range-based sharding on user_id leading to hotspots and overloaded shards, causing latency spikes and uneven resource utilization.
Step 2
Handling Hot Keys and Skewed Access Patterns
How would you mitigate hotspots caused by very popular users or data?
💡 Hint
Think about caching, replication, or directory-based approaches.
Key Decision
Implement directory-based sharding with a metadata service (using Apache Zookeeper) to track hot keys and replicate their data across multiple shards; reject pure hash sharding as it cannot handle hotspots efficiently.
Interviewer Expectation
Mid: Mentions caching hot keys in Redis. Senior: Explains directory-based sharding with Zookeeper metadata for dynamic hot key replication and load balancing.
⚠️Common Wrong Answer
Relying solely on hash sharding without hotspot mitigation, resulting in overloaded nodes and degraded P99 latency.
Step 3
Ensuring Data Encryption and Security
How do you ensure data is encrypted at rest and in transit across shards?
💡 Hint
Consider TLS for network and disk-level encryption for storage.
Key Decision
Use TLS 1.3 for all inter-node and client-server communication; enable disk-level encryption with AWS KMS-managed keys on Cassandra nodes; reject application-level encryption due to complexity and performance overhead.
Interviewer Expectation
Mid: Mentions TLS for network encryption. Senior: Details TLS 1.3, disk encryption with KMS, and trade-offs rejecting app-level encryption for latency reasons.
⚠️Common Wrong Answer
Encrypting only in transit but not at rest, exposing data to risk if disks are compromised.
Step 4
Designing for Online Resharding and Minimal Downtime
How would you enable resharding as user base grows without downtime?
💡 Hint
Think about consistent hashing ring changes and metadata updates.
Key Decision
Use consistent hashing with virtual nodes and a metadata service (Apache Zookeeper) to update shard mappings dynamically; clients fetch updated shard map to route requests; reject static range sharding which requires full data migration and downtime.
Interviewer Expectation
Mid: Mentions consistent hashing. Senior: Explains virtual nodes, metadata service for shard map updates, client-side routing, and zero downtime resharding.
⚠️Common Wrong Answer
Static shard assignments requiring offline data migration causing service downtime.
Step 5
API Design for Client Interaction
Sketch 3 core API endpoints for clients to interact with the sharded database system.
💡 Hint
How does the client write or update user data?How does the client read or sync user data efficiently?How does the system acknowledge successful writes or resharding?
Key Decision
Design endpoints: POST /user/{user_id}/data to write/update data routed via shard map; GET /user/{user_id}/data?version= to read with versioning for offline sync; POST /reshard/ack to confirm resharding completion; reject generic CRUD without shard awareness causing routing errors.
Interviewer Expectation
Mid: Lists basic CRUD endpoints. Senior: Details shard-aware endpoints with versioning for offline sync and resharding acknowledgments.
⚠️Common Wrong Answer
Designing APIs without shard-awareness causing clients to send requests to wrong shards and increasing latency.
🔌
API Design Challenge
Sketch 3 core API endpoints to interact with the sharded database system.
Hints
  • How does the client write or update user data?
  • How does the client read or sync user data efficiently?
  • How does the system acknowledge successful writes or resharding?
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Consistent hashing with user_id shard key for balanced load
  • Directory-based sharding for hotspot mitigation
  • TLS and disk encryption for data security
  • Online resharding with virtual nodes and metadata service
  • Shard-aware API design with versioning
Good to Have - 30%
  • Use of Apache Zookeeper for metadata and coordination
  • Client-side shard map caching and refresh
  • Replication strategies for high availability
Bonus - 10%
  • Detailed failure mode analysis of resharding process
  • Trade-offs between encryption approaches with latency impact
Anti-patterns to Avoid
Range sharding causing hotspot nodes and latency spikes under skewed user distribution, leading to overloaded shards and degraded performance
Ignoring encryption at rest exposing data to disk compromise and potential data breaches
Static shard assignments requiring offline migrations causing service downtime and user impact
APIs without shard awareness causing routing errors and increased latency due to requests sent to wrong shards
Relying solely on hash sharding without hotspot mitigation leading to overloaded nodes and degraded P99 latency
Application-level encryption causing high latency and operational complexity, impacting system performance
✅
Model Answer
▼ Reveal

Use consistent hashing on user_id with virtual nodes and a Zookeeper-based directory service to handle hotspots and enable online resharding. Encrypt data in transit with TLS 1.3 and at rest using AWS KMS-managed disk encryption on Cassandra nodes. Design shard-aware APIs with versioning to support offline sync and acknowledgments.

Key Decisions
  • Adopt consistent hashing with MurmurHash on user_id to evenly distribute load and simplify resharding
  • Use directory-based sharding with Zookeeper to track and replicate hot keys dynamically
  • Encrypt all data in transit using TLS 1.3 and at rest using AWS KMS-managed disk encryption on storage nodes
  • Implement virtual nodes in consistent hashing ring to enable smooth online resharding with zero downtime
  • Design shard-aware APIs with versioning parameters to support offline data sync and resharding acknowledgments
  • Consistent hashing with MurmurHash on user_id for balanced shard distribution and easy resharding
  • Directory-based sharding using Apache Zookeeper metadata service to track and replicate hot keys
  • TLS 1.3 for all network communication and AWS KMS-managed disk encryption on Cassandra nodes
  • Virtual nodes in consistent hashing ring to enable smooth online resharding with zero downtime
  • Shard-aware client routing using metadata service to fetch current shard map
  • API endpoints designed with shard key awareness and versioning for offline data sync
  • Reject range sharding due to skewed user ID distribution causing hotspots and uneven load
  • Reject application-level encryption due to high latency and complexity at scale

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. For detecting anomalies in high-volume metric streams with low latency, which architecture is better suited and why?
medium
A. Batch processing with hourly aggregation to reduce noise and improve accuracy
B. Polling external ML service every 10 minutes to classify anomalies asynchronously
C. Streaming anomaly detection using windowed statistical models for near real-time alerts
D. Threshold-based alerts combined with manual tuning to approximate anomalies

Solution

  1. Step 1: Analyze latency and volume constraints

    High-volume streams require low-latency detection to be actionable.

  2. Step 2: Match architecture to constraints

    Streaming anomaly detection with windowed models processes data continuously, enabling near real-time alerts, unlike batch or polling which add latency.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Streaming windowed models -> low latency anomaly detection [check]
Hint: High volume + low latency -> streaming anomaly detection [check]
Common Mistakes:
3. If the reconciliation service that compares debit and credit entries is temporarily down, what is the immediate failure mode observed in the digital wallet system?
medium
A. The system marks transactions as pending and delays final confirmation to users until reconciliation completes
B. New transactions are blocked until reconciliation service recovers to prevent ledger divergence
C. Transactions continue normally but inconsistencies accumulate silently until reconciliation resumes
D. Debit entries are committed immediately but credit entries are delayed, causing temporary imbalance

Solution

  1. Step 1: Understand reconciliation service role

    It ensures debit and credit entries match before confirming transactions to users.

  2. Step 2: Analyze failure impact

    Blocking all transactions (B) reduces availability unnecessarily; silent accumulation (A) risks unnoticed errors; committing debit only (D) breaks double-entry. Marking transactions pending (C) delays confirmation but preserves consistency.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Pending status delays confirmation -> preserves ledger integrity [check]
Hint: Pending transactions delay confirmation, not silent failure [OK]
Common Mistakes:
4. For a distributed cache with frequent node additions and removals, which approach best balances load and minimizes key remapping?
medium
A. Use rendezvous hashing to assign keys to nodes
B. Use a modulo hash on node count with manual rebalancing
C. Use consistent hashing with virtual nodes to smooth load distribution
D. Use a centralized directory to track key-node mappings

Solution

  1. Step 1: Compare consistent hashing and rendezvous hashing

    Both minimize remapping, but consistent hashing with virtual nodes better smooths load across nodes, especially with frequent changes.

  2. Step 2: Evaluate centralized directory and modulo hashing

    Centralized directory adds latency and single point of failure; modulo hashing causes massive remapping and manual rebalancing overhead.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Virtual nodes in consistent hashing smooth load and minimize remapping [check]
Hint: Virtual nodes smooth load in consistent hashing [check]
Common Mistakes:
5. If the Ticket Server crashes after allocating an ID block but before the client acknowledges, what is the exact failure observed in the system?
medium
A. Clients receive duplicate IDs because the block is reissued without tracking
B. Some ID blocks are lost, causing gaps in the global ID sequence but no duplicates
C. Clients block indefinitely waiting for the Ticket Server response, halting ID generation
D. Clients generate IDs locally without coordination, risking collisions

Solution

  1. Step 1: Understand Ticket Server crash impact

    If the server crashes post-allocation but pre-acknowledgment, it cannot confirm the block was assigned.

  2. Step 2: Trace ID block state

    The allocated block is effectively lost, causing gaps in the global ID sequence, but clients do not reuse lost blocks, preventing duplicates.

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Crash after allocation -> lost ID blocks, no duplicates [check]
Hint: Crash post-allocation loses blocks, no duplicate IDs generated [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