How Memcached Works Internally: Slab Allocation, the LRU Eviction Engine, and the Multi-Threaded Architecture Behind Sub-Millisecond Caching

Memcached is one of those tools whose reputation precedes its documentation. Most engineers know it as a fast in-memory key-value cache. Fewer know why it is fast, where it breaks down, and what “modern Memcached” means after a decade of architectural changes that most tutorials ignore. This article covers the internals: the slab allocator, the four-tier LRU eviction engine, the multi-threaded libevent architecture, and the protocol evolution from text to meta.

The Slab Allocator

Memcached does not call malloc and free for every stored item. General-purpose allocators add fragmentation over long-running processes, and in a cache where millions of items churn continuously, that fragmentation accumulates until resident memory far exceeds the configured limit. Memcached solves this with a custom slab allocator that pre-partitions memory into size classes and never returns allocations to the OS.

Slab Classes and Chunk Sizing

At startup, Memcached requests a contiguous memory region (the -m flag, defaulting to 64 MB). It divides this region into slabs, where each slab is exactly 1 MB. Each slab belongs to a slab class, and every slab class holds chunks of a fixed size. The chunk size grows by a configurable factor (default 1.25) from a minimum of 96 bytes up to the maximum item size (default 1 MB):

Slab class 1:   chunk size = 96 bytes
Slab class 2:   chunk size = 120 bytes
Slab class 3:   chunk size = 152 bytes
Slab class 4:   chunk size = 192 bytes
...
Slab class 42:  chunk size = 1,048,576 bytes (1 MB)

When you store an item, Memcached rounds the required size up to the nearest slab class and allocates one chunk from a free list in that class. When the item is deleted or evicted, the chunk returns to the free list of its class, not to any global pool. Chunks never move between slab classes.

This design eliminates fragmentation within a class: every chunk in a class is exactly the same size, so there are no gaps. The tradeoff is inter-class waste. An item requiring 97 bytes consumes a 120-byte chunk from class 2, wasting 23 bytes per item. In workloads with highly variable value sizes, this waste compounds. The stats slabs command exposes mem_requested versus chunk_size * used_chunks per class, which is the most direct way to measure how much memory the slab allocator is wasting for your specific workload.

Page Allocation

When a slab class exhausts its free chunks, Memcached allocates a new 1 MB page from the global memory pool and carves it into chunks of that class’s size. Pages are never reclaimed from a class once assigned. This means a class that handled a burst of large items months ago will hold those pages indefinitely, even if the workload has shifted to smaller items. The automove feature (discussed in the production section) exists specifically to address this.

The Item Structure

Each allocated chunk holds a item struct followed by the key and value in the same contiguous block:

typedef struct _stritem {
    struct _stritem *next;  // LRU chain pointer
    struct _stritem *prev;
    struct _stritem *h_next; // hash table chain pointer
    rel_time_t      time;    // last access time
    rel_time_t      exptime; // expiration time (0 = never)
    int             nbytes;  // value length
    unsigned short  refcount;
    uint8_t         nsuffix; // suffix string length
    uint8_t         it_flags;
    uint8_t         slabs_clsid; // owning slab class
    uint8_t         nkey;    // key length
    /* key and value follow in the same allocation */
} item;

The fixed overhead per item is roughly 48 bytes plus the key and value lengths plus alignment padding. For small items (say, 32-byte keys and 64-byte values), this overhead is significant: you are storing 96 bytes of user data inside a 192-byte or 240-byte chunk. That ratio matters when you are sizing a cluster for millions of small keys.

The LRU Eviction Engine

When all slab classes are full and a new item needs to be stored, Memcached must evict something. The eviction policy has changed substantially since the early versions, and modern Memcached (1.5+) uses a four-tier sub-LRU system that is meaningfully different from a naive global LRU.

The Four Sub-LRUs: HOT, WARM, COLD, and TEMP

Each slab class maintains four independent LRU queues:

• HOT: items that were recently set or items that have been accessed more than once since being promoted to WARM. Newly stored items enter HOT.
• WARM: items that have been accessed at least once while in COLD. These are items the system has evidence are actively used.
• COLD: items that have aged out of HOT without being accessed. This is the primary eviction candidate pool.
• TEMP: items with a TTL under a configurable threshold (default 61 seconds). These are not subject to LRU-based eviction; they expire naturally and bypass the sub-LRU promotion logic entirely.

The flow looks like this: new items enter HOT. Items in HOT that get accessed stay in HOT (they get bumped to the head). Items in HOT that age to the tail are moved to COLD, not WARM. Items in COLD that get accessed are promoted to WARM. Items that reach the tail of COLD without being accessed are evicted. Items in WARM that age to the tail cycle back to COLD.

