Database sharding strategies in HLD - System Design Exercise

Design: Database Sharding Strategies

Design focuses on sharding strategies and architecture for relational or NoSQL databases. Out of scope: detailed application logic, specific database vendor features, and network infrastructure.

Functional Requirements

FR1: Distribute data across multiple database instances to improve scalability

FR2: Support horizontal scaling to handle increasing data volume and traffic

FR3: Ensure data availability and fault tolerance

FR4: Maintain reasonable query latency (p99 < 200ms)

FR5: Support both read and write operations efficiently

FR6: Allow easy addition of new shards without downtime

Non-Functional Requirements

NFR1: Handle up to 1 billion records distributed across shards

NFR2: Support 10,000 concurrent read/write requests

NFR3: Availability target of 99.9% uptime

NFR4: Latency target: p99 API response time under 200ms

NFR5: Data consistency can be eventual for some use cases but must support strong consistency for critical data

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

Shard key selection mechanism

Shard mapping and routing layer

Database instances or clusters for each shard

Metadata service to track shard locations

Load balancer or proxy for query routing

Backup and recovery tools for shards

Design Patterns

Horizontal partitioning (range-based, hash-based, directory-based)

Consistent hashing

Lookup tables for shard mapping

Replication strategies per shard

Re-sharding and data migration approaches

Reference Architecture

Client
  |
  v
Shard Router / Proxy Layer
  |
  +-----------------------------+
  |                             |
Shard 1                     Shard 2 ... Shard N
(Database Instance)         (Database Instance)

Metadata Service tracks shard keys and locations

Backup & Monitoring systems connected to each shard

Components

Shard Router / Proxy Layer

Custom routing service or middleware

Routes client queries to the correct shard based on shard key

Database Shards

Relational DB (e.g., PostgreSQL) or NoSQL DB (e.g., MongoDB)

Store partitioned data subsets independently

Metadata Service

Distributed key-value store or config service (e.g., ZooKeeper, etcd)

Maintain shard key ranges and mapping info

Backup and Monitoring

Backup tools and monitoring dashboards

Ensure data durability and system health

Request Flow

1. Client sends request with data or query including shard key

2. Shard Router extracts shard key and consults Metadata Service

3. Router forwards request to the appropriate shard database instance

4. Shard processes query and returns result to Router

5. Router sends response back to client

6. Metadata Service updates if shards are added or re-sharded

Database Schema

Entities are partitioned by shard key. Each shard holds a subset of data with the same schema. Relationships that span shards require application-level joins or denormalization. Metadata Service stores shard key ranges or hash mappings.

Scaling Discussion

Bottlenecks

Shard Router becomes a single point of failure or bottleneck

Uneven data distribution causing hotspot shards

Cross-shard queries causing high latency

Complexity in re-sharding and data migration

Metadata Service availability impacting routing

Solutions

Use multiple router instances with load balancing and failover

Choose shard keys carefully or use consistent hashing to balance load

Design queries to minimize cross-shard operations or use caching

Implement online re-sharding with minimal downtime and data sync

Deploy Metadata Service in a highly available cluster with consensus

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing the sharding strategy and architecture, 10 minutes discussing scaling and trade-offs, and 5 minutes summarizing.

Explain importance of shard key selection and its impact on load balancing

Discuss trade-offs between range-based and hash-based sharding

Highlight how routing and metadata services work together

Address how to handle cross-shard queries and consistency

Show awareness of operational challenges like re-sharding and monitoring

Practice

1. Which of the following best describes database sharding?

easy

A. Backing up the entire database to multiple locations for safety.

B. Splitting a large database into smaller, faster, more manageable parts called shards.

C. Encrypting the database to protect sensitive data.

D. Merging multiple databases into one large database.

Solution

1. Step 1: Understand the concept of sharding

   Sharding means dividing a database into smaller parts to improve speed and manageability.

2. Step 2: Compare options with the definition

   Only Splitting a large database into smaller, faster, more manageable parts called shards. describes splitting into smaller parts called shards, which matches the definition.

3. Final Answer:

   Splitting a large database into smaller, faster, more manageable parts called shards. -> Option B

4. Quick Check:

   Sharding = splitting database [OK]

Hint: Sharding means splitting data into parts [OK]

Common Mistakes:

