15 ms·

Sieve is simpler than LRU

• blt 3y ago
  SIEVE isn't just playing the part of a cache eviction algorithm; it's stepping up as a cache design superstar. Think of it like giving a fresh spin to classics. Is this how academics write about their own work in blog posts now? The result seems really strong. It's sad the author feels this kind of hype is necessary.
  • lstamour 3y ago
    I haven't read the original article yet but your excerpt here reminds me strongly of what ChatGPT writes when you ask it to rewrite technical prose in an approachable, non-technical "for dummies" style. As in, I asked ChatGPT to rewrite some text with metaphors and it kept giving me answers that included the phrase "Think of it like...." And whatever the metaphor it came up with was. It also often used words like "superstar" far more than I would.
  • falsandtru 3y ago
    Recent hype cache algorithms are characterized by cherry-picking hit rates in content caching such as CDNs. Common cache algorithms such as ARC, LIRS, and TinyLFU have made consistent and common comparisons across a variety of disk access patterns, but hype cache algorithms boast hit/miss rates for network accesses without these comparisons. Hype cache algorithms have only been validated in a very narrow domain, and their general superiority has not been validated at all.
    • falsandtru 3y ago
      Just to clarify, this means hype cache algorithms are basically not replaceable with common cache algorithms such as LRU or ARC.
      • falsandtru 3y ago
        I probably should have written the opposite. English is unfamiliar.
  • SerCe 3y ago
    I believe there is also a paper [1] if you're looking for more details or a more academic description. [1]: https://junchengyang.com/publication/nsdi24-SIEVE.pdf https://junchengyang.com/publication/nsdi24-SIEVE.pdf
    • neoneye2 3y ago
      Impressive how few code changes they managed to convert an existing LRU library into SIEVE. https://github.com/cacheMon/lru-rs/commit/1c45ef7fe85f4a43956a58452cfdd90c6215a1ab https://github.com/cacheMon/lru-rs/commit/1c45ef7fe85f4a4395...
  • sebastianconcpt 3y ago
    That caught my attention too. It mixes the level of communication jumping from highly technical to kindergarten when you have not a cognitive seat belt for that. Also why? The only value that comes out of that comment in the middle of the technical discussion is vanity and nothing else. It could have been more useful if it would be creating a metaphor that approximates understanding. That would be forgivable. But vanity isn't.
  • prof-dr-ir 3y ago
    I agree that the hyped-up language is off-putting. It is however not at all typical for academic publications and blog posts. In the few times I have seen it before, the author was always a PhD student and a non-native speaker (as it happens from China) and this case is no exception. They were also all smart people, so I am optimistic that with time their writing style will become more attractive.
  • scotty79 3y ago
    I didn't even notice the style. I first read the verbal description of the algorithm, got angry that it's incomplete and I lack context of what this is trying to achieve. Then I skipped to reading Python code. Then got back to verbal desc to confirm. Concluded it's not that bad but still incomplete. Then I looked at the performance graphs and concluded I might use it if I ever need something like that. Why do you guys read prose at all when it's obviously just a filler?
  • vanderZwan 3y ago
    I presume you have not experienced being an academic in recent years and having to deal with the expectation to sell your research on "Scientific Outreach Twitter". Now, technically neither have I, but I've worked alongside scientists for a couple of years who do. Yes, it's kind of sad, but I feel more empathy for situation the author is in that leads to it. The actual papers themselves seem pretty solid from a surface reading as a non-expert, at least in terms of having clear explanations and easily verifiable results.
    • falsandtru 3y ago
      > The actual papers themselves seem pretty solid from a surface reading as a non-expert, at least in terms of having clear explanations and easily verifiable results. If you only read one paper in an unfamiliar field, you will not know if it lacks the necessary analysis.
      • vanderZwan 3y ago
        This isn't exactly a paper on room temperature superconductors... I read plenty of compsci papers and whitepapers, I just don't have to work with this specific niche of web caching. I doubt the methodology for benchmarking is so radically different from other computer backgrounds that my ability to detect fudging in it, or other structural issues with them would be compromised. And on top of that, in this case both the code and data sets are available and the papers went through peer review.
        • falsandtru 3y ago
          > This isn't exactly a paper on room temperature superconductors... Same in every field. > I read plenty of compsci papers and whitepapers, I just don't have to work with this specific niche of web caching. You clearly have no expertise in this field. Over.
          • vanderZwan 3y ago
            Ah, you didn't come here to have a discussion, but to "win" a "debate". Sure, whatever, you win
