Understanding Distributed Caching with Memcached: Principles and Algorithms

Author: Float_Luuu Source: Open Source China

Abstract

In high‑concurrency scenarios, massive read/write requests overwhelm the database and disk I/O becomes a bottleneck, causing high response latency; therefore caching is introduced. Both single‑node and distributed caches have their own scenarios, with Redis and Memcached being the most common. This article focuses on the distributed implementation principles of the Memcached service.

Cache Essence

Computer System Cache

A cache is a faster storage layer in the memory hierarchy. According to the Von Neumann architecture, a computer consists of CPU, control unit, memory, input and output devices. Modern PCs typically have the following storage components:

356 GB disk

4 GB RAM

3 MB L3 cache

256 KB L2 cache (pre‑core)

In addition, there are registers and sometimes L1 cache inside the CPU. When the CPU needs data, it first looks in the nearest L2 cache, which is the fastest and smallest due to its high cost.

Storage Pyramid

The storage hierarchy resembles a pyramid: the top layers are fastest and most expensive, while the bottom layers are slower and cheaper. Data is fetched from the highest‑level storage that contains it.

Cache in Application Systems

The same principle applies to applications: Cache (fast) → DB (slow). The workflow is illustrated below.

Cache‑enabled storage access model

When a request arrives, the system first checks the cache; if the entry is present and valid, it returns the data. Otherwise it queries the database, returns the result, and updates the cache.

Memcached Overview

What is Memcached?

Memcached was originally developed by Brad Fitzpatrick at Danga Interactive for LiveJournal. It is now widely used by services such as Facebook, mixi, and many others to improve web‑application scalability. Traditional web apps store data in an RDBMS; as traffic grows, the database becomes a bottleneck, increasing response latency.

Memcached addresses this by providing a high‑performance distributed in‑memory cache, reducing database load, speeding up responses, and enhancing scalability.

Memcached cache usage

Memcached Features

Simple protocol

Event‑driven via libevent

In‑memory storage

Stateless distributed architecture (nodes do not communicate directly)

Memcached Distributed Principle

Memcached achieves distribution on the client side. When a client receives data, it hashes the key to decide which Memcached server will store the value; the same hash is used for retrieval, ensuring that the same server is selected.

Memcached distribution diagram

Remainder (Modulo) Hashing

The classic Memcached distribution method uses the following algorithm:

CRC($key) % N

The client computes the CRC of the key, then takes the modulo with the number of servers (N) to select a node. This method has two drawbacks:

If a selected server is unreachable, a common workaround is to append a retry count to the key and re‑hash (rehash).

When servers are added or removed, a large portion of keys must be remapped, causing costly cache reshuffling.

Consistent Hashing Algorithm

Consistent hashing maps both server nodes and keys onto a logical ring (0‑2³²). Each server’s hash determines its position on the ring; a key’s hash is also placed on the ring, and the key is stored on the first server encountered clockwise. If the end of the ring is reached, the key wraps to the first server.

Basic Consistent Hashing Principle

When a server is added or removed, only keys that map to the affected region need to be redistributed. For example, adding a fifth node (node5) between node4 and node2 only changes the mapping for keys that previously fell between node2 and node4.

Adding node5 to the ring

Optimized Consistent Hashing

To improve key distribution uniformity, virtual nodes are introduced. Each physical server is assigned multiple hash values, creating several virtual nodes on the ring. Keys are first mapped to a virtual node, which then maps to the underlying physical server. With enough virtual nodes, the key distribution becomes more balanced even with few physical servers.

Conclusion

After covering basic cache concepts, this article described Memcached’s distributed algorithms, showing that its distribution is entirely handled by the client library.

References

《Large‑Scale Distributed Website Architecture Design and Practice》

《Comprehensive Analysis of Memcached》