redis 数据结构（一）

Redis 为什么那么快

redis是一种内存数据库，所有的操作都是在内存中进行的，还有一种重要原因是：它的数据结构的设计对数据进行增删查改操作很高效。

redis的数据结构是什么

redis数据结构是对redis键值对值的数据类型的底层的实现，注意不是String、List、Hash、Set、Zset、BitMap、HyperLogLog、GEO、Stream这些数据类型，而是对这些类型的底层实现。

redis数据结构与数据类型的关系

 从上图我们也知道数据结构主要有：：SDS、双向链表、压缩列表、哈希表、跳表、整数集合、quicklist、listpack。但是，双向链表、压缩列表已经使用quicklist、listpack替代了。

键值对数据库是怎么实现的？

在讲数据结构之前，我们先了解一下redis的键值对（key-value）是怎么实现的。

redis键值对的key是一个字符串对象，而value可以是redis数据类型中的任何一个对象。那这键值对是怎么保存的呢？

Redis 是使用了一个「哈希表」保存所有键值对，哈希表的最大好处就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对。哈希表其实就是一个数组，数组中的元素叫做哈希桶

那么哈希桶又是怎么保存键值对数据的呢？

哈希桶存放的是指向键值对数据的指针（dictEntry*），这样通过指针就能找到键值对数据，然后因为键值对的值可以保存字符串对象和集合数据类型的对象，所以键值对的数据结构中并不是直接保存值本身，而是保存了 void * key 和 void * value 指针，分别指向了实际的键对象和值对象，这样一来，即使值是集合数据，也可以通过 void * value 指针找到。

 上图说明：

redisDb 结构，表示 Redis 数据库的结构，结构体里存放了指向了 dict 结构的指针

dict 结构，结构体里存放了 2 个哈希表，正常情况下都是用「哈希表1」，「哈希表2」只有在 rehash 的时候才用，具体什么是 rehash，我在本文的哈希表数据结构会讲

ditctht 结构，表示哈希表的结构，结构里存放了哈希表数组，数组中的每个元素都是指向一个哈希表节点结构（dictEntry）的指针

dictEntry 结构，表示哈希表节点的结构，结构里存放了 void * key 和 void * value 指针， *key 指向的是 String 对象，而 *value 则可以指向 String 对象，也可以指向集合类型的对象，比如 List 对象、Hash 对象、Set 对象和 Zset 对象

 注意，void * key 和 void * value 指针指向的是 Redis 对象，Redis 中的每个对象都由 redisObject 结构表示，如下：

  上图说明：

• type，标识该对象是什么类型的对象（String 对象、 List 对象、Hash 对象、Set 对象和 Zset 对象）；

• encoding，标识该对象使用了哪种底层的数据结构；

• ptr，指向底层数据结构的指针。

到这里，我们大概知道edis的键值对（key-value）的大体实现，那么下面我们就开始聊聊这些底层实现的数据结构。

SDS

字符串在 Redis 中是很常用的，键值对中的键是字符串类型，值有时也是字符串类型。

Redis 是用 C 语言实现的，但是它没有直接使用 C 语言的 char* 字符数组来实现字符串，而是自己封装了一个名为简单动态字符串（simple dynamic string，SDS） 的数据结构来表示字符串，也就是 Redis 的 String 数据类型的底层数据结构是 SDS。

SDS 的数据结构：

 SDS 的数据结构说明：

len：记录了字符串长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。

alloc：分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS  的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出的问题。

flags：用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在说明区别之处。

buf[]：字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。
 

SDS与C语言中字符串的区别

1.获取字符串长度

因为C语言字符串本身不记录自身的长度，若要获取其长度，则需要遍历字符串才能得到，时间复杂度为O(N)；而SDS在其自身的数据结构中记录了以使用字符串空间（也就是len），所以获取一个字符串长度的时间复杂度为O(1)

2.防止缓冲区的溢出