• kazinator 3y ago
  There is obviously a LRU-like element in the algorithm because 1. Evacuation generally shifts items to the right. 2. The Hand moves to the left. 3. Items skipped by the Hand (appearing to its right) are spared from eviction until the Hand wraps around. You can see it in the animation. D is flipped to visited just in the nick of time, and the Hand moves over it. Then it is spared from then on until the Hand wraps around (the animation doesn't go that far). Items that are used frequently will tend to be in the Visited state when the Hand passes over them, and stay cached.
  • cryptonym 3y ago
    I don't understand why D is NOT switched to false when the hand moves left and removes E. At the beginning A is switched to false when the hand moves left over it.
    • joaomacp 3y ago
      I watched it again and read the algorithm description part, and I think you're right - D should have been switched to false, as the hand was pointing to it when a cache miss happened.
      • j16sdiz 3y ago
        I watched it again and checked it against the python reference code. The code and documentation are correct, the animation is wrong.
        • kazinator 3y ago
          The behavior is inconsistent with what happens to A and B at the very beginning. Whenever the hand skips a visited node in search of an unvisited one, it must flip it to unvisited. If D were given this special treatment every time the hand cycles around, it will forever stay in the cache even if not accessed (D-plomatic immunity?)
      • deleted 3y ago
        [deleted]
• hknmtt 3y ago
  >On a cache hit, SIEVE marks the object as visited. On a cache miss, SIEVE checks the object pointed to by the hand. If the object has been visited, its visited bit is reset, and the hand moves to the next position, keeping the retained object in its original position in the queue. This continues until an unvisited object is found and evicted. After eviction, the hand moves to the next position. Dude, what?
  • echelon 3y ago
    The hand is a pointer on the queue to the current cache item being inspected. The cache miss eviction behavior depends on if the pointed to element is marked as visited. If you're familiar with LRU/LFU, ring buffers (though this isn't such), and data structures this will probably make a lot more sense. A rigorous course in data structures is fantastic for any engineer. Everything is data structures and algorithms at the end of the day.
  • vidarh 3y ago
    Look at the animation. The description is confusing. It uses a list that's treated as a ring buffer to keep track of keys currently in the cache. The "hand" is a pointer that points to a given node in that ring buffer. When the cache is full and a space is needed, the "hand" moves through that buffer (possibly wrapping around). Whenever it points at a node that hasn't been touched since the last time it was seen, that node is evicted and you're done for this time, otherwise it clears the visited bit for that node and keeps going. (You're always guaranteed to find a node to evict, because worst case you scan through the entire set of nodes, and find the first node you cleared the visited bit of)
  • Epa095 3y ago
    Maybe it's a bit odd that it resets the 'visited' bit on non-related objects (why are they suddenly not visited)? For me it helped to rather think about 'visited' as a special case of a counter called 'valuation' (or something like that). New objects come in with valuation 1, on cache hits a objects valuation is set to 2, and when the hand moves left it decreases objects valuations until it reaches one that gets valuation 0, then it's evicted immediately. One could easily imagine a modified algorithm where 'valuation' could be increased further than 2 if an object got visited many times (but then eviction would be much slower in some cases). Then this is all optimized by using a bool instead of an int since we truncate 'valuation' at max 2. Idk why they choose to call it 'visited' though.
