Redis 源碼--省內(nèi)存大法--intset和ziplist

今天把這兩貨放在一起來看看，因為Redis是把數(shù)據(jù)都放在了內(nèi)存里，所以涉及到內(nèi)存的占用雳旅，基本就是能省則省，對于一些小容量的redis對象來說间聊，redis底層會選擇一些壓縮數(shù)據(jù)結(jié)構(gòu)而不是大容量的結(jié)構(gòu)來存儲他們,今天要寫的就屬于這種類型攒盈。分別是Intset和ziplist.

先來看看intset吧，顧名思義哎榴，這玩意就是一個整數(shù)集合型豁，用來實現(xiàn)少量整數(shù)的集合。下面是它的類型定義尚蝌。

typedef struct intset {
 
    // 編碼方式
    uint32_t encoding;

    // 集合包含的元素數(shù)量
    uint32_t length;

    // 保存元素的數(shù)組
    int8_t contents[];

} intset;

intset是一種具有一致類型數(shù)據(jù)的set迎变，它里面的數(shù)據(jù)可以是int_16 int_32 int_64 的，為了區(qū)分他們飘言，需要一個encoding來記錄contents數(shù)組里面存放的是何種數(shù)據(jù)衣形。
當(dāng)我們需要放入的數(shù)據(jù)超出了當(dāng)前set的encoding所能表示的范圍，那么我們就需要對intset進(jìn)行升級姿鸿，也就是upgrade方法
哦對了谆吴，下面的代碼里會出現(xiàn)一個定義在endianconv中的反轉(zhuǎn)字節(jié)函數(shù)。它是這么定義的苛预。以intrev32ifbe為例句狼。

uint32_t intrev32(uint32_t v) {
    memrev32(&v);
    return v;
}

void memrev32(void *p) {
    unsigned char *x = p, t;

    t = x[0];
    x[0] = x[3];
    x[3] = t;
    t = x[1];
    x[1] = x[2];
    x[2] = t;
}

對于為什么要使用這種函數(shù)，注釋里是這么說的热某。
Redis tries to encode everything as little endian (but a few things that need

to be backward compatible are still in big endian) because most of the
production environments are little endian, and we have a lot of conversions
in a few places because ziplists, intsets, zipmaps, need to be endian-neutral
even in memory, since they are serialied on RDB files directly with a single
write(2) without other additional steps.
簡單來說腻菇，在redis的RDB持久化方式中胳螟，ziplists, intsets等是直接被寫到文件中去的，所以這要求他們在內(nèi)存中是大小端中性（endian-neutral）筹吐，而大部分環(huán)境是小端法的糖耸，于是對于這些壓縮的數(shù)據(jù)結(jié)構(gòu)，redis總是采取小端法的方式來存放字節(jié)骏令，那么對于大端法的機器來說蔬捷，想要得到正確的數(shù)，便需要端轉(zhuǎn)換榔袋。需要注意的是周拐，反轉(zhuǎn)的僅僅是作為參數(shù)傳入的在棧上的字節(jié)，對于結(jié)構(gòu)體自身的字節(jié)并未發(fā)生改變凰兑。

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    
    // 當(dāng)前的編碼方式
    uint8_t curenc = intrev32ifbe(is->encoding);

    // 新值所需的編碼方式
    uint8_t newenc = _intsetValueEncoding(value);

    // 當(dāng)前集合的元素數(shù)量
    int length = intrev32ifbe(is->length);

    // 根據(jù) value 的值妥粟，決定是將它添加到底層數(shù)組的最前端還是最后端
    // 注意，因為 value 的編碼比集合原有的其他元素的編碼都要大
    // 所以 value 要么大于集合中的所有元素吏够，要么小于集合中的所有元素
    // 因此勾给，value 只能添加到底層數(shù)組的最前端或最后端
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    // 更新集合的編碼方式
    is->encoding = intrev32ifbe(newenc);
    // 根據(jù)新編碼對集合（的底層數(shù)組）進(jìn)行空間調(diào)整
    // T = O(N)
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    // 根據(jù)集合原來的編碼方式，從底層數(shù)組中取出集合元素
    // 然后再將元素以新編碼的方式添加到集合中
    // 當(dāng)完成了這個步驟之后锅知，集合中所有原有的元素就完成了從舊編碼到新編碼的轉(zhuǎn)換
    // 因為新分配的空間都放在數(shù)組的后端播急，所以程序先從后端向前端移動元素
    // 舉個例子，假設(shè)原來有 curenc 編碼的三個元素售睹，它們在數(shù)組中排列如下：
    // | x | y | z | 
    // 當(dāng)程序?qū)?shù)組進(jìn)行重分配之后桩警，數(shù)組就被擴(kuò)容了（符號 ？ 表示未使用的內(nèi)存）：
    // | x | y | z | ? |   ?   |   ?   |
    // 這時程序從數(shù)組后端開始昌妹，重新插入元素：
    // | x | y | z | ? |   z   |   ?   |
    // | x | y |   y   |   z   |   ?   |
    // |   x   |   y   |   z   |   ?   |
    // 最后捶枢，程序可以將新元素添加到最后 ？ 號標(biāo)示的位置中：
    // |   x   |   y   |   z   |  new  |
    // 上面演示的是新元素比原來的所有元素都大的情況飞崖，也即是 prepend == 0
    // 當(dāng)新元素比原來的所有元素都小時（prepend == 1）烂叔，調(diào)整的過程如下：
    // | x | y | z | ? |   ?   |   ?   |
    // | x | y | z | ? |   ?   |   z   |
    // | x | y | z | ? |   y   |   z   |
    // | x | y |   x   |   y   |   z   |
    // 當(dāng)添加新值時，原本的 | x | y | 的數(shù)據(jù)將被新值代替
    // |  new  |   x   |   y   |   z   |
    // T = O(N)
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    // 設(shè)置新值固歪，根據(jù) prepend 的值來決定是添加到數(shù)組頭還是數(shù)組尾
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);

    // 更新整數(shù)集合的元素數(shù)量
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);

    return is;
}

