Memcached Optimization

项目新功能上线后频繁发现缓存丢失,怀疑是数据还没过期就被LRU置换了,但Memcached设置了8G内存对目前的流量来说不应该出现内存不足的情况。以前觉得Memcached比较简单配好参数用就可以了,但借这次机会研究了一下它的细节后发现有坑,有大坑……下面说两个。

Basic Concept: Slab/Chunk/Page

在讲坑前需要先厘清几个重要的概念,在Memcached中数据是以Chunk为单位存储的,每一条数据就是一个Chunk,但由于写入的数据大小是不固定的,因此若是Chunk的大小简单等于数据大小的话会造成系统严重的碎片化从而降低性能,因此在Memcached的设计中Chunk的大小是一系列的固定值,数据会以其最合适的Chunk写入,Slab就是某个大小Chunk的集合。又因为Memcached中内存是以Page为单位管理的,因此Slab实际上关联着许多个Page,Chunk写入到对应Slab下的Page中。有一个经常提及的问题是Memcached中每条数据的最大长度,这个值实际上就是Page的大小(准确说必须减掉Key和Flag的长度),一个Chunk只能存储在一个Page中,但是一个Page可以存储多个Chunk。新一点的版本中可以通过-I参数设置Page的大小,范围是1K到128M。Slab的类型(Chunk的大小)由参数增长系数-f和初始大小-n控制,Memcached启动时会根据这两个值计算出所有的Slab,简单说就是循环计算slab_size * factor直到达到Page大小,其中还需要考虑8-bytes的对齐,参考源码:

while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {
    /* Make sure items are always n-byte aligned */
    if (size % CHUNK_ALIGN_BYTES)
        size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);

    slabclass[i].size = size;
    slabclass[i].perslab = settings.item_size_max / slabclass[i].size;
    size *= factor;
    if (settings.verbose > 1) {
        fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                i, slabclass[i].size, slabclass[i].perslab);
    }
}

增长系数的默认值是1.25,初始大小为48 bytes,Page大小为1M也就是1048576 bytes,默认情况下我们可以得到96, 120, 152, ... , 771184, 1048576一共42个Slab。这里值得注意的是第一个Slab大小不是48而是96,这是因为Memcached除了存储数据外还需要封装对应的描述结构item,而item的大小为48。

了解这些基本概念后就可以来看看Memcached的坑了,为了方便读取Memcached的状态这里提供一个telnet的封装:

class MemcachedStats:
    """Dump memcached stats data"""
    _stats_regex = re.compile(ur"STAT (\w+) (.*)\r")
    _items_regex = re.compile(ur'STAT items:(.*):(.*) (\d+)\r')
    _slabs_regex = re.compile(ur'STAT (\d+):(.*) (\d+)\r')

    def __init__(self, host='localhost', port='11211'):
        self._client = telnetlib.Telnet(host, port)

    def _cast(self, val):
        try:
            return int(val)
        except ValueError:
            return val

    def _command(self, cmd):
        self._client.write('%s\n' % cmd)
        return self._client.read_until('END')

    @property
    def settings(self):
        raw = zip(*self._stats_regex.findall(self._command('stats settings')))
        return dict(zip(raw[0], map(self._cast, raw[1])))

    @property
    def items(self):
        data = defaultdict(dict)
        for id, key, val in self._items_regex.findall(self._command('stats items')):
            data[id][key] = self._cast(val)
        return dict(data)

    @property
    def slabs(self):
        msg = self._command('stats slabs')
        data = { 'slabs': defaultdict(dict) }
        for key, val in self._stats_regex.findall(msg):
            data[key] = self._cast(val)
        for id, key, val in self._slabs_regex.findall(msg):
            data['slabs'][id][key] = self._cast(val)
        data['slabs'] = dict(data['slabs'])
        return data

    @property
    def sizes(self):
        raw = zip(*self._stats_regex.findall(self._command('stats sizes')))
        return dict(zip(raw[0], map(self._cast, raw[1])))

    @property
    def info(self):
        raw = zip(*self._stats_regex.findall(self._command('stats')))
        return dict(zip(raw[0], map(self._cast, raw[1])))

另外下面的演示还用到了一些辅助的函数:

_random = random.SystemRandom()
def random_string(length=12, chars='abcdefghijklmnopqrstuvwxyz'
        'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'):
    return ''.join([_random.choice(chars) for i in range(length)])


