PDF版 ePub版

# Redis 数据结构 ziplist

## 压缩双链表的具体实现

ziplist 的格式可以表示为：

<zlbytes><zltail><zllen><entry>...<entry><zlend>

zlbytes 是 ziplist 占用的空间；zltail 是最后一个数据项的偏移位置，这方便逆向遍历链 表，也是双链表的特性；zllen 是数据项entry 的个数；zlend 就是 255，占 1B。

|<prelen><<encoding+lensize><len>><data>|
|---1----------------2--------------3---|

3 种长度的字符串：

#define ZIP_STR_06B (0 << 6)
#define ZIP_STR_14B (1 << 6)
#define ZIP_STR_32B (2 << 6)

5 种长度的整数：

#define ZIP_INT_16B (0xc0 | 0<<4)
#define ZIP_INT_32B (0xc0 | 1<<4)
#define ZIP_INT_64B (0xc0 | 2<<4)
#define ZIP_INT_24B (0xc0 | 3<<4)
#define ZIP_INT_8B 0xfe

// 在ziplist 中查找数据项
/* Find pointer to the entry equal to the specified entry. Skip 'skip' entries
* between every comparison. Returns NULL when the field could not be found. */
unsigned char *ziplistFind(unsigned char *p, unsigned char *vstr,
unsigned int vlen, unsigned int skip) {
int skipcnt = 0;
unsigned char vencoding = 0;
long long vll = 0;

while (p[0] != ZIP_END) {
unsigned int prevlensize, encoding, lensize, len;
unsigned char *q;
ZIP_DECODE_PREVLENSIZE(p, prevlensize);

// 跳过前驱数据项大小，解析数据项大小
// len 为data 大小
// lensize 为len 所占内存大小
ZIP_DECODE_LENGTH(p + prevlensize, encoding, lensize, len);
// q 指向data
q = p + prevlensize + lensize;
if (skipcnt == 0) {
/* Compare current entry with specified entry */
if (ZIP_IS_STR(encoding)) {
// 字符串比较
if (len == vlen && memcmp(q, vstr, vlen) == 0) {
return p;
}
} else {
// 整数比较
/* Find out if the searched field can be encoded. Note that
* we do it only the first time, once done vencoding is set
* to non-zero and vll is set to the integer value. */
if (vencoding == 0) {
// 尝试将vstr 解析为整数
if (!zipTryEncoding(vstr, vlen, &vll, &vencoding)) {
/* If the entry can't be encoded we set it to
* UCHAR_MAX so that we don't retry again the next
* time. */
// 不能编码为数字！！！会导致当前查找的数据项被跳过
vencoding = UCHAR_MAX;
}
/* Must be non-zero by now */
assert(vencoding);
}
/* Compare current entry with specified entry, do it only
* if vencoding != UCHAR_MAX because if there is no encoding
* possible for the field it can't be a valid integer. */
if (vencoding != UCHAR_MAX) {
// 读取整数
long long ll = zipLoadInteger(q, encoding);
if (ll == vll) {
return p;
}
}
}
/* Reset skip count */
skipcnt = skip;
} else {
/* Skip entry */
skipcnt--;
}
// 移动到ziplist 的下一个数据项
/* Move to next entry */
p = q + len;
}
// 没有找到
return NULL;
}

## 为什么要用 ziplist

redis HSET 命令官网的描述是： Sets field in the hash stored at key to value. If key does not exist, a new key holding a hash is created. If field already exists in the hash, it is overwritten.