koffein

A modern, zero-dependency cache for JavaScript and TypeScript with a pluggable eviction policy. Its headline policy is W-TinyLFU: a frequency-based admission filter in front of a Segmented LRU, which keeps the hot set resident and beats plain LRU on skewed (Zipfian) and bursty workloads without giving up recency.

This is not "another LRU". lru-cache already owns the LRU default and does it well. The wedge here is the eviction quality niche that JavaScript lost when its only real W-TinyLFU port (transitory) went unmaintained: a measurably higher hit ratio on real traces, with the policy swappable so you can run your own bake-off. This is my take on that gap, not the one true cache.

What this is

If none of the words above meant anything, start here.

A cache is a small box you keep answers in so you do not have to compute or fetch them twice. It is small on purpose, because the whole point is that it costs less than the thing it is standing in front of. So the box fills up, and every time something new arrives you have to throw something out.

Which thing you throw out is the entire game. That decision is called the eviction policy, and it decides your hit ratio: the fraction of requests the box can answer without going to the database, the network or the CPU behind it. A cache with a good policy and a cache with a bad one can be the same size and differ by a factor of two in how often they help you.

The default policy nearly everywhere is LRU: throw out whatever was used least recently. It is simple, it is fast, and it has one well-known weakness. Sweep a few thousand items through it that nobody will ever ask for again, a report job, a crawler, a backup, and LRU dutifully evicts your genuinely hot data to make room for garbage it will never be asked for. That is called scan pollution, and it is the reason your cache hit ratio falls off a cliff at 3am for no reason anybody can find.

The fix, known for years and standard on the JVM, is to stop admitting things just because they are new. Keep a compact record of how often keys are requested, and when a newcomer wants in, only let it displace an incumbent if it is actually more popular. That is W-TinyLFU, and this package is a JavaScript implementation of it, with the policy swappable so you can put LRU, LFU or your own back in and measure the difference yourself.

So: this is a cache, in the class of eviction-policy libraries, competing on hit ratio rather than on ergonomics or speed.

Status: early release (0.6.x)

The Cache is here with a real, scan-resistant W-TinyLFU by default, optional per-entry TTL, a pluggable eviction policy (WTinyLFU, LRU, LFU, or your own), and memo for caching sync or async functions with in-flight de-duplication. A reproducible hit-ratio bake-off backs the claims. The core is feature-complete; the version is 0.x while the API settles toward 1.0. See the roadmap.

Install

npm install koffein

Ships ESM and CommonJS builds with type declarations. Node >= 18. Zero runtime dependencies.

Quick start

import { Cache } from "koffein";

const cache = new Cache<string, User>(10_000); // hold up to 10k entries

cache.set("user:42", user);
cache.get("user:42"); //  => user
cache.get("user:999"); // => undefined (a miss)

cache.has("user:42"); //  => true
cache.peek("user:42"); // read without counting it as a use
cache.delete("user:42");
cache.stats(); // { size, capacity, hits, misses, evictions, hitRatio }

Keys can be any type as storage: membership is Map identity, so any value works as a key. Admission control is not indifferent to the key's shape, though. The default policy feeds every key to a frequency sketch, and its built-in hash only distinguishes strings and integers. Every other shape goes through String(key), so all plain objects collapse onto the single counter "[object Object]": the sketch can no longer tell a hot key from a one-hit scan, ties are decided by the admission coin flip, and the scan resistance this cache exists for quietly stops working. If your keys are objects, hash their content:

import { Cache, WTinyLFU } from "koffein";

type Key = { tenant: string; id: number };

const cache = new Cache<Key, Row>(10_000, {
  policy: new WTinyLFU<Key, Row>({ hash: (k) => fnv1a(`${k.tenant}:${k.id}`) }),
});

fnv1a is four lines and is spelled out under Hashing string keys; see Choosing a policy for the rest of the policy options.

Expiry (TTL)

Give entries a time-to-live, cache-wide or per entry. Expiry is lazy: an expired entry reads as a miss and frees its slot on the next touch, so there are no timers to manage.

const sessions = new Cache<string, Session>(10_000, { ttl: 60_000 }); // 60s default
sessions.set("sid:abc", session); //           expires 60s after this write
sessions.set("sid:xyz", session, 5 * 60_000); // this one lives 5 minutes

Why it holds up under scans

The cache records every access in a frequency sketch, and when it is full it admits a newcomer into the main region only if the sketch says that newcomer has been seen at least as often as the entry it would replace. A key touched once (a scan, a crawler, a one-off report) cannot evict a proven-hot entry, which is exactly where a plain LRU bleeds hit ratio.

