DEV Community: holmeshe

Understanding The Memcached Source Code - LRU II

holmeshe — Tue, 18 Dec 2018 11:00:00 +0000

II, III) 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,

II - this article) for entry expiration; and an

event driven model (not complete) based on libevent; and the

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.

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;
}

hash_init@hash.c

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

...
...
    if (hash_init(hash_type) != 0) {
        fprintf(stderr, "Failed to initialize hash_algorithm!\n");
        exit(EX_USAGE);
    }
...

main@memcached.c:5849

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

...
            case MODERN:
                /* Modernized defaults. Need to add equivalent no_* flags
                 * before making truly default. */
...
                hash_type = MURMUR3_HASH;
...
                break;
...

main@memcached.c:5849

The second method

assoc_init

allocates the fixed sized array mentioned in the beginning.

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
}

hash_init@hash.c

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

...
    assoc_init(settings.hashpower_init);
...

main@memcached.c:5976

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

...
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;
...

main@memcached.c:5677

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.

...
    if (! expanding && hash_items > (hashsize(hashpower) * 3) / 2) {
        assoc_start_expand();
    }
...

assoc_insert@assoc.c:173

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.

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

    started_expanding = true;
    pthread_cond_signal(&maintenance_cond);
}

assoc_insert@assoc.c:173

Maintenance thread main loop

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;
}

assoc_maintenance_thread@assoc.c

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.

/* 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. */
    }
}

assoc_expand@assoc.c

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.

#define DEFAULT_HASH_BULK_MOVE 1
int hash_bulk_move = DEFAULT_HASH_BULK_MOVE;

assoc.c:207

...
    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;
        }
    }
...

start_assoc_maintenance_thread@assoc.c:281

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);
}

stop_assoc_maintenance_thread@assoc.c

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.

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;
}

item_trylock@thread.c

void item_trylock_unlock(void *lock) {
    mutex_unlock((pthread_mutex_t *) lock);
}

item_trylock@thread.c

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

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;
}

start_assoc_maintenance_thread@assoc.c

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

...
if (start_assoc_maintenance_thread() == -1) {
    exit(EXIT_FAILURE);
}
...

main@memcached.c:5992

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.

...
    stop_assoc_maintenance_thread();
...

main@memcached.c:6098

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);
}

stop_assoc_maintenance_thread@assoc.c

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; 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

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;
}

assoc_insert@assoc.c

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.

...
static unsigned int hash_items = 0;
...

assoc.c:51

assoc_find

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;
}

assoc_find@assoc.c

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. 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;).

Understanding The Memcached Source Code - LRU I

holmeshe — Tue, 11 Dec 2018 12:00:00 +0000

II, III) 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,

LRU algorithm (I - this article, II) for entry expiration; and an

event driven model (not complete) based on libevent; and the

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 a

LRU Cache

In a LRU-cache , the hash map enables the fast accessing of the cached objects; and LRU avoids the cache to grow infinitely by marking expired, or so called, least recently used objects. Next we look at how LRU works from a high level standpoint.

Linked list

Technically, LRU algorithm works on a linked list, whenever a list entry is used (accessed or updated), it is removed from the list and be attached to the list head. In this way, the closer an element is to the list tail, the less recently used it is. Hence it is easy to remove irrelevant or “expired” elements from the tail based on a certain configuration.

Harsh map

Linked list is slow when it comes to element access, hence another data structure is employed. We have seen how linked list “strings” chunks in slabs to make free list_s. In an LRU cache , the mechanism is similar, however, it is the hash map entries instead of _chunks in slabs got wired up this time, which looks like:

We can also flatten the linked list, and make the structure a bit more clear,

Core data structure - item

