Managed Key-Value Service

In the previous two lessons, nearly every kept decision turned out to be a setting: a sticky window can be changed, a replica can be closed. In the managed key-value service, the table turns. Data lands according to the value of a field called the partition key, and once that key is chosen, which queries can be served is fixed.

The mechanics of partitioning — whether the split is by range or by hash, how much data rebalancing moves — were measured in the Advanced Data Scaling course and are not repeated here. What this lesson measures is specific to the cloud context: what the key does to the capacity model, and the irreversibility of changing it.

The Unserved Query

If a query fixes the partition key by equality, the request goes straight to the relevant partition; if it does not, the service has no way to know where to look, and the only option is scanning the whole table. At this scale, a scan is not a query but a batch job; such an access pattern is counted as an unserved query and stands as its own column below.

The second measure is how servable requests spread across partitions: in a load spread over sixteen partitions, the gap between requests per partition and what the busiest partition receives is the hot partition itself.

Mechanics

MD13 — the fictional measurement network holds 40,000 meters, 12 regions, and 26,000 subscribers; each meter writes a reading every 15 minutes (96 a day), and retention is 90 days: 345.6M items, 180 bytes each, 62.2 GB. Region shares run from 27 down to 1; the central region carries roughly a quarter of the meters. MD14 — the access mix: a meter’s last 24 hours is 38%, a single reading record 22%, a region’s daily total 17%, a subscriber’s latest readings 10%, today’s threshold-exceeding readings 8%, the last hour’s readings across the board 5%. MD15 — the service spreads data across 16 partitions; in provisioned capacity, the total is split equally across the partitions, and in this model a partition cannot exceed its own share. Real services soften that rigidity with adaptive capacity: a hot partition may go above its own share as long as it stays under the table’s total capacity and the per-partition ceiling. The multipliers below are therefore an upper bound. MD16 — the request rate averages 1,200/s, and the daily profile is a fictional 24-hour multiplier array. MD17 — fictional price: provisioned capacity is 0.12 unit/capacity-hour, per-request is 0.25 unit/1,000 requests, a write unit is 5 times a read. MD18 — the key-change job runs at 12,000 items/s. MD14 is the determinant; if the weights change, the unserved-request share moves in the same direction.

// md/model.mjs — MANAGED KEY-VALUE SERVICE model: partition key candidates are run over the
// fictional regional measurement network's meter readings. Partitioning MECHANICS (range vs.
// hash, rebalancing) were measured in M17/K05 and are not repeated; what is measured here is
// how well the key's VALUE DISTRIBUTION fits the access pattern. Hand-written generator, seed visible.
export const REGION = [["central", 27], ["north", 14], ["harbor", 11], ["industrial", 9], ["west", 8],
  ["east", 7], ["highland", 6], ["coast", 5], ["plain", 5], ["dam", 4], ["hill", 3], ["island", 1]];
export const METERS = 40000, SUBSCRIBERS = 26000, READINGS_PER_DAY = 96, RETENTION = 90, PARTITIONS = 16;
export const ITEMS = METERS * READINGS_PER_DAY * RETENTION, ITEM_BYTES = 180;
export const TODAY = RETENTION - 1;

// The meter registry is a closure: given a meter_id its region is known, given a subscriber its meters are.
export function registry(seed = 20260803) {
  let s = seed % 2147483647;
  const rand = () => (s = (s * 48271) % 2147483647) / 2147483647;
  const total = REGION.reduce((t, [, w]) => t + w, 0);
  const regionOf = new Int32Array(METERS), subscriberOf = new Int32Array(METERS);
  const regionCount = new Array(REGION.length).fill(0), metersOfSubscriber = new Map();
  for (let i = 0; i < METERS; i += 1) {
    let x = rand() * total, region = 0;
    for (let j = 0; j < REGION.length; j += 1) { if (x < REGION[j][1]) { region = j; break; } x -= REGION[j][1]; }
    regionOf[i] = region; regionCount[region] += 1;
    const sub = Math.floor(rand() * SUBSCRIBERS);
    subscriberOf[i] = sub;
    if (!metersOfSubscriber.has(sub)) metersOfSubscriber.set(sub, []);
    metersOfSubscriber.get(sub).push(i);
  }
  return { rand, regionOf, subscriberOf, regionCount, metersOfSubscriber };
}

// An access pattern is defined by which fields it can FIX when building the query (A1..A6, per MD14);
// if the partition key is not among those fields, the query is unserved.
export const ACCESS = [38, 17, 22, 8, 10, 5];

