1. You've got a cache miss 2. You need to evict something, so look at the next item due for eviction. 3. It's a candidate for promotion, so you reinsert it. 4. You still need to evict something, so goto 2.
Isn't that a potential infinite loop? And even if not (because there's some other exit clause), how is it quick?
The second is quick demotion which uses a small FIFO to filter out most objects that are not requested soon after insertion in the cache.
Your algorithm on the other hand does not need to modify the order of the queue on a Get (just mark single item as hit if not marked already) which is really good. But on Insert your algorithm needs to do a reverse scan through the queue until it finds an item it can evict (not marked as hit). This might need to walk the whole queue if unlucky. And it can get so bad that it needs to do that on every single eviction so latency and CPU usage could skyrocket. Granted, this is a worst case scenario that shouldn't happen usually but if it does then it could be a real problem.
So in that sense LRU would be O(m) in terms of queue modifications and reads but yours would be O(n*m) for queue reads.
The O(n) I mentioned was for the number of items the algorithm needs to check on a single insert that results in an eviction aka the usual case.
I don't understand the O(n*m) argument, does the answer invalidates it?
On the tail latency part, if it becomes a problem, we can bound the number of objects it checks.
Fetch("1"); Fetch("1"); Fetch("2"); Fetch("2"); Fetch("3"); Fetch("3"); ...
My O(n*m) reply was because your O(m) was considering a whole run over multiple requests and my O(n) was only considering one request. So if I were to also talk about multiple requests then your eviction algorithm needs to look at O(n*m) items for evictions in the example pattern I presented. O(n) per request for m requests.
A malicious actor could abuse this fact to cause a DoS.
No you can't just bound the number of objects it checks because that would result in a flurry of cache misses as it would mean you have to fail the insert.
and it will trigger an eviction, and requires resetting 2 (or O(m)) objects with the following state changes b(1) a(1) -> b(1) a(0) -> b(0) a(0) -> c(0) b(0)
the next c will change the bit to 1, and we will have c(1) b(0),
When d arrives, b will be evicted, and we have d(0) c(1)
Note that we only check/reset one object this time instead of O(m).
Therefore, in the worst case between each O(m) eviction, you need O(m) requests to set the m objects to "visited", strictly no more than a LRU cache.
When d arrives state changes c(0) b(1) a(1) -> d(0) c(0) b(0). When e arrives state changes d(1) c(0) b(0) -> e(0) d(0) c(0).
Note how b got evicted from the cache even though it was requested more recently and more frequently than c because d cleared out the hit bit for both b and c.
Now you traded off hitrate vs latency. But the worst case latency is still O(n) just can't happen multiple times in a row anymore.
Imagine you have a cache of 1 million items all marked as hit and you get a new request which would evict all 1 million items. You gained latency for some subsequent requests but increased it in the current one. Crucially you also just cleared out the hit marker of whole cache.
Any eviction algorithm would have an adversarial workload, so a simpler algorithm is better because you know what the workload was and whether it happens in production; on the other end, the complicated one only makes this worse and the failure of a cache is often catastrophic. :)
You don't always know the workload beforehand and can pick the appropriate cache policy. Workloads can even change during runtime.
I haven't seen a simple cache algorithm that performs well in every workload and I believe any that wants to succeed needs to incorporate different sub-algorithms for different workloads and be adaptive.
Having an ideal adaptive algorithm is certainly better, and I do observe different workloads favor different algorithms, but all adaptive algorithms have parameters that are not optimal for a portion of workloads and also hard to tune (including ARC).
If you give me an algorithm, I can always find a production workload for you that the algorithm does not work well.
"Simple algorithms are the ones most likely to fail catastrophically because they are made for a certain range of access patterns" I do not see how FIFO and LRU fail catastrophically except on scanning/streaming workloads. Happy to learn about it.
A friend of mine works on a online-shop / distribution system that during most of the day has a zipf like distribution but after normal working hours when retail shops close he gets completely different patterns as the shops push their data for the day into the system and then all kinds of BI tools run for a few hours.
Of course adaptive caches are never completely optimal because it takes time for them to learn which workload is actually currently happening but after a while they can get very close. A good adaptive cache should not need tuning to get good results because the whole reason for it to be adaptive is to tune itself. Of course there are quite a few adaptive caches, especially the first ones that pioneered this, that still needed tuning.
I don't understand the last question. You say you can't see how FIFO can fail catastrophically and at the same time state a case how it can. Scanning workloads are something that does show up in the real world all the time. NovaX seems to have run your algorithm through some traces where it had a near zero hitrate. It can be more important to avoid these extreme cases than having a slightly better hitrate in the normal case.