RAM Cache

New RAM Cache Algorithm (CLFUS)

The new RAM Cache uses ideas from a number of cache replacement policies and algorithms, including LRU, LFU, CLOCK, GDFS and 2Q, called CLFUS (Clocked Least Frequently Used by Size). It avoids any patented algorithms and includes the following features:

• Balances Recentness, Frequency and Size to maximize hit rate (not byte hit rate).

• Is Scan Resistant and extracts robust hit rates even when the working set does not fit in the RAM Cache.

• Supports compression at 3 levels: fastlz, gzip (libz), and xz (liblzma). Compression can be moved to another thread.

• Has very low CPU overhead, only slightly more than a basic LRU. Rather than using an O(lg n) heap, it uses a probabilistic replacement policy for O(1) cost with low C.

• Has relatively low memory overhead of approximately 200 bytes per object in memory.

The rationale for emphasizing hit rate over byte hit rate is that the overhead of pulling more bytes from secondary storage is low compared to the cost of a request.

The RAM Cache consists of an object hash fronting 2 LRU/CLOCK lists and a seen hash table. The first cached list contains objects in memory, while the second contains a history of objects which have either recently been in memory or are being considered for keeping in memory. The seen hash table is used to make the algorithm scan resistant.

The list entries record the following information:

Value	Description
key	16 byte unique object identifier
auxkeys	8 bytes worth of version number (in our system, the block in the partition). When the version of an object changes old entries are purged from the cache.
hits	Number of hits within this clock period.
size	size of the object in the cache.
len	Length of the object, which differs from size because of compression and padding).
compressed_len	Compressed length of the object.
compressed	Compression type, or none if no compression. Possible types are: fastlz, libz, and liblzma.
uncompressible	Flag indicating that content cannot be compressed (true), or that it mat be compressed (false).
copy	Whether or not this object should be copied in and copied out (e.g. HTTP HDR).
LRU link
HASH link
IOBufferData	Smart point to the data buffer.

The interface to the cache is Get and Put operations. Get operations check if an object is in the cache and are called on a read attempt. The Put operation decides whether or not to cache the provided object in memory. It is called after a read from secondary storage.

Seen Hash

The Seen List becomes active after the Cached and History lists become full following a cold start. The purpose is to make the cache scan resistant, which means that the cache state must not be affected at all by a long sequence Get and Put operations on objects which are seen only once. This is essential, and without it not only would the cache be polluted, but it could lose critical information about the objects that it cares about. It is therefore essential that the Cache and History lists are not affected by Get or Put operations on objects seen the first time. The Seen Hash maintains a set of 16 bit hash tags, and requests which do not hit in the object cache (are in the Cache List or History List) and do not match the hash tag result in the hash tag being updated but are otherwise ignored. The Seen Hash is sized to approximately the number of objects in the cache in order to match the number that are passed through it with the CLOCK rate of the Cached and History Lists.

Cached List

The Cached List contains objects actually in memory. The basic operation is LRU with new entries inserted into a FIFO queue and hits causing objects to be reinserted. The interesting bit comes when an object is being considered for insertion. A check is first made against the Object Hash to see if the object is in the Cached List or History. Hits result in updating the hit field and reinsertion of the object. History hits result in the hit field being updated and a comparison to see if this object should be kept in memory. The comparison is against the least recently used members of the Cache List, and is based on a weighted frequency:

CACHE_VALUE = hits / (size + overhead)

A new object must be enough bytes worth of currently cached objects to cover itself. Each time an object is considered for replacement the CLOCK moves forward. If the History object has a greater value then it is inserted into the Cached List and the replaced objects are removed from memory and their list entries are inserted into the History List. If the History object has a lesser value it is reinserted into the History List. Objects considered for replacement (at least one) but not replaced have their hits field set to 0 and are reinserted into the Cached List. This is the CLOCK operation on the Cached List.

History List

Each CLOCK, the least recently used entry in the History List is dequeued and if the hits field is not greater than 1 (it was hit at least once in the History or Cached List) it is deleted. Otherwise, the hits is set to 0 and it is requeued on the History List.

Compression and Decompression

Compression is performed by a background operation (currently called as part of Put) which maintains a pointer into the Cached List and runs toward the head compressing entries. Decompression occurs on demand during a Get. In the case of objects tagged copy, the compressed version is reinserted in the LRU since we need to make a copy anyway. Those not tagged copy are inserted uncompressed in the hope that they can be reused in uncompressed form. This is a compile time option and may be something we want to change.

There are 3 algorithms and levels of compression (speed on an Intel i7 920 series processor using one thread):

Method	Compression Rate	Decompression Rate	Notes
fastlz	173 MB/sec	442 MB/sec	Basically free since disk or network will limit first; ~53% final size.
libz	55 MB/sec	234 MB/sec	Almost free, particularly decompression; ~37% final size.
liblzma	3 MB/sec	50 MB/sec	Expensive; ~27% final size.

These are ballpark numbers, and your millage will vary enormously. JPEG, for example, will not compress with any of these (or at least will only do so at such a marginal level that the cost of compression and decompression is wholly unjustified), and the same is true of many other media and binary file types which embed some form of compression. The RAM Cache does detect compression level and will declare something incompressible if it doesn’t get below 90% of the original size. This value is cached so that the RAM Cache will not attempt to compress it again (at least as long as it is in the history).