Memcached 自带了一个内存分配模块slab,自己在用户层实现了内存的分配,而不是完全依赖于系统的 malloc。这篇文章,来看看 Memcached slab 内存分配算法是怎么做的。
一个内存分配算法要考虑算法的效率,管理内存所占的空间和内存碎片的问题。这个是三个衡量点往往不能个个都得到满足,每个实现都会各有所长。slab 能较好的规避内存碎片的问题,但也带来了一定的内存浪费,算法的效率还不错。
Memcached slab 概述
在 Memcached 中,为键值对分配空间的时候都会调用 do_item_alloc() 函数,真正设计 slab 的是slabs_alloc() 这个函数:
void *slabs_alloc(size_t size, unsigned int id);
size 是所需分配空间的实际大小,id 是这个空间大小所对应的数量级。
slab class
slab 为空间的大小划分了数量级。在 memecached 初始化的时候可以设置 chrunk 和 factor 属性,前者是一个底数,后者是一个因子,前一个数量级乘于因子已得到新的数量级,依次可以推算下一级的数量级。
来看看内存管理的结构体 slabclass_t:
typedef struct {
// 每个内存块大小
unsigned int size; /* sizes of items */
// 每个slab 内存块的数量
unsigned int perslab; /* how many items per slab */
// 空闲的内存块会组成一个链表
void *slots; /* list of item ptrs */
// 当前空闲内存块的数量
unsigned int sl_curr; /* total free items in list */
// slab 数量
unsigned int slabs; /* how many slabs were allocated for this class */
// slab 指针
void **slab_list; /* array of slab pointers */
unsigned int list_size; /* size of prev array */
......
} slabclass_t;
现在对于某一级别的 slab 有如下印象图:
对于不同的 class 有如下印象图:
内存分配的过程
来看看 slab 内存分配入口函数做了什么?
void *slabs_alloc(size_t size, unsigned int id) {
void *ret;
// 每次内存的分配都需要加锁
pthread_mutex_lock(&slabs_lock);
ret = do_slabs_alloc(size, id);
pthread_mutex_unlock(&slabs_lock);
return ret;
}
do_slabs_alloc() 实际上会先检测是否有空闲的内存块,有则返回空闲的内存块;否则,会调用do_slabs_newslab() 分配新的内存。
static void *do_slabs_alloc(const size_t size, unsigned int id) {
slabclass_t *p;
void *ret = NULL;
item *it = NULL;
// 所需分配空间的数量级别不合法
if (id < POWER_SMALLEST || id > power_largest) {
MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
return NULL;
}
p = &slabclass[id];
assert(p->sl_curr == 0 || ((item *)p->slots)->slabs_clsid == 0);
// 如果指定的slab 内还有空闲的内存块,返回空闲的内存块,否则调用
// do_slabs_newslab()
// do_slabs_newslab() 为指定的slab 分配更多的空间
if (! (p->sl_curr != 0 || do_slabs_newslab(id) != 0)) {
/* We don't have more memory available */
ret = NULL;
} else if (p->sl_curr != 0) {
/* return off our freelist */
it = (item *)p->slots;
p->slots = it->next;
if (it->next) it->next->prev = 0;
p->sl_curr--;
ret = (void *)it;
}
......
return ret;
}
我们来看看 do_slabs_newslab() 是怎么做的:首先会看 slab_list 是否已经满了,如果满 了则 resize slab_list 并分配空间,将新分配的空间初始化后切割插入到空闲链表中。
static int do_slabs_newslab(const unsigned int id) {
slabclass_t *p = &slabclass[id];
// 计算需要分配内存的大小
int len = settings.slab_reassign ? settings.item_size_max
: p->size * p->perslab;
char *ptr;
// 扩大slab_list,并分配内存
if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||
(grow_slab_list(id) == 0) ||
((ptr = memory_allocate((size_t)len)) == 0)) {
MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
return 0;
}
// 将新分配的内存初始化,并切割插入到空闲链表中
memset(ptr, 0, (size_t)len);
split_slab_page_into_freelist(ptr, id);
// 调整slab_list 指针指向新分配的空间
p->slab_list[p->slabs++] = ptr;
mem_malloced += len;
MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
return 1;
}
do_slabs_newslab() 之前:
do_slabs_newslab() 之后:
slab 能较好的规避内存碎片的问题,但也带来了一定的内存浪费,算法的效率还不错。现在能够较好的理解这一句话。因为 slab 内存分配算法预先分配了一大块的连续紧凑的内存空间,只一点能将内存的使用都限定在紧凑连续的空间内;但很明显它会带来一定的浪费,因为每个 slab class 内的每个内存块大小都是固定的,数据的大小必须小于等于内存块的大小。
lru 机制
Memcached slab 还有一个超时淘汰的机制,当发现某个 slab class 内无空间可分配的时候,并不是立即去像上面所说的一样去扩展空间,而是尝试从已经被使用的内存块中寻找是否有已经超时的块,如果超时了,则原有的数据会被删除,这个内存块被作为结果内存分配的结果。
那如何快速找到这个块呢?对于某个 slab class,所有已使用和空闲的内存块都会被组织成一个链表,
static item *heads[LARGEST_ID];
static item *tails[LARGEST_ID];
这两个全局变量就保存这些链表的头指针和尾指针。对于新的数据插入,会更新 heads[classid],对于超时被剔除的数据删除操作,会更新 tails[classid]。
下面图解上述的过程:
转自:http://wiki.jikexueyuan.com/project/redis/slab.html
相关推荐
### Memcached内存分配与SLAB机制 #### 第1章 前言 本文将深入探讨Memcached中的内存分配原理及SLAB机制的核心概念。通过详细分析Memcached如何管理内存资源,帮助读者理解其高效内存利用背后的逻辑。 #### 第2章...
SLAB机制是Memcached为了高效管理内存而设计的一种内存分配策略。传统的内存分配方式在处理小块内存时效率低下,容易产生内存碎片。SLAB机制则解决了这个问题,它将内存划分为一系列的分页(chunk),每个分页又分为...
### Memcached Slab 分配器及其 LRU 机制详解 #### 第一章 前言 本文档将详细介绍 memcached 的内存管理机制,特别是 slab 分配器和 LRU(Least Recently Used)置换算法的工作原理。这些机制对于 memcached 的...
memcached采用了一种特殊的内存分配策略,名为Slab Allocation,以避免频繁的内存碎片和提高内存利用率。 1. Slab Allocation原理: Slab Allocation的核心思想是将内存分为多个大小不等的chunk(块),每个chunk...
调整 slab 分配策略,避免内存浪费;监控和调整超时时间,确保高并发下系统的响应速度。 七、Memcached与Linux的关系 在Linux环境下,Memcached可以充分利用操作系统的内存管理机制,如页缓存,进一步提高性能。...
1. **slab类分配器**:memcached使用slab分配器来管理内存,避免了内存碎片。slab被划分为多个大小不同的chunk,每个chunk用于存储特定大小的数据。每个 slab 分区由一系列连续的内存块(slabs)组成,每个slab内的...
- `memcached`采用slab分配机制来管理内存,将内存划分为不同大小的chunk,每个chunk对应一个slab类,避免了内存碎片。 6. **libevent事件驱动** - `memcached`利用libevent库实现非阻塞I/O,能够高效处理大量...
1. 内存管理:Memcached采用slab分配机制管理内存,将内存分为多个 slab 分区,每个分区内部又细分为多个chunk,以减少内存碎片。 2. 数据存储:键值对存储,键必须是字符串,值可以是任意类型(转换为二进制)。每...
Memcached采用slab分配器来管理内存,每个slab class包含一组相同大小的pages。当请求一个对象时,Memcached会查找合适的slab class来存放该对象。如果找不到,则创建一个新的slab class,并分配相应的pages。 - **...
当数据量超过单个服务器的内存限制时,可以将Memcached 部署在多台服务器上,通过一致性哈希策略将数据均匀分配到各个节点,从而实现数据的分布式存储和访问。 ### 3. 性能优化 - **内存管理**:Memcached 使用...
- mixi的memcached部署通常涉及到多个实例,通过客户端的智能路由策略实现数据分布。 - **TokyoTyrant案例**: - TokyoTyrant是一款由mixi工程师开发的兼容memcached协议的键值存储系统,具有更高的性能和稳定性。 ...
2. **内存管理**:Memcached使用slab分配器管理内存,避免了内存碎片问题。slab将内存分为多个大小固定的chunk,每个chunk用于存储特定大小的数据,提高了内存利用率。 3. **一致性哈希**:在分布式环境中,...
- 理解Memcached的 slab 分配机制,有效管理内存使用。 - 探索如何调整缓存大小、超时设置以适应不同应用场景。 6. **分布式缓存概念**: - Memcached可以部署在多台服务器上,形成分布式缓存集群。 - 了解一致...
1. **内存管理**:Memcached使用 slab 分配器来管理内存,避免了小块内存的碎片问题。 2. **一致性哈希**:分布式环境下的数据分布策略,确保数据迁移时尽可能少地影响缓存命中率。 3. **超时设置**:根据应用需求,...
- **Slab分配器**:Memcached采用slab分配器来管理内存,将内存划分为多个大小固定的chunk,每个chunk用于存储特定大小的数据,避免了内存碎片问题。 - **LRU策略**:当内存满时,使用最近最少使用(LRU)算法来...
- slab分配器:Memcached使用slab分配器管理内存,将内存预先分配为不同大小的chunk,减少内存碎片。 - 并发处理:通过调整并发连接数和线程池大小,可以优化多用户并发访问性能。 - 压缩:启用压缩选项可以减小存储...
- **自主内存存储处理**:Memcached自行管理内存空间,采用了一种称为Slab Allocation的内存分配策略,有效避免了内存碎片问题。 - **基于客户端的Memcached分布式**:客户端负责构建分布式环境中的数据分布逻辑,...