Understanding The Memcached Source Code - LRU II
Tags: memcachedsourcecod, memcached, cache, lru
Published: 2018-12-23 02:31:23

---
title: Understanding The Memcached Source Code - LRU II
published: true
tags: Memcached Source Cod,memcached,cache,LRU
canonical_url: https://holmeshe.me/understanding-memcached-source-code-V/
---

[![](../gallery/spade.svg) slab allocator (I, ](https://dev.to/holmeshe/understanding-the-memcached-source-code---slab-i-165h) [II,](https://dev.to/holmeshe/understanding-the-memcached-source-code---slab-ii-2kc3) [III)](https://dev.to/holmeshe/understanding-the-memcached-source-code---slab-iii-3h8l) is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilized. The other 3 parts, namely,

[![](../gallery/heart.svg) LRU algorithm (I, ](https://dev.to/holmeshe/understanding-the-memcached-source-code---lru-i-2pdm) II - this article) for entry expiration; and an

![](../gallery/club.svg) event driven model (not complete) based on libevent; and the

![](../gallery/diamond.svg) consistent harsh (not complete) for data distribution,

are built around it.

More often than not, the **LRU** algorithm is combined with a **hash map** , and is referred to as an LRU cache.

In a **LRU-cache** , the **hash map** enables fast accessing of _cached_ objects; and **LRU** avoids the _cache_ to grow infinitely by marking expired, or so called, **least recently used** objects. This time we examine the **memcached** ‘s implementation of **hash map**.

# Overview (textbook overlapped, skip)

**Hash map** is basically a _fixed-sized_ array that indexes _value_s with integers **hashed** from _key_s. In **hash map** an array entry is referred to as a _bucket_. If the **hash value** exceeds the number of buckets (i.e., array size), it _rolls over_ using ‘mod’ (`%`). _Collision_ occurs when more than two _key_s result in the same **hash value** or different **hash value** s roll over to the same bucket, then a \*linked list is formed on the bucket in a collision.

_Collision_ slows down lookups speed for the sequential access of _linked list_, hence it is required to increase the _bucket number_, and to _rehash_ entries using the new **bucket number** before the performance goes too bad. This process will be discussed soon.

# Module initialization

The first relevant method is

## hash\_init

which simply determines the hash algorithm type.

```c
int hash_init(enum hashfunc_type type) {
    switch(type) {
        case JENKINS_HASH:
            hash = jenkins_hash;
            settings.hash_algorithm = "jenkins";
            break;
        case MURMUR3_HASH:
            hash = MurmurHash3_x86_32;
            settings.hash_algorithm = "murmur3";
            break;
        default:
            return -1;
    }
    return 0;
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">hash_init@hash.c</text></a></center>

This method is called from here as one of the init steps before the logic enters the main event loop.

```c
...
...
    if (hash_init(hash_type) != 0) {
        fprintf(stderr, "Failed to initialize hash_algorithm!\n");
        exit(EX_USAGE);
    }
...
```  
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">main@memcached.c:5849</text></a></center>  

The parameter `hash_type` is set to `MURMUR3_HASH` by the mentioned command-line argument modern.

```c
...
            case MODERN:
                /* Modernized defaults. Need to add equivalent no_* flags
                 * before making truly default. */
...
                hash_type = MURMUR3_HASH;
...
                break;
...
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">main@memcached.c:5849</text></a></center>  

The second method

## assoc\_init

allocates the fixed sized array mentioned in the beginning.

```c
void assoc_init(const int hashtable_init) {
    if (hashtable_init) {
        hashpower = hashtable_init;
    }
    primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
    if (! primary_hashtable) {
        fprintf(stderr, "Failed to init hashtable.\n");
        exit(EXIT_FAILURE);
    }
...// scr: stat
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">hash_init@hash.c</text></a></center>

This method is called in a similar location as `hash_init` as part of the system bootstrap process.

```c
...
    assoc_init(settings.hashpower_init);
...
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">main@memcached.c:5976</text></a></center>  

And the actual initial size is determined by the command-line argument `hashpower`.

```c
...
case HASHPOWER_INIT:
    if (subopts_value == NULL) {
        fprintf(stderr, "Missing numeric argument for hashpower\n");
        return 1;
    }
    settings.hashpower_init = atoi(subopts_value);
    if (settings.hashpower_init < 12) {
        fprintf(stderr, "Initial hashtable multiplier of %d is too low\n",
            settings.hashpower_init);
        return 1;
    } else if (settings.hashpower_init > 64) {
        fprintf(stderr, "Initial hashtable multiplier of %d is too high\n"
            "Choose a value based on \"STAT hash_power_level\" from a running instance\n",
            settings.hashpower_init);
        return 1;
    }
    break;
...
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">main@memcached.c:5677</text></a></center>  

As said before, the array can be replaced with a newly allocated larger one if the performance drops due to excessive _collision_. Next we discuss the process of

# Scale up & entry migration

In **memcached** , the threshold is 1.5, meaning, if the **item** s number exceeds 1.5 \* **bucket number** , the mentioned expanding process starts.

![Expand hash map](https://thepracticaldev.s3.amazonaws.com/i/wlqk1aedozzuq2u4o9p6.png)

```c
...
    if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
        assoc_start_expand();
    }
...
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">assoc_insert@assoc.c:173</text></a></center>

The `assoc_start_expand` simply set a flag (i.e., `do_run_maintenance_thread`), and send a signal to awake a maintenance thread that does the actual job.

```c
static void assoc_start_expand(void) {
    if (started_expanding)
        return;

    started_expanding = true;
    pthread_cond_signal(&maintenance_cond);
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">assoc_insert@assoc.c:173</text></a></center>
## Maintenance thread main loop

```c
static void *assoc_maintenance_thread(void *arg) {

  mutex_lock(&maintenance_lock);
  while (do_run_maintenance_thread/* scr: the flag*/) {
    int ii = 0;

    /* There is only one expansion thread, so no need to global lock. */
    for (ii = 0; ii < hash_bulk_move && expanding; ++ii) { // scr: ----> 2)
      item *it, *next;
      int bucket;
      void *item_lock = NULL;

      /* bucket = hv & hashmask(hashpower) =>the bucket of hash table
       * is the lowest N bits of the hv, and the bucket of item_locks is
       *  also the lowest M bits of hv, and N is greater than M.
       *  So we can process expanding with only one item_lock. cool! */
      if ((item_lock = item_trylock(expand_bucket))) { // scr: --------> 3)
        for (it = old_hashtable[expand_bucket]; NULL != it; it = next) {
          next = it->h_next; // scr: ----------------------------------> 4)
          bucket = hash(ITEM_key(it), it->nkey) & hashmask(hashpower);
          it->h_next = primary_hashtable[bucket];
          primary_hashtable[bucket] = it;
        }

        old_hashtable[expand_bucket] = NULL; // scr: ----------------> 4.1)

        expand_bucket++; // scr: --------------------------------------> 5)
        if (expand_bucket == hashsize(hashpower - 1)) { // scr: -------> 6)
          expanding = false;
          free(old_hashtable);
... // scr: ---------------------------------------------------> stat & log
        }
      } else {
        usleep(10*1000); // scr: ------------------------------------> 3.1)
      }


      if (item_lock) { // scr: --------------------------------------> 3.2)
        item_trylock_unlock(item_lock);
        item_lock = NULL;
      }
    }

    if (!expanding) {
      /* We are done expanding.. just wait for next invocation */
      started_expanding = false;
      pthread_cond_wait(&maintenance_cond, &maintenance_lock); // scr: > 0)
      /* assoc_expand() swaps out the hash table entirely, so we need
       * all threads to not hold any references related to the hash
       * table while this happens.
       * This is instead of a more complex, possibly slower algorithm to
       * allow dynamic hash table expansion without causing significant
       * wait times.
       */
      pause_threads(PAUSE_ALL_THREADS);
      assoc_expand(); // scr: -----------------------------------------> 1)
      pause_threads(RESUME_ALL_THREADS);
    }
  }
  return NULL;
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">assoc_maintenance_thread@assoc.c</text></a></center>

0) This is where the thread waits up from sleep and start working, and goes to sleep when there is nothing to be done.

1) assoc\_expand allocates the resource for the new **hash map** which is meant to replace the old one initialized from here.

```c
/* grows the hashtable to the next power of 2. */
static void assoc_expand(void) {
    old_hashtable = primary_hashtable;

    primary_hashtable = calloc(hashsize(hashpower + 1), sizeof(void *));
    if (primary_hashtable) {
... // scr: log
        hashpower++;
        expanding = true;
        expand_bucket = 0;
... // scr: stat
    } else {
        primary_hashtable = old_hashtable;
        /* Bad news, but we can keep running. */
    }
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">assoc_expand@assoc.c</text></a></center>  

2) Only migrate a certain number of **item** s in one batch. hash\_bulk\_move avoids the thread hanging around too long when stop\_assoc\_maintenance\_thread is called. In contrast to the discussed `assoc_start_expand`, stop\_assoc\_maintenance\_thread reset the flag `do_run_maintenance_thread` and send the signal to wake up the thread to exit.

```c
#define DEFAULT_HASH_BULK_MOVE 1
int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">assoc.c:207</text></a></center>  

```c
...
    char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
    if (env != NULL) {
        hash_bulk_move = atoi(env);
        if (hash_bulk_move == 0) {
            hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
        }
    }
...
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">start_assoc_maintenance_thread@assoc.c:281</text></a></center>  

```c
void stop_assoc_maintenance_thread() {
    mutex_lock(&maintenance_lock);
    do_run_maintenance_thread = 0;
    pthread_cond_signal(&maintenance_cond);
    mutex_unlock(&maintenance_lock);

    /* Wait for the maintenance thread to stop */
    pthread_join(maintenance_tid, NULL);
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">stop_assoc_maintenance_thread@assoc.c</text></a></center>  

3) (The “item lock” actually works on the whole _bucket_ hence I will call it _bucket lock_ instead) Use low priority item\_trylock (`i.e., pthread_mutex_trylock`) to access the _bucket lock_; 3.1) sleep for 10 sec when the the **item** is not available; and 3.2) release the lock using item\_trylock\_unlock when the migration (of this _bucket_) completes.

