# Eviction and value modes (https://lazy-layers-cache.vercel.app/docs/concepts/eviction)

> How L1 decides what to evict (S3-FIFO by default, or LRU, SIEVE, FIFO or your own policy), how it stays within memory limits, and whether it stores copies or objects.



lazy-layers-cache evicts L1 entries with S3-FIFO by default, and offers LRU, SIEVE, FIFO or a policy you register. On the synthetic traces in [BENCHMARKS.md](https://github.com/Amon20044/LazyLayers/blob/main/BENCHMARKS.md#eviction-policies), S3-FIFO had the lowest mean miss ratio of the built-in policies, 56.39% against 61.31% for LRU. L1 is bounded by bytes as well as entries, and shrinks when the process nears its memory limits.

The built-in L1 has two independent choices: which entry leaves when it needs room (the **eviction policy**), and whether it keeps values as encoded bytes or as the objects themselves (the **value mode**).

## Eviction policies [#eviction-policies]

```js
const cache = createCache({
  levels: { L1: { maxEntries: 50_000 } }, // S3-FIFO by default
})

const lruCache = createCache({ levels: { L1: { policy: 'lru' } } })
```

| Policy                          | On a hit                                   | Evicts                                                                             | Best for                                                |
| ------------------------------- | ------------------------------------------ | ---------------------------------------------------------------------------------- | ------------------------------------------------------- |
| `s3fifo` (default)              | adds one to a 2-bit counter; nothing moves | new keys not reused while on probation, then main-queue keys whose counter ran out | almost every workload                                   |
| `lru`                           | moves the key to the front                 | the least recently used key                                                        | a popular set replaced wholesale that fits in the cache |
| `sieve`                         | sets one bit; nothing moves                | the oldest key not hit since the hand last passed                                  | skewed traffic, with the cheapest bookkeeping           |
| `sievePolicy({ maxVisits: 3 })` | adds one visit, up to 3                    | the oldest key whose visits ran out                                                | skewed traffic mixed with long scans                    |
| `fifo`                          | nothing                                    | the oldest key                                                                     | a baseline for comparison                               |

S3-FIFO ([Yang et al., SOSP 2023](https://dl.acm.org/doi/10.1145/3600006.3613147)) uses three queues. Every new key starts in a small probation queue (10% of entries). A key read while on probation moves to the main queue; any other key is evicted and its hash remembered in a ghost queue. A key that returns while remembered goes straight to the main queue. The main queue reinserts keys whose counter is above zero, lowering it by one, and evicts the rest. One-time keys therefore leave quickly without displacing the working set, and a new popular set is adopted within a round.

SIEVE ([Zhang et al., NSDI 2024](https://www.usenix.org/conference/nsdi24/presentation/zhang-yazhuo)) keeps keys in insertion order. A hand walks from the oldest key toward the newest, clearing visited bits, and evicts the first key it finds unvisited.

### Which to choose [#which-to-choose]

Measured with `benchmarks/policies.mjs` on synthetic traces; the full table, with the offline optimum for each case, is in the repository at `benchmarks/results/8.0.0-dev/policies.md`. Replayed through the real store with admission on, the default (`benchmarks/policies-store.mjs`), S3-FIFO missed 3.8 points less than LRU on average, with the same worst case.

| Policy   | Mean miss ratio | Worst against LRU | Best against LRU |
| -------- | --------------: | ----------------: | ---------------: |
| `s3fifo` |           56.4% |       +4.5 points |     −14.2 points |
| `sieve`  |           57.0% |       +9.9 points |     −13.6 points |
| `lru`    |           61.3% |                 — |                — |

* S3-FIFO had the lowest average miss ratio, and was within half a point of the best policy on average.
* Its worst case, and SIEVE's, is a popular set replaced wholesale while the cache can hold it; LRU wins there.
* S3-FIFO spends about 90 ns more than LRU per miss on bookkeeping (hashing the key, the ghost queue). A hit costs the same as SIEVE's. Every miss it avoids saves an origin load, which costs far more.

Keep the default unless your popular keys are replaced all at once, in which case choose `lru`.

### Your own policy [#your-own-policy]

A policy works on slot numbers only. It never sees keys or values, which keeps it deterministic and testable.

```ts
import { registerEvictionPolicy, type EvictionPolicyFactory } from 'lazy-layers-cache'

const myPolicy: EvictionPolicyFactory = (capacity) => ({
  name: 'my-policy',
  resize(capacity) { /* grow slot metadata */ },
  onInsert(slot) {},
  onHit(slot) {},
  onRemove(slot) {},
  selectVictim(isExpired) { return /* a resident slot, or 0 */ 0 },
  peekVictims(limit, visit) {},
  clear() {},
  stats() { return {} },
})

registerEvictionPolicy('my-policy', myPolicy)
// levels: { L1: { policy: 'my-policy' } }
```

Check it with the conformance kit:

```js
import { test } from 'node:test'
import { evictionPolicyConformance } from 'lazy-layers-cache/testing'

for (const check of evictionPolicyConformance(myPolicy)) test(check.name, check.run)
```

## Value modes [#value-modes]

|                               | `encoded` (default)                                                                   | `reference`                                                                                          |
| ----------------------------- | ------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------- |
| What L1 stores                | the value's wire bytes (up to 2 KiB as a compact one-byte string, larger as a Buffer) | the object you stored                                                                                |
| What a hit returns            | a new decoded copy                                                                    | the same object, every time                                                                          |
| Hit cost (1 KiB record)       | about 1.1 µs                                                                          | about 0.1 µs                                                                                         |
| Callers can affect each other | no                                                                                    | yes, if they modify the value                                                                        |
| Byte accounting               | exact                                                                                 | the object's heap size, from a model of V8's layout (`sizeOf: 'encoded'` for the exact encoded size) |

```js
const cache = createCache({
  levels: { L1: { valueMode: 'reference' } },
})
```

In `reference` mode, treat returned values as read-only. Outside production they are deep-frozen by default, so a modification throws where it happens instead of silently changing what every other caller reads. Set `freezeValues: true` to keep freezing in production, or `false` to turn it off.

Values that reach L1 from L2 or a peer are decoded once, on the way in, and stored as objects.

## Memory limits and pressure [#memory-limits-and-pressure]

Eviction is always on. A write that does not fit evicts the entries the policy values least until it does; you never have to delete entries to make room, and turning settings off cannot stop it. Two limits apply to every write:

* `maxEntries`, a count (1,000 by default).
* `maxMemory`, the bytes all built-in stores in the process may hold together (20% of effective memory by default; effective memory is the container limit, or host memory). Encoded values are charged their exact size. Reference-mode values are charged their heap size, computed from V8's object layout (see below).

The budget also watches the process, every 5 seconds by default:

| Signal                                                              | Pressure    | Critical     |
| ------------------------------------------------------------------- | ----------- | ------------ |
| Free memory, as a share of effective memory                         | under 15%   | under 5%     |
| Linux memory stall (PSI `some avg10`)                               | 10% or more | 50% or more  |
| V8 heap, as a share of its limit                                    | 85% or more | 95% or more  |
| RSS, as a share of `maxProcessMemory` (effective memory by default) | 90% or more | 100% or more |

* **Pressure** that lasts 5 seconds lowers the target to 90% of what the caches hold, once per sample, for as long as it lasts. Writes are still stored, by evicting older entries, so the cache keeps working while it shrinks.
* **Critical** acts at once: the target drops to 70% of what the caches hold, once per sample, and new L1 writes and promotions are refused until it passes.
* Evicting starts with fail-safe snapshots, which are read only when a loader fails, then live entries. It runs in slices of 1,024 evictions that yield to the event loop between them.
* After 30 seconds without pressure, the target grows back by 5% of `maxMemory` per sample.
* Bookkeeping, such as loads in flight and invalidation state, has its own fixed caps and is not refused under pressure, so reads and loads keep working.

Some mistakes are caught for you:

* A `maxMemory` above 75% of effective memory, such as `'100%'` or a size larger than the container, is lowered to 75%, with a `LAZY_LAYERS_MAX_MEMORY` warning.
* Writes check the V8 heap and RSS every 1,024 reservations or 4 MiB. A burst of writes between samples cannot exhaust the heap or the container, and this works even with `autoEvict: { enabled: false }`, which only stops the periodic sampling. RSS covers what the heap does not, such as Buffers.
* More than 1,000 caches on one budget produce a `LAZY_LAYERS_MANY_CACHES` warning. That usually means a cache is created per request and never closed.

Two limits, two jobs. `maxMemory` is what the cache may hold. `maxProcessMemory` is what the whole process should stay under, whatever is using the memory: as RSS nears it, the cache gives memory back. It defaults to effective memory, so a process nearing its container limit always makes the cache shrink, with nothing configured. Set it lower to leave headroom:

```js
const cache = createCache({
  levels: {
    L1: {
      maxEntries: 100_000,
      maxMemory: '512MiB', // what the cache may hold
      maxProcessMemory: '85%', // start giving memory back at 85% of the container
    },
  },
})
```

A cache can shrink to nothing, but it cannot free memory the rest of the application holds. When the application itself outgrows the container, the cache is the first thing to make room, not a guarantee against running out.

### How reference-mode values are sized [#how-reference-mode-values-are-sized]

A reference-mode entry is the object itself, and JavaScript has no call that measures an object. The cache computes its size from V8's object layout, measured on Node:

| Part                  | Bytes (64-bit)                                                                                            |
| --------------------- | --------------------------------------------------------------------------------------------------------- |
| Object                | 24, plus 8 per property; from 128 properties, a hash table of 24 per slot                                 |
| String                | 16, plus 1 per character (2 if any character is outside Latin-1), rounded up to 8                         |
| Number                | 0 for integers that fit in 32 bits, which live in their slot; 16 otherwise, except in an array of numbers |
| Array                 | 48, plus 8 per element                                                                                    |
| `Map` / `Set`         | a hash table sized to a power of two: 24 / 16 per slot                                                    |
| `Date`                | 96                                                                                                        |
| `Buffer`, typed array | about 192, plus its bytes                                                                                 |

`test/size-estimate.test.js` measures the heap V8 actually uses for common shapes and checks the result against it on every run:

* Within 3% for values that own their contents, such as database rows, long strings, arrays, maps and nested objects. The test allows 10%, for noise in measuring the heap.
* High, never low, where `JSON.parse` lets values share short strings (10 characters or fewer): up to 2× for an object full of them. The cache then holds fewer entries than it could, never more memory than allowed.
* An array that grew by `push` keeps spare slots V8 added as it grew, up to half its length, which are not counted. Its contents are.

Set `sizeOf: 'encoded'` to charge the exact encoded size instead, or pass a function.

## Expiry and fail-safe [#expiry-and-fail-safe]

Expired entries are removed when they are read, when the policy evicts them, and by a small sweep on each write, so they release their bytes even if nobody asks for them again.

When an entry expires, or is evicted because L1 holds `maxEntries`, L1 hands it to the fail-safe store, which can serve it for `failSafe.staleTtlMs` if the origin then fails. An entry removed to free memory (for a write that needs bytes, or under memory pressure) is not kept, because keeping it would not free anything. A deleted or invalidated entry is never kept.


## Questions

### Why is S3-FIFO the default instead of LRU?

On the policy matrix in BENCHMARKS.md it had the lowest mean miss ratio of the built-in policies, missed up to 14.18 points less than LRU, and was never more than 4.45 points behind it. Choose `lru` when the whole popular set is replaced at once and fits in the cache.

### What hit ratio does it reach on skewed traffic?

On Zipf α = 1.0 traffic over 100,000 keys with room for 10% of them, the in-memory store hit 78.23% with S3-FIFO, against 76.64% for quick-lru, which holds up to twice its configured size, and 73.59% for lru-cache.

### Should I use encoded or reference mode?

Encoded, the default, stores bytes and decodes a private copy on every hit, so callers cannot change each other's values: a warm L1 `get()` measured 1,141 ns. Reference mode stores the object and returns it, 120 ns in the same benchmark; use it when callers treat values as read-only.

### How much memory does each entry use?

In BENCHMARKS.md, 100,000 small entries retained 76.1 bytes each in encoded mode with LRU and 98.4 with S3-FIFO; reference mode retained 74.5 and 96.8. lru-cache retained 57.1; the difference is the expiry time, charged bytes and payload size each Lazy Layers entry keeps, and S3-FIFO's queue state.