一. 弁言

　　《Redis设想与完成》一书重要分为四个局部，个中第一个局部重要讲的是Redis的底层数据构造与对象的相干学问。

　　Redis是一种基于C言语编写的非干系型数据库，它的五种基础对象范例分别为：STRING，LIST，SET，HASH，ZSET。然则，关于每一种基础对象数据范例，底层都至少有2种分歧的完成体式格局。

二. 简朴动态字符串(Simple Dynamic String, SDS)

　　SDS是Redis的默许字符串透露表现，包罗字符串值的键值对底层都是由SDS完成的。除生存数据库中的字符串值以外，SDS还被用作缓冲区。

示例：

redis>SET msg "hello world"
OK

 　　当实行上述代码以后，Redis会建立一个STRING范例的键值对，个中键和值均是一个字符串对象，键对象的底层是一个生存着字符串"msg"的SDS，而值对象的底层是一个生存着字符串"hello world"的SDS。

　　每一个SDS都构造以下所示：

structsdshdr{//纪录buf数组中已运用的字节数目(也是SDS所生存的字符串长度)
    intlen;//buf数组中未运用的字节数目
    int free;//字节数组，用于存储字符串
    charbuf[];       

};

　　如上图所示，SDS遵照C字符串以空字符末尾的通例，然则生存空字符的一字节空间不盘算在SDS的len属性中。即关于SDS的构造知足：buf的长度 = len + free + 1。即当SDS的len=5,free=0字节时，则buf的长度为 5+0+1=6字节。

　　C字符串本身的两个题目有：1.猎取字符串长度的复杂度高  2.因为C字符串不纪录本身长度轻易形成缓冲区溢出等题目。C字符串修正字符串时会有大批的内存重分派操纵，如拼接字符串时，若是不举行内存重分派，能够会形成缓冲区溢出；举行紧缩字符串操纵时，不举行内存重分派开释不再运用的那局部空间，则会发生内存泄漏。

　　为了处置惩罚上述两个题目，SDS做了一系列的革新操纵。

　　(1)因为SDS将字符串的长度存储在len属性中，所以SDS猎取字符串长度的时候复杂度为O(1)。

　　(2)SDS经由过程设想两种空间分派战略来削减字符串修正时带来的内存重分派次数，同时杜绝了缓冲区溢出的能够性。

SDS的两种空间分派优化战略：

　　SDS的优化战略是经由过程未运用空间(即free符号的空间)完成的

　　(1)空间预分派：用于优化SDS字符串增进操纵。当SDS的API对SDS举行修正而且须要举行空间扩大时，递次不只会为SDS分派修正所须要的空间，还会为SDS分派分外的未运用空间。个中重要分为两点：当len<1MB时，递次分派和len一样巨细的未运用空间，即free=len；当len>=1MB时，free=1MB。

　　(2)惰性空间开释：用于优化SDS的字符串紧缩操纵。当SDS的API须要紧缩SDS生存的字符串时，递次不会立时运用内存重分派往返收紧缩后多出来的空间，而是运用 free 属性将这些字节的数目纪录起来，以供未来运用。(紧缩重分派操纵，并未未来能够有的增进操纵举行了优化)。

三. 链表

　　Redis中链表能够用来完成列表键、宣布与定阅、慢查询、监视器等功能。

　　链表由两种构造构成，分别是list构造和listNode构造，它们的透露表现以下所示：

typedef structlist{

    

    listNode*head;//指向表头
    listNode *tail;//指向表尾
    unsigned long len;//节点数
    void *(*dup)(void *ptr)void *(*free)(void *ptr)int (*match)(void *ptr, void *key)

}list;

typedef structlistNode{struct listNode *prev;//前置节点
    struct listNode *next;//后置节点
    void *value;//节点值
}listNode;

　　依据代码能够晓得，list构造具有一个指向链表表头和一个指向链表表尾的指针，而listNode中有一个前置指针和后置指针，因而，链表取得头、尾节点的时候复杂度为O(1)，且能够从恣意一端最先遍历。另外，list中还存有len属性生存链表长度，因而取得链表长度的时候复杂度仅为O(1)。

四. 字典

　　Redis中字典可用于完成数据库和哈希键等。

　　字典运用哈希表作为底层完成，哈希表dictht和哈希表节点dictEntry构造以下所示：

typedef structdictht{

    disctEntry**table;//哈希表数组
    unsigned long size;//哈希表巨细
    unsigned long sizemask;//哈希表巨细掩码，为size-1，用于盘算索引值
    unsigned long used;//已有节点数
} dictht;

