Cliffhanger
Cliffhanger is a cache-memory allocator that combines shadow-queue feedback with adaptive partitioning to cross performance cliffs.
Shadow hits estimate the benefit of more resident capacity without retaining the evicted payload. Allocation moves memory among slab classes or applications on one server; cliff handling splits a queue and adjusts its request share and capacity. A ghost hit is not a payload hit. [1]
The hill-climbing argument assumes increasing, concave hit-rate curves. A flat region before a sharp rise can hide useful capacity from a local gradient. Cliff scaling addresses that shape without first constructing the complete curve. [1]
Constructed LRU example: A cycles through eight equal-size keys eight times; B requests one other key 16 times. Both start empty. With eight total slots, allocations A/B = 4/4, 5/3, 6/2 and 7/1 all give 15 hits in 80 requests. Allocation 8/0 gives 56/80. A rule that accepts only immediately improving one-slot moves stops at 4/4 despite the better endpoint. This is not a Cliffhanger reproduction. [3]
Cold and warm differ: A alone at eight slots gives 56/64 hits from empty. Excluding its first eight requests as warm-up gives 56/56 scored hits; at seven slots it gives 0/56. Report initial state and scoring window alongside capacity. [3]
Arithmetic check: using hit/miss latencies of 200/10,000 us, a hit-ratio increase from 98.2% to 99.2% changes the weighted mean from 376.4 to 278.4 us. That is 26.0% less latency or 1.352x speedup, not the introduction's claimed latency reduction of over 35%. This is a simple mixture, not an end-to-end measurement. [1] [3]
Relations
Limitations
- The implementation enables cliff scaling only above 1,000 items and is designed to scale a single cliff efficiently; the eight-key example does not test that implementation. [1, 3]
Citations
- Cidon, Eisenman, Alizadeh and Katti. Cliffhanger: Scaling Performance Cliffs in Web Memory Caches. NSDI 2016, pp. 379-392, sections 1 and 3.4-5.3.
- Hesela. Synthetic LRU capacity sweep, allocation plateau and cold/warm scoring counts.
Further reading
- USENIX. Cliffhanger, NSDI 2016: publisher record and proceedings metadata.
- Hesela. Bounded exact LRU interpreter and deterministic evidence generator.
- Hesela. Independent reuse-distance oracle and invalid-input regression tests.
- Hesela. Cache sizing and workload boundaries.
Sources & caveats
- The original NSDI paper was read beyond its abstract. No reported throughput, memory-saving or miss-reduction percentage is generalized to current systems.
- The finite traces are synthetic interpretation controls, not the paper's traces, an implementation of its adaptive allocator or an SSD benchmark.
- The arithmetic check concerns the introduction's motivating example only; it does not re-evaluate the reported workload results.