typedef struct _stritem {
    /* Protected by LRU locks */
    struct _stritem *next;
    struct _stritem *prev;
    /* Rest are protected by an item lock */
    struct _stritem *h_next;    /* hash chain next */
    rel_time_t      time;       /* least recent access */
    rel_time_t      exptime;    /* expire time */
    int             nbytes;     /* size of data */
    unsigned short  refcount;
    uint8_t         nsuffix;    /* length of flags-and-length string */
    uint8_t         it_flags;   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;       /* key length, w/terminating null and padding */
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
... // scr: cas
        char end; // scr: flexible array member indicating the item header "end"
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

do_item_unlink@item.c

Properties in use

next, prev, slabs_clsid - item_link_q, item_unlink_q

it_flags - do_item_link, do_item_unlink

time, refcount - do_item_link

h_next - assoc_insert, assoc_delete

nkey - assoc_delete

Memory layout of an item chunk

We have mentioned item chunk in do_slabs_free. With the help of this data structure, we can now examine the chunk more closely.

Next we read the relevant code that performs the above discussed LRU operations.

do_item_link

int do_item_link(item *it, const uint32_t hv) { // scr: -------------------> 1)
...
    it->it_flags |= ITEM_LINKED;                // scr: -------------------> 2)
    it->time = current_time;

... // scr: stat

    /* Allocate a new CAS ID on link. */
... // scr: cas
    assoc_insert(it, hv);                       // scr: -------------------> 3)
    item_link_q(it);                            // scr: -------------------> 4)
    refcount_incr(&it->refcount);               // scr: -------------------> 5)
... // scr: stat

    return 1;
}

do_item_link@item.c

1) hv is supposed to be the shortened “hashed value”.

2) Set ITEM_LINKED in it->it_flags, and set current time to it->time.

The field it_flags is used in do_slabs_free and do_slabs_alloc

3) Insert the item to hash map.

4) Insert the item to linked list.

5) Increase the reference count.

This field is initialized as 1 in do_slabs_alloc

It is worth noting here that reference count indicates how many sub-modules are using the same resource, so as to determine when to actually deallocate the resource (In this particular case, item is referred by both slab and LRU ). I have written this article that explains a similar mechanism of C++.

item_link_q - add to linked list

item_link_q is a thread safe wrapper of the workhorse method do_item_link_q.

static void item_link_q(item *it) {
    pthread_mutex_lock(&lru_locks[it->slabs_clsid]);
    do_item_link_q(it);
    pthread_mutex_unlock(&lru_locks[it->slabs_clsid]);
}

item_link_q@item.c

static void do_item_link_q(item *it) { /* item is the new head */
    item **head, **tail;
    assert((it->it_flags & ITEM_SLABBED) == 0);

    head = &heads[it->slabs_clsid];           // scr: -------------------> 1)
    tail = &tails[it->slabs_clsid];
    assert(it != *head);
    assert((*head && *tail) || (*head == 0 && *tail == 0));
    it->prev = 0;                             // scr: -------------------> 2)
    it->next = *head;
    if (it->next) it->next->prev = it;
    *head = it;
    if (*tail == 0) *tail = it;
    sizes[it->slabs_clsid]++;                 // scr: -------------------> 3)
    return;
}

do_item_link_q@item.c

1) Get the head and tail of the respective LRU linked list indicated by slabs_clsid. Note that the slabs_clsid is salted with the type of the queue, hence each slab group may enlist multiple lists.

2) Standard operations of “adding an element to the front”.

3) Increase the global array sizes.

static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
...
static unsigned int sizes[LARGEST_ID];

item.c:59

assoc_insert - add to hash map

int assoc_insert(item *it, const uint32_t hv) { // scr: again, hv -> hash value
    unsigned int oldbucket;

... // scr: expanding related operations
    } else {
        it->h_next = primary_hashtable[hv & hashmask(hashpower)]; // scr:  1)
        primary_hashtable[hv & hashmask(hashpower)] = it;         // scr:  2)
    }

... // scr: expanding related operations
}

assoc_insert@assoc.c

1) Deal with potential conflict. If there is no, the h_next will be set to null.

2) Set the item to the bucket in primary_hashtable.

...
static item** primary_hashtable = 0;
...

assoc.c:42

The expanding logic omitted here will be covered in following articles.

do_item_unlink