def populate(client, n, key_len=16, data_len=128, expire=0):
    """填充数据"""
    bar = random_string(data_len)
    for i in xrange(n):
        client.set(random_string(key_len), bar, time=expire)


def calculate_size(key_size, data_size):
    """计算每条写入数据在Memcached中实际占用的空间"""
    size = sum((
            48,                     # Size of item structure in memcached
            key_size + 1,           # Key size
            min(40, len(' %d %d\r\n' % (0, data_size))),        # Suffix defined in memcached. Assume flags is 0
            data_size + 2,          # Data size with addition CRLF terminator
            8,                      # Use CAS. Size of uint64_t
        ))
    return size

Wasted Memory

上面提到了在Memcached中数据是以Chunk的形式写入到Page中的,一个Page中存储了多个Chunk,那么这就带来了我们的第一个问题,也就是内存利用率的问题。为方便说明,我们假设Page大小为100 bytes,Chunk大小为30 bytes,写入数据大小为25 bytes,按照Memcached的工作原理,我们在写入数据时以30 bytes的Chunk存储到Page中,若当前Page空间不足则会申请新的Page。很容易发现每写入一条数据就有5 bytes的空间被浪费了,另外由于一个Page只能容纳3个Chunk,但3个Chunk只使用了这个Page中的90 bytes空间,还有10 bytes由于无法用于别的用途于是被白白浪费了。在实际运行中由于有多个Slab,每个Slab都会出现不同的内存浪费情况。以实际测试说明:

def test_storage(client, settings, stats):
    Test = namedtuple('Test', 'item_num, key_len, data_len')
    tests = [
        Test(3000, 8, 8),                # 8B
        Test(1000, 8, 128),              # 128B
        Test(500, 16, 1024),             # 1K
        Test(20, 32, 1024 * 256),       # 256K
    ]

    output_tpl = """>>>> Test #%(index)d
    Item Number:        %(item_num)d
    Key Size:           %(key_size)d
    Data Size:          %(data_size)d
    Item Size:          %(item_size)d
    Total Memory:       %(total_size)d

    Slab Index:         %(slab_index)d
    Chunk Size:         %(chunk_size)d
    Total Pages:        %(total_pages)d
    Total Chunks:       %(total_chunks)d
    Used Chunks:        %(used_chunks)d
    Requested Memory:   %(mem_requested)d
    Used Memory:        %(used_memory)d
    Wasted:             %(wasted_memory)d
"""

    for idx, t in enumerate(tests, 1):
        key_size = t.key_len
        data_size = t.data_len
        item_size = calculate_size(key_size, data_size)
        total_size = item_size * t.item_num

        slab_index = 0
        while (settings['slab_classes'][slab_index] < item_size):
            slab_index += 1
        slab_index += 1         # 1-based

        populate(client, t.item_num, t.key_len, t.data_len)

        slab_stats = stats.slabs['slabs'][str(slab_index)]
        data = {
            'index': idx,
            'item_num': t.item_num,
            'key_size': key_size,
            'data_size': data_size,
            'item_size': item_size,
            'total_size': total_size,
            'slab_index': slab_index,
            'chunk_size': slab_stats['chunk_size'],
            'total_pages': slab_stats['total_pages'],
            'total_chunks': slab_stats['total_chunks'],
            'used_chunks': slab_stats['used_chunks'],
            'mem_requested': slab_stats['mem_requested'],
            'used_memory': slab_stats['chunk_size'] * slab_stats['used_chunks'],
            'wasted_memory': slab_stats['chunk_size'] * slab_stats['used_chunks'] - slab_stats['mem_requested'],
        }

        print output_tpl % data

部分运行的结果:

>>>> Test #1
    Item Number:        3000
    Key Size:           8
    Data Size:          8
    Item Size:          81
    Total Memory:       243000

    Slab Index:         1
    Chunk Size:         96
    Total Pages:        1
    Total Chunks:       10922
    Used Chunks:        3000
    Requested Memory:   243000
    Used Memory:        288000
    Wasted:             45000

>>>> Test #4
    Item Number:        20
    Key Size:           32
    Data Size:          262144
    Item Size:          262246
    Total Memory:       5244920

    Slab Index:         37
    Chunk Size:         315872
    Total Pages:        7
    Total Chunks:       21
    Used Chunks:        20
    Requested Memory:   5244920
    Used Memory:        6317440
    Wasted:             1072520

