Redis zipmap
2018-03-05 本文已影响8人
烨哥
简介
Redis zipmap是一个String -> String Map data structure optimized for size。不要被它的名字所迷惑,它实际上没有做压缩操作。是一个连续的key value集合。
它的特点就是维护map需要的额外信息很少。最少可以到达只需要三个字节。不过这样做的后果就是时间复杂度为o(N),需要便利才能操作。所以相对来说在定义上ZIPMAP_BIGLEN 就只有254（不过并非到达254就不给你存了,它还是会存的）.
数据结构
zipmap的数据结构特别简单，简单到两个字节，首字节保存长度，尾字节保存结尾标志ZIPMAP_BIGLEN。ZIPMAP_BIGLEN=254
创建zipmap
unsigned char *zipmapNew(void) {
unsigned char *zm = zmalloc(2);
zm[0] = 0; /* Length */
zm[1] = ZIPMAP_END;
return zm;
}
对就是这么简单。分配两字节的空间设置首字节为长度0，尾字节为结束标识。
数据编码
在说插入之前我们先来看一下，对于一个key->value的数据，zipmap是怎么保存的。
引用源码中的介绍
Memory layout of a zipmap, for the map "foo" => "bar", "hello" => "world":
<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"
- zmlen 这个是我们的首字节保存key value的对数。不过zmlen <=ZIPMAP_BIGLEN大了他就不表示了。
- len 表示保存的字符串的长度。第一个len是key的长度。第二个len是value字符串的长度。len在小于254的时候使用一个字节表示。这个字节就是保存len的长度。当len大于254的时候。这时候使用sizeof(unsigned int)+1来保存。其中第一个字节设置为ZIPMAP_BIGLEN。后四个字节用来实际存储长度。
- free 一个字节，用在修改key对应的value后表示剩余的空间。发生在新的value比原来的value的len长度要小的时候。受到ZIPMAP_VALUE_MAX_FREE的限制。当大于ZIPMAP_VALUE_MAX_FREE的时候触发resize
- keyvalue键值对直接没有对于的数据，直接连接
len的编码
因为我们的len有着两种保存方式。所以先来看下len相关的编码和解码
/*获取保存len需要的长度 当len<ZIPMAP_BIGLEN时为1,len>ZIPMAP_BIGLEN时为sizeof(unsigned int)+1)*/
#define ZIPMAP_LEN_BYTES(_l) (((_l) < ZIPMAP_BIGLEN) ? 1 : sizeof(unsigned int)+1)
/*对len进行编码，当没有传入p时，返回需要的空间大小，当p存在时编码保存len并且返回空间大小*/
static unsigned int zipmapEncodeLength(unsigned char *p, unsigned int len) {
if (p == NULL) {
return ZIPMAP_LEN_BYTES(len);//为空直接返回大小
} else {
if (len < ZIPMAP_BIGLEN) {
p[0] = len;//当len<ZIPMAP_BIGLEN时直接保存
return 1;
} else {
p[0] = ZIPMAP_BIGLEN;//首字节设置为ZIPMAP_BIGLEN作为标记
memcpy(p+1,&len,sizeof(len));
memrev32ifbe(p+1);//对于大端小断的操作
return 1+sizeof(len);
}
}
}
/*解len长度*/
static unsigned int zipmapDecodeLength(unsigned char *p) {
unsigned int len = *p;
if (len < ZIPMAP_BIGLEN) return len;//不是ZIPMAP_BIGLEN标记直接返回长度
memcpy(&len,p+1,sizeof(unsigned int));
memrev32ifbe(&len);//大端小端
return len;
}
key value编码
对于key的编码保存方式的<len>key
对于value的编码是<len><free>value
对于一个key->value的键值对的编码则是<len>key<len><free>value，他们中间没有间隔直接连接起来。
我们获取一个key-value所需要的总长度
static unsigned long zipmapRequiredLength(unsigned int klen, unsigned int vlen) {
unsigned int l;
l = klen+vlen+3;// 3 = klen vlen free(一般是klen vlen一般是1)
if (klen >= ZIPMAP_BIGLEN) l += 4;
if (vlen >= ZIPMAP_BIGLEN) l += 4;
return l;
}
key value的解码
对于key，先获得klen 然后获得保存klen所需要的长度klenlen，再偏移klenlen的长度得到保存的key值
unsigned char * p;//表示保存key的开始
unsigned int klen = zipmapDecodeLength(p);
unsigned int klenlen = zipmapEncodeLength(NULL,klen);
unsigned char* key = p+klenlen;
对于value来说基本和key一致，因为在value实际保存位置前，还有一个一字节的free的空间，所以我们需要多偏移一个字节。
unsigned char * p;//表示保存value的开始
unsigned int vlen = zipmapDecodeLength(p);
unsigned int vlenlen = zipmapEncodeLength(NULL,vlen);
unsigned char* key = p+vlenlen+1;
搜索
我们知道编码和保存方式之后，来看下我们的查找操作
static unsigned char *zipmapLookupRaw(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned int *totlen) {
/*1*/ unsigned char *p = zm+1, *k = NULL;//zm实际保存的数据从第二个字节开始
unsigned int l,llen;
while(*p != ZIPMAP_END) {//没有结束
unsigned char free;
/* Match or skip the key */
/*2*/ l = zipmapDecodeLength(p);//长度打头
llen = zipmapEncodeLength(NULL,l);//返回length的长度
/*3*/ if (key != NULL && k == NULL && l == klen && !memcmp(p+llen,key,l)) {//k为null是才比较不为null代表找到
/* Only return when the user doesn't care
* for the total length of the zipmap. */
if (totlen != NULL) {//返回长度不
k = p;
} else {
return p;//直接返回
}
}
p += llen+l; //偏移数据的长度和保存长度的长度
/* Skip the value as well */
/*4*/l = zipmapDecodeLength(p);//value的长度
p += zipmapEncodeLength(NULL,l);//保持value长度的长度
free = p[0];
p += l+1+free; /* +1 to skip the free byte */
}
if (totlen != NULL) *totlen = (unsigned int)(p-zm)+1;
return k;
}
对于我们的搜索key来说特别简单。
1.我们先对传入的zm进行1的偏移，因为第二个字节才是保存的第一个key的开始。
2.获得key的值
3.对key进行比对，成功代表找到，没成功进入偏移掉key的长度，进入到4
4.偏移一个value的长度,value偏移的时候需要注意不要忘记free保存的空闲长度和free本身的一字节的长度。
最后如果传入了totlen则代表需要获取保存所有数据的长度
插入
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);//获取key value保存需要的总长度
unsigned int empty, vempty;
unsigned char *p;
freelen = reqlen;
if (update) *update = 0;
/*1*/p = zipmapLookupRaw(zm,key,klen,&zmlen);//查找key是否存在并且返回总长度
if (p == NULL) {//代表没有
/* Key not found: enlarge */
/*2*/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;
freelen = zipmapRawEntryLength(p);//获取原来保存key value的总大小
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. */
/*3*/ offset = p-zm;//原来保存key value的偏移
zm = zipmapResize(zm, zmlen-freelen+reqlen);//重新分配空间
p = zm+offset;//偏移到原来保存key value的位置
/* 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 );//内存移动过来
/*
我们需要移动原来的keyvlaue后的所有数据（排除最后一个 在resize中已经设置）到新的keyvalue的结束位置
p = zm +offset 所以这个时候p是保存这个key value开始的位置
reqlen新key value保存需要的总大小 所以p+reqlen 就到达下个key value的起始位置（p+reqlen-1 为新key value的结束位置）
freelen 保存原来key value的总大小p+freelen 同里就达到了原来下一个key value保存的位置
这个时候我们把zm看成一个纯的字符串，来看内存移动
zmlen为字符串的长度，p+reqlen为需要移动到的起始位置，p+freelen为需要移动的起始位置
offset为zm到原来字符串中间数据的长度 freelen 为原来kevalue的长度
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. */
/*4*/offset = p-zm;
memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));//回收内存
/*
内存前移和后移一样的 resize会设置最后一个
*/
zmlen -= empty;//变小
zm = zipmapResize(zm, zmlen);
p = zm+offset;//
vempty = 0;
} else {
vempty = empty;
}
/* Just write the key + value and we are done. */
/* Key: */
/*5*/
p += zipmapEncodeLength(p,klen);//设置并返回
memcpy(p,key,klen);//拷贝key
p += klen;
/* Value: */
p += zipmapEncodeLength(p,vlen);
*p++ = vempty;//设置free
memcpy(p,val,vlen);
return zm;
}
设置一个key value经历了以下步骤
- 首先对key进行搜索操作同时返回zmlen
2.如果没有搜索到，那么直接分配一个keyvalue所需要的空间
3.如果搜索到原来有，那么判断当前需要的空间和原来空间的大小，如果当前空间比原来空间小，那么就需要再次分配一个大的内存空间，然后把p+freelen后的数据移动到p+reqlen，不过需要注意的是在代码中，最末尾的标记是在resize的时候设置了，所以在移动的时候少了一个移动
4.当原来的空间比需要的空间大，并且当freelen-reqlen的时候大于了允许的最大freesize，那么就需要重新分配一个小的空间，也是把p+freelen后的数据移动到p+reqlen，不过需要注意的是在代码中，最末尾的标记是在resize的时候设置了，所以在移动的时候少了一个移动
5.最后把新的keyvalue编码到新的空间。
删除
unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
unsigned int zmlen, freelen;
unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);//找到
if (p) {
freelen = zipmapRawEntryLength(p);//获取这个keyvalue总长度
memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));//回收内存 也注意最后一位
zm = zipmapResize(zm, zmlen-freelen);
/* Decrease zipmap length */
if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;
if (deleted) *deleted = 1;
} else {
if (deleted) *deleted = 0;
}
return zm;
}
删除相对来说就是特别的简单了
如果找到key那么或取这个keyvalue的空间，前移keyvalue后面的数据，更改大小
总结
zipmap的数据结构相对简单。我们只需要理解了keyvalue的编码以后，就能快速的掌握。在插入和删除的时候牵涉到的内存移动，都要注意在源码中没有移动最后一位。因为是在resize中设置了。
使用的地方
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 ofelements is reached.
它使用在当hashtable还特别小的时候。因为hashtable需要编码的额外信息很大 sizeof(struct dictEntry) = 24，咱们的zipmap最少只需要三个。最多11个。
在查询效率上当数据量特别小的时候顺序查询花费的时间成本虽然是o(N)，但是N小，所以是可以接受的。这样可以节约出内存。
我们以后还会看到很多这种节约内存的做法
