5 ms·
Here is a flaw in the algorithm. The Hand pointer is essentially a roving pointer around a circular buffer. Elements that it passes over can live for another c
by kazinator 3y ago
Here is a flaw in the algorithm. The Hand pointer is essentially a roving pointer around a circular buffer. Elements that it passes over can live for another cycle (at least; more if they get visited).
But there is a bias in the algorithm. Arbitrarly, the circle is broken into a linear queue, and the not present items which are accessed are arbitrarily inserted into the head of the queue (leftmost slot).
This does not compute: a circular roving pointer sweeping through a queue? What?
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. This is for no good reason other than just luck.
How it should work is that new items should be added at a fixed distance from the Hand pointer. In other words, an Insert point moves around the circular buffer in lock step with the Hand. When the Hand obliterates an evicted item, items between that item and the Insert point will shuffle over, and the new item goes to the Insert point. Next time the Hand moves, the Insert point will move with it in the same direction.
And now here is an elegant thing: we can make Insert and Hand be the same slot! When the Hand finds a victim we just replace the Hand slot with the new item, and mark it visited. Don't move any items around. On the next miss, the Hand will hop away from that item and mark it unvisited, and that's it. That item can then live until the next visit of the Hand, if it isn't touched again. This is just a FIFO with protection for the visited, essentially.
The distance between Insert and Hand is a parameter; the algorithm can be measured at various values of that parameter.
- HackerThemAll 3y ago> 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.
- scotty79 3y ago> 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.
- kazinator 3y agoThe 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.
- scotty79 3y ago> ... 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.
- kazinator 3y ago> 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.
- ricardobeat 3y ago> 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 https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf
- iainmerrick 3y agoI 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.
- kazinator 3y agoI 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.
- vidarh 3y agoWhether 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.
- 1a1a11a 3y ago> 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.
- robertsdionne 3y agoI wonder about allowing the hand to 1-D random walk left or right when examining the visited bit for evicting an item.