Hacker News Reader

> This is for no good reason other than just luck.

> When the Hand finds a victim we just replace the Hand slot with the new item, and mark it visited

That would cause newly inserted items to take at least N (size of the cache) rounds to be evicted. Evicting cache entries early is extremely important for performance. Their algorithm means new items will have a higher chance of being evicted, and that is by design, not random chance.

Here's the paper: https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf

I was curious too so I took a look. I think this is the relevant bit:

Recent work [94] shows that “lazy promotion” and “quick demotion” are two important properties of efficient cache eviction algorithms.

[...]

Quick demotion removes most objects quickly after they are inserted. Many previous works have discussed this idea in the context of evicting pages from a scan [16,60,67,70,75,77]. Recent work also shows that not only storage workloads but web cache workloads also benefit from quick demotion [94] because object popularity follows a power-law distribution, and many objects are unpopular.

[...]

[94] Juncheng Yang, Ziyue Qiu, Yazhuo Zhang, Yao Yue, and K. V. Rashmi. FIFO can be better than LRU: the power of lazy promotion and quick demotion. In The 19th Workshop on Hot Topics in Operating Systems (HotOS 23), 2023.

I read that before.

Caching is predicated on locality. We put things into a cache based on the idea that something accessed once is likely to be used again, due to locality.

Lazy promotion is useful in a situation in which we don't trust that the access pattern exhibits locality, nor not fully. Perhaps it exhibits locality for some data, but is widely scattered for others.

For instance, an algorithm is working with numerous local variables in a loop (good locality) but the loop is also stepping through a very large set of data in memory, much larger than the cache. Moreover, items in this set are visited only once (poor/nonexistent locality).

If we regard accesses with a bit of suspicion ("this might not have good locality") we can avoid those latter items from overstaying in the cache. Items in the cache that are not going to be touched again effectively shrink the cache. Like if at any given time about half our cache has such items, the cache is effectively halved.

With a deterministic, fixed distance between the Hand pointer and the Insert point, which we can tune, we could empirically adjust for this. For instance we could have it so that, consistently, every new item that is not visited within 4 subsequent cache misses will be evicted.

If we had a magic oracle, we would not use LRU or any of these other approaches. We would ask the oracle questions "Great Oracle, given these items in the cache, and this new one which is not in the cache, which one(s) will not be seen again, or else which one(s) will be seen again farthest into the future?" That's really what we want to know, but since oracles don't exist, we use heuristics, like the idea that the longer an item goes without being accessed, the more likely it is that it's a never-again-accessed item.

Great point! We tried the oracle (Belady MIN) and found that the oracle often does not admit new objects (<20% chance admitting new objects) in most traces. That's why we need to evict new objects quickly

I clearly articulated in my comment that this is one choice we could make for the distance between the Insert point and the Hand pointer. That distance is a parameter whose space can be experimentally tested.

Without my proposal, there is no control over the parameter: the distance is an average, and so about half the cache size. When Hand is on the far right, a new item inserted at that time will stay in the cache long. When the Hand is far left, it may get evicted almost immediately.

The only thing important for performance is a good hit ratio, however it is achieved. An evicted item is one that cannot be hit. Early eviction is not ipso facto good for performance; only with regard to some access patterns where early eviction of the right items improves retention of other items that yield good hits.

Early eviction is fine for performance if the average eviction you get is good enough that any improvement in eviction you get from a more optimal choice of distance is outweighed by the effort in picking the insertion point.

You really need to measure, because this will depend on your workload, how fast your implementation is relative to the cost of a miss, what the ratio of "likely to never be requested again" to potentially long-lived objects are, etc.

