Database sharding strategies in HLD - Scalability & System Analysis

Scalability Analysis - Database sharding strategies

Growth Table: Database Sharding Strategies

Users / Data Size	100 Users	10K Users	1M Users	100M Users
Data Volume	Small, fits on single DB	Medium, single DB still possible	Large, single DB slow, storage limits	Very large, single DB impossible
Traffic (QPS)	Low (~10-100 QPS)	Moderate (~1K QPS)	High (~50K QPS)	Very High (~5M QPS)
DB Load	Single instance handles load	Near max capacity, some slow queries	DB CPU/memory bottleneck	DB storage and CPU overwhelmed
Latency	Low latency	Latency starts increasing	Latency high without sharding	Latency very high without sharding
Sharding Need	Not needed	Optional, for growth	Required for performance	Mandatory, complex sharding

First Bottleneck

The database server is the first bottleneck as user count and data grow. It hits CPU, memory, and storage limits. Single-instance databases struggle with high query rates and large data volumes. This causes slow queries and increased latency.

Scaling Solutions for Database Sharding

• Horizontal Sharding: Split data across multiple database servers by a shard key (e.g., user ID range, geographic region). Each shard handles a subset of data and queries.
• Vertical Sharding: Separate tables or features into different databases to reduce load per DB.
• Directory-Based Sharding: Use a lookup service to map keys to shards, allowing flexible shard assignment.
• Consistent Hashing: Distribute data evenly and allow easy addition/removal of shards with minimal data movement.
• Caching: Use in-memory caches (e.g., Redis) to reduce DB reads.
• Read Replicas: Offload read queries to replicas to reduce master DB load.
• Connection Pooling: Efficiently manage DB connections to avoid overload.

Back-of-Envelope Cost Analysis

• At 1M users, expect ~50K QPS. A single DB handles ~5K QPS max, so need ~10 shards.
• Storage per user assumed 1MB -> 1M users = ~1TB data, split across shards.
• Network bandwidth per shard: 5K QPS * 1KB/request ≈ 5MB/s, manageable on 1Gbps links.
• Adding shards increases operational complexity and cost (servers, monitoring).

Interview Tip

Start by explaining the current system limits. Identify the database as the bottleneck. Discuss sharding types and trade-offs. Mention shard key choice importance. Explain how caching and replicas help. Show awareness of operational complexity and data consistency challenges.

Self Check

Your database handles 1000 QPS. Traffic grows 10x to 10,000 QPS. What do you do first?

Answer: Introduce horizontal sharding to split load across multiple database servers. This reduces CPU and memory pressure on each DB instance and maintains low latency.

Key Result

Database sharding becomes essential beyond tens of thousands of users to handle CPU, memory, and storage limits. Horizontal sharding by a good shard key distributes load and data, enabling scalable performance.

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