0% completed
Data Partitioning
On This Page
Horizontal and Vertical Partitioning
Choosing Which Machine Holds a Row
A Good Partition Key
What Becomes Harder
Key Takeaways
One machine can only hold so much data, and it can only handle so many writes. When a table grows past what one machine can serve, you split it across several machines.
Data partitioning is the act of splitting data into parts and putting each part on a different machine. Each part is called a partition or a shard.
The words are used loosely in practice. Partitioning is the general idea. Sharding usually means partitioning across separate machines.
Horizontal and Vertical Partitioning
There are two ways to cut a table, and they solve different problems.
Horizontal partitioning splits the rows. Every part has the same columns and a different set of rows. User 1 to 1,000,000 live on machine A, and user 1,000,001 to 2,000,000 live on machine B. This is what people mean by sharding, and it is the answer when a table has too many rows for one machine.
Vertical partitioning splits the columns. You take one wide table and make two narrower tables, each holding some of the columns for the same entity. The user profile fields go in one table, and the large rarely-read fields such as the biography and settings go in another.
The narrower tables can sit on different machines, but each one still holds a row for every entity. Vertical partitioning therefore does not reduce the number of rows on any machine, so it does not help when a table has too many rows. It helps when a table is wide and most queries need only a few columns.
The rest of this lesson is about horizontal partitioning, because that is the one that carries the hard problems.
Choosing Which Machine Holds a Row
You need a rule that turns a row into a machine. The column that the rule reads is called the partition key, and the rule itself is the partitioning method.
Hash partitioning. Run the key through a hash function and take the result modulo the number of machines. hash(user_id) % 4 gives you a number from 0 to 3. The spread is very even, and that is its main strength.
Its weakness is that the number of machines is inside the rule. Move from 4 machines to 5, and almost every row belongs somewhere new. Consistent Hashing is the fix, because it moves only a small share of the rows when the number of machines changes.
Range partitioning. Give each machine a range of key values. Dates from January on machine A, February on machine B. Range queries are easy, because rows that are near each other in value are on the same machine.
Its weakness is uneven load. If the key is a date, all of today's writes go to one machine while the others hold old data and do nothing.
List partitioning. You write down which values belong to which machine. Norway, Sweden, and Denmark on machine A, Germany and Austria on machine B. It is simple and easy to understand. You have to maintain the list, and the parts are rarely the same size.
Directory based. A separate lookup service holds a table that says where each key lives. You can move any key to any machine and just update the table, which makes rebalancing much easier. The cost is that the lookup service is now on the path of every query, and it must not go down.
Round-robin is sometimes listed here. It puts the first row on the first machine, the second row on the second machine, and so on. The spread is perfect. It is almost never used for databases. No rule connects a key to a machine, so a lookup by key has to ask every machine.
A Good Partition Key
The partition key decides whether this works or not, and it is hard to change later.
A good key has three properties.
Many different values. A key with only three possible values can only ever fill three partitions. A status column is a bad key. A user id is a good one.
Even access. The traffic should be spread across the values, not just the data. A social platform partitioned by user id still has a problem if one account has fifty million followers. That partition is a hot partition: it is overloaded while the others are idle.
Present in most queries. This is the one people forget, and the next section explains why.
What Becomes Harder
Partitioning is not free. Everything below was simple on one machine.
Queries without the partition key. If a query gives the partition key, the system asks one machine. If it does not, the system has to ask every machine and combine the answers. This is called a scatter-gather query, and it becomes slower as you add machines, because it waits for the slowest of them.
Joins. A join between two tables on the same machine is normal work. A join across machines means moving data over the network. Systems often avoid this by storing a copy of the joined data together in one place, which is called a denormalized form. That copy then has to be updated everywhere it is stored.
Foreign keys. Most databases cannot enforce a foreign key across machines. The check has to move into your application code.
Transactions. A change that touches two machines cannot use one simple database transaction. It needs a distributed protocol, and those are slow and complicated.
Rebalancing. When you add a machine, or when one partition becomes too large, data has to move. Doing this while the system is serving traffic is one of the harder operational jobs there is. Consistent hashing and directory based partitioning both exist to make it less painful.
Key Takeaways
- Data partitioning splits data across machines. Each part is a partition, or a shard.
- Horizontal partitioning splits rows and is what people mean by sharding. Vertical partitioning splits columns into narrower tables, and every machine still holds a row for each entity, so it does not reduce the row count anywhere.
- The partition key and the method decide where a row lives. Hash spreads evenly, and range supports range queries but gets hot spots. List is manual, and directory based is flexible with a lookup service to keep alive.
- A good partition key has many values, spreads the traffic, and appears in most queries.
- A query without the partition key has to ask every machine, which is called scatter-gather.
- Joins, foreign keys, and transactions across machines are all much harder after partitioning.
- Adding a machine means moving data. Consistent hashing keeps that movement small.
Partitioning is the point where a system stops being one database with more hardware and becomes a distributed system. Do it when one machine can no longer hold the data or take the writes, and not before.
Piyush Kuhikar
· 3 months ago
Understanding Directory-Based Partitioning
In this explanation, we will break down the concept of directory-based partitioning in a way that’s easy to grasp, including its benefits, drawbacks, and how it fits into the broader context of system design.
What is Partitioning?
Partitioning is the process of dividing a large dataset into smaller, more manageable pieces or partitions. This is often done to improve performance and scalability in systems dealing with vast amounts of data.
Types of Partitioning
- Range-Based Partitioning: Divides data based on ranges of values.
- Hash-Based Partitioning: Distributes data using a hash function, spreading it evenly across partitions.
- Directory-Based Partitioning (Focus of Our Discussion): Uses a directory (lookup table
Sanket Doshi
· 4 months ago
For example, consider an e-commerce website that stores customer data in a database table. The website might partition the customer table vertically based on the type of data, so that personal information such as name and address are stored in one shard, while order history and payment information are stored in another shard. This way, when a customer logs in and their order history needs to be accessed, the query can be directed to the appropriate shard, minimizing the amount of data that needs to be scanned.
This eample for vertical partitioning is wrong.
SOHEL RANA
· 5 months ago
It will be helpful is updation history mentioned in articles, so that user can get if any comments or suggestion has been granted. I think blog is modified based on some suggestion but is not mentioned so when i go through comments feels like already acknowleged.
chosunone
· 7 months ago
Data partitioning is really a late-stage optimization that locks your schema and access patterns a lot. Reaching for this early is an easy way to make poor choices. I think it should be emphasized that data partitioning should come after you have identified stable access patterns and schema.
Marvin Xu
· 4 years ago
For round robin you should mention that the order of data coming in determines which partition it lands in. Otherwise people don't know what "i" means.
Marvin Xu
· 4 years ago
Also hashed based partitioning is incorrect. If you were to use ID then you could end up lopsided if the IDs are heavily weighted to one partition unless IDs are randomly generated. Instead you should always hash the ID so that it's evenly distributed.
Marvin Xu
· 4 years ago
You should mention that vertical partitioning means partition by column
Reading Progress
0%
On This Page
Horizontal and Vertical Partitioning
Choosing Which Machine Holds a Row
A Good Partition Key
What Becomes Harder
Key Takeaways