10 How Does MC Determine the Key #

Hello, I am your caching teacher Chen Bo. Welcome to the 10th lesson “Memcached Hash Table”.

In the analysis of the MC architecture, we have learned about the system architecture, network model, state machine of MC, and also have a basic understanding of MC’s slab allocation, Hashtable, and LRU. In this lesson, we will further delve into these topics.

Next, we will proceed to the advanced study of Memcached. We will explain how MC positions keys, how it eliminates and recycles expired and invalid keys, and analyze MC’s memory management slab mechanism. We will also discuss the key mechanisms for data storage and maintenance in MC, conduct a complete protocol analysis of MC, and use Java as an example to introduce commonly used MC clients and how to optimize and improve them.

Key Positioning #

Hashtable #

MC stores data in Items, which are then managed by four LRU lists for each slabclass. These LRUs are implemented as doubly-linked lists for efficient addition, deletion, and modification of records. However, the performance of locating a key using the doubly-linked list is very poor, as it can only be achieved by traversing the list. Therefore, MC also uses a Hashtable to record and manage these Items, which allows for quick positioning and retrieval of key/value pairs by performing a hash calculation on the key, as shown in the following diagram.

A Hashtable, also known as a hash table or hash map, allows for quick accessing of records by mapping keys to positions in the hash table. The time complexity for key positioning is O(1). MC’s Hashtable is actually a one-dimensional array of pointers, where each position is called a bucket. For performance reasons, the length of MC’s Hashtable is set to a power of 2, denoted as 2^N. When MC is started, it builds a Hashtable with 64,000 buckets by default. As new keys are continuously inserted and the elements in the Hashtable exceed a certain threshold, the Hashtable will be resized. The maximum number of buckets that can be built is 2^32, which means that after multiple resizings, MC’s Hashtable can have a maximum of nearly 4.3 billion buckets.

Hashtable Design #

There are two key points in the design of the Hashtable: the hash algorithm and the hash collision resolution method. MC uses two hash algorithms, namely Murmur3 Hash and Jenkins Hash. The current version of MC defaults to using the Murmur3 Hash algorithm. If different keys are mapped to the same bucket through hashing, this is called a hash collision. MC solves the hash collision problem by using a singly-linked list for each bucket.

Positioning key #

When Memcached locates a key, it first uses the Murmur3 or Jenkins algorithm to calculate the hash value of the key, resulting in a 32-bit unsigned integer output stored in the variable hv. Since the hash table generally does not have a size of 2^32, it is necessary to map the hash value of the key to the range of the hash table. Mc uses the simplest modulus algorithm as the mapping function, which is calculated by hv%hashsize. Because ordinary modulus operations are time-consuming, Mc sets the length of the hash table to a power of 2 and optimizes it using bitwise operations, which is calculated by hv&hashmask. hashmask is equal to 2^n-1.

After locating the position of the key in the bucket, if it is inserting a new data, the data Item is inserted into the singly linked list of the bucket using the head insertion method. If it is a lookup, it scans the corresponding hash bucket in the hash table and compares the key strings one by one. If the keys match, it finds the data Item.

If there are too many elements in the hash bucket of the hash table, scanning this linked list will be time-consuming. Therefore, when the number of elements in the hash table reaches 1.5 times the number of buckets, Mc doubles the size of the hash table. Since there are only about 4.3 billion buckets in the hash table, for performance reasons, a single Mc node can store a maximum of 6.5 billion key/value pairs. If you want to store more keys, you need to modify the Mc source code and increase the maximum hash, which is HASHPOWER_MAX.

Hash table expansion #

When the number of Items in Mc’s hash table is greater than 1.5 times the number of hash buckets, Mc will expand the hash table. As shown in the figure below, Mc’s hash expansion is done by the hash maintenance thread. When ready to expand, the hash maintenance thread first pauses all IO worker threads and auxiliary threads, including the LRU maintenance thread, slab maintenance thread, and LRU crawler thread. After these threads are paused, the hash maintenance thread sets the current main hash table as the old hash table and doubles the capacity of the new main hash table. Then, the worker threads and auxiliary threads resume work, and the hash maintenance thread starts to gradually migrate Item elements from the old hash table to the main hash table.

When Mc starts, it builds an Item lock hash table based on the number of worker threads set. The more threads, the larger the lock hash table, with 4096 buckets for 4 threads and 8192 buckets for 10 threads. The Item lock hash table has a maximum of 32k buckets, where 1k is 1024, thus a maximum of 32768 buckets. In Mc’s lock hash table, each bucket corresponds to an Item lock, so Mc has a maximum of 32768 Item locks.

During the process of reading, modifying, and expanding migration in the Mc hash table, the key hash is first located in the lock bucket of the Item lock hash table, and then the Item lock is locked before performing the actual operation. In fact, except in the hash table, whenever any operation on the Item is involved, the Item hash lock bucket is locked based on the key in the Item to avoid dirty data caused by simultaneous read and write of the Item. Mc has 4096 lock buckets by default, so the probability of conflicts when locking keys is low, and since Mc operates completely in memory, the operation speed is fast. Even if the lock is occupied when applying for it, it will be released quickly.

When the Mc hash table is expanded, the hash table maintenance thread migrates the Item elements from the old hash table to the new main hash table one bucket linked list at a time. During the expansion process, if you want to look up or insert a key, you will refer to the migration position and select the corresponding hash table. If the hash bucket corresponding to the key is before the migration position, it will query or insert in the new main hash table; otherwise, it will query and insert in the old hash table. After all the expansion and migration is completed, all operations will be performed in the new main hash table.