• nsajko 3y ago
  Context: https://en.wikipedia.org/wiki/Cache_replacement_policies https://en.wikipedia.org/wiki/Cache_replacement_policies
• deleted 3y ago
  [deleted]
• tommiegannert 3y ago
  Replaced the linked list with a Python list, for clarity: https://gist.github.com/tommie/577b4e154731a280136295180211e953 https://gist.github.com/tommie/577b4e154731a280136295180211e... (and I hope I got it right) Since this is using a 1-bit visited counter, a small cache could use a bit vector and bit shifting to "remove" a value from the queue.
  • falserum 3y ago
    Python list is backed by array. So removing an element from the middle of list is costly. (I assume this was the reason for linked list usage in original version)
    • tommiegannert 3y ago
      Indeed, but this is clearer to read.
  • ianbicking 3y ago
    Python's ordered dict uses an efficient linked list implementation, it might be elegant here?
    • tommiegannert 3y ago
      Oh, interesting. The documentation there also says > They have become less important now that the built-in dict class gained the ability to remember insertion order (this new behavior became guaranteed in Python 3.7). https://docs.python.org/3/library/collections.html#ordereddict-objects https://docs.python.org/3/library/collections.html#ordereddi... It assumes iterators are stable (and valid) under insertion, and I can't find any docs on that for either. Since you (AFAIK) can't create an iterator at a specific key, we also couldn't use keys as the "hand."
• mgaunard 3y ago
  LRU makes sense to me, so that is what I use. The fact that some algos outperform it on some distributions (which might or might not be relevant to the use cases I might face) isn't good enough to convince me to switch.
  • Karellen 3y ago
    The one problem with LRU that I always remember is one John Carmack one wrote about with an LRU cache for items that were always accessed in the same order (objects to be rendered, in z-order?), which happened to be slightly bigger than the frequently-accessed set... until the day it wasn't. And performance suddenly dropped off a massive cliff. The problem, it turned out, was that iterating through the same frequently accessed set of items, 1...N, in the same order every time, with an LRU cache of size N-1, would put items 1...N-1 in the cache, and then on the very last step evict item 1 (because it was the oldest) to put in item N. The next time round, when item 1 was not in the cache, it would evict item 2 (the oldest) to make way for item 1. And then evict item 3 to make way for item 2, evict 4 for 3, etc..., until finally evicting item 1 (again) to make way for item N. And do the same on the next iteration. IIRC, he solved it by switching one of the cache slots as a "scratch" slot for the current iteration, so the last few items in the set would only overwrite each other, and items 1...C-1 would remain in the cache for the next iteration (where C is the size of the cache). It is an unusual use case, to be sure, and not a reason to avoid LRU caches in general. Most users are unlikely to hit it. But it's useful considering as an example of how edge cases can pop up in places you might not have been expecting. It also shows you don't necessarily need to completely switch algorithms if you hit a pathological case - just tweaking how the cache works slightly (LRU to LRU-plus-scratch-slot) can sometimes get you back to 95% of where you were, which might be good enough.
    • tankenmate 3y ago
      This is the "scan resistance" pathology mentioned in the article. And the scratch slot is a (very simple) form of generational caching; i.e. generational LRU or multi-generational LRU [0]. [0] https://lwn.net/Articles/856931/ https://lwn.net/Articles/856931/
    • 3y ago