```c
void *item_trylock(uint32_t hv) {
    pthread_mutex_t *lock = &item_locks[hv & hashmask(item_lock_hashpower)];
    if (pthread_mutex_trylock(lock) == 0) {
        return lock;
    }
    return NULL;
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">item_trylock@thread.c</text></a></center>  

```c
void item_trylock_unlock(void *lock) {
    mutex_unlock((pthread_mutex_t *) lock);
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">item_trylock@thread.c</text></a></center>  

4) Rehash all the **item** s in the bucket, and migrate them to the new hash map.

5) Move on to the next _bucket_.

6) Last _bucket_ reached -\> go to 0)

## Maintenance thread start

```c
int start_assoc_maintenance_thread() {
    int ret;
    char *env = getenv("MEMCACHED_HASH_BULK_MOVE");
    if (env != NULL) {
        hash_bulk_move = atoi(env);
        if (hash_bulk_move == 0) {
            hash_bulk_move = DEFAULT_HASH_BULK_MOVE;
        }
    }
    pthread_mutex_init(&maintenance_lock, NULL);
    if ((ret = pthread_create(&maintenance_tid, NULL,
                              assoc_maintenance_thread, NULL)) != 0) {
        fprintf(stderr, "Can't create thread: %s\n", strerror(ret));
        return -1;
    }
    return 0;
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">start_assoc_maintenance_thread@assoc.c</text></a></center>

Similar to initialization methods, it is called during system bootstrap.

```c
...
if (start_assoc_maintenance_thread() == -1) {
    exit(EXIT_FAILURE);
}
...
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">main@memcached.c:5992</text></a></center>  

