Key-Value Basics

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.

// 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.

// 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.