Engineering and capstones · 52 / 53
Caches, external memory and streaming
Understand → trace → implement → justify
2 min reading · allow extra time for practiceTwo O(n) RAM-model algorithms can differ substantially because of cache misses. Arrays provide locality; pointer chasing may not. External-memory analysis counts block transfers. External merge sort creates memory-sized runs and merges them; B-tree fanout reduces I/O. Cache-oblivious designs target locality without hard-coded block sizes.
An LRU cache combines a hash map and doubly linked list for expected O(1) updates. OrderedDict below illustrates a small contract. Correct caching also requires eviction, TTL, invalidation, staleness and concurrency decisions. Single-flight or TTL jitter can reduce stampedes, with consistency trade-offs.
LSM trees trade write, read and space amplification through compaction. Streaming processes data without retaining it all. Reservoir sampling selects a uniform fixed-size sample; online algorithms cannot inspect the future. Separate warm/cold cache, p95 latency, allocation and adversarial distributions in benchmarks.
A worked trace
Capacity two: insert A,B, access A, insert C. Least-recently-used B is evicted.
Cost and assumptions
Expected O(1) access under the hashing model and O(c) storage for capacity c.
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
from collections import OrderedDict
cache=OrderedDict(A=1,B=2)
cache.move_to_end("A"); cache["C"]=3
if len(cache)>2:cache.popitem(last=False)
assert list(cache)==["A","C"]TEST YOUR UNDERSTANDING
Your turn
Is LRU the best policy for every workload?
Reveal the reasoning
No. Long sequential scans can evict hot items; LFU/ARC and admission policies offer different trade-offs.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
Pat Morin · Open Data Structures ↗MIT 6.046J · Design and Analysis ↗