core practice · coding problem
Why LRU-K survives a scan
Implement simulate(capacity, accesses, policy) returning the number of hits. policy is 'lru' or 'lru2'. Under 'lru2' a page is only promoted into the resident set on its SECOND access — a page seen once goes to a probationary list and is evicted before any twice-seen page. Evict the least-recently-used within each tier, probationary first.
The mechanism
A database manages its own page cache because it knows things the OS cannot: which pages a query will touch next, which are dirty and pinned by an open transaction, and that a sequential scan should not evict the working set. That last point is why plain LRU is wrong for a database — one big scan touches every page once and flushes everything useful, so real systems use LRU-K or clock-sweep variants that require a second reference before promoting a page.
Expected evidence
A hot working set plus a long one-shot scan: lru2 keeps the working set, lru loses it.
Try this drill in the practice workspace →
Hints when you need them
- Track access counts separately from recency; the tier is decided by count, the victim by recency.
- The point of the second test is that a scan of never-repeated pages should not evict the hot set.
Watch for these mistakes
- Assuming the OS page cache is equivalent — it cannot honour pin counts or write ordering for recovery
- Plain LRU, which a single sequential scan pollutes end to end
- Sizing the pool to fill RAM and leaving nothing for sorts, hash joins, and the OS
- Ignoring that a dirty page cannot be evicted until its log record is durable