Engineering Atlas › System Design Interviews

Memcached for system design interviews

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

A cache with nothing extra

A Memcached server is a hash table in RAM behind a network front end. Each item carries a TTL and a 32-bit flags field clients use for things like "compressed". There are no secondary structures, no multi-key transactions and no server-to-server traffic, so a node is cheap to run and easy to reason about.

Sharding is the client's job

Clients hash each key onto a consistent-hash ring (ketama is the classic scheme) and talk directly to the owning server, so adding a 51st server remaps about 1/51 of keys. Large fleets put a proxy in front, such as mcrouter or the proxy built into Memcached since 1.6.23, for routing by key prefix, named pools, fan-out writes, failover and connection pooling (Memcached docs).

Look-aside caching

The application reads the cache; on a miss it reads the database and sets the value. On a database write it deletes the key rather than updating it, because two racing sets can leave the older value behind. Facebook's leases extend this: on a miss the server hands out a token, only its holder may fill the key, and others wait or take a stale value, which stops thundering herds and stale writes. Facebook issued at most one token per key every 10 seconds, and on herd-prone keys that cut the peak database query rate from 17,000 to 1,300 per second (Nishtala et al., NSDI 2013).

Down the stack

Layer 1The contract

Memcached promises only best-effort storage. A set that returns STORED may be evicted a millisecond later; a server restart loses everything; a network partition makes keys on that server simply miss. Per key, operations are atomic: incr, add (store only if absent) and cas (store only if the CAS unique still matches) are safe under concurrency. TTLs up to 30 days are relative seconds; larger numbers are read as Unix timestamps, a classic source of keys that expire instantly. Keys are limited to 250 bytes (protocol docs). Latency is typically 100 to 300 us per request inside a data centre, dominated by the network.

Layer 2The mechanism

Threads. One listener thread accepts connections and hands each to a worker thread round-robin, signalling it over a pipe. Each worker (-t, default 4 per the man page) runs its own libevent loop over its connections, so a connection is always served by the same thread. Background threads handle hash table expansion, the LRU maintainer, the LRU crawler (which reclaims expired items) and slab rebalancing.

Hash table. A single chained hash table, sized as a power of two (hashpower, starting at 2^16 buckets). When items exceed 1.5 times the bucket count, an expansion thread grows the table while workers keep serving. Concurrency comes from a striped array of item locks keyed by hash, so two workers only contend when their keys share a stripe.

Slab allocator. Memory is carved into pages, 1 MB by default (matching the maximum item size -I). Slab classes have chunk sizes growing by the factor -f (default 1.25) from a small minimum around 96 bytes: 96, 120, 152, 192 and so on, up to half a page, with a final class for full-page items. A page belongs to exactly one class and is cut into equal chunks. An item (header of roughly 48 to 56 bytes plus key plus value) goes into the smallest chunk that fits. A 130-byte item uses a 152-byte chunk, wasting 22 bytes. When a class has no free chunk, the server assigns it a new page if any remain under -m; otherwise it evicts from that class's LRU. Pages assigned to one class stay there unless the slab rebalancer moves them, which it does when one class keeps evicting while another has idle pages. Since 1.5.0 the rebalancer is on by default (slab_reassign true, slab_automove=1) as part of the former -o modern bundle (release notes, source).

Segmented LRU. Since 1.5 each class has HOT, WARM and COLD queues (plus TEMP for very short TTLs). New items enter HOT, which is never bumped and acts as a probation queue; the LRU maintainer moves items down; an item that becomes active while in COLD is queued for an asynchronous move to WARM. Evictions take from the COLD tail. This became the default in 1.5.0 (memcached.org). It replaced the older rule of bumping an item at most once per 60 seconds, which existed so a hot key did not take the LRU lock on every read.

Protocols. The text protocol (get k1 k2, set k flags ttl bytes) is human-readable. The meta protocol (mg, ms, md, ma, 1.6+) adds flags such as returning a stale value with a "win" (W) flag so exactly one client refreshes, while later clients see Z and keep serving the stale copy (meta protocol). Extstore keeps keys in RAM but moves large values to flash.

Layer 3The machine

