(Redis设计与实现-1) 数据结构

摘要：负载因子哈希表已保存节点数量哈希表大小渐进式为了避免对服务器性能造成影响，服务器不是一次性将里面的所有键值对全部到，而是分多次渐进式地将里面的键值对慢慢地到。步骤为分配空间，让字典同时持有和两个哈希表。

一.简单动态字符串

Redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符数组）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。

struct sdshdr {
    int len;   //记录buf数组中已使用字节的数量
    int free;  //记录buf数组中未使用字节的数量
    char buf[];  //字节数组，用于保存字符串
};

a.free属性的值为5,表示这个SDS有5个未使用空间。

b.len属性的值为5,表示这个 SDS 保存了一个五字节长的字符串。

c.buf属性是一个char类型的数组， 数组的前五个字节分别保存了 "R" 、 "e" 、 "d" 、 "i" 、 "s" 五个字符，而
最后一个字节则保存了空字符 "" 。使得SDS可以直接重用一部分C字符串函数库里面的函数。

(1).SDS的空间分配策略

空间预分配：空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间。

a.如果对SDS进行修改之后，SDS的长度（也即是 len 属性的值）将小于1MB，那么程序分配和len属性同样大小的未使
用空间，这时 SDS len 属性的值将和 free 属性的值相同。

b.如果对SDS进行修改之后，SDS的长度将大于等于1MB， 那么程序会分配1 MB的未使用空间。

惰性空间释放：惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。

(2).二进制安全

因为在C中，除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据， 而不能保存二进制数据。而所有SDS API 都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤。这也是我们将SDS的buf属性称为字节数组的原因（Redis 不是用这个数组来保存字符， 而是用它来保存一系列二进制数据）。

二.链表

Redis中的每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表。

//链表
typedef struct list {
    listNode *head; // 表头节点
    listNode *tail; // 表尾节点
    unsigned long len; // 链表所包含的节点数量
    void *(*dup)(void *ptr);  // 节点复制函数
    void (*free)(void *ptr); // 节点释放函数
    int (*match)(void *ptr, void *key);// 节点对比函数
} list;


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

三.字典

字典，又称符号表（symbol table）， 是一种用于保存键值对（key-value pair）的抽象数据结构。字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等。

//字典
typedef struct dict {
    dictType *type;// 指定特定类型函数
    void *privdata;// 保存了需要传给那些特定类型函数的可选参数
    dictht ht[2]; // 哈希表,一般情况下,字典只使用ht[0]哈希表,ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
    int rehashidx;//它记录了rehash目前的进度，当rehash不在进行时，值为 -1
} dict;


//哈希表
typedef struct dictht {
    dictEntry **table; // 哈希表数组
    unsigned long size; // 哈希表大小
    unsigned long sizemask;// 哈希表大小掩码，用于计算索引值，总是等于 size - 1
    unsigned long used; // 该哈希表已有节点的数量
} dictht;


//哈希节点
typedef struct dictEntry {
    void *key;// 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;   // 值
    struct dictEntry *next;// 用于解决冲突
} dictEntry;


//类型函数
typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);// 计算哈希值的函数
    void *(*keyDup)(void *privdata, const void *key);// 复制键的函数
    void *(*valDup)(void *privdata, const void *obj); // 复制值的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);// 对比键的函数
    void (*keyDestructor)(void *privdata, void *key);// 销毁键的函数
    void (*valDestructor)(void *privdata, void *obj);// 销毁值的函数
} dictType;

(1).哈希算法

#使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

#使用哈希表的sizemask属性和哈希值，计算出索引值
index = hash & dict->ht[x].sizemask;

#根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面

#计算键 k0 的哈希值
hash = dict->type->hashFunction(k0);

#假设计算得出的哈希值为8 ，计算出索引值
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;

(2).解决键冲突

Redis的哈希表使用链地址法（separate chaining）来解决键冲突：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来,因为 dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置（复杂度为 O(1)），排在其他已有节点的前面。

(3).rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。这个过程叫做rehash

步骤:

a.为字典的ht[1]哈希表分配空间,这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量(也即
是ht[0].used 属性的值)：
    如果执行的是扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n；
    如果执行的是收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。

b.将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash 指的是重新计算键的哈希值和索引值，然后将键值对放
置到ht[1]哈希表的指定位置上。

c.当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0] 变为空表），释放 ht[0] ，将ht[1]设置为ht[0] ，并在 
ht[1]新创建一个空白哈希表，为下一次rehash做准备。

哈希表的扩展发生时机:
a.服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 1 ；
b.服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于 5 ；

哈希表的收缩发生时机:
a.当哈希表的负载因子小于 0.1 时， 程序自动开始对哈希表执行收缩操作。