Why W-TinyLFU

• LRU leaves hit ratio on the table. On skewed access it evicts a hot key the moment a burst of one-hit-wonders scans through (the classic "scan pollution"). Pure LFU fixes that but never forgets, so a key that was hot yesterday lingers forever.
• W-TinyLFU keeps a small window (an LRU that catches recency and bursts) in front of a Segmented LRU main, and only admits a candidate into the main cache when a compact frequency sketch says it is hotter than the victim it would replace. The sketch ages periodically, so admission stays recency-aware instead of frozen in the past. This is the design behind Caffeine, the reference JVM cache.

Benchmarks

koffein is measured against plain LRU, the popular npm caches, and the modern research policies (SIEVE, S3-FIFO, LFU) with an independent harness, cache-arena, on the same seeded workloads and through the same uniform driver. Caches are compared at equal peak occupancy in entries, measured rather than declared: the harness drives each cache through its own surface until the resident set stops growing, then sizes it so that measured peak matches the budget, which is how a cache that really holds 2x its nominal capacity gets sized down to match. None of that is a claim about bytes: the harness has no byte instrument, and per-entry overhead differs between libraries. Full tables, every workload, and the methodology live in BENCHMARKS.md, which npm run bench:arena regenerates from scratch and which records the harness version and the Node version it ran on. The short version:

Hit ratio (efficiency). On skewed (Zipfian) traffic, the common case, koffein returns markedly more hits than plain LRU at the same size, and the gap is widest exactly where a cache hurts most: when it is small relative to the working set.

| Zipf 0.99, cache size | koffein (W-TinyLFU) | plain LRU | vs LRU | | --- | ---: | ---: | ---: | | 0.1% of footprint | 28.1% | 15.3% | +84% | | 1% of footprint | 49.8% | 39.6% | +26% | | 10% of footprint | 71.7% | 66.3% | +8% |

Read that table with its own limits attached. The +84% is against plain LRU, the default nearly everywhere but not the strongest policy in the panel, at the most extreme size; at 10% of footprint the same comparison is +8%. And against the strong policies koffein does not lead: at the exact column headlined above it sits inside the top group but not at the front of it, behind S3-FIFO at 30.0%, SIEVE at 28.6% and LFU at 28.3%. What the table says is that a good modern policy is worth a great deal over LRU and that this is a good modern policy, which is the honest and still useful claim.

transitory, the other npm W-TinyLFU, reads 27.2% in the same column, and that 0.9 of a point is worth explaining rather than banking. The harness measures peak occupancy instead of trusting it, and transitory holds 1.36 entries per entry of nominal capacity at that size where koffein holds 1.00, so it is sized down to compare at equal occupancy. Treat the two as level. What matters here is not the ordering, it is the cross-check: two independent W-TinyLFU implementations landing in the same region is the evidence that this one is built right.

On a pure loop larger than the cache, LRU's textbook worst case, the W-TinyLFU family is the only one that recovers a meaningful share: koffein reads 0.0% at every size below 25% of footprint and 20.8% at 25%, where the nearest non-family result is Random at 2.0%.

Efficiency numbers above are exact (a deterministic simulation). Throughput is not, so it is measured differently: BENCHMARKS.md reports the median of 12 interleaved trials in each of five separate processes, prints the spread within a run and the spread between runs as two figures, and ranks two caches only when all five processes agreed on which was faster. Pairs they split are listed as unordered.

Where this earns its place

The shape to look for is always the same: the box is small relative to what it is standing in front of, and the traffic is uneven. Uneven traffic is the normal case, because real popularity is skewed: a few keys carry most of the requests. If both halves are true, the eviction policy is doing real work and it is worth caring which one you have.

A read-through cache in front of a database or an API. The classic case. Some rows are requested constantly and most are requested once, so admission control is the difference between serving the hot set from memory and paying for it every time. The bigger the gap between your cache size and your working set, the more the policy matters: at 0.1% of the footprint the table above shows 28.1% against 15.3%, which is most of your database load.

Anything sharing a process with a batch job, a crawler or a report. This is scan pollution and it is the case W-TinyLFU exists for. A sweep of keys nobody will request again cannot evict your hot set here, because a newcomer has to prove it is more popular than the thing it would displace. On a pure loop larger than the cache, LRU's textbook worst case, this is the only family in the benchmark that recovers a meaningful share of the hits, and only once the cache reaches a quarter of the footprint: below that everything in the panel, koffein included, reads zero.

