TS-43: Relational Databases and SQL
This technical standard covers general best practices for working with relational databases and writing SQL. This is not specific to any particular database engine, although some specific guidance for PostgreSQL, MySQL, and others may be given along the way.
Representation is the essence of programming.
– Fred Brooks
Sharding
This section sets out guidelines for the planning, design, and maintenance of sharded databases.
What is sharding?
In large-scale applications, as data and traffic grows, the database can become a bottleneck – in terms of either storage capacity or performance, or both.
Sharding is a database architecture pattern that helps to maintain high performance at scale. This is done by spreading both data and load across multiple databases running on multiple servers.
Database sharding is a horizontal scaling technique. Data is partitioned into "shards", each of which is responsible for a specific subset of the overall data. Each shard is stored on a separate database, running on a dedicated server or cluster. As data and traffic grow, additional shards are added with the aim of further increasing the distribution of both data and load. (This is in contrast to vertical scaling techniques, which involve increasing the capacity of a single server, or reducing the load on it by introducing caching layers between the database and application.)
Sharding is particularly beneficial in applications with very large (and indefinitely growing) datasets, and systems with high transaction volumes. It can also be useful where there is a requirement to distribute data geographically, for example for the purpose of regulatory compliance.
Types of sharding
The two main approaches to sharding are called horizontal and vertical sharding.
Horizontal sharding, also known as range-based sharding, involves partitioning data by rows. Each shard stores a range of rows, usually based on a range of values in a specific column (the "shard key").
Shard | Range |
|---|---|
Shard 1 | Rows with IDs between 1 and 1,000,000 |
Shard 2 | Rows with IDs between 1,000,001 and 2,000,000 |
Shard 3 | Rows with IDs between 2,000,001 and 3,000,000 |
In vertical sharding, tables are partitioned by columns, where each shard contains a subset of columns for each row.
Shard | Columns |
|---|---|
Shard 1 | Columns A, B, C |
Shard 2 | Columns D, E, F |
Shard 3 | Columns G, H, I |
A sharding strategy may combine elements of both horizontal and vertical sharding techniques, known as a hybrid approach.
Shard keys
For horizontal sharding, the shard key is a column, or set of columns, used to determine which shards individual records belong to.
Shard keys may be:
- Range-based: This is the simplest and most common type of shard key. It requires values that have a natural order, such as dates or timestamps, or numerical auto-incrementing IDs.
- Hash-based: Hash keys are created by applying a hash function to the values of one or more columns.
- Composite: Shard keys are composed from the values of multiple columns.
Shard routing
When an application needs to query a sharded database, it must first determine which shard to connect to. In horizontal sharding, the lookup is determined by the shard key. In vertical sharding, the lookup is based on the data types being queried.
The process of resolving a query to a shard is called shard routing. Implementation strategies include:
- Application-level routing: The logic for determining which shard to query is built directly into the application code.
- Middleware and proxy-based routing: An intermediary layer between the application and database is used to handle the shard routing.
- Database-level routing: The database itself handles the routing of queries to the appropriate shards. This approach is common in database management systems that natively support sharding.
Designing a sharding strategy
Sharding strategies should be designed with consideration of the data types and access patterns of the application. Consideration also needs to be give to how best to manage data consistency, how to achieve efficient and correct query routing, and how to maintain balanced shards (ie. have an even distribution of data and load across shards).
Horizontal sharding has the greatest scalability potential. You can just keep adding more and more shards as the data grows. There is also greater scope for automating the creation of new shards, as data reaches predefined thresholds.
By contrast, the scope for vertical sharding is limited to the data types of the system, and the shards tend to be static. Vertical sharding is most beneficial in systems where data can be grouped in a way that queries rarely (or never) require joins between groups. Since queries to discrete data groups will get routed to specific infrastructure, you have the opportunity to optimize individual shards for the unique access patterns of their data. Some shards may be optimized for read-heavy queries, others for write-heavy queries, for example.
Horizontal and vertical sharding may be combined into a hybrid approach, attempting to leverage the benefits of both strategies. For example, lesser-accessed data may be separated out (vertically sharded), leaving the most-accessed data for horizontal sharding.
In horizontal sharding, the choice of shard key is critical. The objective is to choose a key that will result in a relatively even distribution of both data and load across all shards. The objective is to have "well-balanced" shards.
Range-based shard keys are often the simplest to implement, but be careful about the potential for data skew (where some shards store much more data than others) and hotspots (where some shards are accessed much more frequently than others). For example, is you shard by an auto-incrementing ID, and access patterns are biased towards the most recent data, then both read and write operations will be concentrated on the most recent shards.
Data access should be relatively uniform across all shards, so that load is evenly distributed across the infrastructure. Shard keys that are based on hashes of the data values tend to result in more evenly distributed data and load than range-based keys.
Shard keys should be chosen with the most common queries in mind. For example, if most queries filter data based on a specific column, such as a user ID, that column will be a strong candidate for the shard key. It will mean that the shard key will be known to the application, and so queries can be routed directly to the correct shard without requiring any intermediary lookups.
Composite keys – made up of the values of multiple columns – add the most complexity but they can also enable more granular control over data distribution, and queries can be optimized for multiple access patterns. But these keys often require custom routing logic, adding latency to query execution.
In vertical sharding, data partitions should align with queries, such that cross-shard joins and transactions are kept to a minimum. Cross-shard operations will negate some of the benefits of sharding, notably performance.
Sharding strategies should plan for data growth and increased traffic in the future. Consider how will new shards be added over time, and how the shard creation process could be automated. Shard keys that naturally support range-based distribution are often good candidates for auto-scaling.
Consider also the accuracy and efficiency of your routing logic. Shard routing should be quick and reliable. Application-level routing allows for customized routing logic, making it easier to optimize for specific use cases. If required, routing logic can be adjusted dynamically based on real-time data. Middleware and proxies can be used to centralize routing logic, extracting this accidental complexity from the application, leaving the application to specialize in the essential complexity of its domain – a neater separation of concerns. Proxies may also be shared by multiple applications that access the same data, and failover mechanisms can be built-in to the proxies, too. But this design introduces latency and the database proxy becomes a new single point of failure – more things to be considered.
Databases with built-in sharding capabilities, such as MongoDB, allow for easy sharding configuration out-of-the-box. The trade-offs with this approach include limited customization and commercial risks associated with greater vendor lock-in.
Think also about the monitoring of shards, and how fallbacks and error handling will work in the event of shard failures. How will the sharding strategy impact your backup and disaster recovery procedures?
Finally, if sharding is combined with replication and denormalization techniques, you will need to plan for how eventual data consistency will be achieved across shards.
In summary, designing a sharding strategy requires careful consideration of an application’s data types and distribution, query patterns, and performance and scalability needs. All sharding strategies involve compromise. All designs will add some level of accidental complexity to a system, and each solution will have its own particular considerations and trade-offs.