redis源碼學(xué)習(xí)之壓縮列表

2019-11-14 12:08:24

字體：大中小

供稿：網(wǎng)友

壓縮列表

列表鍵和哈希鍵的底層實(shí)現(xiàn)。是為了節(jié)約內(nèi)存而實(shí)現(xiàn)。

壓縮列表是一段連續(xù)的內(nèi)存，每個(gè)屬性都會(huì)有固定的編碼大小，例如對(duì)于字符串來(lái)說(shuō)，我們需要知道字符串的長(zhǎng)度，假設(shè)小于63字節(jié)，那么我們只需要一個(gè)字節(jié)的大小來(lái)表示（2位標(biāo)識(shí)，6位數(shù)據(jù)）；而存儲(chǔ)的結(jié)構(gòu)是整型的數(shù)的話，我們只需要1個(gè)字節(jié)來(lái)表示該整型是16/32/64位整型。

壓縮列表用一段連續(xù)內(nèi)存表示unsigned char *類型指針來(lái)訪問(wèn)，不過(guò)它人為的規(guī)定了這一段連續(xù)內(nèi)存的數(shù)據(jù)類型：前4個(gè)字節(jié)（uint32_t）表示整個(gè)ziplist的長(zhǎng)度所占用的內(nèi)存數(shù)：zlbytes；再往后4個(gè)字節(jié)表示表尾節(jié)點(diǎn)到壓縮列表的字節(jié)數(shù)：zltail；然后2個(gè)字節(jié)（uint16_t）表示壓縮列表中節(jié)點(diǎn)數(shù)目：zllen；之后就是數(shù)據(jù)內(nèi)容zlentry；最后壓縮列表有1個(gè)字節(jié)的特殊值標(biāo)記列表末尾：zlend：0xFF

根據(jù)上述說(shuō)明，redis定義了一些宏來(lái)獲取各個(gè)元素的值，主要是進(jìn)行地址運(yùn)算，因?yàn)閔eader的大小固定：

// 定位到 ziplist 的 bytes 屬性，該屬性記錄了整個(gè) ziplist 所占用的內(nèi)存字節(jié)數(shù)// 用于取出 bytes 屬性的現(xiàn)有值，或者為 bytes 屬性賦予新值#define ZIPLIST_BYTES(zl) (*((uint32_t*)(zl)))// 定位到 ziplist 的 offset 屬性，該屬性記錄了到達(dá)表尾節(jié)點(diǎn)的偏移量// 用于取出 offset 屬性的現(xiàn)有值，或者為 offset 屬性賦予新值#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl)+sizeof(uint32_t))))// 定位到 ziplist 的 length 屬性，該屬性記錄了 ziplist 包含的節(jié)點(diǎn)數(shù)量// 用于取出 length 屬性的現(xiàn)有值，或者為 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 第一個(gè)節(jié)點(diǎn)（的起始位置）的指針#define ZIPLIST_ENTRY_HEAD(zl) ((zl)+ZIPLIST_HEADER_SIZE)// 返回指向 ziplist 最后一個(gè)節(jié)點(diǎn)（的起始位置）的指針#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)

對(duì)字節(jié)長(zhǎng)度進(jìn)行編碼，有兩個(gè)數(shù)據(jù)類型，一個(gè)是字節(jié)長(zhǎng)度，一個(gè)是編碼字節(jié)長(zhǎng)度所需要的長(zhǎng)度。

在Redis設(shè)計(jì)與實(shí)現(xiàn)中，給了兩個(gè)表格，分別是字節(jié)數(shù)組編碼（在源碼中又叫字符串），整數(shù)編碼。

現(xiàn)在給定一個(gè)長(zhǎng)度len，需要對(duì)其進(jìn)行編碼。首先源碼中定義了一些宏，分別表示不同字節(jié)范圍表示的編碼。

/* * 字符串編碼類型 */#define ZIP_STR_06B (0 << 6)//長(zhǎng)度小于等于63字節(jié)#define ZIP_STR_14B (1 << 6)//長(zhǎng)度小于等于16383字節(jié)#define ZIP_STR_32B (2 << 6)//長(zhǎng)度小于等于4294967295字節(jié)/* * 整數(shù)編碼類型 */#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

