Key-Value Stores

Before Redis became ubiquitous, before key-value stores were a recognized database category, there was Memcached. Created by Brad Fitzpatrick in 2003 for LiveJournal, Memcached was the first widely-adopted distributed memory caching system, and it fundamentally changed how we build scalable web applications.

Memcached's design philosophy is radical simplicity: store key-value pairs in memory, expire them after a timeout, and do nothing else. No persistence, no data structures, no clustering—just blazingly fast, distributed caching. This constraint-driven design made Memcached extraordinarily reliable and performant at its core use case.

While Redis has overtaken Memcached in popularity due to its richer features, Memcached remains a compelling choice for pure caching workloads. Companies like Facebook, Twitter, YouTube, and Wikipedia still run massive Memcached deployments handling millions of requests per second. Understanding Memcached helps you appreciate when simplicity wins over capability.

Memcached's architecture is designed for one purpose: serving cached data as fast as possible. Every design decision optimizes for this goal.

Core characteristics:

• In-memory only: All data lives in RAM. No persistence to disk. Restart = empty cache.
• Key-value only: Keys (up to 250 bytes), values (up to 1MB by default). No data structures.
• Stateless servers: Each Memcached server is independent. No inter-server communication.
• Client-side distribution: Clients decide which server holds which key. Servers don't coordinate.
• LRU eviction: When memory is full, least recently used items are evicted.
• Multi-threaded: Unlike Redis, Memcached uses multiple threads for concurrent request handling.

Threading model:

Memcached uses a multi-threaded, event-driven architecture:

┌─────────────────────────────────────────────────────────────────┐
│                     Memcached Server                            │
├─────────────────────────────────────────────────────────────────┤
│  Main Thread (listener)                                         │
│  ├── Accepts new connections                                    │
│  └── Distributes to worker threads                              │
├─────────────────────────────────────────────────────────────────┤
│  Worker Threads (configurable, default 4)                       │
│  ├── Each thread handles subset of connections                  │
│  ├── Event-driven (libevent): handles many connections/thread   │
│  └── Lock-free where possible, fine-grained locks otherwise     │
├─────────────────────────────────────────────────────────────────┤
│  Memory: Slab Allocator                                          │
│  ├── Fixed-size chunks avoid fragmentation                      │
│  └── LRU per slab class                                         │
└─────────────────────────────────────────────────────────────────┘

Why multi-threaded matters:

Memcached can utilize multiple CPU cores, which Redis (single-threaded command processing) cannot. For extremely high-throughput workloads on multi-core machines, Memcached can achieve higher total throughput per instance.

However, this comes with trade-offs:

• More complex internal locking
• Less predictable per-request latency (lock contention)
• Harder to reason about behavior under load

One of Memcached's most important internal mechanisms is its slab allocator—a memory management system designed to eliminate fragmentation that plagued earlier caching systems.

The fragmentation problem:

In a naïve cache, you allocate memory for each item when stored and free it when evicted. With items of varying sizes constantly being added and removed, memory becomes fragmented—free space exists but in pieces too small to use. Eventually, the cache can't store new items even with plenty of 'free' memory.

Slab allocation solution:

Memcached pre-allocates memory into fixed-size chunks organized into 'slab classes':

Slab Class 1:  88-byte chunks   (for items up to 88 bytes)
Slab Class 2: 112-byte chunks   (for items up to 112 bytes)
Slab Class 3: 144-byte chunks   (for items up to 144 bytes)
...
Slab Class N: 1MB chunks        (for items up to 1MB)

Each slab class handles items of similar size:

1. Memory is divided into 1MB pages
2. Each page is assigned to a slab class
3. Page is divided into fixed-size chunks
4. Items are stored in smallest chunk that fits
5. When freed, chunk goes back to slab class freelist

Internal fragmentation vs external fragmentation:

• External fragmentation (eliminated): No unusable memory gaps between allocations
• Internal fragmentation (accepted): Some wasted space within chunks (item smaller than chunk)

This trade-off is deliberate: predictable, bounded waste is better than unpredictable fragmentation that grows over time.

Tuning slab allocation:

# Adjust growth factor (smaller = more classes, less waste, more memory overhead)
memcached -f 1.05  # 5% growth between classes

# Set minimum chunk size
memcached -n 48    # Minimum 48 bytes for key+value+flags

