Simplified
Simplified

L7.1Spreading new rows around

YOU

Spreading new rows around

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?
user ID, in groups of 4Ada, 141 left over→ partition 1Ben, 242 left over→ partition 2Cy, 343 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0partition 1partition 2partition 3
remainder
what's left after taking out every group of 4 that fits
user ID, in groups of 4Ada, 14remainder 1→ partition 1Ben, 242 left over→ partition 2Cy, 343 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0partition 1Adapartition 2partition 3

Databases · Lesson 7.1

No Machine Left Idle

Spreading new rows around

Simplified
0:00 / 2:06

With ranges, partition 3 held every user ID from 1,500,001 up.

So the Forbes rush's new learners, from 2,000,001, all landed on partition 3, a hot partition.

Of 1,000 new attempts a second, it took all 1,000, and partition 0 none.

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

So how else can Simplified's server pick a partition, so new user IDs don't all pile onto one?

Instead of ranges, it splits each user ID into groups of 4.

It uses groups of 4 because there are four partitions.

Then what's left over picks the partition.

user ID, in groups of 4Ada, 11 left over→ partition 1Ben, 22 left over→ partition 2Cy, 33 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0partition 1Adapartition 2partition 3

Picture Ada's user ID, 1, as 1 square.

A group of 4 needs 4 squares, so no group fits.

So 1 square is left over.

And 1 picks partition 1, so Ada's attempts go there.

What's left over is called the remainder.

The remainder is what's left after taking out every group of 4 that fits.

user ID, in groups of 4Ada, 11 left over→ partition 1Ben, 22 left over→ partition 2Cy, 33 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0partition 1Adapartition 2Benpartition 3Cy

Ben's user ID, 2, is 2 squares, too few for a group of 4.

So the remainder is 2, and Ben goes to partition 2.

Cy's user ID, 3, is 3 squares, still too few.

So the remainder is 3, and Cy goes to partition 3.

user ID, in groups of 4Ada, 11 left over→ partition 1Ben, 22 left over→ partition 2Cy, 33 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0Deepartition 1Adapartition 2Benpartition 3Cy

Dee's user ID, 4, is 4 squares.

Take out one group of 4.

Nothing is left over, so the remainder is 0.

And 0 picks partition 0, so Dee goes there.

user ID, in groups of 4Ada, 11 left over→ partition 1Ben, 22 left over→ partition 2Cy, 33 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0Deepartition 1AdaElipartition 2BenFaypartition 3Cy

Eli's user ID, 5, is 5 squares.

Take out one group of 4, and 1 square is left over.

So Eli's remainder is 1, and he goes to partition 1, with Ada.

Fay's 6 squares make one group of 4, with 2 left over.

So Fay's remainder is 2, and she goes to partition 2, with Ben.

The remainder can only be 0, 1, 2 or 3.

Because 4 left over would make another group of 4.

So there's one remainder for each partition, which is why they're numbered from 0.

user ID, in groups of 4Ada, 11 left over→ partition 1Ben, 22 left over→ partition 2Cy, 33 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0Deepartition 1AdaElipartition 2BenFaypartition 3Cy

A user ID's remainder, what's left after every group of 4, is 0 to 3, and it picks the partition.

Example: Spreading new rows around

Simplified splits attempts into 4 partitions, numbered 0 to 3. Its server splits each user ID into groups of 4, and the remainder picks the partition. A learner with user ID 7 answers a question.

Which partition does their new attempt go to?

Explanation

First, 7 squares make one group of 4, with 3 left over.

Then, the remainder, 3, picks partition 3.

Therefore, the new attempt goes to partition 3.

Question 1

Simplified splits attempts into 4 partitions, numbered 0 to 3. Its server splits each user ID into groups of 4, and the remainder, what's left over, picks the partition. Cy, user ID 3, and a learner with user ID 7 each answer a question.

Where do their two new attempts go?

No partition left idle

user ID, in groups of 4Ada, 141 left over→ partition 1Ben, 242 left over→ partition 2Cy, 343 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0partition 1partition 2partition 3
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
user ID, in groups of 42,000,001…500,000 fours= 2,000,0000 left over41 left over→ partition 12,000,002…500,000 fours= 2,000,0000 left over42 left over→ partition 22,000,003…500,000 fours= 2,000,0000 left over43 left over→ partition 32,000,004…500,000 fours= 2,000,0000 left over40 left over→ partition 02,000,005…500,000 fours= 2,000,0000 left over41 left over→ partition 1partition 0partition 1partition 2partition 3?
100,000 new learners2,000,000 (last)+1+12,000,0012,000,002…2,100,000remainders 1, 2, 3, 0, …1,000 new attempts a secondpartition 00 a secondpartition 1partition 2partition 3hot1,000 a second
user ID, in groups of 4Ada, 141 left over→ partition 1Ben, 242 left over→ partition 2Cy, 343 left over→ partition 3Dee, 440 left over→ partition 0Eli, 541 left over→ partition 1Fay, 642 left over→ partition 2partition 0partition 1partition 2partition 3
100,000 new learners2,000,000 (last)+1+12,000,0012,000,002…2,100,000remainders 1, 2, 3, 0, …1,000 new attempts a secondpartition 0250 a secondpartition 1250 a secondpartition 2250 a secondpartition 3250 a second

