cockroachdb / cockroachdb/cockroach
rangecache: range descriptor cache is effectively FIFO, not LRU
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
**Summary**
The [RangeCache](https://github.com/cockroachlabs/cockroach/blob/d52c0693ce1541f38f6b32cdba035c2b047c12b2/pkg/kv/kvclient/rangecache/range_cache.go#L136) is configured with `cache.CacheLRU` eviction policy, but in practice it behaves like a FIFO cache: cache reads do not promote entries toward the most-recently-used end of the eviction list. Only inserts and updates reorder entries. As a result, a frequently-read descriptor can be evicted purely because it is old, even while it is being read constantly.
**Details**
The backing [cache.OrderedCache](https://github.com/cockroachlabs/cockroach/blob/d52c0693ce1541f38f6b32cdba035c2b047c12b2/pkg/kv/kvclient/rangecache/range_cache.go#L246-L251) maintains its LRU ordering by moving an entry on access. The `RangeCache`, however, reads entries through `getCachedRLocked` which fetches the raw entry without moving it to the back of the eviction queue:
https://github.com/cockroachdb/cockroach/blob/8ba72f3434ea5547293eb034cebd689000d5f777/pkg/kv/kvclient/rangecache/range_cache.go#L1130-L1186
This is deliberate: reads are taken under `RangeCache.RLock()` so that many lookups can proceed concurrently. Promoting an entry mutates the eviction list and would require the exclusive `Lock()`, serializing all reads and hurting throughput on the hot path. So the current code trades LRU correctness for read concurrency, leaving the cache as FIFO.
**Impact**
On large clusters where the number of ranges exceeds `kv.range_descriptor_cache.size` (default 1M entries), the cache is permanently over capacity and constantly evicting. With FIFO ordering, hot descriptors are evicted on the same schedule as cold ones, lowering the effective hit rate and driving avoidable `RangeLookup` traffic to `meta1/meta2`. Observed in a support escalation on a ~2M-range cluster, where `meta1/meta2` were the hottest ranges.
Note: for a perfectly uniform access pattern over more ranges than fit in the cache, LRU and FIFO perform equally badly — true LRU helps when there is locality / stickiness.
**Possible fixes**
Make reads promote entries so the cache is genuinely LRU, without giving up read concurrency. Options [discussed](https://cockroachlabs.slack.com/archives/G01G8LK77DK/p1783017948396479?thread_ts=1782858564.704869&cid=G01G8LK77DK):
1. Move-on-read under exclusive lock — simplest (`MoveToEnd` in `getCachedRLocked`), but requires `Lock()` on the read path, likely regressing throughput. Probably unacceptable as-is.
2. Batched promotion — record accessed entries in a lock-free/append-only list under `RLock`, then periodically (every N accesses) take `Lock()` and apply the promotions in a batch. For `N << cache size` this approximates LRU well while keeping the common path read-locked. Implementable entirely at the RangeCache layer.
3. Lock-free eviction list — make the underlying ordering list support a concurrent `MoveToEnd` so promotion doesn't need the exclusive lock.
Explore other caching strategies such as SIEVE.
Jira issue: CRDB-65469
Contributor guide
Assessment
This issue has not been assessed yet.