erigontech / erigontech/erigon

execution/cache: ModeNoOp can over-admit and silently evict

Open
#22,475 1 comment 0 reactions 1 assignee Claimed by @yperbasis View on GitHub
ErigonDB
Dominant language
Go
Stars
3.6k
Forks
1.5k
Avg merge
1d 16h
Merged PRs (30d)
455

Description

`ModeNoOp` promises fill-and-freeze semantics: once the cache is full, new keys are dropped (counted via the `dropped` metric) and first writers win. Two independent admission paths break that promise.

## Enveloped caches silently evict at the start capacity

- `NewGenericCacheWithAvg` starts every cache at `genericCacheStartCapacity` (1024 slots), and growth is driven from the put path via `needGrow`, which excludes `ModeNoOp` — so a `ModeNoOp` cache keeps its 1024-slot freelru forever.
- The admission check refuses inserts on `currentSize+newSize > capacityB || Len() >= maxCap`. With `capacityB/avgBytes` well above 1024 the byte bound admits far more entries than the slot array holds, and the `Len() >= maxCap` guard is dead (`Len` is bounded by the 1024-slot LRU, while `maxCap` is the byte-derived ceiling).
- Inserts past the live slot capacity make freelru evict within the receiving shard. Old entries silently vanish and are not counted as `dropped`, which is exactly what "drop new keys when full" exists to prevent.

A focused repro using a 1 MiB cache with a 256-byte average (`curCap=1024`, `maxCap=4096`) inserted 2,000 distinct keys and observed:

```
Len=1024 evictions=976 dropped=0
```

## Concurrent cold admissions can exceed the byte budget

The byte-budget check and reservation are separate atomic operations:

1. Each writer evaluates `currentSize.Load()+newSize <= capacityB`.
2. The writers are serialized only by their per-key stripes, so distinct keys can pass the check concurrently.
3. Each writer later reserves its bytes with `currentSize.Add(newSize)` and inserts.

With a 53-byte budget that fits exactly one 53-byte entry, two distinct-key puts reproducibly leave both entries resident and report `SizeBytes=106`. The reserve-before-remove change in #22466 closes the transient-dip window during an update, but it does not make cold-key admission atomic.

## Impact

Impact is limited to the diagnostic baseline (`ModeEvictLRU` is the default in-tree), but flipping a production-sized cache to `ModeNoOp` for an A/B comparison quietly changes its semantics:

- an enveloped cache becomes a per-shard LRU over its start-size generation instead of a frozen first-writer set;
- concurrent cold writers can exceed the configured byte budget.

## Possible directions

- Let `ModeNoOp` jump-grow too. Growth is orthogonal to admission policy, and the byte-budget check can still freeze the cache once `capacityB` is reached.
- Or size the initial LRU at `maxCap` for `ModeNoOp`, trading the small-start property for correct semantics.
- Make the byte reservation atomic with admission, using a CAS loop or a shared admission lock; account carefully for collision replacement and rejected inserts.

Regression coverage should include both:

- an enveloped `ModeNoOp` cache must report zero capacity evictions before its configured limit and increment `dropped` once full;
- two concurrent distinct-key puts against a one-entry byte budget must leave exactly one entry resident.

Both behaviors predate #22466 and were noticed while reviewing its concurrency and accounting changes.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.