export function generateRequests(reg, count = 300000) {
  const weight = ACCESS, total = weight.reduce((a, b) => a + b, 0);
  const requests = [];
  for (let i = 0; i < count; i += 1) {
    let x = reg.rand() * total, kind = 0;
    for (let j = 0; j < weight.length; j += 1) { if (x < weight[j]) { kind = j; break; } x -= weight[j]; }
    const meter = Math.floor(reg.rand() * METERS);
    const subscriber = reg.subscriberOf[Math.floor(reg.rand() * METERS)];
    const past = Math.floor(reg.rand() * RETENTION);          // A2 and A3 also look at the past
    const day = kind === 0 ? TODAY                            // A1 "last 24 hours" is always today
      : kind === 3 ? (reg.rand() < 0.7 ? TODAY : TODAY - Math.floor(reg.rand() * 7)) : past;
    requests.push({ kind, meter, region: reg.regionOf[meter], subscriber, day });
  }
  return requests;
}

// Which partition-key VALUES a request touches; null = the key cannot be fixed, i.e. the
// query is UNSERVED (the whole table is scanned).
export function keysFor(q, candidate, reg) {
  const metersOf = () => reg.metersOfSubscriber.get(q.subscriber) ?? [q.meter];
  if (candidate === "region") {
    if (q.kind === 3 || q.kind === 5) return null;
    if (q.kind === 4) return [...new Set(metersOf().map((i) => reg.regionOf[i]))].map((b) => "b" + b);
    return ["b" + q.region];
  }
  if (candidate === "day") {
    if (q.kind === 0) return ["g" + q.day, "g" + Math.max(0, q.day - 1)];
    return ["g" + (q.kind === 4 || q.kind === 5 ? TODAY : q.day)];
  }
  if (q.kind === 1 || q.kind === 3 || q.kind === 5) return null;   // meter_id cannot be fixed
  return q.kind === 4 ? metersOf().map((i) => "s" + i) : ["s" + q.meter];
}

export const hash = (m) => { let h = 2166136261;
  for (const c of m) h = Math.imul(h ^ c.charCodeAt(0), 16777619); return (h >>> 0) % PARTITIONS; };

// md/measure.mjs — three partition key candidates, hot partition, unserved queries, capacity model
import { registry, generateRequests, keysFor, hash, ACCESS, REGION, METERS, SUBSCRIBERS,
  READINGS_PER_DAY, RETENTION, PARTITIONS, ITEMS, ITEM_BYTES } from "./model.mjs";

const s = (x, n) => String(x).padStart(n);
const pct = (a, b) => (100 * a / b).toFixed(2) + "%";
const reg = registry();
const requests = generateRequests(reg);
const CANDIDATE = [["region | time", "region", REGION.length], ["day | meter_id#time", "day", RETENTION],
  ["meter_id | time", "meter_id", METERS]];
console.log(`${METERS} meters, ${REGION.length} regions, ${SUBSCRIBERS} subscribers, ${READINGS_PER_DAY} readings/day, ` +
  `${RETENTION} days retention -> ${(ITEMS / 1e6).toFixed(1)}M items, ${(ITEMS * ITEM_BYTES / 1e9).toFixed(1)} GB.`);
console.log(`measured over ${requests.length} requests. Seed 20260803.\n`);

const results = new Map();
console.log("partition key        | distinct vals | unserved patterns      | unserved requests    | requests/partition (avg / busiest)  | hot partition");
console.log("---------------------|---------------|------------------------|----------------------|-------------------------------------|--------------");
for (const [label, candidate, distinct] of CANDIDATE) {
  const load = new Array(PARTITIONS).fill(0);
  let unserved = 0;
  const patterns = new Set();
  for (const q of requests) {
    const keys = keysFor(q, candidate, reg);
    if (keys === null) { unserved += 1; patterns.add(q.kind); continue; }
    for (const value of keys) load[hash(value)] += 1;   // each value is a separate partition request
  }
  const total = load.reduce((a, b) => a + b, 0), busiest = Math.max(...load);
  results.set(candidate, { hot: busiest / total, unserved });
  console.log(`${label.padEnd(20)} | ${s(distinct, 13)} | ${s(patterns.size + " / " + ACCESS.length, 22)} | ` +
    `${s(unserved + " (" + pct(unserved, requests.length) + ")", 20)} | ` +
    `${s(Math.round(total / PARTITIONS) + " / " + busiest, 35)} | ${s(pct(busiest, total), 11)}`);
}
console.log(`ideal hot-partition share for ${PARTITIONS} partitions is ${(100 / PARTITIONS).toFixed(2)}%; ` +
  `requests per partition were counted over the partitions touched by servable requests.`);

// Capacity model. In provisioned capacity, the total is split equally across PARTITIONS shares;
// a partition cannot exceed its own share, so the hot partition forces the total up.
const BASELINE = 1200, PRICE_PROVISIONED = 0.12, PRICE_REQUEST = 0.25;
const PROFILE = [0.22, 0.18, 0.16, 0.16, 0.20, 0.35, 0.70, 1.20, 1.75, 2.10, 2.20, 2.05,
  1.80, 1.70, 1.80, 2.00, 2.30, 2.55, 2.45, 1.90, 1.30, 0.85, 0.50, 0.32];