• latch 3y ago
  I feel like a simple improvement to LRU is to not promote on every fetch. This adds some frequency bias into the mix and reduces the need to synchronize between threads. Is this a known/used technique?
  • NovaX 3y ago
    Yes, basically you sample requests to improve concurrency and rely on the hottest entries to be more frequently observed in the sample. Memcached uses 60s intervals between promotions and a try-lock guard. A small variation is to do this probabilistically using a thread-local random. Caffeine (BP-Wrapper) decouples the event from the policy by recording into an array of ring buffers hashed to by the thread id. This serves to spread out contention and drains them under a try-lock to update the eviction policy. When the buffers fill up to quickly then it will drop events instead of blocking. This allows the cache to shed load by reducing the sample quality if a burst of activity. Sieve is a very slight modification to the classic Clock algorithm (1969, Multics) which is a well known and commonly used pseudo LRU. The clock hand is a cursor to scan from and to insert behind, where instead they separated it to maintain FIFO insertion order. Clock and its variations are probably the most commonly used caches, e.g. Linux's page cache and Postgres' buffer pool. Sieve decoupling the hand from the insertion point so that new arrivals are evicted sooner, so the benefit is very workload dependent. Sampled policies are another common policy type, e.g. where the timestamp is updated on access. Then on eviction a random subset is chosen and a utility function discards the least valuable. Since there are no promotions it is nice for simple concurrent caches and mimics a classic lru or lfu policy. In short, a concurrent cache will not promote synchronously on every access event. That is only done as a strawman comparison for a simple baseline, though its actually good enough for many simple use-cases. It would be very misleading if researchers pretended that is how concurrent LRU-style caches are implemented.
    • quangtung 3y ago
      Do you mention the old version of memcached? Newer versions seem doesn't need that 60s anymore. The architecture feels similar to BP-Wrapper. Ref: https://memcached.org/blog/modern-lru/ https://memcached.org/blog/modern-lru/
• sph 3y ago
  From the look of it, it seems like this really doesn't like frequently accessed items being close by, as they probably get evicted the first time there is a cache miss on the currently-pointed item (but anyway end up further down the array which would mitigate the problem the second time around) Which also means, this does not perform well at all with very high hit rates. A dumb LRU cache might perform better if you can fit most of your items in the cache. In any case, seems simple enough, but very unintuitive compared to a LRU algorithm which makes obvious sense. It is really hard on paper, without looking at actual numbers, to tell how this would be better than LRU.
  • tankenmate 3y ago
    But the article has tests with results, in practical terms it has actual results of it working; so is your focus on how well it actually performs? or how do we analyse how it achieves its results? As to fitting most of your items in the cache; just about any cache method will work well if you can fit most things in the cache (which will typically blow out your hardware bill, ever tried to make your L3 as big as main memory?)
    • xxs 3y ago
      >L3 as big as main memory That's not possible for many a reason, caches on the CPU die (or substrate, think AMD) tend to use the infamous 6 transistors per bit. The ones in the RAM are composed of a single transistor + capacitor, much denser. We can't have more L3 as the latency to access would pretty much make it main memory. The cache are as big as they can be, increasing their size overall doesn't contribute significant performance boost. The hardware bill is just not a thing, it's physically impossible to build very large caches that have low latency.
      • tankenmate 3y ago
        There are CPUs that have external (including L3) caches; and yes, off die they will have a lower latency. And that is not to mention that a cache topology uses much more power, and not just in the T6 cell itself, there's all the cache handling logic as well. But, it is possible to do; insane but possible.
• Sandworm5639 3y ago
  Why call it "FIFO queue"(isn't it just stack?) when actually you need to remove elements from the middle? Also I think you could do away with storing "prev" for each node and make it like std::forward_list(with some additional work during eviction). > We pushed SIEVE a bit further by letting it peek into the future – well, sort of. We tested how well it could guess the next request. It turns out, with this extra bit of foresight, SIEVE is nailing it, outperforming the rest in almost all scenarios. No idea what they mean here.
  • ncruces 3y ago
    A stack is actually LIFO? Otherwise, yeah, if you remove elements from the middle, you either need a structure that allows it, or you amortize it by making such updates less frequent. Still not a queue.
    • deepGem 3y ago
      If you need middle or random access then it’s an array, neither a queue nor a stack :) I couldn’t understand the animation at all. LRU is much simpler to understand and implement what’s so complicated about a doubly linked list ?
      • xxs 3y ago
        The median could trivially be the root of a red/black tree.
  • scotty79 3y ago
    I think they invoke FIFO because hand pointer start at tail so the first-in objects have first the chance to get evicted (be out).