C 语言的字符串标准库提供的字符串操作函数，大多数（比如 strcat 追加字符串函数）都是不安全的，因为这些函数把缓冲区大小是否满足操作需求的工作交由开发者来保证，程序内部并不会判断缓冲区大小是否足够用，当发生了缓冲区溢出就有可能造成程序异常结束；SDS由于其自身记录了长度，在每次修改SDS时：（1）API会检查SDS的空间是否足够；（2）若不足，则API会自动将SDS的空间扩展至所需的大小，再进行接下来的操作。由此，SDS可以避免缓冲区的溢出。

3.二进制安全

C 语言的字符串需要以 “\0” 字符来标识字符串结尾的。而SDS不需要，它是有len 成员变量来记录长度，所以它存储任意格式的二进制数据，就算这个数据中间有“\0” 也不会因为遇到“\0” 结束。但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 “\0” 字符。

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

在一般的程序中，每次修改字符串都执行一次内存重分配，这是可以接受的；但是redis作为数据库，经常用于速度要求严苛、数据要求频繁修改的场合，每次修改字符串所需要内存重分配，可能会对性能造成影响。通过使用未使用的空间（alloc），SDS实现了空间预分配与惰性空间释放两种优化策略。

5. 节省内存空间

SDS 结构中有个 flags 成员变量，表示的是 SDS 类型。分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。

这 5 种类型的主要区别就在于，它们数据结构中的 len 和 alloc 成员变量的数据类型不同。

比如 sdshdr16 和 sdshdr32 这两个类型，它们的定义分别如下：

struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len;uint16_t alloc; unsigned char flags; char buf[];
};struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len;uint32_t alloc; unsigned char flags;char buf[];
};

可以看到：

• sdshdr16 类型的 len 和 alloc 的数据类型都是 uint16_t，表示字符数组长度和分配空间大小不能超过 2 的 16 次方。

• sdshdr32 则都是 uint32_t，表示表示字符数组长度和分配空间大小不能超过 2 的 32 次方。

之所以 SDS 设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。比如，在保存小字符串时，结构头占用空间也比较少。

除了设计不同类型的结构体，Redis 在编程上还使用了专门的编译优化来节省内存空间，即在 struct 声明了 __attribute__ ((packed)) ，它的作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。

比如，sdshdr16 类型的 SDS，默认情况下，编译器会按照 16 字节对齐的方式给变量分配内存，这意味着，即使一个变量的大小不到 16 个字节，编译器也会给它分配 16 个字节。

举个例子，假设下面这个结构体，它有两个成员变量，类型分别是 char 和 int，如下所示：

#include <stdio.h>struct test1 {char a;int b;} test1;int main() {printf("%lu\n", sizeof(test1));return 0;
}

大家猜猜这个结构体大小是多少？我先直接说答案，这个结构体大小计算出来是 8。

这是因为默认情况下，编译器是使用「字节对齐」的方式分配内存，虽然 char 类型只占一个字节，但是由于成员变量里有 int 类型，它占用了 4 个字节，所以在成员变量为 char 类型分配内存时，会分配 4 个字节，其中这多余的 3 个字节是为了字节对齐而分配的，相当于有 3 个字节被浪费掉了。

如果不想编译器使用字节对齐的方式进行分配内存，可以采用了 __attribute__ ((packed)) 属性定义结构体，这样一来，结构体实际占用多少内存空间，编译器就分配多少空间。

比如，我用 __attribute__ ((packed)) 属性定义下面的结构体 ，同样包含 char 和 int 两个类型的成员变量，代码如下所示：

#include <stdio.h>struct __attribute__((packed)) test2  {char a;int b;} test2;int main() {printf("%lu\n", sizeof(test2));return 0;
}

这时打印的结果是 5（1 个字节 char  + 4 字节 int）。

可以看得出，这是按照实际占用字节数进行分配内存的，这样可以节省内存空间。
 

