Necko/MemoryCache

The Necko memory cache provides a small in-memory cache for data received from the network. The memory cache device (nsMemoryCacheDevice) implements nsCacheDevice and shares many concepts with the disk cache device (nsDiskCacheDevice).

Data Structures

nsMemoryCacheDevice::mEvictionList is an array of lists (PRCList) of cache entries. These lists keep entries in an order appropriate for LRU-SP eviction (see Automatic Eviction, below). When an entry is added to the memory cache, it is added to one of the lists.

nsMemoryCacheDevice::mMemCacheEntries is a hash table (nsCacheEntryHashTable wraps PLDHashTable) of cache entries. When an entry is added to the memory cache, it is also added to the hash table (in addition to an eviction list), for easy lookup.

Initialization and Shutdown

The memory cache is not persisted across sessions. Data structures are empty (have no entries) following initialization; on shutdown, the eviction lists and hash table are cleared and all entries are deleted.

Adding, Finding, Deleting Entries

BindEntry: Add the entry to the tail of the appropriate eviction list. Add the entry to the hash table. Invoke automatic eviction, if necessary.

DoomEntry/EvictEnty: Remove the entry from its eviction list. Remove the entry from the hash table.

FindEntry: Find the entry in the hash table based on the specified key. Remove the entry from its eviction list, then re-add it to the tail of the appropriate eviction list.

Client Eviction

Client eviction involves an exhaustive search of the eviction lists for entries with the specified key. Matching entries are removed from their eviction list, removed from the hash table, and deleted (or doomed, if in use).

Automatic Eviction

When a new entry is added to the memory cache or an entry’s data size grows such that the total data size exceeds the configured capacity, less relevant entries are evicted until the capacity requirements are met again. To identify which entries to evict and in what order, the LRU-SP cache eviction algorithm is used.

LRU-SP ("size adjusted and popularity aware LRU") is a cache eviction algorithm that tries to improve hit rates over LRU 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 straight-forward:

• keep a small collection 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 the appropriate 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. (The Necko cache diverges from the LRU-SP algorithm in this respect: see bug 661900.)

Eviction Lists

mEvictionList is an array of 24 eviction lists. Entries are assigned to lists according to these rules:

• If the entry has no expiration time, assign it to list 0;
• Else, assign to list (log of the greatest power of 2 less than or equal to the entry’s size divided by the entry’s fetch count), or the last list, list 23, if this list number would otherwise be exceeded.

For example, a 256 byte new entry, with a fetch count of 1, would be assigned to list 8. If this entry is fetched again, it would be moved to list 7 (log2(256/2) = 7).

A Complexity Complication

PLDHashTable operations are typically O(1), but additions/deletions may result in hash table growth/shrinkage.