Index Lifecycle

Merging controls segment count, not the index’s growth. The single segment left after forty-six batches becomes a four-hundred-batch segment after four hundred batches, and every merge recopies the whole thing. In a continuously flowing stream, the real question is why the index has to be a single object at all.

This lesson measures the effect of splitting the index by time. Opening a new index at a fixed interval is called rollover; old indexes stay in place, queries reach them when needed, and once the retention period expires an index is dropped whole. Three things are counted: how many indexes a query has to reach, how many bytes deleting old data costs, and what a tiered placement holds in memory.

Timestamped Index and Rollover

CO13. A lifecycle decision only makes sense on timestamped data, so this lesson indexes not the catalog records themselves but the access log kept on top of the catalog. Each record carries an access made on a given day, at a given branch, with given terms, and that record’s view count. Query order follows this metric, not a relevance score: the most-viewed record comes first.

CO16. Posting lists are not separately indexed by time; applying a day window on a single index requires scanning every entry. A real implementation could keep a minimum and maximum day at the segment level and skip within the index too — that would be a finer-grained version of the skipping measured below.

The corpus is 400 records a day for 180 days: 72,000 documents, seed 20260731.

// log.mjs — timestamped catalog access log and a rollover-capable index
export function rng(seed) {                   // deterministic pseudo-random generator
  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;
  };
}

const TOPIC = ('literature short-story novel essay poetry history geography philosophy psychology ' +
  'economics architecture music cinema travel biography memoir fiction mystery folklore linguistics').split(' ');
const ADJ = 'silent distant broken lost white black thin deep yellow long'.split(' ');
const NOUN = 'door sea road house city garden island notebook river well'.split(' ');
const BRANCH = 'central kadikoy bornova cankaya nilufer'.split(' ');

// each record is one catalog access: which day, which branch, which terms, how many views
export function logGenerate(days, perDay, seed) {
  const r = rng(seed), records = [];
  for (let d = 0; d < days; d++)
    for (let i = 0; i < perDay; i++) {
      const terms = [TOPIC[Math.floor(r() * 20)], ADJ[Math.floor(r() * 10)],
        NOUN[Math.floor(r() * 10)], BRANCH[Math.floor(r() * 5)]];
      if (r() < 0.4) terms.push(TOPIC[Math.floor(r() * 20)]);
      records.push({ id: 'e' + String(records.length).padStart(6, '0'), day: d, terms,
        views: Math.ceil(2 / Math.sqrt(r())) });   // CO14: long-tailed access counts
    }
  return records;
}

export class Index {
  constructor(name, firstDay) { this.name = name; this.firstDay = firstDay; this.lastDay = firstDay;
    this.dict = new Map(); this.docs = new Map(); this.deleted = new Set(); }
  add(k) {
    this.lastDay = k.day; this.docs.set(k.id, k);
    for (const t of new Set(k.terms)) {
      if (!this.dict.has(t)) this.dict.set(t, []);
      this.dict.get(t).push([k.id, k.views, k.day]);   // posting: id, metric, day
    }
  }
  get entries() { let n = 0; for (const g of this.dict.values()) n += g.length; return n; }
  get bytes() {
    let s = '';
    for (const [t, g] of this.dict) s += t + '\t' + g.map((p) => p.join(':')).join(' ') + '\n';
    for (const id of this.deleted) s += '-\t' + id + '\n';
    return Buffer.byteLength(s);
  }
  residentBytes(tier) {                        // CO15: dictionary entry is term bytes + 32,
    if (tier === 'cold') return 128;            // a posting entry is 16 bytes; a closed index is 128 bytes
    let b = 0;
    for (const t of this.dict.keys()) b += Buffer.byteLength(t) + 32;
    return tier === 'warm' ? b : b + this.entries * 16;
  }
}

export function rollover(records, dayStep) {   // dayStep days full, a new index opens
  const indexes = [];
  for (const k of records) {
    const no = Math.floor(k.day / dayStep);
    if (!indexes[no]) indexes[no] = new Index('daily-' + no, k.day);
    indexes[no].add(k);
  }
  return indexes;
}

// search: an index that does not overlap the day window is never opened; order is by access count
export function search(indexes, terms, window = null, k = 10) {
  let touched = 0, lookups = 0, scanned = 0;
  const candidates = new Map();
  for (const d of indexes) {
    if (window && (d.lastDay < window[0] || d.firstDay > window[1])) continue;
    touched++;
    for (const t of terms) {
      lookups++;
      const g = d.dict.get(t);
      if (!g) continue;
      for (const [id, views, day] of g) {
        scanned++;
        if (window && (day < window[0] || day > window[1])) continue;
        if (d.deleted.has(id)) continue;
        candidates.set(id, [views, day]);
      }
    }
  }
  const order = [...candidates].sort((a, b) => b[1][0] - a[1][0] || b[1][1] - a[1][1] ||
    (a[0] < b[0] ? -1 : 1));
  return { touched, lookups, scanned, matched: order.length,
    top: order.slice(0, k).map(([id, v]) => [id, v[1]]) };
}

