redis zipmap剖析

发表于 更新于 阅读次数：

说明

本篇文章介绍redis的zipmap结构。zipmap是一个以节约内存为前提的键值对存储结构，这个结构只在内存上有优势，在查找/插入/删除/更新上跟hash表或者红黑树实现的map没有任何优势。所以只适用于元素数量比较少的情况。但实际上redis自己内部并没有使用该结构，而是使用ziplist在元素比较少的场合来替代dict。

实现

zipmap实际上是一个char数组，使用约定好的格式来存放这些key-value。（后面可以看到ziplist也是类似这种实现方式）
下面是一个zipmap的内存格式，该zipmap存放”foo” => “bar”, “hello” => “world”两个键值对：
<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"<ZIPMAP_END>

  • zmlen：1 byte：存放zipmap拥有的key-value对数量，最大为253，如果zmlen>=254，则表示该值无效，需要遍历整个zipmap才能拿到元素数量
  • len：1/5 byte：存放后面key/value的长度，第一个byte值<254则该byte就是接下去的长度，如果=254则接下去4 byte组成的unsinged int才是长度，如果=255(ZIPMAP_END)，则表示到达zipmap尾部
  • free：1 byte：存放value之后剩余的空间长度，有这个字段的好处就是，value长度改变可以利用剩余的空间来减少内存重复申请的次数，该字段为1 byte，所以剩余空间只能<=255，如果剩余空间大于这个范围，就会强制重新申请整个zipmap的内存

对于上面例子，实际的二进制数值为：
"\x02\x03foo\x03\x00bar\x05hello\x05\x00world\xff"
如果将foo => bar改为 foo => hi，则二进制数值为
"\x02\x03foo\x02\x01hir\x05hello\x05\x00world\xff"
可以看到foo对于的value len更新为2，free更新为1，只是利用更改长度的方式避免了重新申请整个zipmap的内存

主要函数分析

函数 描述 时间复杂度
zipmapNew 创建一个空的zipmap内存，只有两个byte：\x00\xff O(1)
zipmapSet 设置key和value到zipmap中，如果key不存在就会创建一个，否则更新key对应的value O(N), N为元素个数
zipmapDel 从zipmap中删除key O(N), N为元素个数
zipmapRewind 在迭代之前调用一起，类似于其他结构返回一个迭代器指针 O(1)
zipmapNext 返回下一个key，value的entry，key，klen，value，vlen用来返回当前迭代到的key，value值；如果已经到尾部，则返回NULL O(1)
zipmapGet 搜索zipmap中key对应的的value，如果找到返回1，找不到返回0 O(N), N为元素个数
zipmapExists 搜索zipmap中是否存在该key，如果找到返回1，找不到返回0 O(N), N为元素个数
zipmapLen 返回zipmap键值对个数 如果元素个数小于254，则O(1)，否则O(N), N为元素个数
zipmapBlobLen 返回zipmap占用的二进制内存大小 O(N), N为元素个数

每个函数的声明及作用，具体细节可以查看我注释的redis源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
unsigned char *zipmapNew(void);             // 创建一个空的zipmap内存，只有两个byte：\x00\xff

// 设置key和value到zipmap中，如果key不存在就会创建一个，否则更新key对应的value；参数update用于返回是更新操作还是插入操作
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update);

// 从zipmap中删除key；deleted用来返回是否删除元素
unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted);

// 在迭代之前调用一起，类似于其他结构返回一个迭代器指针
unsigned char *zipmapRewind(unsigned char *zm);

// 返回下一个key，value的entry，key，klen，value，vlen用来返回当前迭代到的key，value值；如果已经到尾部，则返回NULL
// 返回的key和value只是简单指向到zipmap内部的内存
unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen);

// 搜索zipmap中key对应的的value，如果找到返回1，找不到返回0
// 返回的value只是简单指向到zipmap内部的内存
int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen);

// 搜索zipmap中是否存在该key，如果找到返回1，找不到返回0
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);

void zipmapRepr(unsigned char *p);      // for test