Entity LFU cache eviction is process-dependent: store read counts are not reproducible across otherwise identical runs

[madumas]

Summary

EntityCache's LFU cache (LfuCache, graph/src/util/lfu_cache.rs) evicts a
different set of entries on every process, for the same deployment, the same
blocks and the same binary. The cause is a std::collections::HashMap whose
iteration order (randomly seeded per process) determines the insertion order
into a PriorityQueue in which ties on the eviction priority are the normal
case, not the exception.

The indexing result is unaffected — we verified this deliberately and at
some length: entity data, modification counts and PoI digests are identical
across runs. What is affected is every counter that depends on which reads
reach the store: cache hit rate, store read volume, and get_many batch
shapes. In other words, the read path is observably non-deterministic even
when the write path is deterministic.

We stumbled on this by accident while looking into an unrelated indexing
question: running the exact same indexing work twice produced slightly
different store read counts, which we first took for a bug in our own
analysis. Since "same input, same reads" is a natural assumption for anyone
benchmarking graph-node or tuning its cache from logs, it seemed worth
reporting. All line numbers below refer to master at
8e3debd675309d96eb987bf90f053f378bc917bf (v0.45.0).

Observed behavior

Setup: indexing the same block ranges repeatedly — same binary, same
configuration, same starting database state, one worker — while counting the
entity reads that reach the store.

Short window: 500 blocks of a mainnet deployment, two strictly identical runs:

run	modifications	PoI digests	store reads (entity found)	store reads (no entity)
A	53,209	497	71,818	22,231
B	53,209	497	71,721	22,231

Identical: every PoI digest (497/497) and the modification count. Different:
97 store reads (0.14 %), spread across entity types in both directions.

Longer windows: 5,000 blocks, three deployments, repeated runs:

deployment	runs	store reads, entity found (min–max)	spread	store reads, no entity
A (mainnet, high entity reuse)	6	594,368 – 595,392	0.17 %	181,367 (constant)
B (polygon, low entity reuse)	6	1,353,727 – 1,355,494	0.13 %	2,198,372 (constant)
C (working set fits in cache)	10	365 (constant)	0	945 (constant)

Four observations worth separating:

1. The variation is real, not a measurement artifact. It reproduces across
   two independent deployments on different chains and across window lengths
   differing by 10x. Deployment C, whose working set fits in the cache and
   never triggers eviction, shows zero variation over 10 runs — which is
   exactly what the proposed cause predicts.
2. Everything downstream of the reads is exactly constant. Across all
   runs: handler calls, modification counts, PoI digests (validated against
   production poi2$ digests, more than 10,000 anchors compared, zero
   divergences), and derived-entity lookups.
3. The set of keys read is stable even though the count is not.
   Comparing two runs of the same 500-block prefix: the union of distinct
   (entity_type, id) keys read is identical (37,562 in both); on the
   (block, entity_type, id) tuples common to both runs, multiplicities are
   identical; ~1.7 % of tuples are unique to one run. So what moves is at
   which block a key falls back to the store — never which keys are needed.
   That is consistent with the cause below: the first read of a key always
   reaches the store, so key-set closure is preserved, but subsequent reads
   may or may not be served from cache depending on eviction.
4. Reads that find no entity are exactly constant while reads that find
   one vary. This too is consistent: a store miss is cached —
   entity_cache.rs:246 inserts the None result into the LFU — so its
   constancy indicates the dominant pattern is load → null → create, where
   each absent key is read at most once before being created, and a first
   read always reaches the store regardless of eviction state.

Expected

Two identical runs over the same blocks with the same binary and the same
configuration should produce the same store read counts and the same cache hit
rate — or, if that is explicitly not a goal, the non-determinism should be
documented so that nobody builds measurement on top of it.

Concretely, EvictStats::hit_rate_pct() and accesses, logged per block in
core/src/subgraph/runner/mod.rs:647-656, currently vary run to run for
identical work.

Root cause analysis

Five links, all in graph/src/components/store/entity_cache.rs and
graph/src/util/lfu_cache.rs.

1. The pending updates live in a randomly-seeded HashMap.
graph/src/components/store/entity_cache.rs:140:

    /// The accumulated changes to an entity.
    updates: HashMap<EntityKey, EntityOp>,

std::collections::HashMap defaults to RandomState, whose seed is drawn once
per process. Iteration order therefore differs on every run.

