? ? ? ? ?如果有看過之前我分析的ziplist壓縮列表的分析的話，理解這個我覺得不是什么特別的難題。ziplist壓縮列表和zipmap都采用了動態分配字節的做法表示長度，比如通過固定的字節表示節省了不少的空間。同樣帶來的問題就是復雜的指針移動，和字符位置移動。但總的來說，一定是利大于弊了，要不然設計者也不會這么做。ziplist保存的使用一個列表，zipmap就保存的則是一個個鍵值對，通過key:value key:value的形式連著。下面我給出zipmap的結構構成，zipmap其實也就是一個超級長的字符串。
~~~
<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
~~~
里面涉及了幾個變量zmlen，len,free，下面給出完整的解釋：
~~~
/* 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.
*
* zipmap壓縮表和ziplist十分類似，都做到了內存操作效率比較高的
* --------------------------------------------------------------------------
*
* Copyright (c) 2009-2010, Salvatore Sanfilippo <antirez at gmail dot com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Redis nor the names of its contributors may be used
* to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
/* Memory layout of a zipmap, for the map "foo" => "bar", "hello" => "world":
*
* <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
*
* <zmlen> is 1 byte length that holds the current size of the zipmap.
* When the zipmap length is greater than or equal to 254, this value
* is not used and the zipmap needs to be traversed to find out the length.
* <zmeln>占有著1個字節，所以他的最多可代表的數量是254,當zipmap中的元素記錄超過這個數時，
* 那只能從前往后后遍歷算大小了，和ziplist是不一樣的。
*
* <len> is the length of the following string (key or value).
* <len> lengths are encoded in a single value or in a 5 bytes value.
* If the first byte value (as an unsigned 8 bit value) is between 0 and
* 252, it's a single-byte length. If it is 253 then a four bytes unsigned
* integer follows (in the host byte ordering). A value of 255 is used to
* signal the end of the hash. The special value 254 is used to mark
* empty space that can be used to add new key/value pairs.
* <len>代表了后面字符串key 或 value的值的長度，長度一般被編碼1個字節或5個字節表示，這個和ziplist類似
* 如果后面的字符串長度小于等于252個，可與用單字節表示，其他253,254等長度被用來表示其他作用了，當超過這個數時候
* 則直接按5字節的方式存儲長度。
*
* <free> is the number of free unused bytes after the string, resulting
* from modification of values associated to a key. For instance if "foo"
* is set to "bar", and later "foo" will be set to "hi", it will have a
* free byte to use if the value will enlarge again later, or even in
* order to add a key/value pair if it fits.
* <free>一般來表示后面的value長度的空閑值，當key：value=“foo”:"bar",后來被改為“foo”:"hi"，空閑長度就為1了
*
* <free> is always an unsigned 8 bit number, because if after an
* update operation there are more than a few free bytes, the zipmap will be
* reallocated to make sure it is as small as possible.
* <free>的數字一般比較小，如果空閑太大，zipmap會進行調整大小使map整體變得盡可能小
*
* The most compact representation of the above two elements hash is actually:
* 這是一個例子：
* <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
* <總鍵值對數><第一個key的長度>key字符<第一個value的長度><空閑長度開始都為0>后面同前
* "\x02\x03foo\x03\x00bar\x05hello\x05\x00world\xff"
*
* Note that because keys and values are prefixed length "objects",
* the lookup will take O(N) where N is the number of elements
* in the zipmap and *not* the number of bytes needed to represent the zipmap.
* This lowers the constant times considerably.
*/
~~~
說到鍵值對，里面最最重要的方法當然是根據key ，setValue的方法了，方法如下：
~~~
/* Set key to value, creating the key if it does not already exist.
* If 'update' is not NULL, *update is set to 1 if the key was
* already preset, otherwise to 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;
//尋找key的位置
p = zipmapLookupRaw(zm,key,klen,&zmlen);
if (p == NULL) {
/* Key not found: enlarge */
//key的位置沒有找到，調整zipmap的大小，準備添加操作
zm = zipmapResize(zm, zmlen+reqlen);
p = zm+zmlen-1;
zmlen = zmlen+reqlen;
/* Increase zipmap length (this is an insert) */
//如果頭字節還沒有達到最大值，則遞增
if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;
} else {
/* Key found. Is there enough space for the new value? */
/* Compute the total length: */
if (update) *update = 1;
//key的位置以及找到，判斷是否有空間插入新的值
freelen = zipmapRawEntryLength(p);
if (freelen < reqlen) {
/* Store the offset of this key within the current zipmap, so
* it can be resized. Then, move the tail backwards so this
* pair fits at the current position. */
//如果沒有空間插入新的值，則調整大小
offset = p-zm;
zm = zipmapResize(zm, zmlen-freelen+reqlen);
p = zm+offset;
/* The +1 in the number of bytes to be moved is caused by the
* end-of-zipmap byte. Note: the *original* zmlen is used. */
//移動空間以便增加新的值
memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));
zmlen = zmlen-freelen+reqlen;
freelen = reqlen;
}
}
/* We now have a suitable block where the key/value entry can
* be written. If there is too much free space, move the tail
* of the zipmap a few bytes to the front and shrink the zipmap,
* as we want zipmaps to be very space efficient. */
empty = freelen-reqlen;
if (empty >= ZIPMAP_VALUE_MAX_FREE) {
/* First, move the tail <empty> bytes to the front, then resize
* the zipmap to be <empty> bytes smaller. */
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;
}
/* Just write the key + value and we are done. */
/* Key: */
//定位到插入的位置，首先寫入key值
p += zipmapEncodeLength(p,klen);
memcpy(p,key,klen);
p += klen;
/* Value: */
//key值后面是value值，再次寫入
p += zipmapEncodeLength(p,vlen);
*p++ = vempty;
memcpy(p,val,vlen);
return zm;
}
~~~
map里返回長度的方法有點特別，就直接定位了就用一個字節存儲長度：
~~~
/* Return the number of entries inside a zipmap */
/* 返回map的長度 */
unsigned int zipmapLen(unsigned char *zm) {
unsigned int len = 0;
//如果第一個長度小于最大值，則直接返回
if (zm[0] < ZIPMAP_BIGLEN) {
len = zm[0];
} else {
//否則變量計算長度
unsigned char *p = zipmapRewind(zm);
while((p = zipmapNext(p,NULL,NULL,NULL,NULL)) != NULL) len++;
/* Re-store length if small enough */
if (len < ZIPMAP_BIGLEN) zm[0] = len;
}
return len;
}
~~~
平常我們在redis客戶端執行set key "value"命令的時候，調用的其實就是set方法，如下：
~~~
zm = zipmapSet(zm,(unsigned char*) "name",4, (unsigned char*) "foo",3,NULL);
zm = zipmapSet(zm,(unsigned char*) "surname",7, (unsigned char*) "foo",3,NULL);
zm = zipmapSet(zm,(unsigned char*) "age",3, (unsigned char*) "foo",3,NULL);
~~~
比ziplist方法簡單許多了，最后給出頭文件
~~~
/* String -> String Map data structure optimized for size.
*
* See zipmap.c for more info.
*
* --------------------------------------------------------------------------
*
* Copyright (c) 2009-2010, Salvatore Sanfilippo <antirez at gmail dot com>
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* * Neither the name of Redis nor the names of its contributors may be used
* to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef _ZIPMAP_H
#define _ZIPMAP_H
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); //將在zipmapNext中被調用到
unsigned char *zipmapNext(unsigned char *zm, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen); //取得此鍵值對的下一個鍵值對
int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen); //獲取某個鍵值對
int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen); //某個key值在zipmap中是否存在
unsigned int zipmapLen(unsigned char *zm); //zipmap壓縮圖的總鍵值對數
size_t zipmapBlobLen(unsigned char *zm); //壓縮圖的序列化到文件中所需大小
void zipmapRepr(unsigned char *p); //輸出的壓縮圖的具體信息，用于測試
#endif
~~~
最后，基于本人對redis源代碼分析有一段時間了，我把分析好的代碼，同步到了我的個人github上了，放上地址大家可以一起學習：
**github：https://github.com/linyiqun/Redis-Code**
- 前言
- （一）--Redis結構解析
- （二）--結構體分析(1)
- （三）---dict哈希結構
- （四）-- sds字符串
- （五）--- sparkline微線圖
- （六）--- ziplist壓縮列表
- （七）--- zipmap壓縮圖
- （八）--- t_hash哈希轉換
- （九）--- t_list，t_string的分析
- （十）--- testhelp.h小型測試框架和redis-check-aof.c日志檢測
- （十一）--- memtest內存檢測
- （十二）--- redis-check-dump本地數據庫檢測
- （十三）--- redis-benchmark性能測試
- （十四）--- rdb.c本地數據庫操作
- （十五）--- aof-append only file解析
- （十六）--- config配置文件
- （十七）--- multi事務操作
- （十八）--- db.c內存數據庫操作
- （十九）--- replication主從數據復制的實現
- （二十）--- ae事件驅動
- （二十一）--- anet網絡通信的封裝
- （二十二）--- networking網絡協議傳輸
- （二十三）--- CRC循環冗余算法和RAND隨機數算法
- （二十四）--- tool工具類（2）
- （二十五）--- zmalloc內存分配實現
- （二十六）--- slowLog和hyperloglog
- （二十七）--- rio系統I/O的封裝
- （二十八）--- object創建和釋放redisObject對象
- （二十九）--- bio后臺I/O服務的實現
- （三十）--- pubsub發布訂閱模式
- （三十一）--- latency延遲分析處理
- （三十二）--- redis-cli.c客戶端命令行接口的實現(1)
- （三十三）--- redis-cli.c客戶端命令行接口的實現(2)
- （三十四）--- redis.h服務端的實現分析（1）
- （三十五）--- redis.c服務端的實現分析（2）
- （三十六）--- Redis中的11大優秀設計