Memoizing an expensive pure function. memo wraps a sync or async function with in-flight de-duplication, so a hundred concurrent callers asking for the same uncomputed key produce one computation, not a hundred. Rate-limited API clients, template compilation, parsing, hashing, image transforms.

Serverless and edge, where memory is the billed resource. A higher hit ratio at the same memory is directly a smaller instance or a smaller bill, and zero dependencies means nothing to install at a cold start.

When you actually want to run the bake-off. The policy is a constructor argument, and LRU, LFU and your own implementation all plug into the same interface, so "is this better for my traffic" is a question you can answer on your own trace instead of taking my word for it.

Limits

What the cache does not do, stated here rather than discovered later.

• Capacity is entries, not bytes. new Cache(10_000) holds ten thousand entries whatever they weigh. There is no size function and no byte budget, so a cache of wildly uneven values is not memory-bounded in any useful sense.
• Expiry frees a slot when the entry is touched, not when it expires. Lazy TTL is why there are no timers to manage, and it is also why an expired entry keeps occupying its slot until something reads, overwrites or evicts it. A cache that has gone quiet stays full of dead entries.
• No eviction callback. There is no onEvict or dispose hook, so a value that owns a resource (a socket, a file handle) will not be closed for you.
• No iteration. No keys(), values() or entries(). The cache is a lookup structure, not a collection you walk; size and stats() are the whole introspection surface, and stats() counts from construction or the last clear().
• Frequency is an estimate that saturates at 15. The sketch never underestimates but can overestimate on a hash collision, and above 15 it cannot tell a warm key from a scorching one. That is enough for admission, which only ever asks "hotter than the victim it would replace", and it is not a counter to read as truth.
• Object keys need a hash. Worth repeating from the quick start, because it is the one way to install this cache and silently lose the property it exists for.
• One process, one thread. Nothing is shared across workers, nothing survives a restart, and there is no invalidation protocol.

When not to use this

Both ends, because a package that only names one is advertising.

Your working set fits comfortably in the cache. If almost nothing ever gets evicted, the eviction policy is answering a question that never comes up. You are paying for a frequency sketch and an admission decision to arrange items you were never going to throw out. Use a Map, or lru-cache for the ergonomics.

Your traffic is uniform. Admission control works by betting that popularity is predictive. If every key really is equally likely, there is nothing to predict, the sketch is overhead, and LRU's simplicity wins.

Your working set turns over wholesale, and the cache is not small. Frequency is memory, and memory of a popularity distribution that no longer exists is a cost. On the harness's shift workload, where the working set moves every phase, koffein leads plain LRU while the cache is small (48.1% against 38.9% at 1% of footprint) and then falls behind it as the cache grows: 69.3% against 76.5% at 10% of footprint, and 76.0% against 90.6% at 25%. If your traffic is phases rather than a stable popularity distribution, and your cache is generous relative to the footprint, plain LRU (lru-cache, tiny-lru) is the better bet.

Throughput is your bottleneck, not hit ratio. Admission is not free: koffein does more work per operation than a bare LRU map, a sketch lookup and sometimes an eviction decision, so it is not the throughput leader. In the same report it averages 9.9 million operations per second across the eight workloads, against 18.9 for tiny-lru, 17.1 for quick-lru and 13.2 for lru-cache on the same machine and in the same rounds, and every one of those three gaps is one all five replicates agreed on. If your backing store is fast and your cache is doing millions of operations a second, one of those may serve you better even at a lower hit ratio. That is a real trade and the numbers for both sides are in BENCHMARKS.md.

You need a distributed or persistent cache. This is an in-process, in-memory cache. It does not replicate, it does not survive a restart, and it has no opinion about invalidation across instances. Reach for Redis or Memcached.

What is left, and what this package is for: an in-process cache that is smaller than its working set, on skewed or bursty traffic, where a hit ratio point is worth more to you than a nanosecond.

Choosing a policy

The cache delegates every eviction decision to a policy. The default is WTinyLFU; swap it with one line, or bring your own.

import { Cache, WTinyLFU, LRU, LFU } from "koffein";

new Cache(cap); //                       W-TinyLFU (the default)
new Cache(cap, { policy: new LRU() }); // plain LRU
new Cache(cap, { policy: new LFU() }); // plain LFU (in-cache counts, no aging)

• WTinyLFU (default) is the scan-resistant, skew-friendly policy the rest of this README is about. It takes its own tuning via new WTinyLFU({ hash, random }): hash maps a key to a 32-bit integer for the frequency sketch (strings and integers are handled for you, object keys need one or they all share a single counter and admission degenerates), and random is the admission tie-break source (inject a seeded one for deterministic tests).
• LRU and LFU are honest, textbook baselines, offered so you can measure the gap on your own traffic instead of taking the bake-off's word for it. Install each behind the same Cache and compare stats().hitRatio.

