Redis数据结构

发表于 | 分类于 ， | 游览 次

1. 简单动态字符串(SDS)

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

在Redis的数据库里面,包含字符串值得键值对在底层都是由SDS实现的。

1.1 SDS的定义

每个sds.h/sdshdr结构表示一个SDS值：

1
2
3
4
5
6
7
8
9
struct sdshdr{
    //记录buf数组中已使用字节的数量
    //等于SDS所保存字符串的长度
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组,用于保存字符串
    char buf[];
};

SDS遵循C字符串以空字符结尾的管理，保存空字符的1空间不计算在SDS的len属性里面，
并且为空字符分配而额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的。

1.2 简单比较一下C字符串：

常数复杂度获取字符串长度
​ 可以直接通过len属性获取SDS本身的长度，时间复杂对是O（1）。

杜绝缓冲区溢出

C字符串不记录自己长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）
当SDS API需要对SDS进行修改时，API会先检查SDS的空间爱你是否满足修改所需的要求，
如果不满足的话，API会自动将SDS的控件扩展至执行修改所需的大小，
然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出缓冲区溢出问题。

减少修改字符串时带来的内存重分配次数

C字符串在每次增长那个或者缩短一个C字符串，程序都总要对保存这个C字符串的数组进行一次内存重新分配。
如果频繁进行内存重分配，可能会对性能造成影响。

SDS实现了 空间预分配 和 惰性空间释放 两种优化策略。

       1. 空间预分配

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

       额外分配的未使用空间数量由以下公式决定：

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

在扩展SDS空间之前，SDS API会先检查为食欲on个空间是否足够，如果足够的话，API就会直接使用
未使用控件，而无须执行内存重分配，所以连续增长N次字符串所需的内存重分配次数从必定
N次降低为最多N次。

       2. 惰性空间释放

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

通过使用二进制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不仅可以保存文本数据， 还可以保存任意格式的二进制数据。

兼容部分 C 字符串函数

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

2. 链表

链表提供了高效的节点重排能力，以及顺序型的结点访问形式，并且可以通过增删节点来灵活地
调整链表的长度。

2.1 链表和链表节点的实现

每个链表节点使用一个adlist.h/listNode结构来表示：

1
2
3
4
5
6
7
8
typedef strtct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
}listNode;

多个listNode可以通过prev和next指针组成双端链表，如下图

还有一个list结构adlist.h/list来持有链表，操作起来更方便：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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结构：

Redis的链表实现的特性可以总结如下:

  • 双端：链表节点带有prev和next指针，获取某个节点的前置和后置节点的复杂度都是O（1）。
  • 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。
  • 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。
  • 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行技术，程序获取链表中节点数量的复杂对为O（1）。
  • 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

3. 字典

字典，又称为符号表（symbol table）、关联数组（associativce array）或映射（map），
是一种用于保存键值对（key-value pair）的抽象数据结构。

3.1 字典的实现

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

3.1.1 哈希表

Redis字典所使用的哈希表由dict.h/dictht结构定义:

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

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



3.1.2 字典结构

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

1
2
3
4
5
6
7
8
9
10
11
typedef struct *type {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash 索引
    //当rehash不在进行时，值为-1
    in trehashidx; /*rehashing not in progress if rehashidx == -1*/
}dict;

普通状态下的字典

3.2 哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先更具键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

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

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

3.3 解决键冲突

当有两个或以上数量的键被分配到哈希表数组的同一个索引上面时，我们称这些键发生了冲突（collision）。

Redis的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个 next 指针，多个哈希节点可以用next指针构成一个单向链表。
被分配到同一个索引上的多个节点可以用这个单向链表链接起来，折旧解决了键冲突的问题。

程序总是将新节点添加到链表的表头位置（复杂度为O(1)），排在其它已有节点的前面。

3.4 rehash

扩展和收缩哈希表的工作可以通过rehash（重新散列）操作完成，Redis对字典的哈希表执行 rehash 的步骤如下：

1. 为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量（也就是 ht[0].used 属性的值）

  • 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于 ht[0].used * 2的 2 的 n 次方。
  • 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于 ht[0].used 的 2 的 n 次方。

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

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

3.5 哈希表的扩展和收缩

先说一下哈希表的负载因子：
load_factor = ht[0].used / ht[0].size

扩展的条件：

  1. 服务器目前没有正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，哈比表的负载因子大于等于 1.
  2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，哈希表的负载因子大于等于 5.

收缩操作的条件：
哈希表的负载因子小于0.1.

4. 跳跃表

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

跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

4.1 跳跃表的实现

Redis 的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义，其中 zskipistNode 结构用于表示跳跃表节点，而 zskiplist 结构则用于保存跳跃表节点的相关信息，比如节点的数量，以及指向及表头节点和表尾节点的指针等等。

跳跃表结构

zskiplist 比较简单，用于存放 zskiplistNode，属性值也比较易懂。

zskiplistNode 的结构：

  • 层（level）：节点中用L1、L2、L3等字样标记节点的各个层，每个层都带有两个属性：前进指针和跨度。
  • 后退（backward）指针：节点中用BW字样标记节点的后腿指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
  • 分值（score）：各个节点中的 1.0、2.0 和 3.0 都是节点所保存的分支。在跳跃表中，节点按各自所保存的分值从最小到大排列。
  • 成员对象（obj）：各个节点中的 o1、o2 和 o3 以及所保存的成员对象。
4.1.1 跳跃表节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode {
    //层
    struct zskiplistLevel {
        //前进指针
        struct zskiplistNode * forward;
        //跨度
        unsigned int span;
    } level[];
    //后退指针
    struct zskiplistNode *backward;
    //分数
    double score;
    //成员对象
    robj *obj;
} zskiplistNode;

有以下属性：

  • 层：跳跃表节点的 level 数字可以包含多个元素，程序可以通过这些层来加快访问其它节点的速度。
    level 数组大小就是层的“高度”。
  • 前进指针：每个层都有一个指向表尾的前进指针（level[i].forward 属性），用于从表头向表尾访问节点，可以一次跳过多个节点。
  • 跨度：层的跨度（level[i].span 属性）用于记录两个节点之间的距离，跨度实际上是用来计算排位(rank)的。
  • 后退指针：节点的后腿指针（backward 属性）用于从表尾向表头方向访问节点，每个节点只有一个后退指针，所以每次只能后退至前一个节点。
  • 分值和成员：节点的分值（score 属性）是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大排序。
    节点的成员对象（obj 对象）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个 SDS 值。

4.1.2 跳跃表

通过一个zskiplist结构来持有节点，程序可以更方便地对整个跳跃表进行处理。

1
2
3
4
5
6
7
8
typedef struct zskiplist {
    //表头节点和表尾节点
    struct skiplistNode *header, *tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点的层数（不包括表头节点）
    int level;
}zskiplist;

5. 整数集合

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

5.1 整数集合的实现

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

每个 intset.h/intset 结构表示一个整数集合：

1
2
3
4
5
6
7
8
typedef struct intset {
    //编码方式
    unint32_t encoding;
    //集合包含的元素数量
    unint32_t length;
    //保存元素的数组
    int8_t contents[];
}intset;

5.2 升级

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

升级整数集合并添加新元素共分为三步进行：

  1. 根据新元素的类型，扩展整数集合底层数组的控件大小，并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置正确的为上，而且在放置元素的工程中，需要继续维持底层数组的有序性质不变。
  3. 将新元素添加到底层数组里面。

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

6. 压缩列表

压缩列表（ziplist）是 列表键 和 哈希键 的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。

6.1 压缩列表的构成

压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。

一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配， 或者计算 zlend的位置时使用。
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节： 通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址。
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量： 当这个属性的值小于 UINT16_MAX （65535）时， 这个属性的值就是压缩列表包含节点的数量； 当这个值等于 UINT16_MAX 时， 节点的真实数量需要遍历整个压缩列表才能计算得出。
entryX 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

6.2 压缩列表节点的构成

每个压缩列表节点（上面提到的entryX）可以保存一个字节数组或者一个整数值。

压缩列表节点的各个组成部分

  1. previous_entry_legth 的作用：
    节点的 previous_entry_lenght 属性记录了前一个节点的长度，程序通过当前节点的起始地址计算出前一个节点的起始地址： p = c - current_entry_length;
  2. encoding:
    该属性记录了节点的content属性所保存数据的类型以及长度
  3. content:
    该属性保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。

6.3 连锁更新

如果在压缩列表中插入一个新的节点，长度超出下一节点所保存的 previous_entry_length，这时就需要更新下一节点的 previous_entry_length。

同样，有可能导致第二个节点的空间变大，第三个节点也需要更新保存着第二个节点的 previous_entry_length，以此类推，导致连锁更新。

在删除节点的时候，也有可能导致 previous_entry_length 的更新，也是会引起连锁更新的。

因为连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂对为O（N），
所以连锁更新的最坏复杂度为O（N的平方）

学习参看地址