5 ms·

Rough Summary: Start with a dumb-cache using "FIFO" (first in/first out) Keep track of anything with "hits" while in the cache (simple boolean/bitmap instead

Rough Summary: Start with a dumb-cache using "FIFO" (first in/first out) Keep track of anything with "hits" while in the cache (simple boolean/bitmap instead of complicated locks/data structures) Re-insert "hit" items when they would normally be evicted/age out (Lazy Promotion). BTW, also have a mini-cache in front of the main cache (10% of cache size) which tries to "drop off quickly" (effectively: must have a "hit" within first 10% of being cached). BTW, also keep track of a "ghost cache" ("hits only", not contents??) for the duration of the overall FIFO-cache, and use that to guide eviction/re-insertion. I'm a little bit unclear on this aspect, but it seems like an "obvious in retrospect" set of guidance.

gridspy 3y ago
Useful summary. Made me want to read about the ghost cache. The cache layout is: Probationary 10% + Traditional 90% (of memory). The idea is that most items are not requested again prior to dropping out of probationary and so don't take up space and process in the Traditional Cache. Some infrequently used items however would remain inside the Traditional cache but never make it through the probationary cache. So a small "ghost" cache is used to specifically detect these items rejected from the Probationary cache. Next time we go to fetch a ghost item they go directly into the Traditional cache. The ghost cache is just storing metadata (pointers essentially).
- firstlink 3y ago
  What's the eviction rule from the ghost cache, though? Does it share an eviction queue with the Traditional cache?
  - gridspy 3y ago
    It is the same size as the traditional cache, but it is also a FIFO. Naturally it doesn't need to worry about tracking access, since the moment the ghost cache is "hit" the relevant memory location is loaded into the traditional cache and the ghost cache entry becomes irrelevant. So I guess that means the ghost cache could just be a queue.
- ramses0 3y ago
  So a “bypass probation” ID-only queue.
valleyer 3y ago
This sounds pretty similar to the pageout scan in Mach (i.e., NeXTSTEP, Darwin, macOS, iOS, and derivatives). It's also used by 4.4BSD and some of the modern BSDs. There is an "active" queue and an "inactive" queue. The pageout daemon tries to maintain them in a 1:2 ratio. Active drains to inactive; inactive drains to be paged out. Both are simple FIFO, but the daemon clears the page table referenced bit of pages as they are enqueued onto inactive. When dequeueing a page from inactive, the referenced bit is checked. If it's been set (i.e., the page was referenced since being moved to inactive), the page is diverted back up to active. Otherwise, it's paged out.
- 1a1a11a 3y ago
  This is interesting! Do you have a good reference?
  - valleyer 3y ago
    Not a great one offhand, but here's a decent one from Apple, from back in the days when they put energy into documenting internal stuff like this. (As a result, some of the details in it are slightly out-of-date, but the general shape is still correct.) https://developer.apple.com/library/archive/documentation/Performance/Conceptual/ManagingMemory/Articles/AboutMemory.html https://developer.apple.com/library/archive/documentation/Pe...
    - 1a1a11a 3y ago
      This is very helpful (for someone who has never worked on Darwin)! The algorithm uses two FIFO lists with a "visited" bit (lazy promotion), and is a great idea! There are two differences between what is described and our algorithm, 1. the two FIFO lists are not fix-sized, which cannot guarantee quick demotion; 2. new data (hard fault) are inserted into the active list (I assume it is large than the inactive list), which is different from the quick demotion.
weebull 3y ago
What I'm not getting is... 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?
- 1a1a11a 3y ago
  There are two things. One is reinsertion or lazy promotion as you described, which is used to keep popular objects (reinserted objects have the bit reset to 0, so it won't be infinite loop). And it performs fewer work than LRU because many hits on a popular object result in one "lazy promotion". 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.
  - 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.

gridspy 3y ago

Useful summary. Made me want to read about the ghost cache. The cache layout is: Probationary 10% + Traditional 90% (of memory). The idea is that most items are not requested again prior to dropping out of probationary and so don't take up space and process in the Traditional Cache. Some infrequently used items however would remain inside the Traditional cache but never make it through the probationary cache. So a small "ghost" cache is used to specifically detect these items rejected from the Probationary cache. Next time we go to fetch a ghost item they go directly into the Traditional cache. The ghost cache is just storing metadata (pointers essentially).

firstlink 3y ago
What's the eviction rule from the ghost cache, though? Does it share an eviction queue with the Traditional cache?
- gridspy 3y ago
  It is the same size as the traditional cache, but it is also a FIFO. Naturally it doesn't need to worry about tracking access, since the moment the ghost cache is "hit" the relevant memory location is loaded into the traditional cache and the ghost cache entry becomes irrelevant. So I guess that means the ghost cache could just be a queue.
ramses0 3y ago
So a “bypass probation” ID-only queue.

valleyer 3y ago

This sounds pretty similar to the pageout scan in Mach (i.e., NeXTSTEP, Darwin, macOS, iOS, and derivatives). It's also used by 4.4BSD and some of the modern BSDs. There is an "active" queue and an "inactive" queue. The pageout daemon tries to maintain them in a 1:2 ratio. Active drains to inactive; inactive drains to be paged out. Both are simple FIFO, but the daemon clears the page table referenced bit of pages as they are enqueued onto inactive. When dequeueing a page from inactive, the referenced bit is checked. If it's been set (i.e., the page was referenced since being moved to inactive), the page is diverted back up to active. Otherwise, it's paged out.

1a1a11a 3y ago
This is interesting! Do you have a good reference?
- valleyer 3y ago
  Not a great one offhand, but here's a decent one from Apple, from back in the days when they put energy into documenting internal stuff like this. (As a result, some of the details in it are slightly out-of-date, but the general shape is still correct.) https://developer.apple.com/library/archive/documentation/Performance/Conceptual/ManagingMemory/Articles/AboutMemory.html https://developer.apple.com/library/archive/documentation/Pe...
  - 1a1a11a 3y ago
    This is very helpful (for someone who has never worked on Darwin)! The algorithm uses two FIFO lists with a "visited" bit (lazy promotion), and is a great idea! There are two differences between what is described and our algorithm, 1. the two FIFO lists are not fix-sized, which cannot guarantee quick demotion; 2. new data (hard fault) are inserted into the active list (I assume it is large than the inactive list), which is different from the quick demotion.

weebull 3y ago

What I'm not getting is... 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?

1a1a11a 3y ago
There are two things. One is reinsertion or lazy promotion as you described, which is used to keep popular objects (reinserted objects have the bit reset to 0, so it won't be infinite loop). And it performs fewer work than LRU because many hits on a popular object result in one "lazy promotion". 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.
- 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.