const avg = PROFILE.reduce((a, b) => a + b, 0) / 24;
const rate = PROFILE.map((p) => BASELINE * p / avg);
const dailyRequests = rate.reduce((a, b) => a + b, 0) * 3600;
const peak = Math.max(...rate);
console.log(`\nload profile: average ${BASELINE} requests/s, peak ${peak.toFixed(0)} requests/s ` +
  `(${(peak / BASELINE).toFixed(2)}x), daily ${(dailyRequests / 1e6).toFixed(1)}M requests.`);
console.log(`fictional price: provisioned capacity ${PRICE_PROVISIONED} unit/capacity-hour, per request ` +
  `${PRICE_REQUEST} unit/1000 requests.`);
console.log("partition key        | over-provision  | provisioned (unit/day)  | per-request  | requests throttled at peak");
console.log("---------------------|-----------------|-------------------------|--------------|---------------------------");
for (const [label, candidate] of CANDIDATE) {
  const h = results.get(candidate).hot;
  const provisioned = PARTITIONS * h * peak * 24 * PRICE_PROVISIONED;   // unthrottled provision = PARTITIONS * h * peak
  const ceiling = peak / PARTITIONS;                       // provisioning that only covers the total: C = peak
  const throttled = rate.reduce((t, r) => t + Math.max(0, h * r - ceiling) * 3600, 0);
  console.log(`${label.padEnd(20)} | ${s((PARTITIONS * h).toFixed(2) + "x", 15)} | ${s(provisioned.toFixed(0), 23)} | ` +
    `${s((dailyRequests / 1000 * PRICE_REQUEST).toFixed(0), 12)} | ${s((throttled / 1e6).toFixed(1) + "M", 29)}`);
}

// Irreversible item: changing the partition key means rewriting the data.
const TRANSFER_RATE = 12000, WRITE_FACTOR = 5;
const equivalent = ITEMS * (1 + WRITE_FACTOR), duration = ITEMS / TRANSFER_RATE / 3600;
const cost = equivalent / 1000 * PRICE_REQUEST, dailyOpCost = dailyRequests / 1000 * PRICE_REQUEST;
const exportSize = ITEMS * ITEM_BYTES / 1e9;
console.log(`\nchanging the key: ${(ITEMS / 1e6).toFixed(1)}M items are read and rewritten under the new ` +
  `key (write is ${WRITE_FACTOR}x the read unit) -> equivalent requests ${(equivalent / 1e9).toFixed(2)}G.`);
console.log(`cost ${(cost / 1000).toFixed(1)}K fictional units = ${(cost / dailyOpCost).toFixed(0)}x daily ` +
  `operations (${dailyOpCost.toFixed(0)} units); duration ${duration.toFixed(1)} h ` +
  `(${TRANSFER_RATE} items/s), and a double-write window for the whole duration.`);
console.log(`leaving the service is cheaper: ${exportSize.toFixed(1)} GB export, over the internet at ` +
  `9 units/GB = ${(exportSize * 9).toFixed(0)} fictional units. Distinct value count (${REGION.length} for region) ` +
  `is the run-independent ceiling on partition count.`);

40000 meters, 12 regions, 26000 subscribers, 96 readings/day, 90 days retention -> 345.6M items, 62.2 GB.
measured over 300000 requests. Seed 20260803.

partition key        | distinct vals | unserved patterns      | unserved requests    | requests/partition (avg / busiest)  | hot partition
---------------------|---------------|------------------------|----------------------|-------------------------------------|--------------
region | time        |            12 |                  2 / 6 |       39168 (13.06%) |                       18545 / 78103 |      26.32%
day | meter_id#time  |            90 |                  0 / 6 |            0 (0.00%) |                      25888 / 184840 |      44.62%
meter_id | time      |         40000 |                  3 / 6 |       89856 (29.95%) |                       16010 / 16312 |       6.37%
ideal hot-partition share for 16 partitions is 6.25%; requests per partition were counted over the partitions touched by servable requests.

load profile: average 1200 requests/s, peak 2389 requests/s (1.99x), daily 103.7M requests.
fictional price: provisioned capacity 0.12 unit/capacity-hour, per request 0.25 unit/1000 requests.
partition key        | over-provision  | provisioned (unit/day)  | per-request  | requests throttled at peak
---------------------|-----------------|-------------------------|--------------|---------------------------
region | time        |           4.21x |                   28978 |        25920 |                         16.8M
day | meter_id#time  |           7.14x |                   49127 |        25920 |                         34.7M
meter_id | time      |           1.02x |                    7010 |        25920 |                          0.0M

