Memory Limit and Eviction Policies

The persistence decision settles what happens after a crash. A limit that arrives before a crash has not been addressed at all in this topic: memory runs out. In every measurement so far, the store grew freely; 19,040 loan entries held 1,593,100 bytes and nothing stopped it. In a real setup, the store is given an upper limit, and once that limit is reached, every new entry takes the place of an old one.

This lesson’s question is which old entry goes. The definitions of eviction policies and the arithmetic of hit rate were established in previous courses; they are not repeated here. What gets measured is what four policies buy with the same byte budget on the same loan access trace.

The Budget Is Bytes, Not Entry Count

If the limit is given as an entry count, the policies’ cost becomes invisible. Every policy adds something to an entry so it can make its own decision, and that addition eats into the limit.

PM6. Policy overhead: least recently used keeps two links to hold its place in access order (16 bytes); least frequently used keeps a counter and a link in a frequency bucket (24 bytes); random keeps only its place in the sampling array (8 bytes); time-based keeps an expiry timestamp and ordering information (16 bytes). The entry body’s cost is the same as in the previous lessons: key, value, and 48 bytes.

PM7. The access trace is the library’s loan pattern: across four periods, 60 percent of requests go to that period’s two-hundred-book reading list, 25 percent go to a fixed thousand-book popular segment that never changes, and 15 percent go to the rest of the twenty-thousand-book catalog. The reading list is entirely replaced whenever the period changes.

PM8. Catalog entries are placed with a three-thousand-access freshness window; this window concerns only the time-based policy.

// policy.mjs — four eviction policies at the same byte budget
export const BASE = 48, LIFETIME = 3000;            // PM1: entry overhead, PM8: freshness window

export function generator(seed) {
  let a = seed >>> 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; };
}

// Loan trace: four periods; each period changes a 200-book reading list.
export function generateTrace(length, seed, catalogSize = 20000) {
  const r = generator(seed), trace = [], period = length / 4;
  for (let i = 0; i < length; i++) {
    const d = Math.floor(i / period), p = r();
    let b;
    if (p < 0.60) b = d * 200 + Math.floor(r() * 200);        // this period's reading list
    else if (p < 0.85) b = 1000 + Math.floor(r() * 1000);     // permanently popular books
    else b = Math.floor(r() * catalogSize);                       // the rest of the catalog
    trace.push('book:' + String(b).padStart(5, '0'));
  }
  return trace;
}
export const value = (k) => {
  const n = Number(k.slice(5));
  return `branch=${1 + (n % 8)};shelf=${String.fromCharCode(65 + (n % 26))}${String(n % 100).padStart(2, '0')}`;
};

class Cache {
  constructor(budget, overhead) {
    this.budget = budget; this.overhead = overhead; this.entries = new Map();
    this.bytes = 0; this.hits = 0; this.misses = 0; this.dropped = 0; this.clock = 0;
  }
  cost(k) { return Buffer.byteLength(k) + Buffer.byteLength(value(k)) + BASE + this.overhead; }
  access(k) {
    this.clock++;
    if (this.entries.has(k) && this.valid(k)) { this.hits++; this.touch(k); return; }
    if (this.entries.has(k)) { this.dropped++; this.remove(k); }
    this.misses++;
    while (this.bytes + this.cost(k) > this.budget) this.remove(this.victim());
    this.entries.set(k, value(k)); this.bytes += this.cost(k); this.inserted(k);
  }
  remove(k) { this.bytes -= this.cost(k); this.entries.delete(k); this.removed(k); }
  valid() { return true; }
  touch() {} inserted() {} removed() {}
  get overheadBytes() { return this.entries.size * this.overhead; }
}

export class LeastRecentlyUsed extends Cache {      // least recently used: access-order link, 16 bytes
  constructor(budget) { super(budget, 16); }
  touch(k) { const v = this.entries.get(k); this.entries.delete(k); this.entries.set(k, v); }
  victim() { return this.entries.keys().next().value; }
}

