jplevyak opened a new pull request, #13893:
URL: https://github.com/apache/trafficserver/pull/13893
## Description
### Background & Problem
The Clocked Least Frequently Used by Size (CLFUS) RAM cache replacement
policy is designed to maximize request hit rates by balancing frequency,
recency, object size density, and scan resistance. In production and sustained
benchmarks, however, CLFUS degrades over time and eventually underperforms a
simple LRU cache.
While S3-FIFO is a generally good caching algorithm, CLFUS is sensitive to
object sizes which may give it some advantages on particular mixed size
workloads, e.g. large streaming objects combined with small metadata objects
and additionally it support compression which might help on certain systems.
Your mileage may vary.
Several algorithmic bugs and design flaws causing this degradation:
1. No frequency decay for spared resident entries ("Cache Squatters"):
When an entry at the head of _lru[0] is evaluated for eviction and spared
because its value density exceeds _average_value, its hits counter was never
decayed or reset (contrary to the CLOCK mechanism described in the
documentation). Past popular entries retained massive hit counts indefinitely,
becoming permanent "zombies" that could never be evicted.
2. Recency inversion on cache hits:
In RamCacheCLFUS::get(), an entry in memory was only promoted to the tail
of _lru[0] if cache_value(e) > _average_value. Active, moderately sized objects
(e.g., 30 KB assets) with below-average value density were never refreshed on
hits and were prematurely evicted from the front of the queue while actively
serving client traffic.
3. Redundant 3-miss admission barrier & premature history expiration:
Objects had to clear both the seen hash table and the history queue
(_lru[1]) before being cached in memory, requiring ≥ 3 requests. Concurrently,
_tick() halved history entries immediately (1 >> 1 == 0), discarding new
history entries on their very first tick, while get() ignored accesses to
history entries without refreshing them.
4. Extreme size penalty:
Linear size division (hits + 1)/(size + 256) imposed an insurmountable
penalty (e.g., 64 × to 200 ×) on standard web objects (10 KB–200 KB) compared
to sub-kilobyte files.
5. Requeue loop churn:
When _average_value was uninitialized or low, requeue_limit = 100 allowed
eviction passes to spin multiple times through small caches in a single put().
──────
### Solution
This PR implements five targeted improvements:
1. Clock hit decay on spared victims (RamCacheCLFUS.cc):
When an entry is spared during eviction, its hit count is halved
(victim->hits >>= 1;), bounding unreferenced item lifetime to O(log(hits))
clock passes. Additionally, requeue_count is bounded by std::min(requeue_limit,
this->_objects) to prevent multiple loops over the same items in a single put.
2. Unconditional recency promotion on hit (RamCacheCLFUS.cc):
Removed the cache_value(e) > _average_value requirement in get(). Any hit
on a resident object unconditionally moves it to _lru[0].tail and increments
e->hits.
3. Streamlined admission & history preservation (RamCacheCLFUS.cc):
• Keys matching the seen filter on their second sighting are permitted
to compete for direct admission into _lru[0] rather than being forced to
Lhistory.
• Lookups hitting history entries in get() increment e->hits and
refresh the entry to _lru[1].tail so it survives until the disk fetch completes.
• New history entries are initialized with hits = 2 to grant a
multi-tick second chance.
4. Dampened size penalty (RamCacheCLFUS.h):
Replaced linear size division with an effective size curve: eff_size =
(size >> 1) + 2048. This preserves strict size monotonicity while dampening the
penalty ratio between 1 KB and 64 KB objects to < 15 ×.
5. Periodic global frequency aging (RamCacheCLFUS.cc):
Added _decay_epoch() running on a 30-second epoch under the stripe lock to
halve hit counts and decay _average_value, preventing obsolete popularity peaks
from skewing admission during working set transitions.
──────
### Tests Added & Verified
Enhanced test_RamCacheCLFUS.cc with 5 dedicated Catch2 test cases:
• CLFUS decays hit count when sparing victims during eviction
• CLFUS unconditionally promotes resident entries to the tail on hits
• CLFUS history entry is refreshed on get() hit
• CLFUS size dampening curve bounds disparity between small and large
objects
• CLFUS periodic epoch decay halves hit counts and decays average value
#### Verification:
• ctest -R RamCache passed 100% (23/23 tests, including RamCacheCLFUS,
RamCacheHitRate, RamCacheSeenFilter, RamCacheCopy, and RamCacheCompressEntries).
• Formatted with cmake --build build -t format.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