void do_item_unlink(item *it, const uint32_t hv) {
    MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes);
    if ((it->it_flags & ITEM_LINKED) != 0) {
        it->it_flags &= ~ITEM_LINKED;         // scr: -------------------> 1)
... // scr: stat
        assoc_delete(ITEM_key(it), it->nkey, hv); // scr: ---------------> 2)
        item_unlink_q(it);                    // scr: -------------------> 3)
        do_item_remove(it);                   // scr: -------------------> *)
    }
}

do_item_unlink@item.c

1) Clear ITEM_LINKED in it->it_flags.

2) Remove the item from hash map.

3) Remove the item from linked list.

*) The actual releasing of an item will be covered in the next article.

item_unlink_q - remove from linked list

Likewise, item_unlink_q is a thread safe wrapper of the workhorse method do_item_unlink_q.

static void item_link_q(item *it) {
    pthread_mutex_lock(&lru_locks[it->slabs_clsid]);
    do_item_link_q(it);
    pthread_mutex_unlock(&lru_locks[it->slabs_clsid]);
}

item_unlink_q@item.c

static void do_item_unlink_q(item *it) {
    item **head, **tail;
    head = &heads[it->slabs_clsid];           // scr: -------------------> 1)
    tail = &tails[it->slabs_clsid];

    if (*head == it) {                        // scr: -------------------> 2)
        assert(it->prev == 0);
        *head = it->next;
    }
    if (*tail == it) {
        assert(it->next == 0);
        *tail = it->prev;
    }
    assert(it->next != it);
    assert(it->prev != it);

    if (it->next) it->next->prev = it->prev;
    if (it->prev) it->prev->next = it->next;
    sizes[it->slabs_clsid]--;                 // scr: -------------------> 3)
    return;
}

do_item_unlink_q@item.c

1) Same, get the head and tail of the respective LRU linked list indicated by slabs_clsid.

2) Standard operations of “removing an element from a linked list”.

3) Decrease the global array sizes.

static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
...
static unsigned int sizes[LARGEST_ID];

item.c:59

assoc_delete - remove from hash map

static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
    item **pos;
    unsigned int oldbucket;

... // scr: expanding related operations
    } else {
        pos = &primary_hashtable[hv & hashmask(hashpower)]; // scr: -----> 1)
    }

    while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
        pos = &(*pos)->h_next; // scr: ----------------------------------> 2)
    }
    return pos;
}

...

void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
    item **before = _hashitem_before(key, nkey, hv);

    if (*before) {
        item *nxt;
...
        nxt = (*before)->h_next; // scr: --------------------------------> 3)
        (*before)->h_next = 0;   /* probably pointless, but whatever. */
        *before = nxt; // scr: ------------------------------------------> 4)
        return;
    }
    /* Note:  we never actually get here.  the callers don't delete things
       they can't find. */
    assert(*before != 0);
}

assoc_delete@assoc.c

1) Get the hash bucket using hv.

2) Go through the conflict chain and compare the key. Note that the result value is the address of the next member of the element before the found one. When there is no conflict, the address is the bucket itself.

3) Set the next element after the found one to temporary variable nxt.

4) Update the next member of the element before the found one.

Take home

Try this.

Understanding The Memcached Source Code - Slab III

holmeshe — Fri, 28 Sep 2018 21:55:00 +0000

slab allocator (I, II, III - this article) 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,

LRU algorithm (I , II) for entry expiration; and an

event driven model (not complete) based on libevent; and the

consistent harsh (not complete) for data distribution,

are built around it.

Last time we saw the memory allocating process, which further formulates slabs and the derivative “free lists” (a.k.a., slots). This time we will examine how to take advantage of the established data structures to “slab allocate / release” memory chunks which will be used to store items.

Slab alloc

Firstly, we look at

do_slabs_alloc

which is opposite to the discussed do_slabs_free.

Note that the “public” interface of do_slabs_alloc is slabs_alloc which is basically a thread-safe wrapper that locks the core data structures manipulated by the Memcached instance that is configured as multithreaded.

void *slabs_alloc(size_t size, unsigned int id, unsigned int *total_chunks,
        unsigned int flags) {
    void *ret;

    pthread_mutex_lock(&slabs_lock);
    ret = do_slabs_alloc(size, id, total_chunks, flags);
    pthread_mutex_unlock(&slabs_lock);
    return ret;
}