• 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.
• MrYellowP 3y ago
  > show that SIEVE outperforms all state-of-the-art eviction algorithms on more than 45% of the traces. Doesn't that mean that over half the time, 55%, it's sometimes equal and, more likely so, worse?
  • ColonelPhantom 3y ago
    Well, it mentions comparison against multiple other algorithms. So if those 55% are divided between a bunch of other algorithms, being the best in 45% could mean it's the best more often than any other algorithm.
• 3np 3y ago
  I may be missing some subtlety but it seems like this is computationally O(N) on insertion, since the eviction will have to visit and mark every node in the pathological case where all existing entries are already visited? Compared to typical LRU O(logN) or O(1).
  • munch117 3y ago
    O(N), but amortized O(1).
    • 3np 3y ago
      How is it amortized O(1)? Able to prove it or at least construct an outline of an argument as to why?
      • munch117 3y ago
        Because every object stepped over is downgraded from visited to not visited. At most 1 object is set to visible per lookup.
  • 0xFEE1DEAD 3y ago
    I think you're correct about the worst case being O(n) but it's behavior heavily depends on the access pattern of the cached items which makes it hard to reason about.
• chmike 3y ago
  The effectiveness really depends on the request pattern. In some use case, the LRU is the most efficient. When it is purely random, it obviously won't be the best as any value has the same probability to be selected. Regarding simplicity, there is a simpler algorithm where we don't need the next and prev pointers. We simply replace the non-flagged value at the hand. This is most probably what is used in CPUs.
• furyofantares 3y ago
  I understood it eventually but both the description and animation were confusing at first. I think I would have been a lot less confused if there weren't so much hype and buildup about how simple it was gonna be. Maybe it really is easier to implement than LRU. I'll give the benefit of the doubt on that. But conceptually it's way more complex. I understand the LRU concept immediately from the name alone. All the later hype was off-putting too, in a way that reduces trust. I simply do not believe the author is being candid due to the marketing speak. Maybe those parts of the post can just be ignored but it leaves a lingering uncertainty about even the technical points.
• layer8 3y ago
  > SIEVE isn't just playing the part of a cache eviction algorithm; it's stepping up as a cache design superstar. Think of it like giving a fresh spin to classics. We've plugged SIEVE into LeCaR, TwoQ, ARC, and S3-FIFO, swapping out their LRU or FIFO queue for a SIEVE one. > Swapping LRU with SIEVE in these algorithms isn't just a minor tweak; it's more like giving them a turbo boost. Take ARC-SIEVE, for instance – it's turning heads with its slick efficiency, especially noticeable across different cache sizes. We didn't stop there. We pushed SIEVE a bit further by letting it peek into the future – well, sort of. We tested how well it could guess the next request. It turns out, with this extra bit of foresight, SIEVE is nailing it, outperforming the rest in almost all scenarios. I find that style of language off-putting and immature.
  • spangry 3y ago
    Their early work was a little too new wave for my taste. But when Sports came out in '83, I think they really came into their own, commercially and artistically. The whole album has a clear, crisp sound, and a new sheen of consummate professionalism that really gives the songs a big boost. He's been compared to Elvis Costello, but I think Huey has a far more bitter, cynical sense of humor.
    • gumby 3y ago
      Nicely done!
      • gumby 3y ago
        I’m sorry this was downvoted because I thought spangry’ comment deserved more praise than just my upvote.
    • pmarreck 3y ago
      hahaaaaa love references to this movie
  • scotty79 3y ago
    It's your right to feel that way as is the right of the author to use whatever style they please.
• the_common_man 3y ago
  Is there a term for such hyped up language?
  • dcuthbertson 3y ago
    Yes, language like "... it's turning heads with its slick efficiency..." and "We didn't stop there. We pushed SIEVE a bit further..." smacks of sales pitches for cheap-quality, overpriced merchandise. Certainly the statements are a kind of hyperbole. Maybe puffing/puffery[0] is close to what you're looking for. [0]: https://www.law.cornell.edu/wex/puffing https://www.law.cornell.edu/wex/puffing