#负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

(4).渐进式 rehash

为了避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里面的所有键值对全部rehash到ht[1] ，而是分多次、渐进式地将ht[0]里面的键值对慢慢地rehash到ht[1] 。

步骤:

a.为 ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。

b.在字典中维持一个索引计数器变量rehashidx,并将它的值设置为 0 ，表示rehash工作正式开始。

c.在rehash进行期间，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash
到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。

d.随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx 
属性的值设为 -1 ，表示 rehash 操作已完成。

渐进式rehash执行期间的哈希表操作:

a.在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删
除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行，程序会先在ht[0]里面进行查找，如果
没找到的话，就会继续到ht[1]里面进行查找。

b.在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而 ht[0] 则不再进行任何添加操作,
这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。

四.跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

//跳跃表
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 表头节点和表尾节点
    unsigned long length; // 表中节点的数量(表头节点不计算在内)
    int level;// 表中层数最大的节点的层数(表头节点的层数不计算在内)
} zskiplist;


//跳跃表节点
typedef struct zskiplistNode {
    struct zskiplistNode *backward; // 后退指针
    double score;  // 节点的分值,跳跃表中的所有节点都按分值从小到大来排序
    robj *obj; // 所保存的成员对象,每个节点的成员对象必须是唯一的
    struct zskiplistLevel {
        struct zskiplistNode *forward;// 前进指针
       unsigned int span; //跨度,记录了前进指针所指向节点和当前节点的距离
    } level[];// 层
} zskiplistNode;

注意表头节点和其他节点的构造是一样的：表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性都不会被用到，所以图中省略了这些部分， 只显示了表头节点的各个层。

每次创建一个新跳跃表节点的时候， 程序都根据幂次定律 （power law，越大的数出现的概率越小） 随机生成一个介于 1 和 32 之间的值作为 level 数组的大小， 这个大小就是层的“高度”。 一般来说，层的数量越多，访问其他节点的速度就越快

五.整数集合

整数集合（intset）是Redis 用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t 、int32_t 或者 int64_t的整数值，并且保证集合中不会出现重复元素。

typedef struct intset {
    uint32_t encoding;  // 编码方式
    uint32_t length;// 集合包含的元素数量
    int8_t contents[]; // 保存元素的数组,各个项从小到大有序地排列， 并且不包含任何重复项。
} intset;

编码方式:

a.如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个
项都是一个 int16_t 类型的整数值

b.如果 encoding 属性的值为 INTSET_ENC_INT32 ， 那么 contents 就是一个 int32_t 类型的数组， 数组里的每个
项都是一个 int32_t 类型的整数值

c.如果 encoding 属性的值为 INTSET_ENC_INT64 ， 那么 contents 就是一个 int64_t 类型的数组， 数组里的每个
项都是一个 int64_t 类型的整数值

(1).升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

步骤:

a.根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

b.将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元
素的过程中，需要继续维持底层数组的有序性质不变。

c.将新元素添加到底层数组里面。

(2).降级

整数集合不支持降级操作， 一旦对数组进行了升级， 编码就会一直保持升级后的状态。

六.压缩列表

压缩列表是 Redis 为了节约内存而开发的， 由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。一个压缩列表可以包含任意多个节点（entry）， 每个节点可以保存一个字节数组或者一个整数值。

(1).压缩列表节点

previous_entry_length:

a.如果前一节点的长度小于254字节，那么previous_entry_length属性的长度为1字节：前一节点的长度就保存在这一
个字节里面。

b.如果前一节点的长度大于等于254字节，那么previous_entry_length属性的长度为5字节：其中属性的第一字节会被
设置为 0xFE（十进制值 254）， 而之后的四个字节则用于保存前一节点的长度。

encoding:

a.1字节、2字节或者5字节长，值的最高位为 00 、 01 或者 10 的是字节数组编码：这种编码表示节点的content属性
保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录；

b.1字节，值的最高位以 11 开头的是整数编码：这种编码表示节点的content属性保存着整数值，整数值的类型和长度
由编码除去最高两位之后的其他位记录；

(2).连锁更新

a.当e1至eN的所有节点的长度都小于254 字节，所以记录这些节点的长度只需要1字节长的 previous_entry_length属
性。

b.如果我们将一个长度大于等于254字节的新节点new设置为压缩列表的表头节点，那么new将成为e1的前置节点，因为
 e1的previous_entry_length属性仅长1字节，它没办法保存新节点new的长度，所以程序将对压缩列表执行空间重分配
操作，并将e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长，e1长度的改变导致后续节点
连锁更新

连锁更新不可避免， 但它真正造成性能问题的几率是很低的，因为压缩列表只在包含少量列表项场景下使用