slabs_alloc@slabs.c

...
        case 't':
            settings.num_threads = atoi(optarg);
            if (settings.num_threads <= 0) {
                fprintf(stderr, "Number of threads must be greater than 0\n");
                return 1;
            }
            /* There're other problems when you get above 64 threads.
             * In the future we should portably detect # of cores for the
             * default.
             */
            if (settings.num_threads > 64) {
                fprintf(stderr, "WARNING: Setting a high number of worker"
                                "threads is not recommended.\n"
                                " Set this value to the number of cores in"
                                " your machine or less.\n");
            }
            break;
...

main@memcached.c:5572

static void *do_slabs_alloc(const size_t size, unsigned int id, unsigned int *total_chunks,
        unsigned int flags) {
    slabclass_t *p;
    void *ret = NULL;
    item *it = NULL;
...
    p = &slabclass[id]; // scr: ----------------------------------------> 1)
...
    if (total_chunks != NULL) {
        *total_chunks = p->slabs * p->perslab; // scr: -----------------> 2)
    }
    /* fail unless we have space at the end of a recently allocated page,
       we have something on our freelist, or we could allocate a new page */
    if (p->sl_curr == 0 && flags != SLABS_ALLOC_NO_NEWPAGE) { // scr: --> *)
        do_slabs_newslab(id); // scr: ----------------------------------> 3)
    }

    if (p->sl_curr != 0) {
        /* return off our freelist */
        it = (item *)p->slots; // scr: ---------------------------------> 4)
        p->slots = it->next;
        if (it->next) it->next->prev = 0;
        /* Kill flag and initialize refcount here for lock safety in slab
         * mover's freeness detection. */
        it->it_flags &= ~ITEM_SLABBED; // scr: -------------------------> 5)
        it->refcount = 1;
        p->sl_curr--;
        ret = (void *)it; // scr: --------------------------------------> 6)
    } else {
        ret = NULL;
    }

...
    return ret;
}

do_slabs_alloc@slabs.c

1) For item allocation, id indicates the slab class that suits the requested item size best. In other words, id is selected using the actual item size, the process of which will be discussed very soon.

2) total_chunks is the parameter that outputs the total number of memory chunks (entries in the free list) available for the slab class. if (total_chunks != NULL) suggests that the argument is optional.

*) As the name indicates, SLABS_ALLOC_NO_NEWPAGE (flags) prevents this method to allocate new slab when there is no memory chunk available. This option is not used in the normal path of item allocation, hence is ignored for now.

3) When there is no free memory chunk, allocate a new slab. Here p->sl_curr indicates the number of available chunks, whose value decreases each time this method got called (in step 5 below).

Conversely, this field is increased in do_slabs_free. Note that new slab has also been covered from here.

4) Remove the front element ( f ) from the free list, and set it to it.

In do_slabs_free, an element is added to the front of the free list.

5) Clear the ITEM_SLABBED for the chuck ( f ), set its reference count to 1, and reduce p->sl_curr by 1.

Likewise, this flag is set in do_slabs_free.

6) Return ( f ).

Next, we look at the process of determining the id based on item size, the workhorse method of which is

slabs_clsid

unsigned int slabs_clsid(const size_t size) {
    int res = POWER_SMALLEST;

    if (size == 0)
        return 0;
    while (size > slabclass[res].size)
        if (res++ == power_largest)     /* won't fit in the biggest slab */
            return 0;
    return res;
}

do_slabs_alloc@slabs.c

slabs_clsid consists mainly of a while loop that linear search the possible smallest slab class that can contain the requested size. This method is called from do_item_alloc before slabs_alloc. We will discuss do_item_alloc in the following post.

