Hacker News Reader

Comment by taeric | Hacker News Reader

I don't necessarily understand why caching wouldn't naturally move to the same strategies as garbage collection? Generational collectors, in particular.

I remember we had a CACHE for credentials in a big service at a previous gig, and we found that periodically we would get our cache wiped clean. Turned out, a lot of our clients were working with a third party system that would periodically log into each of the clients' accounts to check on details. To us, that was every credential getting hit in a near linear scan every hour or so. Which... was perfectly set to kill anyone that was using LRU caching.

Outside of randomness to hopefully retain enough of the items in the cache that are likely to get hit again soon, it seemed natural to have a set of generations for items that have only been seen once, and then another generation for things that have been more active. Which, sounds exactly like a lot of garbage collection schemes to my naive ear.

View on HN

LRU is a fairly intuitive and simple strategy but a rather lousy performing one. If you look at the various caches in modern CPU such as data and branch target caches they have been moving away from (P)LRU as replacement strategy. The most modern one I'm aware of is DRRIP [1] in the Arm Cortex-X3 and derived V2 chips, as shown here [2] post [3]. And those are implemented in hardware, in software you are even more flexible.

[1] https://en.wikipedia.org/wiki/Cache_replacement_policies#Dyn...

[2] https://i0.wp.com/chipsandcheese.com/wp-content/uploads/2023...

[3] https://chipsandcheese.com/2023/09/11/hot-chips-2023-arms-ne...

> it seemed natural to have a set of generations for items that have only been seen once, and then another generation for things that have been more active

Have you looked at ARC? It sounds similar - it is a cache split between LRU and MFU areas, where the split point changes dynamically depending on the workload. https://www.youtube.com/watch?v=F8sZRBdmqc0 is a fun watch on the topic.

Caching is bounded, GC is potentially boundless. Caching is all about deciding what to evict.

Right, I know there are differences. Easiest consideration there is that caches are probably never walking to root pointers. They can choose to work on individual entries with no regard to the rest.

My point is not any different than how you design your kitchen/house. Things that you use all of the time, you have up front. The more often you use them, the closer they are to where they are used. Same for general storage.

Why would cache not follow the same pattern? In each "bin" you can go with LRU or Sieve, but having multiple bins makes a ton of sense. And it looks a lot like the way that GC works.

Cache design has a lot of different constraints and you can exploit those constraints to build more efficient systems. And yes, people in the space are aware of GC research and leverage design concepts from there where appropriate.

Think of sieve as one component of a full caching systems. Many caching systems will combine primitives to have a “newly encountered” and “recently expired” generation where they’ll use a probabilistic filter or something similarly compact to determine whether they’ve seen something enough to spend resources caching it.

There’s memory usage concerns (frequently you want a hard upper bound on memory consumption), speed/latencies (these systems are handling many thousands of requests per second and need to have near 0 latency), and fit as much as possible into the memory constraints (eg using probabilistic filters for admittance).

SIEVE can be integrated into things like W-TinyLfu / s3fifo to replace certain individual components (I would read their papers - they’re fairly approachable and discuss the full design).

GC is intrinsically bounded by the amount of memory available. GC is also about deciding what to evict albeit the heuristic used to determine that is based on current use rather than frequency of use.

dotnet runtime GC is interesting for caching, because it has multiple generations for the GC. Each time there is a GC the survivors are moved to the next generation. Moving most used items to the next generation and looking in the later generations first when resolving could be pretty quick.

Reply on news.ycombinator.com