You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@trafficserver.apache.org by "jplevyak (via GitHub)" <gi...@apache.org> on 2026/10/22 19:31:01 UTC
[PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#issuecomment-6387191060
<!-- address-comments-summary -->
## Address-comments run — 2026-10-24
<table>
<tr><th>Comment</th><th>File / Topic</th><th>Label</th><th>Action / Reason</th></tr>
<tr><td>4366151916</td><td>History-recency test could not detect a regression</td><td>FIX</td><td>Fixed in 7c210ab41: a second history entry is added and must be the tail before the lookup, so <code>get(key2)</code> has to move <code>e2</code> to the tail. Verified the test fails if the remove/enqueue in <code>get()</code> is removed.</td></tr>
<tr><td>4366061256</td><td>Aging clock skipped elapsed intervals / hit-only traffic</td><td>SKIP-DONE</td><td>Fixed in 420397d8f and 833424347.</td></tr>
</table>
_Items marked SKIP-DONE were addressed in prior commits or a prior run of this skill._
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366122967
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -243,6 +247,38 @@ RamCacheCLFUS::init(int64_t abytes, StripeSM *astripe)
}
}
+// Advance one epoch for every full decay interval that has elapsed, so idle
+// periods age popularity as much as busy ones. Called from both get() and
+// put() so that hit-only traffic still ages entries.
+void
+RamCacheCLFUS::_decay_epochs()
+{
+ ink_hrtime now = ink_get_hrtime();
+ ink_hrtime elapsed = now - this->_last_decay_time;
+
+ if (elapsed < decay_interval) {
+ return;
+ }
+ // 32 or more epochs clears every hit count, so the advance can be capped
+ // without changing the result while keeping _epoch differences in range.
+ int epochs = static_cast<int>(std::min<ink_hrtime>(elapsed / decay_interval, 32));
+ this->_epoch += epochs;
+ this->_average_value = std::ldexp(this->_average_value, -epochs);
Review Comment:
Agreed. The cap was only meant to bound entry epoch differences. Fixed in 833424347: entry epochs still advance by at most 32, which clears any 32-bit hit count, but `_average_value` now decays by the full interval count. The long-idle test asserts exactly 2⁻⁴⁰ after 40 intervals.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#issuecomment-6380383235
Addressed both "previously missed" items from the last review in 833424347:
- **Spared-victim decay:** the test now asserts `hits == 7` (16 → 8 when spared, 8 → 7 when requeued), so it fails if the halving is removed.
- **Seen-filter second sighting:** new test `CLFUS seen filter admits a filtered key on its second sighting`. With the filter active and the cache full, a key rejected on first sight becomes resident on its second sighting when the victims are worth less, and goes to history (residents kept) when they're worth more.
I checked each test by removing the code it covers and confirming it fails.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "john-icti (via GitHub)" <gi...@apache.org>.
john-icti commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4367860870
##########
src/iocore/cache/unit_tests/test_RamCacheCLFUS.cc:
##########
@@ -398,3 +456,295 @@ TEST_CASE("CLFUS value metric is a floating-point density", "[cache][ramcache][c
static_assert(v_hot > v_one, "CLFUS value metric does not increase with hits");
static_assert(v_small > v_large, "CLFUS value metric does not decrease with size");
}
+
+namespace
+{
+
+CryptoHash
+make_key(uint64_t id)
+{
+ CryptoHash key;
+ key.u32[0] = static_cast<uint32_t>(0xc0ffee00 + id);
+ key.u32[2] = static_cast<uint32_t>(0xdeadbeef + id);
+ key.u32[3] = static_cast<uint32_t>(0x12345678 + id);
+ return key;
+}
+
+} // namespace
+
+TEST_CASE("CLFUS decays hit count when sparing victims during eviction", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(32 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(8 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+ auto key3 = make_key(3);
+
+ REQUIRE(rc.put(&key1, buf.get(), 8 * 1024) == 1);
+ REQUIRE(rc.put(&key2, buf.get(), 8 * 1024) == 1);
+ REQUIRE(rc.put(&key3, buf.get(), 8 * 1024) == 1);
+
+ RamCacheCLFUSEntry *e1 = RamCacheCLFUSTestAccess::find_entry(rc, key1);
+ REQUIRE(e1 != nullptr);
+ e1->hits = 16; // Give key1 high hits so it exceeds average value
+
+ // key4 triggers an eviction pass
+ auto key4 = make_key(4);
+ rc.put(&key4, buf.get(), 8 * 1024);
+
+ // e1 was spared on its first pass as a victim (16 -> 8), then taken on the
+ // second pass once the requeue budget ran out and put back by
+ // _requeue_victims() (8 -> 7). Without the spared-victim decay it would be 15.
+ CHECK(e1->hits == 7);
+}
+
+TEST_CASE("CLFUS unconditionally promotes resident entries to the tail on hits", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(64 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(4 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+ auto key3 = make_key(3);
+
+ REQUIRE(rc.put(&key1, buf.get(), 4 * 1024) == 1);
+ REQUIRE(rc.put(&key2, buf.get(), 4 * 1024) == 1);
+ REQUIRE(rc.put(&key3, buf.get(), 4 * 1024) == 1);
+
+ RamCacheCLFUSEntry *e1 = RamCacheCLFUSTestAccess::find_entry(rc, key1);
+ REQUIRE(e1 != nullptr);
+ // Initial order in _lru[0] has e1 at the head
+ CHECK(RamCacheCLFUSTestAccess::lru_head(rc) == e1);
+
+ // Inflate _average_value so e1's value is lower than average
+ RamCacheCLFUSTestAccess::set_average_value(rc, 1000.0);
+
+ // get() on key1 must unconditionally promote e1 to the tail of _lru[0]
+ Ptr<IOBufferData> got;
+ CHECK(rc.get(&key1, &got) == 1);
+ CHECK(RamCacheCLFUSTestAccess::lru_tail(rc) == e1);
+ CHECK(RamCacheCLFUSTestAccess::lru_head(rc) != e1);
+}
+
+TEST_CASE("CLFUS history entry is refreshed on get() hit", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(12 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(8 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+
+ REQUIRE(rc.put(&key1, buf.get(), 8 * 1024) == 1);
+ // key2 cannot fit in 12KB (8KB + 8KB > 12KB), routed to history (_lru[1])
+ CHECK(rc.put(&key2, buf.get(), 8 * 1024) == 0);
+
+ RamCacheCLFUSEntry *e2 = RamCacheCLFUSTestAccess::find_entry(rc, key2);
+ REQUIRE(e2 != nullptr);
+ REQUIRE(e2->flag_bits.lru == 1); // in history
+
+ uint64_t hits_before = e2->hits;
+ Ptr<IOBufferData> got;
Review Comment:
Fixed in 7c210ab41. The test now adds a second history entry (key3) and requires it to be the history tail before the lookup, so get(key2) must move e2 to the tail. Verified that removing the remove/enqueue in get() makes the test fail.
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -775,10 +799,18 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
if (!this->_max_bytes) {
return 0;
}
+ ink_hrtime now = ink_get_hrtime();
+ if (now - this->_last_decay_time > HRTIME_SECONDS(30)) {
+ if (this->_last_decay_time != 0) {
+ this->_decay_epoch();
+ }
+ this->_last_decay_time = now;
Review Comment:
Fixed in 420397d8f. _decay_epochs() now advances one epoch per whole elapsed 30s interval (carrying the partial remainder), and get() also checks the clock so hit-only traffic ages entries. 833424347 additionally decays _average_value by the full interval count rather than the 32-epoch cap.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4352810653
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -243,6 +244,20 @@ RamCacheCLFUS::init(int64_t abytes, StripeSM *astripe)
}
}
+void
+RamCacheCLFUS::_decay_epoch()
+{
+ forl_LL(RamCacheCLFUSEntry, e, this->_lru[0])
+ {
+ e->hits >>= 1;
+ }
+ forl_LL(RamCacheCLFUSEntry, e, this->_lru[1])
+ {
+ e->hits >>= 1;
+ }
+ this->_average_value *= 0.5;
+}
Review Comment:
Calling `_decay_epoch()` from `put()` does a full traversal of both LRU lists. On large RAM caches this can introduce periodic latency spikes (the first `put()` after 30s pays O(N)). Consider an incremental/lazy decay design (e.g., epoch counter with per-entry last_epoch, or time-sliced work budget per `put()`/`get()`) to spread the cost while preserving aging behavior.
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -775,10 +791,18 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
if (!this->_max_bytes) {
return 0;
}
+ ink_hrtime now = ink_get_hrtime();
+ if (now - this->_last_decay_time > HRTIME_SECONDS(30)) {
+ if (this->_last_decay_time != 0) {
+ this->_decay_epoch();
+ }
+ this->_last_decay_time = now;
+ }
Review Comment:
Calling `_decay_epoch()` from `put()` does a full traversal of both LRU lists. On large RAM caches this can introduce periodic latency spikes (the first `put()` after 30s pays O(N)). Consider an incremental/lazy decay design (e.g., epoch counter with per-entry last_epoch, or time-sliced work budget per `put()`/`get()`) to spread the cost while preserving aging behavior.
##########
src/iocore/cache/unit_tests/test_RamCacheCLFUS.cc:
##########
@@ -398,3 +428,183 @@ TEST_CASE("CLFUS value metric is a floating-point density", "[cache][ramcache][c
static_assert(v_hot > v_one, "CLFUS value metric does not increase with hits");
static_assert(v_small > v_large, "CLFUS value metric does not decrease with size");
}
+
+namespace
+{
+
+CryptoHash
+make_key(uint64_t id)
+{
+ CryptoHash key;
+ key.u64[0] = 0xc0ffee00 + id;
+ key.u64[1] = 0xdeadbeef + id;
+ key.u32[3] = static_cast<uint32_t>(0x12345678 + id);
Review Comment:
`CryptoHash` commonly exposes multiple overlapping views (e.g., `u64[]` and `u32[]`) of the same underlying bytes. Writing `u32[3]` after `u64[1]` can partially overwrite the bytes you just set (and can be endianness/layout sensitive), making the test key construction less deterministic/portable. Prefer initializing exactly one view (all `u64[]`, or a byte array) or zero-initialize then fill a single representation.
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -834,7 +858,7 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
}
Que(RamCacheCLFUSEntry, lru_link) victims;
RamCacheCLFUSEntry *victim = nullptr;
- int requeue_count = requeue_limit;
+ int requeue_count = std::min(static_cast<int64_t>(requeue_limit), this->_objects);
Review Comment:
`std::min(...)` here yields an `int64_t` but is assigned to `int`. Depending on compiler flags (e.g., `-Wconversion/-Werror`) this can warn or truncate when `_objects` exceeds `INT_MAX`. Use a consistent type (e.g., make `requeue_count` `int64_t` or explicitly cast after bounding) to avoid narrowing/truncation.
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -943,7 +977,7 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
e = THREAD_ALLOC(ramCacheCLFUSEntryAllocator, this_ethread());
e->key = *key;
e->auxkey = auxkey;
- e->hits = 1;
+ e->hits = 2;
e->size = data->block_size();
e->flags = 0;
this->_bucket[i].push(e);
Review Comment:
This changes the initial hit count for all newly allocated entries from 1 to 2. The PR description calls out initializing new *history* entries with `hits = 2`, but this allocation site appears to be shared by multiple insertion paths. If this can also allocate resident (_lru[0]) entries, it will unintentionally bias admission/retention. Consider setting the initial hits based on the destination queue (history vs resident), or keep resident entries at 1 and only bump history entries.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub) via github" <gi...@trafficserver.apache.org>.
jplevyak commented on PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#issuecomment-6563628924
@bryancall Thanks for the thorough review. Addressed in c1e2483a8:
- **Wall clock steps:** `_decay_epochs()` resets `_last_decay_time` when `elapsed < 0`. Forward steps are left as is, since aging everything at once is harmless.
- **seen_match before saturation:** not intended. `seen_match` is now set only when `_history >= _objects`, so the unsaturated path matches master. New test covers a tag collision with unsaturated history.
- **hits = 2:** commented, and the history test now checks it. That test already exercises it: `e2` survives the `_tick()` from `key3`'s put, and with `hits = 1` it is freed.
- **Comments:** the size-curve comment now states it is `2(h+1)/(size+4608)`, a fixed ~4.5 KiB charge (1K:64K ~12.5x vs ~51x). Fixed the "64x" test comment and the `RamCacheCLFUSTestAccess` comment, and removed the restated ones.
- **Null deref:** `REQUIRE` on both pointers.
- **hits++ wrap:** left as is. A wrap needs ~4B touches in one epoch and only makes one entry look cold for one epoch.
Each new check fails with its fix reverted. All 78 cache tests pass.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#issuecomment-6356449915
<!-- address-comments-summary -->
## Address-comments run — 2026-10-23
Addressed in d5bbd653e.
<table>
<tr><th>Comment</th><th>File / Topic</th><th>Label</th><th>Action / Reason</th></tr>
<tr><td>4352810653, 4352810729</td><td>O(N) <code>_decay_epoch()</code> walk in <code>put()</code></td><td>FIX</td><td>Decay is now lazy. <code>_decay_epoch()</code> just bumps a global epoch (O(1)), and each entry carries the epoch of its last decay. <code>_apply_decay()</code> catches it up (<code>hits >>= elapsed</code>, cleared at 32 or more epochs) wherever <code>hits</code> is read: get() resident and history hits, put() on an existing entry, eviction victims, and <code>_tick()</code>. <code>hits</code> was split into 32-bit <code>hits</code> plus <code>epoch</code>, so the entry stays the same size.</td></tr>
<tr><td>4352810784</td><td><code>requeue_count</code> int64_t to int narrowing</td><td>FIX-EASY</td><td>Now <code>int64_t</code>. It couldn't actually truncate, since it's capped at 100.</td></tr>
<tr><td>4352810830</td><td><code>hits = 2</code> also affects resident entries</td><td>SKIP-WRONG</td><td>That assignment is under <code>Lhistory:</code> and only creates history entries (<code>flag_bits.lru = 1</code>, queued on <code>_lru[1]</code>). New resident entries are created under <code>Linsert:</code> and still start at <code>hits = 1</code>.</td></tr>
<tr><td>4352810884</td><td>Overlapping u64/u32 writes in test <code>make_key</code></td><td>FIX-EASY</td><td>Keys are now written only through <code>u32[]</code>. The <code>CryptoHash</code> constructor already zeroes the key.</td></tr>
</table>
Tests: the epoch-decay test now checks that decay is deferred until the entry is touched. A new test covers decay across several epochs and clearing after 32 or more.
_Items marked SKIP-WRONG include the evidence above._
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4368089529
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -880,13 +932,19 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
victim_value += cache_value(victim);
this->_tick();
if (!e) {
- goto Lhistory;
+ if (!seen_match) {
+ goto Lhistory;
+ }
+ if (this->_bytes + victim->size + size > this->_max_bytes && victim_value > cache_value_hits_size(1, size)) {
Review Comment:
Agreed, fixed in c25844539. put() now uses size + entry_overhead for the candidate in every fit check, and adds the victim's entry_overhead in the two restore-feasibility checks and in the Linsert restore check. Most of these checks predate this PR, but the seen-match path had the same gap. The new test `CLFUS admission accounts for per-entry overhead` reproduces your scenario (three 8 KiB residents, 32 KiB cache, 7424-byte copy-in candidate): before the fix it admitted the candidate and left _bytes at 33024; now the candidate goes to history and _bytes stays within _max_bytes.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366103236
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -243,6 +247,38 @@ RamCacheCLFUS::init(int64_t abytes, StripeSM *astripe)
}
}
+// Advance one epoch for every full decay interval that has elapsed, so idle
+// periods age popularity as much as busy ones. Called from both get() and
+// put() so that hit-only traffic still ages entries.
+void
+RamCacheCLFUS::_decay_epochs()
+{
+ ink_hrtime now = ink_get_hrtime();
+ ink_hrtime elapsed = now - this->_last_decay_time;
+
+ if (elapsed < decay_interval) {
+ return;
+ }
+ // 32 or more epochs clears every hit count, so the advance can be capped
+ // without changing the result while keeping _epoch differences in range.
+ int epochs = static_cast<int>(std::min<ink_hrtime>(elapsed / decay_interval, 32));
+ this->_epoch += epochs;
+ this->_average_value = std::ldexp(this->_average_value, -epochs);
Review Comment:
The 32-epoch cap clears `uint32_t` hit counts, but stops `_average_value` from aging by all elapsed intervals. After 40 idle intervals, an average of 8 becomes approximately 1.86e-9 instead of 7.28e-12, leaving the threshold above its intended value. Keep the capped advance for entry epochs, decay the average by the full interval count, and assert the expected value in the long-idle test.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#issuecomment-6380282365
> Time-based aging skips elapsed intervals and does not advance during hit-only traffic, preserving stale popularity weights.
▎ - Skipped intervals: _decay_epochs() now advances one epoch for each whole 30s interval that has passed, not one per check. The leftover partial interval carries over to the next decay. The advance is
▎ capped at 32 epochs, which already clears any 32-bit hit count, so a long idle period clears counts rather than wrapping.
▎ - Hit-only traffic: both get() and put() now check for elapsed intervals, so a cache serving only hits still ages. Since decay is lazy (an O(1) epoch bump, applied to each entry when it's next touched),
▎ the extra cost per get() is one clock_gettime.
▎
▎ A new unit test ages an entry through get() alone. It checks that 3.5 intervals give three halvings with the remainder carried over, and that 40 intervals clear the count.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "john-icti (via GitHub)" <gi...@apache.org>.
john-icti commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4367860870
##########
src/iocore/cache/unit_tests/test_RamCacheCLFUS.cc:
##########
@@ -398,3 +456,295 @@ TEST_CASE("CLFUS value metric is a floating-point density", "[cache][ramcache][c
static_assert(v_hot > v_one, "CLFUS value metric does not increase with hits");
static_assert(v_small > v_large, "CLFUS value metric does not decrease with size");
}
+
+namespace
+{
+
+CryptoHash
+make_key(uint64_t id)
+{
+ CryptoHash key;
+ key.u32[0] = static_cast<uint32_t>(0xc0ffee00 + id);
+ key.u32[2] = static_cast<uint32_t>(0xdeadbeef + id);
+ key.u32[3] = static_cast<uint32_t>(0x12345678 + id);
+ return key;
+}
+
+} // namespace
+
+TEST_CASE("CLFUS decays hit count when sparing victims during eviction", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(32 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(8 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+ auto key3 = make_key(3);
+
+ REQUIRE(rc.put(&key1, buf.get(), 8 * 1024) == 1);
+ REQUIRE(rc.put(&key2, buf.get(), 8 * 1024) == 1);
+ REQUIRE(rc.put(&key3, buf.get(), 8 * 1024) == 1);
+
+ RamCacheCLFUSEntry *e1 = RamCacheCLFUSTestAccess::find_entry(rc, key1);
+ REQUIRE(e1 != nullptr);
+ e1->hits = 16; // Give key1 high hits so it exceeds average value
+
+ // key4 triggers an eviction pass
+ auto key4 = make_key(4);
+ rc.put(&key4, buf.get(), 8 * 1024);
+
+ // e1 was spared on its first pass as a victim (16 -> 8), then taken on the
+ // second pass once the requeue budget ran out and put back by
+ // _requeue_victims() (8 -> 7). Without the spared-victim decay it would be 15.
+ CHECK(e1->hits == 7);
+}
+
+TEST_CASE("CLFUS unconditionally promotes resident entries to the tail on hits", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(64 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(4 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+ auto key3 = make_key(3);
+
+ REQUIRE(rc.put(&key1, buf.get(), 4 * 1024) == 1);
+ REQUIRE(rc.put(&key2, buf.get(), 4 * 1024) == 1);
+ REQUIRE(rc.put(&key3, buf.get(), 4 * 1024) == 1);
+
+ RamCacheCLFUSEntry *e1 = RamCacheCLFUSTestAccess::find_entry(rc, key1);
+ REQUIRE(e1 != nullptr);
+ // Initial order in _lru[0] has e1 at the head
+ CHECK(RamCacheCLFUSTestAccess::lru_head(rc) == e1);
+
+ // Inflate _average_value so e1's value is lower than average
+ RamCacheCLFUSTestAccess::set_average_value(rc, 1000.0);
+
+ // get() on key1 must unconditionally promote e1 to the tail of _lru[0]
+ Ptr<IOBufferData> got;
+ CHECK(rc.get(&key1, &got) == 1);
+ CHECK(RamCacheCLFUSTestAccess::lru_tail(rc) == e1);
+ CHECK(RamCacheCLFUSTestAccess::lru_head(rc) != e1);
+}
+
+TEST_CASE("CLFUS history entry is refreshed on get() hit", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(12 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(8 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+
+ REQUIRE(rc.put(&key1, buf.get(), 8 * 1024) == 1);
+ // key2 cannot fit in 12KB (8KB + 8KB > 12KB), routed to history (_lru[1])
+ CHECK(rc.put(&key2, buf.get(), 8 * 1024) == 0);
+
+ RamCacheCLFUSEntry *e2 = RamCacheCLFUSTestAccess::find_entry(rc, key2);
+ REQUIRE(e2 != nullptr);
+ REQUIRE(e2->flag_bits.lru == 1); // in history
+
+ uint64_t hits_before = e2->hits;
+ Ptr<IOBufferData> got;
Review Comment:
Fixed in 7c210ab41. The test now adds a second history entry (key3) and requires it to be the history tail before the lookup, so get(key2) must move e2 to the tail. Verified that removing the remove/enqueue in get() makes the test fail.
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -775,10 +799,18 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
if (!this->_max_bytes) {
return 0;
}
+ ink_hrtime now = ink_get_hrtime();
+ if (now - this->_last_decay_time > HRTIME_SECONDS(30)) {
+ if (this->_last_decay_time != 0) {
+ this->_decay_epoch();
+ }
+ this->_last_decay_time = now;
Review Comment:
Fixed in 420397d8f. _decay_epochs() now advances one epoch per whole elapsed 30s interval (carrying the partial remainder), and get() also checks the clock so hit-only traffic ages entries. 833424347 additionally decays _average_value by the full interval count rather than the 32-epoch cap.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366028198
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -775,10 +791,18 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
if (!this->_max_bytes) {
return 0;
}
+ ink_hrtime now = ink_get_hrtime();
+ if (now - this->_last_decay_time > HRTIME_SECONDS(30)) {
+ if (this->_last_decay_time != 0) {
+ this->_decay_epoch();
+ }
+ this->_last_decay_time = now;
+ }
Review Comment:
_decay_epoch() is now O(1)
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366044475
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -834,7 +858,7 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
}
Que(RamCacheCLFUSEntry, lru_link) victims;
RamCacheCLFUSEntry *victim = nullptr;
- int requeue_count = requeue_limit;
+ int requeue_count = std::min(static_cast<int64_t>(requeue_limit), this->_objects);
Review Comment:
It's now int64_t.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub) via github" <gi...@trafficserver.apache.org>.
jplevyak merged PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366151916
##########
src/iocore/cache/unit_tests/test_RamCacheCLFUS.cc:
##########
@@ -398,3 +456,295 @@ TEST_CASE("CLFUS value metric is a floating-point density", "[cache][ramcache][c
static_assert(v_hot > v_one, "CLFUS value metric does not increase with hits");
static_assert(v_small > v_large, "CLFUS value metric does not decrease with size");
}
+
+namespace
+{
+
+CryptoHash
+make_key(uint64_t id)
+{
+ CryptoHash key;
+ key.u32[0] = static_cast<uint32_t>(0xc0ffee00 + id);
+ key.u32[2] = static_cast<uint32_t>(0xdeadbeef + id);
+ key.u32[3] = static_cast<uint32_t>(0x12345678 + id);
+ return key;
+}
+
+} // namespace
+
+TEST_CASE("CLFUS decays hit count when sparing victims during eviction", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(32 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(8 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+ auto key3 = make_key(3);
+
+ REQUIRE(rc.put(&key1, buf.get(), 8 * 1024) == 1);
+ REQUIRE(rc.put(&key2, buf.get(), 8 * 1024) == 1);
+ REQUIRE(rc.put(&key3, buf.get(), 8 * 1024) == 1);
+
+ RamCacheCLFUSEntry *e1 = RamCacheCLFUSTestAccess::find_entry(rc, key1);
+ REQUIRE(e1 != nullptr);
+ e1->hits = 16; // Give key1 high hits so it exceeds average value
+
+ // key4 triggers an eviction pass
+ auto key4 = make_key(4);
+ rc.put(&key4, buf.get(), 8 * 1024);
+
+ // e1 was spared on its first pass as a victim (16 -> 8), then taken on the
+ // second pass once the requeue budget ran out and put back by
+ // _requeue_victims() (8 -> 7). Without the spared-victim decay it would be 15.
+ CHECK(e1->hits == 7);
+}
+
+TEST_CASE("CLFUS unconditionally promotes resident entries to the tail on hits", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(64 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(4 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+ auto key3 = make_key(3);
+
+ REQUIRE(rc.put(&key1, buf.get(), 4 * 1024) == 1);
+ REQUIRE(rc.put(&key2, buf.get(), 4 * 1024) == 1);
+ REQUIRE(rc.put(&key3, buf.get(), 4 * 1024) == 1);
+
+ RamCacheCLFUSEntry *e1 = RamCacheCLFUSTestAccess::find_entry(rc, key1);
+ REQUIRE(e1 != nullptr);
+ // Initial order in _lru[0] has e1 at the head
+ CHECK(RamCacheCLFUSTestAccess::lru_head(rc) == e1);
+
+ // Inflate _average_value so e1's value is lower than average
+ RamCacheCLFUSTestAccess::set_average_value(rc, 1000.0);
+
+ // get() on key1 must unconditionally promote e1 to the tail of _lru[0]
+ Ptr<IOBufferData> got;
+ CHECK(rc.get(&key1, &got) == 1);
+ CHECK(RamCacheCLFUSTestAccess::lru_tail(rc) == e1);
+ CHECK(RamCacheCLFUSTestAccess::lru_head(rc) != e1);
+}
+
+TEST_CASE("CLFUS history entry is refreshed on get() hit", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(12 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(8 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+
+ REQUIRE(rc.put(&key1, buf.get(), 8 * 1024) == 1);
+ // key2 cannot fit in 12KB (8KB + 8KB > 12KB), routed to history (_lru[1])
+ CHECK(rc.put(&key2, buf.get(), 8 * 1024) == 0);
+
+ RamCacheCLFUSEntry *e2 = RamCacheCLFUSTestAccess::find_entry(rc, key2);
+ REQUIRE(e2 != nullptr);
+ REQUIRE(e2->flag_bits.lru == 1); // in history
+
+ uint64_t hits_before = e2->hits;
+ Ptr<IOBufferData> got;
Review Comment:
The history-recency assertion cannot detect a regression: `e2` is the only history entry, so it is already the tail before `get()`, and the check still passes if the new remove/enqueue operations are deleted. Add another history entry and require `e2` not to be the tail before the lookup, then verify that the lookup moves it there.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366061256
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -775,10 +799,18 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
if (!this->_max_bytes) {
return 0;
}
+ ink_hrtime now = ink_get_hrtime();
+ if (now - this->_last_decay_time > HRTIME_SECONDS(30)) {
+ if (this->_last_decay_time != 0) {
+ this->_decay_epoch();
+ }
+ this->_last_decay_time = now;
Review Comment:
The clock advances only once after any gap over 30 seconds, so an untouched entry with 64 hits decays to 32 after 95 seconds instead of 8; hit-only traffic never advances it because `get()` only applies pending decay. Advance the clock in O(1) from both `get()` and `put()`, accounting for every elapsed interval and preserving the fractional remainder. Add timer-driven regressions for multi-interval gaps and hit-only traffic.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4367872238
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -880,13 +932,19 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
victim_value += cache_value(victim);
this->_tick();
if (!e) {
- goto Lhistory;
+ if (!seen_match) {
+ goto Lhistory;
+ }
+ if (this->_bytes + victim->size + size > this->_max_bytes && victim_value > cache_value_hits_size(1, size)) {
Review Comment:
The new seen-matched admission path can exceed `_max_bytes` because its fit checks omit entry metadata. With nonempty history, three 8 KiB residents in a 32 KiB cache, and a 7,424-byte copy-in candidate, this check lets admission proceed despite a more valuable victim; `Linsert` then restores the victim and raises `_bytes` to 33,024. Include the candidate's `entry_overhead` in admission fit checks and both entries' overhead in victim-restoration checks, and add a near-capacity regression.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366026947
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -243,6 +244,20 @@ RamCacheCLFUS::init(int64_t abytes, StripeSM *astripe)
}
}
+void
+RamCacheCLFUS::_decay_epoch()
+{
+ forl_LL(RamCacheCLFUSEntry, e, this->_lru[0])
+ {
+ e->hits >>= 1;
+ }
+ forl_LL(RamCacheCLFUSEntry, e, this->_lru[1])
+ {
+ e->hits >>= 1;
+ }
+ this->_average_value *= 0.5;
+}
Review Comment:
This is now N(1)
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366037348
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -943,7 +977,7 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
e = THREAD_ALLOC(ramCacheCLFUSEntryAllocator, this_ethread());
e->key = *key;
e->auxkey = auxkey;
- e->hits = 1;
+ e->hits = 2;
e->size = data->block_size();
e->flags = 0;
this->_bucket[i].push(e);
Review Comment:
The hits = 2 line only runs for history entries; it isn't shared with resident entries:
- Lhistory: (RamCacheCLFUS.cc ~line 991). This is the only place set to hits = 2. It always creates a history entry: it sets flag_bits.lru = 1, queues the entry on _lru[1] and increments _history.
- Linsert: (~line 959). New resident entries are created here, and they still start at hits = 1. The PR doesn't change this line.
Copilot does have half a point. A history entry that is later admitted keeps its hits count. So an object that went through history becomes resident with a higher count than one admitted directly. That is deliberate: it was requested again while in history, so it has earned the extra weight. The hits = 2 start also gives it more than one _tick() before it ages out of history. That retention is what the PR description means by "a multi-tick chance".
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366026947
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -243,6 +244,20 @@ RamCacheCLFUS::init(int64_t abytes, StripeSM *astripe)
}
}
+void
+RamCacheCLFUS::_decay_epoch()
+{
+ forl_LL(RamCacheCLFUSEntry, e, this->_lru[0])
+ {
+ e->hits >>= 1;
+ }
+ forl_LL(RamCacheCLFUSEntry, e, this->_lru[1])
+ {
+ e->hits >>= 1;
+ }
+ this->_average_value *= 0.5;
+}
Review Comment:
This is now O(1)
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4366043639
##########
src/iocore/cache/unit_tests/test_RamCacheCLFUS.cc:
##########
@@ -398,3 +428,183 @@ TEST_CASE("CLFUS value metric is a floating-point density", "[cache][ramcache][c
static_assert(v_hot > v_one, "CLFUS value metric does not increase with hits");
static_assert(v_small > v_large, "CLFUS value metric does not decrease with size");
}
+
+namespace
+{
+
+CryptoHash
+make_key(uint64_t id)
+{
+ CryptoHash key;
+ key.u64[0] = 0xc0ffee00 + id;
+ key.u64[1] = 0xdeadbeef + id;
+ key.u32[3] = static_cast<uint32_t>(0x12345678 + id);
Review Comment:
It now writes only through u32[].
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on code in PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#discussion_r4367862510
##########
src/iocore/cache/unit_tests/test_RamCacheCLFUS.cc:
##########
@@ -398,3 +456,295 @@ TEST_CASE("CLFUS value metric is a floating-point density", "[cache][ramcache][c
static_assert(v_hot > v_one, "CLFUS value metric does not increase with hits");
static_assert(v_small > v_large, "CLFUS value metric does not decrease with size");
}
+
+namespace
+{
+
+CryptoHash
+make_key(uint64_t id)
+{
+ CryptoHash key;
+ key.u32[0] = static_cast<uint32_t>(0xc0ffee00 + id);
+ key.u32[2] = static_cast<uint32_t>(0xdeadbeef + id);
+ key.u32[3] = static_cast<uint32_t>(0x12345678 + id);
+ return key;
+}
+
+} // namespace
+
+TEST_CASE("CLFUS decays hit count when sparing victims during eviction", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(32 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(8 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+ auto key3 = make_key(3);
+
+ REQUIRE(rc.put(&key1, buf.get(), 8 * 1024) == 1);
+ REQUIRE(rc.put(&key2, buf.get(), 8 * 1024) == 1);
+ REQUIRE(rc.put(&key3, buf.get(), 8 * 1024) == 1);
+
+ RamCacheCLFUSEntry *e1 = RamCacheCLFUSTestAccess::find_entry(rc, key1);
+ REQUIRE(e1 != nullptr);
+ e1->hits = 16; // Give key1 high hits so it exceeds average value
+
+ // key4 triggers an eviction pass
+ auto key4 = make_key(4);
+ rc.put(&key4, buf.get(), 8 * 1024);
+
+ // e1 was spared on its first pass as a victim (16 -> 8), then taken on the
+ // second pass once the requeue budget ran out and put back by
+ // _requeue_victims() (8 -> 7). Without the spared-victim decay it would be 15.
+ CHECK(e1->hits == 7);
+}
+
+TEST_CASE("CLFUS unconditionally promotes resident entries to the tail on hits", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(64 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(4 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+ auto key3 = make_key(3);
+
+ REQUIRE(rc.put(&key1, buf.get(), 4 * 1024) == 1);
+ REQUIRE(rc.put(&key2, buf.get(), 4 * 1024) == 1);
+ REQUIRE(rc.put(&key3, buf.get(), 4 * 1024) == 1);
+
+ RamCacheCLFUSEntry *e1 = RamCacheCLFUSTestAccess::find_entry(rc, key1);
+ REQUIRE(e1 != nullptr);
+ // Initial order in _lru[0] has e1 at the head
+ CHECK(RamCacheCLFUSTestAccess::lru_head(rc) == e1);
+
+ // Inflate _average_value so e1's value is lower than average
+ RamCacheCLFUSTestAccess::set_average_value(rc, 1000.0);
+
+ // get() on key1 must unconditionally promote e1 to the tail of _lru[0]
+ Ptr<IOBufferData> got;
+ CHECK(rc.get(&key1, &got) == 1);
+ CHECK(RamCacheCLFUSTestAccess::lru_tail(rc) == e1);
+ CHECK(RamCacheCLFUSTestAccess::lru_head(rc) != e1);
+}
+
+TEST_CASE("CLFUS history entry is refreshed on get() hit", "[cache][ramcache][clfus]")
+{
+ CacheDisk disk;
+ init_disk(disk);
+ StripeSM stripe{&disk, 10, 0};
+ CacheVol cache_vol;
+ wire_stripe(stripe, cache_vol);
+
+ cache_config_ram_cache_compress = CACHE_COMPRESSION_NONE;
+ cache_config_ram_cache_use_seen_filter = 0;
+
+ RamCacheCLFUS rc;
+ rc.init(12 * 1024, &stripe);
+
+ auto buf = make_buffer(compressible_bytes(8 * 1024));
+ auto key1 = make_key(1);
+ auto key2 = make_key(2);
+
+ REQUIRE(rc.put(&key1, buf.get(), 8 * 1024) == 1);
+ // key2 cannot fit in 12KB (8KB + 8KB > 12KB), routed to history (_lru[1])
+ CHECK(rc.put(&key2, buf.get(), 8 * 1024) == 0);
+
+ RamCacheCLFUSEntry *e2 = RamCacheCLFUSTestAccess::find_entry(rc, key2);
+ REQUIRE(e2 != nullptr);
+ REQUIRE(e2->flag_bits.lru == 1); // in history
+
+ uint64_t hits_before = e2->hits;
+ Ptr<IOBufferData> got;
Review Comment:
Fixed in 7c210ab41. The test now adds a second history entry (key3) and requires it to be the history tail before the lookup, so get(key2) must move e2 to the tail. Verified that removing the remove/enqueue in get() makes the test fail.
##########
src/iocore/cache/RamCacheCLFUS.cc:
##########
@@ -775,10 +799,18 @@ RamCacheCLFUS::put(CryptoHash *key, IOBufferData *data, uint32_t len, bool copy,
if (!this->_max_bytes) {
return 0;
}
+ ink_hrtime now = ink_get_hrtime();
+ if (now - this->_last_decay_time > HRTIME_SECONDS(30)) {
+ if (this->_last_decay_time != 0) {
+ this->_decay_epoch();
+ }
+ this->_last_decay_time = now;
Review Comment:
Fixed in 420397d8f. _decay_epochs() now advances one epoch per whole elapsed 30s interval (carrying the partial remainder), and get() also checks the clock so hit-only traffic ages entries. 833424347 additionally decays _average_value by the full interval count rather than the 32-epoch cap.
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Fix CLFUS RAM cache frequency decay and admission pathologies [trafficserver]
Posted by "jplevyak (via GitHub)" <gi...@apache.org>.
jplevyak commented on PR #13893:
URL: https://github.com/apache/trafficserver/pull/13893#issuecomment-6388028898
<!-- address-comments-summary -->
## Address-comments run — 2026-10-24
<table>
<tr><th>Comment</th><th>File / Topic</th><th>Label</th><th>Action / Reason</th></tr>
<tr><td>4367872238</td><td>Admission fit checks omit entry metadata, letting <code>_bytes</code> exceed <code>_max_bytes</code></td><td>FIX</td><td>Fixed in c25844539: candidate and victim <code>entry_overhead</code> included in all fit and restore checks in <code>put()</code>. Added near-capacity regression test reproducing the reported 33024 > 32768 overshoot.</td></tr>
</table>
--
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: github-unsubscribe@trafficserver.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org