Redis zipmap内存布局分析

　　Redis 被称为 key/value 应用中的瑞士军刀，除了其丰富的数据结构支持，更重要的是高效的内存使用，分析源码可以发现作者使用每一个 byte 都精打细算。在 hashtable 实现中，Redis 引入了 zipmap 数据结构，保证在 hashtable 刚创建以及元素较少时，用更少的内存来存储，同时对查询的效率也不会受太大的影响。下面就以源码和例子结合的方式来分析一下 zipmap 的内存布局。

　　先来看一下 zipmap 提供的和存储相关的3个 API：

　　zipmapNew：创建一个 zipmap 字符串。zipmap 创建时只有2个字节，后面会随着 set 和 delete 操作动态扩展和收缩。

　　zipmapSet： 加入新的 key/value 或者修改 zipmap 中已有 key 对应的 value。

　　zipmapDel：从 zipmap 中删除 key/value。

　　下面给出一段伪代码并分析其内存布局的变化，如下图：

　　     zipmapNew ();                  

　　    zipmapSet (key1,value1);

　　    zipmapSet (key2,value2); 

　　    zipmapSet (key1,value3);

　　    zipmapDel (key2);            

　　    zipmapSet (key1,value4);

　　1. zipmapNew ();

　　创建一个 zipmap 结构体，包含两个字节，第一个字节(zmlen)是长度为1个字节的无符号整数，用来保存 zipmap 当前元素个数（而非字符串长度）。当 zipmap 的元素个数大于等于254时，zmlen 将不再起作用，zipmap 需要遍历整个字符串来获取当前元素个数。最后一个字节为255，表示 zipmap 的结束。

　　2. zipmapSet (key1, value1)

　　一个元素（key/value）在 zipmap 中有5部分组成: <len><key><len><free><value>。

　　<len>表示紧跟其后的 string（key 或者 value）的长度。如果 string 的长度小于254（这里代码和注释不统一，注释是253，但代码是254，以代码为准），<len>用一个字节就可以表示（254和255有 特殊含义），如果 string 的长度大于等于254，<len>需要5个字节来表示，第一个字节设置为254，紧跟其后的4个字节通过编码（按主机字节序）来表 示<len>的值。zipmapEncodeLength 和 zipmapDecodeLength 就是用来对<len>进行编解码的。<key>和<value>是 char 型 string，<free>在第6步进行说明。

　　3. zipmapSet (key2, value2)

　　调用 zipmapSet 加入新的 key/value 时，zipmap 将根据 key2/value2的长度调用 zipmapResize 扩展空间，并将 key2/value2插入到新分配的空间。同时将 zipmap 元素的个数加1（如果<zmlen>小于254）。

　　4. zipmapSet (key1,value3) 

　　调用 zipmapSet 对已有的 key 修改其 value，且新的 value 值大于现有 value 占用的空间时（加 free 的空间），zipmap 将再次调用 zipmapResize 扩展空间，并调用 memmove 将 key1/vaule1之后的字符串向后顺移。这里只调用一次 memmove，不会对性能有太大影响。

　　5. zipmapDel (key2)

　　调用 zipmapDel 删除 key2/value2时，zipmap 将把 key2/value2之后的字符串前移，并调用 zipmapResize 收缩占用的内存空间。同时将 zipmap 元素个数减1。

　　6. zipmapSet (key1, value4) 

　　调用 zipmapSet 对已有的 key1 修改其 value，且新的 value 值小于现有 value 占用的空间时，zipmap 不会马上去调用 zipmapResize 做内存空间收缩，而是将空闲字节数存入 free 中，用于后面对这个 key 再次修改 value 时，避免调用 zipmapResize（要根据新 value 的长度而定）。当然 free 的空间也不能太多，否则会造出空间的浪费。zipmap 在 free 字节数大于等于 ZIPMAP_VALUE_MAX_FREE（代码中定义为4）时，就对 free 的空间进行收缩。

　　以上就是 zipmap 内存布局和扩展收缩的过程，你可能会问 zipmapGet 岂不是O(n)的吗？没错，但因为 key 和 value 都是确定长度的字符串，所以这个n是 zipmap 中元素的个数，而不是 zipmap 整个串的长度。只要在使用 zipmap 时保证元素个数不是很多，就可以在时间复杂度和空间复杂度两方面找到很好的平衡点。redis.conf 中默认配置 hash-max-zipmap-entries 为512。

来自: rdc.taobao.com