export class LeastFrequentlyUsed extends Cache {             // least frequently used: counter + bucket link, 24 bytes
  constructor(budget) { super(budget, 24); this.counter = new Map(); this.buckets = new Map(); this.minFreq = 1; }
  #move(k, from, to) {
    if (from) { const s = this.buckets.get(from); s.delete(k); if (s.size === 0 && this.minFreq === from) this.minFreq = to; }
    if (to) { if (!this.buckets.has(to)) this.buckets.set(to, new Set()); this.buckets.get(to).add(k); }
  }
  touch(k) { const c = this.counter.get(k); this.counter.set(k, c + 1); this.#move(k, c, c + 1); }
  inserted(k) { this.counter.set(k, 1); this.#move(k, 0, 1); this.minFreq = 1; }
  removed(k) { this.#move(k, this.counter.get(k), 0); this.counter.delete(k); }
  victim() {
    while (!this.buckets.get(this.minFreq) || this.buckets.get(this.minFreq).size === 0) this.minFreq++;
    return this.buckets.get(this.minFreq).values().next().value;
  }
}

export class Random extends Cache {          // random: only the key array, 8 bytes
  constructor(budget, seed) { super(budget, 8); this.list = []; this.position = new Map(); this.r = generator(seed); }
  inserted(k) { this.position.set(k, this.list.length); this.list.push(k); }
  removed(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);
  }
  victim() { return this.list[Math.floor(this.r() * this.list.length)]; }
}

export class TimeBased extends Cache {        // time-based: expiry timestamp + order, 16 bytes
  constructor(budget) { super(budget, 16); this.expiry = new Map(); }
  valid(k) { return this.expiry.get(k) > this.clock; }
  inserted(k) { this.expiry.set(k, this.clock + LIFETIME); }
  removed(k) { this.expiry.delete(k); }
  victim() { return this.entries.keys().next().value; }   // fixed lifetime: closest to expiry = oldest entry
  get expired() {                                    // entries whose lifetime is up but are still held
    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 };
  }
}

The time-based policy’s victim selection carries a simplification that has to be stated plainly: because every entry is placed with the same lifetime, “the one closest to expiry” points to the same entry as “the one inserted earliest.” The victim is therefore the head of the insertion order, a position that access never changes.

Four Policies on the Same Trace

// measurement.mjs — entry count and hit rate of four policies on the same budget
import { LeastRecentlyUsed, LeastFrequentlyUsed, Random, TimeBased, generateTrace, value, BASE } from './policy.mjs';

const TRACE = generateTrace(200000, 20260731);
const factories = { 'least recently used': (b) => new LeastRecentlyUsed(b), 'least frequently used': (b) => new LeastFrequentlyUsed(b),
  'random': (b) => new Random(b, 4242), 'time-based': (b) => new TimeBased(b) };
const BUDGETS = [200000, 400000, 800000];
const sample = 'book:01234';
console.log('trace: 200000 accesses, 20000 books, four periods, seed 20260731');
console.log('entry body:', Buffer.byteLength(sample) + Buffer.byteLength(value(sample)) + BASE, 'bytes');
console.log('policy                 overhead  bytes/entry  entries at 400000 bytes  overhead share');
for (const [name, f] of Object.entries(factories)) {
  const o = f(400000);
  for (const k of TRACE) o.access(k);
  console.log(name.padEnd(22), String(o.overhead).padStart(8), String(o.cost(sample)).padStart(12),
    String(o.entries.size).padStart(24),
    ('%' + ((o.overheadBytes / o.bytes) * 100).toFixed(1)).padStart(15));
}

console.log('\nhit rate (same trace, three budgets)');
console.log('policy                 200000 bytes  400000 bytes  800000 bytes  dropped entries');
for (const [name, f] of Object.entries(factories)) {
  const row = [], dropped = [];
  for (const b of BUDGETS) {
    const o = f(b);
    for (const k of TRACE) o.access(k);
    row.push(('%' + ((o.hits / TRACE.length) * 100).toFixed(1)).padStart(12));
    dropped.push(o.dropped);
  }
  console.log(name.padEnd(22), row.join(' '), String(dropped[1]).padStart(15));
}

console.log('\ntime-based: what changed as the budget grew');
console.log('budget   hits  entries held  expired  dead bytes');
for (const b of BUDGETS) {
  const o = new TimeBased(b);
  for (const k of TRACE) o.access(k);
  const d = o.expired;
  console.log(String(b).padStart(6), String(o.hits).padStart(6), String(o.entries.size).padStart(14),
    String(d.count).padStart(9), String(d.bytes).padStart(11));
}

trace: 200000 accesses, 20000 books, four periods, seed 20260731
entry body: 76 bytes
policy                 overhead  bytes/entry  entries at 400000 bytes  overhead share
least recently used          16           92                     4347           %17.4
least frequently used        24          100                     4000           %24.0
random                        8           84                     4761            %9.5
time-based                   16           92                     4347           %17.4

hit rate (same trace, three budgets)
policy                 200000 bytes  400000 bytes  800000 bytes  dropped entries
least recently used           %82.6        %87.3        %89.9               0
least frequently used         %77.0        %87.1        %89.5               0
random                        %78.0        %84.7        %89.7               0
time-based                    %65.5        %65.5        %65.5           43525