链表

Redis 的 List 对象的底层实现之一就是链表。链表节点的数据结构如下：

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

从定义可以看出，这是一个双向链表：

 但是，Redis 在 listNode 结构体基础上又封装了 list 这个数据结构，如下：

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

list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数。

举个例子，下面是由 list 结构和 3 个 listNode 结构组成的链表。

 

链表的优势与缺陷

Redis 的链表实现优点如下：

listNode 链表节点的结构里带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；

list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)；

list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需O(1)；

listNode 链表节使用 void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；

链表的缺陷也是有的：

链表每个节点之间的内存都是不连续的，意味着无法很好利用 CPU 缓存。能很好利用 CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用 CPU 缓存来加速访问。

还有一点，保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。
 

然后在Redis 5.0 设计了新的数据结构 listpack来替代List 对象的底层数据结构。

压缩列表

压缩列表的最大特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。但是，压缩列表的缺陷也是有的：

不能保存过多的元素，否则查询效率就会降低；

新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题。

因此，Redis 对象（List 对象、Hash 对象、Zset 对象）包含的元素数量较少，或者元素值不大的情况才会使用压缩列表作为底层数据结构。

压缩列表结构设计

压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。

 压缩列表在表头有三个字段：

zlbytes，记录整个压缩列表占用对内存字节数；

zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；

zllen，记录压缩列表包含的节点数量；

zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）。

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。

另外，压缩列表节点（entry）的构成如下：

 压缩列表节点包含三部分内容：

prevlen，记录了「前一个节点」的长度；

encoding，记录了当前节点实际数据的类型以及长度；

data，记录了当前节点的实际数据；

当我们往压缩列表中插入数据时，压缩列表就会根据数据是字符串还是整数，以及数据的大小，会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息，这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是 Redis 为了节省内存而采用的。

分别说下，prevlen 和 encoding 是如何根据数据的大小和类型来进行不同的空间大小分配。

压缩列表里的每个节点中的  prevlen 属性都记录了「前一个节点的长度」，而且 prevlen 属性的空间大小跟前一个节点长度值有关，比如：

如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；

如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

encoding 属性的空间大小跟数据是字符串还是整数，以及字符串的长度有关：

如果当前节点的数据是整数，则 encoding 会使用 1 字节的空间进行编码。

如果当前节点的数据是字符串，根据字符串的长度大小，encoding 会使用 1 字节/2字节/5字节的空间进行编码。

连锁更新

压缩列表除了查找复杂度高的问题，还有一个问题。

压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

前面提到，压缩列表节点的 prevlen 属性会根据前一个节点的长度进行不同的空间大小分配：

如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；

如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；

现在假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，如下图：

 

因为这些节点长度值小于 254 字节，所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。

这时，如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，即新节点将成为 e1 的前置节点，如下图：

 

因为 e1 节点的 prevlen 属性只有 1 个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作，并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。

多米诺牌的效应就此开始。

 e1 原本的长度在 250～253 之间，因为刚才的扩展空间，此时 e1 的长度就大于等于 254 了，因此原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。

正如扩展 e1 引发了对 e2 扩展一样，扩展 e2 也会引发对 e3 的扩展，而扩展 e3 又会引发对 e4 的扩展…. 一直持续到结尾。

这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」，就像多米诺牌的效应一样，第一张牌倒下了，推动了第二张牌倒下；第二张牌倒下，又推动了第三张牌倒下….，

压缩列表的缺陷

空间扩展操作也就是重新分配内存，因此连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能。

所以说，虽然压缩列表紧凑型的内存布局能节省内存开销，但是如果保存的元素数量增加了，或是元素变大了，会导致内存重新分配，最糟糕的是会有「连锁更新」的问题。

因此，压缩列表只会用于保存的节点数量不多的场景，只要节点数量足够小，即使发生连锁更新，也是能接受的。

