Partitioning (Sharding) — Part 2: Internals & Implementation

maang.io System Design Series

What is this?

Back to our library that split its collection across branches. In Part 1 we chose the rule for deciding which branch owns a book (range vs hash). That's the easy day. The hard days come later: you open a new branch and have to move books to it without closing the library (rebalancing); one celebrity author's books get so many visitors that one branch is overwhelmed (hot keys); a reader wants "every mystery novel," but your branches are organized by author, not genre (secondary indexes); and a reader walks in and needs to know which branch to even go to (request routing).

Every one of those is a real engineering problem with a real, sometimes surprising, right answer — and the wrong answers are the ones that take a system down at 3 a.m. This chapter is the machinery beneath the tidy declaration you wrote in Part 1.

The one-line idea: the scheme decides where a key belongs, but production is about everything around that — moving partitions cheaply when capacity changes, without the naive hash % N reshuffle that moves everything; splitting hot keys the scheme can't balance on its own; and giving every client a fast, correct answer to "which node owns this key right now?"