Partitioning Strategies

The sharding decision was made, and the key choice was shown to determine the hot spot — but the decision was left half finished. Once a key is chosen, which rule distributes it to partitions is a separate question: the same tracking number can be split into ranges, hashed, or have its group’s location kept in a separate table. The three rules produce three placements from the same key and affect rebalancing in three different ways.

Partitioning strategy is the rule that converts a partition key into a partition number. The Table Partitioning lesson in the Relational Database Administration course built range, list, and hash mechanics inside a single engine; the Sharding Patterns lesson distributed those same partitions across separate stores. Neither is retold here — the question is selection: across the same three access patterns, which rule moves which number by how much. The terminology split holds in one sentence: partitioning splits a table into pieces inside a single store, sharding puts those pieces into separate stores; the rule is the same in both, only where the result appears differs.

The Three Rules

Range partitioning assigns the partition to the value range the key falls into. Because tracking numbers are issued in increasing creation order, the range axis is a time axis: consecutive numbers fall into the same partition.

Hash partitioning derives the partition number from the key’s hash. Neighboring keys land far apart from each other; placement cannot be chosen. The consistent hash the previous lesson used belongs to this family and behaves the same way.

In a lookup table, the mapping from key group to partition number sits in a separate table. The rule is data, not arithmetic: placement can be chosen, changed for one group, or split in two when a group needs it. Here the group is the seller, and the tracking number carries the seller’s prefix, so the single-record read and the periodic scan share the same mapping. The cost comes from the same place — every access reads the mapping first.

Measurement needs three new assumptions, not added to the assumption table in the Introduction to System Design course; they belong to this lesson alone.

Code	Assumption	Value	Rationale
D1	exponent of the seller volume distribution	0.9	the share of the 4,000 sellers (K01: daily invoice lines) decays as $i^{-0.9}$; a few large sellers, a long tail
D2	partition count	8	starting capacity; sensitivity measured with 16 partitions
D3	active window	5 days	the shipment age that reads and writes fall into: a delivered shipment is neither queried nor updated

Three access patterns come from K01: a single-record read by tracking number, the carrier’s state event write, and the seller’s thirty-day period report. The first two fall into the same shipment set because of D3, so they share the same distribution.

// partition/strategy.mjs — the same key distributed to partitions by three separate rules.
// MODEL: partitions are counters, not a real dataset; results are deterministic.
export const DAILY = 400_000, RETENTION = 730, PERIOD = 30;   // V3, V12, V11
export const SELLER = 4000, EXPONENT = 0.9, WINDOW = 5;        // D1, D3
export const STORE_REQUEST = 138.89, STORED_GB = 712.48;       // K01 computed values

export function shares(exponent = EXPONENT, factor = 1) {
  const p = []; let H = 0;
  for (let i = 1; i <= SELLER; i++) { const a = Math.pow(i, -exponent) * (i === 1 ? factor : 1); p.push(a); H += a; }
  return p.map((a) => a / H);
}
export const hash = (n) => {
  let z = Math.imul(n ^ (n >>> 16), 0x21f0aaad) >>> 0;
  z = Math.imul(z ^ (z >>> 15), 0x735a2d97) >>> 0;
  return (z ^ (z >>> 15)) >>> 0;
};
export const ratio = (k) => Math.max(...k) / (k.reduce((a, b) => a + b, 0) / k.length);

export function initialAssign(group, P) {           // in decreasing order of volume, to the least-loaded partition
  const load = new Array(P).fill(0), placement = new Map();
  for (const x of [...group].sort((a, b) => b.weight - a.weight)) {
    let least = 0; for (let p = 1; p < P; p++) if (load[p] < load[least]) least = p;
    placement.set(x.name, least); load[least] += x.weight;
  }
  return placement;
}
export const loadCalc = (group, placement, P) => {
  const y = new Array(P).fill(0);
  for (const x of group) y[placement.get(x.name)] += x.weight;
  return y;
};

export function requestRange(P) {              // partition = the number range the tracking number falls into
  const sliceSize = (RETENTION * DAILY) / P, k = new Array(P).fill(0);
  for (let g = RETENTION - WINDOW; g < RETENTION; g++)
    for (let s = 0; s < DAILY; s += 1000) k[Math.floor((g * DAILY + s) / sliceSize)] += 1000;
  return k;
}
export function requestHash(P) {               // partition = the hash of the tracking number
  const k = new Array(P).fill(0);
  for (let g = RETENTION - WINDOW; g < RETENTION; g++)
    for (let s = 0; s < DAILY; s++) k[hash(g * DAILY + s) % P] += 1;
  return k;
}

