Sharding in System Design
My raw understanding about sharding
before taking off, we first have to get the motivation on why do we need sharding on the first place. supposed we have a really simple architecture that connecting 3 component which are the client, the server, and the database.
assume for the database we use Postgres RDS from AWS that already do the heavy lifting for us. given time, our software started to grow and scale. hence those large spaces that we have started draining or simply our software demand more than the database could provide. it could be the need to write 20k WPS or simply our total storage are approaching the 70TB. simply looking at this we already know it seems to hit the ceiling that we have.
the storage and write-rate numbers here are assumptions for this example, not official limits or performance guarantees for Amazon RDS. the actual ceiling depends on our instance, storage configuration, and workload.
if u understand a little bit about how to scale software, sure thing our first instinct that are kicking are to do vertical scaling on our software. simply by upgrading our database storage on the chosen provider or, if we manage the hardware ourselves, upgrading our hardware.
vertical scaling offers a simple way out for our case. be that as it may, with the passage of time, also in additional for the sake of our argument, our software scale globally and our necessity are slowly approaching a limit again. even though we already do the scaling. by then just upgrading is not enough to support the necessity that we have to provide.
therefore, we have to come up with a more creative solution which in this blog are gonna be Sharding. by the definition itself, sharding is a way to scale horizontally by splitting a single database into smaller subsets called shards, and distributing them across multiple independent database servers. [ 1 ]
but looking at the architecture of our database right now, multiple constraints and problems came up at the same time that did not exist before. such as how do we choose how to shard? how do we know which shard is gonna be the target of our queries? what happens if we have a particularly hot shard? and what about if one shard goes down, or we need to rebalance the data? these are other problems that we have to deal with when we get involved with sharding.
therefore we also have to tackle the new problems that we have. the placement decisions generally fall under 2 categories:
- How do we group our data
- How do we distribute the data
How we choosing a shard key
the first question that we have to tackle right away is how do we decide what our shard key could be in the first place. what column are you sharding on and why?
a good shard key should at least consider these 3 properties: good cardinality, even distribution, and alignment with queries. [ 2 ]
these 3 properties give us a good starting point for choosing our shard key. starting with high cardinality, we wanna have enough distinct values so we have room to divide the data. but high cardinality by itself does not guarantee a random or even distribution.
with that being said, this leads us to the second property, even distribution. we wanna make sure that the data inside each shard are spread out so each shard has roughly the same amount of data. and the last, we also wanna make sure that our shard key aligns with how we query our data.
there are many ways to choose the shard key such as user_id or order_id. we could even consider a boolean flag like is_premium, but with only two possible values it would usually be a poor standalone key for distributing data across many shards. back again, how we choose the key depends on the characteristics of our queries to the database.
once we choose the key, there are a few methods that we can use to distribute the data.
Range-Based Sharding
the name is quite self explanatory in this one where we take a specific range and divide our database according to that range. if we decide to have user_id as our key with ranges of 10 million, we will have sharding that uses these ranges: 0–10M, 10M–20M, and up to 30M–40M. each upper boundary is excluded so the ranges do not overlap.
while this method could give us an even amount of stored data, that alone does not tell us how the requests are distributed. the concrete example is supposed our software has been growing recently, where the number of users started to spike more than a couple of years before. also given the condition where the majority of active users are new users.
with that condition, much of the traffic in our software will eventually fall into the latest shard that we created, making the distribution of queries uneven. a range can be useful for queries that access nearby keys, but a growing key can also concentrate new writes on one shard. [ 1 , 2 ]
Hash-Based Sharding
in this method, instead of assigning a fixed range for our database, we hash the key and then mod it by the number of shards that we have.
by using a suitable hash function, we can basically scramble the input and spread the keys across our multiple shards. just like the first one, this method also has its own trade-off that we have to deal with.
remember that we always have to mod it by the number of shards that we have. suppose the number grows by 1. in this example, our divisor is gonna increase from 3 to 4. intuitively, there will be many records that get assigned to a different shard.
suppose we have a key of 1234 and with our example hash function, hash(1234) equals 16. previously this data falls into shard 2 since 16 modulo 3 gives us 1. we are using zero-based indexes, so index 1 means shard 2. but right now as the number of shards grows, we mod it by 4, resulting in 0, which means shard 1.
therefore this particular record needs to move, and many other records can also get reshuffled as the number of shards changes. changing the formula does not move the records for us; we still need a migration process. [ 1 ]
Hash-Based Sharding with consistent hashing
to reduce the amount of data that gets reshuffled across multiple shards, there is another method called consistent hashing. it is one approach to distributing keys when the number of servers changes, but it is not something that every sharded database necessarily uses. [ 3 ]
the idea is simply to have our database servers and our keys mapped into the same circular space that we call a hash ring. whenever we wanna know where a particular record should be stored, we hash the key, find its position on the ring, then move clockwise until we meet the first database server. that server is gonna be responsible for the data.
suppose we add another server into the ring. instead of changing the destination for a large portion of the keys like what happened with our previous modulo implementation, only the keys in the interval now assigned to the new server need to move. the remaining data can stay in their existing places.
therefore, this method helps us minimize the amount of data that needs to be reshuffled when the number of servers changes. be that as it may, minimizing does not mean eliminating. we still have to move the affected data and make sure our application knows where to find it during the process.
there is also an additional concept called virtual nodes where each physical server can occupy multiple positions on the ring. this helps us distribute the data more evenly instead of depending on a single position for each server. we are not gonna go too deep into it here, but the Dynamo paper gives a more detailed explanation. [ 3 ]
Directory-Based Sharding
another method that we can use is directory-based sharding. instead of calculating the destination using a range or hash function, we have a lookup table that tells us where a particular record belongs.
suppose user 1234 belongs to shard 1, while user 5678 belongs to shard 3. before sending the query, our application checks the directory first, then forwards the request to the corresponding shard.
the advantage of this method is the flexibility that we have over the placement of our data. if we wanna move a particular user into another shard, we can move their data and update the mapping accordingly.
but looking at the architecture right now, we also introduce another dependency. our application needs the directory to be available and accurate so it can find the correct shard. therefore, the flexibility comes with additional work to maintain the directory itself. [ 1 ]
The challenges of sharding
by now we already have several ways to distribute our data. but remember the problems that came up when we first split our database? choosing the key and distribution method does not automatically solve all of them.
Hot Shards
suppose we already use user_id as our shard key and distribute the users evenly using hashing. each shard has roughly the same number of users, and everything seems fine.
but given the condition where one of our users is a celebrity that receives a massive amount of traffic, the shard that stores their data is gonna receive much more requests compared to the others.
this is where having an even distribution of data does not necessarily mean having an even distribution of workload. a shard with fewer records could still be the busiest one if those records are frequently accessed.
and simply hashing the user_id does not solve this particular problem. the celebrity still has the same user_id, therefore the requests for that key will keep going into the same shard.
to deal with this, we have to look at what kind of traffic is causing the problem. if the majority are repeated reads, caching or read replicas could help reduce the pressure. but if the problem comes from writes, we might need to reconsider how that particular user's data is divided.
therefore, even after choosing a good shard key, we still have to monitor the actual workload. distributing the keys evenly is one thing, distributing the requests evenly is another. [ 1 , 2 ]
Cross-Shard Queries
another problem occurs when the data that we need are spread across multiple shards.
suppose we have an e-commerce application and we choose order_id as our shard key. whenever we wanna retrieve a particular order, we can use the order_id to find its corresponding shard.
but what happens when a user wants to see their entire order history? since each order has a different order_id, their orders could be distributed across multiple shards. therefore, instead of querying one database, we have to collect the results from several shards and combine them before returning the response.
looking at this example, we can see again why our shard key needs to align with the behaviour of our queries. if retrieving a user's order history is one of the most frequent operations in our application, then choosing user_id could help us keep those orders together.
be that as it may, this also changes what information we need to locate an order. if we only have the order_id, we might need an additional lookup to find which user and shard it belongs to.
therefore, choosing the key always comes back to how our application accesses the data. we wanna make sure that the operations happening most frequently do not require unnecessary communication across multiple servers. [ 1 ]
Transactions Across Shards
the next problem appears when we need to update data that live in different shards.
suppose user A wants to transfer some balance to user B. when both accounts are stored inside one database, we can wrap the deduction and addition inside a single transaction. either both changes succeed or neither of them happens.
but right now user A lives in shard 1 while user B lives in shard 2. suppose we successfully deduct the balance from user A, but shard 2 becomes unavailable before we can add the balance to user B. now we have one operation that succeeds while the other fails.
each database can still provide transactions for its own data. the difficulty is making those separate transactions behave as one operation across multiple databases.
there are mechanisms such as two-phase commit that allow us to coordinate this, but they also introduce additional coordination and failure handling. therefore, we cannot assume that a transaction across multiple shards is gonna be as straightforward as the transaction that we previously had inside one database. [ 4 ]
this gives us another reason to keep related data together whenever possible. if several records frequently need to be updated inside the same transaction, their placement should also become part of our consideration when choosing the shard key.
When a shard goes down
there is also something that we have to distinguish when talking about a server going down. knowing where the data should go does not mean the data already exists in that destination.
suppose one shard becomes unavailable. even if our distribution method points the affected keys into another server, that server cannot return the records unless it already has a copy of them.
therefore, sharding itself does not replace replication. sharding helps us divide the data across multiple servers, while replication gives us additional copies that can be used when a server fails. we still need a recovery mechanism to make those copies available to our application. [ 3 ]
Conclusion
looking back at the simple architecture that we started with, sharding gives us a way to scale beyond the capacity of a single database. be that as it may, we also introduce multiple problems that previously did not exist when all of our data lived inside one database.
therefore, before deciding to shard, we first have to understand what limitation our software is actually approaching. from there, we can choose what key we wanna shard on and how we distribute the data according to the characteristics of our queries.
throughout the discussion, we also see that having an even amount of data across the shards does not necessarily mean having an even workload. we still have to consider which data are frequently accessed, which records need to stay together, and how our software handles a shard becoming unavailable.
with that being said, sharding offers a way out for the capacity problem that we have. but choosing how to split the database will always come back to understanding how our software uses the data in the first place.