This two-chance design (HOT tail goes to COLD, COLD tail with access goes to WARM, WARM tail cycles to COLD) prevents a single large sequential scan from flushing out your entire working set. A naive LRU would evict your most-valuable hot items if a one-time bulk load touched keys in LRU order. The sub-LRU system resists this because the bulk-loaded items enter HOT and drain to COLD before they can displace established WARM items from eviction consideration.

The LRU Crawler and LRU Maintainer

Memcached uses two dedicated background threads to manage LRU state.

The LRU crawler (lru_crawler) scans slab classes for items that have expired but have not been touched. Memcached uses lazy expiration: an item is only discovered as expired when a GET request fetches it and the server checks exptime. Items that are never fetched after their TTL elapses sit in memory indefinitely unless the crawler removes them. The crawler walks each slab class at a configurable rate (lru_crawler sleep controls the inter-item sleep in microseconds) to avoid saturating I/O on the item lock table.

The LRU maintainer (lru_maintainer) handles inter-queue promotion and demotion: it moves items from HOT to COLD as they age, promotes COLD items to WARM on access, and runs the automove algorithm for slab rebalancing. This background thread decouples eviction bookkeeping from the hot path, so worker threads processing GET and SET commands do not need to do expensive LRU queue maintenance inline.

The Multi-Threaded Architecture

Unlike Redis, Memcached has been multi-threaded from version 1.2. The architecture is a classic main thread + worker pool pattern built on libevent.

The Main Thread

The main thread owns the server socket and runs an epoll/kqueue event loop. When a new TCP connection arrives, the main thread accepts it and assigns it to a worker thread using a round-robin pipe notification mechanism. Each worker thread has its own libevent event base and its own connection queue. The main thread writes the new connection’s file descriptor to a worker’s notification pipe; the worker wakes up, reads the fd, and adds it to its own event loop.

After the initial assignment, the main thread has no further involvement with that connection. All reads, writes, and command processing happen in the assigned worker thread. This means connection distribution is determined at accept time and does not rebalance dynamically: a worker that gets many long-lived connections will see more load than its peers. In practice this is rarely a problem because Memcached connections are typically short-lived or spread by the client library.

Worker Threads

Each worker thread (controlled by the -t flag, default 4) runs an independent libevent event loop. It reads requests from client sockets, parses the protocol, executes the command (which means touching shared data structures), and writes responses back.

The concurrency challenge is that all worker threads share the same slab allocator, hash table, and LRU structures. Memcached uses two locking mechanisms to handle this:

Global mutex for slabs and hash table: A per-operation mutex covers slab class free list access and hash table modifications. In practice, most SET operations are short critical sections, so lock contention is low at typical worker counts (4 to 8 threads on modern hardware).

Item lock table: For item-level access, Memcached uses a hash-based lock table with a fixed number of locks (default 8191, a prime number chosen to minimize clustering). Each item is assigned to one of these locks based on a hash of its key. Two operations on the same key always acquire the same lock. Two operations on different keys usually acquire different locks, so they proceed in parallel. The lock table is the mechanism that makes concurrent GET and SET operations on different keys safe without a single global item lock.

// Lock acquisition for item-level operations
static inline uint32_t item_lock_hashval(uint32_t hv) {
    return hv & hashmask(hashpower);
}

// Worker thread acquiring per-item lock before read or write
item_lock(hv);
// ... access or modify item ...
item_unlock(hv);

The item lock table approach trades some false sharing (two different keys hashing to the same lock bucket block each other unnecessarily) for low memory overhead and predictable lock granularity. At 8191 buckets with 4 worker threads, false-sharing contention is negligible unless you have an extremely skewed key distribution.

The Hash Table

Memcached stores all items in a hash table for O(1) lookups. The table is a chained hash table: each bucket is a pointer to a singly-linked list of items that hash to that bucket (the h_next pointer in the item struct).

Expansion and Migration

The hash table starts at 64K buckets and doubles when the number of stored items exceeds 1.5 times the current bucket count. This threshold keeps average chain lengths short (target is under 1.5 items per bucket).

Expansion happens in the background via a dedicated hash maintenance thread. This thread migrates items from the old table to the new table incrementally: it moves a batch of buckets per iteration, with a configurable sleep between batches. During migration, Memcached uses a flag (expanding) to decide whether to look up items in the old table, the new table, or both. Worker threads check this flag on every hash lookup and acquire the appropriate lock covering both table positions.

This incremental approach means expansion never causes a stop-the-world pause. The cost is added branching on every lookup during the migration window, which lasts seconds to tens of seconds depending on table size and migration rate.

The Protocol Layer

Memcached supports three protocols over TCP (and historically UDP, discussed below).

Text Protocol