Databases · Lesson 7.2

No Machine Left Idle

No partition left idle

Simplified
0:00 / 1:35

So Simplified's server now splits each user ID into groups of 4, one for each partition.

And the remainder picks the partition: Dee's 4 is one group, with 0 left, so partition 0.

With ranges, the Forbes rush's new learners all landed on partition 3: all 1,000 of their new attempts a second, and partition 0 got none.

So where do those new learners, from user ID 2,000,001, go now?

user ID, in groups of 42,000,001500,000 groups of 41 left over→ partition 12,000,002500,000 groups of 42 left over→ partition 22,000,003500,000 groups of 43 left over→ partition 32,000,004500,000 groups of 440 left over→ partition 0partition 02,000,004partition 12,000,001partition 22,000,002partition 32,000,003

500,000 fours make 2,000,000, so 2,000,000 splits into groups of 4 with nothing left over.

The first new learner, 2,000,001, is one more than 2,000,000, so 1 is left over: partition 1.

2,000,002 is two more, so 2 are left over: partition 2.

2,000,003 is three more, so 3 are left over: partition 3.

2,000,004 is four more: one more group of 4, so nothing is left over: partition 0.

So new learners are dealt out in turn: partitions 1, 2, 3, 0, then round again.

So 1,000 new attempts a second split four ways: about 250 on each partition.

So partition 0 goes from none to about 250, and partition 3 from 1,000 to about 250.

new learners2,000,0012,000,002…2,100,0001,000 new attempts a secondpartition 0250 a secondpartition 1250 a secondpartition 2250 a secondpartition 3250 a second

And every one of Ada's attempts has user ID 1, which always leaves 1.

So one learner's attempts still sit together, on one partition.

Each new user ID leaves the next remainder, so no partition is hot and none sits idle.

Example: No partition left idle

Simplified splits attempts into 4 partitions, numbered 0 to 3, by the remainder after splitting each user ID into groups of 4. 2,000,000 splits into exactly 500,000 groups of 4. A new learner with user ID 2,000,007 answers a question.

Which partition does their new attempt go to?

Explanation

First, 2,000,000 is exactly 500,000 groups of 4, so only the 7 past it can leave anything over.

Then, 7 makes one more group of 4, with 3 left over.

Therefore, the new attempt goes to partition 3.

Question 1

Simplified splits attempts into 4 partitions, numbered 0 to 3, and picks each attempt's partition from the remainder after splitting its user ID into groups of 4. 2,000,000 splits into exactly 500,000 groups of 4. Eight new learners, with user IDs 2,000,001 to 2,000,008, each answer one question.

How many of these 8 new attempts go to partition 2?

attempts

Question 2

Simplified splits attempts into 4 partitions by the remainder after splitting each user ID into groups of 4. During a Forbes rush, 1,200 new attempts arrive a second, all from new learners, whose user IDs come one after another.

How many new attempts a second does each partition take, about?

attempts a second

Question 3

Simplified splits each user ID into groups of 4, and the remainder picks one of 4 partitions, numbered 0 to 3. Eli, user ID 5, has answered 30 questions.

Where are his 30 attempts?

Question 4

Simplified splits attempts into 4 partitions, numbered 0 to 3, and picks each attempt's partition from the remainder after splitting its user ID into groups of 4. A Forbes article brings 100 new learners, with user IDs 2,000,001 to 2,000,100, and 2,000,000 splits into exactly 500,000 groups of 4.

How many of these 100 new learners land on partition 0?

learners

Question 5

With ranges of user IDs, every new learner in a Forbes rush landed on partition 3. Now Simplified's server picks the partition from the remainder after splitting each user ID into groups of 4, and the rush's new learners spread over all four partitions.

Why?

Question 6

Say Simplified had 5 partitions, numbered 0 to 4, and its server split each user ID into groups of 5, so the remainder picked the partition. During a Forbes rush, 1,000 new attempts arrive a second, all from new learners whose user IDs come one after another.

About how many new attempts a second would each partition take?

attempts a second

Which partitions does a query visit?

