Shard key selection in HLD - System Design Exercise

Design: Shard Key Selection for Distributed Database

Design focuses on selecting an optimal shard key and its impact on data distribution, query efficiency, and scalability. It excludes detailed shard rebalancing algorithms and physical hardware setup.

Functional Requirements

FR1: Distribute data evenly across multiple database shards

FR2: Support efficient query routing to minimize cross-shard queries

FR3: Maintain high availability and fault tolerance

FR4: Allow scalability to handle up to 1 billion records

FR5: Support common query patterns such as point lookups and range queries

Non-Functional Requirements

NFR1: Shard key must minimize data skew and hotspots

NFR2: Latency for queries should be under 200ms p99

NFR3: System should tolerate shard failures without data loss

NFR4: Shard key selection should not require frequent re-sharding

NFR5: Support strong consistency within a shard

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Shard key selection logic

Routing layer to direct queries to correct shard

Shard metadata service to track shard locations

Data partitioning and replication mechanisms

Monitoring and alerting for shard health and load

Design Patterns

Range-based sharding

Hash-based sharding

Directory-based sharding

Composite shard keys

Consistent hashing

Reference Architecture

Client
  |
  v
Query Router (Shard Key Extractor)
  |
  v
+-------------------+     +-------------------+     +-------------------+
|    Shard 1        |     |    Shard 2        | ... |    Shard N        |
| (Data Partition 1)|     | (Data Partition 2)|     | (Data Partition N)|
+-------------------+     +-------------------+     +-------------------+

Components

Query Router

Custom routing service

Extract shard key from queries and route requests to the correct shard

Shard Metadata Service

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

Maintain mapping of shard keys to shard locations

Database Shards

Distributed database instances (e.g., MongoDB, Cassandra)

Store partitioned data based on shard key

Shard Key Selection Logic

Application logic or middleware

Determine optimal shard key based on data and query patterns

Request Flow

1. Client sends a query with a shard key field.

2. Query Router extracts the shard key from the query.

3. Router consults Shard Metadata Service to find the shard responsible for the key.

4. Router forwards the query to the appropriate database shard.

5. Shard processes the query and returns the result to the router.

6. Router sends the response back to the client.

Database Schema

Entities: - User (user_id PK, name, email, region) - Orders (order_id PK, user_id FK, product_id, timestamp) Relationships: - User to Orders: 1:N Shard Key Candidates: - user_id (hash-based sharding for even distribution) - region (range-based sharding for locality) Chosen Shard Key: - Composite key of (region, user_id) to balance locality and distribution

Scaling Discussion

Bottlenecks

Uneven data distribution causing hotspots on certain shards

Cross-shard queries increasing latency and complexity

Shard metadata service becoming a single point of failure

Re-sharding complexity when scaling beyond initial shard count

Solutions

Use consistent hashing or composite shard keys to balance load

Design queries to minimize cross-shard operations or use scatter-gather with caching

Deploy shard metadata service in a highly available cluster with leader election

Implement online re-sharding with minimal downtime and data migration tools

Interview Tips

Time: Spend 10 minutes understanding requirements and clarifying queries, 20 minutes designing shard key selection and architecture, 10 minutes discussing scaling and trade-offs, 5 minutes summarizing.

Explain importance of shard key in data distribution and query efficiency

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

Highlight how shard key affects cross-shard queries and latency

Mention strategies to handle hotspots and re-sharding

Show awareness of fault tolerance and metadata management

Practice

1. What is the main purpose of selecting a shard key in a distributed database system?

easy

A. To compress data to save storage space

B. To encrypt data for security purposes

C. To backup data automatically

D. To split data across servers for better load distribution and faster access

Solution

1. Step 1: Understand shard key role

   The shard key determines how data is divided across multiple servers or shards.

2. Step 2: Identify main benefit

   Splitting data helps balance load and speeds up data retrieval by parallelizing queries.

3. Final Answer:

   To split data across servers for better load distribution and faster access -> Option D

4. Quick Check:

   Shard key purpose = split data load [OK]

Hint: Shard key splits data to spread load and speed up access [OK]

Common Mistakes:

• Confusing shard key with encryption key
• Thinking shard key compresses data
• Assuming shard key is for backup

2. Which of the following is a good characteristic of a shard key?

easy

A. Has very few unique values

B. Has many unique values and distributes data evenly

C. Is always a timestamp

D. Is a large text field

Solution

1. Step 1: Identify shard key traits

   A good shard key should have many unique values to avoid data concentration.

2. Step 2: Understand distribution importance

   Even distribution prevents hotspots and balances load across shards.

3. Final Answer:

   Has many unique values and distributes data evenly -> Option B

4. Quick Check:

   Good shard key = unique + even distribution [OK]

Hint: Choose shard keys with many unique values and even spread [OK]

Common Mistakes:

• Picking keys with few unique values causing hotspots
• Assuming timestamp is always best shard key
• Using large text fields that slow down indexing

3. Consider a user database sharded by country_code which has only 5 unique values. What is the likely problem with this shard key?

medium

A. Data will be evenly distributed across shards

B. It will encrypt user data automatically

C. Some shards will be overloaded due to uneven data distribution

D. Queries will be faster because of fewer shards

Solution

1. Step 1: Analyze unique values count

   Only 5 unique values means few shards and many users per shard.

2. Step 2: Understand load distribution

   Popular countries will have more users, causing some shards to be overloaded.

3. Final Answer:

   Some shards will be overloaded due to uneven data distribution -> Option C

4. Quick Check:

   Few unique keys = uneven shard load [OK]

Hint: Few unique shard keys cause uneven load and hotspots [OK]

Common Mistakes:

• Assuming fewer shards always improve speed
• Thinking shard key encrypts data
• Ignoring uneven data distribution effects

4. A system uses user_id % 10 as a shard key but notices uneven shard sizes. What is the likely cause?

medium

A. User IDs are not uniformly distributed modulo 10

B. Shard key is too unique

C. Shard key is a string instead of number

D. System is encrypting shard keys

Solution

1. Step 1: Understand modulo shard key

   Modulo operation expects uniform distribution of user IDs.

2. Step 2: Identify distribution problem

   If user IDs cluster in certain ranges, modulo results cluster causing uneven shards.

3. Final Answer:

   User IDs are not uniformly distributed modulo 10 -> Option A

4. Quick Check:

   Non-uniform IDs cause uneven modulo shard keys [OK]

Hint: Modulo shard keys need uniform input distribution [OK]

Common Mistakes:

• Assuming modulo always balances shards
• Confusing shard key type with encryption
• Ignoring data distribution patterns

5. You design a sharded system for an e-commerce app. Users query orders mostly by user_id and order_date. Which shard key choice best supports fast queries and balanced load?

hard

A. Shard by a composite key of user_id and order_date

B. Shard by user_id only

C. Shard by order_date only

D. Shard by a random UUID

Solution

1. Step 1: Match shard key to query patterns

   Users query by both user_id and order_date, so shard key should support both.

2. Step 2: Evaluate shard key options

   Sharding by user_id alone may cause hotspots; order_date alone may cause uneven load by time.

3. Step 3: Use composite key benefits

   Composite key balances load and supports queries filtering by either field efficiently.

4. Final Answer:

   Shard by a composite key of user_id and order_date -> Option A

5. Quick Check:

   Composite shard key matches queries and balances load [OK]

Hint: Composite keys balance load and match query patterns best [OK]

Common Mistakes:

• Choosing single field shard keys ignoring query patterns
• Using random UUID causing inefficient queries
• Ignoring load balancing in shard key choice