這里的upgradeAndAdd看上去很長蒜鸡，但其實無非就是根據(jù)值決定放在首部還是尾部（因為set是有序的），由于整個過程是需要重新移動數(shù)據(jù)的牢裳，所以復(fù)雜度應(yīng)該是O（N）术瓮，這個復(fù)雜度只在小的時候是可以接受的，好在我們本來就是需要能盡量減少內(nèi)存的使用贰健，這也可以視為是一種 time space trade off.
剩下的方法也差不多，在此基礎(chǔ)上恬汁，對于set進(jìn)行插入伶椿，查找辜伟，刪除。
接下來可以來看看ziplist了脊另。很相似的导狡，ziplist是一種壓縮型的列表，它記錄尾部偎痛，從尾到頭來遍歷整個list旱捧。

非空 ziplist 示例圖

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL

每個 ziplist 節(jié)點的前面都帶有一個 header ，這個 header 包含兩部分信息：

 *
 * 1)前置節(jié)點的長度踩麦，在程序從后向前遍歷時使用枚赡。
 *
 * 2)當(dāng)前節(jié)點所保存的值的類型和長度。

對于前置長度谓谦，為了要省內(nèi)存贫橙，喪心病狂的使用了兩種編碼。

 *
 * 1) 如果前置節(jié)點的長度小于 254 字節(jié)反粥，那么程序?qū)⑹褂?1 個字節(jié)來保存這個長度值卢肃。
 *
 * 2) 如果前置節(jié)點的長度大于等于 254 字節(jié)，那么程序?qū)⑹褂?5 個字節(jié)來保存這個長度值：
 *    a) 第 1 個字節(jié)的值將被設(shè)為 254 才顿，用于標(biāo)識這是一個 5 字節(jié)長的長度值莫湘。
 *    b) 之后的 4 個字節(jié)則用于保存前置節(jié)點的實際長度。

當(dāng)然郑气，對于本節(jié)點自身的長度幅垮，也是不放過的：

