redis源码阅读之zipmap

个人觉得zipmap之于dict，就相当于ziplist之于adlist。好了，闲话少说，先看注释

/* String -> String Map data structure optimized for size.
 * This file implements a data structure mapping strings to other strings
 * implementing an O(n) lookup data structure designed to be very memory
 * efficient.
 *
 * The Redis Hash type uses this data structure for hashes composed of a small
 * number of elements, to switch to a hash table once a given number of
 * elements is reached.
 *
 * Given that many times Redis Hashes are used to represent objects composed
 * of few fields, this is a very big win in terms of used memory.
 */

注释里面也说的比较清楚了，当在redis当中使用hash的时候，如果元素个数在一个比较小的量级，其内部就会使用zipmap这种结构来存储，如果大过某个阈值就会转而使用dict来存储了。
接下来我们就来看看zipmap在内存中的结构

/* Memory layout of a zipmap, for the map "foo" => "bar", "hello" => "world":
 *
 * <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
 */

其中各个字段的意义如下

综上所述，之前例子当中的foo->bar, hello->world在zipmap当中最紧凑的表示方式如下

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

其中第一个字节表示共有两对key->value，第一对的key占3个字节，为foo，第一对的value占3个字节，其后空余字节为0，其值为bar；第二对的key占5个字节，为hello，第二对的value占5个字节，其后空余字节为0，其值为world；最后255表示zipmap的结尾

具体实现的话就是先定义宏来确定上面的具体规则

#define ZIPMAP_BIGLEN 254
#define ZIPMAP_END 255

/* The following defines the max value for the <free> field described in the
 * comments above, that is, the max number of trailing bytes in a value. */
#define ZIPMAP_VALUE_MAX_FREE 4

/* The following macro returns the number of bytes needed to encode the length
 * for the integer value _l, that is, 1 byte for lengths < ZIPMAP_BIGLEN and
 * 5 bytes for all the other lengths. */
#define ZIPMAP_LEN_BYTES(_l) (((_l) < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int)+1)

之后的底层实现就是使用字符数组了，需要注意的就是取值时的大小端的转换问题，其他的就是字符数组的常规操作

喜欢 (0)赏

[搞代码]

分享 (0)