Rollover’s Effect on Query Scope

The same 72,000 records are placed under three placements: a single index, 30-day rollover (6 indexes), and 7-day rollover (26 indexes). Under each placement the same query runs twice — once restricted to the last fourteen days, once with no window.

// rollover.mjs — rollover interval's effect on query scope
import { logGenerate, rollover, search } from './log.mjs';

const RECORDS = logGenerate(180, 400, 20260731);
const QUERY = ['mystery', 'kadikoy'];

console.log('access log: 180 days x 400 records = 72000 records, seed 20260731 | query: mystery kadikoy');
console.log('placement    indexes  query        touched  lookups  scanned  matched');
for (const [name, step] of [['single index', 180], ['30-day', 30], ['7-day', 7]]) {
  const d = rollover(RECORDS, step);
  for (const [label, window] of [['last 14 days', [166, 179]], ['no window', null]]) {
    const c = search(d, QUERY, window);
    console.log(name.padEnd(12), String(d.length).padStart(7), '', label.padEnd(12),
      String(c.touched).padStart(7), String(c.lookups).padStart(9),
      String(c.scanned).padStart(8), String(c.matched).padStart(8));
  }
}

access log: 180 days x 400 records = 72000 records, seed 20260731 | query: mystery kadikoy
placement    indexes  query        touched  lookups  scanned  matched
single index       1  last 14 days       1         2    19476     1406
single index       1  no window          1         2    19476    18456
30-day             6  last 14 days       1         2     3188     1406
30-day             6  no window          6        12    19476    18456
7-day             26  last 14 days       3         6     1993     1406
7-day             26  no window         26        52    19476    18456

The windowed query returns 1,406 records under all three placements: the set does not change. What changes is the work done to reach that set. In the single index, 19,476 postings are scanned and 92 percent of them are eliminated by the day filter. Under 7-day rollover, the query opens only 3 of 26 indexes and scans 1,993 entries — a tenth as many. The gain does not come from scanning faster; it comes from an index that is never opened at all: a non-overlapping index’s dictionary is not read, its posting lists are not loaded into memory.

The same table’s second rows show the cost. For the unwindowed query, scanned entries stay at 19,476 across all three placements, but dictionary lookups rise from 2 to 52. Rollover adds a fixed cost equal to the index count to every query that carries no time window: each index searches its terms separately, and each index’s partial result must be merged separately, too. The rollover interval is a choice between these two query shapes: as windowed queries grow more frequent, a short interval wins; as queries that do not fit the window dominate, a long interval wins.

Two Ways to Delete Old Data

The retention window is the last 100 days (day 80–179). In a single index, the only way to apply this is to mark every document before day 80 as deleted and clean the index. Under rollover, old indexes are dropped whole — but only the ones entirely outside the window.

// retention.mjs — two ways to apply a 100-day retention window, and tier placement
import { logGenerate, rollover, search } from './log.mjs';

const RECORDS = logGenerate(180, 400, 20260731);
const THRESHOLD = 80;                          // last 100 days are kept: 80..179
const QUERY = ['mystery', 'kadikoy'];

function clean(step) {
  const dz = rollover(RECORDS, step);
  if (step === 180) {                          // single index: every old document is marked deleted
    const d = dz[0];
    for (const k of RECORDS) if (k.day < THRESHOLD) d.deleted.add(k.id);
    const read = d.bytes;
    const fresh = rollover(RECORDS.filter((k) => k.day >= THRESHOLD), 180);
    return { remaining: fresh, dropped: 0, marked: d.deleted.size, copied: read + fresh[0].bytes,
      extra: 0 };
  }
  const remaining = dz.filter((d) => d.lastDay >= THRESHOLD);   // an index entirely old is dropped
  return { remaining, dropped: dz.length - remaining.length, marked: 0, copied: 0,
    extra: remaining.reduce((n, d) => n + [...d.docs.values()].filter((k) => k.day < THRESHOLD).length, 0) };
}

console.log(`retention window: last 100 days (day 80-179), 180 days x 400 records, seed 20260731`);
console.log('placement    dropped  marked  copied bytes  extra retained  matched  top 10 outside window');
const placement = new Map();
for (const [name, step] of [['single index', 180], ['30-day', 30], ['7-day', 7]]) {
  const t = clean(step);
  placement.set(name, t.remaining);
  const c = search(t.remaining, QUERY, null);
  console.log(name.padEnd(12), String(t.dropped).padStart(7), String(t.marked).padStart(7),
    String(t.copied).padStart(13), String(t.extra).padStart(15),
    String(c.matched).padStart(8), String(c.top.filter(([, g]) => g < THRESHOLD).length).padStart(22));
}