The original protocol, still widely used. Commands are human-readable ASCII lines. A SET looks like:

set mykey 0 3600 5\r\n
hello\r\n

Arguments are: key, flags (a 32-bit integer stored with the item, opaque to Memcached), TTL in seconds (0 means no expiry), and byte count of the value. The response is STORED\r\n on success. GET returns VALUE key flags bytes\r\ndata\r\nEND\r\n.

The text protocol’s weakness is that it requires parsing variable-width ASCII fields on every command, which is measurably slower than binary framing at very high throughput.

Binary Protocol

Added in 1.3, the binary protocol uses fixed-width headers (24 bytes per request and response) with a defined opcode byte, key length, extra length, and body length. It eliminates text parsing overhead, supports pipelining without response ambiguity, and adds operations that the text protocol cannot express cleanly, such as quiet GET variants (GETKQ) that suppress NOT_FOUND responses for batch lookups.

The binary protocol also enables noreply semantics with proper framing: the client can fire many SET commands without waiting for STORED responses and then batch-confirm success only when needed.

Meta Protocol

Introduced in Memcached 1.6, the meta protocol is the current recommended interface for new client implementations. It uses a compact token-based syntax where every command starts with a two-letter verb (mg for meta-get, ms for meta-set, md for meta-delete, ma for meta-arithmetic) followed by the key and optional flag tokens:

ms mykey 5 T3600 F0\r\n
hello\r\n

mg mykey v f t\r\n

The mg example requests the value (v), flags (f), and remaining TTL (t) in a single round trip. The meta protocol exposes item metadata that previously required separate commands, supports CAS operations with a unified syntax, and allows returning different subsets of item data without separate command variants. It is also more extensible: new flag tokens can be added without breaking existing parsers that ignore unknown tokens.

Consistent Hashing on the Client Side

Memcached itself has no concept of clustering. There is no gossip protocol, no slot assignment, no replication, no automatic failover. A Memcached deployment is a pool of independent nodes, and the intelligence for distributing keys across that pool lives entirely in the client library.

Early deployments used modulo hashing: server_index = hash(key) % server_count. This is simple but catastrophic when a node goes down: every key’s server assignment changes, invalidating the entire cache and sending all traffic to the database until the cache warms up.

Consistent hashing places both servers and keys on a virtual ring. Adding or removing a server only remaps the keys that were assigned to that server’s arc on the ring, not the entire keyspace. A well-implemented consistent hashing client (libmemcached, Spymemcached, or most modern client libraries) uses virtual nodes: each physical server is represented by many points on the ring (100 to 200 is typical) to distribute load evenly without relying on hash function uniformity alone.

import Memcached from "memcached";

// The client handles consistent hashing internally across this pool.
// Adding or removing a server only remaps keys on that server's arc.
const client = new Memcached([
  "cache1.internal:11211",
  "cache2.internal:11211",
  "cache3.internal:11211",
], {
  retries: 2,
  retry: 3000,
  failures: 3,
  // Consistent hashing is the default in most modern Memcached clients.
  // Verify your client library's default before deploying.
});

client.get("user:42:profile", (err, data) => {
  if (err) throw err;
  if (!data) {
    // Cache miss: fetch from DB and populate
  }
});

The practical implication for capacity planning: when you add a server to expand the pool, expect cache hit rate to drop temporarily as traffic for the remapped key arcs misses until those keys are re-cached. Size your nodes so that a single-node failure or addition causes a manageable spike in database read traffic.

Production Considerations

Memory Overhead Per Item and Slab Waste

For a 20-byte key and a 100-byte value, the total required size is roughly 48 (item struct) + 4 (suffix) + 20 (key) + 100 (value) = 172 bytes. The nearest slab class above 172 bytes might be 192 bytes, meaning 11% waste per item. For very small values (session tokens, boolean flags), the struct overhead can exceed the user data size. Account for this in capacity estimates by checking mem_requested from stats slabs and comparing it to mem_used.

Slab Rebalancing with Automove

If your workload shifts from small items to large items (or vice versa), some slab classes will have idle pages while others run out and start evicting. The slab_automove feature (enabled with -o slab_automove=1) monitors slab class eviction rates. When a class has been evicting for several consecutive seconds and another class has pages with a high ratio of free chunks, automove reassigns one page from the cold class to the hot class. This is a slow process by design: pages are only moved once the evidence of imbalance is consistent, preventing thrashing.

For workloads that shift rapidly, automove may not react quickly enough. The alternative is to pre-size slab classes with -o slab_sizes to match your value size distribution precisely, reducing the need for runtime rebalancing.

Connection Limits and Worker Saturation