export function table(P) {
  const group = shares().map((a, i) => ({ name: `${i}`, weight: a }));
  const D = loadCalc(group, initialAssign(group, P), P);
  const busiest = Math.max(...D) / D.reduce((a, b) => a + b, 0);
  return [
    ["range", ratio(requestRange(P)), 1, PERIOD * DAILY, 1],
    ["hash", ratio(requestHash(P)), P, PERIOD * DAILY, 1],
    ["lookup table", ratio(D), 1, Math.round(PERIOD * DAILY * busiest), 2],
  ];
}

if (import.meta.filename === process.argv[1]) {
  const pay = shares();
  console.log(`D1: ${SELLER} sellers, largest share ${(pay[0] * 100).toFixed(2)}%, ` +
    `first eight ${(pay.slice(0, 8).reduce((a, b) => a + b, 0) * 100).toFixed(2)}%, ` +
    `smallest ${(DAILY * pay[SELLER - 1]).toFixed(1)} shipments/day`);
  for (const P of [8, 16]) {
    console.log(`\nP = ${P} partitions`);
    console.log("strategy          request hot spot  period report partition  scanned records  store touches");
    for (const [name, i, b, t, d] of table(P))
      console.log(name.padEnd(17) + i.toFixed(2).padStart(17) + String(b).padStart(20) +
        t.toLocaleString("en-US").padStart(15) + String(d).padStart(15));
  }
  console.log(`\nK01 tie-back: requests reaching the store ${STORE_REQUEST} req/s, stored ${STORED_GB} GB, P = 8`);
  for (const [name, i, , , d] of table(8))
    console.log(`  ${name.padEnd(15)} busiest partition ${(STORE_REQUEST * i / 8).toFixed(2).padStart(6)} req/s` +
      ` and ${(STORED_GB / 8).toFixed(2)} GB | total reaching the store ${(STORE_REQUEST * d).toFixed(2)} req/s`);
}

D1: 4000 sellers, largest share 7.41%, first eight 21.92%, smallest 17.0 shipments/day

P = 8 partitions
strategy          request hot spot  period report partition  scanned records  store touches
range                         8.00                   1     12,000,000              1
hash                          1.00                   8     12,000,000              1
lookup table                  1.00                   1      1,500,137              2

P = 16 partitions
strategy          request hot spot  period report partition  scanned records  store touches
range                        16.00                   1     12,000,000              1
hash                          1.00                  16     12,000,000              1
lookup table                  1.19                   1        889,566              2

K01 tie-back: requests reaching the store 138.89 req/s, stored 712.48 GB, P = 8
  range           busiest partition 138.89 req/s and 89.06 GB | total reaching the store 138.89 req/s
  hash            busiest partition  17.42 req/s and 89.06 GB | total reaching the store 138.89 req/s
  lookup table    busiest partition  17.36 req/s and 89.06 GB | total reaching the store 277.78 req/s

These numbers belong to the computed-value class: they follow arithmetically from D1–D3 and K01’s assumptions, and none depends on the environment.

No Strategy Wins Outright

The hot spot column divides the busiest partition’s load by the per-partition average: 1.00 is perfect balance, 8.00 means only one of eight partitions is doing any work.

Range partitioning splits nothing in a partitioned store. The ratio is 8.00 — D3 is why: the shipments read and written are from the last five days, and since consecutive tracking numbers fall into the same range, they all land in the last partition. The other seven partitions carry 725 days of data and see almost no requests. The storage column confirms this: the stored 712.48 GB splits evenly, 89.06 GB per partition. Range partitioning balances storage, not requests — and the row K01 wants moved is the request row.

Hash partitioning balances requests, and spreads the query. The ratio is 1.00: the hash of twelve million tracking numbers falls almost evenly across eight partitions. The cost shows up in the period report column: a seller’s records spread across eight partitions, so the thirty-day report has to touch all eight. Total scanned records stay the same (12,000,000), but the query now falls into the scatter-gather behavior measured in the Sharding Patterns lesson.

