2021-05-09 23:48 已编辑吉林大学 Java

关注

Redis读书笔记（一）Redis的数据结构

一、Redis的数据结构

1.简单动态字符串

在Redis里面，C字符串只会作为字符串字面量，用在一些无须对字符串值修改的地方，比如日志打印。而当Redis需要的是一个可以被修改的字符串值时，Redis就会使用SDS来表示字符串值。

SDS还被用作缓冲区，比如AOF模块中的AOF缓存区，客户端状态中的输入缓冲区。

1.1 SDS的定义

struct sdshdr{
    // buf数组中已使用的字节数，等于SDS所保存字符串的长度。
    int len;
    // buf数组中未使用的字节数
    int free;
    // 字节数组，用于保存字符串
    char buf[];
}

SDS遵循C字符串以空字符结尾的惯例，保存空字符串的1字节空间不计算在SDS的len属性里面，并为空字符分配额外1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，所以这个空字符对于SDS的使用者来说是透明的。

遵循空字符结尾这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数。

图片说明
如图展示了SDS的数据结构，5字节未使用空间，已使用5字节，buf存储了字符串值，最后一个字节保存了空字符'\0'。这里要注意的是，free和len的计算不涉及空字符。

1.2 SDS与C字符串的区别

常数复杂度获取字符串长度。

由于C字符串不会记录自身长度，因此只能遍历，直到遇到结尾的空字符为止,时间复杂度为O(N)。而SDS在len属性中记录了SDS本身的长度，只要访问SDS的len属性即可，所以时间复杂度为O(1)。
杜绝缓冲区溢出

由于C字符串未记录自身长度，容易导致缓冲区溢出。在执行字符串拼接时，如果没有足够的空间，并且相邻内存地址被其他字符串占用时，字符串的数据将溢出，且容易意外修改相邻的字符串内容。相比而言，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：API先判断SDS的空间是否满足修改所需的要求，如果不满足则将空间扩展至执行修改所需的大小。
减少修改字符串时带来的内存重分配次数

因为C字符串并不记录自身长度，并且需要额外一个字符空间保存空字符，因此每次增长或缩短字符串时，就要对其进行一次内存重分配操作。增长字符串时要看空间是否够用，否则会有缓冲区溢出；缩短字符串要释放不用的空间，否则会有内存泄漏。

通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

空间预分配用于优化SDS字符串增长操作。在扩展SDS空间前，SDS的API会先检查未使用空间够不够，如果不够，则进行空间预分配。此时，程序不仅会为SDS分配修改所必须要的空间，还为其分配额外未使用的空间。
- 修改后的SDS<1MB，程序分配和len属性同样大小的未使用空间，此时SDS的len与free大小相等。比如修改后实际存储字符串的空间变为13字节，那么len=13，free=13，buf数组整体的长度=13+13+1（额外1字节保存空字符）。
- 修改后SDS>=1MB。程序会分配1MB的未使用空间。比如修改后实际存储字符串的空间变为2MB，那么len=2M，free=1MB，buf数组整体的长度=2MB+1MB+1byte。
通过空间的预分配，将连续增长N次字符串需要的内存分配次数从一定需要N次变为最多N次。

惰性空间释放

惰性空间释放用于优化SDS字符串缩短操作。当SDS的API需要缩短保存的字符串时，程序并不立即回收这部分内存，而是使用free属性将字节的数量记录，等待使用。与此同时，SDS提供了相关API，在有需要时，真正释放未使用空间，不需要担心惰性空间造成的内存浪费。
二进制安全

C字符串的字符必须符合某种编码，并且中间不能有空字符，否则读取时会被误以为是字符串结尾。这些限制使得C字符串只能存文本，不能存图片，音频，视频，压缩文件等二进制数据。为确保Redis对不同使用场景的支持，SDS的API都是二进制安全的，也就是所有SDS API都会以二进制的方式存取buf中的数据，数据的写入和读出都是一个样的。由于SDS读取时并不是依靠空字符来判断结束的，而是len属性，所以是二进制安全的。
兼容部分C字符串函数

通过遵循C字符串以空字符结尾的惯例，SDS可以在有需要时重用<string.h>函数库，避免不必要代码重复。

2.链表

当一个列表键包含了数量比较多的元素，或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

链表被广泛用于实现Redis的各种功能，比如列表键、发布和订阅、慢查询、监视器等。

2.1 链表和链表结点的实现

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

多个listNode可以通过prev和next指针组成双端链表。Redis的链表实现是双端链表。

图片说明

使用adlist.h/list来持有，操作链表：

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;

下图是由一个list结构和三个listNode结构组成的链表。

图片说明

表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。所以Redis的链表实现是无环链表。

3.字典

字典又称符号表，关联数组或映射，用于保存键值对的抽象数据结构。当一个哈希键包含的键值对比较多时，或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。

3.1 字典的实现

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，每个哈希表节点保存了字典中的一个键值对。

哈希表

使用dict.h/dictht结构定义：

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

数组中的每个元素都是指向dict.h/dictht的结构，每个dictEntry结构保存着一个键值对。

哈希表节点

