CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 6 of 8 · 2 min read

Sharding

Fixed ranges or hash slots.

The book imagines 100 times the load: 500 million daily users. Memory grows to 65 GB (650 MB × 100), and updates to 250,000 a second (2,500 × 100). One server may not do. Two sharding options follow.

Fixed partitions by score range. Suppose scores run from 1 to 1,000. Make 10 shards, each holding a range of 100 scores: 1 to 100, 101 to 200, and so on. For an even load, the scores should be spread evenly, or the ranges are adjusted.

  • To update a player, the service must know their current shard. A small cache that maps a player to a score gives it quickly. When a score crosses a range limit, the player is removed from one shard and added to the next.
  • The top 10 come from the shard with the highest range.
  • A player's rank is the rank inside their own shard, plus the number of players in all higher shards. Each shard's size is available in constant time.

A worked example (made up). A player is rank 40 inside the 401 to 500 shard. The shards for 501 to 600, 601 to 700, and so on up to 1,000 hold 300, 200, 100, 50 and 10 players, or 660 in total. The player's overall rank is 660 + 40 = 700.

Redis Cluster with hash slots. The cluster divides keys into 16,384 hash slots by CRC16 of the key modulo 16,384, and nodes own ranges of slots. Adding a node moves slots, not every key. An update goes to the slot for the player. But the top 10 needs the top 10 from every shard, merged by the application. Drawbacks: large top-K queries are slow, many shards make the slowest one set the latency, and finding a rank is not simple. So the book prefers fixed ranges.

Sizing nodes. Write-heavy use needs spare memory to take a snapshot while writes continue, so allocate about twice the expected data. Test the set-up with a benchmark tool before launch.

Common mistake

Sharding too early. At 5 million daily users, one Redis server is enough, and shards add rank arithmetic and move logic for no gain.

Check yourself: 1. How is the overall rank found with fixed ranges? 2. Why is the top 10 harder with hash slots? 3. When is sharding unnecessary?