const remaining = placement.get('7-day');       // tier placement over the 7-day rollover
const age = (d) => 179 - d.lastDay;
console.log('\ntier placement (7-day rollover, after cleanup):');
console.log('placement    hot  warm  cold  resident bytes  bytes to reopen');
for (const [name, tierOf] of [['all hot', () => 'hot'],
  ['three tiers', (d) => (age(d) < 7 ? 'hot' : age(d) < 30 ? 'warm' : 'cold')]]) {
  const count = { hot: 0, warm: 0, cold: 0 };
  let bytes = 0, toReopen = 0;
  for (const d of remaining) {
    const t = tierOf(d);
    count[t]++; bytes += d.residentBytes(t);
    if (t === 'cold') toReopen += d.bytes;
  }
  console.log(name.padEnd(12), String(count.hot).padStart(4), String(count.warm).padStart(5),
    String(count.cold).padStart(5), String(bytes).padStart(15), String(toReopen).padStart(16));
}

retention window: last 100 days (day 80-179), 180 days x 400 records, seed 20260731
placement    dropped  marked  copied bytes  extra retained  matched  top 10 outside window
single index       0   32000       6985651               0    10262                      0
30-day             2       0             0            8000    12274                      2
7-day             11       0             0            1200    10545                      0

tier placement (7-day rollover, after cleanup):
placement    hot  warm  cold  resident bytes  bytes to reopen
all hot        15     0     0         2914122                0
three tiers     2     3    10          346942          1686139

The cost gap shows up in a single row. In the single index, deletion marks 32,000 documents, and cleanup reads and writes 6,985,651 bytes; the only way to get rid of deleted data is to rewrite the entirety of what remains. Under rollover, the same deletion copies zero bytes: the index is dropped, the file goes whole. This is the direct sibling of the previous lesson’s merge cost — there, copied bytes were paid per segment; here, they are paid per deletion.

Rollover’s cost is granularity. In the 30-day interval, the index spanning days 60–89 has part of its range inside the window, so it cannot be dropped, and 8,000 records keep being retained outside the retention window; at the 7-day interval this number falls to 1,200. The gap measurably leaks into the answer. The same query returns 10,262 records in the single index, 10,545 under 7-day rollover, and 12,274 under 30-day rollover: the set has grown by 20 percent. The order changes too: under 30-day rollover, two of the top ten results come from outside the retention window, from days that should have been deleted. The expected magnitude confirms this — roughly a sixth of the matched set is outside the window, and two records in the top ten is consistent with that ratio. The sentence “we retain a hundred days of data” means, once the rollover interval is thirty days, retaining data for up to 120 days.

Hot, Warm, and Cold Tiers

The remaining fifteen indexes do not get equal attention: the past week’s index is queried constantly, an index from three months back only a few times a month. A tiered placement turns this into a resource decision. In the hot tier, the dictionary and posting lists sit in memory; in the warm tier, only the dictionary is kept, and posting lists are read from disk on every query; in the cold tier, the index is closed and all that remains is metadata carrying the day range.

The second table gives the cost of this. Under the all-hot placement, fifteen indexes hold 2,914,122 bytes of resident memory. Under the three-tier placement, two indexes stay hot, three warm, ten cold, and resident memory falls to 346,942 bytes: an eighth as much. In return, a query reaching the ten cold-tier indexes has to open 1,686,139 bytes from disk. The tier decision sits between these two numbers, and it depends directly on the query shape from the previous section: windowed queries never open the cold indexes, an unwindowed query opens all of them every time.

Summary

• Rollover does not change the set; the windowed query returned 1,406 records under all three placements, but scanned postings fell from 19,476 to 1,993 because a non-overlapping index was never opened.
• Rollover’s fixed cost falls on the unwindowed query: dictionary lookups rose from 2 to 52, because each index searches its terms separately.
• Deleting 32,000 old documents in the single index copied 6,985,651 bytes; under rollover, the same deletion cost zero bytes by dropping the index.
• The rollover interval is retention granularity: the 30-day interval kept 8,000 records outside the window, the set grew from 10,262 to 12,274, and two of the top ten results came from days that should have been deleted; at the 7-day interval, extra retained records fell to 1,200.
• The three-tier placement lowered resident memory from 2,914,122 bytes to 346,942 bytes; the cost is the 1,686,139 bytes a query reaching the cold tier has to open.

Next Step

Rollover, just as it cheapens dropping an index, also changes another task. Segments and completed indexes are never written again; what needs backing up is not a single, constantly changing file but a set of immutable files. The next lesson takes this up: a snapshot of an index can run incrementally at the segment level, but a merge running in the background breaks that incrementality. The same lesson compares restoring from a snapshot against reindexing from the source; what gets measured is bytes copied per snapshot, the bytes a restore moves against the documents a reindex processes, and how reindexing shifts the set and the order once the analyzer changes.