Expiration Management

The previous lesson’s last measurement left a gap. In a store carrying expiry timestamps, at the end of the eight-hundred-thousand-byte budget, 7,676 of the 8,695 entries held were expired and were still sitting in memory. Accessing an expired entry produced the correct behavior — the entry was disregarded and dropped — but as long as nothing accessed it, the entry kept its place. The freshness window fixed what a read returned; it did not fix the bytes held.

This lesson takes up that gap. There are two paths, and both can run together in the same store. Lazy cleanup checks an entry only when it is accessed and deletes it if its lifetime is up; its cost is close to zero, because it only adds a comparison on top of a lookup that would happen anyway. Active cleanup samples the key space in the background, deletes the expired ones, and repeats the round if the sample turns up too many expired entries; its cost is work that no client asked for.

Mechanism

PM9. The library’s traffic over one hour: 20 new keys are placed per second and 60 accesses are made. Of the keys, 30 percent are 60-second loan locks, 50 percent are 300-second catalog entries, and 20 percent are 1,800-second session records. Of the accesses, 70 percent go to the last two thousand keys and 30 percent go to the entire key space. The value body is 24 bytes; entry overhead is 48 bytes, the expiry timestamp is 16 bytes.

PM10. Active cleanup starts one round every second. In a round, a set number of keys is sampled; the expired ones are deleted. If more than a quarter of the sampled keys are expired, the round repeats, up to sixteen times.

// expiry.mjs — store with expiry timestamps, lazy and active cleanup
export const BASE = 48, STAMP = 16;             // PM1: entry overhead, PM6: expiry timestamp

