Least Frequently Used cache.
/strat contains an approximate implementation of the Clock algorithm, which increments
frequency on cache-hits and decrements frequency of items in the same 'clock' where a newer
entry seeks admission into, which helps avoid starvation. Another algorithm, O1 implements
a constant-time LFU-LRU hybrid cache, but the flip side is it consumes extra memory compared
to Clock, though is very much simpler to reason about.
/ds contains implementations of underlying stores supporting the cache: A HashMap backed
by the native Map impl, and a restrictive RangeList backed by a Skip List.
That is, Clock.js, MultiClock.js, O1.js instances can be backed by either HashMap
for point queries (takes ~500ms for 1M point-queries), or by RangeList for range queries
(takes ~5000ms for 1M range queries; see the perf workflow).
lfu.js serves as the entrypoint to construct and interact with these LFUs.
import { LfuCache, RangeLfu } from "@serverless-dns/lfu.js";
const lfu = new LfuCache("L1", 10)
lfu.put(1, "a") // 1 -> "a"
const v = lfu.get(1) // v = "a"
const rgcache = new RangeLfu("R1", 10)
rgcache.put(1, 10, "a") // (1, 10) -> "a"
const v = rgcache.get(5) // v = "a"All caches are magic. Knowing their mechanism is not enough to predict their outcome.