redis源碼學習之壓縮列表

2019-11-14 12:08:24

字體：大中小

來源：轉載

供稿：網友

壓縮列表

列表鍵和哈希鍵的底層實現。是為了節約內存而實現。

壓縮列表是一段連續的內存，每個屬性都會有固定的編碼大小，例如對于字符串來說，我們需要知道字符串的長度，假設小于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); }

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

下一篇：C結構體