11_Database_Sharding_And_Partitioning

Difficulty: Intermediate
Generated on: 2025-07-13 02:52:36
Category: System Design Cheatsheet

---

Database Sharding and Partitioning Cheatsheet (Intermediate)

1. Core Concept

What is it? Database sharding (horizontal partitioning) and partitioning (both horizontal and vertical) are techniques for breaking up a large database into smaller, more manageable pieces. This distributes the load across multiple servers (shards) or tables, improving performance, scalability, and manageability.

Why is it important?

• Scalability: Handles increasing data volume and user load.
• Performance: Reduces query latency by searching smaller datasets.
• Availability: Isolates failures to a single shard/partition, improving overall system uptime.
• Manageability: Simplifies backup, recovery, and maintenance operations.

2. Key Principles

• Partitioning Key: A column or set of columns used to determine which shard/partition a row belongs to. The choice of partitioning key is critical and depends heavily on the access patterns of your application.
• Horizontal Partitioning (Sharding): Dividing a table into multiple tables (shards) with the same schema, each containing a subset of the rows.
• Vertical Partitioning: Dividing a table into multiple tables with different columns. Useful for separating frequently accessed columns from less frequently accessed ones or for security reasons.
• Data Locality: Placing related data on the same shard/partition to minimize cross-shard queries.
• Consistency: Ensuring data consistency across shards, especially when updating data across shards.
• Single Point of Failure (SPOF) Mitigation: Sharding can inadvertently create a SPOF if the sharding logic itself is not highly available.
• Rebalancing: Redistributing data across shards when adding/removing shards or when shards become unevenly loaded.

3. Diagrams

Horizontal Partitioning (Sharding):

graph LR
    A[Client] --> B{Sharding Layer};
    B --> C1[Shard 1];
    B --> C2[Shard 2];
    B --> C3[Shard 3];
    C1 --> D1((Data));
    C2 --> D2((Data));
    C3 --> D3((Data));
    style B fill:#f9f,stroke:#333,stroke-width:2px

Vertical Partitioning:

graph LR
    A[Original Table] --> B{Vertical Split};
    B --> C1[Table 1 (Frequent Columns)];
    B --> C2[Table 2 (Infrequent Columns)];
    C1 --> D1((Col 1, Col 2));
    C2 --> D2((Col 3, Col 4));

4. Use Cases

Use Case	Description	Example
High Data Volume	Data grows beyond the capacity of a single server.	E-commerce product catalog, user activity logs.
High Read/Write Load	A single database server cannot handle the request volume.	Social media feeds, online gaming leaderboards.
Geographic Distribution	Data needs to be stored closer to users in different geographic regions.	Content delivery networks (CDNs), global social media platforms.
Compliance Requirements	Data needs to be stored in specific regions to comply with local regulations (e.g., GDPR).	Financial institutions, healthcare providers.
Hot/Cold Data Separation	Some data is accessed frequently (hot data), while other data is accessed infrequently (cold data). Vertical partitioning can separate these.	Archiving old orders in an e-commerce system.
Security Isolation	Sensitive data needs to be separated from less sensitive data.	Storing user profiles separately from financial information.

When to Avoid:

• Small Datasets: The overhead of sharding outweighs the benefits for small datasets.
• Complex Cross-Shard Queries: If your application requires frequent and complex joins across shards, sharding can significantly increase query complexity and latency. Consider denormalization or alternative database technologies (e.g., graph databases).
• Rapidly Changing Schema: Sharding adds complexity to schema changes, as the schema must be consistent across all shards.
• Lack of Expertise: Sharding is a complex undertaking and requires a deep understanding of database administration and application architecture.

5. Trade-offs

Aspect	Sharding (Horizontal)	Partitioning (Vertical)
Complexity	High. Requires careful planning of the partitioning key, data distribution, and query routing. Rebalancing is also complex.	Medium. Relatively simpler to implement than sharding, but requires careful consideration of column grouping.
Scalability	Excellent. Scales horizontally by adding more shards.	Limited. Scales primarily by improving I/O performance through separating column access. Doesn’t directly address data volume.
Performance	Improved query performance for queries that target a single shard. Cross-shard queries can be slow and complex.	Improved performance for queries that only access a subset of columns. Can reduce I/O overhead.
Data Locality	Can be optimized by choosing a partitioning key that groups related data together.	Not directly related to data locality.
Consistency	Maintaining consistency across shards can be challenging, especially for write operations. Requires careful consideration of transaction management and conflict resolution.	Simpler consistency management within a single database instance.
Recovery	Recovery from shard failures can be complex and time-consuming. Requires robust backup and restore procedures.	Simpler recovery procedures within a single database instance.
Query Routing	Requires a mechanism to route queries to the appropriate shard (e.g., sharding layer, consistent hashing).	No query routing required.
Resharding	Resharding (redistributing data across shards) is a complex and potentially disruptive operation.	Not applicable.

6. Scalability & Performance

• Horizontal Scalability (Sharding): Adding more shards increases the overall capacity of the database. Theoretically scales linearly if the load is evenly distributed across shards.
• Vertical Scalability: Improving the hardware resources (CPU, memory, storage) of each shard.
• Read Performance: Sharding improves read performance by reducing the amount of data that needs to be scanned for each query if the query can be routed to a single shard.
• Write Performance: Sharding can improve write performance by distributing write operations across multiple shards. However, cross-shard transactions can significantly reduce write performance.
• Network Latency: Cross-shard queries can be affected by network latency between shards. Minimize cross-shard queries whenever possible.
• Hot Spots: Uneven data distribution can lead to “hot spots” on certain shards, negating the benefits of sharding. Choose a partitioning key that distributes data evenly.
• Caching: Caching frequently accessed data can further improve performance, especially for read-heavy workloads.

7. Real-world Examples

• Facebook: Shards its user database based on user ID. Also uses vertical partitioning to separate frequently accessed user profile data from less frequently accessed data.
• Twitter: Uses a combination of horizontal and vertical partitioning to handle its massive tweet volume. Tweets are sharded based on user ID and time.
• YouTube: Shards its video database based on video ID.
• Netflix: Uses sharding for its user account data and content catalog.
• Amazon: Uses sharding for its product catalog and order management systems.

8. Interview Questions

• What is database sharding, and why is it used?
• What are the different types of partitioning?
• What are the trade-offs of using sharding?
• How do you choose a partitioning key? What makes a good partitioning key?
• How do you handle cross-shard queries?
• How do you rebalance shards?
• How do you ensure data consistency across shards?
• What are the challenges of sharding?
• Describe a sharding strategy for a specific application (e.g., a social media platform, an e-commerce website).
• How would you design a system to route queries to the correct shard?
• How do you monitor and maintain a sharded database?
• What are the alternatives to sharding? (e.g., read replicas, caching, different database technologies).
• How does sharding affect ACID properties? How can you maintain ACID properties in a sharded environment?
• What are the differences between consistent hashing and range-based partitioning? What are the pros and cons of each?
• How would you handle a situation where one shard becomes a hot spot?
• How can you minimize downtime during resharding?
• Explain the CAP theorem and how it relates to sharding.
• Discuss the importance of data locality in a sharded system.
• How does sharding interact with other database technologies like replication?

This cheatsheet provides a comprehensive overview of database sharding and partitioning. Remember to consider the specific requirements of your application when choosing a sharding strategy. Good luck!