Write your own by implementing EvictionPolicy<K, V>: init(capacity), onAdd(node) (returns a victim to evict or null), onAccess(node), onMiss(key), onRemove(node), and clear(). The Node and EvictionPolicy types are exported for this. So is IntrusiveList, the doubly-linked list the built-in policies are built on (pushHead, moveToHead, popTail, remove, clear, plus head, tail and size): the node is the list cell, so moving an entry between lists is O(1) and allocates nothing, and Node carries three scratch fields (segment, hash, freq) your policy may use however it likes. TTL is orthogonal and works behind any policy.

Selecting a policy by name

A policy can also be chosen by a registered name, and you can register your own so it is selectable exactly like a built-in:

import { Cache, registerPolicy, policyNames } from "koffein";

new Cache(cap, { policy: "lru" }); // built-in names: "w-tinylfu", "lru", "lfu"

registerPolicy("my-policy", () => new MyPolicy());
new Cache(cap, { policy: "my-policy" }); // your policy, selected by name

policyNames(); // => ["w-tinylfu", "lru", "lfu", "my-policy"]

The registry stores factories, so each cache gets a fresh instance, and an unknown name throws. Instance and string forms coexist: pass an instance when you need to configure it (new WTinyLFU({ hash })) or want full type checking, a name when the default of a policy is all you want.

Memoizing a function

memo wraps a function so its results are cached, with the whole W-TinyLFU (and optional TTL) machine underneath. It is async-aware where it counts.

import { memo } from "koffein";

const getUser = memo(fetchUser, { capacity: 10_000, ttl: 60_000 });

await getUser(42); // runs fetchUser(42), caches the result
await getUser(42); // served from cache

For async functions it caches the promise, so two concurrent calls for the same key share a single in-flight computation (the function runs once, not once per caller). If that promise rejects, the entry is evicted, so a failure is never cached and the next call retries.

Keys default to the first argument. For multi-argument functions, pass a keyFn:

const distance = memo(computeDistance, { keyFn: (from, to) => `${from}->${to}` });

capacity (default 1000), ttl, clock, and policy pass through to the underlying cache. The memoized function also carries .delete(...args) to invalidate one call, .clear(), .stats(), and .cache for direct access.

One behavior to know: undefined is the miss sentinel, so a call that returns undefined is never served from cache and runs again every time. Return null for "computed, and the answer is nothing".

Cache API

new Cache<K, V>(capacity, options?)

A cache holding up to capacity entries. Options: policy?: EvictionPolicy selects the eviction strategy (default new WTinyLFU(); see Choosing a policy); ttl?: number sets a default per-entry lifetime in milliseconds (omit for no expiry); clock?: () => number overrides the time source (defaults to Date.now, injectable for deterministic tests). Throws RangeError if capacity is not a positive integer or ttl is not positive. (Key hashing and the admission RNG are configured on WTinyLFU, not here.)

cache.get(key) / cache.set(key, value, ttl?)

Read (recording a use, which can promote the entry) and insert-or-update. A per-call ttl (milliseconds) overrides the cache-wide default for that entry, and every write refreshes the entry's expiry.

cache.peek(key) / cache.has(key) / cache.delete(key) / cache.clear()

peek reads without recording a use; the others are the obvious operations.

cache.stats() / cache.size / cache.capacity

stats() returns { size, capacity, hits, misses, evictions, hitRatio }.

The frequency sketch (also usable on its own)

FrequencySketch is a Count-Min Sketch with 4-bit saturating counters and periodic aging: the frequency estimator behind TinyLFU admission, and the engine the Cache uses internally. It is exported on its own for any "how hot is this key, approximately and cheaply" question.

import { FrequencySketch } from "koffein";

const sketch = new FrequencySketch(1000); // tuned for ~1000 live entries

// The sketch works on a 32-bit numeric hash of your key. Any integer works:
// it runs a murmur3 finalizer internally, so even low-entropy ids spread well.
sketch.increment(42);
sketch.increment(42);
sketch.increment(42);

sketch.frequency(42); // => 3   (an estimate; never below the true count)
sketch.frequency(7); //  => 0   (never seen)

Hashing string keys

The sketch takes a number so it stays a pure primitive. For string keys, hash them first (the Cache does this for you; here is a compact FNV-1a, the same one it uses, for the sketch on its own):

