--- title: 'In-Memory Stores and Caching Systems' source: 'https://academia.sh/en/courses/in-memory-stores' language: en updated: '2026-08-23T07:00:42+00:00' license: 'CC BY-SA 4.0' lessons: 22 outcomes: - 'Maps in-memory data structures to the use cases that suit them' - 'Configures persistence and memory eviction policies' - 'Raises availability with clustering and replication' --- # In-Memory Stores and Caching Systems Stores that keep all data in memory, where durability becomes a setting: key-value basics, counters, lists, hashes, sets, sorted sets, bitmaps, probabilistic structures, streams, and spatial indexes mapped to the scenarios that suit them, the durability and performance trade-off between snapshot and append-log persistence, the memory limit and eviction policies, expiration management, replication, automatic failover, clustering, optimistic locking, publish-subscribe, and typical use cases. ## Data Structures and Commands Mapping the structures an in-memory store offers to scenarios: key setting, reading, and expiration, counters built on atomic increment, lists as queues and stacks, hash structures that manage object fields separately, sets and sorted sets in membership and ranking scenarios, bitmaps and probabilistic structures for memory-efficient counting, streams and consumer groups as an ordered event log, spatial indexes for location-based queries, and server-side scripting for atomic multi-step operations. ### Key-Value Basics Source: https://academia.sh/en/courses/in-memory-stores/key-value-basics The contract and the cost of an in-memory store: building set, get, and expiration on a hand-written store, counting bytes held per entry as key, value, and overhead, comparing no-expiration, fixed-expiration, and sliding-expiration policies on peak memory and re-entry count, the effect of key and value shape on bytes held, and how overhead scales with entry count. The Non-Relational Data Models course closed on a habit shared by every store it covered: data was written to disk sooner or later, and durability was a given part of the model. This course takes up the stores that drop that habit. In an in-memory store, all of the data sits in process memory, disk is an optional setting, and the real constraint is not capacity but the **memory budget**. Every lesson in this course asks the same three questions: how many **bytes** does a structure hold in memory, what does that buy in return, and what does an alternative that does the same job with less memory give up. "It is fast" answers none of these questions; a fast in-memory store is this course's assumption, not its subject. This lesson opens with the contract itself: a key is set, read, and given a lifetime. #### The Contract and Bytes per Entry The store defines three operations. **Set** binds a value to a key and gives it an optional lifetime. **Get** takes the key and returns the value; it treats an expired entry as if it were absent. **Renewal** moves the expiration timestamp forward. The basic key-value contract still holds here: the store does not look inside the value. The only thing that changes is where the record sits — and that single change rewrites the cost calculation, because space on disk is a capacity line item while space in memory is a budget. The measurement uses the library's session record. **DS1:** the catalog carries 20,000 members, the day is 12 hours (43,200 seconds), each member touches the system 1 to 5 times during the day, and the gap between touches is 60 to 2,459 seconds; touch times come from a linear congruential generator with a visible seed. **DS2:** overhead per entry is counted as 56 bytes — 8 for the hash bucket pointer, 16 for the entry structure's pointers, 16 for length fields, 8 for the expiration timestamp, 8 for alignment. Held bytes are always computed as `key + value + 56`. **DS3:** a live entry is sampled every 300 seconds, and the peak is the largest of these samples; when an expired entry is actually removed from memory is a separate question — only **unexpired** entries are counted here. ```js // memory/store.mjs — a hand-written in-memory store: key space, expiration, and // counting the bytes held. Overhead per entry is reported in DS2; a live entry is // counted once every 300 s. const OVERHEAD = 56; class InMemoryStore { #table = new Map(); reads = 0; misses = 0; set(key, value, now, lifetime) { const s = JSON.stringify(value); this.#table.set(key, { s, expiresAt: lifetime === null ? null : now + lifetime }); } get(key, now) { // an expired entry is treated as absent this.reads += 1; const entry = this.#table.get(key); if (entry === undefined || (entry.expiresAt !== null && entry.expiresAt <= now)) { this.misses += 1; return undefined; } return JSON.parse(entry.s); } renew(key, now, lifetime) { const entry = this.#table.get(key); if (entry) entry.expiresAt = now + lifetime; } live(now) { // per entry: key + value + overhead let n = 0, b = 0; for (const [key, entry] of this.#table) if (entry.expiresAt === null || entry.expiresAt > now) { n += 1; b += Buffer.byteLength(key) + Buffer.byteLength(entry.s) + OVERHEAD; } return { n, b }; } } // --- event generation: a 12-hour day, 20,000 members, touches from a seeded generator --- const MEMBERS = 20_000, DAY = 43_200, LIFETIME = 1800, SAMPLE = 300, SEED = 20240115; let state = SEED; const rand = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648; const BRANCH = ["central", "shore", "university", "children", "archive"]; const events = []; for (let m = 1; m <= MEMBERS; m += 1) { let t = Math.floor(rand() * (DAY - 7200)); const touches = 1 + Math.floor(rand() * 5); for (let k = 0; k < touches && t < DAY; k += 1) { events.push([t, m]); t += 60 + Math.floor(rand() * 2400); } } events.sort((x, y) => x[0] - y[0] || x[1] - y[1]); const sessionKey = (m) => `session:${m}:${(m * 2654435761) % 4294967296}`; const session = (m) => ({ member: m, branch: BRANCH[m % 5], role: m % 97 === 0 ? "clerk" : "reader" }); function run(name, lifetime, sliding) { const store = new InMemoryStore(); let peakEntries = 0, peakBytes = 0, newEntries = 0, nextSample = SAMPLE; for (const [t, m] of events) { while (t >= nextSample) { const snapshot = store.live(nextSample); if (snapshot.n > peakEntries) { peakEntries = snapshot.n; peakBytes = snapshot.b; } nextSample += SAMPLE; } const key = sessionKey(m); if (store.get(key, t) === undefined) { store.set(key, session(m), t, lifetime); newEntries += 1; } else if (sliding) store.renew(key, t, lifetime); } const final = store.live(DAY); if (final.n > peakEntries) { peakEntries = final.n; peakBytes = final.b; } return [name, peakEntries, peakBytes, final.n, final.b, store.misses, newEntries]; } console.log(`seed ${SEED}; ${MEMBERS} members, ${events.length} touches, day ${DAY} s, lifetime ${LIFETIME} s`); console.log(`sample session value ${Buffer.byteLength(JSON.stringify(session(4242)))} bytes, ` + `key ${Buffer.byteLength(sessionKey(4242))} bytes, overhead ${OVERHEAD} bytes`); const rows = [run("no expiration", null, false), run("fixed expiration", LIFETIME, false), run("sliding expiration", LIFETIME, true)]; console.log(`\n${"policy".padEnd(16)}${"peak entries".padStart(12)}${"peak bytes".padStart(11)}` + `${"end-of-day entries".padStart(19)}${"end-of-day bytes".padStart(17)}${"misses".padStart(7)}${"extra re-entries".padStart(18)}`); for (const [name, pe, pb, ee, eb, ms] of rows) console.log(name.padEnd(16) + String(pe).padStart(12) + String(pb).padStart(11) + String(ee).padStart(19) + String(eb).padStart(17) + String(ms).padStart(7) + String(ms - MEMBERS).padStart(18)); ``` ``` seed 20240115; 20000 members, 59337 touches, day 43200 s, lifetime 1800 s sample session value 53 bytes, key 23 bytes, overhead 56 bytes policy peak entries peak bytes end-of-day entries end-of-day bytes misses extra re-entries no expiration 20000 2600406 20000 2600406 20000 0 fixed expiration 2193 285185 28 3644 36951 16951 sliding expiration 2658 345617 29 3769 31182 11182 ``` #### Expiration Is a Memory Policy All three runs process the same 59,337 touches; the only thing that differs is the lifetime setting. With no expiration given, the store carries 20,000 entries and 2,600,406 bytes by the end of the day, and that number never shrinks: once a member logs in, the record sits there for as long as the process lives. In exchange, every touch finds its record in place; the 20,000 misses are only the day's first touches and are unavoidable — nobody finds a session without logging in for the first time. Extra re-entries are zero. Fixed expiration does the same job with a peak of 2,193 entries and 285,185 bytes: roughly nine times less memory. What that buys is plain to see — memory now scales with the count of concurrently active members, not the member count, and only 28 entries remain at the end of the day. What it gives up is just as countable: 16,951 extra re-entries. A member whose record has dropped has to re-authenticate. Sliding expiration sits between the two and makes the purchase rate visible. The peak climbs to 345,617 bytes, 60,432 bytes more than the fixed policy; in exchange, extra re-entries drop from 16,951 to 11,182. Each of the 5,769 saved entries costs 10.5 bytes of peak memory. The lesson foregrounds this number: policy choice is not a matter of style, it is a purchase priced in bytes. The same arithmetic looks completely different in end-of-day memory — the no-expiration policy holds onto 2.6 MB permanently, while the two expiring policies close out around 3.6-3.8 KB; the difference is roughly 700-fold. #### The Shape of the Key and the Value Entry count is not the only lever. The same session can be held in different key and value shapes, and each shape directly changes the bytes held. The second setup counts the same member in six shapes and, at the end, compares the structural count against an environment-dependent measurement. ```js // memory/shape.mjs — key and value representations of the same session: bytes held // per format. OVERHEAD is the same constant; the structural count is run-independent. const OVERHEAD = 56, ENTRIES = 20_000, BRANCH = ["central", "shore", "university", "children", "archive"]; const session = (m) => ({ member: m, branch: BRANCH[m % 5], role: m % 97 === 0 ? "clerk" : "reader" }); const member = 4242, token = (member * 2654435761) % 4294967296, rec = session(member); const formats = [ ["session:token:4242:...", `session:token:${member}:${token}`], ["session:4242:...", `session:${member}:${token}`], ["s:...", `s:${token}`], ]; const values = [["self-describing", JSON.stringify(rec)], ["positional", `${rec.member}|${rec.branch}|${rec.role}`]]; console.log(`${"key format".padEnd(23)}${"key".padStart(8)}${"value format".padStart(20)}` + `${"value".padStart(7)}${"entry".padStart(7)}${`at ${ENTRIES}`.padStart(14)}`); for (const [label, keyStr] of formats) for (const [valueLabel, valueStr] of values) { const entryBytes = Buffer.byteLength(keyStr) + Buffer.byteLength(valueStr) + OVERHEAD; console.log(label.padEnd(23) + String(Buffer.byteLength(keyStr)).padStart(8) + valueLabel.padStart(20) + String(Buffer.byteLength(valueStr)).padStart(7) + String(entryBytes).padStart(7) + String(entryBytes * ENTRIES).padStart(14)); } // a new field (branch_code) is inserted in second position — how OLD entries are read const parsed = JSON.parse(values[0][1]), [, k1, k2, k3] = values[1][1].split("|"); console.log(`\nold entry, read with new order (member|branch_code|branch|role):`); console.log(` self-describing -> branch=${parsed.branch} role=${parsed.role} branch_code=${parsed.branch_code}`); console.log(` positional -> branch=${k2} role=${k3} branch_code=${k1}`); const before = process.memoryUsage().heapUsed; // ENVIRONMENT-DEPENDENT const table = new Map(); for (let i = 1; i <= ENTRIES; i += 1) table.set(`session:${i}:${(i * 2654435761) % 4294967296}`, { s: JSON.stringify(session(i)), expiresAt: 1800 }); const after = process.memoryUsage().heapUsed; const structural = [...table].reduce((t, [key, entry]) => t + Buffer.byteLength(key) + Buffer.byteLength(entry.s) + OVERHEAD, 0); console.log(`\nstructural count of ${ENTRIES} entries is ${structural} bytes (run-independent); ` + `the real heap difference is ${((after - before) / structural).toFixed(1)} times that (ENVIRONMENT-DEPENDENT, varies from run to run)`); ``` ``` key format key value format value entry at 20000 session:token:4242:... 29 self-describing 53 138 2760000 session:token:4242:... 29 positional 22 107 2140000 session:4242:... 23 self-describing 53 132 2640000 session:4242:... 23 positional 22 101 2020000 s:... 12 self-describing 53 121 2420000 s:... 12 positional 22 90 1800000 old entry, read with new order (member|branch_code|branch|role): self-describing -> branch=university role=reader branch_code=undefined positional -> branch=reader role=undefined branch_code=university structural count of 20000 entries is 2600406 bytes (run-independent); the real heap difference is 2.5 times that (ENVIRONMENT-DEPENDENT, varies from run to run) ``` At 20,000 entries, there are 960,000 bytes between the priciest shape and the cheapest — a 34.8 percent difference from a one-line code change. Shrinking the key from 29 bytes to 12 bytes saves 340,000 bytes; stripping the value of its field names saves 620,000 bytes. Both losses are concrete. The short key removes the key namespace's readability: without the `session:` prefix, the same namespace cannot distinguish which entry is a session and which is a cache record, and two different jobs that produce the same name collide silently. The loss from the positional value is harsher. The three middle lines of the output show it: once a `branch_code` field is added in second position, the self-describing value still resolves old entries correctly (`branch=university`, `role=reader`) and only finds the new field empty. The positional value misreads the same entry: `reader` lands in the branch field, `university` lands in the branch code. The 620,000 bytes gained are paid for with the data's ability to describe itself. The last line marks the limit of the measurement. The structural count is 2,600,406 bytes, identical to the first setup's end-of-day count; the real heap usage, in this run, is 2.5 times that. This second number is environment-dependent and varies from run to run — it only says that the structural count is a lower bound; the measure that drives the decision throughout the course is the first one. The ratio between the two also says something else: the 56-byte overhead takes up 62.2 percent of the entry in the cheapest shape. As entries shrink, the payoff from shaping them better shrinks with them; the real lever is not the shape of the entry, it is the **number of entries** — which is to say, the expiration policy. #### Summary - An in-memory store defines three operations: set, get, renew. The value is opaque to the store; the only thing that changes is that the record sits in memory instead of on disk, and that turns space from a capacity line item into a budget. - Held bytes are counted as key + value + 56. 20,000 session records hold 2,600,406 bytes — an average of 130.0 bytes per entry. - Expiration is a memory policy: fixed expiration drops the peak from 20,000 entries to 2,193 and from 2,600,406 bytes to 285,185, at the cost of 16,951 extra re-entries. - Sliding expiration holds 60,432 bytes more and prevents 5,769 re-entries — 10.5 bytes per prevented re-entry. Policy choice is a purchase priced in bytes. - Key and value shape make a 960,000-byte difference at 20,000 entries; the positional value earns that gain by keeping field order outside the store, and it silently misreads old entries once the schema changes. - The structural count is run-independent and is the measure that drives the decision; the real heap usage (2.5 times the structural count) is environment-dependent and only shows that the structural count is a lower bound. #### Next Step Every write in this lesson overwrote the entire value: the session record was read, changed, and put back. The things the library needs to count do not fit this pattern. How many times a book has been borrowed, how many loans a branch handed out during the day, how many times a member has been late — each of these is a single number that goes up by one on every request. What happens when two requests read and write back the same counter at the same time was never asked in this lesson. The next lesson measures exactly that: the difference between read-modify-write and the store's own increment under concurrent requests, the number of lost updates, and how many bytes a single counter costs across a 200,000-book catalog. ### Strings and Counters Source: https://academia.sh/en/courses/in-memory-stores/strings-and-counters What atomic increment buys: updating the same loan counter with read-modify-write and with the store's own single-step increment, measuring the lost updates and round trips this produces at increasing branch concurrency, breaking down a counter's real memory price into key, value, and overhead, and comparing no-counter, partial-counter, and full-counter options in terms of steps prevented per byte. Every write in the previous lesson overwrote the entire value. Most of what the library needs to count does not fit that pattern: how many times a book has been borrowed, a branch's daily loan total, how many times a member has been late — each of these is a single number that goes up by one on every event. This lesson takes up that number with two questions: what changes depending on **who** increments the counter, and what a single number actually costs in memory. The store holds a value as a byte string; a number is also a string. But the store can interpret that string as a number and increment it in a single step. This capability is called atomic increment, and at first glance it looks like a convenience. Measured, it turns out to be not a convenience but accuracy itself. #### Who Increments the Counter There are two paths. **Read-modify-write** is three separate steps: the value is read, incremented in the application, and written back. **Atomic increment** is a single step: the store reads the value, adds to it, and writes it; nothing else can interleave in between. The difference only shows up under concurrency. The measurement uses a popular book's loan counter. **DS1:** the same book is loaned out concurrently by 1, 2, 4, 8, and 16 branches, and each branch records 500 loans; the expected counter value is the branch count times 500. **DS2:** concurrency is built with generators, every `yield` is a suspension point, and the scheduler picks among ready clients with a generator whose seed is visible; the run is deterministic. ```js // memory/counter.mjs — the same loan counter incremented two ways. Clients are // generators, the scheduler is seeded; step order is run-independent. class InMemoryStore { #table = new Map(); roundTrips = 0; get(key) { this.roundTrips += 1; const s = this.#table.get(key); return s === undefined ? 0 : Number(s); } set(key, value) { this.roundTrips += 1; this.#table.set(key, String(value)); } increment(key, delta) { // reads, adds, and writes in a single step this.roundTrips += 1; const value = (this.#table.has(key) ? Number(this.#table.get(key)) : 0) + delta; this.#table.set(key, String(value)); return value; } } function* readModifyWrite(store, key, times) { for (let i = 0; i < times; i += 1) { const value = store.get(key); yield; store.set(key, value + 1); yield; } } function* atomic(store, key, times) { for (let i = 0; i < times; i += 1) { store.increment(key, 1); yield; } } const SEED = 20240115, TIMES = 500, KEY = "book:100427:loan"; function schedule(generators) { // seeded selection among ready clients let state = SEED; const rand = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648; const live = [...generators]; while (live.length > 0) { const i = Math.floor(rand() * live.length); if (live[i].next().done) live.splice(i, 1); } } console.log(`seed ${SEED}; each branch records ${TIMES} loans, key ${KEY}`); console.log(`${"branches".padStart(9)}${"expected".padStart(10)}${"read-modify-write".padStart(19)}` + `${"lost".padStart(7)}${"round trips".padStart(13)}${"atomic increment".padStart(18)}${"lost".padStart(7)}${"round trips".padStart(13)}`); for (const branches of [1, 2, 4, 8, 16]) { const expected = branches * TIMES; const rmwStore = new InMemoryStore(); schedule(Array.from({ length: branches }, () => readModifyWrite(rmwStore, KEY, TIMES))); const atomicStore = new InMemoryStore(); schedule(Array.from({ length: branches }, () => atomic(atomicStore, KEY, TIMES))); const rmwFinal = rmwStore.get(KEY), atomicFinal = atomicStore.get(KEY); console.log(String(branches).padStart(9) + String(expected).padStart(10) + String(rmwFinal).padStart(19) + String(expected - rmwFinal).padStart(7) + String(rmwStore.roundTrips - 1).padStart(13) + String(atomicFinal).padStart(18) + String(expected - atomicFinal).padStart(7) + String(atomicStore.roundTrips - 1).padStart(13)); } ``` ``` seed 20240115; each branch records 500 loans, key book:100427:loan branches expected read-modify-write lost round trips atomic increment lost round trips 1 500 500 0 1000 500 0 500 2 1000 620 380 2000 1000 0 1000 4 2000 747 1253 4000 2000 0 2000 8 4000 871 3129 8000 4000 0 4000 16 8000 938 7062 16000 8000 0 8000 ``` With a single branch running, both paths give the correct result; the divergence starts at the second branch. At two branches, 380 of 1,000 loans go missing; at sixteen branches, 7,062 of 8,000. The counter stalls at 938: the library handed out eight thousand loans, and its record reads nine hundred thirty-eight. A lost update is not a delay or a slowdown — it is a **wrong number**, and it shows up nowhere as an error. The cause is the gap between the read and the write. By the time one branch reads 41 and writes 42, other branches have also read 41; all of them write 42, and all four of them together have made a single increment. Atomic increment has no such gap — the store reads, adds, and writes as one operation that cannot be split. At sixteen branches, the loss is zero. The round-trip column shows the second gain: read-modify-write spends two round trips per increment, while atomic increment finishes in one — 8,000 instead of 16,000. Getting the same correctness out of read-modify-write means holding a lock in the application, which in turn means keeping the lock itself in memory and lining the branches up in a queue. Atomic increment removes both a round trip and the lock's memory — and asks for no extra bytes in return, because the increment is the store's own job. #### The Memory Price of a Number The counter now increments correctly; the real question comes next. How much memory does holding a loan counter for the entire catalog take up. **DS3:** the catalog carries 200,000 books, each book's counter value comes from a deterministic function and falls between 1 and 4,096; the loan ledger is 119,993 records and sits outside the in-memory store — scanning it counts steps, not bytes. **DS4:** the query load is 10,000 "how many times was this book borrowed" questions, skewed toward popularity; the skew comes from the same seeded generator. ```js // memory/budget.mjs — the memory price of one counter and two options that skip it. // The loan ledger is outside the in-memory store; scanning it counts steps, not bytes. const OVERHEAD = 56, BOOKS = 200_000, LEDGER = 119_993, QUERIES = 10_000, HOT = 1_000, SEED = 20240115; let state = SEED; const rand = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648; // counter value: daily loan count for book i (deterministic) const counterValue = (i) => 1 + ((i * 7919) % 4096); const key = (i) => `book:${100_000 + i}:loan`; let totalKey = 0, totalValue = 0, totalOverhead = 0; for (let i = 1; i <= BOOKS; i += 1) { totalKey += Buffer.byteLength(key(i)); totalValue += Buffer.byteLength(String(counterValue(i))); totalOverhead += OVERHEAD; } const full = totalKey + totalValue + totalOverhead; console.log(`${BOOKS} books, sample entry "${key(427)}" -> "${counterValue(427)}"`); console.log(`full counter: key ${totalKey} + value ${totalValue} + overhead ${totalOverhead} = ${full} bytes` + ` (per entry ${(full / BOOKS).toFixed(1)}; value's share %${(100 * totalValue / full).toFixed(1)})`); // query load: "how many times was this book borrowed" — skewed to popularity, seeded const queries = Array.from({ length: QUERIES }, () => 1 + Math.floor(BOOKS * rand() ** 6)); const hotQueries = queries.filter((i) => i <= HOT).length; const partial = Array.from({ length: HOT }, (_, j) => Buffer.byteLength(key(j + 1)) + Buffer.byteLength(String(counterValue(j + 1))) + OVERHEAD) .reduce((t, x) => t + x, 0); const baseline = QUERIES * LEDGER; // steps when no counter is held const paths = [ ["no counter, ledger scan", 0, 0, baseline], [`partial counter (top ${HOT})`, HOT, partial, hotQueries + (QUERIES - hotQueries) * LEDGER], ["full counter", BOOKS, full, QUERIES], ]; console.log(`\n${QUERIES} queries, ${hotQueries} of them to the first ${HOT} books (%${(100 * hotQueries / QUERIES).toFixed(1)})`); console.log(`${"path".padEnd(27)}${"entries".padStart(8)}${"bytes held".padStart(14)}` + `${"steps per query".padStart(19)}${"steps prevented per byte".padStart(27)}`); for (const [name, n, b, steps] of paths) console.log(name.padEnd(27) + String(n).padStart(8) + String(b).padStart(14) + (steps / QUERIES).toFixed(1).padStart(19) + (b === 0 ? "-" : ((baseline - steps) / b).toFixed(1)).padStart(27)); ``` ``` 200000 books, sample entry "book:100427:loan" -> "2214" full counter: key 3200000 + value 745901 + overhead 11200000 = 15145901 bytes (per entry 75.7; value's share %4.9) 10000 queries, 4149 of them to the first 1000 books (%41.5) path entries bytes held steps per query steps prevented per byte no counter, ledger scan 0 0 119993.0 - partial counter (top 1000) 1000 75662 70208.3 6579.9 full counter 200000 15145901 1.0 79.2 ``` The first line carries the lesson's headline: 200,000 counters hold 15,145,901 bytes, 75.7 per entry. Yet the information stored is a four-digit number. The number itself takes up only 4.9 percent of the total; the key name takes 21.1 percent, entry overhead takes 73.9 percent. Holding a number in an in-memory store costs not four bytes but seventy-six. This ratio holds for every small value, and the real lever is not the value itself, it is **how many keys are opened**. The lower table compares three options under the same load. If the counter is never held, memory is zero and every query scans the 119,993-record ledger. With the full counter, memory rises to 15.1 MB and steps per query drop to 1: 15.1 MB buys 119,992 steps per query. The last column is the number that actually decides. Holding a counter only for the first 1,000 books costs 75,662 bytes — one two-hundredth of the full counter — and it drops 41.5 percent of the queries to a single step. Every byte it holds prevents 6,579.9 steps; the same figure for the full counter is 79.2. The partial counter is roughly eighty-three times more byte-efficient. But the raw number is still unforgiving: 70,208 steps per query, because each of the missed 58.5 percent scans the entire ledger. If the memory budget is tight, the partial counter is the more efficient purchase; if a fixed step count per query is required, there is no alternative to the 15.1 MB. What decides between the two is not "speed" — it is the product of the miss rate and the budget. #### Summary - A counter has two update paths: read-modify-write is three steps and is open to other clients between the read and the write; atomic increment is the store's single, unsplittable step. - Loss grows with concurrency: at 2 branches, 380 of 1,000 loans go missing; at 16 branches, 7,062 of 8,000, and the counter stalls at 938. With atomic increment, the loss is zero at every level. - Atomic increment also halves round trips (8,000 instead of 16,000) and removes the need to hold a lock in the application for correctness; a lock means both memory and waiting. - 200,000 loan counters hold 15,145,901 bytes. The number itself is 4.9 percent of that, the key name is 21.1 percent, entry overhead is 73.9 percent: a number in an in-memory store costs 75.7 bytes. - Three options under the same load: no counter, 0 bytes and 119,993 steps per query; partial counter, 75,662 bytes and 70,208 steps; full counter, 15,145,901 bytes and 1 step. - Steps prevented per byte are 6,579.9 for the partial counter and 79.2 for the full counter. The partial counter is far more efficient per unit of budget, but it gives no guarantee of a fixed step count per query. #### Next Step A counter answers the "how many" question at the scale of a single byte, but it never meets the library's second question: who is waiting for a popular book, and in what order. A waiting list is not a number, it is a sequence; the order itself is part of the information, and if the store is to preserve it, it has to hold every member individually. The next lesson takes up the list and measures three things: the step count of inserting and removing from both ends, the effect of the list's growth on memory, and what a bounded list — one trimmed to a fixed length — cheapens compared to an unbounded one, and what it silently loses. ### Lists Source: https://academia.sh/en/courses/in-memory-stores/lists The cost of holding order itself as data: measuring the same waiting-list workload in contiguous-array, linked-node, and ring-buffer implementations by steps and bytes per entry, how many bytes per entry constant-step access from both ends is bought for, rank lookup being a scan in all three structures, and how trimming a recent-activity list lowers bytes held while narrowing the covered time window and the satisfied query rate. The counter answered the "how many" question with a single number. The library's second question cannot be answered with a number: who is waiting for a popular book, and in what order. In a waiting list, the order itself is part of the information; if the store is to preserve it, it has to hold every member individually, together with their position. A list is a single structure with two distinct uses. A **queue** appears when items are added at one end and removed from the other: the waiting list works this way, first come, first served. A **stack** appears when items are added and removed from the same end: a clerk undoing their last action works this way. From the store's point of view, the difference is not in the structure, it is in which end is chosen. The real question is this: what does constant-step access from both ends cost in memory. #### The Same Workload, Three Implementations **DS1:** 20,000 requests are added to the waiting list from the back, a front pickup happens after every fourth request (5,000 removals), and a priority request is moved to the front every fortieth request (500 insertions); 25,500 operations total. **DS2:** an array slot is 8 bytes, a linked node's extra cost is 24 bytes (previous and next pointers plus the node header), overhead per structure is 56 bytes. **DS3:** the ring buffer starts with 1,024 slots and doubles its capacity once full; copy steps are counted. ```js // memory/list.mjs — the same waiting-list workload in three implementations. Step and // byte counters live inside the structure itself; the workload is deterministic. const OVERHEAD = 56, SLOT = 8, NODE_OVERHEAD = 24; // DS2 class ArrayList { // contiguous array: a front operation shifts everything #items = []; steps = 0; pushBack(v) { this.steps += 1; this.#items.push(v); } pushFront(v) { this.steps += this.#items.length + 1; this.#items.unshift(v); } popFront() { this.steps += this.#items.length; return this.#items.shift(); } get length() { return this.#items.length; } get bytes() { return OVERHEAD + this.#items.reduce((t, v) => t + Buffer.byteLength(v) + SLOT, 0); } rank(v) { let n = 0; for (const x of this.#items) { n += 1; if (x === v) return n; } return -1; } } class LinkedList { // constant single step from both ends; extra pointer per node #head = null; #tail = null; #n = 0; #b = 0; steps = 0; #node(v) { this.#n += 1; this.#b += Buffer.byteLength(v) + SLOT + NODE_OVERHEAD; return { v, prev: null, next: null }; } pushBack(v) { this.steps += 1; const node = this.#node(v); node.prev = this.#tail; if (this.#tail) this.#tail.next = node; else this.#head = node; this.#tail = node; } pushFront(v) { this.steps += 1; const node = this.#node(v); node.next = this.#head; if (this.#head) this.#head.prev = node; else this.#tail = node; this.#head = node; } popFront() { this.steps += 1; const node = this.#head; if (!node) return undefined; this.#head = node.next; if (this.#head) this.#head.prev = null; else this.#tail = null; this.#n -= 1; this.#b -= Buffer.byteLength(node.v) + SLOT + NODE_OVERHEAD; return node.v; } get length() { return this.#n; } get bytes() { return OVERHEAD + this.#b; } rank(v) { let n = 0; for (let node = this.#head; node; node = node.next) { n += 1; if (node.v === v) return n; } return -1; } } class RingBuffer { // fixed slots; capacity doubles once full #slots; #head = 0; #n = 0; steps = 0; copies = 0; growths = 0; constructor(capacity) { this.#slots = new Array(capacity); } #grow() { if (this.#n < this.#slots.length) return; const grown = new Array(this.#slots.length * 2); for (let i = 0; i < this.#n; i += 1) grown[i] = this.#slots[(this.#head + i) % this.#slots.length]; this.steps += this.#n; this.copies += this.#n; this.growths += 1; this.#slots = grown; this.#head = 0; } pushBack(v) { this.#grow(); this.steps += 1; this.#slots[(this.#head + this.#n) % this.#slots.length] = v; this.#n += 1; } pushFront(v) { this.#grow(); this.steps += 1; this.#head = (this.#head - 1 + this.#slots.length) % this.#slots.length; this.#slots[this.#head] = v; this.#n += 1; } popFront() { this.steps += 1; if (this.#n === 0) return undefined; const v = this.#slots[this.#head]; this.#slots[this.#head] = undefined; this.#head = (this.#head + 1) % this.#slots.length; this.#n -= 1; return v; } get length() { return this.#n; } get capacity() { return this.#slots.length; } get bytes() { let d = 0; for (let i = 0; i < this.#n; i += 1) d += Buffer.byteLength(this.#slots[(this.#head + i) % this.#slots.length]); return OVERHEAD + this.#slots.length * SLOT + d; } rank(v) { for (let i = 0; i < this.#n; i += 1) if (this.#slots[(this.#head + i) % this.#slots.length] === v) return i + 1; return -1; } } // --- workload: 20,000 requests to the back, 1 front pop every 4 requests, 1 priority push to the front every 40 requests const REQUESTS = 20_000; const value = (i) => `${10_000 + i}:${40_000 + i * 2}`; const operations = []; for (let i = 1; i <= REQUESTS; i += 1) { operations.push(["back", value(i)]); if (i % 4 === 0) operations.push(["pop", null]); if (i % 40 === 0) operations.push(["front", `9${value(i)}`]); } const run = (list) => { for (const [op, v] of operations) { if (op === "back") list.pushBack(v); else if (op === "front") list.pushFront(v); else list.popFront(); } return list; }; const ring = new RingBuffer(1024); const structures = [["contiguous array", run(new ArrayList())], ["linked node", run(new LinkedList())], ["ring buffer", run(ring)]]; console.log(`${operations.length} operations (${REQUESTS} to the back, ${REQUESTS / 4} pops from the front, ${REQUESTS / 40} to the front)`); console.log(`${"structure".padEnd(15)}${"length".padStart(9)}${"bytes held".padStart(14)}` + `${"per entry".padStart(13)}${"total steps".padStart(13)}${"per operation".padStart(14)}`); for (const [name, list] of structures) console.log(name.padEnd(15) + String(list.length).padStart(9) + String(list.bytes).padStart(14) + (list.bytes / list.length).toFixed(1).padStart(13) + String(list.steps).padStart(13) + (list.steps / operations.length).toFixed(1).padStart(14)); console.log(`ring buffer: ${ring.growths} growths, ${ring.copies} copy steps, capacity ${ring.capacity}, ` + `empty slots ${ring.capacity - ring.length}`); const target = value(19_000); console.log(`\n"${target}" ranked at: ` + structures.map(([name, list]) => `${name} -> rank ${list.rank(target)}`).join(", ")); ``` ``` 25500 operations (20000 to the back, 5000 pops from the front, 500 to the front) structure length bytes held per entry total steps per operation contiguous array 15500 294557 19.0 42662750 1673.0 linked node 15500 666557 43.0 25500 1.0 ring buffer 15500 301629 19.5 40860 1.6 ring buffer: 4 growths, 15360 copy steps, capacity 16384, empty slots 884 "29000:78000" ranked at: contiguous array -> rank 14500, linked node -> rank 14500, ring buffer -> rank 14500 ``` All three structures carry the same 15,500-person waiting list; the bytes they hold and the steps they spend are far apart. The contiguous array is the cheapest at 19.0 bytes per entry, but because every front operation shifts every remaining entry, it spends 1,673 steps per operation; the total for 25,500 operations is 42.7 million steps. Calling one person off the waiting list means moving everyone else's position. The linked node reverses this: every operation is exactly 1 step, 25,500 total. Its price is 43.0 bytes per entry — 2.26 times the array's cost. The difference is purely pointer overhead: every entry carries an extra 24 bytes for two neighbor pointers and the node header. A member identifier itself is 11 bytes, while binding it into the sequence costs 24 — as much space as the data itself goes toward describing the data's position. The ring buffer shows the third path, and it is the best purchase for this workload: 19.5 bytes per entry — only 0.5 bytes more than the array — and 1.6 steps per operation. Keeping a head pointer turns removal from the front from a shift into a constant step. Its price is capacity management: starting with 1,024 slots, it has grown four times, spent 15,360 copy steps, and ends up holding 884 empty slots. The only thing the linked node buys over the ring buffer is those 15,360 steps, and its price is 364,928 bytes: 23.8 bytes per step. That is a poor purchase for a waiting list; the decision is set by this ratio, not by the structure's name. The last line shows a limit common to all three. A given member's rank is 14,500 in all three structures, and finding it means walking 14,500 entries. The list holds order but does not provide lookup by order; going from membership to position is a scan in every case. #### The Price of Trimming The second use is the recent-activity list: every loan, return, renewal, and reservation is written to the end of the list, and the clerk panel asks for the "last m events." If this list is never trimmed, it grows all day. **DS4:** the day is 43,200 seconds and produces 60,000 events; an entry averages 25.7 bytes. **DS5:** 2,000 queries arrive, the requested m is skewed toward small values with a visible seed, and a trimmed list is counted at ring-buffer cost. ```js // memory/trim.mjs — the recent-activity list: holding it unbounded vs. trimming it to // a fixed length. A trimmed list is counted at ring-buffer cost: 56 + capacity*8 + live value bytes. const OVERHEAD = 56, SLOT = 8, DAY = 43_200, EVENTS = 60_000, QUERIES = 2_000, SEED = 20240115; let state = SEED; const rand = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648; const KIND = ["loan", "return", "renewal", "reservation"]; const events = Array.from({ length: EVENTS }, (_, i) => `${Math.floor(i * DAY / EVENTS)}|${10_000 + (i * 7919) % 20_000}|${KIND[i % 4]}|${100_000 + (i * 4241) % 200_000}`); const valueBytes = events.map((e) => Buffer.byteLength(e)); const totalBytes = valueBytes.reduce((t, x) => t + x, 0); // query: "last m events" — skewed toward small m, seeded const queries = Array.from({ length: QUERIES }, () => 1 + Math.floor(3_000 * rand() ** 2)); console.log(`${EVENTS} events / ${DAY} s, sample "${events[41]}" (${valueBytes[41]} bytes), ` + `average ${(totalBytes / EVENTS).toFixed(1)} bytes`); console.log(`${QUERIES} queries, largest m ${Math.max(...queries)}, median m ${[...queries].sort((a, b) => a - b)[QUERIES / 2]}`); console.log(`\n${"limit".padStart(9)}${"bytes held".padStart(14)}${"dropped".padStart(11)}` + `${"covered s".padStart(13)}${"queries satisfied".padStart(19)}${"rate".padStart(8)}`); for (const k of [100, 1_000, 10_000, EVENTS]) { const live = events.slice(EVENTS - k); const bytes = OVERHEAD + k * SLOT + valueBytes.slice(EVENTS - k).reduce((t, x) => t + x, 0); const span = Number(live.at(-1).split("|")[0]) - Number(live[0].split("|")[0]); const satisfied = queries.filter((m) => m <= k).length; console.log(String(k === EVENTS ? "unbounded" : k).padStart(9) + String(bytes).padStart(14) + String(EVENTS - k).padStart(11) + String(span).padStart(13) + String(satisfied).padStart(19) + `%${(100 * satisfied / QUERIES).toFixed(1)}`.padStart(8)); } ``` ``` 60000 events / 43200 s, sample "29|14679|return|273881" (22 bytes), average 25.7 bytes 2000 queries, largest m 2999, median m 752 limit bytes held dropped covered s queries satisfied rate 100 3456 59900 71 368 %18.4 1000 34056 59000 719 1167 %58.4 10000 340056 50000 7199 2000 %100.0 unbounded 2024625 0 43199 2000 %100.0 ``` The unbounded list closes out the day at 2,024,625 bytes and keeps growing at the same rate the next day; a list has no natural stopping point. The 10,000-entry trim satisfies all 2,000 of the same queries, and it does so with 16.8 percent of the unbounded list's memory: the 1.7 MB saved costs nothing on the query side. The **covered s** column tells us where the cost is. The 10,000-entry list only covers the last 7,199 seconds, that is, two hours; the unbounded list covers twelve hours. Because nobody in this workload asks further back than two hours, the loss is invisible — but invisible does not mean it does not exist. When the limit drops to 1,000, memory falls to 34,056 bytes and the list covers only 719 seconds, twelve minutes; 41.6 percent of queries get an incomplete answer. At the 100 limit, coverage drops to 71 seconds and the satisfied rate falls to 18.4 percent. The real warning here is not in the numbers themselves, it is in the shape of the error. A trimmed list does not say "I do not have it"; it gives whatever it has. A query asking for 2,400 events gets 1,000 records back from a 1,000-entry list and uses the answer without knowing it is incomplete. The limit is chosen where the memory budget and the query distribution intersect, and once the distribution shifts, it silently starts producing wrong answers. #### Summary - A queue and a stack are not separate structures; they are which end of the same list items are added to and removed from. The waiting list is a queue, the clerk's undo sequence is a stack. - Across the same 25,500 operations, the contiguous array holds 19.0 bytes per entry but spends 1,673 steps per operation; the linked node drops to 1 step per operation and demands 43.0 bytes per entry (2.26 times). - The ring buffer closes the gap between the two: 19.5 bytes and 1.6 steps. The 15,360 steps the linked node buys over it are priced at 364,928 bytes — 23.8 bytes per step. - Rank lookup is a scan in all three structures: the target entry ranks 14,500th and finding it takes 14,500 steps. The list holds order but does not provide lookup by order. - The recent-activity list closes out the day at 2,024,625 bytes when it is never trimmed, and it has no stopping point. A 10,000-entry limit cuts memory to 16.8 percent and satisfies all 2,000 queries in this workload. - The real price of trimming is the covered time window: 10,000 entries cover two hours, 1,000 entries cover twelve minutes. A trimmed list does not report that its answer is incomplete; it gives whatever it has. #### Next Step Everything placed in the store up to this point has been a single-piece value: a session record is a whole, a counter is a number, a list entry is a string. The library's actual record is not like that. A book has a title, an author, a shelf code, a status, and a loan count; status changes several times an hour while the title never changes. Holding the whole record as a single value means writing the whole record to update a single field. The next lesson builds this record in two more shapes and measures three things: the bytes written on a single-field update, the bytes read on a single-field read, and the overhead share that managing fields separately asks back. ### Hash Structures Source: https://academia.sh/en/courses/in-memory-stores/hashes The cost and the payoff of introducing object fields to the store: building the same book record in holistic-value, dense-hash, and per-field-entry shapes and measuring it under daily loan load by bytes held, bytes written, bytes read, round trips, and steps, per-field overhead roughly doubling record cost, and how the dense representation's memory gain is paid for in scan steps as field count grows, plus a threshold policy's catalog-wide outcome. Everything placed in the store up to this point has been a single piece: a session record is a whole, a counter is a number, a list entry is a string. The library's actual record is not like that. A book has a title, an author, a shelf code, a status, a loan count, a date added, and a number. These fields also do not change at the same rate: status changes many times a day, the title never changes. In a holistic value, the store has no concept of a field; updating a single field means reading the whole record and writing it back — and the lost-update problem measured in the previous lesson comes from exactly this. The hash structure is the alternative: the store knows the record's fields, reads by name, writes by name. This lesson asks the price of that knowledge. #### The Same Record, Three Shapes Three shapes are compared. A **holistic value** holds the record as a single serialized string. A **dense hash** holds the fields consecutively in one block, but the store knows the field boundaries; a single-field request is served by scanning the block. A **hash structure** holds every field as its own entry and accesses it by name in a single step. **DS1:** the catalog carries 200,000 books, each record has seven fields, and field values come from deterministic functions. **DS2:** overhead per structure is 56 bytes, overhead per field is 40 bytes (hash bucket pointer, pointers for the field name and value, length fields). **DS3:** `bytesRead` and `bytesWritten` are the bytes the store touches for that operation, `roundTrips` is the client's call count, `steps` is the number of fields resolved or compared. **DS4:** during the day, 119,993 loan/return events update two fields (status and loan count), 400,000 status queries read one field, 60,000 book pages read the whole record. ```js // memory/hash.mjs — the same book record in three shapes. read/written = bytes the // store touches for that operation, roundTrips = client call count, steps = field // lookup/comparison count. The workload is deterministic. const OVERHEAD = 56, FIELD_OVERHEAD = 40, BOOKS = 200_000; // DS2 const bl = (x) => Buffer.byteLength(String(x)); const key = (i) => `book:${100_000 + i}`; const record = (i) => ({ title: `Notes on Book ${100_000 + i}`, author: `Author ${i % 997}`, shelf: `K-${1 + (i % 20)}-${String(i % 400).padStart(3, "0")}`, status: i % 3 === 0 ? "on_loan" : "on_shelf", loan_count: String(1 + (i * 7919) % 4096), added: `20${10 + (i % 15)}-${String(1 + (i % 12)).padStart(2, "0")}-14`, isbn: String(9_780_000_000_000 + i), }); class HolisticStore { // the value is a single piece: the store does not know fields #table = new Map(); bytesRead = 0; bytesWritten = 0; roundTrips = 0; steps = 0; put(key, record) { this.#table.set(key, JSON.stringify(record)); } readAll(key) { this.roundTrips += 1; const s = this.#table.get(key); this.bytesRead += bl(s); const record = JSON.parse(s); this.steps += Object.keys(record).length; return record; } // every field is parsed readField(key, field) { return this.readAll(key)[field]; } // the whole value is read, one field used writeField(key, field, value) { const record = this.readAll(key); record[field] = value; // read-modify-write const s = JSON.stringify(record); this.roundTrips += 1; this.bytesWritten += bl(key) + bl(s); this.#table.set(key, s); } bytes() { let b = 0; for (const [key, s] of this.#table) b += bl(key) + bl(s) + OVERHEAD; return b; } } class DenseHashStore { // fields sit consecutively in one blob; the store knows fields #table = new Map(); bytesRead = 0; bytesWritten = 0; roundTrips = 0; steps = 0; put(key, record) { this.#table.set(key, Object.entries(record).map(([k, v]) => `${k}=${v}`).join(";")); } #find(s, field) { for (const part of s.split(";")) { this.steps += 1; if (part.startsWith(`${field}=`)) return part; } return null; } readAll(key) { this.roundTrips += 1; const s = this.#table.get(key); this.bytesRead += bl(s); return Object.fromEntries(s.split(";").map((part) => part.split("="))); } readField(key, field) { this.roundTrips += 1; const s = this.#table.get(key); this.bytesRead += bl(s); const part = this.#find(s, field); return part === null ? undefined : part.slice(field.length + 1); } writeField(key, field, value) { this.roundTrips += 1; const s = this.#table.get(key); this.bytesRead += bl(s); const updated = s.split(";").map((part) => { this.steps += 1; return part.startsWith(`${field}=`) ? `${field}=${value}` : part; }).join(";"); this.bytesWritten += bl(key) + bl(updated); this.#table.set(key, updated); } // the blob is rewritten bytes() { let b = 0; for (const [key, s] of this.#table) b += bl(key) + bl(s) + OVERHEAD; return b; } } class HashStore { // every field is its own entry: accessed by name #table = new Map(); bytesRead = 0; bytesWritten = 0; roundTrips = 0; steps = 0; put(key, record) { this.#table.set(key, new Map(Object.entries(record).map(([k, v]) => [k, String(v)]))); } readAll(key) { this.roundTrips += 1; const fields = this.#table.get(key); for (const [k, v] of fields) { this.steps += 1; this.bytesRead += bl(k) + bl(v); } return Object.fromEntries(fields); } readField(key, field) { this.roundTrips += 1; this.steps += 1; const v = this.#table.get(key).get(field); this.bytesRead += bl(v); return v; } writeField(key, field, value) { this.roundTrips += 1; this.steps += 1; this.bytesWritten += bl(key) + bl(field) + bl(value); this.#table.get(key).set(field, String(value)); } bytes() { let b = 0; for (const [key, fields] of this.#table) { b += bl(key) + OVERHEAD; for (const [k, v] of fields) b += bl(k) + bl(v) + FIELD_OVERHEAD; } return b; } } const sample = record(427); console.log(`sample ${key(427)}: ${Object.keys(sample).length} fields, JSON ${bl(JSON.stringify(sample))} bytes, ` + `field names ${Object.keys(sample).reduce((t, k) => t + bl(k), 0)} bytes, ` + `field values ${Object.values(sample).reduce((t, v) => t + bl(v), 0)} bytes`); const stores = [["holistic value", new HolisticStore()], ["dense hash", new DenseHashStore()], ["hash structure", new HashStore()]]; for (const [, store] of stores) for (let i = 1; i <= BOOKS; i += 1) store.put(key(i), record(i)); // daily load: 119,993 loan/return events update two fields, 400,000 status queries, 60,000 full reads const LOANS = 119_993, STATUS_QUERIES = 400_000, PAGE_VIEWS = 60_000; for (const [, store] of stores) { for (let j = 0; j < LOANS; j += 1) { const i = 1 + (j * 4241) % BOOKS; store.writeField(key(i), "status", j % 2 === 0 ? "on_loan" : "on_shelf"); store.writeField(key(i), "loan_count", String(1 + (i * 7919) % 4096)); } for (let j = 0; j < STATUS_QUERIES; j += 1) store.readField(key(1 + (j * 7919) % BOOKS), "status"); for (let j = 0; j < PAGE_VIEWS; j += 1) store.readAll(key(1 + (j * 4241) % BOOKS)); } console.log(`\n${BOOKS} books; daily load ${2 * LOANS} field writes, ${STATUS_QUERIES} field reads, ${PAGE_VIEWS} full reads`); console.log(`${"shape".padEnd(16)}${"bytes held".padStart(14)}${"per record".padStart(13)}` + `${"written".padStart(10)}${"read".padStart(11)}${"round trips".padStart(13)}${"steps".padStart(9)}`); for (const [name, store] of stores) console.log(name.padEnd(16) + String(store.bytes()).padStart(14) + (store.bytes() / BOOKS).toFixed(1).padStart(13) + String(store.bytesWritten).padStart(10) + String(store.bytesRead).padStart(11) + String(store.roundTrips).padStart(13) + String(store.steps).padStart(9)); ``` ``` sample book:100427: 7 fields, JSON 156 bytes, field names 41 bytes, field values 72 bytes 200000 books; daily load 239986 field writes, 400000 field reads, 60000 full reads shape bytes held per record written read round trips steps holistic value 44547129 222.7 39998208 109012753 939972 4899902 dense hash 38547129 192.7 32798628 88013173 699986 3279902 hash structure 91947129 459.7 5907195 9786807 699986 1059986 ``` The hash structure's price shows up in the first column: the same 200,000 records hold 44.5 MB as a holistic value and 91.9 MB as a hash structure, 222.7 bytes per record against 459.7. The difference is a single line item: each of the seven fields is its own entry, and every entry carries 40 bytes of overhead along with a copy of the field name. Of the 237-byte increase per record, 280 bytes is field overhead — meaning more space than the record itself goes toward recognizing the fields separately. What that buys is in the other four columns. A single-field update writes the entire record in a holistic value; 40.0 MB is written over the day. In a hash structure, only the key, the field name, and the new value are written: 5.9 MB, 6.8 times less. The gap on the read side is larger. Each of the 400,000 status queries reads out the entire 156-byte record in a holistic value; the total is 109.0 MB against 9.8 MB in a hash structure — 11.1 times. Round trips also fall: because a field update is read-modify-write in a holistic value, it needs two calls, 939,972 against 699,986. These 239,986 extra round trips are not just a traffic line item; the previous lesson's lost update arises from exactly this gap. In a hash structure, a field update is a single call and cannot be split. The middle row carries the lesson's surprise. Even though the dense hash holds fields in a single block, it takes up less space than the holistic value (192.7 bytes, because there is no delimiter and quote overhead) while also preserving the concept of a field: round trips drop to 699,986, and updates become unsplittable. Across a seven-field record, there is no single column where the holistic value beats the dense hash. What the dense hash pays for is the step column: finding a single field means scanning the block, 3,279,902 steps. The hash structure finishes the same job in 1,059,986 steps. #### Where the Threshold Is At seven fields, the dense hash is a good choice; the scan is four steps. As field count grows, this changes. **DS5:** for comparison, the field name is 9 bytes and the field value is 7 bytes, and record kinds in the catalog come in four different sizes. ```js // memory/threshold.mjs — as field count grows, dense and hash representations // diverge, and the catalog-wide cost of a threshold policy. All numbers are structural. const OVERHEAD = 56, FIELD_OVERHEAD = 40; const fieldName = (j) => `field_${String(j).padStart(3, "0")}`; const fieldValue = (j) => String(1_000_000 + j * 7919); const bl = (x) => Buffer.byteLength(String(x)); const KEY = bl("book:100427"); const denseBytes = (f) => KEY + OVERHEAD + bl(Array.from({ length: f }, (_, j) => `${fieldName(j)}=${fieldValue(j)}`).join(";")); const hashBytes = (f) => KEY + OVERHEAD + Array.from({ length: f }, (_, j) => bl(fieldName(j)) + bl(fieldValue(j)) + FIELD_OVERHEAD).reduce((t, x) => t + x, 0); console.log(`field name ${bl(fieldName(0))} bytes, field value ${bl(fieldValue(0))} bytes, ` + `field overhead ${FIELD_OVERHEAD} bytes, key ${KEY} bytes`); console.log(`\n${"fields".padStart(6)}${"dense bytes".padStart(13)}${"hash bytes".padStart(12)}${"ratio".padStart(7)}` + `${"dense access steps".padStart(20)}${"dense field write".padStart(19)}${"hash field write".padStart(18)}`); for (const f of [4, 7, 16, 64, 256]) { const dense = denseBytes(f), hash = hashBytes(f); console.log(String(f).padStart(6) + String(dense).padStart(13) + String(hash).padStart(12) + (hash / dense).toFixed(2).padStart(7) + `${((f + 1) / 2).toFixed(1)} / ${f}`.padStart(20) + String(dense - OVERHEAD).padStart(19) + String(KEY + bl(fieldName(0)) + bl(fieldValue(0))).padStart(18)); } // catalog: four record kinds, three policies const kinds = [["book record", 200_000, 7], ["member profile", 20_000, 12], ["branch daily counter", 5, 24], ["popular book tag counter", 2_000, 256]]; console.log(`\n${"record kind".padEnd(29)}${"count".padStart(8)}${"fields".padStart(7)}` + `${"all dense".padStart(13)}${"all hash".padStart(13)}${"threshold 64".padStart(14)}`); let totalDense = 0, totalHash = 0, totalThreshold = 0; for (const [name, n, f] of kinds) { const dense = n * denseBytes(f), hash = n * hashBytes(f), chosen = f <= 64 ? dense : hash; totalDense += dense; totalHash += hash; totalThreshold += chosen; console.log(name.padEnd(29) + String(n).padStart(8) + String(f).padStart(7) + String(dense).padStart(13) + String(hash).padStart(13) + String(chosen).padStart(14)); } console.log("total".padEnd(29) + "".padStart(8) + "".padStart(7) + String(totalDense).padStart(13) + String(totalHash).padStart(13) + String(totalThreshold).padStart(14)); console.log(`threshold 64: %${(100 * totalThreshold / totalHash).toFixed(1)} of all-hash, %` + `${(100 * totalThreshold / totalDense).toFixed(1)} of all-dense; worst-case field access is 64 steps`); ``` ``` field name 9 bytes, field value 7 bytes, field overhead 40 bytes, key 11 bytes fields dense bytes hash bytes ratio dense access steps dense field write hash field write 4 138 291 2.11 2.5 / 4 82 27 7 192 459 2.39 4.0 / 7 136 27 16 354 963 2.72 8.5 / 16 298 27 64 1218 3651 3.00 32.5 / 64 1162 27 256 4674 14403 3.08 128.5 / 256 4618 27 record kind count fields all dense all hash threshold 64 book record 200000 7 38400000 91800000 38400000 member profile 20000 12 5640000 14780000 5640000 branch daily counter 5 24 2490 7055 2490 popular book tag counter 2000 256 9348000 28806000 28806000 total 53390490 135393055 72848490 threshold 64: %53.8 of all-hash, %136.4 of all-dense; worst-case field access is 64 steps ``` The upper table sets two curves side by side. The memory ratio climbs from 2.11 to 3.08 as field count grows — the dense representation's gain increases further on larger records. But two columns grow in opposite directions. In the dense representation, finding a field averages `(f+1)/2` steps, rising to 128.5 steps at 256 fields and 256 steps in the worst case. Sharper still is the single-field write: the dense representation rewrites the entire block, 4,618 bytes at 256 fields. The same write in a hash structure is 27 bytes, independent of field count. The write multiplier from the list lesson returns here, and it grows in direct proportion to field count. The lower table gives the decision at catalog scale. Keeping everything dense costs 53.4 MB, keeping everything as a hash structure costs 135.4 MB. A threshold policy — dense below 64 fields, hash structure above — holds steady at 72.8 MB: 53.8 percent of keeping everything as a hash structure. The price of the 62.5 MB saved in between is at most a 7-step scan across the 200,000 book records. The same policy, by keeping the 2,000 tag counters as a hash structure, avoids a 256-step scan and a 4,618-byte write. The threshold policy spends 36.4 percent more memory than keeping everything dense, and in return it caps the worst-case field access at 64 steps instead of 256. The decision is not choosing one representation over the other, it is choosing where the line runs. #### Summary - In a holistic value, the store has no concept of a field: a single-field update reads and writes the entire record and needs two round trips; the lost update arises from exactly this gap. - 200,000 records hold 44.5 MB as a holistic value and 91.9 MB as a hash structure. Most of the 237-byte increase per record is the 40-byte overhead per field. - What the hash structure buys is a drop in daily write traffic from 40.0 MB to 5.9 MB, in read traffic from 109.0 MB to 9.8 MB, and in round trips from 939,972 to 699,986. - At seven fields, the dense hash loses to the holistic value in no column: 192.7 bytes, the same round-trip count, and an unsplittable field update. The only price it pays is the scan step count (3,279,902 against 1,059,986). - As field count grows, the dense representation's memory gain increases (ratio rising from 2.11 to 3.08), but access rises to an average of `(f+1)/2` steps, and a single-field write climbs to 4,618 bytes at 256 fields; the same write is 27 bytes in a hash structure. - A threshold policy (dense up to 64 fields) holds 72.8 MB catalog-wide: 53.8 percent of keeping everything as a hash structure, 136.4 percent of keeping everything dense. What that buys is capping the worst-case access at 64 steps. #### Next Step The hash structure separated a record's fields, but they all still belonged to a single record. Some of the library's questions do not belong to a single record: "is this book among the ones currently on loan," "is this member on the fine list," "which twenty books are borrowed the most." The first is a membership question and its answer is yes or no; the last is a rank question and its answer is a sorted list. The next lesson takes up these two structures and measures three things: the step count of a membership check, the step count of a rank query in a sorted set, and the bytes-per-entry cost of both. ### Sets and Sorted Sets Source: https://academia.sh/en/courses/in-memory-stores/sets-and-sorted-sets The memory price of membership and rank questions: building the same on-loan book set as a list, sorted array, and hash-based set and measuring it in query steps, insertion steps, and bytes per entry, building the popular-book ranking on a member-score hash with three separate rank indexes, how much the skip list's pointer cost buys down the rank query, and how the sorted array buys nothing under update load. The hash structure separated a record's fields, but every field still belonged to a single record. Some of the library's questions do not belong to a single record. "Is this book currently among the ones on loan" is a membership question, and its answer is yes or no. "Where does this book rank among the most-borrowed" is a rank question, and its answer is a number, but one read off a sorted whole. Both questions require the same thing: holding in memory which members are present. The complexity analysis of these structures has already been done elsewhere; what is measured here is bytes held and store semantics. #### Membership: Yes or No **DS1:** 38,000 books are on loan during the day, the member identifier is 6 bytes; half of the 10,000 membership queries ask about a book that is in the set, half about one that is not. **DS2:** an array slot is 8 bytes, structure overhead is 56 bytes, overhead per set entry is 48 bytes (bucket pointer, entry structure, hash value, alignment). ```js // memory/membership.mjs — "is this book currently on loan" in three structures. Steps // are counted inside the implementation; the workload is deterministic. const OVERHEAD = 56, SLOT = 8, SET_OVERHEAD = 48; // DS2 const bl = (x) => Buffer.byteLength(String(x)); const ON_LOAN = 38_000, QUERIES = 10_000, BOOKS = 200_000; const member = (i) => String(100_000 + (i * 4241) % BOOKS); const members = [...new Set(Array.from({ length: ON_LOAN }, (_, i) => member(i)))]; class ListMembership { // order is preserved, membership is a scan #items = []; steps = 0; insertSteps = 0; insert(v) { this.insertSteps += 1; this.#items.push(v); } has(v) { for (const x of this.#items) { this.steps += 1; if (x === v) return true; } return false; } bytes() { return OVERHEAD + this.#items.reduce((t, v) => t + bl(v) + SLOT, 0); } get size() { return this.#items.length; } } class SortedArrayMembership { // binary search; insertion needs shifting #items = []; steps = 0; insertSteps = 0; #locate(v) { let lo = 0, hi = this.#items.length; while (lo < hi) { this.steps += 1; const mid = (lo + hi) >> 1; if (this.#items[mid] < v) lo = mid + 1; else hi = mid; } return lo; } insert(v) { const i = this.#locate(v); this.insertSteps += this.#items.length - i + 1; this.#items.splice(i, 0, v); } has(v) { const i = this.#locate(v); return this.#items[i] === v; } bytes() { return OVERHEAD + this.#items.reduce((t, x) => t + bl(x) + SLOT, 0); } get size() { return this.#items.length; } } class SetMembership { // hash: a single step, extra overhead per entry #set = new Set(); steps = 0; insertSteps = 0; insert(v) { this.insertSteps += 1; this.#set.add(v); } has(v) { this.steps += 1; return this.#set.has(v); } bytes() { let b = OVERHEAD; for (const v of this.#set) b += bl(v) + SET_OVERHEAD; return b; } get size() { return this.#set.size; } } const structures = [["list", new ListMembership()], ["sorted array", new SortedArrayMembership()], ["set", new SetMembership()]]; for (const [, impl] of structures) for (const v of members) impl.insert(v); // half the queries ask about a book that is in the set, half about one that is not const queries = Array.from({ length: QUERIES }, (_, j) => j % 2 === 0 ? members[(j * 7919) % members.length] : String(100_000 + BOOKS + j)); let found = 0; for (const [, impl] of structures) { let f = 0; for (const q of queries) if (impl.has(q)) f += 1; found = f; } console.log(`${members.length} books on loan (member ${bl(members[0])} bytes), ${QUERIES} membership queries, ` + `${found} found`); console.log(`${"structure".padEnd(13)}${"bytes held".padStart(14)}${"per entry".padStart(13)}` + `${"query steps".padStart(13)}${"per query".padStart(14)}${"insert steps".padStart(14)}`); for (const [name, impl] of structures) console.log(name.padEnd(13) + String(impl.bytes()).padStart(14) + (impl.bytes() / impl.size).toFixed(1).padStart(13) + String(impl.steps).padStart(13) + (impl.steps / QUERIES).toFixed(1).padStart(14) + String(impl.insertSteps).padStart(14)); ``` ``` 38000 books on loan (member 6 bytes), 10000 membership queries, 5000 found structure bytes held per entry query steps per query insert steps list 532056 14.0 284642000 28464.2 38000 sorted array 532056 14.0 676550 67.7 360742025 set 2052056 54.0 10000 1.0 38000 ``` The list and the sorted array hold the same 532,056 bytes, 14.0 per entry. The set demands 2,052,056 bytes for the same 38,000 members — 54.0 per entry, that is, 3.86 times. The difference is a single line item: 40 bytes per member for the bucket pointer and the entry structure. Holding a six-byte book identifier in a set costs nine times the identifier's own size. The payoff is in the query column: the list answers each question in an average of 28,464.2 steps, the set in 1. The sorted array looks like an interesting middle ground — 67.7 steps at the list's memory cost — but the insert column finishes it off. In a sorted array, every insertion shifts the remaining entries: 38,000 insertions cost 360,742,025 steps, 9,493 per insertion. The set of books on loan is not static; during the day, every loan is an insertion and every return is a removal. In this workload, the sorted array gives back what it gains on queries a hundred times over on insertion. The 1,520,000 extra bytes the set holds bring both the query and the insertion down to a single step. What it loses does not show up in any column: the set does not preserve order. The list carried the 38,000 books in insertion order; the set carries the same books, but there is no information about which was loaned out first. Order is abandoned in exchange for the membership answer. #### Rank: Where in the Order A leaderboard asks two questions at once: what is a book's score, and where does that score rank. A member-score hash is enough for the first question and is common to all three approaches; the second needs a **rank index**. **DS3:** 50,000 books have a popularity score, 10,000 loans increment a score, 2,000 rank queries and 200 "top 20" queries arrive. **DS4:** the skip list's node levels come from a generator with a visible seed; the node header is 24 bytes, the pointer pair per level is 16 bytes. The ranks given by all three approaches are checked against brute force. ```js // memory/ranking.mjs — popular-book ranking: three rank indexes over a member->score // hash. Skip list levels come from a seeded generator; ranks are checked by brute force. const OVERHEAD = 56, SLOT = 8, SET_OVERHEAD = 48, NODE = 24, POINTER = 16; // DS2 const BOOKS = 50_000, UPDATES = 10_000, QUERIES = 2_000, TOP = 20, SEED = 20240115; const bl = (x) => Buffer.byteLength(String(x)); let c = SEED; const rand = () => (c = (c * 1103515245 + 12345) % 2147483648) / 2147483648; const member = (i) => String(100_000 + i); const score0 = (i) => 1 + (i * 7919) % 4096; const before = (score1, member1, score2, member2) => score1 > score2 || (score1 === score2 && member1 < member2); // score descending, member ascending class SkipList { #head; #level = 1; #n = 0; #maxLevel; steps = 0; pointers = 0; constructor(maxLevel = 16) { this.#maxLevel = maxLevel; this.#head = { member: "", score: 0, forward: new Array(maxLevel).fill(null), span: new Array(maxLevel).fill(0) }; } #pickLevel() { let lvl = 1; while (rand() < 0.5 && lvl < this.#maxLevel) lvl += 1; return lvl; } #path(score, member) { const update = new Array(this.#maxLevel), rankSum = new Array(this.#maxLevel).fill(0); let node = this.#head; for (let i = this.#level - 1; i >= 0; i -= 1) { rankSum[i] = i === this.#level - 1 ? 0 : rankSum[i + 1]; while (node.forward[i] && before(node.forward[i].score, node.forward[i].member, score, member)) { this.steps += 1; rankSum[i] += node.span[i]; node = node.forward[i]; } update[i] = node; } return [update, rankSum, node.forward[0]]; } insert(member, score) { const [update, rankSum] = this.#path(score, member); const lvl = this.#pickLevel(); if (lvl > this.#level) { for (let i = this.#level; i < lvl; i += 1) { rankSum[i] = 0; update[i] = this.#head; this.#head.span[i] = this.#n; } this.#level = lvl; } const newNode = { member, score, forward: new Array(lvl), span: new Array(lvl) }; this.pointers += lvl; for (let i = 0; i < lvl; i += 1) { newNode.forward[i] = update[i].forward[i]; update[i].forward[i] = newNode; newNode.span[i] = update[i].span[i] - (rankSum[0] - rankSum[i]); update[i].span[i] = (rankSum[0] - rankSum[i]) + 1; } for (let i = lvl; i < this.#level; i += 1) update[i].span[i] += 1; this.#n += 1; } remove(member, score) { const [update, , node] = this.#path(score, member); if (!node || node.member !== member || node.score !== score) return false; for (let i = 0; i < this.#level; i += 1) { if (update[i].forward[i] === node) { update[i].span[i] += node.span[i] - 1; update[i].forward[i] = node.forward[i]; } else update[i].span[i] -= 1; } this.pointers -= node.forward.length; while (this.#level > 1 && this.#head.forward[this.#level - 1] === null) this.#level -= 1; this.#n -= 1; return true; } rank(member, score) { const [, rankSum, node] = this.#path(score, member); return node && node.member === member ? rankSum[0] + 1 : -1; } top(k) { const r = []; let node = this.#head.forward[0]; while (node && r.length < k) { this.steps += 1; r.push(node.member); node = node.forward[0]; } return r; } bytes() { let b = OVERHEAD; let node = this.#head.forward[0]; while (node) { b += bl(node.member) + NODE + node.forward.length * POINTER; node = node.forward[0]; } return b; } get level() { return this.#level; } } const scores = new Map(); // member -> score; common to all three approaches for (let i = 1; i <= BOOKS; i += 1) scores.set(member(i), score0(i)); const scoresBytes = [...scores].reduce((t, [m]) => t + bl(m) + SLOT + SET_OVERHEAD, OVERHEAD); const sorted = [...scores].map(([m, s]) => [s, m]).sort((a, b) => (before(a[0], a[1], b[0], b[1]) ? -1 : 1)); const skip = new SkipList(); for (const [m, s] of scores) skip.insert(m, s); let sortedSteps = 0, noIndexSteps = 0; const locate = (score, m) => { let lo = 0, hi = sorted.length; while (lo < hi) { sortedSteps += 1; const mid = (lo + hi) >> 1; if (before(sorted[mid][0], sorted[mid][1], score, m)) lo = mid + 1; else hi = mid; } return lo; }; // daily load: score increments, rank queries, top K const events = Array.from({ length: UPDATES }, (_, j) => member(1 + (j * 4241) % BOOKS)); for (const m of events) { const oldScore = scores.get(m), newScore = oldScore + 1; const oldPos = locate(oldScore, m); sortedSteps += sorted.length - oldPos; sorted.splice(oldPos, 1); // shift const newPos = locate(newScore, m); sortedSteps += sorted.length - newPos; sorted.splice(newPos, 0, [newScore, m]); skip.remove(m, oldScore); skip.insert(m, newScore); scores.set(m, newScore); } const queries = Array.from({ length: QUERIES }, (_, j) => member(1 + (j * 7919) % BOOKS)); let matches = 0; for (const m of queries) { const score = scores.get(m); let rankNoIndex = 1; for (const [otherMember, otherScore] of scores) { noIndexSteps += 1; if (before(otherScore, otherMember, score, m)) rankNoIndex += 1; } const rankSorted = locate(score, m) + 1, rankSkip = skip.rank(m, score); if (rankNoIndex === rankSorted && rankSorted === rankSkip) matches += 1; } for (let j = 0; j < 200; j += 1) { [...scores].sort((a, b) => { noIndexSteps += 1; return before(a[1], a[0], b[1], b[0]) ? -1 : 1; }).slice(0, TOP); sortedSteps += TOP; sorted.slice(0, TOP); skip.top(TOP); } console.log(`${BOOKS} books, ${UPDATES} score increments, ${QUERIES} rank queries, 200 "top ${TOP}"`); console.log(`${matches}/${QUERIES} queries: all three approaches gave the same rank; skip list level ${skip.level}, ` + `pointers ${skip.pointers} (${(skip.pointers / BOOKS).toFixed(2)} per node), seed ${SEED}`); const paths = [ ["no rank index", scoresBytes, noIndexSteps], ["sorted array", scoresBytes + OVERHEAD + sorted.reduce((t, [, m]) => t + bl(m) + SLOT + SLOT, 0), sortedSteps], ["skip list", scoresBytes + skip.bytes(), skip.steps], ]; console.log(`\n${"rank index".padEnd(17)}${"bytes held".padStart(14)}${"index share".padStart(12)}` + `${"per entry".padStart(13)}${"total steps".padStart(13)}`); for (const [name, b, steps] of paths) console.log(name.padEnd(17) + String(b).padStart(14) + String(b - scoresBytes).padStart(12) + (b / BOOKS).toFixed(1).padStart(13) + String(steps).padStart(13)); ``` ``` 50000 books, 10000 score increments, 2000 rank queries, 200 "top 20" 2000/2000 queries: all three approaches gave the same rank; skip list level 13, pointers 102228 (2.04 per node), seed 20240115 rank index bytes held index share per entry total steps no rank index 3100056 0 62.0 212473400 sorted array 4200112 1100056 84.0 500247667 skip list 6235760 3135704 124.7 1336074 ``` All three approaches give the same rank in all 2,000 queries; the difference is only in price. If no rank index is held, the hash is 3,100,056 bytes, and every rank query walks every entry while every "top 20" query sorts the entire table: 212,473,400 steps. The sorted array buys nothing in this workload. It holds 1,100,056 extra bytes and pushes the total step count to 500,247,667 — worse than the no-index path. The reason is the same as in the previous section: while a rank query is cheap with binary search, every score increment shifts an average of fifty thousand entries to move the entry out of its old position and into its new one. A sorted array is good for a static table and the wrong choice for a leaderboard that keeps changing. The skip list holds 3,135,704 extra bytes — 124.7 bytes per entry, more than double the membership set — and brings the total step count down to 1,336,074. Every extra byte it holds prevents 67.3 steps. More than half of those bytes are neither score nor identifier: 102,228 pointer pairs, 2.04 levels per node, 1,635,648 bytes. The rank index's cost is not the data itself, it is the way of reaching the data in order. In exchange, both the rank query and the "top 20" query become independent of table size, and so does the score update. #### Summary - The membership question is answered correctly by all three structures: the list in 28,464.2 steps, the sorted array in 67.7, the set in 1.0. - The set holds the same 38,000 members in 2,052,056 bytes; the list and the sorted array in 532,056 bytes. The difference is 40 bytes per member of bucket and entry overhead — nine times the six-byte identifier. - The sorted array is deceptive for membership: the query is cheap, but 38,000 insertions cost 360,742,025 steps (9,493 per insertion). It is the worst choice for a membership set that keeps changing. - What the set loses is order: there is no information in the set about which book was loaned out first. - Holding no rank index for the leaderboard means 3,100,056 bytes and 212,473,400 steps; the sorted array holds 1,100,056 extra bytes and pushes the step count up to 500,247,667, because every score increment requires a shift. - The skip list holds 3,135,704 extra bytes and brings the step count down to 1,336,074: 67.3 steps per byte. 1,635,648 of those bytes are pure pointers — 2.04 levels per node. #### Next Step Both structures in this lesson gave the correct answer, and both did the same thing: they held exactly what they counted. The set carried the identity of 38,000 books one by one; the sorted set carried the identity, the score, and the rank position of 50,000 books. The same held true in earlier lessons — the hash structure held every field, the list held every entry, the counter held every key, each one individually. Yet part of the library's questions do not want the members themselves. "How many distinct members logged in today," "has anyone ever borrowed this book before," "on which days was anything loaned out" — the answer to these is a number or a yes-no, not a list of members. While a number is enough for the answer, the cost of holding every member in memory has not been asked in any of these lessons. The next lesson opens that question. ### Bitmaps and Probabilistic Structures Source: https://academia.sh/en/courses/in-memory-stores/bitmaps-and-probabilistic-structures The cost of keeping a member list when the number alone would do: the same distinct-reader question solved with an exact set, a bitmap, a probabilistic membership structure, and a cardinality estimate, the bytes each of the four structures holds read from its own buffer, the false positive rate measured, and how many bytes giving up certainty buys counted out. The structures covered so far keep what they count **exactly**. For a set to know its member count, every member number sits in memory; for a hash structure to know its field count, every field name sits in memory. This is unavoidable when a member has to be handed back. But not every question asks for the member back: the library's end-of-day report asks "how many distinct readers took a loan today," and the answer is a single number — holding hundreds of thousands of reader numbers in memory just to produce it has never been questioned as a decision. This lesson questions that decision. Two questions are separated: **cardinality estimation** ("how many distinct readers") and **membership** ("did this reader take a loan today"). Each can be answered with a different structure, a different byte budget, and a different degree of certainty. #### Two Questions, Four Structures The library's loan record accumulates in the in-memory store over the course of the day. At day's end the report asks for the distinct reader count; during the day the loan screen asks "has this reader already made a transaction today." | Code | Assumption | Value | Rationale | |---|---|---|---| | DS10 | registered reader | 2,000,000 | member number is a dense range starting from 1 | | DS11 | daily loan event | 900,000 | sum across all branches | | DS12 | distribution of events | 70% from 15% of readers | a core of frequent borrowers exists | | DS13 | deviation accepted for the report | 2% | the end-of-day report does not need an exact count | DS10 is this lesson's deciding assumption: because the member number is a **dense** range, the reader number can be used directly as a bit position. A sparse range would give the table's second row a completely different number; the lesson measures this at the end. #### Two Exact Structures The first setup fills two exact structures with the same data. The exact set is an open-addressed hash table and the bytes it holds are the size of its buffer; the bitmap uses the reader number directly as a bit position. ```js // distinct-count.mjs — the day's distinct readers who took a loan: exact set vs. bitmap. // Byte counts are read straight from the structure's own buffer, no estimate; the seed is visible. const READERS = 2_000_000, EVENTS = 900_000, SEED = 20260731; let d = SEED; // 32-bit integer generator, no overflow const rand = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; }; const reader = () => rand() < 0.7 // 70% of events, from 15% of readers ? 1 + Math.floor(rand() * READERS * 0.15) : 1 + Math.floor(rand() * READERS); class ExactSet { // open addressing, empty slot is 0 constructor() { this.k = 1024; this.t = new Int32Array(this.k); this.n = 0; } slot(t, k, x) { let i = (Math.imul(x, 2654435761) >>> 0) & (k - 1); while (t[i] !== 0 && t[i] !== x + 1) i = (i + 1) & (k - 1); return i; } add(x) { if ((this.n + 1) * 2 > this.k) this.grow(); const i = this.slot(this.t, this.k, x); if (this.t[i] === 0) { this.t[i] = x + 1; this.n += 1; } } contains(x) { return this.t[this.slot(this.t, this.k, x)] !== 0; } grow() { const y = new Int32Array(this.k * 2); for (const v of this.t) if (v !== 0) y[this.slot(y, this.k * 2, v - 1)] = v; this.t = y; this.k *= 2; } bytes() { return this.t.byteLength; } } class Bitmap { // the reader number is directly the bit position constructor(n) { this.b = new Uint8Array(Math.ceil(n / 8)); } add(x) { this.b[x >> 3] |= 1 << (x & 7); } contains(x) { return (this.b[x >> 3] & (1 << (x & 7))) !== 0; } count() { let s = 0; for (let v of this.b) while (v) { s += v & 1; v >>= 1; } return s; } bytes() { return this.b.byteLength; } } const set = new ExactSet(), bitmap = new Bitmap(READERS + 1); for (let i = 0; i < EVENTS; i += 1) { const o = reader(); set.add(o); bitmap.add(o); } const n = set.n, fmt = (x) => x.toLocaleString("en-US"); console.log(`model: ${fmt(READERS)} registered readers, ${fmt(EVENTS)} loan events, seed ${SEED}`); console.log(`distinct readers: ${fmt(n)} (bitmap gives the same count: ${fmt(bitmap.count())})\n`); console.log("structure".padEnd(14) + "bytes held".padStart(14) + "per distinct".padStart(14) + "membership".padStart(12) + "count".padStart(12)); for (const [label, y] of [["exact set", set], ["bitmap", bitmap]]) console.log(label.padEnd(14) + fmt(y.bytes()).padStart(14) + (y.bytes() / n).toFixed(2).padStart(14) + "exact".padStart(12) + "exact".padStart(12)); let mismatches = 0; // do both structures give the same answer for (let x = 1; x <= READERS; x += 7) if (set.contains(x) !== bitmap.contains(x)) mismatches += 1; console.log(`\n${fmt(Math.ceil(READERS / 7))} membership queries where the two structures differ: ${mismatches}`); const SPARSE = 1_000_000_000; // if a 9-digit member number were used console.log(`the bitmap depends on the number range: 1..${fmt(READERS)} takes ${fmt(bitmap.bytes())} bytes, ` + `1..${fmt(SPARSE)} takes ${fmt(Math.ceil(SPARSE / 8))} bytes (exact set unchanged: ${fmt(set.bytes())})`); ``` ``` model: 2,000,000 registered readers, 900,000 loan events, seed 20260731 distinct readers: 482,085 (bitmap gives the same count: 482,085) structure bytes held per distinct membership count exact set 4,194,304 8.70 exact exact bitmap 250,001 0.52 exact exact 285,715 membership queries where the two structures differ: 0 the bitmap depends on the number range: 1..2,000,000 takes 250,001 bytes, 1..1,000,000,000 takes 125,000,000 bytes (exact set unchanged: 4,194,304) ``` These numbers are in the **measurement** class: the distinct reader count depends on the seed, the bytes held do not — that number is the buffer's size and stays constant across runs with the same entry count. The bitmap holds **sixteen times** less space than the exact set (250,001 against 4,194,304 bytes) and loses nothing: the distinct count is the same, and the two structures never differ across the 285,715 membership queries. The reason: the bitmap uses the reader number **as an address, not as data**. The exact set has to store the number, because which number occupies a slot is only known if it was written; in a bitmap, where the number sits is already the number, so nothing is left to store, and cost per entry drops from 8.70 bytes to 0.52. What is lost shows up in the last line: the bitmap's cost depends **not on how many readers took a loan, but on how wide the number range is**. If the library switched to a nine-digit member number, the same 482,085 readers would need 125,000,000 bytes instead of 250,001; the exact set's cost would not change. A bitmap is free where the range is dense and unaffordable where it is sparse. #### Giving Up Certainty Both exact structures represent every reader individually. The next step is to abandon that representation: answering the same question with structures that **leave uncertain** which reader is inside. ```js // probabilistic-count.mjs — the same day, the same two questions, this time giving up certainty. // Membership structure and cardinality estimate; a full list is also kept for the accuracy measure. const READERS = 2_000_000, EVENTS = 900_000, SEED = 20260731, QUERIES = 300_000; let d = SEED; const rand = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d); t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; }; const reader = () => rand() < 0.7 ? 1 + Math.floor(rand() * READERS * 0.15) : 1 + Math.floor(rand() * READERS); const hash = (x, seed) => { let h = Math.imul(x ^ seed, 0x85ebca6b) >>> 0; h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35) >>> 0; return (h ^ (h >>> 16)) >>> 0; }; const truth = new Uint8Array(READERS + 1); // accuracy measure only, not the measured structure for (let i = 0; i < EVENTS; i += 1) truth[reader()] = 1; const members = [], outsiders = []; for (let x = 1; x <= READERS; x += 1) (truth[x] ? members : outsiders).push(x); const queries = outsiders.slice(0, QUERIES), n = members.length; const fmt = (x) => x.toLocaleString("en-US"); console.log(`model: ${fmt(n)} distinct readers, ${fmt(QUERIES)} negative membership queries, seed ${SEED}\n`); console.log("probabilistic membership structure (k = 3 hashes)"); console.log("bits".padEnd(10) + "bytes held".padStart(14) + "per distinct".padStart(14) + "false positive".padStart(15) + "expected".padStart(10) + "missed".padStart(11)); for (const p of [17, 18, 19, 20, 21, 22]) { const m = 1 << p, K = 3, b = new Uint8Array(m / 8); const positions = (x) => Array.from({ length: K }, (_, i) => hash(x, 0x1000 + i * 0x9e3779b1) % m); for (const x of members) for (const i of positions(x)) b[i >> 3] |= 1 << (i & 7); const contains = (x) => positions(x).every((i) => (b[i >> 3] & (1 << (i & 7))) !== 0); let fp = 0, missed = 0; for (const x of queries) if (contains(x)) fp += 1; for (const x of members) if (!contains(x)) missed += 1; const expected = (1 - Math.exp((-K * n) / m)) ** K; console.log(`2^${p}`.padEnd(10) + fmt(b.byteLength).padStart(14) + (b.byteLength / n).toFixed(2).padStart(14) + `%${((fp / QUERIES) * 100).toFixed(2)}`.padStart(15) + `%${(expected * 100).toFixed(2)}`.padStart(10) + `${missed}`.padStart(11)); } console.log("\ncardinality estimate (count only; does not answer membership)"); console.log("register".padEnd(10) + "bytes held".padStart(14) + "per distinct".padStart(14) + "estimate".padStart(12) + "deviation".padStart(11) + "theoretical".padStart(13)); for (const p of [8, 10, 12, 14]) { const m = 1 << p, R = new Uint8Array(m); for (const x of members) { const h = hash(x, 0x9e37), i = h >>> (32 - p), w = (h << p) >>> 0; const r = w === 0 ? 33 - p : Math.clz32(w) + 1; if (r > R[i]) R[i] = r; } let z = 0, zeros = 0; for (const v of R) { z += 2 ** -v; if (v === 0) zeros += 1; } let e = (0.7213 / (1 + 1.079 / m)) * m * m / z; if (e <= 2.5 * m && zeros > 0) e = m * Math.log(m / zeros); // linear counting correction console.log(`2^${p}`.padEnd(10) + fmt(R.byteLength).padStart(14) + (R.byteLength / n).toFixed(4).padStart(14) + fmt(Math.round(e)).padStart(12) + `%${(((e - n) / n) * 100).toFixed(2)}`.padStart(11) + `%${((1.04 / Math.sqrt(m)) * 100).toFixed(2)}`.padStart(13)); } ``` ``` model: 482,085 distinct readers, 300,000 negative membership queries, seed 20260731 probabilistic membership structure (k = 3 hashes) bits bytes held per distinct false positive expected missed 2^17 16,384 0.03 %99.99 %100.00 0 2^18 32,768 0.07 %98.83 %98.80 0 2^19 65,536 0.14 %82.26 %82.16 0 2^20 131,072 0.27 %42.09 %41.89 0 2^21 262,144 0.54 %12.41 %12.37 0 2^22 524,288 1.09 %2.53 %2.48 0 cardinality estimate (count only; does not answer membership) register bytes held per distinct estimate deviation theoretical 2^8 256 0.0005 476,215 %-1.22 %6.50 2^10 1,024 0.0021 481,111 %-0.20 %3.25 2^12 4,096 0.0085 474,849 %-1.50 %1.63 2^14 16,384 0.0340 478,877 %-0.67 %0.81 ``` In the upper table, the **missed** column reads zero on every row: the probabilistic membership structure never answers "no" for a member, because the bits of every added member are set and never cleared. The error runs in one direction only, and its name is **false positive**: even for a reader that was never added, the structure can find all three bits set. The measured ratio tracks the theoretical ratio row by row (12.41% against 12.37% at 2^21), so this ratio is not a surprise — it is a quantity **chosen** by the structure's size. The same pair of words also appears in software testing; there, a **false alarm** is a fixable defect of a test that flags correct code as broken, while the **false positive rate** measured here is written into the structure's definition — lowered by adding bytes, never zeroed. The lower table is the sharpest form of the trade-off. A register array holding 4,096 bytes counts 482,085 distinct readers with a 1.50% deviation: it holds **one thousand and twenty-four times** less space than the exact set, sixty-one times less than the bitmap. The size to pick is read from the last column, not from the measured deviation. The 256-byte array came out at 1.22% deviation on this run, but its theoretical margin of error is 6.50%; the first size that safely meets DS13's 2% tolerance is the 4,096-byte one, whose theoretical margin is 1.63%. What it gives up in return is absolute: this structure cannot answer "did this reader take a loan" **at any degree of certainty**, because the reader itself is never represented — only how many leading zeros its hash has is kept. #### Which Structure Buys What The four structures hold 4,194,304, 250,001, 524,288, and 4,096 bytes for the same day, respectively. The ranking breaks in a surprising place: **in a dense number range, the probabilistic membership structure loses to the bitmap.** The structure running at 2.53% false positive wants 524,288 bytes, the exact bitmap wants 250,001. So under these conditions, giving up certainty does not save memory — it costs more. The probabilistic membership structure wins where the range is **sparse**. The library's second question is this: which book ID changed hands at least once today? A book ID is not a dense number but a thirteen-digit string, and a bitmap has no address to use. There the exact set has to hold the string itself, while the probabilistic structure uses the string's hash and its size stays tied to the member count. The rule for choosing is not in the structure's name — it is in the **density of the key space**. There is also merging. The weekly distinct-reader question requires combining seven days of results. Bitmaps merge with a bitwise OR and stay exact; cardinality estimates merge by taking the maximum per register and the deviation does not grow; exact sets, when merged, touch every member again and the cost multiplies by the number of days. A daily 4,096-byte register array, kept for a year, holds 1,495,040 bytes — still smaller than a single day's exact set, and it can still answer separately for any sub-range within the year. #### Summary - Cardinality and membership are two separate questions answered by separate structures: cardinality estimation gives a count but cannot answer membership at any certainty, since it does not represent the member. - In a dense number range, a bitmap holds sixteen times less space than an exact set (250,001 against 4,194,304 bytes) and loses nothing; its cost depends on the width of the range, not the entry count, and rises to 125,000,000 bytes for a nine-digit number. - The probabilistic membership structure's error runs in one direction only: missed members are zero, and the false positive rate is chosen by the structure's size — 42.09% at 131,072 bytes, 2.53% at 524,288 bytes, and the measured ratio tracks the theoretical ratio. - Giving up certainty does not save memory in a dense range: the structure with 2.53% error wants 524,288 bytes, the exact bitmap wants 250,001. The probabilistic structure only wins once the key space is sparse. - Cardinality estimation gives a 1.50% deviation at 4,096 bytes; it holds one thousand and twenty-four times less space than the exact set, and in return it irreversibly gives up which reader was counted. #### Next Step The structures measured in this lesson never cared about time. The bitmap answers "did they take a loan today" but does not know **when**; cardinality estimation produces a number at day's end but cannot say in what order it was collected. One more question has to be read within the same day: the library's shelving team, its overdue-notice job, and its search-index update each have to see events **in the order they happened, each from its own last position.** None of the structures so far provide this — a set does not keep order, a counter does not keep history, and a list does not help each reading side remember its own position separately. The next lesson takes up the structure that stores events in order and keeps every reader's position inside the structure itself. ### Streams Source: https://academia.sh/en/courses/in-memory-stores/streams Treating the ordered event log as a data structure: the entry id built from time and sequence, the bytes per entry counted field by field, length and duration limits compared on a day's activity stream, and the unread share shown to determine the bytes held. None of the previous structures kept order and read position together. A set holds the member but forgets the order entries were added in; a counter holds the total but leaves no history; a list keeps order but leaves it to each reader to remember where it left off. The library's three separate jobs — shelving, overdue notices, and search-index updates — each have to see the same event sequence **in the order it happened** and **each from its own last position**. A **stream** combines this into a single structure: entries sit in the order they were added, every entry has a sortable id, and each **consumer group** remembers where it left off by holding only a boundary id. This lesson treats the stream not as a message channel but as a **data structure that holds memory**: how many bytes an entry takes, what the id is for, and when entries are discarded. #### Entry ID The id is built from two parts: the clock time when the entry was added and the sequence within that time. When the clock does not advance, the sequence advances, so two entries never receive the same id without needing a separate counter structure. ```js // entry-id.mjs — a stream entry's id and its bytes. The id is generated in