Slow recovery with large entry counts in block engine

[leiysky]

Summary

We observed that disk cache recovery can become slow when the number of entries is large, even when the payload size is tiny. This suggests that recovery time is strongly affected by entry metadata / index reconstruction cost, not only by total value bytes.

In a metadata-heavy simulation with 50M entries and 1-byte values, recovery took about 24.35s on my machine.

For a 2TiB cache with 16KiB values, the raw payload-only entry count is about:

2 TiB / 16 KiB = 134,217,728 entries

So production-scale caches may have 100M+ entries, where recovery time could become a noticeable startup / restart latency.

Environment

• foyer: 0.22.3
• OS: macOS arm64, Darwin 25.3.0
• rustc: 1.96.0-nightly (55e86c996 2026-04-02)
• cargo: 1.96.0-nightly (888f67534 2026-03-30)

I understand foyer is primarily designed for Linux production use, so these numbers should be treated as a local reproduction / signal rather than final production benchmark data.

Benchmark Setup

The benchmark builds a HybridCache<u64, Vec<u8>> backed by FsDeviceBuilder, writes N entries, closes the cache, then reopens it and measures the time spent in HybridCache::builder().storage().build().await.

Most foyer/block-engine settings are left at defaults. The relevant non-default settings are:

• HybridCachePolicy::WriteOnInsertion, to make sure entries are written to disk.
• flush_on_close(false), to avoid measuring extra close-time flush work.
• fixed FsDeviceBuilder::with_capacity(...), to keep the test capacity explicit.
• BlockEngineConfig::with_recover_concurrency(...), varied in one test.
• BlockEngineConfig::with_flushers(1), matching block-engine default.

Recovery correctness is checked by loading 32 evenly distributed keys after reopening.

Results

4KiB value baseline: effect of recover_concurrency

value_bytes=4096, flushers=1, capacity_factor=4, 3 samples per point. Numbers below are median recovery times.

recover_concurrency	1k entries	10k entries	100k entries	1M entries
1	0.384 ms	1.828 ms	16.432 ms	190.792 ms
2	0.324 ms	1.562 ms	13.286 ms	170.964 ms
4	0.344 ms	1.653 ms	12.844 ms	156.829 ms
8	0.353 ms	1.652 ms	13.094 ms	159.954 ms
16	0.394 ms	1.630 ms	13.347 ms	165.685 ms

Observation: increasing recover_concurrency helps up to around 4 in this environment, but the improvement is limited. At 1M entries, the best result was about 1.22x faster than concurrency 1.

50M metadata-heavy simulation

Command shape:

recovery \
  --keys 50000000 \
  --value-bytes 1 \
  --samples 1 \
  --verify-keys 32 \
  --capacity-factor 6144 \
  --flushers 1 \
  --recover-concurrency 4

Result:

entries	value size	logical capacity	populate time	recovery time	verify time
50,000,000	1 byte	292,968.75 MiB	125.14s	24.35s	49.69ms

All 32 sampled keys were readable after recovery.

A smaller capacity factor failed to recover early keys, likely because the cache had already evicted/overwritten older entries. The larger capacity was used to keep the 50M-entry dataset recoverable and focus the test on recovery cost.

Why this matters

For large block caches with small or medium value sizes, entry count can be very high. For example, a 2TiB cache with 16KiB values contains about 134M entries at the raw payload level, before metadata and fragmentation overhead.

If recovery cost scales heavily with entry count and/or block scanning, restart latency can become tens of seconds or more.

Questions / Possible Improvements

Would it be possible to improve recovery for high-entry-count caches? Some possible directions:

• persist a compact index/checkpoint to reduce full block scanning during recovery;
• support incremental or lazy recovery, allowing the cache to become available before the full index is rebuilt;
• expose recovery progress / metrics so applications can observe startup recovery cost;
• document expected recovery complexity and tuning guidance for high-entry-count deployments;
• investigate whether metadata layout or block index scanning can be optimized for very many small entries.

I can provide the benchmark source if useful.