What is database sharding?

// Sharding a users table four ways: range vs hash on the same workload, a hot key,
// and what resharding costs with hash % N versus fixed logical shards.
function h32(s) {
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35); h ^= h >>> 16;
  return h >>> 0;
}
const pct = (num, den) => { const v = Math.floor((num * 1000) / den); return Math.floor(v / 10) + "." + (v % 10) + "%"; };
const USERS = 12000, SHARDS = 4;
const byRange = (id) => Math.floor((id - 1) / (USERS / SHARDS)); // ids 1-3000 -> 0, 3001-6000 -> 1, ...
const byHash = (id) => h32("user:" + id) % SHARDS;
const row = (label, counts, total) => console.log(`  ${label.padEnd(14)}` + counts.map((c) => pct(c, total).padStart(7)).join("") + `   busiest ${pct(Math.max(...counts), total)}`);
const tally = (ids, f) => { const c = new Array(SHARDS).fill(0); for (const id of ids) c[f(id)]++; return c; };

console.log("Users 1..12000 on 4 shards. Share of traffic per shard (s0 s1 s2 s3):");
const writes = []; for (let i = 0; i < 20000; i++) writes.push(9001 + ((i * 7919) % 3000)); // newest users are the active ones
console.log("1) 20000 writes, all from the 3000 newest users:");
row("range by id", tally(writes, byRange), writes.length);
row("hash of id", tally(writes, byHash), writes.length);

const reads = []; for (let i = 0; i < 20000; i++) reads.push(i % 10 < 3 ? 777 : 1 + ((i * 104729) % USERS));
console.log("2) 20000 reads, 30% of them for one celebrity, user 777:");
row("hash of id", tally(reads, byHash), reads.length);

const touched = (ids, f) => new Set(ids.map(f)).size;
const scan = []; for (let id = 5000; id <= 5999; id++) scan.push(id);
console.log("3) Shards a query must touch:");
console.log(`  get user 4217:            range ${touched([4217], byRange)}, hash ${touched([4217], byHash)}`);
console.log(`  users with id 5000-5999:  range ${touched(scan, byRange)}, hash ${touched(scan, byHash)}`);

console.log("4) Grow from 4 to 6 physical databases:");
let modMoved = 0; for (let id = 1; id <= USERS; id++) { const h = h32("user:" + id); if (h % 4 !== h % 6) modMoved++; }
console.log(`  hash % N (4 -> 6):        ${modMoved} of ${USERS} users move (${pct(modMoved, USERS)})`);
const LOGICAL = 48;
const before = []; for (let l = 0; l < LOGICAL; l++) before.push(Math.floor(l / 12)); // 12 logical shards per host
const after = before.slice(); let n = 0;
for (let host = 0; host < 4; host++) for (let j = 8; j < 12; j++) after[host * 12 + j] = 4 + (n++ % 2); // hand 4 from each host to the new ones
let logicalMoved = 0, shardsMoved = 0;
for (let l = 0; l < LOGICAL; l++) if (before[l] !== after[l]) shardsMoved++;
for (let id = 1; id <= USERS; id++) { const l = h32("user:" + id) % LOGICAL; if (before[l] !== after[l]) logicalMoved++; }
const perHost = new Array(6).fill(0); for (const h of after) perHost[h]++;
console.log(`  48 logical shards:        ${shardsMoved} logical shards copied whole, ${logicalMoved} of ${USERS} users move (${pct(logicalMoved, USERS)})`);
console.log(`  logical shards per host after: ${perHost.join(" ")}`);

console.log("5) Capacity estimate (assumptions in the doc):");
const usersM = 200, ordersPerUser = 50, rowBytes = 1000, peakWrites = 30000;
const dataTB = Math.floor((usersM * 1000000 * ordersPerUser * rowBytes) / 1e12);
const perShardTB = 2, perShardWrites = 5000;
const byData = Math.ceil(dataTB / perShardTB), byWrites = Math.ceil(peakWrites / perShardWrites);
console.log(`  data ${dataTB} TB / ${perShardTB} TB per shard = ${byData} shards; peak ${peakWrites} writes/s / ${perShardWrites} per shard = ${byWrites} shards`);
console.log(`  need max(${byData}, ${byWrites}) = ${Math.max(byData, byWrites)} shards today; with 2x headroom plan ${2 * Math.max(byData, byWrites)}`);