changing the key: 345.6M items are read and rewritten under the new key (write is 5x the read unit) -> equivalent requests 2.07G.
cost 518.4K fictional units = 20x daily operations (25920 units); duration 8.0 h (12000 items/s), and a double-write window for the whole duration.
leaving the service is cheaper: 62.2 GB export, over the internet at 9 units/GB = 560 fictional units. Distinct value count (12 for region) is the run-independent ceiling on partition count.

Three Candidates, Three Different Failures

No candidate comes out ahead; each one sinks in a different column.

region matches the operating structure and produces a hot partition. While the average is 18,545 requests per partition, the busiest partition takes 78,103: 26.32%, four times the ideal 6.25%. The reason is that one of twelve distinct values carries a quarter of the meters; adding partitions does not fix this, because a single key value cannot be split.

day serves every query and produces the worst hot partition. Unserved patterns are zero — the only zero in the table. In exchange, today’s partition takes 184,840 requests, seven times the average, 44.62% of requests: on a monotonically increasing key, most new writes and reads pile onto a single value.

meter_id balances flawlessly and cannot serve nearly a third of requests. Average 16,010, busiest partition 16,312 — the hot partition sits at 6.37%, within 2% of the ideal. Against that, three of the six patterns — the region total, the threshold scan, and the last hour’s readings — never fix the key at all: 29.95% of requests, 89,856 of them. These do not run slowly; they do not run at all.

The Hot Partition Passes into the Bill Through the Capacity Model

The second table converts the hot partition into money. The total allocated splits equally across partitions and no partition may exceed its own share (MD15); if the hot partition’s share is h, the capacity that must be provisioned to avoid throttling is 16 x h x peak. On a service that offers adaptive capacity the factor is smaller but not gone — the per-partition ceiling and the total capacity limit stay in place. The first column gives this factor: 1.02x for meter_id, 4.21x for region, 7.14x for day. On a key with a hot partition, five-sixths of the provisioned capacity never gets used: what the capacity buys is not work, it is imbalance.

The daily cost follows from this. With meter_id, provisioned capacity is 7,010 fictional units against 25,920 for the per-request model — the provisioned model is 3.7 times cheaper. With region, provisioned rises to 28,978 and overtakes the per-request model; with day it reaches 49,127. What decides which capacity model is cheaper is not the load, it is the partition key. The per-request model is indifferent to imbalance; the provisioned model bills it by its factor.

The last column shows what happens when provisioning is thin: allocate just enough to cover the total peak (2,389 units) and meter_id is never throttled, region throttles 16.8M requests a day, day throttles 34.7M. The total capacity is sufficient; it is only the partition that gets throttled.

The Cost of Changing the Key

Everything measured so far looks like a choice; the last block counts why it is not. Changing the partition key is not a setting change: all 345.6M items are read and rewritten under the new key. Since a write unit is five times a read, the equivalent request count is 2.07 billion, and the fictional cost is 518.4 thousand units — 20 times the daily operating cost. The duration is 8 hours, and through that whole span the application writes to two tables at once, because writes arriving while the migration runs still need somewhere to land. The major version upgrade on the relational side was also one-way, but the data stayed in place; here, reversing means rewriting the data itself. Leaving the service outright is cheaper: a 62.2 GB export and 560 fictional units. Changing the key costs 900 times more than leaving the service — what binds you is not the provider, it is the schema.

Summary

• With the region key, the hot partition sits at four times the ideal share (26.32%), and twelve distinct values cap the partition count; adding partitions does not fix the imbalance.
• day serves all six access patterns, but today’s partition takes 184,840 requests (44.62%); meter_id balances flawlessly at 16,010 against 16,312, but cannot serve three of the six patterns — 29.95% of requests.
• The hot partition converts into over-provisioning in provisioned capacity: 1.02x / 4.21x / 7.14x. What decides which capacity model is cheaper is the partition key, not the load (7,010 against 25,920 fictional units).
• Even provisioning that covers the total peak throttles 16.8M and 34.7M requests a day on a hot key.
• Changing the key means rewriting 345.6M items: 8 hours, 518.4 thousand fictional units, and an 8-hour double-write window — 900 times the cost of leaving the service outright.

Next Step

The table leaves one gap. On meter_id, the best-balanced key, 29.95% of requests go unserved, and the fix is not changing the key — that door closed at 518.4 thousand fictional units. Managed key-value services offer a secondary index for this gap: it places the same data a second time, under a different key. The next lesson counts how many of the three unserved patterns a secondary index recovers, and what it costs in exchange — extra writes, extra storage, lag time — and models a change stream with a consumer, measuring event order, reprocessing, and the missed window once the stream’s retention runs out.