Understanding The Memcached Source Code - LRU I
Tags: memcachedsourcecod, memcached, cache, lru
Published: 2018-12-23 01:37:31

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

[![](../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 - this article[, II)](https://holmeshe.me/understanding-memcached-source-code-V/) 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 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:

![hash map perspective](https://thepracticaldev.s3.amazonaws.com/i/9ssuslvuvvajxr1jo901.png)

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

![linked list perspective](https://thepracticaldev.s3.amazonaws.com/i/tsphpdbjw9u2wgumquha.png)

# Core data structure - item

```c
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;
```
<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;">do_item_unlink@item.c</text></a></center>
## 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](https://holmeshe.me/understanding-memcached-source-code-II/#do-slabs-free). With the help of this data structure, we can now examine the chunk more closely.

![item chunk](https://thepracticaldev.s3.amazonaws.com/i/wh44s95ketp608gg67e7.png)

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

# do\_item\_link

```c
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;
}
```
<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;">do_item_link@item.c</text></a></center>

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](https://holmeshe.me/understanding-memcached-source-code-II/#do-slabs-free) and [do\_slabs\_alloc](https://holmeshe.me/understanding-memcached-source-code-III/#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](https://holmeshe.me/understanding-memcached-source-code-III/#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](https://holmeshe.me/cpp-pointers/) 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`.  

```c
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]);
}
```
<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_link_q@item.c</text></a></center>

```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;
}
```
<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;">do_item_link_q@item.c</text></a></center>

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.

```c
static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
...
static unsigned int sizes[LARGEST_ID];
```  
<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.c:59</text></a></center>  

## assoc\_insert - add to hash map

```c
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
}
```
<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) 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.

```c
...
static item** primary_hashtable = 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:42</text></a></center>  

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

# do\_item\_unlink

```c
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: -------------------> *)
    }
}
```
<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;">do_item_unlink@item.c</text></a></center>

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

```c
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]);
}
```
<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_unlink_q@item.c</text></a></center>  

```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;
}
```
<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;">do_item_unlink_q@item.c</text></a></center>

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.

```c
static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
...
static unsigned int sizes[LARGEST_ID];
```
<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.c:59</text></a></center>  

## assoc\_delete - remove from hash map

```c
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);
}
```
<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_delete@assoc.c</text></a></center>

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](https://leetcode.com/problems/lru-cache/).