# Enable slab reassignment (move pages between classes)
memcached -o slab_reassign

# View slab statistics
stats slabs
stats items

The slab calcification problem:

With fixed slab class assignments, a class that was initially popular may become underutilized while others need more space. Memcached 1.4.11+ introduced slab rebalancing:

# Automatic reassignment
memcached -o slab_reassign,slab_automove=1

This moves pages from underutilized slab classes to those under pressure.

Unlike Redis Cluster (where servers coordinate), Memcached servers are completely independent. Distribution is entirely the client's responsibility—the client decides which server holds each key.

How it works:

Client wants to store key "user:123:profile"
  ↓
Client hashes key: hash("user:123:profile") = 2847593
  ↓
Client maps hash to server: 2847593 % 3 = 1 → server 1
  ↓
Client sends SET directly to server 1

Simple modulo hashing:

servers = ["cache1:11211", "cache2:11211", "cache3:11211"]
server_index = hash(key) % len(servers)
target_server = servers[server_index]

The problem with modulo:

When adding or removing servers, nearly all keys remap to different servers:

# 3 servers: hash(key) % 3 = 1 → server 1
# Add server: hash(key) % 4 = 2 → server 2 (different!)

After adding one server, ~75% of keys now hash to different servers. This causes a cache stampede—massive cache miss rate triggering overwhelming database load.

Consistent hashing:

Consistent hashing solves the rehashing problem. Servers and keys are both mapped onto a circular hash ring:

                    0°
                    │
            ┌───────┴───────┐
           S3               S1
            │               │
     270°───┼───────────────┼───90°
            │               │
           S2              (S3)
            └───────┬───────┘
                    │
                  180°

Key lookup: hash(key) → position on ring → walk clockwise to first server

Why consistent hashing helps:

When a server is added or removed, only keys that were (or would be) on that server are affected—roughly 1/N of keys, not N-1/N:

# Adding server S4 between S1 and S2:
# Only keys between S4 and S1 remap (from S1 to S4)
# All other keys unchanged

Virtual nodes (vnodes):

Consistent hashing can create imbalanced load if servers have uneven positions on the ring. Virtual nodes solve this by placing each physical server at multiple positions:

Server 1 → vnode1-1, vnode1-2, vnode1-3, ... vnode1-150
Server 2 → vnode2-1, vnode2-2, vnode2-3, ... vnode2-150
Server 3 → vnode3-1, vnode3-2, vnode3-3, ... vnode3-150

With many vnodes per server, the statistical distribution becomes even, and load balances naturally.

Client library support:

Most Memcached clients support consistent hashing:

# Python pylibmc
import pylibmc
mc = pylibmc.Client(
    ["cache1:11211", "cache2:11211", "cache3:11211"],
    behaviors={"ketama": True}  # Consistent hashing (ketama algorithm)
)

Memcached's protocol is intentionally simple—a text-based format that's human-readable and easy to debug. While a binary protocol exists for efficiency, the text protocol remains widely used for its simplicity.

Core commands:

Example session:

$ telnet localhost 11211
Connected to localhost.

# Store a value
set user:123:name 0 300 5
Alice
STORED

# Retrieve the value
get user:123:name
VALUE user:123:name 0 5
Alice
END

# Increment a counter
set pageviews:home 0 0 1
0
STORED
incr pageviews:home 1
1
incr pageviews:home 1
2

# Compare-and-swap for safe updates
gets user:123:balance
VALUE user:123:balance 0 3 12345
100
END
cas user:123:balance 0 300 3 12345
200
STORED

Command parameters:

• flags: 32-bit integer stored with value (often used for serialization format)
• exptime: Expiration in seconds (0 = never, <30 days = relative, >30 days = Unix timestamp)
• bytes: Exact byte length of value (must match!)
• cas: CAS (check-and-set) token for optimistic locking

Multi-get efficiency:

Memcached's multi-get is crucial for performance. Instead of:

get user:1:profile
get user:2:profile
get user:3:profile

Use:

get user:1:profile user:2:profile user:3:profile

This reduces round trips from 3 to 1—a massive latency improvement.

Memcached's CAS (Compare-And-Swap) mechanism enables safe concurrent updates without distributed locks. This is essential for use cases like counters, balances, and any read-modify-write pattern.

The lost update problem:

Without CAS, concurrent updates can overwrite each other:

