How does Memcached handle memory allocation using the slab allocator mechanism?

Memcached manages memory allocation using a specialized slab allocator mechanism designed to eliminate memory fragmentation and maintain high-speed, constant-time operations. Rather than relying on standard system memory allocation functions like malloc and free for every individual cached item, Memcached pre-allocates memory into fixed-size regions called pages, subdivides them into uniform units called chunks, and groups these chunks into specific slab classes based on size.

Core Elements of the Slab Allocator Architecture

The slab allocation strategy in Memcached relies on three fundamental components working together:

  • Pages: Memory is requested from the operating system in large, continuous blocks called pages, typically 1 MB in size. Pages serve as the foundational units of memory assignment in Memcached.
  • Chunks: Each page assigned to a slab class is divided into smaller, equal-sized slots called chunks. A chunk represents the smallest unit of storage that holds a single cached key-value entry.
  • Slab Classes: Memcached categorizes chunks by size into different slab classes. For example, Class 1 might contain 96-byte chunks, Class 2 might contain 120-byte chunks, and Class 3 might contain 152-byte chunks.

The Allocation Process

When an application sends a key-value item to Memcached, the engine executes a specific allocation flow to store the item:

  1. Class Selection: Memcached calculates the total size required for the item (including key, value, and internal metadata). It searches its ordered list of slab classes to locate the smallest chunk size capable of holding the data.
  2. Best-Fit Assignment: The data is placed into an available free chunk inside that target slab class.
  3. Page Expansion: If all chunks in the selected slab class are currently in use, Memcached assigns a new 1 MB page from the global free pool to that slab class, dividing the page into additional chunks of that class's fixed size.

Growth Factor and Size Progression

The increment in chunk size between successive slab classes is governed by a growth factor parameter (configurable via -f, with a default value of 1.25).

With a growth factor of 1.25, each slab class features chunks approximately 25% larger than those of the preceding class. A lower growth factor creates finer granularity between chunk sizes, reducing internal unused space within a chunk at the cost of managing more slab classes. A higher growth factor reduces the number of classes but can increase internal memory waste.

Memory Trade-Offs and Internal Fragmentation

While the slab allocator successfully prevents external memory fragmentation—where system memory becomes broken up into unallocated, unusable gaps—it introduces internal fragmentation.

Internal fragmentation occurs when an item's exact size is smaller than the assigned chunk size. For instance, storing a 70-byte payload inside a 96-byte chunk leaves 26 bytes of unused space within that specific chunk. Because chunks are uniform and atomic, that extra space cannot be reclaimed or allocated to other items.

Recycling Memory and Evictions

When memory reaches capacity or free chunks run out within a specific class, Memcached reclaims space through built-in mechanisms:

  • Free List Reuse: When items are updated or deleted, their occupied chunks are returned directly to the target slab class's free list for instant reuse.
  • Lazy Deletion: Expired items are not proactively swept from memory by a background cleaner; instead, their space is reclaimed when requested by a client or when new data needs to occupy the slot.
  • LRU Eviction: When a slab class has exhausted all allocated chunks and no unallocated 1 MB pages remain in the global pool, Memcached uses a Least Recently Used (LRU) algorithm to evict old items specifically within that slab class to free up chunks for new writes.