--- title: Clustering source: 'https://academia.sh/en/courses/in-memory-stores/clustering' course: 'In-Memory Stores and Caching Systems' language: en updated: '2026-08-23T07:00:43+00:00' license: 'CC BY-SA 4.0' --- # Clustering Partitioning the key space: mapping a key to a slot by hash and a slot to a node, shown with a hand-written hash function, measuring the multi-key transaction's cross-node constraint across four node counts and comparing the single-node landing rate against the formula one over n to the power of k minus one, tagging keys into the same partition raising transactions to one hundred percent while narrowing the usable slot count to six, and counting how the tag's granularity trades multiplied bytes held against imbalance in load per node. The previous two lessons assumed that the entire data set fits on a single node. Replication produced copies of that set, failover promoted one of the copies into service; both multiplied the bytes stored, neither split it. When catalog and loan records outgrow a single node's memory budget, only one path remains: splitting the key space and giving each node only a share of it. This lesson covers that split. Sharding and shard-key selection were measured in the Scaling the Data Layer and Non-Relational Data Models courses; they are not repeated here. This lesson's question is different: how does the split decision constrain the in-memory store's transaction semantics, and what does removing that constraint cost in the memory budget. ## From Key to Node Partitioning is two steps. A key passes through a **hash** function and lands on one of a fixed number of **slots**; slot ranges are distributed across nodes. The slot layer in between means that adding a node only moves slot ranges — keys do not need to be rehashed. The mechanism below has 16,384 slots, and the hash function is hand-written. The direct consequence is this: which node two keys land on is independent of each other. If a loan transaction touches the catalog entry, the loan counter, and the waiting queue together, these three keys being on the same node is not a design decision, it is a coincidence. When they are not on the same node, the transaction cannot run on a single node — this is the **multi-key transaction's cross-node constraint**. ## Mechanism The mechanism is a **model**: no real cluster, network, or node is set up; a node is a number, and which node a key falls on is computed from the hash. **CU6 — branch shares are not equal: six branches carry 34, 24, 16, 12, 9, and 5 percent of loans.** Rationale: library branches are not equally sized, and the cost of the tagging decision shows up exactly in this inequality. **CU7 — two transaction shapes are measured: T1 touches the catalog entry, the loan counter, and the waiting queue; T2 adds the branch's concurrent-loan counter to that.** Rationale: an unbounded loan and one that checks a branch limit touch a different number of keys, and the cross-node constraint depends exponentially on key count. ```js // clustering/model.mjs — key-space partitioning is an IN-PROCESS MODEL. No real cluster, network, or // node is set up; a node is a number and which node a key falls on is computed from the hash. // The hash function (FNV-1a, 32 bit) is hand-written here. export const SLOTS = 16384, CATALOG_BYTES = 240, LOAN_BYTES = 96, QUEUE_BYTES = 128, COUNTER_BYTES = 64; export function hash(s) { let h = 0x811c9dc5; for (let i = 0; i < s.length; i += 1) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193) >>> 0; } return h >>> 0; } export function slotOf(key) { // if the key carries a tag, ONLY the tag is hashed const a = key.indexOf("{"), b = key.indexOf("}"); return hash(a >= 0 && b > a + 1 ? key.slice(a + 1, b) : key) % SLOTS; } export const nodeOf = (slot, n) => Math.floor(slot * n / SLOTS); // equal slot ranges export function generator(seed) { // linear congruential generator; seed is visible let s = seed >>> 0; return () => { s = (Math.imul(s, 1103515245) + 12345) >>> 0; return s / 4294967296; }; } // Branch shares are not equal: the largest branch carries a third of all loans. export const SHARE = [0.34, 0.24, 0.16, 0.12, 0.09, 0.05]; export function data({ books = 3000, loans = 12000, queueShare = 0.25, seed = 20260731 }) { const rnd = generator(seed), records = [], queue = new Set(); const threshold = SHARE.map((p, i) => SHARE.slice(0, i + 1).reduce((a, b) => a + b, 0)); for (let i = 0; i < loans; i += 1) { const x = rnd(), s = threshold.findIndex((t) => x < t); records.push([s < 0 ? SHARE.length - 1 : s, Math.floor(rnd() * books)]); } for (let k = 0; k < books; k += 1) if (rnd() < queueShare) queue.add(k); return { books, records, queue }; } // Three tagging schemes. The tag determines which part of the key gets hashed. export const SCHEME = { none: { catalog: (k) => `catalog:${k}`, loan: (s, k) => `loan:${s}:${k}`, queue: (k) => `queue:${k}`, counter: (s) => `branch:${s}:openLoans` }, branch: { catalog: (k, s) => `{branch:${s}}catalog:${k}`, loan: (s, k) => `{branch:${s}}loan:${k}`, queue: (k, s) => `{branch:${s}}queue:${k}`, counter: (s) => `{branch:${s}}openLoans` }, book: { catalog: (k) => `{book:${k}}catalog:${k}`, loan: (s, k) => `{book:${k}}loan:${s}`, queue: (k) => `{book:${k}}queue:${k}`, counter: (s) => `branch:${s}:openLoans` }, }; export function run({ scheme, nodes, d }) { const S = SCHEME[scheme], bytes = new Map(), slots = new Set(); const add = (key, b) => { bytes.set(key, b); slots.add(slotOf(key)); }; let t1 = 0, t2 = 0; for (const [s, k] of d.records) { add(S.catalog(k, s), CATALOG_BYTES); // if the tag is a branch, the catalog entry MULTIPLIES add(S.loan(s, k), LOAN_BYTES); if (d.queue.has(k)) add(S.queue(k, s), QUEUE_BYTES); add(S.counter(s), COUNTER_BYTES); const g = [S.catalog(k, s), S.loan(s, k), S.queue(k, s)].map((a) => nodeOf(slotOf(a), nodes)); if (g.every((x) => x === g[0])) t1 += 1; // T1: catalog + loan + queue if (g.every((x) => x === g[0]) && nodeOf(slotOf(S.counter(s)), nodes) === g[0]) t2 += 1; } const load = Array(nodes).fill(0), count = Array(nodes).fill(0); for (const [key, b] of bytes) { const n = nodeOf(slotOf(key), nodes); load[n] += b; count[n] += 1; } const total = load.reduce((a, b) => a + b, 0); return { slots: slots.size, keys: bytes.size, total, load, count, mostLoaded: Math.max(...load), imbalance: Math.max(...load) / (total / nodes), t1: t1 / d.records.length, t2: t2 / d.records.length }; } ``` ```js // clustering/measure.mjs — same data set: first node count, then three tagging schemes import { data, run, slotOf, nodeOf, SLOTS } from "./model.mjs"; const s = (x, n) => String(x).padStart(n); const e = (x, n) => String(x).padEnd(n); const kib = (b, n) => s((b / 1024).toFixed(1) + " KiB", n); const pct = (x, n) => s((x * 100).toFixed(2) + "%", n); const row = (cells, widths) => cells.map((c, i) => s(c, widths[i])).join(" | "); const d = data({}); console.log("3,000 books, 6 branches, 12,000 loan records (seed 20260731). Catalog entry 240,"); console.log("loan 96, queue 128, branch counter 64 bytes. " + SLOTS + " slots, equal ranges per node."); console.log("T1 = catalog + loan + queue; T2 = T1 + branch counter. No tag:\n"); const WA = [5, 7, 12, 15, 12, 15, 7]; console.log(row(["nodes", "keys", "total bytes", "busiest node", "imbalance", "T1 on 1 node", "T2"], WA)); console.log(WA.map((w) => "-".repeat(w)).join("-|-")); for (const n of [3, 4, 6, 8]) { const r = run({ scheme: "none", nodes: n, d }); console.log(row([n, r.keys, kib(r.total, 10), kib(r.mostLoaded, 10), r.imbalance.toFixed(3), pct(r.t1, 13), pct(r.t2, 6)], WA)); } console.log("\n6 nodes fixed; tagging scheme varies:"); const WB = [6, 15, 7, 12, 10, 11, 7, 7]; console.log(row(["scheme", "slots used", "keys", "total bytes", "busiest", "imbalance", "T1", "T2"], WB)); console.log(WB.map((w) => "-".repeat(w)).join("-|-")); for (const scheme of ["none", "branch", "book"]) { const r = run({ scheme, nodes: 6, d }); console.log(row([scheme, r.slots, r.keys, kib(r.total, 10), kib(r.mostLoaded, 6), r.imbalance.toFixed(3), pct(r.t1, 6), pct(r.t2, 6)], WB)); } console.log("\n6 nodes, tag = branch. Load per node (branch shares 34/24/16/12/9/5):"); const b = run({ scheme: "branch", nodes: 6, d }); console.log("node : " + b.load.map((_, i) => s("n" + i, 9)).join("")); console.log("keys : " + b.count.map((x) => s(x, 9)).join("")); console.log("KiB : " + b.load.map((x) => s((x / 1024).toFixed(1), 9)).join("")); console.log("\nquantities independent of the run:"); console.log(" probability that a K-key transaction lands on 1 node = (1/n)^(K-1), untagged"); console.log(" n : " + [3, 4, 6, 8].map((n) => s(n, 8)).join("")); console.log(" K=3 : " + [3, 4, 6, 8].map((n) => s((100 / n ** 2).toFixed(2) + "%", 8)).join("")); console.log(" K=4 : " + [3, 4, 6, 8].map((n) => s((100 / n ** 3).toFixed(2) + "%", 8)).join("")); console.log(" tag = branch -> usable slot count = branch count = 6"); console.log(" tag = book -> usable slot count = book count = 3000"); console.log(" sample slot no: branch:0 -> " + slotOf("{branch:0}catalog:7") + ", book:7 -> " + slotOf("{book:7}catalog:7") + ", untagged catalog:7 -> " + slotOf("catalog:7")); console.log(" nodes for those slots at 6 nodes: " + [ nodeOf(slotOf("{branch:0}catalog:7"), 6), nodeOf(slotOf("{book:7}catalog:7"), 6), nodeOf(slotOf("catalog:7"), 6)].join(", ")); ``` ``` 3,000 books, 6 branches, 12,000 loan records (seed 20260731). Catalog entry 240, loan 96, queue 128, branch counter 64 bytes. 16384 slots, equal ranges per node. T1 = catalog + loan + queue; T2 = T1 + branch counter. No tag: nodes | keys | total bytes | busiest node | imbalance | T1 on 1 node | T2 ------|---------|--------------|-----------------|--------------|-----------------|-------- 3 | 11758 | 1539.6 KiB | 543.8 KiB | 1.060 | 7.55% | 2.90% 4 | 11758 | 1539.6 KiB | 410.1 KiB | 1.066 | 3.79% | 1.18% 6 | 11758 | 1539.6 KiB | 278.3 KiB | 1.085 | 1.15% | 0.27% 8 | 11758 | 1539.6 KiB | 209.4 KiB | 1.088 | 0.08% | 0.02% 6 nodes fixed; tagging scheme varies: scheme | slots used | keys | total bytes | busiest | imbalance | T1 | T2 -------|-----------------|---------|--------------|------------|-------------|---------|-------- none | 8437 | 11758 | 1539.6 KiB | 278.3 KiB | 1.085 | 1.15% | 0.27% branch | 6 | 18151 | 2899.0 KiB | 2373.9 KiB | 4.913 | 100.00% | 100.00% book | 2706 | 11758 | 1539.6 KiB | 306.5 KiB | 1.195 | 100.00% | 14.90% 6 nodes, tag = branch. Load per node (branch shares 34/24/16/12/9/5): node : n0 n1 n2 n3 n4 n5 keys : 14865 0 0 0 0 3286 KiB : 2373.9 0.0 0.0 0.0 0.0 525.2 quantities independent of the run: probability that a K-key transaction lands on 1 node = (1/n)^(K-1), untagged n : 3 4 6 8 K=3 : 11.11% 6.25% 2.78% 1.56% K=4 : 3.70% 1.56% 0.46% 0.20% tag = branch -> usable slot count = branch count = 6 tag = book -> usable slot count = book count = 3000 sample slot no: branch:0 -> 487, book:7 -> 11715, untagged catalog:7 -> 6819 nodes for those slots at 6 nodes: 0, 4, 2 ``` ## The Size of the Cross-Node Constraint **Splitting is balanced; balance is not what constrains.** The first table's imbalance column sits between 1.060 and 1.088 across all four node counts: the busiest node is at most nine percent above average. The hash distribution does its job and the bytes held really do get split — the busiest node holds 543.8 KiB at three nodes, 209.4 KiB at eight. This is what replication could not do. **What gets lost is the transaction.** The same table's last two columns count this: in a three-node cluster, 7.55 percent of T1 transactions and 2.90 percent of T2 transactions land on a single node. At eight nodes, the rates drop to 0.08 percent and 0.02 percent. The expected value, in the run-independent rows, is `(1/n)^(K-1)`. The measured numbers sit well below that expectation — loan records are not independent, the same book–branch pair recurs many times, so a particular set of hot pairs can land off the theoretical curve in either direction — but the trend is the same: **adding a node drops a transaction's chance of staying on one node exponentially**, and the number of keys touched is the exponent. T2 adds a single key to T1 and lowers the rate fivefold at eight nodes. This is the real cost of moving to a cluster. If a loan transaction that checks a branch limit can run on a single node only about once in six thousand attempts, that transaction has to be carried out by the application in a cluster deployment, and it keeps no atomicity. ## The Tag's Granularity The second table compares three ways of lifting the constraint. A **tag** is hashing only a specific part of the key; every key carrying the same tag lands on the same slot, and therefore the same node. When the tag is branch, the cross-node constraint disappears completely, and so does the partitioning. T1 and T2 climb to 100 percent. In exchange, the slot count in use drops from 8,437 to **6**: six branches, six slots. The third block's result shows this plainly — four of the six nodes are completely empty, all the data is concentrated on two nodes, and the imbalance is 4.913. Which node will hit the memory limit is obvious in advance. There is a second line item, and it comes directly out of the memory budget: total bytes held climb from 1,539.6 KiB to **2,899.0 KiB**, and the key count from 11,758 to 18,151. The reason is that the catalog entry is now written with the branch tag — the same book's record stands separately at every branch it was lent from. Tagging determines not only placement, but **copy count**. When the tag is book, the picture is mixed rather than a clean reversal. The slot count in use climbs to 2,706, and total bytes never grow, because the catalog entry does not get multiplied. But the imbalance is slightly higher than the untagged distribution (1.195 against 1.085): spreading 3,000 tags across six nodes carries more sampling noise than spreading tens of thousands of independently hashed keys does. T1 is 100 percent: a book's catalog entry, loan record, and waiting-queue entry always land on the same node. T2 stays at 14.90 percent, because the branch's concurrent-loan counter does not carry the book tag and lands on one of six nodes at random. The rule that comes out of this is not about the tag itself but about the transaction: **a tag does not fit a transaction onto one node, it defines the transaction's scope.** Pulling the branch counter onto the same node too requires either binding the counter to the book tag — at which point there is no longer a single counter per branch — or moving the limit check outside the transaction. In a cluster deployment, key naming decides which transactions stay atomic. ## Summary - A key is first mapped by hash to one of 16,384 slots, and the slot is then mapped to a node; two keys landing on the same node is not a design decision, it is a coincidence. - Untagged partitioning is balanced (imbalance 1.060–1.088) and really does split the bytes held: the busiest node holds 543.8 KiB at three nodes, 209.4 KiB at eight. - The multi-key transaction's single-node landing rate follows the shape of `(1/n)^(K-1)`: for T1 it drops from 7.55 percent to 0.08 percent, for T2 from 2.90 percent to 0.02 percent. - When the tag is branch, T1 and T2 climb to 100 percent; the cost is the slot count in use dropping to 6, four of the six nodes staying empty, and the imbalance reaching 4.913. - Because the branch tag multiplies the catalog entry per branch, total bytes held climbed from 1,539.6 KiB to 2,899.0 KiB, and the key count from 11,758 to 18,151. - The book tag never grows the bytes held but pushes the imbalance to 1.195 and makes only T1 reach 100 percent; T2, which includes the branch counter, stays at 14.90 percent — the tag defines the transaction's scope. ## Next Step This lesson showed that all of a transaction's keys can be gathered onto the same node, but it never asked what happens once they are. A loan transaction reads the branch's concurrent-loan counter, checks whether it is over the limit, and only then increments it; in the time between the read and the increment, another branch clerk may have changed the same counter. In an in-memory store, closing that gap is not done by taking a lock — it is done by **watching** the key and, if it changed, dropping the transaction and retrying it. The next lesson measures this watch-based check under concurrency: the collision rate, retries per transaction, the metadata a watched key holds, and the rounds during which every client waits while a transaction runs.