item *do_item_alloc(char *key, const size_t nkey, const unsigned int flags,
                    const rel_time_t exptime, const int nbytes,
                    const uint32_t cur_hv) {
...
    unsigned int id = slabs_clsid(ntotal);
    if (id == 0)
        return 0;
...
        it = slabs_alloc(ntotal, id, &total_chunks, 0);
...

do_item_alloc@items.c

Understanding The Memcached Source Code - Slab II

holmeshe — Mon, 17 Sep 2018 20:17:00 +0000

slab allocator (I, II - this article , III) 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,

LRU algorithm (I , II) for entry expiration; and an

event driven model (not complete) based on libevent; and the

consistent harsh (not complete) for data distribution,

are built around it.

This time we continue examining how slab s memory is allocated.

Firstly we look at the two arguments for slabs_init, which were passed over in the previous article. The first one is settings.maxbytes. It limits the overall memory that can be used by the memcached instance. In slabs_init, the value of settings.maxbytes is assigned to the global variable mem_limit which will be used very soon.

void slabs_init(const size_t limit, const double factor, const bool prealloc, const uint32_t *slab_sizes) {
...
    mem_limit = limit; // scr: here
...

slabs_init@memcached.c

...
  settings.maxbytes = 64 * 1024 * 1024; /* default is 64MB */
...
        case 'm':
            settings.maxbytes = ((size_t)atoi(optarg)) * 1024 * 1024;
            break;
...

memcached.c:210,5493

  static size_t mem_limit = 0;

memcached.c:43

The other argument is preallocate. It determines whether to preallocate slab for each slab class. This argument is toggled with L command line argument.

...
   bool preallocate = false;
...
        case 'L' :
            if (enable_large_pages() == 0) {
                preallocate = true;
            } else {
                fprintf(stderr, "Cannot enable large pages on this system\n"
                    "(There is no Linux support as of this version)\n");
                return 1;
            }
            break;
...

main@memcached.c:5350,5597

Next, we look at the method for slabs memory allocation itself.

New slab

do_slabs_newslab

More specific, this method allocates one 1M sized slab for the slab class indicated by the parameter id.

static int do_slabs_newslab(const unsigned int id) {
    slabclass_t *p = &slabclass[id]; // scr: ----------------------------> 1)
    slabclass_t *g = &slabclass[SLAB_GLOBAL_PAGE_POOL]; // scr: ---------> *)
    int len = settings.slab_reassign ? settings.item_size_max // scr: ---> 2)
        : p->size * p->perslab;
    char *ptr;

    if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0 // -> 3)
         && g->slabs == 0)) {
        mem_limit_reached = true;
        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }

    if ((grow_slab_list(id) == 0) || // scr: ----------------------------> 4)
        (((ptr = get_page_from_global_pool()) == NULL) && // scr: -------> *)
        ((ptr = memory_allocate((size_t)len)) == 0))) { // scr: ---------> 5)

        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }

    memset(ptr, 0, (size_t)len);
    split_slab_page_into_freelist(ptr, id); // scr: ---------------------> 6)

    p->slab_list[p->slabs++] = ptr; // scr: -----------------------------> 7)
    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);

    return 1;
}

do_slabs_newslab@slabs.c

1) slabclass[id] is one of the slab class , the initialization of which is discussed in last article.

2) settings.slab_reassign determines whether to enlist a rebalancing mechanism, which recycles the unused slabs and redistributes them across slab classes. This requires that slabs contained in all slab classes be of the same size, hence this setting also decides whether to use unanimous (i.e., settings.item_size_max, or 1M as mentioned before) or heterogeneous (i.e., p->size * p->perslab) slabs. Besides its associated command-line argument "slab_reassign", the value can be controlled by another argument "modern". For the positivity the name “modern” implies, 1M will be used throughout the text.

...
    settings.slab_reassign = false;
...
            case SLAB_REASSIGN:
                settings.slab_reassign = true;
            break;
...

main@memcached.c:238,5694

            case MODERN:
                /* Modernized defaults. Need to add equivalent no_* flags
                 * before making truly default. */
                settings.slab_reassign = true;
                settings.slab_automove = 1;
...
            break;

main@memcached.c:5820

N.b. *, rebalancing mechanism will be discussed later when we have a better understanding of the LRU module.

3) Check if the memory usage will exceed the upper limit.

4) grow_slab_list checks if we need to increase slabclass_t.slab_list, if so, grows it.

