5 ms·

> 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 pruden

> 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 ago
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.
- 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.
    - 1a1a11a 3y ago
      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.
    - scotty79 3y ago
      > 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.
      - kazinator 3y ago
        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.
cbsmith 3y ago
Yeah... It's hard not to read "luck" as, "there's something I don't understand". Luck doesn't really happen with caching.
- kazinator 3y ago
  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.
  - 1a1a11a 3y ago
    Do you have an example of a non-random algorithm that does not have adversarial workloads?
  - NovaX 3y ago
    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.

kazinator 3y ago

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.

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.
  - 1a1a11a 3y ago
    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.
  - scotty79 3y ago
    > 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.
    - kazinator 3y ago
      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.

cbsmith 3y ago

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

kazinator 3y ago
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.
- 1a1a11a 3y ago
  Do you have an example of a non-random algorithm that does not have adversarial workloads?
- NovaX 3y ago
  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.