# Understanding The Memcached Source Code - LRU I

slab allocator (I, 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 , III) for entry expiration; and an

event driven model (I , II , III) 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 fast accessing of 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.

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

## Properties in discussion

next, prev - LRU list pointers, initialized in do_item_alloc (LRU III), used by item_link_q, item_unlink_q

h_next - hash collision list pointers, initialized in do_item_alloc (LRU III), used by assoc_insert, assoc_delete, various methods (LRU II)

time - last access time, set in do_item_link, used by lru_pull_tail (LRU III)

exptime - expire time indicated by request argument, initialized in do_item_alloc (LRU III), used by lru_pull_tail (LRU III)

nbytes - data size indicated by request argument, initialized in do_item_alloc (LRU III)

refcount - reference cound, initialized in do_slabs_alloc (Slab III), used by do_item_link

nsuffix - initialized in do_item_alloc (LRU III) with item_make_header

it_flags - initialized in do_item_alloc (LRU III), used by do_item_link, do_item_unlink

slabs_clsid - the LRU list the item belongs, initialized in do_item_alloc (LRU III), used by item_link_q, item_unlink_q

nkey - key size, calcuated in do_item_alloc (LRU III), used by 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.

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 is a thread safe wrapper of the workhorse method do_item_link_q.

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.

## assoc_insert - add to hash map

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

2) Set the item to the bucket in primary_hashtable.

The expanding logic omitted here will be covered in the next post.

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 later posts.

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

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.

## assoc_delete - remove from hash map

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.

That's it. Did I make a serious mistake? or miss out on anything important? Or you simply like the read. Link me on -- I'd be chuffed to hear your feedback.