Closed Bug 648605 Opened 10 years ago Closed 10 years ago

HTTP cache: Use smarter than plain LRU for small (mobile) disk caches

Categories

(Core :: Networking: Cache, defect)

ARM
All
defect
Not set
normal

Tracking

()

RESOLVED WONTFIX

People

(Reporter: jduell.mcbugs, Assigned: gbrown)

References

(Blocks 1 open bug)

Details

(Keywords: mobile, perf)

Attachments

(2 files, 1 obsolete file)

So the memory cache apparently implements a "Size-Adjusted and Popularity-Aware LRU Algorithm":

http://mxr.mozilla.org/mozilla-central/source/netwerk/cache/nsMemoryCacheDevice.cpp#52

AFAIK the disk cache just does plain old LRU.  Given the tiny size (sometimes 6-8 MB max!) of some fennec device's HTTP disk cache, we may want to implement the memory cache algorithm, or some other algorithm that does even better (a review of the literature might be in order--the article the memory cache is using is from a paper published in 2000).  These could be useful starting points (gotten from 30-second Google search of papers that cite the LRU-SP paper):

  http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5342239

  http://portal.acm.org/citation.cfm?id=954341

Depending on how we implement cache priorities, this may be a dupe of bug 578541.  But we could also possibly implement this separately (and sooner).
No longer blocks: 644431
LRU-SP has its problems as well, see my remarks in bug 397275. I think you still need some kind of timeout-mechanism, otherwise very small objects will never be cleared.
Blocks: 645848
Assignee: nobody → gbrown
@jo: thanks--that's good to know.  Seem like LRU-SP isn't optimal as implement.
ARC is a highly cited improvement to LRU, but I see that it was discussed in bug 512849, and passed over because of patent concerns. I am going to assume that ARC is not a potential solution for this bug.
(In reply to comment #1)
> LRU-SP has its problems as well, see my remarks in bug 397275. I think you
> still need some kind of timeout-mechanism, otherwise very small objects will
> never be cleared.

Looking at the LRU-SP implementation for the memory cache, it seems to me that evictions occur strictly in the order of the eviction lists: http://mxr.mozilla.org/mozilla-central/source/netwerk/cache/nsMemoryCacheDevice.cpp#368. Note that eviction lists (correctly) group items based on Si/nrefi (size and number of fetches).

However, the LRU-SP paper says "The extended cost-to-size model is applied to the eviction candidates from all nonempty groups, purging the object with largest (Ti x Si/nrefi)." (Ti is "elapsed time from last access to current time"). (Also, figure 5 has a note "evict object with maximum (atime*size/nref)".

The memory cache implementation seems like a significant departure from LRU-SP in this regard and this might be related to the short-comings reported by Jo. On the other hand, our implementation is simpler / faster than the LRU-SP algorithm, and the memory cache header comment only claims to implement a "variation" of LRU-SP -- so I wonder if the difference is intentional. Does anyone know?
(In reply to comment #4)
> ... I wonder if the difference is intentional. Does anyone know?

I didn't hear from anyone, so went ahead and created bug 661900. I also tried making the memory cache use true-LRU-SP: it seems to work fine, and alleviates the problem of small unused entries not being evicted.
Keywords: mobile, perf
OS: Mac OS X → All
Hardware: x86 → ARM
This patch works for me, and passes all xpcshell tests. LRU-SP eviction works the same as the memory cache and includes the fix for bug 661900. The implementation uses the same data structures and algorithms as the memory cache, which raises a concern: the disk cache per-record overhead increases by 12 bytes.

I will write up an array-based solution to reduce the memory overhead and compare the performance...
This patch works for me, and passes all xpcshell tests. LRU-SP eviction works the same as the memory cache and includes the fix for bug 661900. The implementation uses the data structures and algorithms similar to the existing disk cache, and with exactly the same per-record memory use as the existing disk cache.
Some background info:

LRU-SP ("size adjusted and popularity aware LRU") is a cache eviction algorithm that tries to improve hit rates by:
 - tending to evict larger items over smaller items
 - tending to evict items with fewer accesses over items with more accesses 
 - tending to evict less recently used items

The LRU-SP algorithm is fairly straight-forward: 
 - Keep a small number (say, 24) of LRU queues. 
 - Assign each new item to a queue based on size and number of fetches.
 - When an item's size or number of fetches changes, remove it from its queue and re-add it to the MRU-end of a (possibly new) queue based on new size and number of fetches.
 - When eviction is required, examine the items at the LRU-end of each queue and calculate a cost based on size, number of fetches, and last access time; evict the item with greatest cost.

Our memory cache implements each LRU queue with a PRCList, and speeds up record lookup with a PLDHashTable: Each item in the memory cache is on a list and also pointed to by a hash table entry. Items are in LRU order on each list; eviction is a simple matter of examining the tail of each list.

Our existing disk cache is a simple array-based LRU cache with a couple of peculiarities. A 16 byte record provides a mapping from hash number to disk locations and includes a time-based "eviction rank" which effectively provides the LRU order. Records are distributed between 32 "buckets" based on hash number. Physically, each bucket is a segment of a single array of records. Lookup involves using the hash number to select a bucket, then iterating over the entire bucket until a match is found. Records are not ordered (simplifying deletion), so eviction involves an iterative search for the record with max eviction rank (again, this is mitigated by keeping per-bucket max eviction ranks, so that the bucket containing the max record can be identified and the search limited to a single bucket).
Added dependency on bug 651011 (too much I/O when cache invalidated) since LRU-SP necessitates a change to the map file format, and thus a change to the cache version number.
Depends on: 651011
Implementing LRU-SP efficiently in the disk cache is challenging. Two of the most frequent cache operations are "find" (is this page in the cache?) and "evict" (a new page is being visited; make room for it by deleting the least relevant content). "Find" requires lookup by hash number; "evict" requires lookup by LRU order. The memory cache implements both lookups efficiently by keeping each record in both a hash table and an LRU-ordered list, but the increased memory overhead seems inadvisable for the disk cache. (On desktop, consider a 500 MB cache with, say, 100000 entries; an extra 12 bytes per entry requires an extra 1.2 MB of memory use.) Using the traditional/existing disk cache strategy of unordered records kept in an array allows for an LRU-SP implementation without any additional memory use, but requires an exhaustive search for each "find" and each "evict". The existing disk cache mitigates these searches by segmenting the array into 32 buckets, accessed by hash number; this optimization is not possible with LRU-SP since the algorithm requires segmentation based on size and number of references. 

An additional problem for disk cache LRU-SP eviction is that the eviction choice is based on DataSize, FetchCount, and LastFetched - attributes which are not generally in memory. Calls to ReadDiskCacheEntry provide the required info, but introduce additional disk reads at eviction time.


I expect LRU-SP will increase the number and relevance of entries in the disk cache, translating to improved hit rates. This benefit should be weighed against the additional CPU use and disk access required by the implementation....but how? Your ideas welcome!
The attached patches implement LRU-SP in the disk cache, but not efficiently (see Comment 10 particularly). I don't have any ideas for overcoming the deficiencies, and cannot advocate going forward with either patch. We might consider starting over with a separate research effort into designing a better disk cache, but then again, there are numerous promising efforts to improve the disk cache with the existing design too. 

Marking as WONTFIX.
Status: NEW → RESOLVED
Closed: 10 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.