Redis源码剖析之zipmap

浅浅的花香味﹌ 2022-05-17 12:53 186阅读 0赞

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

### 文章目录 ###

*   *  zipmap
     *  数据结构
     *  API

## 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;
    }

[Link 1]: https://github.com/antirez/redis/releases