time-based: what changed as the budget grew
budget   hits  entries held  expired  dead bytes
200000 130965           2173      1154      106168
400000 130965           4347      3328      306176
800000 130965           8695      7676      706192

The Share Taken by Overhead

The first table shows that choosing a policy is a memory decision. The entry body is 76 bytes; the gap between 8 and 24 bytes that a policy adds swings the number of entries that fit in the same 400,000-byte budget between 4,000 and 4,761. Least frequently used’s counters and bucket links take up 24.0 percent of the budget, roughly a quarter; for random, that share is 9.5 percent. With the same budget, random holds 19 percent more books than least frequently used.

This shows why comparing policies by entry count alone is misleading: a comparison measured at a fixed entry count leaves a cheap-overhead policy uncharged for the very place it wins.

Reading the Hit Rate

Least recently used leads at all three budgets. This is the expected result, because the trace’s main source is the period’s reading list, and access to that list clusters in the recent past.

Least frequently used falls clearly behind at the narrow budget: 77.0 percent against 82.6 percent. The reason is in the trace’s structure. When a period changes, the old reading list’s entries keep sitting with high counters; the new list’s books, meanwhile, enter with a counter of one and land first in line for the next eviction. The policy keeps treating what was correct in the past as correct today. At an 800,000-byte budget the gap between the two policies narrows to 0.4 points, because the budget is wide enough to carry both the old list and the new one at the same time.

Random’s result is more interesting. At 400,000 bytes it trails least recently used by 2.6 points; at 800,000 bytes the gap drops to 0.2 points. Random selection picks what to discard without any thought at all, but it carries two advantages: its overhead is the cheapest, so it holds the most entries for the same budget, and once the budget comfortably covers the working set, which entry gets discarded stops changing the outcome. At the narrow budget the policy is off by 4.6 points; at the wide budget the gap approaches measurement noise.

The decision follows from this: the policy debate only matters while the budget is smaller than the working set. Once the budget is comfortable, the effort spent changing the eviction policy buys less than the same effort spent lowering memory overhead.

Time-Based Eviction Does Not Protect Memory

The last table shows that one of the four policies is actually doing a different job. The time-based policy gives the same hit rate at all three budgets: 65.5 percent. This is not a rounding artifact — the hit count is exactly 130,965 in all three runs. Quadrupling the budget changed the hit rate not at all.

What changes is only dead weight. At a 200,000-byte budget the store holds 2,173 entries, and 1,154 of them are already expired; at 800,000 bytes it holds 8,695 entries, of which 7,676 have expired and take up 706,192 bytes. More than three-quarters of the budget, in other words, goes to entries that will never produce another hit.

The cause is the policy’s own logic. An expired entry, even while it sits in memory, counts as a miss and gets dropped the moment it is accessed: 43,525 entries dropped this way over the course of the four-hundred-thousand-byte run. Eviction, meanwhile, always discards the oldest entry, and under a fixed lifetime the oldest entry is already the expired one. As a result, eviction never discards a live entry; the extra memory only serves to hold more dead entries in waiting.

Expiration is a freshness tool, not a memory tool. Refreshing the library’s catalog entries every three thousand accesses is a correctness decision, and it belongs where it is; but meeting the memory limit still requires a separate eviction policy. Neither substitutes for the other.

Summary

• The memory limit is given in bytes, not entry count, because the overhead a policy adds to each entry eats into the budget: the share ranged from 9.5 percent to 24.0 percent.
• At the same 400,000 bytes, random held 4,761 entries and least frequently used held 4,000; cheap overhead partly compensates for a weaker decision.
• Least recently used leads at all three budgets; least frequently used fell 5.6 points behind at the narrow budget, because when the period changed, the old reading list’s high counters kept their place.
• As the budget widens, the gap between policies closes: at 800,000 bytes only 0.2 points separated least recently used from random.
• Time-based eviction gave the same 130,965 hits at all three budgets; the extra memory only grew the dead entries (from 106,168 bytes to 706,192 bytes). Expiration protects freshness, not memory.

Next Step

The last measurement left a question open: 7,676 expired entries sat in memory because nothing touched them. Without a mechanism that removes an entry the instant its lifetime is up, the freshness window only fixes what a read returns, not the bytes it holds. The next lesson takes up that gap: the lazy method that only cleans an entry when it is accessed, against the active method that samples the key space in the background. What gets measured is how much memory expired entries hold, how late that memory is freed under lazy cleanup, and what a round of active sampling costs.