redis源码学习之压缩列表

2019-11-14 11:40:05

字体：大中小

来源：转载

供稿：网友

压缩列表

列表键和哈希键的底层实现。是为了节约内存而实现。

压缩列表是一段连续的内存，每个属性都会有固定的编码大小，例如对于字符串来说，我们需要知道字符串的长度，假设小于63字节，那么我们只需要一个字节的大小来表示（2位标识，6位数据）；而存储的结构是整型的数的话，我们只需要1个字节来表示该整型是16/32/64位整型。

压缩列表用一段连续内存表示unsigned char *类型指针来访问，不过它人为的规定了这一段连续内存的数据类型：前4个字节（uint32_t）表示整个ziplist的长度所占用的内存数：zlbytes；再往后4个字节表示表尾节点到压缩列表的字节数：zltail；然后2个字节（uint16_t）表示压缩列表中节点数目：zllen；之后就是数据内容zlentry；最后压缩列表有1个字节的特殊值标记列表末尾：zlend：0xFF

根据上述说明，redis定义了一些宏来获取各个元素的值，主要是进行地址运算，因为header的大小固定：

// 定位到 ziplist 的 bytes 属性，该属性记录了整个 ziplist 所占用的内存字节数// 用于取出 bytes 属性的现有值，或者为 bytes 属性赋予新值#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))// 定位到 ziplist 的 offset 属性，该属性记录了到达表尾节点的偏移量// 用于取出 offset 属性的现有值，或者为 offset 属性赋予新值#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))// 定位到 ziplist 的 length 属性，该属性记录了 ziplist 包含的节点数量// 用于取出 length 属性的现有值，或者为 length 属性赋予新值#define ZIPLIST_LENGTH(zl) (*((uint16_t*)((zl)+sizeof(uint32_t)*2)))// 返回 ziplist 表头的大小#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))// 返回指向 ziplist 第一个节点（的起始位置）的指针#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)// 返回指向 ziplist 最后一个节点（的起始位置）的指针#define ZIPLIST_ENTRY_TAIL(zl) ((zl)+intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl)))// 返回指向 ziplist 末端 ZIP_END （的起始位置）的指针#define ZIPLIST_ENTRY_END(zl) ((zl)+intrev32ifbe(ZIPLIST_BYTES(zl))-1)

对字节长度进行编码，有两个数据类型，一个是字节长度，一个是编码字节长度所需要的长度。

在Redis设计与实现中，给了两个表格，分别是字节数组编码（在源码中又叫字符串），整数编码。

现在给定一个长度len，需要对其进行编码。首先源码中定义了一些宏，分别表示不同字节范围表示的编码。

/* * 字符串编码类型 */#define ZIP_STR_06B (0 << 6)//长度小于等于63字节#define ZIP_STR_14B (1 << 6)//长度小于等于16383字节#define ZIP_STR_32B (2 << 6)//长度小于等于4294967295字节/* * 整数编码类型 */#define ZIP_INT_16B (0xc0 | 0<<4)//1100 0000#define ZIP_INT_32B (0xc0 | 1<<4)//1101 0000#define ZIP_INT_64B (0xc0 | 2<<4)//1110 0000#define ZIP_INT_24B (0xc0 | 3<<4)//1111 0000#define ZIP_INT_8B 0xfe//1111 1110

这种编码方式很好理解，对于长度小于等于63字节编码，编码方式应该是00xxxxxx，除了高位两位的标识位，后六位能表示的数字范围为0~63，这是1个字节的情况。当数据变大时，一个字节显然不能满足条件了，因此就需要加一个字节（8+6 位）的编码长度来表示长度。

如果是整型类型编码就容易多了，不同于字节数组需要记录数据长度，整型数据总是只需要1个字节来表示整型数据类型。

在redis源码src/ziplist.c中用zipEncodeLength函数来描述上述过程。

static unsigned int zipEncodeLength(unsigned char *p, unsigned char encoding, unsigned int rawlen) { unsigned char len = 1, buf[5]; // 编码字符串 if (ZIP_IS_STR(encoding)) { /* Although encoding is given it may not be set for strings, * so we determine it here using the raw length. */ if (rawlen <= 0x3f) {//63 if (!p) return len;//1 buf[0] = ZIP_STR_06B | rawlen; } else if (rawlen <= 0x3fff) {//16383 len += 1;//2 if (!p) return len; buf[0] = ZIP_STR_14B | ((rawlen >> 8) & 0x3f); buf[1] = rawlen & 0xff; } else { len += 4;//5 if (!p) return len; buf[0] = ZIP_STR_32B; buf[1] = (rawlen >> 24) & 0xff; buf[2] = (rawlen >> 16) & 0xff; buf[3] = (rawlen >> 8) & 0xff; buf[4] = rawlen & 0xff; } // 编码整数 } else { /* Implies integer encoding, so length is always 1. */ if (!p) return len; buf[0] = encoding; } /* Store this length at p */ // 将编码后的长度写入 p memcpy(p,buf,len); // 返回编码所需的字节数 return len;}

插入元素

主要过程是： 1.确定插入位置：头插/尾插。分为头部和尾部来讨论，如果在头部插入，则待插入元素所需要的字节数就是头部元素PRelen的值。如果在尾部插入，则尾部元素的字节长度就是p节点的prelen长度。 2.尝试将字符串转换为长整型，比如“123”->123 转换成功将根据encoding获取不同编码获取不同大小例如uint_32位4个字节，否则使用字符串原始长度，例如“hello”长度为5个字节，将这个长度值加到reqlen上，reqlen为新添加节点的长度，包括content的长度和header的长度。 3.将prelen编码长度加到reqlen上 4.将encoding编码长度加到reqlen上 5.之后就是最复杂的一步了，就考虑如果在头部插入元素，且原来头部元素的prelen不够编码新的元素，他们之间产生一个差值，这个差值也要计算到重新分配ziplist时的大小。比如，原节点的prelen为1个字节（记录content小于254的情况），现在插入一个很长的节点，则需要5个字节的空间保存，那么这个额外多出来的4个字节nextdiff则需要记录进来。 6.重新申请ziplist大小，为原长度curlen+新节点长度reqlen+第5步所说的nextdiff。 7.调整原来的元素，为新元素挪动位置。 8.将header写入新元素地址，此时需要挪动指针，方便拷贝content。这部分想了很久：

// 一切搞定，将前置节点的长度写入新节点的 header p += zipPrevEncodeLength(p,prevlen); // 将节点值的长度写入新节点的 header p += zipEncodeLength(p,encoding,slen);//这里写入同时还要移动p的位置，方便后面memcpy拷入content // 写入节点值 if (ZIP_IS_STR(encoding)) { // T = O(N) memcpy(p,s,slen); } else { // T = O(1) zipSaveInteger(p,value,encoding); }

上一篇：ChucK初步（1）

下一篇：Java 8增强的工具类 Arrays（二）