5

Chromium Disk Cache docs state:

Right now we have a simple Least Recently Used algorithm that just starts deleting old entries once a certain limit is exceeded, and a second algorithm that takes reuse and age into account before evicting an entry.

However, when testing a website with repetitive requests in my Chrome, I noticed that a large 5 MB file is constantly evicted from the cache when the cache is full, while smaller files are kept cached.

Are the docs on cache eviction wrong, or is there any other explanation for the behavior?

1 Answer 1

6
+100

The explanation is simple enough : Chrome(ium) does not use a "simple Least Recently Used algorithm".

An examination of the Chromium source file MemoryCache.cpp finds this line of code at its very end, containing a debug routine that prints out the cache:

printf("LRU-SP lists in eviction order (Kilobytes decoded, Kilobytes encoded, Access count, Referenced, isPurgeable, wasPurged):\n"); 

The LRU-SP algorithm was first described in the paper LRU-SP: A Size-Adjusted and Popularity-Aware LRU Replacement Algorithm for Web Caching, presented in the Twenty-Fourth Annual International Computer Software and Applications Conference.

A description of the algorithm is given in the post What cache replacement strategies do various popular web browsers use?, contributed by Felix Gessert:

LRU-SP extends the classic Least-Recently-Used (LRU) algorithm to take the varying object sizes (1) into account. Varying latencies (2) aren't considered. LRU-FP is an extension of PSS (Pyramidal Selection Scheme). The LRU-SP algorithm works like this:

  • Each object x gets assigned to a class: enter image description here
  • Each class maintains a separate LRU list

  • Each time a cached object is requested it might change the class according to the above formula

  • When an object needs to be replaced, the algorithm looks at the least recently used (i.e. oldest) objects in each LRU list and chooses the object x with the smallest enter image description here with R being the number of requests to a cached object, since it was fetched the last time

(1) Revitalizing Caching

(2) LRU-SP: A Size-Adjusted and Popularity-Aware LRU Replacement Algorithm for Web Caching

I would guess that in your case the formula "size / accesses" gave a large value, as this was a large file accessed only once, so this file of 5 MB was the first candidate for eviction.

2
  • What is the difference between R(x) (number of requests to object) and accessFrequency? Isn't "request" and "access" are synonimous? Commented Aug 25, 2021 at 9:38
  • 1
    For a browser, "request" and "access" should be the same. "Frequency" is number over time, but the implementation is undefined so seems left to the developer. Commented Aug 25, 2021 at 9:50

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.