最近工作上的需要，需要做一个LRU形式管理内存的分配器，首先想到的就是Memcached这个项目。早些年粗略的看过一些，有个大体的了解，这一次看下来发现其LRU算法做了不少的改动。

Tags:

via Pocket https://ift.tt/3jURfbl original site

July 04, 2021 at 08:28PM

Comments

from: github-actions[bot] on: 7/4/2021

Memcached的存储原理解析 by codedump

概述

最近工作上的需要，需要做一个LRU形式管理内存的分配器，首先想到的就是Memcached这个项目。早些年粗略的看过一些，有个大体的了解，这一次看下来发现其LRU算法做了不少的改动。

本文解析Memcached内存管理这部分的内容，基于Memcached 1.6.9版本。

Memcached将单个KV数据的存储，都放在item这个结构体中，每个item数据同时存在于这几个数据结构之中：

slabclass_t：以分级存储机制来提供内存的数据结构（下面展开详细讨论slabclass）。
链表：当item被使用时，存储在LRU链表中（下面详细讨论LRU链表）；当item被释放之后，空闲的item形成一个链表以备再次使用。
hash表：用于根据键值查找数据的数据结构。

hash表自不必多说，Memcached中将item组织成一个名为primary_hashtable的hash数组，根据键值查找元素时，首先计算出键值的hash值，再到对应的数组元素中遍历查找数据。

slabclass_t结构体以分级的方式分配内存给item，这样做有以下几个好处：

统一了内存的管理，避免了内存的碎片化。
分配、释放内存时都能到对应的slab中。

slabclass_t

定义

slabs.c中定义了类型为slabclass_t、大小为MAX_NUMBER_OF_SLAB_CLASSES的数组slabclass，用于分级存储只用。

数组中的每个slabclass_t元素，其能分配出去的内存大小递增，由如下的规则决定：

每个数组可分配的内存大小都要8字节对齐（CHUNK_ALIGN_BYTES）,这个大小保存在slabclass_t的size成员中。
数组的第一个slabclass_t元素的可分配内存大小为sizeof(item) + settings.chunk_size。这之后的slabclass_t可分配内存大小，都在上一个的元素的基础上放大factor倍，同时还要8字节对齐。
每次分配一个页面的大小由配置项settings.slab_page_size来决定，因此每一个slabclass_t元素的一个页面能容纳的item数量为settings.slab_page_size / slabclass[i].size。

当需要分配一块大小的内存时，首先需要根据其大小，计算出该尺寸最终对应到上面的哪个元素，这个数组索引在Memcached中被称为clsid，这个计算索引的过程参见函数slabs_clsid。

比如：

slabclass[0].size = 56，fator参数为1.2，那么slabclass[1].size = (56 * 1.25)向上对齐8位 = 72，以此类推。
假设需要分配的内存大小为60，就会去找slabclass_t.size >= 60的第一个slabclass，在这个例子中返回的clsid是1，也就是slabclass[1]。
内存分配时根据大小向上取满足条件的第一个slab的做法，优点在于方便了内存的分配管理，缺陷是会浪费掉部分空间，比如上面的例子中，将大小为72的slab用于60的内存，那么12字节的空间就被浪费掉了。

每一个slab中，需要维持两类空间：

按照页面大小来分配的一整页空间，每个页面又按照该slab的大小划分成了多个不同的chunk。
管理使用已被释放的item。

在slabclass_t结构体中，以下几个成员用来维护该class的内存信息：

slab_list：保存页面的数组，其大小保存在slabs成员中。
sl_curr：可用的item数量。
slots：保存在该slabclass_t中空闲item的链表头。

即：

在Memcached的这一套内存管理体系中，一个页面被称为一个slab，其大小为settings.slab_page_size；页面中可以分割成多个slot用来分配内存，一个slot的大小由该slabclass的初始大小及factor来决定，但是需要向上补齐为8位对齐的大小。
一个slabclass中，有预分配好的页面数组，也有被回收的元素组成的空闲slot链表，分配元素时优先从空闲链表中分配（见函数do_slabs_alloc）。

内存分配

既然Memcached是一个LRU形式的内存分配器，所以其内存是有限制的，系统中定义了如下几个全局变量来保存当前系统的内存分配信息：

static size_t mem_limit：内存分配的上限。
static size_t mem_malloced：当前分配的内存大小。
static void *mem_base：保存内存的起始地址。
static void *mem_current：保存内存分配的当前地址。

在初始化时，系统首先会根据mem_limit分配一大块内存出来。

后续各个slabclass需要内存时，如下操作：

就从这一大块内存中每次分配一个页面（大小为settings.slab_page_size）出去用。
将分配好的内存按照每个slab中容纳的slot大小切分成多个slot。（见函数split_slab_page_into_freelist）。

LRU算法

旧的LRU算法及其问题