export function generator(t0) {
  let a = t0 >>> 0;
  return () => { a = (a + 0x6d2b79f5) >>> 0; let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}

export class Store {
  constructor(seed) {
    this.entries = new Map(); this.expiry = new Map(); this.list = []; this.position = new Map();
    this.bytes = 0; this.clock = 0; this.r = generator(seed);
    this.lazyDeleted = 0; this.activeDeleted = 0; this.sampled = 0; this.rounds = 0;
    this.delayTotal = 0; this.delayWorst = 0; this.peakDead = 0;
  }
  cost(k) { return Buffer.byteLength(k) + 24 + BASE + STAMP; }
  put(k, lifetime) {
    if (!this.entries.has(k)) {
      this.bytes += this.cost(k);
      this.position.set(k, this.list.length); this.list.push(k);
    }
    this.entries.set(k, 1); this.expiry.set(k, this.clock + lifetime);
  }
  remove(k) {
    this.bytes -= this.cost(k); this.entries.delete(k); this.expiry.delete(k);
    const i = this.position.get(k), last = this.list.pop();
    if (i < this.list.length) { this.list[i] = last; this.position.set(last, i); }
    this.position.delete(k);
  }
  access(k) {                                      // lazy cleanup: an expired entry drops on access
    if (!this.entries.has(k)) return 'missing';
    if (this.expiry.get(k) > this.clock) return 'hit';
    const delay = this.clock - this.expiry.get(k);
    this.delayTotal += delay;
    if (delay > this.delayWorst) this.delayWorst = delay;
    this.lazyDeleted++; this.remove(k);
    return 'expired';
  }
  active(sampleSize, threshold = 0.25, maxRounds = 16) {      // active cleanup: rounds that sample and delete
    for (let t = 0; t < maxRounds; t++) {
      let deletedCount = 0, checked = 0;
      for (let i = 0; i < sampleSize && this.list.length > 0; i++) {
        const k = this.list[Math.floor(this.r() * this.list.length)];
        checked++;
        if (this.expiry.get(k) <= this.clock) { this.remove(k); deletedCount++; }
      }
      this.sampled += checked; this.activeDeleted += deletedCount; this.rounds++;
      if (checked === 0 || deletedCount / checked < threshold) return;
    }
  }
  dead() {
    let count = 0, bytes = 0;
    for (const k of this.entries.keys()) if (this.expiry.get(k) <= this.clock) { count++; bytes += this.cost(k); }
    return { count, bytes };
  }
}

// One hour of library traffic: 20 new keys per second, 60 accesses per second.
export function run(sampleSize, seed = 20260731, duration = 3600) {
  const store = new Store(seed + 7), r = generator(seed);
  const categories = [['lock', 60], ['catalog', 300], ['session', 1800]];
  const keys = [];
  for (let t = 1; t <= duration; t++) {
    store.clock = t;
    for (let i = 0; i < 20; i++) {
      const p = r(), [name, lifetime] = p < 0.30 ? categories[0] : p < 0.80 ? categories[1] : categories[2];
      const k = name + ':' + String(keys.length).padStart(6, '0');
      keys.push(k); store.put(k, lifetime);
    }
    for (let i = 0; i < 60; i++) {                // 70% from the last 2000 keys, 30% from the entire space
      const n = keys.length;
      const j = r() < 0.70 ? n - 1 - Math.floor(r() * Math.min(2000, n))
        : Math.floor(r() * n);
      store.access(keys[j]);
    }
    if (sampleSize > 0) store.active(sampleSize);
    if (t % 60 === 0) {                           // peak measured once per minute
      const d = store.dead();
      if (d.bytes > store.peakDead) store.peakDead = d.bytes;
    }
  }
  return store;
}

Measurement

// measurement.mjs — lazy cleanup alone and active cleanup at three sample sizes
import { run } from './expiry.mjs';

console.log('one hour of traffic: 72000 keys placed, 216000 accesses made, seed 20260731');
console.log('method            entries held  dead entries  dead bytes  dead share  peak dead bytes');
const runs = [['lazy only', 0], ['active, 5 samples', 5], ['active, 20 samples', 20],
  ['active, 100 samples', 100]];
const results = runs.map(([name, n]) => [name, n, run(n)]);
for (const [name, , store] of results) {
  const d = store.dead();
  console.log(name.padEnd(20), String(store.entries.size).padStart(13), String(d.count).padStart(10),
    String(d.bytes).padStart(9), ('%' + ((d.bytes / store.bytes) * 100).toFixed(1)).padStart(8),
    String(store.peakDead).padStart(14));
}

console.log('\ncleanup cost and delay');
console.log('method            lazy deleted  average delay  worst  active deleted  sampled');
for (const [name, , store] of results) {
  const avg = store.lazyDeleted ? (store.delayTotal / store.lazyDeleted).toFixed(1) : '0.0';
  console.log(name.padEnd(20), String(store.lazyDeleted).padStart(14), (avg + ' s').padStart(17),
    (store.delayWorst + ' s').padStart(8), String(store.activeDeleted).padStart(14),
    String(store.sampled).padStart(11));
}

const t = results[0][2], y = results[2][2];
console.log('\nextra work per access: lazy 0 (limited to the accessed entry) |',
  'active, 20 samples:', (y.sampled / 216000).toFixed(3), 'entries,',
  y.rounds, 'rounds /', 3600, 'seconds');
console.log('memory with lazy only:', t.bytes, 'bytes | with active, 20 samples:', y.bytes, 'bytes |',
  'difference', t.bytes - y.bytes, 'bytes (%' + (((t.bytes - y.bytes) / t.bytes) * 100).toFixed(1) + ')');

one hour of traffic: 72000 keys placed, 216000 accesses made, seed 20260731
method            entries held  dead entries  dead bytes  dead share  peak dead bytes
lazy only                    39714      29205   2964300    %73.5        2964300
active, 5 samples            20891      10382   1053954    %49.6        1113648
active, 20 samples           14460       3951    401040    %27.2         414303
active, 100 samples          12539       2030    205941    %16.1         212913

cleanup cost and delay
method            lazy deleted  average delay  worst  active deleted  sampled
lazy only                     32286           421.4 s   3500 s              0           0
active, 5 samples             23572           206.5 s   3009 s          27537       62375
active, 20 samples            16649            68.1 s   1563 s          40891      167200
active, 100 samples           12772            30.7 s    781 s          46689      362500

extra work per access: lazy 0 (limited to the accessed entry) | active, 20 samples: 0.774 entries, 8360 rounds / 3600 seconds
memory with lazy only: 4035180 bytes | with active, 20 samples: 1471920 bytes | difference 2563260 bytes (%63.5)

The Limit of Lazy Cleanup

The first row does not mean lazy cleanup fails to work. It works exactly as intended: over the course of the run, 32,286 entries were caught and deleted during access. The problem is that cleanup only touches the entry that gets accessed. At the end of one hour the store holds 39,714 entries, and 29,205 of them are expired entries; the 2,964,300 bytes they occupy amount to 73.5 percent of the memory the store holds. These entries were never requested again after their lifetime ran out, so they were never checked at all.

The second table gives the delay. Entries deleted through the lazy path dropped out of memory an average of 421.4 seconds after their lifetime expired; in the worst case, 3,500 seconds, which is nearly the entire run. In the library’s terms: a sixty-second loan lock is still sitting in memory roughly seven minutes after its job is done.

This confirms that expiration alone is not a memory tool. The freshness window honors its contract — an expired entry is never read — but the memory side of that contract goes unattended. Over one hour of traffic, three-quarters of the store goes to data that no one will ever ask for again.

The Price of Active Cleanup

Active cleanup closes this gap and pays for it with work that no client asked for. The scheme that samples twenty keys per round brings the dead share down from 73.5 percent to 27.2 percent and pulls the store’s total memory down from 4,035,180 bytes to 1,471,920 bytes, a drop of 63.5 percent. The average delay falls from 421.4 seconds to 68.1 seconds.

The cost is measured by the number of entries sampled: 167,200 entries. Since the number of accesses made in the same hour is 216,000, cleanup adds 0.774 entry touches for every access. The number of rounds is 8,360 — an average of 2.3 rounds per second. The threshold rule shows up here: while expired entries are dense, the round repeats and cleanup speeds up; once the space thins out, it finishes in a single round. The sampling round is taken out of the time the store sets aside for serving accesses, which is why both the sample count per round and the cap on round count are, in effect, response-time decisions.

The effect of the sample size is not linear. Going from five to twenty brought the dead memory down from 1,053,954 bytes to 401,040 bytes in exchange for 104,825 extra samples: 6.2 bytes per sample. Going from twenty to a hundred brought it down from 401,040 bytes to 205,941 bytes in exchange for 195,300 extra samples: 1.0 byte per sample. The marginal return drops to a sixth. The reason is direct: as the space gets cleaned, the probability that a randomly chosen key turns out to be expired falls, and sampling starts coming back empty.

The dead share never reaching zero in any scheme has the same cause. Even at a hundred samples per round, 2,030 entries remain expired; random sampling eventually finds any given entry, but “eventually” is a stretch of time, and that stretch sits in memory as bytes.

The Choice

The two methods do not substitute for each other; they run together and guarantee two different things. Lazy cleanup guarantees correctness: an expired entry cannot be read, even if active cleanup has not found it yet. Active cleanup guarantees memory: it reclaims the space of entries that will never be accessed again.

The sample size, in turn, is a budget setting. For short-lived, heavily produced keys like the library’s loan locks, the space fills quickly, so a large sample pays off. For long-lived, sparse keys like session records, the same sampling mostly comes back empty, and the work spent on it is paid in response time. In this run, the twenty-sample round reclaimed 86 percent of the dead memory at a cost of 0.774 entry touches per access; the hundred-sample round reclaimed half of the remaining share and doubled the cost.

Summary

• Lazy cleanup only touches the accessed entry: at the end of the run, 29,205 of 39,714 entries were expired and held 73.5 percent of memory.
• Entries dropped through the lazy path left memory an average of 421.4 seconds after their lifetime expired, and up to 3,500 seconds in the worst case.
• Active cleanup sampling twenty keys per round brought the dead share down to 27.2 percent and total memory down from 4,035,180 bytes to 1,471,920 bytes; its cost is 0.774 entry touches per access.
• The return on a larger sample size diminishes: going from five to twenty gained 6.2 bytes per sample, going from twenty to a hundred gained 1.0 byte per sample.
• Lazy cleanup guarantees correctness, active cleanup guarantees memory; expiration alone meets neither on its own.

Next Step

This topic built the ways a store looks after itself: writing its state to disk, recording its writes, deciding between the two by looking at recovery and the data loss window, knowing which key to evict once the memory limit is reached, and not leaving an expired one in place. Every number measured was read from inside a single process.

All of these decisions share one assumption: the node is running. A snapshot was written to disk, but that disk belongs to that one machine; the data loss window was calculated, but it assumed the process could restart; the eviction policy protected the memory limit, but that memory belongs to a single machine. When the machine itself stops — or becomes unreachable — the recovery files are still there, but the clients asking for the store are somewhere else. The next topic opens this question: how a second copy of the data is kept, how far behind that copy falls, and what happens to a write that was accepted but not yet propagated at the moment of failover.