function fnv1a(str: string): number {
  let h = 0x811c9dc5;
  for (let i = 0; i < str.length; i++) {
    h ^= str.charCodeAt(i);
    h = Math.imul(h, 0x01000193);
  }
  return h >>> 0;
}

sketch.increment(fnv1a("user:1042"));
sketch.frequency(fnv1a("user:1042")); // => 1

Aging

Aging is automatic: once the sketch observes 10 x capacity increments, every counter is halved, so recent activity outweighs the distant past. You can also trigger it manually to decay the whole sketch on demand:

const s = new FrequencySketch(500);
for (let i = 0; i < 15; i++) s.increment(99); // saturates at 15
s.reset();
s.frequency(99); // => 7   (15 >> 1)

API

new FrequencySketch(capacity: number)

Creates a sketch tuned for roughly capacity live entries. Internally sizes to the next power of two and 4 hash rows. Throws RangeError if capacity is not a positive integer.

sketch.increment(hash: number): void

Records one occurrence of hash. Increments 4 counters (one per row, all distinct) up to a ceiling of 15, and ages the sketch when the sample fills.

sketch.frequency(hash: number): number

Returns the estimated count of hash, in 0..15. The estimate is the minimum across the 4 rows, so it can overestimate on a hash collision but never underestimates the true count. That one-sided error is exactly what an admission filter wants: better to admit a cold key than reject a hot one.

sketch.reset(): void

Halves every counter (recency-biased aging). Called automatically at the sample threshold; exposed for manual decay and inspection.

sketch.clear(): void

Drops all state.

sketch.size / sketch.capacity / sketch.sampleSize (readonly)

Diagnostics: increments observed since the last aging reset, the configured capacity, and the increment count that triggers aging (10 x capacity).

Design notes

• One-sided error. Count-Min never underestimates. A cache does not need the true frequency, only "is this key hotter than the victim it would evict", so a saturating 4-bit counter (0..15) is enough and keeps the whole sketch tiny: eight counters packed per 32-bit word.
• Distinct rows. The 4 rows use double hashing g_i = h1 + i * h2 with an odd stride, so a key's 4 counters never collide with each other. Only other keys can inflate an estimate, and only upward.
• Aging keeps it honest. Halving on a schedule is what separates TinyLFU from a plain frequency counter: yesterday's hot key decays instead of dominating.

Roadmap

• [x] FrequencySketch (Count-Min + 4-bit counters + aging) with correctness tests
• [x] Window (LRU ~1%) + SLRU main (probation / protected ~80%)
• [x] Admission gate: candidate-vs-victim frequency + randomized tie-break
• [x] Cache: get / set / has / delete / peek / clear, .stats()
• [x] TTL (cache-wide default + per-call override, injectable clock)
• [x] Hit-ratio bake-off (seeded Zipfian / scan / shifting traces vs LRU / LFU)
• [x] Pluggable EvictionPolicy interface (WTinyLFU / LRU / LFU / your own)
• [x] memo (sync/async, in-flight de-duplication, a rejected result not cached)
• [x] Extensible string-name policy selector ({ policy: 'lru' }, registerPolicy)

Out of scope for v1: ARC and S3-FIFO (behind the policy interface later), adaptive window resizing, and any distributed or multi-backend store (that is keyv's job; koffein stays in-memory).

References

The design rests on published, peer-reviewed work. Verified citations:

1. G. Einziger, R. Friedman, B. Manes. TinyLFU: A Highly Efficient Cache Admission Policy. ACM Transactions on Storage 13(4), Article 35, 2017. DOI:10.1145/3149371 · arXiv:1512.00727
2. G. Cormode, S. Muthukrishnan. An Improved Data Stream Summary: The Count-Min Sketch and its Applications. Journal of Algorithms 55(1):58-75, 2005. DOI:10.1016/j.jalgor.2003.12.001
3. A. Kirsch, M. Mitzenmacher. Less Hashing, Same Performance: Building a Better Bloom Filter. ESA 2006, LNCS 4168, pp. 456-467 (the g_i = h1 + i*h2 double hashing used here). Journal version: Random Structures & Algorithms 33(2):187-218, 2008. DOI:10.1007/11841036_42
4. R. Karedla, J. S. Love, B. G. Wherry. Caching Strategies to Improve Disk System Performance. IEEE Computer 27(3):38-46, 1994 (Segmented LRU). DOI:10.1109/2.268884
5. B. Manes. Caffeine, the reference W-TinyLFU cache for the JVM. github.com/ben-manes/caffeine
6. A. Appleby. MurmurHash3 (the fmix32 finalizer used to spread hashes). github.com/aappleby/smhasher

License

MIT (c) David Estevez