Time 0: balance = 100
Time 1: Client A: GET balance → 100
Time 2: Client B: GET balance → 100
Time 3: Client A: SET balance = 100 + 50 = 150  ✓
Time 4: Client B: SET balance = 100 - 30 = 70   ✗ (overwrites A's update!)
Time 5: balance = 70 (should be 120)

Client B's update was based on stale data and overwrote Client A's deposit.

CAS solution:

Every value has a CAS token (unique identifier that changes on each update):

Time 0: balance = 100, CAS = 5
Time 1: Client A: GETS balance → 100, CAS = 5
Time 2: Client B: GETS balance → 100, CAS = 5
Time 3: Client A: CAS balance = 150 (if CAS = 5) → SUCCESS, CAS = 6
Time 4: Client B: CAS balance = 70 (if CAS = 5) → FAIL (CAS mismatch!)
Time 5: Client B: GETS balance → 150, CAS = 6 (retry with fresh data)
Time 6: Client B: CAS balance = 120 (if CAS = 6) → SUCCESS, CAS = 7
Time 7: balance = 120 ✓ (both updates applied correctly)

CAS workflow:

1. GETS — Read value with CAS token
2. Compute — Calculate new value
3. CAS — Write if CAS token matches
4. Retry — If CAS fails (EXISTS response), go to step 1

Implementation pattern:

def update_balance(key, delta):
    MAX_RETRIES = 10
    for attempt in range(MAX_RETRIES):
        # Step 1: Get current value and CAS token
        result = mc.gets(key)
        if result is None:
            # Key doesn't exist, create it
            if mc.add(key, delta):
                return delta
            continue  # Race condition, retry
        
        value, cas_token = result
        new_value = value + delta
        
        # Step 3: Attempt CAS
        if mc.cas(key, new_value, cas_token):
            return new_value  # Success!
        
        # CAS failed, another client updated - retry
    
    raise Exception("CAS failed after max retries")

CAS response codes:

Running Memcached at scale requires understanding its operational characteristics and failure modes.

Deployment topologies:

Configuration best practices:

# Start with sensible defaults
memcached 
    -m 8192 \            # 8GB memory
    -c 10000 \           # Max 10K connections
    -t 4 \               # 4 worker threads
    -p 11211 \           # Port
    -l 0.0.0.0 \         # Listen address
    -o slab_reassign \   # Enable slab rebalancing
    -o slab_automove=1   # Automatic slab moving

Key metrics to monitor:

Failure handling:

Memcached servers will fail. Your application must handle:

1. Server unreachable — Skip the server in the hash ring, continue with remaining servers
2. Timeout — Set reasonable timeouts (100-500ms); don't let cache slow down your app
3. Eviction storms — Monitor eviction rate; add memory or servers before it's critical
4. Thundering herd — When servers restart, cache is empty; use cache stampede protection

Cache stampede protection:

def get_with_stampede_protection(key, ttl, compute_fn):
    value = cache.get(key)
    if value is not None:
        return value
    
    # Try to acquire lock to compute
    lock_key = f"lock:{key}"
    if cache.add(lock_key, "1", timeout=10):  # 10 second lock
        try:
            value = compute_fn()  # Only one process computes
            cache.set(key, value, time=ttl)
            return value
        finally:
            cache.delete(lock_key)
    else:
        # Another process is computing; wait and retry
        time.sleep(0.1)
        return get_with_stampede_protection(key, ttl, compute_fn)

The Memcached vs Redis debate is one of the most common in system design. While Redis has broader capabilities, Memcached remains a valid choice for specific use cases.

Choose Memcached when:

The modern reality:

For most new projects, Redis is the default choice. Its richer feature set covers more use cases with one technology, reducing operational complexity. The performance difference for typical workloads is negligible.

However, if you:

• Have existing Memcached infrastructure that works
• Need to maximize per-instance throughput on large machines
• Only need simple key-value caching with no persistence
• Want the absolute minimum memory overhead

...then Memcached remains a solid, battle-tested choice.

We've explored Memcached's architecture, internals, and operational considerations. Let's consolidate the key concepts:

What's next:

With Redis and Memcached covered, we'll explore DynamoDB and Riak—two distributed key-value stores designed for different scales and consistency models. DynamoDB brings managed, serverless key-value at AWS scale, while Riak demonstrates Dynamo-style eventual consistency for on-premises deployments.