The lookup table delivers both, at the cost of one extra touch. Placing sellers in decreasing order of volume into the least-loaded partition brings the ratio to 1.00, and since a seller’s records all stay in one partition, the period report touches one partition. Scanned records come out to 1,500,137 instead of 12,000,000: the window is still thirty days, but that partition only holds the sellers assigned to it. The eightfold reduction comes from there.

The cost sits in the last column: every access reads the mapping, then goes to the data — two store touches per access. K01’s requests reaching the store row climbs from 138.89 to 277.78. Read the two together: the busiest partition’s load drops from 138.89 to 17.36 while total requests reaching the store doubled, because the lookup table itself sees the entirety of that request — a ninth hot spot built to balance the other eight. Whether this table stays in memory is a caching decision, the next topic’s question.

The P = 16 rows give the sensitivity. Range’s ratio climbs to 16.00: adding partitions grows the hot spot. The lookup table’s scanned records drop to 889,566 while its ratio climbs to 1.19, since the largest seller’s 7.41 percent share exceeds a single partition’s 6.25 percent share.

Rebalancing

Placement is not set up once and left alone. When a seller grows, the three strategies each do something different.

// partition/rebalance.mjs — the behavior of the three strategies when the largest seller triples.
// MODEL: the rebalancer starts from the current placement and moves a single group at a time
// from the busiest partition to the least busy; moved weight is summed. Results are deterministic.
import { shares, initialAssign, loadCalc, ratio, requestRange, requestHash, SELLER, PERIOD }
  from "./strategy.mjs";
const P = 8, FACTOR = 3, TARGET = 1.20;

function moveLeast(group, placement0, target) {
  const placement = new Map(placement0), y = loadCalc(group, placement, P);
  let moved = 0, steps = 0;
  while (ratio(y) > target) {
    let h = 0, c = 0;
    for (let p = 1; p < P; p++) { if (y[p] > y[h]) h = p; if (y[p] < y[c]) c = p; }
    const candidate = group.filter((x) => placement.get(x.name) === h && y[c] + x.weight < y[h])
      .sort((a, b) => b.weight - a.weight)[0];
    if (candidate === undefined) break;
    placement.set(candidate.name, c); y[h] -= candidate.weight; y[c] += candidate.weight;
    moved += candidate.weight; steps += 1;
  }
  return { placement, ratio: ratio(y), moved, steps };
}
const format = (r) => `ratio ${r.ratio.toFixed(3)} | moved keys ${(r.moved * 100).toFixed(2)}%` +
  ` | ${r.steps} moves`;

const before = shares(), after = shares(0.9, FACTOR);
const gAfter = after.map((a, i) => ({ name: `${i}`, weight: a }));
const placement0 = initialAssign(before.map((a, i) => ({ name: `${i}`, weight: a })), P);
console.log(`largest seller share ${(before[0] * 100).toFixed(2)}% -> ${(after[0] * 100).toFixed(2)}%`);
const [rR, rH] = [ratio(requestRange(P)), ratio(requestHash(P))];   // both independent of the seller
console.log(`range: ratio ${rR.toFixed(2)} -> ${rR.toFixed(2)} | the move does not remove the write hot spot`);
console.log(`hash:  ratio ${rH.toFixed(2)} -> ${rH.toFixed(2)} | the partition comes from the tracking number`);
console.log(`lookup table, untouched: ratio ${ratio(loadCalc(gAfter, placement0, P)).toFixed(3)}`);
console.log(`lookup table, group = seller:     ${format(moveLeast(gAfter, placement0, TARGET))}`);

const gSplit = [];                                  // only the hot seller is split into day groups
for (let g = 0; g < PERIOD; g++) gSplit.push({ name: `0/${g}`, weight: after[0] / PERIOD });
for (let i = 1; i < SELLER; i++) gSplit.push({ name: `${i}`, weight: after[i] });
const placementSplit = new Map(placement0);
for (let g = 0; g < PERIOD; g++) placementSplit.set(`0/${g}`, placement0.get("0"));
const r = moveLeast(gSplit, placementSplit, TARGET);
const spread = new Set();
for (let g = 0; g < PERIOD; g++) spread.add(r.placement.get(`0/${g}`));
console.log(`lookup table, group = seller-day: ${format(r)}`);
console.log(`  cost: the hot seller's period report now touches ${spread.size} partitions (others: 1),` +
  ` lookup rows ${SELLER} -> ${gSplit.length}`);