• jstanley 3y ago
  My favourite simple "eviction" algorithm is just to wipe out the entire cache as soon as it gets full. Insertion: %hash = () if keys %hash > 100000; $hash{$key} = $val; Retrieval: return $hash{$key}; Desirable properties include bounded memory usage (assuming bounded size of $val), O(1) (amortised) insertion/retrieval, and (most importantly) it only takes a second to write and there's almost 0 chance of writing it wrong. The downside is that the mean utilisation is only 50%.
  • throwaway143829 3y ago
    I love the simplicity, but wiping the cache is a no-go for most serious apps.
    • jstanley 3y ago
      It depends on the application.
    • 3np 3y ago
      If wiping the cache is a no-go, how do you handle (unexpected) restarts?
      • jrockway 3y ago
        With a 3 day outage and a status page that says "a small percentage of users are experiencing decreased availability while we investigate a network issue in us-east-1".
  • cmrdporcupine 3y ago
    Another simple one is to just identify a bunch of completely random candidates for eviction, give them some interval of time for a "second chance" to be used, and if not used in that time, flush them. Has the advantage of lower overhead and simplicity.
  • phkahler 3y ago
    I wonder how that would compare to randomly evicting something.
• 0xFEE1DEAD 3y ago
  > SIEVE is nailing it, outperforming the rest in almost all scenarios. I'm curious why there's a lack of transparency regarding the scenarios where SIEVE did not surpass other algorithms. Another concern is the emphasis on average performance and P10/P90 metrics. When evaluating a caching algorithm metrics like P99x are often more insightful. The omission of these details coupled with the sensationalist tone of the article definitely triggers some red flags for me.
  • brightball 3y ago
    I've always wondered about setting up a Cost-Benefit Cache. Elixir's built in cache made me think of it first because it would simplify the implementation, but it could really be done in any language. The idea being that you track a few stats for each cache item: a. Time to retrieve the cached data from original source b. Frequency of requests for the data from the cache c. Size of the data to be stored Size of the data to be stored is the "cost" since it takes up space in the cache that could be occupied by other data. Retrieval time and frequency of requests would be the benefit since it should reflect the amount of time saved (a 5 second query called 4 times / minute would save 20 seconds per minute of execution time). (a * b) / c = Priority. Lowest priority gets evicted first as cache size reaches it's limit. The idea behind doing this is that you could run just about any data that could potentially be cached through the system and it would only be stored if the priority was higher than the lowest priority item currently in the cache. This should also deal with spikes or sudden slowness automatically if a part of the application is suddenly hammered.
  • shaicoleman 3y ago
    The con is mentioned in the "SIEVE is not scan-resistant" section https://cachemon.github.io/SIEVE-website/blog/2023/12/17/sieve-is-simpler-than-lru/#sieve-is-not-scan-resistant https://cachemon.github.io/SIEVE-website/blog/2023/12/17/sie...
• jimberlage 3y ago
  This is very interesting! I really like the emphasis on simplicity in addition to performance - seems easy enough to reason about. I guess for observability’s sake, when implementing this, you’d probably want to record a distribution of distance from the pointer to the evicted item, and match it up with request latencies.
• rix0r 3y ago
  There seems to be a mistake in the animation. > On a cache miss, SIEVE checks the object pointed to by the hand. If the object has been visited, its visited bit is reset When the animation gets to the point where the I element is checked against the cache, the hand moves off of D without resetting its visited bit.
  • kbutler 3y ago
    Yes, the illustration is incorrect, and does not match the code's evict function, which only moves the hand after marking the current object "unvisited". From the initial state, with the hand pointing to A(visited), when the request for H comes in, A is marked unvisited before moving the hand. When the hand is pointing to D(visited) and the request for I comes in, it should mark D unvisited before moving the hand. This "feels wrong" because D had just barely been marked visited, but it is an implication of the SIEVE algorithm. It's generally a red flag when a "better, simpler" algorithm is explained with a faulty illustration, suggesting the author overlooked or misunderstood the implications of the algorithm.
    • yazhuo 3y ago
      Thanks for pointing out. We have updated the animation.
