Sieve is simpler than LRU
cachemon.github.io
cachemon.github.io
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.
> 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
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.
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.
[ ][ ][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 don't see why I would think about doing it in hardware.
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 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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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?
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 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).
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.
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.
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.
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.
* is not worse than
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.
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.
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.
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.
That could possibly reveal interesting security-related properties, i.e. maybe future vulnerabilities.
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.
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.
> 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.
love references to this movie
Thanks for pointing out! I tried to write a blog post about SIEVE that was informative yet not too technical, and to infuse it with some humor. However, I clearly failed to find the balance. I'd like to change it back to a simpler, more straightforward style.
It's a long way to go for me to write a good tech blog. Criticism taken.
The advice I got about posting publicly, don't read the comments section lol
I normally do too but somehow it didn’t rub me the wrong way in this instance.
Perhaps the 1980s style day-glo star disarmed me? I didn’t really like that esthetic back when it was in fashion, but for some reason it was disarming here.
Perhaps it was the fact that the page was mainly a simple explanation with some clear drawings so a little stylistic exuberance didn’t overclutter things in my head.
All that been said, I’d normally be the same kind of curmudgeon as you.
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
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), 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.
At first, I thought FIFO-Merge keeping objects in the insertion order (FIFO) helps the eviction because I mostly worked with Twitter data in which popularity decay is common.
But later when I evaluated more traces (including block I/O workloads), it turned out that quickly evicting new objects (quick demotion) is the source of a low miss ratio. That's why we wrote these papers.
Interested readers are welcome to read more of related work 1. FIFO can be better than LRU, the power of lazy promotion and quick demotion https://dl.acm.org/doi/pdf/10.1145/3593856.3595887
2. FIFO queues are all you need for cache eviction https://dl.acm.org/doi/10.1145/3600006.3613147
[1] https://www.eecs.harvard.edu/~michaelm/postscripts/handbook2...
It is simpler to implement than LRU - a single "access timestamp" needed to be attached to data. It also shows performance on par or better than LRU when applied to database caching.
LRU suffers from linear access pattern, where it cannot degrade gracefully. Try to cache N+1 items in N-item LRU when items are accessed linearly or at random with removal.
The "random two choices" algorithm will replace an entry that is less recently accessed from two randomly selected. There is a chance that some of N+1 linealy accessed items will be in cache after a full scan.
Here are some comparisons of 2-random-choices with LRU in context of CPU caches: https://danluu.com/2choices-eviction/
Relevant quote: "LRU does worse than 2-random when the miss rates are high, and better when the miss rates are low."
"The miss rates are high" is the case when evicting newer but unused in nea future objects is preferable, in my opinion. Thus, "two random choices" algorithm is a direct competitor to SIEVE, they work better than LRU in about same conditions.
Implementation can be found https://github.com/1a1a11a/libCacheSim/blob/develop/libCache...
cache_obj_t *chained_hashtable_rand_obj_v2(const hashtable_t *hashtable) {
uint64_t pos = next_rand() & hashmask(hashtable->hashpower);
while (hashtable->ptr_table[pos] == NULL)
pos = next_rand() & hashmask(hashtable->hashpower);
return hashtable->ptr_table[pos];
}
As the code of RandomTwo depends on the hashtable_rand_obj, it also biased.
The same is for Random cache policy.
> 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.
[2] https://yazhuozhang.com/assets/pdf/nsdi24-sieve.pdf
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.
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.
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.
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.
https://github.com/cacheMon/lru-rs/commit/1c45ef7fe85f4a4395...
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.
But still, even in the current climate, I think this is going too far. The whole paragraph after the part I quoted is just as bad.
If you only read one paper in an unfamiliar field, you will not know if it lacks the necessary analysis.
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.
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.
Why do you guys read prose at all when it's obviously just a filler?
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.
https://cachemon.github.io/SIEVE-website/blog/2023/12/17/sie...
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.
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.
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.
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 ?
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.
[1] https://en.wikipedia.org/wiki/Cache_replacement_policies#Dyn...
[2] https://i0.wp.com/chipsandcheese.com/wp-content/uploads/2023...
[3] https://chipsandcheese.com/2023/09/11/hot-chips-2023-arms-ne...
Have you looked at ARC? It sounds similar - it is a cache split between LRU and MFU areas, where the split point changes dynamically depending on the workload. https://www.youtube.com/watch?v=F8sZRBdmqc0 is a fun watch on the topic.
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.
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).
dotnet runtime GC is interesting for caching, because it has multiple generations for the GC. Each time there is a GC the survivors are moved to the next generation. Moving most used items to the next generation and looking in the later generations first when resolving could be pretty quick.
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.
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.
In that regard - such eviction can be implemented "entirely" concurrently.
If you have multiple threads, then presumably you should think how to serialize access to your shared resource anyway.
>presumably you should think how to serialize access to your shared resource anyway.
I'd call that 'false'. The shared resource is the LRU Map in that case. The one w/ prob. eviction can be implemented (as in has been implemented) w/o a global lock (per the Map, which the LRU requires it). Prob. eviction can be implemented entirely lock free for that matter.
Locks offer no forward grantees, and don't scale. The changes of the lock state require the coherency traffic between the cores. Reads scale very well, writes don't.
Overall any data structure that requires a lock per the entire structure, especially on the read path -> bad, doesn't scale. Like I've said it's possible to have a Map w/o locks both on the reading/writing paths.
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.
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?)
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.
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.
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.
[1] https://github.com/memcached/memcached/pull/97
[2] https://github.com/memcached/memcached/blob/9723c0ea8ec1237b...
[3] https://github.com/memcached/memcached/blob/9723c0ea8ec1237b...
> 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.
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.
Compared to typical LRU O(logN) or O(1).
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.
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).
You are probably familiar with this problem but it is trickier than many average software devs allow. Basic CLOCK-derived algorithms are an obvious choice for CPU efficiency, and easy to patch up for most weaknesses, but when cache metadata becomes large, which is common on modern servers, they have a tendency to thrash the CPU cache for some access patterns. This has some pretty negative performance effects. Not having to worry about multithreading (because thread-per-core) enabled some modifications that came about as close I’ve seen to ensuring that cache replacement lives in hot CPU cache lines. This largely involves ensuring that you can find an immediately evictable buffer with a short scan with very high probability, and if that fails (a rare case), the scan metadata is so compressed that it often easily fits within L1. And that metadata is often evaluated with massive parallelism in a handful of clock cycles using vector intrinsics. AFAIK, these variants are the strongest cache replacement designs in terms of CPU efficiency (not necessarily cache hit rate for some access patterns).
Some of the core techniques above are things I learned from other database kernel designers who themselves learned it from someone else. The scan length reduction technique was so elegant and obvious in hindsight that I am surprised that it never occurred to me or most anyone else (though it does make the designs more subtle). Quite a lot of these practical details have never been written down a far as I can tell, it is passed along as lore and beer convos. I am as guilty of this as anyone else.
I thought the SIEVE algorithm was great, by the way! This area of research deserves far more attention than it seems to receive, most people act like it is a fully solved problem. Caches are in the hot path of everything.
That said, in recent years I have become a lot more interested in the theoretical limits of effective cache replacement, regardless of algorithm. There are modern workloads that are asymptotically approaching randomness for all cache replacement even when the cache is 10-20% of the working set. Being able to narrowly split and assign workload to things that are effectively cacheable and things that are not is becoming important. I routinely deal with workloads now where <1% of the working set fits in memory, and it is becoming more common. Caching is important but the impact on overall performance is diminishing.
> a lot of these practical details have never been written down a far as I can tell, it is passed along as lore and beer convos
I wish the valuable knowledge could be written down and shared.
Yup, I am on the same page as you, after seeing the many state-of-the-art having similar miss ratios, I am inclined to think we are close to the maximum possible hit ratio bounded by the limited information from the request history (information theory).
Doesn't that mean that over half the time, 55%, it's sometimes equal and, more likely so, worse?
Insertion:
%hash = () if keys %hash > 100000;
$hash{$key} = $val;
return $hash{$key};
The downside is that the mean utilisation is only 50%.
Has the advantage of lower overhead and simplicity.
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.
The code and documentation are correct, the animation is wrong.
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?)
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.
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#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."
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.
Dude, what?
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)
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.
Really handy for tracking potentially abusive ips, if your table is big enough; on a request, check if it's in the table - if so increase the count and if it's above the theshold mark it. If it's not in the list, decrement the current item and move current to the next item.
An agressive user will clear out a slot for itself, and rapidly hit the threshold. Other users will come and go. You can iterate through and try to always clear a spot for a new entry, but it might not be necessary, depending on what you're caching.
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.