Kangaroo
Kangaroo is a tiny-object flash cache that combines a small log-structured staging cache with a larger set-associative cache.
KLog batches objects for KSet to reduce set rewrites while limiting the DRAM index to the staging tier. KSet also retains Bloom filters and hit metadata in memory; no full-object index does not mean no DRAM cost. [1]
Threshold admission counts objects mapping to a set, not bytes. The pinned simulator rejects undersized groups and offers rejected objects to log readmission; warm-up controls when admission filtering runs. Its write-factor calculation weights the set component by the admitted-byte fraction before adding log writes. [2] [3]
Constructed drain: forty 100-byte objects occupy one padded 4,096-byte log write. With threshold 2, forty singleton groups cause no set writes and retain no objects after the drain; twenty pairs cause 81,920 set-write bytes and retain forty objects. Lower write traffic alone therefore does not establish better caching. This example has no hits, readmission, metadata or FTL copying. [4]
Relations
Limitations
- The published production tests report application write rates, not NAND-programmed bytes, and their different request streams prevent direct comparison between the two admission-policy experiments. [1]
Citations
- McAllister et al. Kangaroo: Caching Billions of Tiny Objects on Flash. SOSP 2021, pp. 243-262, sections 3-5. DOI: 10.1145/3477132.3483568.
- Kangaroo simulator, commit 48397846: threshold admission and rejected-group handling.
- Kangaroo simulator, commit 48397846: insertion, warm-up and calcFlashWriteAmp.
- Hesela. Synthetic log-and-set drain: bytes, admission counts and explicit unavailable metrics.
Further reading
- Hesela. Executable byte-accounting example (CC0).
- Hesela. Exact-byte and input-validation tests (CC0).
- Hesela. Cache admission can lower writes by dropping objects.
Sources & caveats
- Primary paper and pinned simulator source reviewed; no original trace replay or on-flash benchmark was performed.
- The byte ledger is an original, single-drain illustration, not an implementation or replication of Kangaroo. Its fixed write units do not describe every SSD.