概述

最近工作上的需要,需要做一个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_tsize成员中。
  • 数组的第一个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

slabclass的分级存储

当需要分配一块大小的内存时,首先需要根据其大小,计算出该尺寸最终对应到上面的哪个元素,这个数组索引在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的链表头。

slabclass结构体示意图

即:

  • 在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链表实现

综上,经典的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

同时,使用了headstais两个数组用来保存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链表中查找元素:

将slabclass数组索引映射到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算法做了如下的优化:

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

参考资料