Sieve is simpler than LRU

Re:Sieve is simpler than LRU by NovaX on Wednesday January 03, 2024 @05:28PM (#38860731)

Unfortunately most researchers do not consider attack vectors and often consider inputs that do not meet their preferred examples to be invalid. If a hostile user is able to pollute the cache so that it significantly degrades then that exploit becomes an easy denial of service attack. It is somewhat out of scope, but means that more general robust algorithms are needed because most users won't fine tune a system for a bespoke algorithm and instead take an off-the-shelf solution. I am therefore not a big fan of these minor tweaks to historical algorithms by making a one or two line change and therefore only slightly modifying what it is good or bad at. I try for more holistic solutions, even if a small percent worse in some cases, and infuse randomness to avoid deterministic exploits. To me that's more worthwhile and a big factor in whether it is a research toy or production-grade engineering.

[ Parent | on HN ]

Re:Sieve is simpler than LRU by 1a1a11a on Wednesday January 03, 2024 @06:57PM (#38861432)

I agree with you; any non-random algorithm has the problem

[ Parent | on HN ]

Re:Sieve is simpler than LRU by kazinator on Wednesday January 03, 2024 @08:59PM (#38862205)

Well, any pseudo-random algorithm. If we avoid pseudo-random behaviors, we can provide certain guarantees that no pattern of access can get around, such as that if an item is freshly inserted into the cache, then it will stay there for (at least) the next N cache misses, for some specific N; that those N misses will evict something else.

If we consider LRU, no contrived pattern of access on LRU will cause it to evict some item Y if there is an item Z present which was less recently touched than Y.

[ Parent | on HN ]

Re:Sieve is simpler than LRU by NovaX on Thursday January 04, 2024 @12:25AM (#38863383)

Those guarantees are also what makes the algorithm exploitable and inflexible to handle unknown or adversary workloads. Your LRU example suffers in scan / loop / zigzag patterns, which the author's policies do poorly at as well. They target CDNs workloads where that can be ignored there due to its scale, but that is not a generalizable assumption for other workloads where it more common like databases, search, and analytics.

If the algorithm is known and accepts user facing requests then it becomes a target. A client can use the network speed of a dialup modem to bring down a modern server simply by crafting a request pattern to exploit hash flooding. This is why you generally want some injected noise, adaptivity, and use an algorithm that offers robustly good hit rates. A specialized policy that is superior in a narrow set of workload is still very useful when targeted at an expensive problem, but that's a design assumption that few can reasonably make.

[ Parent | on HN ]

Re:Sieve is simpler than LRU by kazinator on Thursday January 04, 2024 @12:10PM (#38869515)

Hash attacks work because hash tables are pseudo random algorithms, whose worst case performance is linear, and whose average case constant time performance depends on keys being distributed evenly, which depends on luck. A different kind of container, like something with a worst case that is logarithmic and doesn't depend on luck is immune to that kind of attack.

It is only these kinds of pseudo-randomized algorithms that have hidden degenerate cases that need to be randomized for protection.

More generally, software that has some hidden severe problems for certain inputs, such that the degenerate choice of inputs depends on incidental factors, benefits from having those incidental factors perturbed randomly (like a form of seeding) so that attackers cannot identify those inputs or use the same ones consistently.

ASLR is like this. A bug-free program (or at least one free of memory errors) does not benefit from address space layout randomization, only one that has bugs. The successful exploitation of those bugs for gaining unauthorized access depends on incidental pseudo-random factors like in what layout the misused objects are allocated.

I believe there's no need for a cache to have a behavior whereby a sequence of accesses that shows good locality its able to get a frequently accessed item to be given poor cache residency, while another item that is just as frequently accessed is given good residency. On the other hand kind of inputs that trigger poor hit rates in a cache are hardly random. To trigger a poor hit rate in almost any cache algorithm whatsoever, all you have to do is access a sequence of items in which nothing appears twice. Only an algorithm with prefetch that happens to predict that sequence will do well or at least somewhat well.

[ Parent | on HN ]