這種編碼方式很好理解，對(duì)于長(zhǎng)度小于等于63字節(jié)編碼，編碼方式應(yīng)該是00xxxxxx，除了高位兩位的標(biāo)識(shí)位，后六位能表示的數(shù)字范圍為0~63，這是1個(gè)字節(jié)的情況。當(dāng)數(shù)據(jù)變大時(shí)，一個(gè)字節(jié)顯然不能滿足條件了，因此就需要加一個(gè)字節(jié)（8+6 位）的編碼長(zhǎng)度來(lái)表示長(zhǎng)度。

如果是整型類型編碼就容易多了，不同于字節(jié)數(shù)組需要記錄數(shù)據(jù)長(zhǎng)度，整型數(shù)據(jù)總是只需要1個(gè)字節(jié)來(lái)表示整型數(shù)據(jù)類型。

在redis源碼src/ziplist.c中用zipEncodeLength函數(shù)來(lái)描述上述過(guò)程。

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; } // 編碼整數(shù) } else { /* Implies integer encoding, so length is always 1. */ if (!p) return len; buf[0] = encoding; } /* Store this length at p */ // 將編碼后的長(zhǎng)度寫入 p memcpy(p,buf,len); // 返回編碼所需的字節(jié)數(shù) return len;}

插入元素

主要過(guò)程是： 1.確定插入位置：頭插/尾插。分為頭部和尾部來(lái)討論，如果在頭部插入，則待插入元素所需要的字節(jié)數(shù)就是頭部元素PRelen的值。如果在尾部插入，則尾部元素的字節(jié)長(zhǎng)度就是p節(jié)點(diǎn)的prelen長(zhǎng)度。 2.嘗試將字符串轉(zhuǎn)換為長(zhǎng)整型，比如“123”->123 轉(zhuǎn)換成功將根據(jù)encoding獲取不同編碼獲取不同大小例如uint_32位4個(gè)字節(jié)，否則使用字符串原始長(zhǎng)度，例如“hello”長(zhǎng)度為5個(gè)字節(jié)，將這個(gè)長(zhǎng)度值加到reqlen上，reqlen為新添加節(jié)點(diǎn)的長(zhǎng)度，包括content的長(zhǎng)度和header的長(zhǎng)度。 3.將prelen編碼長(zhǎng)度加到reqlen上 4.將encoding編碼長(zhǎng)度加到reqlen上 5.之后就是最復(fù)雜的一步了，就考慮如果在頭部插入元素，且原來(lái)頭部元素的prelen不夠編碼新的元素，他們之間產(chǎn)生一個(gè)差值，這個(gè)差值也要計(jì)算到重新分配ziplist時(shí)的大小。比如，原節(jié)點(diǎn)的prelen為1個(gè)字節(jié)（記錄content小于254的情況），現(xiàn)在插入一個(gè)很長(zhǎng)的節(jié)點(diǎn)，則需要5個(gè)字節(jié)的空間保存，那么這個(gè)額外多出來(lái)的4個(gè)字節(jié)nextdiff則需要記錄進(jìn)來(lái)。 6.重新申請(qǐng)ziplist大小，為原長(zhǎng)度curlen+新節(jié)點(diǎn)長(zhǎng)度reqlen+第5步所說(shuō)的nextdiff。 7.調(diào)整原來(lái)的元素，為新元素挪動(dòng)位置。 8.將header寫入新元素地址，此時(shí)需要挪動(dòng)指針，方便拷貝content。這部分想了很久：

// 一切搞定，將前置節(jié)點(diǎn)的長(zhǎng)度寫入新節(jié)點(diǎn)的 header p += zipPrevEncodeLength(p,prevlen); // 將節(jié)點(diǎn)值的長(zhǎng)度寫入新節(jié)點(diǎn)的 header p += zipEncodeLength(p,encoding,slen);//這里寫入同時(shí)還要移動(dòng)p的位置，方便后面memcpy拷入content // 寫入節(jié)點(diǎn)值 if (ZIP_IS_STR(encoding)) { // T = O(N) memcpy(p,s,slen); } else { // T = O(1) zipSaveInteger(p,value,encoding); }

上一篇：Codeforces Round #395 (Div. 2) D Timofey and rectangles（思維題）

下一篇：C結(jié)構(gòu)體