2. That iteration order becomes the LFU insertion order.
entity_cache.rs:480 (in as_modifications), plus the load loop just above it
at :474:

            for (entity_key, entity) in self.store.get_many(missing.cloned().collect()).await? {
                self.current.insert(entity_key, Some(Arc::new(entity)));
            }
        }

        let mut mods = Vec::new();
        for (key, update) in self.updates {

Each arm of the match in that loop calls self.current.insert(key.clone(), …).
So at the end of every block, entities are (re-)inserted into the LFU in an
order that is random per process.

3. Every block ends with an eviction pass.
entity_cache.rs:545:

        let evict_stats = self
            .current
            .evict_and_stats(ENV_VARS.mappings.entity_cache_size);

with GRAPH_ENTITY_CACHE_SIZE defaulting to 10 MB
(graph/src/env/mappings.rs:176-177). For any deployment whose working set
exceeds that, this pass evicts on every single block.

4. The eviction priority produces ties by construction.
graph/src/util/lfu_cache.rs:59:

// The priorities are `(stale, frequency)` tuples, first all stale entries will be popped and
// then non-stale entries by least frequency.
type Priority = (bool, Reverse<u64>);

and lfu_cache.rs:133-146, where a new entry is pushed with:

                self.queue.push(
                    CacheEntry { weight, key, value, will_stale: false },
                    (false, Reverse(1)),
                );

Within one block the overwhelming majority of entries carry exactly
(false, Reverse(1)). Ties are the rule, not a corner case.

5. Ties are broken by insertion order.
lfu_cache.rs:286-294:

        while self.total_weight + dead_weight > max_weight {
            let entry = self
                .queue
                .pop()
                .expect("empty cache but total_weight > max_weight")
                .0;
            evicted += entry.weight;
            self.total_weight -= entry.weight;
        }

self.queue is a priority_queue::PriorityQueue (lfu_cache.rs:99,
priority-queue = "2.7.0"). At equal priority, which element pop() returns
depends on the internal heap layout, which depends on the order elements were
pushed — i.e. on link 2.

Chain: random HashMap order → random LFU insertion order → different
entries evicted at the block boundary → the next read of those keys is served
by the store instead of the cache (or the reverse) → store read counters move.
The effect also compounds: the surviving cache is carried into the next block,
so a divergence at block n changes the eviction candidate set at block n+1.

Why the result is nevertheless stable: the modifications form a set, not a
sequence, and the PoI is built from the handler event stream, not from where a
read was served. Eviction changes provenance, not values. This is consistent
with everything we measured: identical digests, identical modification counts,
identical key-set union.

Impact

Not a correctness bug. We want to be explicit about that: we found no effect on
entity data, on modifications, or on PoI, and we looked hard (more than 10,000
PoI anchors compared against production, zero divergences).

What it does affect:

• Cache hit rate is not reproducible. EvictStats::hit_rate_pct() /
  accesses, logged per block, differ between identical runs. Anyone tuning
  GRAPH_ENTITY_CACHE_SIZE from those logs is reading a noisy signal with no
  documented noise floor.
• Database read volume is not reproducible. The number of entities fetched
  by store.get_many in as_modifications varies run to run, at the
  ~0.1-0.5 % level in our measurements. Small on average; not something you
  can subtract out when comparing two configurations whose expected difference
  is itself a few percent.
• Any analysis that treats read counts as reproducible is misled. The safe
  invariant is the union of distinct keys read — which we verified is stable
  — not the per-run read counts.
• Eviction quality, marginally. With ties this common, LFU degrades toward
  "evict an arbitrary entry of frequency 1". That may be fine, but it is
  probably not what the LFU was meant to do, and it is invisible today.

Related reports

The closest prior report we found is #5866 ("Load Related requests not
deterministic"), closed early 2026 without an identified root cause. We do
not claim the mechanism here explains it: load_related fetches derived
entities from the store unconditionally (it populates the LFU but never reads
from it), so its database query count is not eviction-gated — and in our runs
derived-entity lookups were exactly constant. But the symptom reported there —
read counts that vary across runs and resist reproduction at a fixed block —
is the same shape of problem, and the mechanism described here is a systematic
source of exactly that shape on the get path. It may be worth keeping both
in mind when triaging future reports of non-reproducible read behavior.

Suggested fix directions

We are not proposing a specific patch, and we do not know which of these fits
graph-node's priorities. Options, roughly in increasing order of cost:

1. Document the behavior and leave it. State in lfu_cache.rs /
   entity_cache.rs that eviction order is process-dependent and that read-path
   counters are not reproducible across runs. This is the cheapest correct
   outcome. If this is the chosen answer we are happy to send the doc patch.
2. Make the update map's iteration order deterministic. Either a
   BTreeMap<EntityKey, EntityOp> or a HashMap with a fixed-seed hasher for
   updates at entity_cache.rs:140. Note that updates is on the hot path,
   not merely drained once per block: it is consulted on every get
   (entity_cache.rs:266) and written through entity_op (:426), so a
   BTreeMap puts an O(log n) lookup on every entity load and save. Likely
   negligible against store roundtrips, but worth measuring. A fixed-seed
   hasher avoids that cost entirely; losing HashDoS hardening is not a concern
   for this map, whose keys are generated by the subgraph's own handlers.
3. Make the tie-break explicit in the LFU. Extend Priority with a
   deterministic third component — an insertion sequence number, or the entity
   key itself — so that pop() never depends on heap layout. This fixes the
   symptom at the layer that owns it, independently of who inserts, and would
   also make eviction behavior explainable rather than incidental.
4. Revisit the priority itself. If ties at (false, Reverse(1)) are the
   normal case, frequency alone may not be carrying much signal at block scale.
   A recency component, or per-entity-type weighting, would both break ties and
   arguably improve eviction. Larger change, out of scope for this issue, noted
   only because the tie density is the underlying reason the bug is visible.

Options 2 and 3 are complementary rather than alternatives: 2 removes the
current source of entropy, 3 makes the LFU robust to the next one.

[SnowingFox]

Opened a PR to address this: #6707