Your rank, 48,213 of 50 million: why SQL can't answer it live

transcript

The top 10 of a leaderboard? Easy. Your exact rank, out of 50 million, live? That breaks a database.

You finish a match. Plus 30 points. Instantly: rank 48,213, with 2,210 points. Plus the 5 players above you, and 5 below. Under 50 milliseconds.

Here's the catch. A rank is a count. Everyone with a higher score. An index on score doesn't fix that. The database still walks every entry above you.

For rank 48,213, about 48,000 index entries. For a player in the middle of 50 million? 25 million. At 45,000 reads a second, that's billions of entries a second. A sorted set finds any rank in about 26 steps.

Redis builds a sorted set as a skip list. Its links record how many elements they span. The counts are already stored. So a rank is order log N. About 26 steps for 50 million.

And the whole board? About 100 bytes a player. 5 gigabytes. One sorted set, on one machine. Size was never the problem. Counting was.

SQL computes a rank by counting. A skip list already knows. Don't count your way to a rank. Store the counts.

Full breakdown in the lecture.