按对象大小分组,复用 slab 中的固定块
Memcached 按完整缓存对象的大小选择 slab class,将页拆成等尺寸块;普通对象从对应空闲链表取块,释放后仍回到同一规格。
工程问题#
缓存反复创建和淘汰大小不同的对象,既要控制分配成本,也要在有限内存下重复利用空间。若所有对象都依赖通用堆逐个分配,碎片与管理开销会随工作负载变化。
实际实现#
do_item_alloc 先计算元数据、键和值等的总大小,再用 slabs_clsid 找到可容纳它的规格。slabs_init 按增长因子或显式大小表建立 class,每页切成固定数量的 chunk。普通单块对象从 class 的 slots 链表头取出,释放时挂回表头;无空闲块时可申请整页,上层分配路径还会尝试同 class 的 LRU 回收。
处理流程#
- 计算对象完整大小,包括 item 元数据、键、协议字段、值以及启用时的 CAS 数据。
- 顺序查找首个能容纳普通对象的 slab class;规格来自增长因子或显式配置,并做对齐。
- 进入受 slabs_lock 保护的分配器,若该 class 没有空闲块,尝试补充一页并拆成固定块。
- 从空闲链表头取一块,清除空闲标记并初始化引用计数;若失败,上层尝试回收后重试。
- 对象最终释放时,通过自身 next/prev 字段挂回对应 class 的空闲链表,等待后续复用。
源码片段#
固定版本 · 原文摘录249item *do_item_alloc(const char *key, const size_t nkey, const client_flags_t flags,250 const rel_time_t exptime, const int nbytes) {251 uint8_t nsuffix;252 item *it = NULL;253 char suffix[40];254 // Avoid potential underflows.255 if (nbytes < 2)256 return 0;257258 size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);259 if (settings.use_cas) {260 ntotal += sizeof(uint64_t);261 }262263 unsigned int id = slabs_clsid(ntotal);264 unsigned int hdr_id = 0;265 if (id == 0)266 return 0;选择规格依据完整对象大小而非纯 value 长度。CAS 启用时另加 64 位字段;后文再区分普通单块和大对象分块路径。
77unsigned int slabs_clsid(const size_t size) {78 int res = POWER_SMALLEST;7980 if (size == 0 || size > settings.item_size_max)81 return 0;82 while (size > slabclass[res].size)83 if (res++ == power_largest) /* won't fit in the biggest slab */84 return power_largest;85 return res;86}按 class 顺序寻找大小上界。超出单块上限但仍在 item_size_max 内的对象可能返回最大 class,交由 items.c 的 chunked 路径处理,不能据此断言它是普通单块。
243 while (++i < MAX_NUMBER_OF_SLAB_CLASSES-1) {244 if (slab_sizes != NULL) {245 if (slab_sizes[i-1] == 0)246 break;247 size = slab_sizes[i-1];248 } else if (size >= settings.slab_chunk_size_max / factor) {249 break;250 }251 /* Make sure items are always n-byte aligned */252 if (size % CHUNK_ALIGN_BYTES)253 size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);254255 slabclass[i].size = size;256 slabclass[i].perslab = settings.slab_page_size / slabclass[i].size;257 if (slab_sizes == NULL)258 size *= factor;可显式指定大小表,也可按 factor 增长;每种大小先按 CHUNK_ALIGN_BYTES 对齐,再计算一页的块数。并非所有部署都固定使用某一个增长因子。
421 p = &slabclass[id];422 assert(p->sl_curr == 0 || (((item *)p->slots)->it_flags & ITEM_SLABBED));423424 /* fail unless we have space at the end of a recently allocated page,425 we have something on our freelist, or we could allocate a new page */426 if (p->sl_curr == 0 && flags != SLABS_ALLOC_NO_NEWPAGE) {427 do_slabs_newslab(id);428 }429430 if (p->sl_curr != 0) {431 /* return off our freelist */432 it = (item *)p->slots;433 p->slots = it->next;434 if (it->next) it->next->prev = 0;435 /* Kill flag and initialize refcount here for lock safety in slab436 * mover's freeness detection. */437 it->it_flags &= ~ITEM_SLABBED;438 it->refcount = 1;439 p->sl_curr--;440 ret = (void *)it;无空闲块时尝试新增 slab 页;有块时从 slots 头部摘取,维护后继 prev、空闲标记和引用计数。公开 slabs_alloc 在这一段外持有 slabs_lock。
512 it = (item *)ptr;513 if ((it->it_flags & ITEM_CHUNKED) == 0) {514 it->it_flags = ITEM_SLABBED;515 it->slabs_clsid = id;516 it->prev = 0;517 it->next = p->slots;518 if (it->next) it->next->prev = it;519 p->slots = it;520521 p->sl_curr++;522 } else {523 do_slabs_free_chunked(it);普通对象利用自身 prev/next 挂回空闲链表头并增加空闲计数;ITEM_CHUNKED 对象走专门释放函数。这个链表是空闲块链表,不是活跃缓存对象的 LRU 队列。
171 for (i = 0; i < 10; i++) {172 /* Try to reclaim memory first */173 if (!settings.lru_segmented) {174 lru_pull_tail(id, COLD_LRU, 0, 0, 0, NULL);175 }176 it = slabs_alloc(id, 0);177178 if (it == NULL) {179 // We send '0' in for "total_bytes" as this routine is always180 // pulling to evict, or forcing HOT -> COLD migration.181 // As of this writing, total_bytes isn't at all used with COLD_LRU.182 if (lru_pull_tail(id, COLD_LRU, 0, LRU_PULL_EVICT, 0, NULL) <= 0) {183 if (settings.lru_segmented) {184 lru_pull_tail(id, HOT_LRU, 0, 0, 0, NULL);185 } else {186 break;187 }188 }189 } else {190 break;调用 slabs_alloc 失败时,上层可以尝试同 class 的 LRU 淘汰或段间移动。循环上限为 10;有回收逻辑不意味着任何请求都一定成功。
连续原文覆盖调用方、规格选择、规格建立、取块、归还和失败重试。整页拆块由 slabs.c 的 split_slab_page_into_freelist 完成,它按 perslab 次数调用 do_slabs_free。
收益与取舍#
工程分析带来的收益
- 已有空闲块时,取出和归还只需修改少量指针,避免每次分配都搜索任意大小的空闲区间。
- 规格和页管理使内存占用、可容纳对象数以及不同大小对象的压力可观察。
- 对象在空闲状态复用自身链表字段,不需要为每个空闲块再分配外部链表节点。
付出的代价
- 向上取整到 class 大小会产生块内浪费;增长因子越大,规格越少但浪费可能越明显。
- 一个 class 的空闲块不能直接当作另一规格使用;跨 class 调整需要额外的页迁移机制。
- 现有块的链表操作虽是 O(1),完整分配还包括 O(C) 的规格查找、锁等待、整页初始化及可能的 LRU 回收,不能统一写成恒定延迟。
可比较的选择
直接使用通用 malloc/free可交给通用分配器管理多种大小与跨规格复用,但需要结合缓存对象生命周期评估碎片、元数据和锁成本。
更细的 size class降低向上取整损失,但各 class 可能出现难以共享的空闲空间,规格查找和监控也更复杂。
版本与适用范围#
固定 Memcached 提交 2d51e364799b,正文重点是总大小不超过 slab_chunk_size_max 的普通单块对象。更大的对象有单独 header 和分块分配路径;slabs_clsid 返回最大 class 不代表大对象一定能装入一个块。页迁移、LRU 分段、持久内存和 extstore 未完整分析,不能把 slab 分配机制等同于缓存淘汰算法。
参考来源#
源码、官方文档与原始论文items.c · do_item_alloc / do_item_alloc_pull
slabs.c · slabs_init / slabs_clsid / do_slabs_alloc / do_slabs_free / split_slab_page_into_freelist
相关实现与比较#
4 个相关案例伙伴分配器把空闲物理页组织为不同 order 的连续块,并用空闲链表管理同阶块。
limit_req 把漏桶计算、红黑树查状态与队列回收组合起来,按配置的 key 管理请求速率。
QEMU 的 QEMUTimerList 用有序单链表维护定时器,链表头就是下一到期项。
缓存块命中后可能需要从队列中间移除,双向链表让这一步保持常数时间。