07 Why MC is the Most Widely Used Caching Component #

Okay, I am your caching teacher, Chen Bo. Welcome to lesson 7 “Memcached Principles and Features”.

As we all know, user experience is the most important indicator for internet companies, and in user experience, response speed is of utmost importance. Therefore, the pursuit of performance in internet systems is endless. In the battle for performance, caching is king, and Memcached, as the most widely used and influential caching component in internet systems, can be regarded as the king among kings.

In this lesson, we will explain the principles and features of Memcached, the system architecture, and we will also focus on the network model and state machine of Memcached and touch on the entire process of handling Memcached commands.

Memcached Principles and Features #

First, let’s look at the principles and features of Memcached.

Principles #

Memcached is an open-source, high-performance distributed key/value in-memory cache system. It stores data in the form of key/value pairs and is a key-value type NoSQL component.

NoSQL stands for Not SQL, which refers to non-relational data storage. NoSQL processes data using aggregation models. The aggregation models mainly include key/value pairs, column families, and graphs. Among them, the key/value pairs are similar to maps that we usually use, and they can only be searched and modified by key. Memcached, Redis, and other similar components are key-value type NoSQL storage components that we use.

Memcached is commonly abbreviated as MC and is a typical in-memory caching component, which means that once MC is restarted, all data is lost. As shown in the following diagram, the MC components do not communicate with each other and are completely distributed and coordinated by the client after hashing the key. MC uses multiple threads to process requests, with one main thread and any number of worker threads working together, making full use of multiple cores to improve IO efficiency.

Slab Mechanism #

Next, let’s introduce the slab mechanism of MC.

MC does not manage all data together, but divides the memory into a series of equally sized slab spaces, with each slab only managing a certain range of data storage. In other words, MC uses the slab mechanism to manage memory allocation internally. In MC, memory allocation is done on a slab level. By default, a slab is 1MB, and you can specify a different value using the -I parameter at startup.

Inside the slab space, it is further divided into a series of fixed-sized chunks. Each chunk stores an Item using the Item structure. Because the size of chunks is fixed while the size of key/value data is random, there is usually extra space after storing the key/value data in an Item. This extra space is wasted. To improve the efficiency of memory usage, the chunk size cannot be too large and should be as close as possible to the size of the key/value data, thereby reducing wasted space inside the chunks.

When allocating memory, MC first divides the memory into slabs of fixed sizes, and then divides each slab into chunks of fixed sizes. Although the chunks within a slab are of the same size, the chunk sizes of different slabs are different. MC gradually increases the size of the allocated chunk by a fixed ratio, allowing it to meet the storage needs of key/value pairs of different sizes.

As shown in the following diagram, a group of slabs with the same chunk size forms a slab class. The chunk sizes of different slab classes increase with an incremental factor. MC manages the storage space within a group of slabs using slab classes. Each slab class has a freelist that contains all the vacant chunks in this group of slabs. When data needs to be stored, a chunk is quickly allocated from this freelist as storage space. When an Item is evicted due to data elimination, the chunk it was in is recycled to this freelist.

When MC manages the allocation of memory using the slab mechanism, the actual allocation of key/value pairs is translated into the allocation of Items. There are two ways to allocate Item space: if MC has available space, it is allocated from the freelist of the slab class; if no space is available, an Item is evicted from the LRU corresponding to the slab class ID to reuse its space.

When looking up or modifying a key, the first step is to locate the storage location of the key. MC uses a hashtable to locate keys. The hashtable can be seen as a large array with contiguous memory space, and each slot in this array corresponds to the hash value of a key. These slots are also called buckets. Since different keys may have the same hash value, MC uses a singly linked list inside each bucket of the hashtable to solve hash collision problems.

MC uses LRU to manage the storage of Item data internally. When memory is insufficient, it evicts an expired or least active key from the LRU queue at the tail to be used by a new Item.

Features #

After explaining the slab mechanism, let’s learn about the features of MC.

• The biggest feature of MC is high performance, with the performance of a single-node load test reaching millions of queries per second (QPS).
• Secondly, because MC’s access protocol is very simple, with only a few limited commands such as get/set/cas/touch/gat/stats. MC’s simple access protocol is related to its storage structure.
• MC has a simple storage structure, storing only simple key/value pairs, and directly storing the value using binary format without recognizing the internal storage structure. Therefore, a few instructions are sufficient to meet the operational needs.
• MC operates entirely on memory. During the system runtime, when a new key is written in and there is no available memory allocation, it evicts the least active key for eviction.
• Finally, the operation of MC service nodes is very simple, with no communication between different MC nodes, and the distribution of data is managed by the client itself.