Part 7 of 8 · 3 min read
NoSQL and trade-offs
Another store, and what to say.
A NoSQL alternative and trade-offs
NoSQL option. A managed store such as DynamoDB keeps the whole leaderboard in one denormalised table, with the user details beside the score. A plain table needs a scan to rank. So the table uses a global secondary index, a second view of the same data with a different key.
- Partition key: game name plus month, such as
chess#2020-02. Sort key: score. This lists players in score order. - Problem: all of one month's rows share a partition key, so one hot partition takes all the writes.
- Fix: write sharding. Add a partition number to the key, such as
chess#2020-02#p3, chosen by user id modulo the number of partitions. Each partition holds a sorted slice, and the writes spread out. - Cost: reading the month means querying every partition and merging the results, so more partitions mean heavier reads. Choose the count from write volume.
Ranks across partitions are then approximate or require extra counting, which is why the book still prefers Redis for exact ranks.
| Choice | Gain | Cost |
|---|---|---|
| Relational table | Simple | Slow ranks at scale |
| Redis sorted set | Fast exact ranks | Memory, needs a rebuild path |
| Single server | Simple | A limit at about 100 times the scale |
| Score-range shards | Easy rank sums | Moves between shards, uneven load |
| Hash-slot cluster | Even load | Slow top K, hard rank |
| NoSQL with write sharding | Managed, scalable | Approximate rank, merge reads |
| Serverless | No servers to run | Cold starts, vendor lock-in |
Ties. Equal scores share a rank. To break ties, give the earlier score the higher place by packing the time of the last win into the score, for example score × 10^10 plus the inverse of the timestamp.
Interview angle
Answer in your head first, then open it.
Why not SQL?
Ranking needs a sort of millions of rows on every request.
Why a sorted set?
Order is kept at insert, and rank takes logarithmic time.
How much memory?
About 650 MB for 25 million players.
What if Redis dies?
Promote a replica, or rebuild from the point table.
What if load grows 100 times?
Shard by score range and sum higher shards for the rank.
One follow-up to try. "Show the top 10 among a player's friends." A good reply: keep the global sorted set, and for each player make a small sorted set of friend scores, or fetch the friends' scores with a batch lookup and sort them in the service. The friend list is small, so sorting is cheap. A per-player set trades memory and update work for faster reads.
Check yourself: 1. What problem does write sharding solve? 2. What does it cost on reads? 3. How can ties be broken by time?
Words you will meet
| Word | Meaning |
|---|---|
| Leaderboard | Players ordered by score |
| Sorted set | A unique collection kept in score order |
| Skip list | A sorted list with index levels for fast search |
| Hash slot | One of 16,384 buckets that Redis Cluster uses to place keys |
| Hot partition | One partition that takes too much of the load |
| Write sharding | Adding a number to the key to spread writes |
| Global secondary index | A second view of a table with a different key |
| Serverless function | Code that a cloud runs and scales on demand |