Redis源码剖析之zipmap

以下涉及到的源码均为redis5.0-rc3版本的代码【点击查看官方源码】

zipmap

1. zipmap是为优化string映射到其他string这种结构而生的，故名思意其能节约内存。
2. zipmap是redis中hash结构的底层涉及之一。当hash存储的元素数量少的情况下，底层使用zipmap结构，一旦元素数量达到一个限定值的时候就会自动切换成哈希表。
3. 由于zipmap的特性，hash结构在存储的数据少的情况下，在内存使用方面又相当大的优势。

数据结构

在源码中例子可见，对于一个map中的值有 “foo” => “bar”, “hello” => “world”，那么其结构如下所示：

<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

其中各部分的含义如下：

• zmlen
  占用一个字节长度，保存zipmap结构的当前长度，但是只针对zipmap的长度小于254时，如果大于等于254，那么仍然需要遍历整理结构才能得知长度值。
• len
  表示后面紧跟着的一个字符串的长度，可以说key的长度，也可以是value的长度。len会被编码为一个单值或者一个5个字节的值，如果第一个字节值在0-253之间，那么len代表一个单值；如果是254，那么接下来的4个字节是一个无符号整型；如果是255，那么它是一个表示hash’结束点的信号。

• free
  代表后面的字符串未使用的字节空间，往往是由于对一个键的值做修改导致。如原键值对映射为foo->bar,后续变为foo->ba，那么就会出现就会出现2哥字节的空闲空间，此时并不会去释放掉，而是供后续使用，如果后续再变为foo->baa，那么就不需要重新分配空间了。 但是free字段始终保持着一个特定字节长度（在zipmap.c文件中定义：“#define ZIPMAP_VALUE_MAX_FREE 4”），如果空闲的字节数多了，zipmap会释放其它的空闲空间来保证zipmap的占用空间尽量的小。

介绍了个字段的含义，那么就可以知道上面的例子的占用内存情况了，如下所示：

"\x02\x03foo\x03\x00bar\x05hello\x05\x00world\xff"

API

zipmap.h头文件中定义了如下api：

//创建zipmap结构
unsigned char *zipmapNew(void);
//添加值
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update);
//删除值
unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted);
//迭代元素之前调用
unsigned char *zipmapRewind(unsigned char *zm);
//用于遍历zipmap，返回下一个节点
unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen);
//get给定key的映射值
int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen);
//判断一个key是否在zipmap中存在
int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen);
//zipmap中节点的个数
unsigned int zipmapLen(unsigned char *zm);
//zipmap占用总字节数
size_t zipmapBlobLen(unsigned char *zm);
//格式化打印zipmap信息
void zipmapRepr(unsigned char *p);

zipmap的源码很简单，也不难理解，下面就只介绍一下zipmapSet函数的源码，其他的有兴趣的可以自行点击本文首部的链接去下载源码查看。

/*如果key不存在，则创建；在update不为NULL的前提下  *，如果key存在则update指针的值为1，否则为0*/
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
    unsigned int zmlen, offset;
    unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
    unsigned int empty, vempty;
    unsigned char *p;

    freelen = reqlen;
    if (update) *update = 0;
    p = zipmapLookupRaw(zm,key,klen,&zmlen);
    if (p == NULL) {
        //key不存在，则分配空间创建key
        zm = zipmapResize(zm, zmlen+reqlen);
        p = zm+zmlen-1;
        zmlen = zmlen+reqlen;

        //增加zipmap的长度
        if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
    } else {
        //key存在，判断是否有足够的空间存储值
        if (update) *update = 1;
        freelen = zipmapRawEntryLength(p);
        if (freelen < reqlen) {
            //空闲空间不足，需要重新分配空间
            offset = p-zm;
            zm = zipmapResize(zm, zmlen-freelen+reqlen);
            p = zm+offset;
            memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
            zmlen = zmlen-freelen+reqlen;
            freelen = reqlen;
        }
    }
    
    empty = freelen-reqlen;
    if (empty >= ZIPMAP_VALUE_MAX_FREE) {
        //如果空闲空间待遇设定的空间空间允许数，则释放部分空间
        offset = p-zm;
        memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
        zmlen -= empty;
        zm = zipmapResize(zm, zmlen);
        p = zm+offset;
        vempty = 0;
    } else {
        vempty = empty;
    }

    //写入值
    p += zipmapEncodeLength(p,klen);
    memcpy(p,key,klen);
    p += klen;
    p += zipmapEncodeLength(p,vlen);
    *p++ = vempty;
    memcpy(p,val,vlen);
    return zm;
}