The roving Insert point is harder to implement, due to the reversed case:

  [ ][ ][I][ ][ ][H][ ][ ]
         ^^^^^^^^
                 `these items move right

  [ ][ ][H][ ][I][ ][ ][ ]
   ^^^^        ^^^^^^^  ^- this item moves to the top (left most slot)
    |                 `--- these items move right
     ` these items move right

If we think about doing it in hardware, like for each set of a set-associative L1 or L2 cache, it's a hindrance.

I totally agree with you, this is not designed for hardware... and as others mentioned RRIP might be better for set-associative caches

With respect to my other reply mentioning a ring instead of a linked list, here's a quick and dirty Ruby port because I couldn't resist that uses a ring with a single dummy head node to simplify the logic:

https://gist.github.com/vidarh/b72615c16673cb38630cab5148190...

You'll note it avoids a bunch of conditionals in add_to_head, remove_node and evict because the wraparound happens automatically and the next/prev pointers are never nil/None

I've not verified it matches the behaviour of yours exactly other than adding a handful of extra access calls and comparing the state.

If you're not familiar with Ruby, the one particularly dirty trick I'm using is that in Ruby you can define methods directly on a specific object, so by defining the method "@head.visited" to always return true, the eviction will just try to set it to false and move straight over it every run, cutting a conditional. You could do a ring without a dummy @head to but it makes the insertion/deletion logic more annoying.

it looks like the ring is implemented using a linked list?

Yes, I wanted to change as little as possible to illustrate why you almost always want to close your lists into a ring when using a linked list ;)

It simplifies a lot of algorithms to be able to guarantee no null pointers. It's a very old trick. You trade a lot of conditionals and a risk of null pointers dereference for a smaller risk of non-termination (failure to check for a null pointer is always bad; failure to check for the end is only a problem if the end of the list is actually your termination condition).

You could do a ring with an array and modulus too, but then you end up copying the whole thing to open up slots to insert to maintain the property of your insertion point being separate from the hand.

That may or may not do worse, but likely to depend on cache size and implementation language.

What you'd almost certainly want in a production implementation anyway would in any case be to do away with constantly allocating nodes and just move them to a free list and reuse to avoid dynamic allocation overhead and garbage collection.

I added a second, singly-linked ring version to the gist I linked above. It doesn't save much, as to be able to unlink the hand you need to keep a pointer to the node adjacent to the hand (I changed "direction" in the naming because it feels weird to have a singly linked list with just "prev" pointers, but that doesn't matter), but it does mean a pointer less for each Node and from experience a lot of people struggle to get the pointer updates right for doubly linked lists, and that is a lot harder to get wrong when singly linked...

Got it. Make sense, I like the reason why you want to make it circular. :)

I'd just have implemented it as a ring instead of a list and insertion at any point is identical, but my point was exactly that unless your workload specifically fits insert at the "hand" better than the current algorithm, you will need to account for the cost of whatever complexity you add in order to move the insert point.

> If we think about doing it in hardware, like for each set of a set-associative L1 or L2 cache, it's a hindrance.

I don't see why I would think about doing it in hardware.

> This is for no good reason other than just luck.

There is a good reason. And that reason is that many recently accessed items survived. Then it's only prudent to devote more of the cache for surviving items than for fresh ones in such circumstances.

This continues until the cache is completely filled with recent survivors which moves the hand back to tail and oldest previous survivors get reevaluated for eviction. This, I imagine happens periodically in practice and often enough for the algorithm to perform well.

The problem is that the more the cache is filled, and the closer the Hand gets to the head of the queue, the closer are newly inserted items to being evicted.

There doesn't seem to be any good reason for this over putting the newly inserted items at a consistent distance away from the Hand, so they are a predictable, controllable number of steps away from the threat of eviction, and so that the Hand movement is just a cyclic treadmill with no spot of the circular buffer being arbitrarily special.

If randomization of the distance is beneficial, let that be explicit! Feed a stream of pseudo-random integers to the cache which is used to select the distance between the Hand and the Insert point. That could be still be nicely controlled as a jitter within a minimum and maximum range.

> ... the closer are newly inserted items to being evicted.

That's a good thing because newly inserted items didn't prove yet that they are worth keeping.

They have less time to proove themselves but if they prove themselves they can have a long lifetime because they will remain when the hand loops back to tail.

End of cache is filled with items of proven utility. New ones are unproven. Shrinking distance between head and hand reflect accumulation of proven items which leaves less space for unproven ones. Which is good. Eventually (when the space for fresh ones ends) you want to reconsider the proven ones again and this is achieved by moving hand back from head to tail.

It might be unfair to new items comming in at the times when there are a lot of proven ones accumulated but it is a good strategy from the point of view of the whole process. Good solutions are not necessarily fair.

> If randomization of the distance is beneficial, let that be explicit!

But it's better than random. It's adaptive to how many of the items already stored were visited recently.

> That's a good thing because newly inserted items didn't prove yet that they are worth keeping.

It isn't good that the probation is random, depending on how far left the Hand is at the time the item is inserted. Or else if it is good for that distance to be randomized, it would be good to make that random choice explicit.

> It's adaptive to how many of the items already stored were visited recently.

It's not adaptive whatsoever. The Hand moves left when there are cache misses, in order to find items to evict, and then wraps back to the rightmost slot. The current position of the Hand bears no relation to a newly observed cache miss, yet affects its retention.

You are probably thinking of block I/O or CPU cache workloads where scans cause the miss ratio to increase. This algorithm targets web workloads where scans are not common, and the miss ratio does not change abruptly.

Yes, SIEVE does not adapt to miss ratio, but it adapts to the inherent popularity in the workloads. You can see the evidence in the results.

> The Hand moves left when there are cache misses

It moves only if there were cache hits. If there are only cache misses it stays at the tail so the whole cache is dedicated for new unproven entries. Once there are some cache hits then they are retained and the area shrinks. It's not random. It reacts to whether it managed to catch something valuable or not.

> The current position of the Hand bears no relation to a newly observed cache miss, yet affects its retention.

Yes, but it is related to recent cache hits. It sacrifices chances of new items getting retained in exchange for retaining items that were recently proven to be worth keeping.

When there is a cache hit, the accessed item is flipped to visited state (if necessary). No eviction takes place and so the Hand stays where it is.

The Hand moves when it has to scan over visited items in search of an unvisited item to evict, when there is a cache miss. The scanned items are flipped to unvisited.

Exactly. And if there are no visited items, evictions happen at hand and hand is at tail and doesn't move. Full cache is dedicated to finding items that will repeat. They are getting the best chance they can.

Once some visited items arrive they are retained and the fraction of cache dedicated to new ones shrinks, so they have less time to get visited again and avoid eviction. But this happens for the benefit of retained items. If they were already seen second time there's a chance they'll occur for the third time and more. They are worth more than fresh ones. It's unfair to new items but beneficial for the cache as a whole.

When many different items are revisited hand moves and eventually reaches the head. Then the cache is full. So it's moved back to tail to see if we can evict some of the old stuff because maybe they weren't re-visted since last time we considered them for eviction.

Can you see it's not random and that it's actually useful?

The algorithm is arbitrarily unfair towards new items based on its state, which has no relation to those items.

It's like being rude to customers whenever the day of year is divisible by five. Sure it's not mathematically even pseudo-random, but it's unrelated to the customers. It's effectively random to them.

It's rude to new customers when restaurant is already full of paying customers.

It's unrelated to the new customers and in that sense unfair to them. But it's related to how successful is the restaurant at the moment.

Fairness is not the goal. Success of the restaurant is.

Objects near the tail are the people who occupy the table but keep ordering new dishes. Objects near the head are people who ordered just one thing and now they are politely asked to leave so new, potentially more generous customers can be accomodated.

If restaurant is more full, new customers have less time to justify their continued occupation of the table by ordering again, but it's fine because it allowes more of the older customers with repeated orders to be served again and again.

There is potential problem with the algorithm if there's very little space left for new items so they are never retained so hand never moves to head. Probaby you could refine the algorithm by moving hand to tail when it gets closer to head than some fixed value, finetuned to the production load. Or just occasionally move hand to tail every n inputs on average (also finetuned).

You're still on a mistaken program whereby because items are inserted at the leftmost slot of the array, that slot is the head. And so the rightmost slot is the tail.

This is not so. The tail of the buffer is the Hand pointer, and it behaves like a circular buffer tail.

This is at odds with the fixed head.

Your full versus empty analysis is flawed, because once the cache warms up, which takes only one cycle, it stays permanently full. At each subsequent cache miss, one item is evicted and one item is inserted. One in, one out. There is no tide-like ebb and flow between empty and full. That is just rhetoric which is not anchored to anything that is real in the algorithm.

Items that are booted out are identified at the circular buffer tail. But, oddly, the new ones are inserted at the physical top of the circular buffer's linear implementation which bears no relation to the circularity.

In a circular buffer, the linear indices have no special meaning.

So it is like a code smell, but for algorithms.

You can look at this cache as circular buffer. But in this interpretation there is not one pointer into that buffer, but two. Insertion pointer and eviction pointer. Their location in memory is irrelevant. What matters is that eviction pointer moves while insertion point doesn't.

Those two pointers split the circular buffer inti two parts. The part after insertion pointer but before eviction pointer you could call staging. It's a space where items that have not yet been considered for eviction are held. When an item gets evicted items in this staging space are moved one spot towards eviction pointer so that under insertion pointer a free space appears which is filled by the newly inserted item.

As items are considered for eviction and rejected (because they had visited status) eviction pointer moves closer and closer to insertion pointer shrinking the staging area. So the new items have less and less time to acquire visited status before the eviction pointer reaches them. This is what's unfair. That the chances of item getting visited and spared from eviction is lower for the items that arrive when staging is small.

This is somewhat alleviated by the fact that after eviction pointer in its motion reaches stationary insertion pointer it passes it so the staging area grows from almost nothing to the full size of the circular buffer. The items which had a bad luck to arrive when the staging is small, if they are repeated, have a later chance to arrive again when staging is large and then have a lot of time to earn visted status and avoid eviction the next time they are considered.

What you are advocating for is that insertion pointer should move too, either to keep fixed distance from the eviction pointer or to keep explicitly randomized distance. Those are of course valid choices when you design your cache algorithm. But the author(s) of this one went with another method. They reduce the distance between insertion and eviction pointer by one only after item is considered for eviction but rejected (because it got visited status since the time it was inserted or considered for eviction the previous time). Once the distance between insertion and eviction point reaches small enough value (for example zero) they increase the distance to be maximum possible (to the size of the circular buffer).

You don't see a reason for this choice and I'm telling you that the reason is that the second part of the buffer (the part starting at eviction point and ending at insertion point) is devoted exclusively to items that since their insertion acquired visited status at least once thus prooving they are worth keeping in cache.

So it might be a good strategy to dedicate larger part of the buffer to those items in times when they are abundant in the input rather than fixed part or random part as you propose.

To address your concern that new items are inserted at the physical top of circular buffer implementation ... It doesn't matter. Insertion pointer could be placed at any spot in the buffer. You can randomize its initial (and ultimate since its not moving) placement and it would change nothing in the performance of the algorithm (after the buffer is initially filled). This cache could be implemented as circular linked list with two pointers into it.

Do you understand all that? Because I'm not sure if I can explain it any more clearly.

> You can look at this cache as circular buffer.

After that, you cannot "unsee" it any more.

> items that since their insertion acquired visited status at least once

> the second part of the buffer (the part starting at eviction point and ending at insertion point) is devoted exclusively to items that since their insertion acquired visited status at least once thus prooving they are worth keeping in cache.

Items can acquire visited status anywhere in the cache, to the left or right of the Hand pointer. There is no special area.

The "reaper" which ages visited items to unvisited, and which collects aged items, moves in a circle.

If an item is inserted while the Hand is in the leftmost position, it will be evicted immediately when another not-present item is accessed. If an item is inserted while the Hand is farthest away at the rightmost slot, and not visited again, it can stay in the cache for a number of miss cycles, until the Hand goes to the top again.

That variability, as such, may be useful and good.

One problem is that it's not actually random, and it's not even a good form of pseudo-random.

I posit that input sequences exist in which two items of equal importance, A and B, are consistently treated unequally, with B enjoying much longer retention in the cache than A.

Moreover, the algorithm doesn't allow for experimentation with randomly varying the trim distance between two arbitrary values. Like say random between 4 and 8 slots in a 64 slot cache. That's a disadvantage, because for some given patterns, it prevents the optimal parameters from being discoverable.

Algorithms like LRU don't have the above weird property. While their hit rate may be good or bad depending on the locality of patterns, you cannot construe a sequence of access patterns under LRU in which two items A and B appear equally frequently, yet enjoy significantly different retention times.

> Items can acquire visited status anywhere in the cache, to the left or right of the Hand pointer. There is no special area.

They can lose visited status only if they are between head and hand pointer. That's the special area. There's no way for item to loose their visited status if they are between hand and tail until the hand reaches head. In this sense area between hand and tail is privileged.

> If an item is inserted while the Hand is in the leftmost position, it will be evicted immediately when another not-present item is accessed.

You see the cost of small head-hand area but you don't see the benefit of large hand-tail area.

> Moreover, the algorithm doesn't allow for experimentation with randomly varying the trim distance between two arbitrary values.

In its basic form it doesn't. However I suggested that you might tweak how far from the head, the hand loops back to tail. It doesn't have to happen at exactly zero distance if you don't want to ever disadvantage new entries too much.

> .. construe a sequence of access patterns under LRU in which two items A and B appear equally frequently, yet enjoy significantly different retention times.

I see no cost of that. Cache doesn't need to be fair. It only needs to be successful. If it can serve item A from cache for 100% of the time and item B 0% of the time despite same patterns its still better than if it serves each of them 25% of time from cache.

> its still better than

* is not worse than

Yeah... It's hard not to read "luck" as, "there's something I don't understand". Luck doesn't really happen with caching.

It's not hard to see that in this algorithm when a new cache miss is handled to insert an item, the current position of the Hand bears no relation to that new item.

Sure, we can contrive access sequences where that is not random, because the whole thing is actually deterministic. That's not what I mean by random; I mean not expected to be related under realistic conditions where the inputs aren't contrived.

A good cache algorithm should be immune against contrived input sequences. With this one, we could devise a degenerate access sequence such that a particular item is always placed just ahead of the Hand, such that it is victimized in the next access cycle. Yet another particular item is given the maximum leeway. And that could be in spite of both items appearing equally often and deserving the same treatment.

Do you have an example of a non-random algorithm that does not have adversarial workloads?

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.

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

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.

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.

> How it should work is that new items should be added at a fixed distance from the Hand pointer.

This would help with the implementation with a circular buffer. But for now, let's decouple the algorithm from the implementation.

> we can make Insert and Hand be the same slot

This is just CLOCK algorithm. It is easy to implement with a circular buffer. But the change we made deliberately improves the miss ratio significantly.

Wouldn't a hand that follows the head at an offset of ca 10% of the ring buffer size be mimicking the S3-FIFO quick demotion threshold and likely reap the same kind of benefits?

Yes if you add a ghost queue. :)

In reference to a key aspect of ARC's design.

> The problem is that items that are inserted at the head of the queue during a moment when the Hand is in a low position (close to the head, toward the left) are closer to being doomed than items added when the Hand is in the rightmost position.

That could possibly reveal interesting security-related properties, i.e. maybe future vulnerabilities.

Whether that is "how it should work" and whether your proposed fix is better or worse for a given workflow depends on a lot of factors.

You're right that putting the insert in a fixed location will mean the time a new element has before it must either be visited or get evicted will vary quite a bit, but it's not obvious that it will always be better to "fix" that.

E.g. consider the typical "generation gap" where the set of objects are bimodal and either likely to be frequently used or be garbage right away. Depending on the odds that a new object falls in either category, it might be better for the insert to be closer to the hand than further away (or it might be opposite). That is, you might want the chance for a new entry to survive to be fairly low.

If the best bet is to have the new entry on average an inconvenient distance from the hand, it might well be the variability is better than either moving the insert to the hand or a more convoluted scheme to keep them at a fixed distance.

I agree it'd be more predictable and/or easier to reason about if it's a fixed distance, and if the fill size of the cache is the right distance then certainly inserting it at the hand works great.

But really, I think you should measure for your specific workflow. It'd be interesting to see this option and some other ways of separating them tested, though.

Another thing I think would be interesting to test is whether (it wasn't an accident that I hinted at generational garbage collection above) it'd be worth keeping a second pointer that you move past objects that have survived "long enough" in the cache, and most of the time move the hand back to that pointer instead of "all the way" so you don't spend as much time iterating over objects that won't get evicted anyway. If the number of cache entries is small, probably not worth it, but for a large cache with a decently large proportion of persistently hot objects, maybe (but then you could just also outright move objects to a second cache, and that might well be simpler; again something to measure on actual workloads).

I'm assuming this isn't anything new to people who follow the field more closely in any case.

"Your specific workflow" is a myth. A cache designed for "your specific workflow" will be subject to completely unforseen workflows when put into production.

While that's something to keep in mind, that's a reason for measuring tue effects and choosing accordingly, not a reason not to.

Otherwise on that basis you shouldn't put a cache in at all as there will be workflows where the hit rate is so low the cache has a negative effect, however unlikely.

If you don't know e.g. the rough performance profile of your requests, and the typical distribution of them, you likely have far bigger things you should be worrying about.

I wonder about allowing the hand to 1-D random walk left or right when examining the visited bit for evicting an item.