Every request is a short syscall dance: epoll_wait returns, read pulls the request, a hash lookup touches a bucket and an item header (two or three cache misses, a few hundred nanoseconds), and sendmsg writes the value. Multi-get batches amortise this; a get of 100 keys in one request costs far less than 100 round trips. With enough threads and NIC queues, a single modern server can serve several million small gets per second, at which point the NIC and interrupts are the limit (hedge: published numbers range from 1 to over 10 million depending on hardware and batching). Lock granularity matters as much as threads: Facebook's finer-grained locking tripled one server's peak hit rate from 600,000 to 1.8 million items per second. Facebook also moved gets to UDP to avoid per-connection TCP state, treating the 0.25 percent of gets dropped at peak as misses (NSDI 2013 paper). Stock Memcached went the other way: UDP has been off by default since 1.5.6 because open UDP ports were being abused for reflection attacks (release notes).

The slab design comes from malloc behaviour under churn: many allocations and frees of varied sizes fragment the heap until resident memory far exceeds live data. Fixed-size chunks never fragment, and allocation is popping a free list. The cost moves to internal waste (up to about 20 percent with factor 1.25) and to slab calcification, where yesterday's size distribution owns the pages today's traffic needs.

Why it's built this way

  1. RAM is the expensive resource in a cache fleet, so memory overhead per item must be small and predictable; that rules out general-purpose malloc with its fragmentation.
  2. Fixed chunks bring internal waste and calcification, so the server adds tunable growth factors and a background page rebalancer.
  3. A cache can always be refilled from the database, so replication and persistence are not worth their CPU and network cost; clients handle failure as misses.
  4. Without server-side clustering, servers stay simple, and consistent hashing in the client keeps remapping small when the fleet changes.
  5. Small requests are dominated by per-request syscalls, so many threads and multi-get batching are how one box uses all its cores.

Diagram

flowchart TD
    S["set key (130 B item)"] --> H["hash key, lock item stripe"]
    H --> C["pick slab class: 152 B chunks"]
    C --> F{"free chunk in class?"}
    F -->|"yes"| W["write item, link into HOT LRU"]
    F -->|"no"| P{"unassigned page left?"}
    P -->|"yes"| A["assign 1 MB page, cut into chunks"]
    A --> W
    P -->|"no"| E["evict tail of this class's COLD LRU"]
    E --> W

Worked example

A catalogue service caches product JSON: 30 million hot products, 1.8 KB average, 400,000 reads per second at peak.

An item of about 1.9 KB with header and key lands in the roughly 2.3 KB class at the default factor, so 30 million items need about 69 GB. On 64 GB servers giving 54 GB to Memcached (-m 55296), two servers would almost fit; the fleet runs 6, which survives a node loss and keeps each near 67,000 requests per second. At a 95 percent hit rate, Postgres sees 20,000 reads per second.

Six months later the average value is 3 KB and the hit rate falls to 85 percent although total memory looks fine: pages are still held by the 2.3 KB class while the 3.6 KB class evicts. On 1.5.0 and later the default rebalancer (slab_automove=1) notices the skew and migrates pages over minutes; on an older build, or with automove turned off, the operator must enable it or restart, and the hit rate recovers once pages move. A growth factor of 1.08 would also cut per-item waste from up to 20 percent to under 8 percent, at the cost of more classes.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
MemcachedMultithreaded, predictable memory, very simpleOnly opaque values; no replication or persistenceLarge look-aside cache of serialised objects
RedisRich types, replication, persistence, scriptingOne execution thread per shard, fork memory overheadCounters, leaderboards, queues, sessions
In-process cacheNanosecond access, no networkPer-host duplication, harder invalidationTiny hot sets, config, read-mostly reference data
CDN or HTTP cacheOffloads whole responses at the edgeCoarse invalidation, public responses onlyCacheable pages and assets

Pitfalls in production

Leadership lens

Check yourself

  1. Why does Memcached use a slab allocator instead of malloc?

    Show answer

    Fixed-size chunks never fragment and allocate in constant time, so memory use stays predictable under churn; the cost is internal waste and per-class eviction.

  2. Total memory is half free but one slab class is evicting heavily. How?

    Show answer

    Pages are assigned to classes and stay there; the free memory belongs to other classes. The rebalancer or a restart is needed to move pages.

  3. Why delete on write instead of updating the cached value?

    Show answer

    Delete is idempotent and cannot reorder badly; two concurrent updates can leave the older value cached indefinitely.

  4. What do leases fix?

    Show answer

    Only one client per key gets permission to fill a miss, which prevents thundering herds, and a delete invalidates outstanding tokens so stale fills are rejected.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →