introduce
A memcache hashtable is a memory area that holds item* of a fixed size, that is, an array of Pointers of a fixed size. The size of the array is initialized at startup. The main core points involved are hashtable dynamic expansion, hashtable segment lock, etc. The corresponding hashtable files are hash.c, hash.h, assoc.c, assoc.h
Memcache hash table
The source code to achieve
Initialize the hash algorithm, hash_init ()
// Currently only two hash algorithms are available Jenkins and Murmur3
enum hashfunc_type {
JENKINS_HASH=0, MURMUR3_HASH
};
// when memcache is started
int hash_init(enum hashfunc_type type) {
switch(type) {
case JENKINS_HASH:
hash = jenkins_hash; // Jenkins_hash function pointer
settings.hash_algorithm = "jenkins";
break;
case MURMUR3_HASH:
hash = MurmurHash3_x86_32; // murmur3_hash function pointer
settings.hash_algorithm = "murmur3";
break;
default:
return - 1;
}
return 0;
}Copy the codeInitialize hashTable, assoc_init()
settings.hashpower_init // The reference value of hashtable, set when memcache is started
void assoc_init(const int hashtable_init) {
// Assign hashpower if it exists; otherwise, use the default hashpower = 16
if (hashtable_init) {
hashpower = hashtable_init;
}
// hashSize Calculates the final hashtable length based on the passed hashpower
// hashsize(n) -> #define hashsize(n) ((ub4)1<<(n))
// 实际上就是进行右移运算，右移 hashpower 位 ( 1 << 16 = 65536 )
Item ** primary_hashtable -> hashtable header pointer
primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
if (! primary_hashtable) {
fprintf(stderr."Failed to init hashtable.\n");
exit(EXIT_FAILURE);
}
STATS_LOCK();
stats.hash_power_level = hashpower;
stats.hash_bytes = hashsize(hashpower) * sizeof(void *); // How many bytes of memory does hashtable take up
STATS_UNLOCK();
}Copy the codeHashtable and
In the memcache thread initialization section, some mutex will be initialized, including the segment lock of the hashtable. The segment lock may have multiple keys corresponding to a lock, instead of each key corresponding to a lock, because different keys may hash the same value. So they all correspond to this lock.
Initialize the Hashtable lock
// the memcached_thread_init function is a piece of code
void memcached_thread_init(int nthreads, struct event_base *main_base) {
int i;
int power;
/ /...
// Set the hashtable lock to power based on the number of threads
if (nthreads < 3) {
power = 10;
} else if (nthreads < 4) {
power = 11;
} else if (nthreads < 5) {
power = 12;
} else {
/* 8192 buckets, and central locks don't scale much past 5 threads */
power = 13;
}
// Power is less than hashPower because the number of hashtable locks and the number of hashtables are not one-to-one
// Not every hashtable key has a lock. Memcache uses multiple keys to save memory
// It corresponds to a lock, namely a segment lock
if (power >= hashpower) {
fprintf(stderr."Hash table power size (%d) cannot be equal to or less than item lock table (%d)\n", hashpower, power);
fprintf(stderr."Item lock table grows with `-t N` (worker threadcount)\n");
fprintf(stderr."Hash table grows with `-o hashpower=N` \n");
exit(1);
}
// Calculate the length of the hashtable lock, default 4 threads power = 12, 1 << 12 = 4096/ lock
item_lock_count = hashsize(power);
item_lock_hashpower = power;
/ / to apply for the lock
// Then the item_LOCKS do not expand as the Hashtable expands
Hashsize (power) -> 4096/ lock
// This will also result in more and more keys for each lock
item_locks = calloc(item_lock_count, sizeof(pthread_mutex_t));
if (! item_locks) {
perror("Can't allocate item locks");
exit(1);
}
// Loop to initialize the item_locks
for (i = 0; i < item_lock_count; i++) {
pthread_mutex_init(&item_locks[i], NULL);
}
/ /...
}Copy the codeThe memcache HashTable has been initialized with the above code
Insert and expand hashtable
Memcache hashtable capacity expansion processing way is, in the program startup stage, open a thread on standby, when the need to expand the trigger thread, dynamic capacity expansion processing, and capacity expansion operation is not a table lock, but the use of the above mentioned segment lock
Capacity Expansion process:
When hashtable is expanded memcache copies the current primary_hashtable to old_hashtable. Then expand primary_hashtable (1 << hashpower + 1). If you are currently in hashtable expansion and there are requests to access the key, It determines whether the current key-hash index position is smaller than the current migrated index position. If it is smaller, it indicates that it has been migrated to the new primary_hashTable index position. If it is larger, it indicates that it has not been migrated to the new primary_Hashtable index position. So it will still operate at the old old_hashtable location, and then it will free old_hashtable after capacity expansion, and then it will all operate at primary_hashtable.
Description:
When a hashtable is migrated, it migrates index positions from small to large, which is the hash value. Therefore, when a hashtable is migrated, a lock is placed on the current index position, which is the segment lock, but the number of locks is limited. Many index locations share the same lock. Such as: 0 & (4096-1) = 0, 4096&(4096-1) = 0, 8192&(4096-1) = 0 In addition, if the key-hash value corresponds to the index position we are migrating, it will block because it has been locked. If other keys do not match the index position we are migrating, they will be accessed normally. Whether to access primary_hashtable or old_hashtable depends on the conditions described above.
Insert hashtable function, assoc_insert()
// hv = hash(key, nkey); Hash value
int assoc_insert(item *it, const uint32_t hv) {
unsigned int oldbucket;
// Check whether the capacity is being expanded
if (expanding &&
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
// Insert into hashtable
it->h_next = old_hashtable[oldbucket];
old_hashtable[oldbucket] = it;
} else {
// Insert into hashtable
it->h_next = primary_hashtable[hv & hashmask(hashpower)];
primary_hashtable[hv & hashmask(hashpower)] = it;
}
// Lock to prevent multiple threads from triggering capacity expansion at the same time
pthread_mutex_lock(&hash_items_counter_lock);
hash_items++;
// Determine whether capacity expansion is required
if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
// Capacity expansion is triggered
assoc_start_expand();
}
pthread_mutex_unlock(&hash_items_counter_lock);
MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey, hash_items);
return 1;
}Copy the codeTrigger the expansion operation, assoc_start_expand()
static void assoc_start_expand(void) {
if (started_expanding)
return;
started_expanding = true;
// Wake up the hashtable expansion thread
pthread_cond_signal(&maintenance_cond);
}Copy the codeHashtable extension thread function, assoc_maintenance_thread()
Pthread_cond_wait (&maintenance_cond, &maintenance_lock);
// Until pthread_cond_signal wakes up the operation above, then proceed.
static void *assoc_maintenance_thread(void *arg) {
mutex_lock(&maintenance_lock);
/ / death cycle
while (do_run_maintenance_thread) {
int ii = 0;
Old_hashtable -> primary_hashtable */
for (ii = 0; ii < hash_bulk_move && expanding; ++ii) {
item *it, *next;
int bucket;
void *item_lock = NULL;
// Lock the index location that is currently being migrated
if ((item_lock = item_trylock(expand_bucket))) {
// Loop through all items at the current index position
// Because there may be more than one item in the current index position
// Hash conflict chain resolution
for (it = old_hashtable[expand_bucket]; NULL! = it; it = next) {// Get the next item
next = it->h_next;
// Relocate an index to the new hashTable length
bucket = hash(ITEM_key(it), it->nkey) & hashmask(hashpower);
// Save the assignment
it->h_next = primary_hashtable[bucket];
primary_hashtable[bucket] = it;
}
// After all items are migrated, the previous hashtable index is empty
old_hashtable[expand_bucket] = NULL;
// Update the current index position
expand_bucket++;
// Determine whether all migrations are complete
if (expand_bucket == hashsize(hashpower - 1)) {
expanding = false; // Disable the expanding HashTable status
free(old_hashtable); / / release old_hashtable
STATS_LOCK();
stats.hash_bytes -= hashsize(hashpower - 1) * sizeof(void *);
stats.hash_is_expanding = 0;
STATS_UNLOCK();
if (settings.verbose > 1)
fprintf(stderr."Hash table expansion done\n"); }}else {
// If the lock fails, another thread may be manipulating the item in the current hashTable index
// So wait until you grab the lock
usleep(10*1000);
}
/ / releases the lock
if (item_lock) {
item_trylock_unlock(item_lock);
item_lock = NULL; }}if(! expanding) {/* We are done expanding.. just wait for next invocation */
started_expanding = false;
// Wait for wake up
pthread_cond_wait(&maintenance_cond, &maintenance_lock);
pause_threads(PAUSE_ALL_THREADS);
// Expand hashtable operation
assoc_expand();
// Execute the while loop downpause_threads(RESUME_ALL_THREADS); }}return NULL;
}Copy the codeExpand hashtable function, assoc_expand()
static void assoc_expand(void) {
// Save a copy of the current HashTable
old_hashtable = primary_hashtable;
// Add hashPower + 1 each time
// (1 << 16) = 65536, (1 << 17) = 131072
primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
if (primary_hashtable) {
if (settings.verbose > 1)
fprintf(stderr."Hash table expansion starting\n");
hashpower++; // hashpower++
expanding = true; // Indicates that the capacity is being expanded
expand_bucket = 0; // Currently migrated to the primary_hashtable index position
STATS_LOCK();
stats.hash_power_level = hashpower;
stats.hash_bytes += hashsize(hashpower) * sizeof(void *);
stats.hash_is_expanding = 1;
STATS_UNLOCK();
} else {
primary_hashtable = old_hashtable;
/* Bad news, but we can keep running. */}}Copy the codeFind the hashtable function, assoc_find()
item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
item *it;
unsigned int oldbucket;
// Whether capacity expansion is being performed
if (expanding &&
(oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
{
/ / get the item
it = old_hashtable[oldbucket];
} else {
/ / get the item
it = primary_hashtable[hv & hashmask(hashpower)];
}
item *ret = NULL;
int depth = 0;
// Loop judgment, since hash conflicts are chain-resolved, we need to traverse the chain to find the keys equal
while (it) {
if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
ret = it;
break;
}
it = it->h_next;
++depth;
}
MEMCACHED_ASSOC_FIND(key, nkey, depth);
return ret;
}Copy the codeThe end of the
Item_locks are locked on the key of the current hashtable. As the hashtable grows, the lock contention becomes larger and larger. Performance may also have some impact.