Databases · Lesson 7.1
Spreading new rows around
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.
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.
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.
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.
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.
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.
A user ID's remainder, what's left after every group of 4, is 0 to 3, and it picks the partition.
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.
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?
Databases · Lesson 7.2
No partition left idle
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?
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.
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.
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.
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?
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?
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?
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?
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?
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?
Databases · Lesson 7.3
Which partitions does a query visit?
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?
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.
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.
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.
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.
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?
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?
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?
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?
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?
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?