虽说如此，Redis 针对压缩列表在设计上的不足，在后来的版本中，新增设计了两种数据结构：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。这两种数据结构的设计目标，就是尽可能地保持压缩列表节省内存的优势，同时解决压缩列表的「连锁更新」的问题。

哈希表

redis中哈希键的底层实现之一就是字典，实际与C++语言中的哈希表一样，都是一个键与一个值进行关联，并称为键值对。由于redis使用的C语言没有这种数据结构，所以redis自己构建了字典实现。在我看来，在redis中的字典与哈希表的关系就是，字典就是对哈希表的结构的一个封装而已，只是为了方便使用。下面会讲到二者的关系。

优缺点

哈希表优点在于，它能以 O(1) 的复杂度快速查询数据。怎么做到的呢？将 key 通过 Hash 函数的计算，就能定位数据在表中的位置，因为哈希表实际上是数组，所以可以通过索引值快速查询到数据。

但是存在的风险也是有，在哈希表大小固定的情况下，随着数据不断增多，那么哈希冲突的可能性也会越高。Redis 采用了「链式哈希」来解决哈希冲突。

哈希表结构设计

字典的定义：

typedef struct dict{//类型特定的函数dictType * type;//私有数据void * private;//哈希表dictht ht[2];//rehash的索引int rehashidx;
} dict;

哈希表的数据结构如下：

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

其中，哈希表节点的数据结构如下：

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

dictEntry 结构里不仅包含指向键和值的指针，还包含了指向下一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对链接起来，以此来解决哈希冲突的问题，这就是链式哈希。

另外，这里还跟你提一下，dictEntry 结构里键值对中的值是一个「联合体 v」定义的，因此，键值对中的值可以是一个指向实际值的指针，或者是一个无符号的 64 位整数或有符号的 64 位整数或double 类的值。这么做的好处是可以节省内存空间，因为当「值」是整数或浮点数时，就可以将值的数据内嵌在 dictEntry 结构里，无需再用一个指针指向实际的值，从而节省了内存空间。

哈希表的结构图

 关于什么是哈希冲突和解决方案 可以查看我之前的文章解决哈希冲突的方案，不过，链式哈希局限性也很明显，随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，毕竟链表的查询的时间复杂度是 O(n)。要想解决这一问题，就需要进行 rehash，也就是对哈希表的大小进行扩展。

哈希表扩容（rehash）

1.  为字典的 ht[1] 哈希表分配空间（ht[1] 大小为 ht[0] 的 2^n）；

2. 将 ht[0] 中的键值对reahash到 ht[1] 中；

3. 当 ht[0] 中的所有数据拷贝到 ht[1] 后，释放 ht[0];

4. 将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次rehash做准备

为了方便你理解，我把 rehash 这三个过程画在了下面这张图：

 这个过程看起来简单，但是其实第二步很有问题，如果「哈希表 1 」的数据量非常大，那么在迁移至「哈希表 2 」的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求

渐进式rehash

为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。

渐进式 rehash 步骤如下：

1. 为ht[1]分配空间，让字典同时持有 ht[0] 与 ht[1] ;

2. 在字典中维持一个索引计数器变量rehashidx，并将其设置为0，表示rehash开始；

3. rehash期间，每次的修改，程序除了指定的操作外，还会将 ht[0] 在rehashidx上的所有键值rehash到 ht[1]，rehash完成后，rehashidx加一；

4. 当 ht[0] 中所有的数据都rehash到 ht[1] 时，rehashidx设置为-1，rehash完成

这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。

在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。

比如，查找一个 key 的值的话，先会在「哈希表 1」 里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。

另外，在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」 则不再进行任何添加操作，这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表。

触发 rehash 操作的条件：

当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。

当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。

负载因子就是：

 由于篇章过于庞大，就先写到这里，至于整数集合，跳表，quicklist，listpack在<<redis 数据结构（二）>>再分析