Simplified
Simplified

L6.1When a table outgrows one machine

YOU

When a table outgrows one machine

server Aserver Bprimaryusers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionsattemptsuser_idlesson_id13replicadisk fullusers · lessons · completionsattempts · 400,000,000 rows2,000,000 learnersattempts · 400,000,000 rowsdatabase serverdatabase serverdatabase serverdatabase server?
partition
a slice of a table's rows, on its own database server
sharding
splitting a table across machines; each slice is a shard
replicationpartitioningAda · lesson 3primaryusers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionspartition 0attempts · 100,000,000 rowspartition 1attempts · 100,000,000 rowspartition 2attempts · 100,000,000 rowspartition 3attempts · 100,000,000 rows
replicationpartitioningAda · lesson 3primaryusers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionspartition 0attempts · 100,000,000 rowspartition 1attempts · 100,000,000 rowspartition 2attempts · 100,000,000 rowspartition 3attempts · 100,000,000 rows
Instagramdatabase serverdisk fullaccountspartition 0a slice of the accountspartition 1a slice of the accountspartition 2a slice of the accountspartition 3a slice of the accounts?

Databases · Lesson 6.1

Splitting a Table

When a table outgrows one machine

Simplified
0:00 / 2:10

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.

server Aserver Bprimaryusers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionspartition 0attempts · 100,000,000 rowspartition 1attempts · 100,000,000 rowspartition 2attempts · 100,000,000 rowspartition 3attempts · 100,000,000 rows

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.

server Aserver Bprimaryusers · lessons · completionsattempts · 400,000,000 rowsreplicausers · lessons · completionsattempts · 400,000,000 rowsreplicausers · lessons · completionsattempts · 400,000,000 rowsreplicausers · lessons · completionsattempts · 400,000,000 rowspartition 0attempts · 100,000,000 rowspartition 1attempts · 100,000,000 rowspartition 2attempts · 100,000,000 rowspartition 3attempts · 100,000,000 rows

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.

server Aserver Bprimaryusers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionsreplicausers · lessons · completionspartition 0attempts · 100,000,000 rowspartition 1attempts · 100,000,000 rowspartition 2attempts · 100,000,000 rowspartition 3attempts · 100,000,000 rows

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.

replicationpartitioningserver Aserver Bprimaryattempts · 400,000,000 rowsAda · lesson 3replicaattempts · 400,000,000 rowsAda · lesson 3replicaattempts · 400,000,000 rowsAda · lesson 3replicaattempts · 400,000,000 rowsAda · lesson 3partition 0attempts · 100,000,000 rowsAda · lesson 3partition 1attempts · 100,000,000 rowspartition 2attempts · 100,000,000 rowspartition 3attempts · 100,000,000 rows

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.

Instagram's accountspartition 0a slice of the accountspartition 1a slice of the accountsyour accountpartition 2a slice of the accountspartition 3a slice of the accountsyour friend's account

A partition holds only its own slice of a table, so no machine needs the whole table.

Example: When a table outgrows one machine

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: 600,000,000÷4=150,000,000600{,}000{,}000 \div 4 = 150{,}000{,}000600,000,000÷4=150,000,000.

Therefore, each partition holds 150,000,000 rows.

Question 1

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?

Which partition gets the row?

Simplified'sservernew attemptuser_idlesson_id13partition keypartition 0partition 1partition 2partition 3?
partition key
the column that decides which partition a row goes to
Simplified'sservernew attemptuser_idlesson_id13partition keypartition 0attempts · 100,000,000 rowspartition 1attempts · 100,000,000 rowspartition 2attempts · 100,000,000 rowspartition 3attempts · 100,000,000 rows
your phone's contactsBenSamA to MBenN to ZSam?
Simplified'sservernew attemptuser_idlesson_id13partition key2,000,000 learnerspartition 0IDs 1 to 500,000partition 1IDs 500,001 to 1,000,000partition 2IDs 1,000,001 to 1,500,000partition 3IDs 1,500,001 and up

Databases · Lesson 6.2

Splitting a Table

Which partition gets the row?

Simplified
0:00 / 1:53

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?

Simplified'sservernew attemptuser_idlesson_id13partition key?partition 0attempts · 100,000,000 rowspartition 1attempts · 100,000,000 rowspartition 2attempts · 100,000,000 rowspartition 3attempts · 100,000,000 rows

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.

Simplified'sservernew attemptuser_idlesson_id13partition key?partition 0IDs 1 to 500,000partition 1IDs 500,001 to 1,000,000partition 2IDs 1,000,001 to 1,500,000partition 3IDs 1,500,001 and up

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.

Simplified'sservernew attemptuser_idlesson_id13partition key?partition 0IDs 1 to 500,000Adapartition 1IDs 500,001 to 1,000,000partition 2IDs 1,000,001 to 1,500,000partition 3IDs 1,500,001 and up

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.

Simplified'sservernew attemptuser_idlesson_id1,200,0003partition key?partition 0IDs 1 to 500,000partition 1IDs 500,001 to 1,000,000partition 2IDs 1,000,001 to 1,500,000partition 3IDs 1,500,001 and up

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.

your phone's contactsA to MBenN to ZSam

A row's partition key, and nothing else, decides which partition holds it.

Example: Which partition gets the row?

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.

Question 1

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?

attempts

Question 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. 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?

attempts

Question 3

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?

Question 4

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?

Question 5

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?

attempts

Question 6

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?

When one partition does all the work

Simplified'sservernew attemptuser_idlesson_id13partition key2,000,000 learnerspartition 0IDs 1 to 500,000partition 1IDs 500,001 to 1,000,000partition 2IDs 1,000,001 to 1,500,000partition 3IDs 1,500,001 and up
100,000 new learners2,000,000 (last)+1+12,000,0012,000,002…2,100,000remainders 1, 2, 3, 0, …partition 0IDs 1 to 500,000partition 1IDs 500,001 to 1,000,000partition 2IDs 1,000,001 to 1,500,000partition 3IDs 1,500,001 and up?
100,000 new learners2,000,000 (last)+1+12,000,0012,000,002…2,100,000remainders 1, 2, 3, 0, …new attemptspartition 0IDs 1 to 500,000partition 1IDs 500,001 to 1,000,000partition 2IDs 1,000,001 to 1,500,000partition 3IDs 1,500,001 and up

Databases · Lesson 6.3

Splitting a Table

When one partition does all the work

Simplified
0:00 / 1:31

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?

new learners2,000,0012,000,002…2,100,000partition 0IDs 1 to 500,000partition 1IDs 500,001 to 1,000,000partition 2IDs 1,000,001 to 1,500,000partition 3IDs 1,500,001 and up

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.

new learners2,000,0012,000,002…2,100,0001,000 new attempts a secondpartition 0IDs 1 to 500,0000 a secondpartition 1IDs 500,001 to 1,000,0000 a secondpartition 2IDs 1,000,001 to 1,500,0000 a secondpartition 3hotIDs 1,500,001 and up1,000 a second

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.

Example: When one partition does all the work

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.

Question 1

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?

attempts a second

Question 2

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?

attempts

Question 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?

Question 4

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?

Question 5

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?

writes a second

Question 6

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?

Assistant

Highlight lesson text and click Ask AI, or type a question below.