static int grow_slab_list (const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    if (p->slabs == p->list_size) {
        size_t new_size =  (p->list_size != 0) ? p->list_size * 2 : 16;
        void *new_list = realloc(p->slab_list, new_size * sizeof(void *));
        if (new_list == 0) return 0;
        p->list_size = new_size;
        p->slab_list = new_list;
    }
    return 1;
}

grow_slab_list@slabs.c

5) memory_allocate allocates the actual memory for the slab. As discussed, here the value of len is 1M.

static void *memory_allocate(size_t size) {
    void *ret;

    if (mem_base == NULL) {
        /* We are not using a preallocated large memory chunk */
        ret = malloc(size);
    } else { // scr: when preallocate is set to true
...

memory_allocate@slabs.c

6) split_slab_page_into_freelist initializes (frees) the newly allocated slab preparing for objects storing. This method will be discussed in the next section.

7) Add the newly allocated slab to the slabclass_t.slab_list.

What has happened so far can be summarized with the following figure, (we assume do_slabs_newslab(n) is called two times)

Now we look inside the 1M slab in step 6).

split_slab_page_into_freelist

static void split_slab_page_into_freelist(char *ptr, const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    int x;
    for (x = 0; x < p->perslab; x++) {
        do_slabs_free(ptr, 0, id);
        ptr += p->size;
    }
}

split_slab_page_into_freelist@slabs.c

This method goes through all the _item chunk_s (in the size of slabclass_t.size) within a slab. And for each of them, the method initializes its meta data by calling do_slabs_free. Another way to interpret this process is “split a slab into item free list”. As you might have already figured out, this “free list” will be used by item allocation in the future.

do_slabs_free

static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
    slabclass_t *p;
    item *it;
...
    p = &slabclass[id];

    it = (item *)ptr;
    it->it_flags = ITEM_SLABBED; // scr: ---------------> 1)
    it->slabs_clsid = 0;
    it->prev = 0; // scr: ------------------------------> 2)
    it->next = p->slots;
    if (it->next) it->next->prev = it;
    p->slots = it;

    p->sl_curr++; // scr: ------------------------------> 3)
    p->requested -= size;
    return;
}

do_slabs_free@slabs.c

This method works on item meta data that is populated at the beginning of an item chunk.

typedef struct _stritem {
    /* Protected by LRU locks */
    struct _stritem *next;
    struct _stritem *prev;
...
    uint8_t         it_flags;   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
...
} item;

main@memcached.c:5820

1) Initialize some fields. item is another core data structure, we will come back to item data structure later.

2) Add the item to the front of the linked list (a.k.a., free list). And update the list head, slabclass_t.slots.

3) Update the available (free list) slot count, slabclass_t.sl_curr; and updates the slabclass_t.requested for statistic. Note that here we are not actually releasing an item , so the passed size is 0.

Slab preallocate

Next we look at how do_slabs_newslab is used. One place it gets called is from the discussed slabs_init when preallocate is set to true,

void slabs_init(const size_t limit, const double factor, const bool prealloc, const uint32_t *slab_sizes) {
...
    if (prealloc) {
        slabs_preallocate(power_largest);
    }
}

slabs_init@slabs.c

static void slabs_preallocate (const unsigned int maxslabs) {
    int i;
    unsigned int prealloc = 0;

    /* pre-allocate a 1MB slab in every size class so people don't get
       confused by non-intuitive "SERVER_ERROR out of memory"
       messages.  this is the most common question on the mailing
       list.  if you really don't want this, you can rebuild without
       these three lines.  */

    for (i = POWER_SMALLEST /* scr: 1 */; i < MAX_NUMBER_OF_SLAB_CLASSES; i++) {
        if (++prealloc > maxslabs)
            return;
        if (do_slabs_newslab(i) == 0) {
            fprintf(stderr, "Error while preallocating slab memory!\n"
                "If using -L or other prealloc options, max memory must be "
                "at least %d megabytes.\n", power_largest);
            exit(1);
        }
    }

}

slabs_preallocate@slabs.c

This method simply goes through the slabclass starting from the POWER_SMALLEST, i.e., 1st entry, and allocate one slab for each of them. Note that the 0th is a special slab class used by mentioned rebalancing mechanism.