• Hrun0 3y ago
  It's a bit off topic, but how are the animations made?
  • portpecos 3y ago
    Came here to ask the same question.
    • 1a1a11a 3y ago
      It was made with keynote with the magic move between slides. Maybe @yazhuo can share the file.
      • yazhuo 3y ago
        @Hrun0 @portpecos Sure, I'd like to share the file if anyone needs it.
        • Hrun0 3y ago
          No need, but thanks :)
    • yazhuo 3y ago
      I used Keynote, especially the magic move function, to create the animation. A magic move is transition that creates the effect of objects moving from their positions on one slides to new positions on the next slide. Then you can export the keynote file as a GIF.
• sebnukem2 3y ago
  This is presented like the best cache algorithm ever invented, but it's not simpler than LRU.
• vanderZwan 3y ago
  My first impression was that this seems related to the S3-FIFO queue data structure that was posted here last year[0], and the personal site of that algorithm's main author actually mentions it[1]: > S3-FIFO and SIEVE are being evaluated at several companies, if you are interested in joining the adoption army or if you look for help and want to provide help, find my email on this page. :) Looking into the papers of both algorithms, they basically swapped primary and secondary authors[3][4], with the main author of Sieve being the one to write this blog post. Just sharing this to give some context that could be useful for people who actually know about these topics to assess the claims being made. I don't deal with the problems these data structures aim to solve at my day job, so I'll refrain from commenting on that. But I will say that from an implementation perspective I think the algorithms look elegant in their simplicity, and easy to grok, so at least that part of what they promise is held up. EDIT: Mark Brooker also wrote a blog post about it[4], for those who want to have read the perspective from a third party who has the proper background. [0] https://s3fifo.com/ https://s3fifo.com/ [1] https://junchengyang.com/ https://junchengyang.com/ [2] https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf [3] https://dl.acm.org/doi/10.1145/3600006.3613147 https://dl.acm.org/doi/10.1145/3600006.3613147 [4] https://brooker.co.za/blog/2023/12/15/sieve.html https://brooker.co.za/blog/2023/12/15/sieve.html
  • cbsmith 3y ago
    I also noticed that S3-FIFO was the one approach that didn't seem to improve when SIEVE was added in.
    • 1a1a11a 3y ago
      Yup, SIEVE is good enough for web workloads :)
• taeric 3y ago
  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.
  • vardump 3y ago
    Caching is bounded, GC is potentially boundless. Caching is all about deciding what to evict.
    • taeric 3y ago
      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.
      • vlovich123 3y ago
        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).
• e63f67dd-065b 3y ago
  A lab mate of mine is actually submitting a paper on investigating why clock sometimes outperforms LRU very soon. The other benefit of clock is simplicity of implementation: you just have a pointer march around a ring buffer. I’m surprised that sieve is sometimes better, we might have to add a small section to the paper discussing it.
  • 1a1a11a 3y ago
    Do you work with Peter? If not, this will probably be the third paper...
    • e63f67dd-065b 3y ago
      Haha I do, are you with CMU's Yang Jun Cheng? Can't really think of anybody else working on this that would know these names.
• Dwedit 3y ago
  I always heard of this algorithm under the name "Not Recently Used" cache.