The default maximum connections is 1024 (-c 1024). Each connection consumes a small amount of state in the accepting worker thread’s event loop. At high connection counts, the per-worker event loop can saturate even if the per-command processing time is negligible. Increase -c carefully and watch curr_connections and rejected_connections from stats to detect ceiling issues. Deploying a connection pool proxy (mcrouter from Meta is the canonical choice) in front of Memcached nodes reduces the raw connection count that each node must manage.

UDP and Reflection Attack Mitigations

Memcached historically supported UDP on port 11211 for low-overhead reads. In 2018, Memcached became a significant amplification vector in DDoS attacks: a spoofed UDP request of 15 bytes could elicit a response of 100 KB or more, yielding a ~10,000x amplification factor. Attackers used this to generate terabit-scale floods.

The fix is straightforward: disable UDP entirely with -U 0 unless you have a specific operational need for it and are running Memcached exclusively on a private network with source address verification at the router. Memcached 1.5.6+ disables UDP by default. If you are running anything older, check with netstat -anu | grep 11211 and disable immediately.

The stats Command as a Diagnostic Interface

Memcached exposes runtime telemetry through the stats command family. The most useful subcommands for diagnosing production issues:

• stats: global counters including get_hits, get_misses, evictions, bytes_written, curr_items
• stats slabs: per-slab-class allocation, mem_requested vs actual usage, eviction counts per class
• stats items: per-class LRU metadata including ages of the tail item in each sub-LRU queue
• stats conns: per-connection state (useful when debugging connection leak issues)

Tracking evictions over time is the clearest signal that your cache is undersized for the current working set. Track get_misses separately from evictions because misses from cold starts, TTL expiry, and new key space all show up there; evictions specifically indicate pressure-driven removals.

Tradeoffs: Memcached vs Alternatives

Dimension	Memcached	Redis	Valkey	Hazelcast	KeyDB
Threading model	Multi-threaded (worker pool, 4 default)	Single-threaded command execution, optional I/O threads	Single-threaded command execution, improved I/O thread ring buffer	Multi-threaded, Java thread pool per partition	Lock-striped multi-threaded, 2-5x throughput on multi-core
Data structures	Strings only (key-value)	Strings, hashes, lists, sets, sorted sets, streams, geospatial	Same as Redis 7.2	Maps, queues, topics, locks, ring buffers, PN counters	Same as Redis
Persistence	None	RDB snapshots, AOF log, hybrid RDB+AOF	RDB + AOF (same as Redis)	Yes (hot restart, disk persistence)	RDB + AOF (same as Redis)
Cluster mode	None (client-side sharding only)	Redis Cluster (hash slots, gossip)	Valkey Cluster (improved async migration)	Built-in distributed cluster with replication	KeyDB Active Replication, compatible with Redis Cluster
Memory efficiency	Very high for string workloads; slab waste for variable sizes	Adaptive encodings (listpack, intset) reduce overhead for small values	Same as Redis	JVM heap overhead; GC pressure at high item counts	Same as Redis
Protocol	Text, binary, meta (1.6+)	RESP2, RESP3	RESP2, RESP3	Proprietary (IMDG) + REST/SQL interfaces	RESP2, RESP3
Replication	None native	Primary-replica with partial resync (PSYNC2)	Same as Redis	Synchronous or asynchronous replica per partition	Active-active multi-master (conflict-free per key)
Operational maturity	Very high (20+ years), simple ops	Very high, large ecosystem	Growing (Linux Foundation governance)	High, complex (JVM tuning, cluster sizing)	Moderate; smaller community than Redis
Sweet spot	High-throughput string caching where Redis complexity is unnecessary; simplest possible cache layer with maximum memory efficiency	Rich data structure needs, persistence required, Lua scripting, sorted sets	Redis replacement where open license matters more than cutting-edge threading	Java-native deployments, JCache integration, compute-in-data-grid use cases	Redis workloads that need higher multi-core throughput without switching client libraries

Where Memcached Still Makes Sense

Memcached wins in one specific scenario: you want to cache strings at very high throughput across multiple cores without paying for data structure complexity you do not need. The slab allocator’s predictability means memory usage is stable over time without GC pressure or allocator fragmentation. The multi-threaded worker pool uses all available cores without configuration. The meta protocol gives you efficient batching and TTL introspection without the overhead of RESP framing.

Where it loses: no persistence, no replication, no server-side data structure operations, no pub/sub, and no way to do server-side computation on stored values. If your cache needs any of those, you are looking at Redis or Valkey. If you need your cache to survive a restart, you need a different tool entirely.

The fact that Memcached is still running under significant production traffic at Meta, Wikipedia, and major CDN providers twenty years after its initial release is a signal. Not that it is perfect, but that the slab allocator, the LRU engine, and the multi-threaded event loop are a durable foundation for workloads that fit its constraints.