#define POWER_SMALLEST 1
#define POWER_LARGEST 256 /* actual cap is 255 */
#define SLAB_GLOBAL_PAGE_POOL 0 /* magic slab class for storing pages for reassignment */

memcached.h:88

References

Same to the last article.

Understanding The Memcached Source Code - Slab I

holmeshe — Wed, 12 Sep 2018 21:17:00 +0000

slab allocator (I - this article , II , III) 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,

LRU algorithm (I , II) for entry expiration; and an

event driven model (not complete) based on libevent; and the

consistent harsh (not complete) for data distribution,

are built around it.

Variants of slab allocator is implemented in other systems, such as nginx and Linux kernel, to fight a common problem called memory fragmentation. And this article will, of course, focus on memcached’s implementation of the algorithm.

memcached version: 1.4.28

Firstly, let’s answer some questions.

Introduction

What is a slab

slab s are pre-allocated 1M memory chunks that can be subdivided for numerous objects. They are grouped into slab class es to serve allocation requests for various sizes.

What is memory fragmentation, how it occurs

In particular, slab allocator curbs internal memory fragmentation. This kind of fragmentation exits within an allocated memory chunk. In the context of OS kernel, for instance, the fundamental unit allocated by memory management sub-system is called a page.

On the other hand, external memory fragmentation exists across chunks, and the solution of which (keyword: buddy) belongs to another story.

The most common phenomenon where internal fragmentation causes the problem is as following:

1) malloc of small objects is called a lot of times; and in the meantime;

2) free of those objects is called a lot of times.

The above process generates (a lot of) nominal “free” memory that can not be utilized, as the discrete holes of various sizes, or fragments , cannot be reused by subsequent mallocs for any objects that are larger than them.

Why memory fragmentation is bad

The impact of memory fragmentation is similar to that of memory leak - periodical system reboot is inevitable whenever the fragments accumulate to a certain level, which, increase the complexity in system operation, or even worse, leads to bad user experiences.

How the problem is fixed

Slab allocator does not eliminate internal fragmentation. Instead, it converges the fragments and locks them in fixated memory locations. This is done by 1) categorizing objects of similar sizes in classes ; and 2) allocating objects belonging to the same class only on the same group of “ slab s”, or, a slab class.

The detail devil is in the code, so we start reading the code.

reminder: memcached version is 1.4.28

The core data structure in use

typedef struct {
    unsigned int size;      /* sizes of items */
    unsigned int perslab;   /* how many items per slab */

    void *slots;           /* list of item ptrs */
    unsigned int sl_curr;   /* total free items in list */

    unsigned int slabs;     /* how many slabs were allocated for this class */

    void **slab_list;       /* array of slab pointers */
    unsigned int list_size; /* size of prev array */

    size_t requested; /* The number of requested bytes */
} slabclass_t;

static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];

slabclass_t@slabs.c

Module initialization

In this section we examine slabs_init that initializes slabclass[MAX_NUMBER_OF_SLAB_CLASSES] array. In particular, this process initializes the values of two fields, i.e., slabclass_t.size, the item (object) size of each slab class , and slabclass_t.perslab the item number one slab contains. This method is called from here as one of the init steps before the logic enters the main even loop.

...
    assoc_init(settings.hashpower_init);
    conn_init();
    slabs_init(settings.maxbytes, settings.factor, preallocate,
               use_slab_sizes ? slab_sizes : NULL);
...

main@memcached.c:5977

In this step slab_sizes and settings.factor jointly control the routes in which sizes of each slab class are decided, they are:

 uint32_t slab_sizes[MAX_NUMBER_OF_SLAB_CLASSES];

main@memcached.c:5372

settings.factor = 1.25;

settings_init@memcached.c:217

a) if slab_sizes is not NULL, the values within the array are used directly; and

b) otherwise, the sizes are calculated as base size × n × settings.factor where n is the index within slabclass.

Besides the default values, the two arguments can be set at runtime as well.

...
        case 'f':
            settings.factor = atof(optarg);
            if (settings.factor <= 1.0) {
                fprintf(stderr, "Factor must be greater than 1\n");
                return 1;
            }
            break;