typedef structdictEntry{void *key;//键
    union{//值
        void *val;

        unint64_t u64;

        int64_t s64;

    } v;struct dicEntry *next;//指向下个哈希表节点
} dictEntry;    

　　由构造代码和图可知，dictht构造中size属性为哈希表的总巨细，used为哈希表节点个数；dictEntry节点中存储了键值对和指向下一个节点的指针。而dictht中sizemask属性总即是size-1，该属性值用于哈希算法。

　　字典构造则以下所示：

typedef structdict{

    dictType*type;//范例特定函数
    void *privdata;//私有数据
    dictht ht[2];//两个哈希表
    int rehashidx;//用于符号是不是处于rehash状况
} dict; 

　　字典由dict构造透露表现，其属性type是指向dictType构造的指针，该构造中生存了一簇用于操纵特定范例键值对的函数；privdata属性则生存了须要传给这些函数的可选参数；rehashIdx则用于符号以后字典是不是处于rehash(从新哈希)状况，rehashidx=-1时未举行rehash。(图示中略有毛病，处置惩罚争执时，链地点法是将新节点插进去头部，即头插法，所以应该k2在前，k1在后)

　　字典的哈希算法：每当一个新键值对增添到字典中时，递次须要先依据键盘算出哈希值和索引值，再依据索引值将包罗键值对的哈希节点放到哈希表数组的指定地位。哈希值运用字典的type中存储的哈希函数(hashFunction)盘算(当字典被用作数据库或哈希键(HASH-key)的底层完成时，Redis运用MurmurHash2算法)，而索引值则依据哈希表的sizemask和哈希值盘算，index = 哈希值 & sizemask。例，新增键的哈希值为8，则上图新增键在ht[0]索引值为 8 & 3 = 0。

　　处置惩罚键争执：Redis的哈希表接纳链地点法处置惩罚键争执的题目，且为了速率斟酌，每次都是将新节点增添到链表的表头地位(复杂度为O(1))。

　　哈希表的扩大与紧缩：负载因子 load_factor = ht[0].used / ht[0].size

　　　　(1)当服务器未实行BGSAVE敕令或许BGREWRITEAOF敕令时，且哈希表的负载因子大于即是1时，自动扩大。

　　　　(2)当服务器正在实行BGSAVE敕令或许BGREWRITEAOF敕令时，且哈希表的负载因子大于即是5时，自动扩大。

　　　　(3)当哈希表的负载因子小于0.1时，递次对哈希表自动紧缩。

　　　　之所以有(1)、(2)的区分，是因为在实行这些敕令的过程当中，Reis须要建立以后服务器历程的子历程，而大多数操纵系统都接纳写时复制手艺来优化紫禁城的运用效力；因而，子历程存在时期，服务器会进步举行扩大操纵所需的负载因子，尽量制止子历程存在时期举行哈希表扩大操纵，制止不须要的内存写入，最大限制的勤俭内存。

　　渐进式rehash：当递次须要对哈希表的巨细举行扩大或许紧缩时，须要经由过程rehash操纵来完成。

　　　　(1)字典会为ht[1]的哈希表分派空间(扩大操纵，ht[1]巨细为第一个大于即是ht[0].used*2的2ⁿ；紧缩操纵，则ht[1]巨细为第一个大于即是ht[0].used的2ⁿ)。

　　　　(2)将生存在ht[0]上的键值对rehash到ht[1]上(即从新盘算键的哈希值和索引值)。

　　　　(3)当ht[0]上的键值对悉数迁徙终了后，开释ht[0]，并将ht[1]设置ht[0]，再建立一个空缺哈希表作为ht[1]，为下次rehash预备。

　　　　值得注意的是，rehash操纵并非一次性鸠合完成的，而是分屡次、渐进式的完成。为了制止rehas对服务器机能形成影响，rehash采取了分而治之的体式格局，将rehash键值对所需的盘算事情平摊到对字典的增添、删除、查找和更新操纵上，从而制止鸠合式rehash带来了重大盘算量。

五. 腾跃表

　　腾跃表是有序鸠合键的底层完成之一，它的构造由zskiplist和zskiplistNode构成，其构造和代码以下图所示

typedef structzskiplistNode{struct zskiplistNode *backward;//退却指针
    double score;//分值
    robj *obj;//成员对象
    structzskiplistLevel {struct zskiplistNode *forward;//行进指针
        unsigned int span;//跨度
}

} zskiplistNode;