可以看到对于Test #1来说,我们写入了3000条Key长度为8 bytes数据大小为8 bytes的记录,可以计算出每条记录实际占用的空间为81 bytes(参考上面的计算函数,涉及Memcached内部存储的实现),所有记录一共需要243000 bytes的存储空间。通过查看Memcached的状态我们可以看到这些记录最后都被写入到了Slab 1中,这个Slab的Chunk大小为96 bytes,于是一共有(96 - 81) * 3000 = 45000bytes被浪费了。这个测试只输出了由于数据大小与Chunk大小不一致导致的浪费,实际上由于Page为最小的内存管理单位,那些无法分配成Chunk的Page空间也会造成浪费。参考Test #4的情况,我们可以看到在Slab 37中有7个Page,实际应该占用了1048576 * 7 = 7340032bytes,但Chunk只使用了其中的315872 * 21 = 6633312bytes,有7340032 - 6633312 = 706720bytes被浪费了。

为了减少内存浪费,就需要让缓存数据的大小尽可能与Chunk的大小一致,同时Page的大小尽可能接近Chunk大小的倍数。对于后者,由于Chunk的大小有很多种,因此只能考虑使用最多的那种Chunk与Page的倍数关系。对于前者,由于Chunk大小是由初始大小与增长系数控制的,只要我们把二者设置得很小,那么理论上就能得到粒度很小的一系列Slab,使得不同大小的数据使用更“合身”的Chunk,从而降低内存浪费。但实际真的可以这么做吗?很遗憾答案是否定的,先不说Memcached有POWER_LARGEST也就是最大Slab数(200)的限制,这样做将直接掉进接下来要讲的第二个坑:过期数据占用空间的利用问题

Expired Data Space Usage

由于Memcached缺少可用的持久化方法,因此一般都作为缓存数据库使用,这就意味着里面的数据存在有效时间,有效时间过了数据所占用的内存空间就可以释放出来存储新的数据。简单地设想,若Memcached大小为100M,每秒写入10M数据同时这些数据只有10s的有效时间,那么在第10s写满Memcached后由于第1s写入的数据超时,因此我们可以继续写入而不会导致有效数据丢失。配合上内存不足时的LRU,我们只需要为Memcached设置较为充足的内存大小就应该可以保证正常使用了,但是……要是真的那么简单就不会出现开头提到的数据丢失问题了,问题在Slab的存储方式上。

数据在写入时Memcached会计算其所使用的Slab,若该数据对应的Slab已有的Page中已没有可用空间,则会尝试为该Slab分配新的Page,若无法分配新的Page(达到最大使用内存),则根据LRU删除现有数据为新数据提供空间。问题就出现在这个环节,Memcached中LRU删除数据的操作是限制在Slab的范围内的,也就是说往96 bytes Slab写入数据时,若内存已满,那么LRU移出的数据也一定是96 bytes Slab的。考虑这么一种情况:Memcached的大小为10M,写入了单条记录大小为8 bytes有效期为10s的数据共3M,同时写入大小为1024 bytes永远有效的数据7M,于是10s后尝试继续写入1024 bytes大小数据时,尽管Memcached中有3M数据已经过期失效了,但在这次写入中那些空间将无法被利用从而导致已有数据被LRU置换出去。参考下面的测试:

def test_expire(client, settings, stats):
    def print_condition(item_size, n):
        print '    Item size: %d' % item_size
        print '    Item number: %d' % n
        print '    Total size: %d' % (item_size * n)

    def print_stats(slabs):
        for slab_index in slabs:
            slab_stats = stats.slabs['slabs'][str(slab_index)]
            item_stats = stats.items[str(slab_index)]
            print '    Slab #%d' % slab_index
            print '      Requested memory: %d' % slab_stats['mem_requested']
            print '      Used memory: %d' % (slab_stats['chunk_size'] * slab_stats['total_chunks'])
            print '      Evicted: %d' % item_stats['evicted']

    print '>>>> 1st Population - Use 2/3 Memory and expire in 10s'
    key_len, data_len, expire = 32, 1024, 10
    item_size = calculate_size(key_len, data_len)
    n = int(settings['max_memory'] * 1024 * 1024 / 2 / item_size)
    print_condition(item_size, n)

    populate(client, n, key_len, data_len, expire)
    print_stats([12])       # I just know it's slab 12...

    sys.stdout.write('\nSleep 12s waiting data expired...')
    sys.stdout.flush()
    for i in xrange(12):
        time.sleep(1)
        sys.stdout.write('.')
        sys.stdout.flush()
    sys.stdout.write('\n\n')

    print '>>>> 2nd Population - Use 2/3 Memory with a different slab size'
    key_len, data_len, expire = 32, 256, 0
    item_size = calculate_size(key_len, data_len)
    n = int(settings['max_memory'] * 1024 * 1024 / 2 / item_size)
    print_condition(item_size, n)

    populate(client, n, key_len, data_len, expire)
    print_stats([7, 12])

    sys.stdout.write('\n')

    print '>>>> 3rd Population - Use 2/3 Memory. Same size of 1st Population and never expire'
    key_len, data_len, expire = 32, 1024, 0
    item_size = calculate_size(key_len, data_len)
    n = int(settings['max_memory'] * 1024 * 1024 / 2 / item_size)
    print_condition(item_size, n)

    populate(client, n, key_len, data_len, expire)
    print_stats([7, 12])

    sys.stdout.write('\n')

    print '>>>> 4th Population - Use 2/3 Memory. Same as 3rd Population'
    key_len, data_len, expire = 32, 1024, 0
    item_size = calculate_size(key_len, data_len)
    n = int(settings['max_memory'] * 1024 * 1024 / 2 / item_size)
    print_condition(item_size, n)

    populate(client, n, key_len, data_len, expire)
    print_stats([7, 12])

该测试模拟多次写入不同大小的数据,输出结果:

>>>> 1st Population - Use 2/3 Memory and expire in 10s
    Item size: 1124
    Item number: 9950
    Total size: 11183800
    Slab #12
      Requested memory: 11183800
      Used memory: 11780800
      Evicted: 0

Sleep 12s waiting data expired...............

>>>> 2nd Population - Use 2/3 Memory with a different slab size
    Item size: 355
    Item number: 31506
    Total size: 11184630
    Slab #7
      Requested memory: 3876600
      Used memory: 4193280
      Evicted: 20586
    Slab #12
      Requested memory: 11183800
      Used memory: 11780800
      Evicted: 0

>>>> 3rd Population - Use 2/3 Memory. Same size of 1st Population and never expire
    Item size: 1124
    Item number: 9950
    Total size: 11183800
    Slab #7
      Requested memory: 3876600
      Used memory: 4193280
      Evicted: 20586
    Slab #12
      Requested memory: 11183800
      Used memory: 11780800
      Evicted: 0

>>>> 4th Population - Use 2/3 Memory. Same as 3rd Population
    Item size: 1124
    Item number: 9950
    Total size: 11183800
    Slab #7
      Requested memory: 3876600
      Used memory: 4193280
      Evicted: 20586
    Slab #12
      Requested memory: 11936880
      Used memory: 12574080
      Evicted: 9280

可以看到在第二次写入中尽管第一次写入的数据已经失效,Memcached还是无法利用失效数据所占用的内存空间,从而导致了Evicted: 20586条数据丢失。在第三次写入中,由于写入的数据大小与第一次写入一致,因此能够正常利用释放的内存空间,Slab 12中没有发生数据丢失Evicted: 0。这个问题貌似没有什么好的解决办法,不过还好实际使用中只要Slab的粒度不要过细,数据大小还是比较平均不会出现明显的波峰波谷(我的情况是因为线上Memcached跑了很久而中间代码有过几次重构导致写入缓存数据大小的变化),只要加强监控应该不会造成很严重的问题。

总结一句话,路漫漫其修远兮,没碰到坑只能说明走过的路太少。上面测试的代码可在Gist上查看。

Updated

Updated: Memcached中有一个实验的设置参数-o slab_reassign,在开启时Slab会以Page的大小分配内存,这样所得到的Page就可以被别的Slab复用;当参数关闭时Slab是以chunk_size * chunks_per_page为Page的大小,这样的好处是不会造成Page空间的浪费,但Slab跟Page就完全绑定了。另外有一个参数slab_automove可以让Memcached启动一个维护线程自动调整各个Slab间的Page分配,但看上去好像现在有Bug:

 memset(slab_rebal.slab_start, 0, (size_t)settings.item_size_max);

因为slab_automove是可以在服务运行中开关的,而且就算slab_reassign关闭了也可以通过命令进行slabs reassign s d操作,那么在这里直接使用settings.item_size_max应该是会问题的,这两个实验性的功能还是要慎重使用。