Understanding The memcached Source Code — Slab I

Holmes He
Holmes He
Sep 16, 2018 · 4 min read
Photo by Brooke Lark on Unsplash

Slab allocator is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilised. The other 3 parts, namely, LRU algorithm for entry expiration; and an event driven model based on libevent; and the consistent harsh for data distribution, are built around it.

Slab I (this article)
Slab II
Slab III
LRU I
LRU II
LRU III
Event driven I

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

Memcached version: 1.4.28

Firstly, let’s answer some questions.

Introduction

What is a slab

What is memory fragmentation, how it occurs

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 problem is as following:

1) malloc of small objects are called a lot of times; and in the mean time;

2) free of those objects are 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, can not be reused by subsequent mallocs for any objects that are larger than them.

Why memory fragmentation is bad

How the problem is fixed

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

Module initialization

SourceRead

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

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 run time as well.

SourceRead

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.

SourceRead

Route a

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 is allocated on slabs. Likewise, the value of settings.item_size_max can be set in run time

SourceRead

Route b

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


Originally published at holmeshe.me.

source code

If you are also interested in source code exploration &…

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store