Real-Time Live Leaderboard

Most apps talk like letters in the mail. The app asks a question, the server writes back, and that conversation is over. For a live game that is too slow, because each kid would have to keep asking, is there news yet, is there news yet, over and over. A WebSocket is more like a phone call that stays connected. Once the line is open, either side can talk at any moment, so the server can share news the instant it happens.

One computer can only keep so many lines open, because each line uses a little memory. A well tuned server might hold tens of thousands of quiet lines, sometimes many more. For a million players we need a room full of these helpers, called gateways. At the door stands a load balancer, like a host at a restaurant, who sends each new caller to a helper who is not too busy. It must be a host who is happy with calls that last an hour, not one who expects a quick hello and goodbye.

Lines can go dead without anyone hanging up, for example when a tablet rides into a tunnel. So every so often the two sides trade a tiny message, called a heartbeat, that means, are you still there? If no answer comes back, the line is closed and its spot is freed. When a kid's line drops, the app calls back, but it waits a bit longer after each failed try and adds a small random extra wait. Without that random part, if one gateway crashed, all of its kids would call back at the very same instant and knock over the next helper.

Gateways keep almost nothing important in their heads. They know who is on their lines, and that is all. Scores live somewhere else. So if a gateway breaks, its players simply reconnect to another one and nothing is lost. The cost is that open lines take up memory even when they are quiet, and updating gateway software means gently moving many callers to other helpers first.

When a kid answers, a game server checks the answer and writes a small note, such as, Mia earned 30 points. Those notes go into a queue, which is like a tray of slips waiting their turn. A score service takes slips from the tray and updates the scoreboard. If a sudden rush of answers arrives, the slips simply wait a moment instead of overwhelming the scoreboard. Each slip carries its own id, so if a slip is ever delivered twice, the score service can spot the repeat and skip it instead of adding the points twice.

Now the news has to reach a million kids spread across many gateways, and no single gateway knows all of them. So we use pub/sub, short for publish and subscribe. It works like the school speaker system. The office says something once, and every classroom speaker plays it. Here, the score service publishes the new top 10 once, every gateway is listening, and each gateway passes it on to its own players.

The weakness is that simple pub/sub does not keep old messages. A gateway that was restarting while the message went out will miss it. For a leaderboard that is fine, because a fresh top 10 arrives again a moment later, and a player who just reconnected can ask for the current board directly.

Redis is a very fast storage program that keeps its data in memory, the quick desk space of a computer. One of its tools is the sorted set. Every member, like a player's name, has a score, and Redis keeps the whole set in order by score all the time. Nobody ever sorts the list from scratch.

Inside, a sorted set uses two helpers together. A hash table is like a phone book: give it a name and it finds that player's score right away. A skip list is like a long line of kids standing in score order, with a few express lanes above it. To find a spot, you ride the express lanes past big chunks of the line, then step down to slower lanes as you get close, the way you flip through a book by chapters before turning single pages.

Thanks to the express lanes, adding points or asking what place someone is in takes about log N steps, where N is the number of players. That means the work grows very slowly. For a million players it is a few dozen steps, not a million. The trade-off is memory. Everything lives in fast but pricey memory, and each entry carries extra links for the express lanes, so a huge board needs a big machine.

A few short commands do almost all the work. ZINCRBY adds points to a player. ZADD sets a score directly. ZREVRANGE, or ZRANGE with the REV option in newer versions of Redis, lists players from the highest score down, so asking for places 0 to 9 gives the top 10. ZREVRANK tells you a player's place counting from the top, and ZSCORE tells you their score.

One surprise: computers count places from 0. If ZREVRANK says 0, you are first. If it says 41, you are in 42nd place. The app adds 1 before showing it, so nobody ever sees a 0th place. To show a player the kids just around them, first ask for their place, then ask for a small slice of the list around it, such as five places above and five below. Both questions are quick.

Ties need a plan. When two players have exactly the same score, Redis puts them in order by comparing their names letter by letter, which has nothing to do with who scored first. If the rule should be that whoever got there first wins, mix time into the score: keep the points in the big part of the number and use the small part to give earlier players a tiny edge. Be careful, though. Redis stores scores in a number format that is exact only up to about 15 digits, so the points and the time must fit together inside that limit.

• ZINCRBY board 30 mia: add 30 points to Mia.
• ZREVRANGE board 0 9 WITHSCORES: the top 10, with their scores.
• ZREVRANK board mia: Mia's place, counting from 0.
• ZSCORE board mia: Mia's current score.

With a million players, scores can change thousands of times every second. If we told every player about every change, we would be sending billions of messages each second, most of them about strangers. It would be like a teacher reading out every single point scored in the whole school, all day long. Nobody could hear anything useful.

Instead, we announce on a steady beat. Once a second, the score service reads the top 10 and publishes it. If the top 10 did not change since last time, it skips the message. Each player still gets about one small message a second, but that number stays the same no matter how fast the scores change, and the work is spread across all the gateways.

A player's own place matters only to that player, so it travels separately. The app asks for it when the player opens the board, or the gateway sends it on a slower beat, like every few seconds. On the way in, the score service can batch its writes too: it gathers a few hundred slips and sends them to Redis together, which saves many round trips.

The trade-off is freshness. A player may see a top 10 that is up to a second old. For a game show, that is a small price for a system that stays calm under a storm of answers.

The easiest way to grow is to keep one sorted set per game, per region, or per time period, like today's board and this week's board. Each one stays small enough for one Redis machine, and old boards can simply be deleted.

If one single board is truly gigantic, we split its players across several sorted sets, called shards, for example by player id. Each player lives in exactly one shard. To find the overall top 10, we ask every shard for its own top 10 and pick the best 10 from those. That is always exact, because anyone in the true top 10 must also be in the top 10 of their own shard.

Exact places far down the list are harder with shards, because you would have to ask every shard how many players beat you. Instead, we can keep a count of how many players fall into each score range, like sorting marbles into labeled jars, and tell a player they are around 48,000th. Players far from the top rarely mind a close estimate.

Finally, memory can be wiped. Redis can save copies to disk and keep backup copies on other machines, but the true record of every score should also live in a durable database, one that keeps data safely on disk. If the board is ever lost, we rebuild it from that record. Redis is the fast scoreboard on the wall. The database is the teacher's notebook.