Memory: slab allocation, calcification and jemalloc

What to evict

The primer uses least recently used (LRU) eviction: new and recently used entries go to the head of a doubly linked list, and the entry at the tail is evicted when the cache is full. Chapter 6 compares LRU with LFU and ARC, and Redis's sampled approximations of them.

Memcached's slab allocator

Memcached divides memory into pages, 1 MB by default. Each page is assigned to a slab class and cut into equal chunks. In the documentation's words, items are "pushed into the slab class of the nearest fit".

How the classes are sized (from slabs.c): the smallest chunk is the item header plus chunk_size (48 + 48 = 96 bytes on 64-bit builds). Each next class multiplies by the growth factor (-f, default 1.25) and rounds up to a multiple of 8:

A chunk holds the whole item: a 48-byte header, 8 bytes of CAS value, the key, the value and terminators, not just the key or value.

Internal waste. An item uses the smallest chunk that fits, and the rest of the chunk is unused. The worst case is an item just over the previous class's size, wasting about $1 - 1/f$ of the chunk: 20% at $f = 1.25$, about 7% at $f = 1.08$. A smaller factor wastes less per item but creates more classes, which spreads pages across more of them.

No holes between items. Chunks in a page are all one size, so a freed chunk is exactly right for the next item of that class.

Slab calcification

Pages are assigned to classes as traffic arrives. If the workload changes, say from many small items to larger ones, the pages that went to the small class stay there even when they are empty. The large class has no free pages, so it evicts recent items while memory sits idle elsewhere.

Memcached's fix is to move pages between classes. The slabs reassign command moves a page from one class to another, and slabs automove runs a background thread that "decides on its own when to move memory between slab classes". In current Memcached source both are on by default (slab_reassign = true, slab_automove = 1). The visual lets you calcify a tiny cache and then run the rebalancer.

Redis's memory

Redis does not use slab pages. It allocates each object through its allocator, by default jemalloc on Linux (chapter 6):

• Every value is wrapped in a 16-byte redisObject header: 4 bits of type, 4 bits of encoding, 24 bits of LRU or LFU data, a 32-bit reference count and a 64-bit pointer.
• Strings of up to 44 bytes use the embstr encoding, which allocates the header and the string together: one allocation instead of two.
• Active defragmentation exists but is off by default (chapter 6).