...
        case 'o': /* It's sub-opts time! */
...
            case SLAB_SIZES:
                if (_parse_slab_sizes(subopts_value, slab_sizes)) {
                    use_slab_sizes = true;
                } else {
                    return 1;
                }
            break;
...

main@memcached.c:5558, 5810

The other two arguments of this method settings.maxbytes and preallocate will be discussed soon. For now we set false to preallocate and ignore the relevant logic flow.

Next we look at the slabs_init itself.

void slabs_init(const size_t limit, const double factor, const bool prealloc, const uint32_t *slab_sizes) {
    int i = POWER_SMALLEST /* scr: 1 */ - 1;
    unsigned int size = sizeof(item) + settings.chunk_size; // scr: ---------> b 1)
...
    memset(slabclass, 0, sizeof(slabclass));

    while (++i < MAX_NUMBER_OF_SLAB_CLASSES-1) {
        if (slab_sizes != NULL) { // scr: -----------------------------------> a 1)
            if (slab_sizes[i-1] == 0)
                break;
            size = slab_sizes[i-1];
        } else if (size >= settings.item_size_max / factor) {
            break;
        }
        /* Make sure items are always n-byte aligned */
        if (size % CHUNK_ALIGN_BYTES) // scr: ---------------------------------> 2)
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);

        slabclass[i].size = size;
        slabclass[i].perslab = settings.item_size_max / slabclass[i].size; // -> 3)
        if (slab_sizes == NULL)
            size *= factor; // scr: -----------------------------------------> b 4)
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }
    }
    // scr: -------------------------------------------------------------------> 5)
    power_largest = i;
    slabclass[power_largest].size = settings.item_size_max;
    slabclass[power_largest].perslab = 1;
...
}

slabs_init@slabs.c

Route a

1) use the values in slab_sizes;

2) align the size to CHUNK_ALIGN_BYTES, and give the result to slabclass[i].size;

3) calculate the slabclass[i].perslab;

5) use the settings.item_size_max to initialize the last slab class.

Note that settings.item_size_max is the size of each slab , hence it is also the max size of items that are allocated on slabs. Likewise, the value of settings.item_size_max can be decided in runtime.

 settings.item_size_max = 1024 * 1024;

settings_init@memcached.c:226

        case 'I':
            buf = strdup(optarg);
            unit = buf[strlen(buf)-1];
            if (unit == 'k' || unit == 'm' ||
                unit == 'K' || unit == 'M') {
                buf[strlen(buf)-1] = '\0';
                size_max = atoi(buf);
                if (unit == 'k' || unit == 'K')
                    size_max *= 1024;
                if (unit == 'm' || unit == 'M')
                    size_max *= 1024 * 1024;
                settings.item_size_max = size_max;
            } else {
                settings.item_size_max = atoi(buf);
            }
            free(buf);
            if (settings.item_size_max < 1024) {
                fprintf(stderr, "Item max size cannot be less than 1024 bytes.\n");
                return 1;
            }
            if (settings.item_size_max > 1024 * 1024 * 128) {
                fprintf(stderr, "Cannot set item size limit higher than 128 mb.\n");
                return 1;
            }
            if (settings.item_size_max > 1024 * 1024) {
                fprintf(stderr, "WARNING: Setting item max size above 1MB is not"
                    " recommended!\n"
                    " Raising this limit increases the minimum memory requirements\n"
                    " and will decrease your memory efficiency.\n"
                );
            }
            break;

main@memcached.c:5626

Route b

1) calculate the base size with settings.chunk_size plus the extra bytes for metadata (item will be discussed in following articles);

2) align the size to CHUNK_ALIGN_BYTES, and give the result to slabclass[i].size; (same to route a)

3) calculate the slabclass[i].perslab; (same to route a)

4) calculate the size for the next slab class using factor (settings.factor);

5) use the settings.item_size_max to initialize the last slab class. (same to route a)

References

memcached wiki

第2回　memcachedのメモリストレージを理解する

 Memcached源码分析之存储机制Slabs（7）

Understanding Malloc

Ch8 - Slab Allocator