redis源码学习之压缩列表

2/10/2017来源:ASP.NET技巧人气:345

压缩列表

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

压缩列表是一段连续的内存,每个属性都会有固定的编码大小,例如对于字符串来说,我们需要知道字符串的长度,假设小于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); }