## Maintenance thread stop

This method is called in system shutdown process, hence it is opposite in logic to `start_assoc_maintenance_thread`. Nevertheless, the operations of this method are opposite that of `assoc_start_expand` mechanism wise.

```c
...
    stop_assoc_maintenance_thread();
...
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">main@memcached.c:6098</text></a></center>  

```c
void stop_assoc_maintenance_thread() {
    mutex_lock(&maintenance_lock);
    do_run_maintenance_thread = 0;
    pthread_cond_signal(&maintenance_cond);
    mutex_unlock(&maintenance_lock);

    /* Wait for the maintenance thread to stop */
    pthread_join(maintenance_tid, NULL);
}
```

<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">stop_assoc_maintenance_thread@assoc.c</text></a></center>

As said before, the expanding & migration process discussed here has an impact on the logic of all **hash map** related operations. In the next section, we look at these operations.

# CRUD

N.b., `assoc_delete` has been discussed in the [previous post](https://holmeshe.me/understanding-memcached-source-code-IV/#assoc-delete-remove-from-hash-map); and in a key-value system _update_ and _insert_ are essentially the same, thus, this section will discuss the operations of _C_ (create) and _R_ (read) only.

## assoc\_insert

```c
int assoc_insert(item *it, const uint32_t hv) {
    unsigned int oldbucket;

    if (expanding &&
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        it->h_next = old_hashtable[oldbucket]; // scr: -------------------> 1)
        old_hashtable[oldbucket] = it;
    } else {
        it->h_next = primary_hashtable[hv & hashmask(hashpower)]; // scr: > 2)
        primary_hashtable[hv & hashmask(hashpower)] = it;
    }

    pthread_mutex_lock(&hash_items_counter_lock);
    hash_items++; // scr: ------------------------------------------------> 3)
    if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
        assoc_start_expand();
    }
    pthread_mutex_unlock(&hash_items_counter_lock);

    MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey, hash_items);
    return 1;
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">assoc_insert@assoc.c</text></a></center>

