redis 基本數(shù)據(jù)結(jié)構(gòu).

redis的基本數(shù)據(jù)結(jié)構(gòu)主要有: SDS動態(tài)字符串,鏈表,字典,哈希表,跳躍表,整數(shù)集合,壓縮列表.

SDS 動態(tài)字符串

typedef char *sds;

struct sdshdr {
//記錄已使用的長度
    int len;
//記錄buf中未使用字符串
    int free;
//字節(jié)數(shù)據(jù),保存字符串
    char buf[];
};

分配內(nèi)存時,會多分配一個字節(jié)來存放'\0'結(jié)束標(biāo)記.

注意: 在sdshdr結(jié)構(gòu)體中,buf未分配內(nèi)存時,buf是不占空間的

int main(){

    printf("int --- %ld\n",sizeof(int));
    printf("struct sdshdr --- %ld\n", sizeof(struct sdshdr));
    return 0;
}
輸出: 
int --- 4
struct sdshdr --- 8

//分配空間
sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;

    if (init) {
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }
    if (sh == NULL) return NULL;
    sh->len = initlen;
    sh->free = 0;
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}
//獲取字符串長度
static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}
//獲取未使用空間
static inline size_t sdsavail(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->free;
}

優(yōu)點:

• 常數(shù)復(fù)雜度獲取字符串的長度
• 杜絕緩沖區(qū)溢出
• 減少修改字符串時重新分配內(nèi)存的次數(shù)
  1. 空間預(yù)分配
  2. 惰性回收
• 二進制安全

• 兼容部分C字符串

  
  

鏈表

/*
 * 雙端鏈表節(jié)點
 */
typedef struct listNode {

    // 前置節(jié)點
    struct listNode *prev;

    // 后置節(jié)點
    struct listNode *next;

    // 節(jié)點的值
    void *value;

} listNode;

/*
 * 雙端鏈表迭代器
 */
typedef struct listIter {

    // 當(dāng)前迭代到的節(jié)點
    listNode *next;

    // 迭代的方向
    int direction;

} listIter;

/*
 * 雙端鏈表結(jié)構(gòu)
 */
typedef struct list {

    // 表頭節(jié)點
    listNode *head;

    // 表尾節(jié)點
    listNode *tail;

    // 節(jié)點值復(fù)制函數(shù)
    void *(*dup)(void *ptr);

    // 節(jié)點值釋放函數(shù)
    void (*free)(void *ptr);

    // 節(jié)點值對比函數(shù)
    int (*match)(void *ptr, void *key);

    // 鏈表所包含的節(jié)點數(shù)量
    unsigned long len;

} list;

字典

Key-Value

/*
 * 哈希表節(jié)點
 */
typedef struct dictEntry {
    
    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個哈希表節(jié)點，形成鏈表
    struct dictEntry *next;

} dictEntry;

哈希表

/*
 * 哈希表
 *
 * 每個字典都使用兩個哈希表，從而實現(xiàn)漸進式 rehash 。
 */
typedef struct dictht {
    
    // 哈希表數(shù)組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩碼，用于計算索引值
    // 總是等于 size - 1
    unsigned long sizemask;

    // 該哈希表已有節(jié)點的數(shù)量
    unsigned long used;

} dictht;

字典

/*
 * 字典
 */
typedef struct dict {

    // 類型特定函數(shù)
    dictType *type;

    // 私有數(shù)據(jù)
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 當(dāng) rehash 不在進行時，值為 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在運行的安全迭代器的數(shù)量
    int iterators; /* number of iterators currently running */

} dict;

字典的普通狀態(tài):

• 索引值計算
  h = dictHashKey(ht, key) & ht->sizemask;
• 解決鍵沖突
  當(dāng)有兩個或以上數(shù)量的鍵被分配到哈希表上的同一索引的時候,我們稱這些鍵發(fā)生了沖突,redis通過鏈地址法來解決沖突
• rehash
  當(dāng)哈希表保存的鍵值對數(shù)量太多或者太少時,要進行rehash
  漸進式rehash: http://www.itdecent.cn/p/9c84856cd5c0

跳躍表

跳躍表節(jié)點

/*
 * 跳躍表節(jié)點
 */