Simplified'sserverSELECT * FROM attemptsWHERE user_id = 1;partition keyAda, 141 left over→ partition 1no remainder300,000 + 250,000+ 200,000 + 250,000= 1,000,000partition 0partition 1partition 2partition 3?
Simplified'sserveranalytics pageSELECT * FROM attemptsWHERE user_id = 1;partition keyAda, 141 left over→ partition 1no remainder300,000 + 250,000+ 200,000 + 250,000= 1,000,000partition 0partition 1partition 2partition 3
Simplified'sserverSELECT * FROM attemptsWHERE user_id = 1;partition keyAda, 141 left over→ partition 1no remainder300,000 + 250,000+ 200,000 + 250,000= 1,000,000partition 0partition 1Ada's attemptspartition 2partition 3
Simplified'sserveranalytics pageSELECT COUNT(*)FROM attemptsWHERElesson_id= 3;partition keyAda, 141 left over→ partition 1no remainder300,000 + 250,000+ 200,000 + 250,000= 1,000,000partition 0partition 1partition 2partition 3

Databases · Lesson 7.3

No Machine Left Idle

Which partitions does a query visit?

Simplified
0:00 / 1:54

So Simplified's server now picks each attempt's partition from its user ID's remainder.

Ada's user ID, 1, leaves 1, so all her attempts are on partition 1.

Now say Ada opens her progress, so the server needs her attempts.

The query is SELECT star FROM attempts WHERE user ID equals 1.

But with attempts split four ways, which partitions does the server send that query to?

Simplified'sserverSELECT * FROM attemptsWHEREuser_id = 1;1 left over→ partition 1partition 0partition 1Adapartition 2partition 3

The query's WHERE names user ID, the partition key.

So the server works out 1's remainder, just as it does for each write.

1 is too few for a group of 4, so 1 is left over.

So Ada's attempts can only be on partition 1.

So the server sends the query to partition 1 alone, and the others never see it.

But what about a query whose WHERE doesn't name user ID?

Say Simplified's team opens its analytics page, to see how many answers lesson 3 has had.

Its query is SELECT COUNT star FROM attempts WHERE lesson ID equals 3.

Simplified'sserverSELECT COUNT(*)FROM attemptsWHERElesson_id = 3;1 left over→ partition 1partition 0partition 1partition 2partition 3

Lesson ID isn't the partition key, so there's no remainder to work out.

And lesson 3's attempts could be on any partition, since every learner can answer it.

So the server sends the query to all four partitions.

Each counts the lesson 3 attempts it holds: say 300,000, 250,000, 200,000 and 250,000.

Then each sends its count back, and the server adds them up: 1,000,000.

Simplified'sserverSELECT COUNT(*)FROM attemptsWHERE lesson_id = 3;300,000250,000200,000250,0001 left over→ partition 1300,000 + 250,000+ 200,000 + 250,000= 1,000,000partition 0partition 1partition 2partition 3

So that one query makes all four machines work, and the server waits for all four.

So Simplified picks a partition key its most common queries name.

Its most common attempts query is one learner's answers, to show their progress.

That names user ID, so it goes to just one partition.

A query that names the partition key goes to one partition; any other goes to all of them.

Example: Which partitions does a query visit?

Simplified splits attempts into 4 partitions, numbered 0 to 3, by the remainder after splitting each user ID into groups of 4. Fay opens her progress, so Simplified's server sends SELECT * FROM attempts WHERE user_id = 6;.

Which partition does the server send the query to?

Explanation

First, the WHERE names user_id, the partition key, so the server works out 6's remainder.

Then, 6 squares make one group of 4, with 2 left over.

Therefore, it sends the query to partition 2 only.

Question 1

Simplified splits attempts into 4 partitions, numbered 0 to 3, with user_id as the partition key: the remainder after splitting each user ID into groups of 4 picks the partition. Simplified's analytics page sends SELECT COUNT(*) FROM attempts WHERE lesson_id = 5;.

How many partitions does Simplified's server send this query to?

partitions

Question 2

Simplified splits attempts into 4 partitions, with user_id as the partition key. Its analytics page sends SELECT COUNT(*) FROM attempts WHERE lesson_id = 2;, so Simplified's server sends it to all 4 partitions. They send back counts of 400,000, 350,000, 500,000 and 450,000.

What count does the server send back to the analytics page?

attempts

Question 3

Simplified splits attempts into 4 partitions, with user_id as the partition key: the remainder after splitting each user ID into groups of 4 picks the partition.

Which of these queries does Simplified's server send to just one partition?

Question 4

Say Instagram is splitting its likes table, with columns user_id and photo_id, into partitions. Its most common query, by far, is every like on one photo: WHERE photo_id = …. Now and then, it asks for one user's likes.

Which column should be the partition key?

Question 5

Simplified splits attempts into 4 partitions, numbered 0 to 3, with user_id as the partition key: the remainder after splitting each user ID into groups of 4 picks the partition. Its server sends three queries: SELECT * FROM attempts WHERE user_id = 1;, then the same with user_id = 2, then with user_id = 5.

How many different partitions do these three queries reach?

partitions

Question 6

Simplified splits attempts into 4 partitions, numbered 0 to 3, with user_id as the partition key: the remainder after splitting each user ID into groups of 4 picks the partition.

Why does Simplified's server send SELECT COUNT(*) FROM attempts WHERE lesson_id = 3; to all four partitions?

Assistant

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