• 1a1a11a 3y ago
  Disclaimer: this is the co-author. Sorry for the hyped language. If my guess is correct, the blog was "polished" by ChatGPT, and the intention was to "polish" the English. The paper has more content and should be read more seriously. We will fix the animation error and update the writing shortly. Thank you for the feedback! Regarding some of the complaints on SIEVE performance. Here are some more results that I ran for other purposes. https://observablehq.com/@1a1a11a/sieve-miss-ratio-plots https://observablehq.com/@1a1a11a/sieve-miss-ratio-plots I haven't had time to add other algorithms to the plot, but they are often similar to or worse than TinyLFU (I did not pick TinyLFU to compare deliberately; I happen to have the figures on hand). While the results do not include byte miss ratio, which is important in some use cases, they are better than the results already shown. We acknowledge that * SIEVE may not work well on some block I/O workloads (this has been the statement in our writing from the beginning). However, SIEVE works well on large multi-tenanted block I/O workloads (see the Tencent and Alibaba figure in the link). For web workloads, SIEVE shows consistently good results. * As the author, when I look at this algorithm. My own feeling is that SIEVE may not be robust because it keeps evicting new objects when the hand moves to the head, effectively behaving as MRU. However, our large evaluations showed that modern workloads have certain properties that enable SIEVE to achieve a low miss ratio. We are still investigating this property and how to model it. If someone is interested, feel free to shoot me an email. * implementing SIEVE with a log-structured design or circular buffer is not trivial, but we had a design called Segcache (https://segcache.com https://segcache.com), which runs a constrained version of SIEVE. In simple libraries, linked list implementation should be easy, and one can check the examples on the website.
  • 1a1a11a 3y ago
    And Segcache is available in Rust as part of Pelikan project https://github.com/pelikan-io/pelikan https://github.com/pelikan-io/pelikan
    • thinkingfish 3y ago
      We also published it as a crate https://crates.io/crates/segcache https://crates.io/crates/segcache
• 1a1a11a 3y ago
  In case someone is interested, there is an independent review and implementation at https://github.com/scalalang2/golang-fifo https://github.com/scalalang2/golang-fifo
  • kurtextrem 3y ago
    Made also a JS implementation based on the golang one here: https://github.com/kurtextrem/js-sieve https://github.com/kurtextrem/js-sieve. It's a bit different than your reference implementation.
    • 1a1a11a 3y ago
      This is fantastic work!
• jandrewrogers 3y ago
  There are two important differences between academic and real-world cache replacement designs that should be kept in mind: First, most competent real-world designs are considerably more complex than the academic model whence they are derived. Support for or resistance to many common cache patterns can often be grafted onto simpler academic designs, making them considerably more robust and flexible than academic analysis may suggest. Consequently, benchmarking performance of an academic design with other academic designs is not all that indicative of how it would perform against a real-world implementation. In practice, thoroughly engineered real-world designs all have similar cache hit rate characteristics regardless of the algorithm starting point because it is relatively straightforward to take ideas from other algorithms and make something that works similarly for your algorithm, albeit a bit less elegantly. Second, one of the most important properties of cache replacement algorithms that is often overlooked in academic literature is real-world computational cost and operation latency. It is not unusual for a disk cache to be accessed 10s of millions of times per second. This cost can vary by orders of magnitude across algorithm implementations that have similar cache hit rates. Consequently, you often go with a design that has excellent memory locality, efficient concurrency, minimizes CPU cache thrashing etc because that is what keeps cache replacement out of the profiler. Given the first point above, there is a bit of a convergent evolution in real-world cache replacement designs because this has a larger engineering impact than the specific algorithm you use. Heavy optimization of the CPU throughput characteristics severely restricts the practical design space, which tends to push you toward the same couple algorithm starting points. It is not intuitive to most software engineers that this is often the property you most optimize for, not things like cache hit rate, when they first get into the space. It is a fun design problem with a very high dimensionality tradeoff space.
  • 1a1a11a 3y ago
    Good points. The first point is probably true for most research in computer systems. Different systems have different constraints that make a simple design very complex or not possible. Can you elaborate on the second point more? It feels to me that S3-FIFO is optimized for latency, throughput, and scalability than existing algorithms (e.g., with multiple LRU queues).
• charles_f 3y ago
  What does the acronym SIEVE mean? I guess SImple EViction something? I couldn't find that in the paper