console.log("\nD1 sensitivity: as the distribution exponent grows, the largest unsplit group sets a floor");
for (const exponent of [0.9, 1.1, 1.3]) {
  const p = shares(exponent);
  console.log(`  exponent ${exponent.toFixed(1)}: largest seller share ${(p[0] * 100).toFixed(2)}%,` +
    ` best reachable ratio ${Math.max(1, p[0] * P).toFixed(2)}`);
}

largest seller share 7.41% -> 19.37%
range: ratio 8.00 -> 8.00 | the move does not remove the write hot spot
hash:  ratio 1.00 -> 1.00 | the partition comes from the tracking number
lookup table, untouched: ratio 1.904
lookup table, group = seller:     ratio 1.549 | moved keys 4.43% | 468 moves
lookup table, group = seller-day: ratio 1.181 | moved keys 9.04% | 14 moves
  cost: the hot seller's period report now touches 8 partitions (others: 1), lookup rows 4000 -> 4029

D1 sensitivity: as the distribution exponent grows, the largest unsplit group sets a floor
  exponent 0.9: largest seller share 7.41%, best reachable ratio 1.00
  exponent 1.1: largest seller share 16.07%, best reachable ratio 1.29
  exponent 1.3: largest seller share 27.36%, best reachable ratio 2.19

In the hash row, the ratio stays at 1.00 even as the seller triples, because the partition comes from the tracking number, not the seller. Hash partitioning produces no seller-driven hot spots — but it can also never bring the period report down to a single partition. In the range row, moving anything is pointless: the hot spot comes from the time axis, not a specific seller.

The lookup table’s three rows are the real measurement. Left untouched, the ratio is 1.904. Moving the largest seller whole only brings it to 1.549, after 468 moves and 4.43 percent of the keys, then it stops: that partition now holds one seller worth 19.37 percent, and unsplit it cannot fall below 1.549 times the eight partitions’ average. The largest unsplit group is the floor on the balance; the sensitivity rows repeat this: at exponent 1.3, the largest seller alone holds 27.36 percent, and the best reachable ratio is 2.19.

The only way to lower the floor is to redefine the group. Splitting the hot seller into seller-day groups brings the ratio to 1.181 in 14 moves — 9.04 percent of keys moved, twice the first attempt, but reaching a ratio the first could not. The cost: the hot seller’s period report now touches eight partitions, so the lookup table’s entire gain there was given back, while the other 3,999 sellers still touch a single partition. The decision: the lookup table builds balance selectively; the cost falls only on the split group’s query. The Sharding Patterns lesson measured the moved fraction when the shard count changes; here the question differs — fixing the placement while the partition count stays fixed.

Summary

• Partitioning strategy converts a key into a partition; it is not key selection, and the same key produces three different placements under three rules.
• Range partitioning distributed 712.48 GB evenly across eight partitions but never split requests: the hot spot ratio is 8.00, and the busiest partition sees all of K01’s 138.89 req/s.
• Hash partitioning brought the ratio to 1.00 (17.42 req/s per partition) but spread the seller’s period report across all eight partitions.
• The lookup table brought the ratio to 1.00, kept the report in a single partition, and dropped scanned records from 12,000,000 to 1,500,137; in exchange it required two store touches per access and pushed requests reaching the store from 138.89 to 277.78.
• The largest unsplit group sets a floor on the balance: when the largest seller tripled, the best seller-level ratio stayed at 1.549; splitting the group into seller-days moved 9.04 percent of the keys, brought the ratio to 1.181, and spread that seller’s report across eight partitions.

Next Step

The three strategies share a common silence: all of them settle where the data goes, none asks what shape it stands in. The 1,500,137 records the lookup table scans is the count read to produce the seller’s report, and part of that comes from the schema itself: completing a report means pulling tariff, zone, and contract records alongside the shipment record, so the read path spans multiple tables even within a single partition. The next lesson shortens that path: what gets copied alongside the record being read, how many tables and records the copy drops from the read, how many steps that stretches the write path by, and how much the stored 712.48 GB and the daily 976 MB growth grow because of it.