1) If expanding process is undergoing and the _hash key_ associated bucket has not been migrated, insert the item to `old_hashtable`. Note that here we use the old _bucket number_ (i.e., `hashmask(hashpower - 1))`) to calculate the hash index.

2) Otherwise, insert the **item** to `primary_hashtable` directly.

3) Increase the global variable hash\_items (number of **item** s). If it exceeds the threshold after the **item** is added, start expanding & migration process. Note that this is also the preamble of the previous section.

```c
...
static unsigned int hash_items = 0;
...
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">assoc.c:51</text></a></center>  

## assoc\_find

```c
item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
    item *it;
    unsigned int oldbucket;

    if (expanding &&
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        it = old_hashtable[oldbucket]; // scr: ---------------------------> 1)
    } else {
        it = primary_hashtable[hv & hashmask(hashpower)]; // scr: --------> 2)
    }

    item *ret = NULL;
    int depth = 0;
    while (it) { // scr: -------------------------------------------------> 3)
        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;
}
```
<center style="line-height:0.3;margin:0;"><a href="https://play.google.com/store/apps/details?id=me.holmeshe.sc" target="_blank" rel="noopener"><text style="color:black;font-weight:bold;">assoc_find@assoc.c</text></a></center>

1) Similar to that of assoc\_insert, this step locates the bucket from `old_hashtable` when the key is yet to be rehashed.

2) Use `primary_hashtable` directly otherwise.

3) Go through the _linked list_ and compare the _key_ (instead of the _hash index_) directly to lookup the **item** in the case of _Collision_.

One thing worth noting is that `assoc_find` is very similar to `_hashitem_before` which has been discussed in the [previous post](https://holmeshe.me/understanding-memcached-source-code-IV/#assoc-delete-remove-from-hash-map). The difference here is, `_hashitem_before` returns the **address of the next member of the element before the found one** (`pos = &(*pos)->h_next;`), which is required when removing entries from a _singly linked list_; whilst this method returns the element found directly (`ret = it;`).