• Confusing sharding with backup or encryption
• Thinking sharding merges databases
• Assuming sharding is only about security

2. Which of the following is a valid shard key choice for hash-based sharding?

easy

A. User ID hashed to assign shard

B. Timestamp of record creation

C. Database server IP address

D. Number of active connections

Solution

1. Step 1: Identify shard key for hash sharding

   Hash sharding uses a hash function on a key like User ID to distribute data evenly.

2. Step 2: Evaluate options

   User ID is a stable, unique key suitable for hashing. Timestamp or server IP are not good shard keys for hashing.

3. Final Answer:

   User ID hashed to assign shard -> Option A

4. Quick Check:

   Hash shard key = User ID [OK]

Hint: Hash shard keys are stable unique IDs [OK]

Common Mistakes:

• Using timestamps which cause uneven shard distribution
• Choosing server IP which is unrelated to data
• Picking dynamic values like active connections

3. Given a range-based sharding on user age groups: shard 1 for ages 0-20, shard 2 for 21-40, shard 3 for 41-60. Which shard will a user aged 35 be stored in?

medium

A. Shard 3

B. Shard 1

C. Shard 2

D. None of the above

Solution

1. Step 1: Understand the age ranges for each shard

   Shard 1: 0-20, Shard 2: 21-40, Shard 3: 41-60.

2. Step 2: Determine which range 35 falls into

   Age 35 is between 21 and 40, so it belongs to Shard 2.

3. Final Answer:

   Shard 2 -> Option C

4. Quick Check:

   35 in 21-40 = Shard 2 [OK]

Hint: Check which range the value fits [OK]

Common Mistakes:

• Choosing shard 1 by mistake for age 35
• Confusing shard 3 range
• Selecting 'None of the above' incorrectly

4. A system uses hash-based sharding on user email addresses. Recently, many users with emails starting with 'a' are causing one shard to overload. What is the likely problem?

medium

A. The hash function is not distributing keys evenly.

B. Emails starting with 'a' are stored in a separate shard by design.

C. Range sharding was used instead of hash sharding.

D. The shard key is not unique.

Solution

1. Step 1: Analyze the shard overload cause

   Hash-based sharding should distribute keys evenly. Overload on one shard means uneven distribution.

2. Step 2: Evaluate options

   The hash function is not distributing keys evenly. explains uneven hash distribution. Emails starting with 'a' are stored in a separate shard by design. is incorrect because hash sharding doesn't group by prefix. Range sharding was used instead of hash sharding. is wrong as range sharding is not used. The shard key is not unique. is unrelated to overload.

3. Final Answer:

   The hash function is not distributing keys evenly. -> Option A

4. Quick Check:

   Uneven hash distribution = overload [OK]

Hint: Uneven load means bad hash distribution [OK]

Common Mistakes:

• Assuming range sharding was used
• Thinking shard key uniqueness causes overload
• Believing emails with same prefix go to same shard by hash

5. You need to shard a global user database to minimize latency and balance load. Which strategy is best to combine geographic location and user ID for sharding?

hard

A. Use range sharding on user ID across all regions.

B. Use only hash sharding on user ID ignoring location.

C. Use directory sharding mapping user ID to random shards.

D. Use geographic sharding first, then hash shard within each region by user ID.

Solution

1. Step 1: Understand the goal

   Minimize latency by serving users from nearby data centers and balance load within each region.

2. Step 2: Evaluate sharding strategies

   Geographic sharding groups users by location to reduce latency. Hash sharding inside each region balances load evenly.

3. Step 3: Compare options

   Use geographic sharding first, then hash shard within each region by user ID. combines geographic and hash sharding effectively. Use only hash sharding on user ID ignoring location. ignores location, increasing latency. Use range sharding on user ID across all regions. uses range sharding which may cause hotspots. Use directory sharding mapping user ID to random shards. uses random mapping, ignoring location and load balance.

4. Final Answer:

   Use geographic sharding first, then hash shard within each region by user ID. -> Option D

5. Quick Check:

   Geo + hash sharding = low latency + balanced load [OK]

Hint: Combine geo then hash for best latency and balance [OK]

Common Mistakes:

• Ignoring geographic location causing high latency
• Using only hash sharding causing uneven latency
• Using range sharding causing load hotspots