typedef struct zskiplistNode {

    // 成員對象
    robj *obj;

    // 分值
    double score;

    // 后退指針
    struct zskiplistNode *backward;

    // 層
    struct zskiplistLevel {

        // 前進指針
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

跳躍表

/*
 * 跳躍表
 */
typedef struct zskiplist {

    // 表頭節(jié)點和表尾節(jié)點
    struct zskiplistNode *header, *tail;

    // 表中節(jié)點的數(shù)量
    unsigned long length;

    // 表中層數(shù)最大的節(jié)點的層數(shù)
    int level;

} zskiplist;

//隨機獲取層數(shù)
int zslRandomLevel(void) {
    int level = 1;

    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;

    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

• 跳躍表是有序集合的底層實現(xiàn)
• 跳躍表根據(jù)分值的大小進行排序,當(dāng)分值大小相同時,按照成員對象的大小排序
  詳細(xì)跳躍表講解:
  (http://blog.csdn.net/gqtcgq/article/details/50613896)

整數(shù)集合

整數(shù)集合是集合鍵的底層實現(xiàn)之一,當(dāng)一個集合只包含整數(shù)值,并且這個集合元素不多時,redis會使用整數(shù)集合作為集合鍵的底層實現(xiàn).

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

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

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

} intset;

encoding: 表示整數(shù)集合中,存放的是那種長度的整數(shù):16位,32位,64位.

• 升級
  當(dāng)添加一個整數(shù)到整數(shù)集合中時,如果新元素的長度比集合中的編碼方式都要長時,要發(fā)生升級動作 , 整數(shù)集合只支持升級操作,不支持降級操作.

/* Insert an integer in the intset 
 * 
 * 嘗試將元素 value 添加到整數(shù)集合中。
 *
 * *success 的值指示添加是否成功：
 * - 如果添加成功，那么將 *success 的值設(shè)為 1 。
 * - 因為元素已存在而造成添加失敗時，將 *success 的值設(shè)為 0 。
 *
 * T = O(N)
 */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {

    // 計算編碼 value 所需的長度
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;

    // 默認(rèn)設(shè)置插入為成功
    if (success) *success = 1;

    /* Upgrade encoding if necessary. If we need to upgrade, we know that
     * this value should be either appended (if > 0) or prepended (if < 0),
     * because it lies outside the range of existing values. */
    // 如果 value 的編碼比整數(shù)集合現(xiàn)在的編碼要大
    // 那么表示 value 必然可以添加到整數(shù)集合中
    // 并且整數(shù)集合需要對自身進行升級，才能滿足 value 所需的編碼
    if (valenc > intrev32ifbe(is->encoding)) {
        /* This always succeeds, so we don't need to curry *success. */
        // T = O(N)
        return intsetUpgradeAndAdd(is,value);
    } else {
        // 運行到這里，表示整數(shù)集合現(xiàn)有的編碼方式適用于 value

        /* Abort if the value is already present in the set.
         * This call will populate "pos" with the right position to insert
         * the value when it cannot be found. */
        // 在整數(shù)集合中查找 value ，看他是否存在：
        // - 如果存在，那么將 *success 設(shè)置為 0 ，并返回未經(jīng)改動的整數(shù)集合
        // - 如果不存在，那么可以插入 value 的位置將被保存到 pos 指針中
        //   等待后續(xù)程序使用
        if (intsetSearch(is,value,&pos)) {
            if (success) *success = 0;
            return is;
        }

        // 運行到這里，表示 value 不存在于集合中
        // 程序需要將 value 添加到整數(shù)集合中
    
        // 為 value 在集合中分配空間
        is = intsetResize(is,intrev32ifbe(is->length)+1);
        // 如果新元素不是被添加到底層數(shù)組的末尾
        // 那么需要對現(xiàn)有元素的數(shù)據(jù)進行移動，空出 pos 上的位置，用于設(shè)置新值
        // 舉個例子
        // 如果數(shù)組為：
        // | x | y | z | ? |
        //     |<----->|
        // 而新元素 n 的 pos 為 1 ，那么數(shù)組將移動 y 和 z 兩個元素
        // | x | y | y | z |
        //         |<----->|
        // 這樣就可以將新元素設(shè)置到 pos 上了：
        // | x | n | y | z |
        // T = O(N)
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
    }

    // 將新值設(shè)置到底層數(shù)組的指定位置中
    _intsetSet(is,pos,value);

    // 增一集合元素數(shù)量的計數(shù)器
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);

    // 返回添加新元素后的整數(shù)集合
    return is;
}

升級操作:

/* Upgrades the intset to a larger encoding and inserts the given integer. 
 *
 * 根據(jù)值 value 所使用的編碼方式，對整數(shù)集合的編碼進行升級，
 * 并將值 value 添加到升級后的整數(shù)集合中。
 *
 * 返回值：添加新元素之后的整數(shù)集合
 *
 * T = O(N)
 */
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ù)組）進行空間調(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ù)組進行重分配之后，數(shù)組就被擴容了（符號 ？ 表示未使用的內(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;
}

壓縮列表

壓縮列表是列表鍵和哈希鍵的底層實現(xiàn)之一,當(dāng)一個列表鍵只包含少量列表項,并且每個列表項要么是小數(shù)值,要么是長度比較短的字符串,那么redis會用壓縮列表作為列表鍵的底層實現(xiàn).

壓縮列表整體結(jié)構(gòu):

空 ziplist 示例圖:

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

size          4 bytes   4 bytes 2 bytes  1 byte
            +---------+--------+-------+-----------+
component   | zlbytes | zltail | zllen | zlend     |
            |         |        |       |           |
value       |  1011   |  1010  |   0   | 1111 1111 |
            +---------+--------+-------+-----------+
                                       ^
                                       |
                               ZIPLIST_ENTRY_HEAD
                                       &
address                        ZIPLIST_ENTRY_TAIL
                                       &
                               ZIPLIST_ENTRY_END

非空 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

entry結(jié)構(gòu):

/*
 * 保存 ziplist 節(jié)點信息的結(jié)構(gòu)
 */
typedef struct zlentry {

    // prevrawlen ：前置節(jié)點的長度
    // prevrawlensize ：編碼 prevrawlen 所需的字節(jié)大小
    unsigned int prevrawlensize, prevrawlen;

    // len ：當(dāng)前節(jié)點值的長度
    // lensize ：編碼 len 所需的字節(jié)大小
    unsigned int lensize, len;

    // 當(dāng)前節(jié)點 header 的大小
    // 等于 prevrawlensize + lensize
    unsigned int headersize;

    // 當(dāng)前節(jié)點值所使用的編碼類型
    unsigned char encoding;

    // 指向當(dāng)前節(jié)點的指針
    unsigned char *p;

} zlentry;

• previous_entry_length
  以字節(jié)為單位,記錄了壓縮列表前一個節(jié)點的長度.,該屬性的長度可以是1字節(jié),或者5字節(jié). 如果前節(jié)點的長度小于254字節(jié),則previous_entry_length的長度為1字節(jié),如果前一節(jié)點的長度大于254字節(jié),則previous_entry_length的長度為5字節(jié).其屬性的第一字節(jié)被設(shè)置為0xFE,而后4個字節(jié)保存前一節(jié)點的長度.

• encoding
  記錄節(jié)點的content屬性保存數(shù)據(jù)的類型及長度
  字節(jié)數(shù)組編碼

  
  
  
  

  整數(shù)編碼

  
  

• content
  保存節(jié)點的值
  字節(jié)數(shù)組:

  
  
  
  

  整數(shù)值:

  
  

連鎖更新:
有一種情況,在一個壓縮列表中,有多個連續(xù)的,長度在250字節(jié)---253字節(jié)的節(jié)點,他們的previous_entry_length長度都是1字節(jié),當(dāng)我們在頭部插入一個大于254字節(jié)長度的節(jié)點時,第二個節(jié)點要用5個字節(jié)來保存前一個節(jié)點的長度,但是現(xiàn)在只有1個字節(jié),要進行擴容到5字節(jié),而第三個節(jié)點要保存第二個節(jié)點的長度,由于第二個節(jié)點的previous_entry_length屬性由1字節(jié)變?yōu)榱?字節(jié),第二個節(jié)點的整體長度也超過了254,第三個節(jié)點也需要擴容.這樣一直更新下去,就會發(fā)生連鎖更新.
連鎖更新最壞的復(fù)雜度為O(N2);

添加節(jié)點到要列表或者從壓縮列表刪除節(jié)點,都會發(fā)生連鎖更新操作,但是這個幾率并不高.

參考----<redis設(shè)計與實現(xiàn)>