How to Build a Billion‑Item Distributed Store: From Modulo Hash to Raft

During a system design interview the candidate is asked to create a storage architecture that can hold billions of products. Most people immediately suggest simple sharding with hash modulo, but the interviewer then probes scaling, hot‑item handling, and consistency.

📌 Step 1 – Modulo Hash : The simplest scheme stores an item at productId % N where N is the number of nodes. With four nodes the mapping is 0→A, 1→B, 2→C, 3→D, giving uniform distribution with one line of code. However, adding a fifth node changes the modulus to 5, forcing every item to relocate and causing massive data movement; therefore modulo hashing ties data placement tightly to node count and offers no real scalability.

📌 Step 2 – Consistent Hashing : Nodes and data are placed on a circular hash ring; each item is stored on the first node encountered clockwise. When a new node E joins, only the segment between E and its predecessor needs to move, leaving the rest untouched. Virtual nodes (multiple points per physical machine) improve balance. The approach eases scaling and supports concurrent writes, but it remains a static partitioning scheme that cannot avoid single‑node hotspots, because a hot product will still map to a single machine.

📌 Step 3 – Range Partitioning (Business‑Driven Sharding) : When certain business categories generate far more traffic (e.g., 3C electronics on JD.com), pure hash fails. The solution is to split data by business ranges: high‑traffic categories are sharded finely (e.g., by sub‑category such as phones, computers, accessories), while low‑traffic categories use coarse sharding (e.g., top‑level category). This yields more balanced partitions and allows targeted optimization for hot items, at the cost of maintaining metadata that maps each item to its shard.

📌 Step 4 – Metadata Routing Cluster (etcd) : A routing service stores a "metadata table" that tells a client which node holds a given key, along with QPS and replica health. The table is replicated across a cluster using a consensus algorithm, storage instances periodically report heartbeats and shard info, and high availability plus consistency are delegated to external coordinators such as etcd. Clients cache routing results to reduce lookup overhead.

📌 Step 5 – Consensus Protocol Choice (Raft vs. Gossip) : Replication requires a consensus protocol. Raft provides strong consistency with a leader‑centric model; it works well for small clusters (3‑5 nodes) and is used by etcd and TiDB. Gossip achieves eventual consistency by spreading state like rumors, scaling to large, dynamic clusters such as Cassandra. The interview tip: pick Raft for strong consistency, pick Gossip for scalability and eventual consistency.

💡 Three‑Pillar Summary : Distributed storage solves three core problems – data sharding (hash modulo → consistent hash → range partitioning), data replication (master‑slave failover), and consistency (Raft vs. Gossip, CAP trade‑offs). Each step addresses the shortcomings of the previous one, forming a logical interview answer chain.

🎯 Final Thought : There is no universal silver bullet; the right trade‑offs depend on the business stage. Being able to articulate this evolution demonstrates architect‑level thinking.