`
javafan_303
  • 浏览: 957106 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Memcached slab 分配策略

 
阅读更多

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机制

    ### Memcached内存分配与SLAB机制 #### 第1章 前言 本文将深入探讨Memcached中的内存分配原理及SLAB机制的核心概念。通过详细分析Memcached如何管理内存资源,帮助读者理解其高效内存利用背后的逻辑。 #### 第2章...

    Memcached内存分配与SLAB机制[借鉴].pdf

    SLAB机制是Memcached为了高效管理内存而设计的一种内存分配策略。传统的内存分配方式在处理小块内存时效率低下,容易产生内存碎片。SLAB机制则解决了这个问题,它将内存划分为一系列的分页(chunk),每个分页又分为...

    memcached_allocator_slab_langwan

    ### Memcached Slab 分配器及其 LRU 机制详解 #### 第一章 前言 本文档将详细介绍 memcached 的内存管理机制,特别是 slab 分配器和 LRU(Least Recently Used)置换算法的工作原理。这些机制对于 memcached 的...

    memcached的内存分配代码

    memcached采用了一种特殊的内存分配策略,名为Slab Allocation,以避免频繁的内存碎片和提高内存利用率。 1. Slab Allocation原理: Slab Allocation的核心思想是将内存分为多个大小不等的chunk(块),每个chunk...

    网上收集最新的Memcached学习资料

    调整 slab 分配策略,避免内存浪费;监控和调整超时时间,确保高并发下系统的响应速度。 七、Memcached与Linux的关系 在Linux环境下,Memcached可以充分利用操作系统的内存管理机制,如页缓存,进一步提高性能。...

    memcached源代码分析

    1. **slab类分配器**:memcached使用slab分配器来管理内存,避免了内存碎片。slab被划分为多个大小不同的chunk,每个chunk用于存储特定大小的数据。每个 slab 分区由一系列连续的内存块(slabs)组成,每个slab内的...

    memcached-1.5.4

    - `memcached`采用slab分配机制来管理内存,将内存划分为不同大小的chunk,每个chunk对应一个slab类,避免了内存碎片。 6. **libevent事件驱动** - `memcached`利用libevent库实现非阻塞I/O,能够高效处理大量...

    memcached-1.5.11.tar.gz

    1. 内存管理:Memcached采用slab分配机制管理内存,将内存分为多个 slab 分区,每个分区内部又细分为多个chunk,以减少内存碎片。 2. 数据存储:键值对存储,键必须是字符串,值可以是任意类型(转换为二进制)。每...

    Memcached 内存分析、调优、集群

    Memcached采用slab分配器来管理内存,每个slab class包含一组相同大小的pages。当请求一个对象时,Memcached会查找合适的slab class来存放该对象。如果找不到,则创建一个新的slab class,并分配相应的pages。 - **...

    memcached1.4.31

    当数据量超过单个服务器的内存限制时,可以将Memcached 部署在多台服务器上,通过一致性哈希策略将数据均匀分配到各个节点,从而实现数据的分布式存储和访问。 ### 3. 性能优化 - **内存管理**:Memcached 使用...

    memcached全面剖析.pdf

    - mixi的memcached部署通常涉及到多个实例,通过客户端的智能路由策略实现数据分布。 - **TokyoTyrant案例**: - TokyoTyrant是一款由mixi工程师开发的兼容memcached协议的键值存储系统,具有更高的性能和稳定性。 ...

    Memcached-1.49 源代码

    2. **内存管理**:Memcached使用slab分配器管理内存,避免了内存碎片问题。slab将内存分为多个大小固定的chunk,每个chunk用于存储特定大小的数据,提高了内存利用率。 3. **一致性哈希**:在分布式环境中,...

    Memcached相关程序

    - 理解Memcached的 slab 分配机制,有效管理内存使用。 - 探索如何调整缓存大小、超时设置以适应不同应用场景。 6. **分布式缓存概念**: - Memcached可以部署在多台服务器上,形成分布式缓存集群。 - 了解一致...

    memcached-1.4.5 windows版

    1. **内存管理**:Memcached使用 slab 分配器来管理内存,避免了小块内存的碎片问题。 2. **一致性哈希**:分布式环境下的数据分布策略,确保数据迁移时尽可能少地影响缓存命中率。 3. **超时设置**:根据应用需求,...

    memcached源码

    - **Slab分配器**:Memcached采用slab分配器来管理内存,将内存划分为多个大小固定的chunk,每个chunk用于存储特定大小的数据,避免了内存碎片问题。 - **LRU策略**:当内存满时,使用最近最少使用(LRU)算法来...

    memcached-1.5.14.tar.gz

    - slab分配器:Memcached使用slab分配器管理内存,将内存预先分配为不同大小的chunk,减少内存碎片。 - 并发处理:通过调整并发连接数和线程池大小,可以优化多用户并发访问性能。 - 压缩:启用压缩选项可以减小存储...

    memcached学习总结

    - **自主内存存储处理**:Memcached自行管理内存空间,采用了一种称为Slab Allocation的内存分配策略,有效避免了内存碎片问题。 - **基于客户端的Memcached分布式**:客户端负责构建分布式环境中的数据分布逻辑,...

Global site tag (gtag.js) - Google Analytics