　　zskiplist生存腾跃表信息，header指向表头节点，tail指向表尾节点，level为腾跃表中的最大层数(表头节点层数不算在内)，length为腾跃表长度(不包罗表头节点)。

　　zskiplistNode为腾跃表节点，level数组中能够包罗多个元素分为多个层(每一个腾跃表层高都是1~32之间的整数)，每一个层都有一个forward行进指针(用于表头向表尾偏向接见)和一个span跨度(用于纪录两个节点之间的间隔以及纪录排位的，一切指向NULL的行进指针跨度都为0)；backward指针用于从表尾向表头偏向遍用时运用(每次只能退却一个节点)；score分值是一个double范例的浮点数，腾跃表中节点都按分值从小到大排序；obj属性是一个指向字符串对象的指针，而字符串对象生存着一个SDS值。

　　同一个腾跃表中，多个节点能够包罗雷同的分值，但每一个节点的成员对象必需是独一的。

　　腾跃表中的节点依照分值巨细递次分列，当分值雷同时，依照成员对象的巨细分列。

六. 整数鸠合

　　整数鸠应时Redis中用于生存整数值的鸠合笼统数据构造，其构造代码和图示以下所示：

typedef structintset{

    uint32_t encoding;//编码体式格局
    uint32_t length;//鸠合包罗的元素数目
    int8_t contents;//生存元素的数组
} intset;

　　个中，encoding为intset的编码体式格局，length存储元素的数目，contents数组是整数鸠合的底层完成，其内的元素按从小到大的体式格局生存。contents数组的真正范例取决于encoding的值。

　　整数鸠合的晋级操纵：每当一个范例比整数鸠合现有一切元素的范例都要长的新元素增添到整数鸠合中时，整数鸠合都须要先举行晋级操纵。

　　　　(1)依据新元素的范例，扩大整数鸠合底层数组的空间巨细，并未新元素分派空间。

　　　　(2)将本来元素转换为新元素雷同的范例，并从后往前顺次安排本来的元素(安排过程当中需地位底层数组的有序性子稳定)

　　　　(3)将新元素增添到底层数组中

　　　　从上可知，向整数鸠合增添新元素的时候复杂度为O(n)。

　　晋级的优点：

　　　　(1)经由过程自动晋级来运用分歧范例元素的数组，提升了整数鸠合的灵活性

　　　　(2)尽量节约内存。(如构造有在将int32_t范例存入时，本来的int16_t范例数组才会转换，不须要预先设定好)

七. 紧缩列表

　　紧缩列表式列表建和哈希键的底层完成之一，是Redis为了勤俭内存而开辟的，是一系列特别编码的一连内存块构成的递次型数据构造。其构造以下所示：

　　zlbytes透露表现紧缩列表总长度，zltail透露表现偏移量（用于纪录气质地点到表尾节点的间隔有若干字节），zllen为紧缩列表节点个数，entry等都是紧缩列表的节点，zlend用于符号紧缩链表末尾。而紧缩列表节点中，previous_entry_length透露表现前一个节点长度(该属性长度能够是1字节或许5字节)，encoding透露表现content属性生存的数据范例与长度，content卖力生存节点值。

　　若是前一个节点长度小于254字节，previous_entry_length长度为1字节；若是前一个节点长度大于即是254字节，previous_entry_length长度为5字节，背面4个字节生存前一个节点长度，第一个字节的值被设置为0x05。

　　紧缩列表从表尾向表头的遍历就是基于 previous_entry_length属性完成的(先要取得肇端地点，再依据zltail取得指向表尾节点的指针，然后previous_entry_length属性盘算出前一个节点的地点，即可顺次从后往前遍历)。

　　因为previous_entry_length属性纪录前一个节点的长度，且该属性的长度由前一个节点的长度决议，因而在某些特别状况下，删除或许增添节点能够会形成连锁更新(即特别状况下发生的一连屡次空间扩大操纵)。比方，本来紧缩列表节点长度都小于254（确实的说是250~253之间），此时将一个长度大于254的节点放到他们之前，便会引发后一个节点previous_entry_length的长度转变，从而使后一个节点长度大于即是254，顺次类推，就想多米诺骨牌一样形成连锁反应。删除节点时的特别状况则恰好相反。

　　连锁更新在最坏状况下复杂度为O(N²)，但真正形成这类状况涌现的操纵其实不多见。