Databases · Lesson 6.1
When a table outgrows one machine
So for the Forbes rush, Simplified added read replicas: three of them now share the reads.
Server A and server B still send every write to the primary, which passes each change to every replica.
Every time a learner answers a question, Simplified writes one row to attempts.
That row holds the learner's user ID, and the lesson's ID.
With 2,000,000 learners, attempts now holds 400,000,000 rows.
The primary takes all those writes, and every replica holds every row.
Say attempts grows until it no longer fits on one machine's disk.
Then another replica can't help: it would need every row too.
So how can Simplified share attempts' rows and writes between machines?
It can split the rows, instead of copying them.
Say it moves attempts onto four new database servers, a quarter of the rows on each.
400,000,000 rows split four ways is 100,000,000 rows on each.
Each of those slices is called a partition.
A partition is a slice of a table's rows, on its own database server.
Splitting a table across machines like this is also called sharding, and each slice a shard.
They're numbered 0 to 3, and a later lesson shows why they start from 0.
Only attempts is split: users, lessons and completions stay on the primary and its replicas.
Each new attempt goes to just one partition, so each takes about a quarter of the writes.
Take one of Ada's attempts, her answer in lesson 3.
With replicas, it's on the primary and on all three replicas.
With partitions, it's on just one partition, and on none of the others.
So replication copies every row to every machine.
And partitioning splits the rows, so each row is on just one machine.
Now how might Instagram keep more accounts than one machine can hold?
Say its accounts table no longer fits on one database server.
So it might split them into partitions, each on its own server.
Your account is on one partition, and your friend's might be on another.
A partition holds only its own slice of a table, so no machine needs the whole table.
Say Simplified's attempts table grows to 600,000,000 rows. Simplified splits it into 4 partitions, each holding the same number of rows.
How many rows does each partition hold?
Explanation
First, a partition is a slice of the table's rows, so the 600,000,000 rows are shared out, not copied.
Then, 4 slices of the same size: .
Therefore, each partition holds 150,000,000 rows.
Say Pinterest keeps every pin in a pins table, on one primary. The pins table is growing too big for one database server's disk.
Which plan lets the pins table keep growing, with no machine holding every pin?
Databases · Lesson 6.2
Which partition gets the row?
So Simplified's attempts are split into four partitions, numbered 0 to 3.
Each holds about 100,000,000 rows, and each row is on just one of them.
Now say Ada answers a question in lesson 3.
So Simplified's server has a new row to write: user ID 1, lesson ID 3.
But how does the server know which partition to send Ada's new row to?
It picks the partition from one column of the row.
That column is called the partition key.
The partition key is the column that decides which partition a row goes to.
Simplified makes user ID the partition key for attempts.
That way, all of one learner's attempts sit together, on one partition.
Simplified has 2,000,000 learners, so each partition gets a range of 500,000 user IDs.
User IDs 1 to 500,000 go to partition 0.
500,001 to 1,000,000 go to partition 1.
1,000,001 to 1,500,000 go to partition 2.
And 1,500,001 and up go to partition 3.
Ada's user ID is 1, so the server sends her new row to partition 0.
Her 250 earlier attempts are there too, since each one has user ID 1.
Now say a learner with user ID 1,200,000 answers a question.
1,200,000 is past 1,000,000, but not past 1,500,000.
So the server sends their new row to partition 2.
And how might your phone's contacts app use a key like this?
Say it keeps names A to M in one list, and N to Z in another.
The first letter of each name is the key that picks the list.
So Ben goes in A to M, and Sam goes in N to Z.
A row's partition key, and nothing else, decides which partition holds it.
Simplified splits attempts into 4 partitions, with user ID as the partition key: user IDs 1 to 500,000 go to partition 0, 500,001 to 1,000,000 to partition 1, 1,000,001 to 1,500,000 to partition 2, and 1,500,001 and up to partition 3. A learner with user ID 1,000,001 answers a question.
Which partition does their new attempt go to?
Explanation
First, the partition key is user ID, so the server looks at 1,000,001.
Then, 1,000,001 is past 1,000,000, but not past 1,500,000.
Therefore, the new attempt goes to partition 2.
Simplified splits attempts into 4 partitions, with user ID as the partition key: user IDs 1 to 500,000 go to partition 0, 500,001 to 1,000,000 to partition 1, 1,000,001 to 1,500,000 to partition 2, and 1,500,001 and up to partition 3. Dee, user ID 4, has 90 attempts. A learner with user ID 900,000 has 60.
How many of these 150 attempts are on partition 0?
Simplified splits attempts into 4 partitions, with user ID as the partition key: user IDs 1 to 500,000 go to partition 0, 500,001 to 1,000,000 to partition 1, 1,000,001 to 1,500,000 to partition 2, and 1,500,001 and up to partition 3. Learners with user IDs 499,999, 500,000, 500,001 and 500,002 each answer one question.
How many of these 4 new attempts go to partition 1?
Say WhatsApp splits its messages table across 8 database servers. Each message's chat_id, the chat it was sent in, decides which server the message goes to.
What is chat_id here?
Simplified splits attempts into 4 partitions, with user ID as the partition key: user IDs 1 to 500,000 go to partition 0, 500,001 to 1,000,000 to partition 1, 1,000,001 to 1,500,000 to partition 2, and 1,500,001 and up to partition 3. Ada, user ID 1, answers a question in lesson 3. A learner with user ID 600,000 answers a question in lesson 3 too.
Where do the two new attempts go?
Simplified splits attempts into 4 partitions, with user ID as the partition key: user IDs 1 to 500,000 go to partition 0, 500,001 to 1,000,000 to partition 1, 1,000,001 to 1,500,000 to partition 2, and 1,500,001 and up to partition 3. A learner with user ID 1,500,000 answers 40 questions, and a learner with user ID 1,500,001 answers 30.
How many of these 70 new attempts go to partition 3?
Simplified splits attempts into 4 partitions, with user ID as the partition key: user IDs 1 to 500,000 go to partition 0, 500,001 to 1,000,000 to partition 1, 1,000,001 to 1,500,000 to partition 2, and 1,500,001 and up to partition 3. Learners with user IDs 1,000,000 and 1,000,001 each answer one question.
Where do their two new attempts go?
Databases · Lesson 6.3
When one partition does all the work
So Simplified's server sends each new attempt to a partition by its user ID.
User IDs 1 to 500,000 go to partition 0, and 1,500,001 and up to partition 3.
Now say another Forbes article brings a rush of 100,000 new learners.
Each new learner gets the next user ID, one more than the last.
Simplified had 2,000,000 learners, so the first new one gets 2,000,001.
So which partition do the new learners' attempts go to?
2,000,001 is past 1,500,000, so that learner's attempts go to partition 3.
The next new learner gets 2,000,002, so partition 3 again.
And so on, up to 2,100,000: all 100,000 land on partition 3.
And new learners answer the most questions, so nearly every new attempt goes to partition 3.
Say 1,000 new attempts arrive a second, all from new learners.
Then partition 3 takes all 1,000, and partition 0 takes none.
Partition 3 is overloaded, while partitions 0 to 2 sit almost idle.
This is called a hot partition: one partition that gets most of the traffic, its reads and writes.
Simplified split attempts four ways, so each partition would take a quarter of the writes.
Now one machine does the work meant for four, while three sit almost idle.
With ranges of user IDs, every new learner lands on partition 3, so it does the work of four.
Simplified splits attempts into 4 partitions by ranges of user IDs, with 1,500,001 and up on partition 3. Simplified has 2,000,000 learners, and a Forbes article brings new learners with user IDs 2,000,001 to 2,050,000. 600 new attempts arrive a second, all from these new learners.
How many new attempts a second does partition 3 take?
Explanation
First, every new learner's user ID is past 1,500,000, so each one's attempts go to partition 3.
Then, all 600 new attempts a second come from new learners.
Therefore, partition 3 takes 600 a second, and the other partitions none.
Simplified splits attempts into 4 partitions by ranges of user IDs: 1 to 500,000 on partition 0, 500,001 to 1,000,000 on partition 1, 1,000,001 to 1,500,000 on partition 2, and 1,500,001 and up on partition 3. It has 2,000,000 learners, and a Forbes article brings new ones, with user IDs past 2,000,000. Now 1,000 new attempts arrive a second: 900 from new learners, and 100 from earlier learners, spread evenly over the 4 partitions.
How many new attempts a second does partition 3 take?
Simplified splits attempts into 4 partitions by ranges of user IDs: 1 to 500,000 on partition 0, 500,001 to 1,000,000 on partition 1, 1,000,001 to 1,500,000 on partition 2, and 1,500,001 and up on partition 3. During a Forbes rush, 100,000 new learners join, with user IDs past 2,000,000. In the same hour, Ada, user ID 1, answers 20 questions.
How many of Ada's 20 new attempts go to partition 3?
Say Instagram splits its likes table into 4 partitions. Partition 0 holds 120,000,000 rows and takes 50 writes a second. Partition 1 holds 100,000,000 rows and takes 60. Partition 2 holds 110,000,000 rows and takes 40. Partition 3 holds 90,000,000 rows and takes 850.
Which is a hot partition?
Simplified splits attempts into 4 partitions by ranges of 500,000 user IDs, with 1,500,001 and up on partition 3. It has 2,000,000 learners. A Forbes article brings 100,000 new learners, and every one's attempts go to partition 3.
Why?
Simplified splits attempts into 4 partitions by ranges of user IDs. During a Forbes rush, 1,000 new attempts arrive a second, all from new learners, so partition 3 takes all 1,000.
If the same 1,000 had spread evenly over the 4 partitions, how many more writes a second does partition 3 take than it would have?
Say Instagram splits its photos table into 4 partitions by the year each photo was posted: 2023, 2024, 2025 and 2026. It's now 2026: every new photo is posted this year, and people mostly look at photos posted this year.
Which partition is a hot partition?