这篇带你彻底拿捏Redis数据结构 ！

Redis 为什么那么快除了它是内存数据库使得所有的操作都在内存上进行之外还有一个重要因素它实现的数据结构使得我们对数据进行增删查改操作时Redis 能高效的处理。因此这次我们就来好好聊一下 Redis 数据结构这个在面试中太常问了。注意Redis 数据结构并不是指 tring字符串、List列表、Hash哈希、Set集合和 Zset有序集合因为这些是 Redis 键值对中值的数据类型并不是数据结构。这些数据类型的底层实现的方式才是数据结构。Redis 底层的数据结构一共有 6 种如下图右边部分它和数据类型对应关系也如下图可以看到有些数据类型可以由两种 数据结构实现比如List 数据类型底层数据结构由「双向链表」或「压缩表列表」实现Hash 数据类型底层数据结构由「压缩列表」或「哈希表」实现Set 数据类型底层数据结构由「哈希表」或「整数集合」实现Zset 数据类型底层数据结构由「压缩列表」或「跳表」实现好了不多 BB 了直接发车SDS字符串在 Redis 中是很常用的键值对中的键是字符串值有时也是字符串。Redis 是用 C 语言实现的但是它没有直接使用 C 语言的 char* 字符数组来实现字符串而是自己封装了一个名为简单动态字符串simple dynamic stringSDS 的数据结构来表示字符串也就是 Redis 的 String 数据类型的底层数据结构是 SDS。既然 Redis 设计了 SDS 结构来表示字符串肯定是 C 语言的 char* 字符数组存在一些缺陷。要了解这一点得先来看看 char* 字符数组的结构。C 语言字符串的缺陷C 语言的字符串其实就是一个字符数组即数组中每个元素是字符串中的一个字符。比如下图就是字符串“xiaolin”的 char* 字符数组的结构没学过 C 语言的同学可能会好奇为什么最后一个字符是“\0”在 C 语言里对字符串操作时char * 指针只是指向字符数组的起始位置而字符数组的结尾位置就用“\0”表示意思是指字符串的结束。因此C 语言标准库中字符串的操作函数就通过判断字符是不是“\0”如果不是说明字符串还没结束可以继续操作如果是则说明字符串结束了停止操作。举个例子C 语言获取字符串长度的函数 strlen就是通过字符数组中的每一个字符并进行计数等遇到字符为“\0”后就会停止遍历然后返回已经统计到的字符个数即为字符串长度。下图显示了 strlen 函数的执行流程很明显C 语言获取字符串长度操作的时间复杂度是 ON这是一个可以改进的地方C 语言的字符串用 “\0” 字符作为结尾标记有个缺陷。假设有个字符串中有个 “\0” 字符这时在操作这个字符串时就会提早结束比如 “xiao\0lin” 字符串计算字符串长度的时候则会是 4如下图还有除了字符串中不能 “\0” 字符外用 char* 字符串中的字符必须符合某种编码比如ASCII。这些限制使得 C 语言的字符串只能保存文本数据不能保存像图片、音频、视频文化这样的二进制数据这也是一个可以改进的地方C 语言标准库中字符串的操作函数是很不安全的对程序员很不友好稍微一不注意就会导致缓冲区溢出。举个例子strcat 函数是可以将两个字符串拼接在一起。c //将 src 字符串拼接到 dest 字符串后面 char *strcat(char *dest, const char* src);C 语言的字符串是不会记录自身的缓冲区大小的所以 strcat 函数假定程序员在执行这个函数时已经为 dest 分配了足够多的内存可以容纳 src 字符串中的所有内容而一旦这个假定不成立就会发生缓冲区溢出将可能会造成程序运行终止这是一个可以改进的地方。而且strcat 函数和 strlen 函数类似时间复杂度也很高也都需要先通过遍历字符串才能得到目标字符串的末尾。然后对于 strcat 函数来说还要再遍历源字符串才能完成追加对字符串的操作效率不高。好了 通过以上的分析我们可以得知 C 语言的字符串 不足之处以及可以改进的地方获取字符串长度的时间复杂度为 ON字符串的结尾是以 “\0” 字符标识而且字符必须符合某种编码比如ASCII只能保存文本数据不能保存二进制数据字符串操作函数不高效且不安全比如可能会发生缓冲区溢出从而造成程序运行终止Redis 实现的 SDS 的结构就把上面这些问题解决了接下来我们一起看看 Redis 是如何解决的。SDS 结构设计下图就是 Redis 5.0 的 SDS 的数据结构结构中的每个成员变量分别介绍下lenSDS 所保存的字符串长度。这样获取字符串长度的时候只需要返回这个变量值就行时间复杂度只需要 O1。alloc分配给字符数组的空间长度。这样在修改字符串的时候可以通过alloc - len计算 出剩余的空间大小然后用来判断空间是否满足修改需求如果不满足的话就会自动将 SDS 的空间扩展至执行修改所需的大小然后才执行实际的修改操作所以使用 SDS 既不需要手动修改 SDS 的空间大小也不会出现前面所说的缓冲区益处的问题。flagsSDS 类型用来表示不同类型的 SDS。一共设计了 5 种类型分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64后面在说明区别之处。buf[]字节数组用来保存实际数据。不需要用 “\0” 字符来标识字符串结尾了而是直接将其作为二进制数据处理可以用来保存图片等二进制数据。它即可以保存文本数据也可以保存二进制数据所以叫字节数组会更好点。总的来说Redis 的 SDS 结构在原本字符数组之上增加了三个元数据len、alloc、flags用来解决 C 语言字符串的缺陷。O1复杂度获取字符串长度C 语言的字符串长度获取 strlen 函数需要通过遍历的方式来统计字符串长度时间复杂度是 ON。而 Redis 的 SDS 结构因为加入了 len 成员变量那么获取字符串长度的时候直接返回这个变量的值就行所以复杂度只有 O1。二进制安全因为 SDS 不需要用 “\0” 字符来标识字符串结尾了而且 SDS 的 API 都是以处理二进制的方式来处理 SDS 存放在 buf[] 里的数据程序不会对其中的数据做任何限制数据写入的时候时什么样的它被读取时就是什么样的。通过使用二进制安全的 SDS而不是 C 字符串使得 Redis 不仅 可以保存文本数据也可以保存任意格式的二进制数据。不会发生缓冲区溢出C 语言的字符串标准库提供的字符串操作函数大多数比如 strcat 追加字符串函数都是不安全的因为这些函数把缓冲区大小是否满足操作的工作交由开发者来保证程序内部并不会判断缓冲区大小是否足够用当发生了缓冲区溢出就有可能造成程序异常结束。所以Redis 的 SDS 结构里引入了 alloc 和 leb 成员变量这样 SDS API 通过alloc - len计算可以算出剩余可用的空间大小这样在对字符串做修改操作的时候就可以由程序内部判断缓冲区大小是否足够用。而且当判断出缓冲区大小不够用时Redis 会自动将扩大 SDS 的空间大小以满足修改所需的大小。在扩展 SDS 空间之前SDS API 会优先检查未使用空间是否足够如果不够的话API 不仅会为 SDS 分配修改所必须要的空间还会给 SDS 分配额外的「未使用空间」。这样的好处是下次在操作 SDS 时如果 SDS 空间够的话API 就会直接使用「未使用空间」而无须执行内存分配有效的减少内存分配次数。所以使用 SDS 即不需要手动修改 SDS 的空间大小也不会出现缓冲区溢出的问题。节省内存空间SDS 结构中有个 flags 成员变量表示的是 SDS 类型。Redos 一共设计了 5 种类型分别是 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; }这时打印的结果是 51 个字节 char 4 字节 int。可以看得出这是按照实际占用字节数进行分配内存的这样可以节省内存空间。链表除了数组之外相信大家最熟悉的数据结构就是链表了。Redis 的 list 数据类型的底层实现之一就是链表。C 语言本身也是没有链表这个数据结构的所以 Redis 自己设计了一个链表数据结构。链表节点结构设计先来看看链表节点结构的样子typedef struct listNode { //前置节点 struct listNode *prev; //后置节点 struct listNode *next; //节点的值 void *value; } listNode;有前置节点和后置节点可以看的出这个是一个双向链表。链表结构设计不过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 的 list 数据类型在数据量比较少的情况下会采用「压缩列表」作为底层数据结构的实现压缩列表就是由数组实现的下面我们会细说压缩列表。压缩列表压缩列表是 Redis 数据类型为 list 和 hash 的底层实现之一。当一个列表键list只包含少量的列表项并且每个列表项都是小整数值或者长度比较短的字符串那么 Redis 就会使用压缩列表作为列表键list的底层实现。当一个哈希键hash只包含少量键值对并且每个键值对的键和值都是小整数值或者长度比较短的字符串那么 Redis 就会使用压缩列表作为哈希键hash的底层实现。压缩列表结构设计压缩列表是 Redis 为了节约内存而开发的它是由连续内存块组成的顺序型数据结构有点类似于数组。压缩列表在表头有三个字段zlbytes记录整个压缩列表占用对内存字节数zltail记录压缩列表「尾部」节点距离起始地址由多少字节也就是列表尾的偏移量zllen记录压缩列表包含的节点数量zlend标记压缩列表的结束点特殊值 OxFF十进制255。在压缩列表中如果我们要查找定位第一个元素和最后一个元素可以通过表头三个字段的长度直接定位复杂度是 O(1)。而查找其他元素时就没有这么高效了只能逐个查找此时的复杂度就是 O(N) 了。另外压缩列表节点entry的构成如下压缩列表节点包含三部分内容prevlen记录了前一个节点的长度encoding记录了当前节点实际数据的类型以及长度data记录了当前节点的实际数据当我们往压缩列表中插入数据时压缩列表 就会根据数据是字符串还是整数以及它们的大小会在 prevlen 和 encoding 这两个元素里保存不同的信息这种根据数据大小进行对应信息保存的设计思想正是 Redis 为了节省内存而采用的。连锁更新压缩列表除了查找复杂度高的问题压缩列表在插入元素时如果内存空间不够了压缩列表还需要重新分配一块连续的内存空间而这可能会引发连锁更新的问题。压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」而且 prevlen 属性的空间大小跟前一个节点长度值有关比如如果前一个节点的长度小于 254 字节那么 prevlen 属性需要用1 字节的空间来保存这个长度值如果前一个节点的长度大于等于 254 字节那么 prevlen 属性需要用5 字节的空间来保存这个长度值现在假设一个压缩列表中有多个连续的、长度在 250253 之间的节点如下图因为这些节点长度值小于 254 字节所以 prevlen 属性需要用 1 字节的空间来保存这个长度值。这时如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点即新节点将成为 e1 的前置节点如下图因为 e1 节点的 prevlen 属性只有 1 个字节大小无法保存新节点的长度此时就需要对压缩列表的空间重分配操作并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。多米诺牌的效应就此开始。e1 原本的长度在 250253 之间因为刚才的扩展空间此时 e1 的长度就大于等于 254 了因此原本 e2 保存 e1 的 prevlen 属性也必须从 1 字节扩展至 5 字节大小。正如扩展 e1 引发了对 e2 扩展一样扩展 e2 也会引发对 e3 的扩展而扩展 e3 又会引发对 e4 的扩展…. 一直持续到结尾。这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」就像多米诺牌的效应一样第一张牌倒下了推动了第二张牌倒下第二张牌倒下又推动了第三张牌倒下….连锁更新一旦发生就会导致压缩列表 占用的内存空间要多次重新分配这就会直接影响到压缩列表的访问性能。所以说虽然压缩列表紧凑型的内存布局能节省内存开销但是如果保存的元素数量增加了或是元素变大了压缩列表就会面临「连锁更新」的风险。因此压缩列表只会用于保存的节点数量不多的场景只要节点数量足够小即使发生连锁更新也是能接受的。哈希表哈希表是一种保存键值对key-value的数据结构。哈希表中的每一个 key 都是独一无二的程序可以根据 key 查找到与之关联的 value或者通过 key 来更新 value又或者根据 key 来删除整个 key-value等等。在讲压缩列表的时候提到过 Redis 的 hash 数据类型的底层实现之一是压缩列表。hash 数据类型的另外一个底层实现就是哈希表。那 hash 数据类型什么时候会选用哈希表作为底层实现呢当一个哈希键包含的 key-value 比较多或者 key-value 中元素都是比较长多字符串时Redis 就会使用哈希表作为哈希键的底层实现。Hash 表优点在于它能以 O(1) 的复杂度快速查询数据。主要是通过 Hash 函数的计算就能定位数据在表中的位置紧接着可以对数据进行操作这就使得数据操作非常快。但是存在的风险也是有在哈希表大小固定的情况下随着数据不断增多那么哈希冲突的可能性也会越高。解决哈希冲突的方式有很多种。Redis 采用了链式哈希在不扩容哈希表的前提下将具有相同哈希值的数据链接起来以便这些数据在表中仍然可以被查询到。接下来详细说说哈希冲突以及链式哈希。哈希冲突哈希表实际上是一个数组数组里多每一个元素就是一个哈希桶。当一个键值对的键经过 Hash 函数计算后得到哈希值再将(哈希值 % 哈希表大小)取模计算得到的结果值就是该 key-value 对应的数组元素位置也就是第几个哈希桶。举个例子有一个可以存放 8 个哈希桶的哈希表。key1 经过哈希函数计算后再将「哈希值 % 8 」进行取模计算结果值为 1那么就对应哈希桶 1类似的key9 和 key10 分别对应哈希桶 1 和桶 6。此时key1 和 key9 对应到了相同的哈希桶中这就发生了哈希冲突。因此当有两个以上数量的 kay 被分配到了哈希表数组的同一个哈希桶上时此时称这些 key 发生了冲突。链式哈希Redis 采用了「链式哈希」的方法来解决哈希冲突。实现的方式就是每个哈希表节点都有一个 next 指针多个哈希表节点可以用 next 指针构成一个单项链表被分配到同一个哈希桶上的多个节点可以用这个单项链表连接起来这样就解决了哈希冲突。还是用前面的哈希冲突例子key1 和 key9 经过哈希计算后都落在同一个哈希桶链式哈希的话key1 就会通过 next 指针指向 key9形成一个单向链表。不过链式哈希局限性也很明显随着链表长度的增加在查询这一位置上的数据的耗时就会增加毕竟链表的查询的时间复杂度是 On。要想解决这一问题就需要进行 rehash就是对哈希表的大小进行扩展。接下来看看 Redis 是如何实现的 rehash 的。rehashRedis 会使用了两个全局哈希表进行 rehash。在正常服务请求阶段插入的数据都会写入到「哈希表 1」此时的「哈希表 2 」 并没有被分配空间。随着数据逐步增多触发了 rehash 操作这个过程分为三步给「哈希表 2」 分配空间一般会比「哈希表 1」 大 2 倍将「哈希表 1 」的数据迁移到「哈希表 2」 中迁移完成后「哈希表 1 」的空间会被释放并把「哈希表 2」 设置为「哈希表 1」然后在「哈希表 2」 新创建一个空白的哈希表为下次 rehash 做准备。为了方便你理解我把 rehash 这三个过程画在了下面这张图这个过程看起来简单但是其实第二步很有问题如果「哈希表 1 」的数据量非常大那么在迁移至「哈希表 2 」的时候因为会涉及大量的数据拷贝此时可能会对 Redis 造成阻塞无法服务其他请求。渐进式 rehash为了避免 rehash 在数据迁移过程中因拷贝数据的耗时影响 Redis 性能的情况所以 Redis 采用了渐进式 rehash也就是将数据的迁移的工作不再是一次性迁移完成而是分多次迁移。渐进式 rehash 步骤如下给「哈希表 2」 分配空间在 rehash 进行期间每次哈希表元素进行新增、删除、查找或者更新操作时Redis 除了会执行对应的操作之外还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上随着处理客户端发起的哈希表操作请求数量越多最终会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」从而完成 rehash 操作。这样就巧妙地把一次性大量数据迁移工作的开销分摊到了多次处理请求的过程中避免了一次性 rehash 的耗时操作。在进行渐进式 rehash 的过程中会有两个哈希表所以在渐进式 rehash 进行期间哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。比如查找一个 key 的值的话先会在哈希表 1 里面进行查找如果没找到就会继续到哈希表 2 里面进行找到。另外在渐进式 rehash 进行期间新增一个 key-value 时会被保存到「哈希表 2 」里面而「哈希表 1」 则不再进行任何添加操作这样保证了「哈希表 1 」的 key-value 数量只会减少随着 rehash 操作的完成最终「哈希表 1 」就会变成空表。rehash 触发条件介绍了 rehash 那么多还没说什么时情况下会触发 rehash 操作呢rehash 的触发条件跟负载因子load factor有关系。负载因子可以通过下面这个公式计算触发 rehash 操作的条件主要有两个当负载因子大于等于 1 并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令也就是没有执行 RDB 快照或没有进行 AOF 重写的时候就会进行 rehash 操作。当负载因子大于等于 5 时此时说明哈希冲突非常严重了不管有没有有在执行 RDB 快照或 AOF 重写都会强制进行 rehash 操作。