typedef struct dictEntry{
    //键
    void *key;
    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

键值对的值可以是一个指针，或一个uint64_t整数，或一个int64_t整数。next是指向另一个哈希表节点的指针，可将多个哈希值相同的键值对连接在一起，以此来解决冲突。

如图，表示的是两个哈希值相同的节点，通过指针连接在一起。

字典

Redis中的字典由dict.h/dict结构表示：

typedef struct dict{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash索引
    //当rehash不在进行时，值为-1
    int rehashidx;
} dict;

type和privdata属性是针对不同类型的键值对，为创建多态字典而设置的：

type属性是一个指向dictType的结构指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis为用途不同的字典设置不同的类型特定函数。
```
typedef struct dictType{
    //计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    //复制键的函数
    void *(*keyDup)(void *privdata,const void *key)
    ...
}
```
privdata属性保存了需要传给那些类型特定函数的可选参数。
ht属性是一个包含两个项的数组，每项都是一个哈希表，一般情况下，字典只使用ht[0]哈希表，而ht[1]只会在对ht[0]进行rehash时使用。
rehashidx记录了rehash目前的进度，初始为-1。

3.2 哈希算法

Redis计算哈希值方法： hash = dict->type->hashFunction(key);

计算索引值的方法：index = hash & dict->ht[x].sizemask;

3.3 解决键冲突

当有两个或以上的键被分配到哈希表数组的同个索引上，那么就发生了冲突。Redis使用链地址法来解决键冲突，被分配到同一个索引上的多个节点使用单向链表连接。为了提高速度，总是将新节点添加到链表的表头位置。

3.4 rehash

为了让哈希表的负载因子维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行响应的扩容或缩容。扩容和缩容哈希表的工作通过执行rehash（重新散列）操作来完成

Redis中重新散列的步骤如下：

为字典ht[1]哈希表分配空间，大小取决于要执行的操作，以及ht[0]当前包含键值对的数量。(即ht[0].used属性的值)。
将保存在ht[0]中的所有键值对rehash到ht[1]上面
当ht[0]的所有键值对都迁移完毕后，释放ht[0]，将ht[1]设置为h[0]，并在ht[1]上新建一个空的哈希表，为下次rehash准备。

扩容与缩容的场景

扩容操作场景：

服务器目前没有在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子>=1。
服务器正在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子>=5。

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

为什么根据BGSAVE命令或BGREWRITEAOF命令来判断是否扩展？

因为执行这些命令时，Redis需要创建当前服务器进程的子进程，而大多数操作系统采用写时复制技术来优化子进程使用效率，此时提高负载因子，可以尽量避免子进程对哈希表扩展，避免不必要的内存写入操作，节约内存。

缩容操作场景：

负载因子<0.1时，自动对哈希表执行收缩操作。

3.5 渐进式rehash

rehash时会将ht[0]中所有的键值对rehash到ht[1]，如果键值对很多并且一次性操作的话，容易导致服务器在一段时间内停止服务。为避免这种情况，Redis采用渐进式rehash，将ht[0]中的键值对分多次，慢慢的rehash到ht[1]之中。

渐进式rehash的步骤：

为ht[1]分配空间，让字典同时持有两个哈希表。
在字典中维持一个索引计数器变量rehashidx，将其设置为0，表示rehash正式开始。
在rehash进行期间，每次对字典进行添加，删除，查找或更新操作时，程序除了执行指定的操作外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成后，将rehashidx++。
某个时刻，ht[0]中的所有键值对都被rehash至ht[1]，此时设置rehashidx=-1时，表示rehash操作已经完成。

渐进式rehash的好处在于采用了分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、更新和查找操作上，从而避免集中式rehash带来庞大计算量。

4.跳跃表

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

如果一个有序集合中包含的元素数量比较多，又或者有序集合中元素的成员是较长的字符串，Redis就会使用跳跃表来作为有序集合键的底层实现。Redis只有在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中作为内部数据结构。

4.1 跳跃表的实现

Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个数据结构定义。

typedef struct zskiplist{
    //表头节点和表尾节点
    structz zskiplistNode *header,* tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点的层数
    int level;
} zskiplist;

跳跃表由zskiplist组织，通过多个跳跃表节点zskiplistNode组成一个跳跃表。值得注意的是，记录level时，表头节点的层高不会记录在内。

跳跃表节点

typedef strct zskiplistNode{
    //后退指针
    struct zskiplistNode *backward;
    //分值
    double score;
    //成员对象
    robj *obj;
    //层
    struct zskiplistlevel{
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    }level[];
} zskiplistNode;

层——level[]

跳跃表的每个节点都会包含多个层，每次创建一个新跳跃表时，都会根据幂次定律，随机生成一个1~32之间的数作为level数组的大小。每个层都会包含前进指针和跨度。

前进指针（forword）用于访问下一个节点。跨度表示两个节点之间的距离，指向NULL的所有前进指针的跨度为0。跨度用于计算排位，访问某一结点的经过的跨度之和就是当前节点的排位。
后退指针——backward

用于从表尾向表头方向访问节点，前进指针可以一次跳过多个节点，后退指针每次只能后退至前一个节点，因为每个节点只有一个后退指针。
分值——score

分值是一个double类型的浮点数，跳跃表中节点都按照分值排序。
成员对象——obj

节点的成员对象是一个指针，指向字符串SDS对象。一个跳跃表中，对象必须是唯一的，但分值可以相同。相同时按对象字典序来排序。

5.整数集合

当一个集合只包含整数元素，并且元素不多时，Redis就会使用整数集合作为集合键的底层实现。

5.1 整数集合的实现

整数集合是Redis中用于保存整数值的集合抽象数据结构，可以保证集合有序不重复。每个intset.h/intset结构来表示一个整数集合：

typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数据项，各个项在数组中按值的大小从小到大排列，并且数组中不包含任何重复项。

length属性记录了整数集合包含的元素数量，即contents数组的长度。contents存储元素的真实类型取决于encoding，比如encoding==INT_ENC_INT16时，contents数组中每个向都是int16_t类型的整数。encoding可以为int16_t,int32_t或int64_t。