3 ms·

It looks like your lazy promotion algorithm is O(n). If you get a particularily unlucky request pattern you'll be walking the whole list to know which item to e

by eis 3y ago

It looks like your lazy promotion algorithm is O(n). If you get a particularily unlucky request pattern you'll be walking the whole list to know which item to evict. I don't think the claim that this LP FIFO method is always less intensive than LRU will hold up to scrutiny. But I still find the paper inspiring. Thanks for shaking a bit the established believes in the field :)

1a1a11a 3y ago
This is common confusion. It is O(n) where n is the number of objects, but LRU is O(m) where m is the number of requests, which is often more than the number of objects :)
- eis 3y ago
  I think we are not talking about the same thing. LRU needs to access/modify the tail and head of the queue once per request for both Get and Insert. 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.
  - 1a1a11a 3y ago
    Yes, in the worst case, it would need O(n) to evict, and it can hurt tail latency, but it only happens once in a while in the worst case because each time when an object is checked, the bit is set to 1. 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.
    - eis 3y ago
      It might not happen only once in a while. Consider the following pattern in which a Fetch() does a Get and then an Insert on cach-miss: Fetch("1"); Fetch("1"); Fetch("2"); Fetch("2"); Fetch("3"); Fetch("3"); ... This will result in your queue being 100% filled with items that are marked as hit because of the second Fetch for each key. After the queue is full each first Fetch will result in an eviction (new key to insert) which has to walk the whole queue because the only item marked not-hit is at the head of the queue due to being lazy promoted. 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.
      - 1a1a11a 3y ago
        Consider the the request sequence you gave a, a, b, b, c, c, d, d ... and a cache size of 2, when the first c arrives, the cache is in the following state (left is head and right is the tail, inserted at the head): b(1) a(1) 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.
        eis 3y ago
        Ok I see where the difference is now. You are clearing the hit bit for all items marked as hit on a single eviction. I mean yes I guess that means that during the following request you don't have to check all items in the queue but now you have a different problem: you evict items prematurely. With a cache of size 2 I can't show it but consider a cache of size 3 and the following pattern: a, a, b, b, c, b, d, e 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.

by eis 3y ago

1a1a11a 3y ago

This is common confusion. It is O(n) where n is the number of objects, but LRU is O(m) where m is the number of requests, which is often more than the number of objects :)

eis 3y ago
I think we are not talking about the same thing. LRU needs to access/modify the tail and head of the queue once per request for both Get and Insert. 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.
- 1a1a11a 3y ago
  Yes, in the worst case, it would need O(n) to evict, and it can hurt tail latency, but it only happens once in a while in the worst case because each time when an object is checked, the bit is set to 1. 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.
  - eis 3y ago
    It might not happen only once in a while. Consider the following pattern in which a Fetch() does a Get and then an Insert on cach-miss: Fetch("1"); Fetch("1"); Fetch("2"); Fetch("2"); Fetch("3"); Fetch("3"); ... This will result in your queue being 100% filled with items that are marked as hit because of the second Fetch for each key. After the queue is full each first Fetch will result in an eviction (new key to insert) which has to walk the whole queue because the only item marked not-hit is at the head of the queue due to being lazy promoted. 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.
    - 1a1a11a 3y ago
      Consider the the request sequence you gave a, a, b, b, c, c, d, d ... and a cache size of 2, when the first c arrives, the cache is in the following state (left is head and right is the tail, inserted at the head): b(1) a(1) 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.
      - eis 3y ago
        Ok I see where the difference is now. You are clearing the hit bit for all items marked as hit on a single eviction. I mean yes I guess that means that during the following request you don't have to check all items in the queue but now you have a different problem: you evict items prematurely. With a cache of size 2 I can't show it but consider a cache of size 3 and the following pattern: a, a, b, b, c, b, d, e 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.