以往的LRU算法，基本做法都是这样的：

创建一个LRU链表，每次新加入的元素都放在链表头。
如果元素被访问了一次，同样从当前链表中摘除放到链表头。
需要淘汰元素时，从链表尾开始找可以淘汰的元素出来淘汰。

这个算法有如下几个问题：

元素被访问一次就会被放到LRU链表的头部，这样即便这个元素可以被淘汰，也会需要很久才会淘汰掉这个元素。
由于上面的原因，从链表尾部开始找可以淘汰的元素时，实际可能访问到的是一些虽然不常被访问，但是还没到淘汰时间（即有效时间TTL还未过期）的数据，这样会一直沿着链表往前找很久才能找到适合淘汰的元素。由于这个查找被淘汰元素的过程是需要加锁保护的，加锁时间一长影响了系统的并发。

综上，经典的LRU链表问题的核心在于：

只需要一次被访问就能让元素远离被淘汰的地方。
以及如何高效定位到更可能被淘汰的元素。

从Memcached 1.5版本开始，引入了所谓的分段LRU算法（Segmented LRU）来解决这些问题。

改进的分段LRU算法（Segmented LRU）

分段LRU算法中将LRU链表根据活跃度分成了三类：

HOT_LRU：存储热数据的LRU链表。
WARM_LRU：存储温数据（即活跃度不如热数据）的LRU链表。
COLD_LRU：存储冷数据的LRU链表。

需要说明的是：热（参数settings.hot_lru_pct）和暖（参数settings.warm_lru_pct）数据的占总体内存的比例有限制，而冷数据则无限。

#define HOT_LRU 0
#define WARM_LRU 64
#define COLD_LRU 128

同时，使用了heads和tais两个数组用来保存LRU链表：

#define POWER_LARGEST  256 /* actual cap is 255 */

#define LARGEST_ID POWER_LARGEST

static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];

上面分析slabclass的时候提到过，首先会根据被分配内存大小计算出来一个slabclass数组的索引。在需要从LRU链表中淘汰数据时，由于LRU链表分为了上面三类，那么就还需要再进行一次slabid | lru id计算（其实就是slabid + lru id），到对应的LRU链表中查找元素：

有了这三种LRU队列的初步印象，可以接下来解释这个分段LRU算法了。

前面提到，原有LRU算法最大的问题是：只要元素被访问过一次，就马上会被移动到LRU链表的前面，影响了后面对这个元素的淘汰。

首先，改进的算法中，加入了一个机制：只有当元素被访问两次以后，才会标记成活跃元素。

代码中引入了两个标志位，其置位的规则如下：

ITEM_FETCHED：第一次被访问时置位该标志位。
ITEM_ACTIVE：第二次被访问时（即it->it_flags & ITEM_FETCHED为true的情况下）置位该标志位。

ITEM_ACTIVE标志位清除的规则如下：

如果从链表尾遍历到某一个LRU链表时，该元素是链表的最后一个元素，则认为是不活跃的元素，即可以清除ITEM_ACTIVE标志位；

这样，有效避免了只访问一次就变成活跃元素的问题（见函数do_item_bump）。

以下的讨论中，元素变成活跃就意指“至少被访问两次以上”。

其次，由于从链表尾部往前查找可以淘汰的元素，中间可能会经历很多不能被淘汰的元素，影响了淘汰的速度，因此前面的分级LRU链表就能帮助程序快速识别出哪些元素可以被淘汰。三个分级的LRU链表之间的转换规则如下：

HOT_LRU：在HOT LRU队列中的数据绝不会到HOT_LRU队列的前面，只会往更冷的队列中放。规则是：如果元素变的活跃，就放到WARM队列中；否则如果不活跃，就直接放到COLD队列中。
WARM_LRU：如果WARM队列的元素变的活跃，就会移动到WARM队列头；否则往COLD队列移动。
COLD_LRU：从上面可知，COLD队列中的元素，都是不太活跃的了，所以当需要淘汰元素时都会首先到COLD LRU队列中找可以淘汰的数据。当一个在COLD队列的元素重新变成活跃元素时，并不会移动到COLD队列的头部，而是直接移动回去WARM队列。

以上需要注意的是：任何操作都不能将一个元素从WARM和COLD队列中移动回去HOT队列了，也就是从HOT队列中移动元素出去的操作是单向操作。

上述算法的状态机转换过程，可以参考下图。使用了这些规则来维护着三个队列之后，基本能保证COLD队列中的元素是不活跃的，这样查找起被淘汰元素也更快了。

综述起来，改进的分段LRU算法做了如下的优化：

需要至少两次被访问，才能变成活跃元素。
将元素按照被访问频率的冷热程度，划分为三种LRU链表来分段管理，加速了查找被淘汰元素的流程。

Pocket Readings

Memcached的存储原理解析