1) 如果節(jié)點保存的是字符串值，
 *    那么這部分 header 的頭 2 個位將保存編碼字符串長度所使用的類型竣贪，
 *    而之后跟著的內(nèi)容則是字符串的實際長度军洼。
 *
 * |00pppppp| - 1 byte
 *      String value with length less than or equal to 63 bytes (6 bits).
 *      字符串的長度小于或等于 63 字節(jié)。
 * |01pppppp|qqqqqqqq| - 2 bytes
 *      String value with length less than or equal to 16383 bytes (14 bits).
 *      字符串的長度小于或等于 16383 字節(jié)演怎。
 * |10______|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| - 5 bytes
 *      String value with length greater than or equal to 16384 bytes.
 *      字符串的長度大于或等于 16384 字節(jié)匕争。
 *
 * 2) 如果節(jié)點保存的是整數(shù)值，
 *    那么這部分 header 的頭 2 位都將被設(shè)置為 1 爷耀，
 *    而之后跟著的 2 位則用于標(biāo)識節(jié)點所保存的整數(shù)的類型甘桑。
 *
 * |11000000| - 1 byte
 *      Integer encoded as int16_t (2 bytes).
 *      節(jié)點的值為 int16_t 類型的整數(shù)，長度為 2 字節(jié)歹叮。
 * |11010000| - 1 byte
 *      Integer encoded as int32_t (4 bytes).
 *      節(jié)點的值為 int32_t 類型的整數(shù)跑杭，長度為 4 字節(jié)。
 * |11100000| - 1 byte
 *      Integer encoded as int64_t (8 bytes).
 *      節(jié)點的值為 int64_t 類型的整數(shù)咆耿，長度為 8 字節(jié)德谅。
 * |11110000| - 1 byte
 *      Integer encoded as 24 bit signed (3 bytes).
 *      節(jié)點的值為 24 位（3 字節(jié)）長的整數(shù)。
 * |11111110| - 1 byte
 *      Integer encoded as 8 bit signed (1 byte).
 *      節(jié)點的值為 8 位（1 字節(jié)）長的整數(shù)萨螺。
 * |1111xxxx| - (with xxxx between 0000 and 1101) immediate 4 bit integer.
 *      Unsigned integer from 0 to 12. The encoded value is actually from
 *      1 to 13 because 0000 and 1111 can not be used, so 1 should be
 *      subtracted from the encoded 4 bit value to obtain the right value.
 *      節(jié)點的值為介于 0 至 12 之間的無符號整數(shù)窄做。
 *      因為 0000 和 1111 都不能使用愧驱，所以位的實際值將是 1 至 13 。
 *      程序在取得這 4 個位的值之后椭盏，還需要減去 1 组砚，才能計算出正確的值。
 *      比如說掏颊，如果位的值為 0001 = 1 糟红，那么程序返回的值將是 1 - 1 = 0 。
 * |11111111| - End of ziplist.
 *      ziplist 的結(jié)尾標(biāo)識

看到這么多的格式乌叶，是不是要崩潰了盆偿。。枉昏。其實我的感覺也是差不多的陈肛，為了省內(nèi)存，這也是沒有辦法的事情兄裂。說了這么多句旱，當(dāng)前面的結(jié)點長度改變時，有時還會發(fā)生更蛋疼的事情晰奖，那就是前面結(jié)點的長度超過我之前記錄的一個字節(jié)所能容納的范圍了谈撒，于是我就是變成四個字節(jié)了，這可沒那么輕松匾南，又得重新分配內(nèi)存了啃匿，最糟糕的事情是一個結(jié)點的更新如同蝴蝶效應(yīng)一般，造成了之后的結(jié)點的長度都超出了一個字節(jié)所能表示（255字節(jié)）的范圍蛆楞，那么我得連鎖更新溯乒，不過，從概率學(xué)的角度來說豹爹，那并不是很容易發(fā)生裆悄。
寫到這里，我也覺得很蛋疼臂聋，但是沒有辦法作為一種跑在內(nèi)存里吃內(nèi)存的NOSQL光稼，為了省內(nèi)存，redis也是拼了孩等。