Rank 31,402,117 or 31,402,118? Nobody can tell.

transcript

Your rank: 31,402,117. Or was it 31,402,118? You can't tell. So why is the leaderboard paying to know?

The interviewer pushes. Now it's 500 million players. Or 200,000 score updates a second. One sorted set on one node won't do. So you shard it.

Shard by player hash. Now every shard holds some players above you. So an exact rank asks every shard: how many scored higher? Add the counts. Fine for tens of shards. With hundreds, every rank query hits hundreds of nodes.

But here's the catch. Who actually needs that number exact? Rank 31,402,117 and 31,402,118 mean the same thing to a human.

So be exact at the top. The top 10,000 care, and they're a small set. Everyone else? Keep a histogram of scores. Say, 1,000 buckets. Update it as scores change. Read a rank from it in constant time.

So most players see: you're in the top 38 percent. Or: about rank 19 million. Instantly. No call to every shard.

Precision has a price. Pay it where people can tell the difference. Exact at the top. A histogram for the tail.

Full breakdown in the lecture.