1.数据结构篇

1.1说说Redis的底层数据结构有哪些？

Redis之所以快，一方面是因为它是内存数据库，所有操作都是在内存中完成的，内存的访问速度本身就很快，在接收到一个键值对指令后，它几乎能以微秒级别的速度找到数据快速完成操作。另一方面也归功于Redis使用了高效的底层数据结构。
Redis使用全局哈希表来保存一个库中所有的键值对数据，一个哈希表就是一个数组，数组中的每个下标称为一个哈希桶。key是字符串对象而value可以是字符串对象，也可以是集合数据类型的对象。哈希桶中的元素不保存键值对本身，而是指向具体值的指针。比如key指向字符串对象，value可以指向字符串对象或者是集合对象。Redis中的每个对象都由redisObject对象来表示。

type字段标识该对象是什么类型的对象(String对象、List对象、Hash对象等等)，encoding标识该对使用了哪种底层数据结构，prt指向底层数据结构的指针。

哈希表的最大好处就是能以O(1)的时间复杂度来快速查找键值对，底层只需要计算键的哈希值就可以算出其数组中的哈希桶位置，然后就可以访问entry元素。但是哈希表就会存在哈希冲突以及rehash可能带来的阻塞问题。Redis解决哈希冲突的方式就是链式哈希，同一个哈希桶中的多个元素使用链表来保存，依次用next指针相连接。

所以如果这个链表过长就会导致查找效率变低，因为链表的时间复杂度是O(n)，这对追求快的Redis来说肯定是不能接受的。所以，Redis会对哈希表做rehash操作，rehash就是增加现有的哈希桶数量，让逐渐增多的entry元素在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少哈希冲突。
【渐进式rehash】
Redis默认使用了两个全局哈希表来使得rehash操作更高效，一开始当你插入元素的时候默认会使用哈希表1，此时的哈希表2没有被分配空间。随着数据逐步增多，Redis开始执行rehash，这个过程主要分为：
（1）给哈希表2分配更多的空间，例如是当前哈希表1的两倍；
（2）把哈希表1的数据重新映射拷贝到哈希表2中；
（3）释放哈希表1的空间。
（4）把哈希表1切换到哈希表2，用更大的哈希表2保存更多元素， 原来的哈希表1用来留作下一个rehash扩容使用。
整个过程虽然看起来简单，但是哈希表1数据重新映射拷贝到哈希表2时涉及到大量的数据拷贝工作，如果一次性把哈希表1的数据都迁移完，会造成Redis线程阻塞，无法服务请求。为了避免这个问题，Redis采用了渐进式rehash。
简单来说就是在第二步拷贝数据时，Redis依然能正常处理客户端请求，每处理一个请求时，从哈希表1的第一个索引位置开始，顺带着将这个索引位置上所有的entries拷贝到哈希表2中；等到下一次处理时，再顺带拷贝哈希表1的下一个索引位置的entries。这样就巧妙地避免了一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时保证，保证数据的快速访问。

另外rehash的触发条件与负载因子有关，触发rehash还有两个条件：

（1）如果负载因子大于等于1，并且Redis没有在执行bgsave命令或者是bgrewriteof命令，也就是没有执行RDB快照或AOF重写的时候，就会进行rehash操作。
（2）当负载因子大于等于5时，说明哈希冲突非常严重了，不管有没有执行RDB或AOF，都会强制进行rehash操作。

1.2说说Redis的SDS

字符串在Redis中是非常常用的，键值对中的key是字符串类型，值有时也是字符类型。
Redis是由C语言实现的，但是它没有使用C语言的char字符数组来实现字符串，而是自己封装了名为简单动态字符串的数据结构来表示字符串。
【C语言字符串的缺陷】
C语言的字符串其实就是一个字符数组，在C语言中，对字符串操作时，char指针只是指向字符数组的起始位置，而字符数组的结尾位置就使用\0表示，表示一个字符串的结束。所以C语言获取字符串长度的时间复杂度是O(N)。从起始位置开始遍历，遍历到\0就结束遍历。所以字符串中就不能有\0字符，否则会被程序当做是字符串的结尾，这个限制使得C语言的字符串只能保存文本数据，不能保存图片、音频、视频等这样的二进制数据。另外C语言的字符串操作函数是不高效且不安全的，比如有缓冲区溢出的风险，可能会造成程序终止运行，比如在做字符串拼接的时候。

【SDS结构设计】

Redis就自定义了SDS的数组结构来保存字符串对象，结构的每个成员变量分别是：
（1）len：记录了字符串的长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行了，时间复杂度是O(1)；
（2）alloc：分配给字符数组的空间长度。这样在修改字符串的时候，可以通过alloc-len计算出剩余空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将SDS的空间扩展至执行修改所需的大小，然后再执行实际的修改操作。避免缓冲区溢出的风险。
（3）flags：用来表示不同类型的SDS，分别是sdshdr5、shshdr8、sdshdr16、shshdr32、sdshdr64。这个设计其实需要是用于节省内存空间，它们之间的区别在于len和alloc成员变量的值不同。比如sdshdr16表示字符数组长度和分配空间大小不能超过2^16，shshdr32表示字符数组长度和分配空间大小不能超过2^32，这样能够有效节省内存空间。

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

1.3说说Redis的list数据结构

Redis在listNode结构体基础上又封装了list这个数据结构，这样操作起来会更加方便。

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

【优点】：
（1）listNode链表结构体里带有pre指针和next指针，获取某个节点的前继节点和后驱节点的时间复杂度是O(1)。而且这连个指针都可以指向null，所以是一个双向的无环链表。
（2）list结构因为了链表的头指针head和尾指针tail，所以获取链表的头结点和尾节点的时间复杂度是O(1)；
（3）list结构因为提供了链表节点数量len，所以获取链表中的节点数量的时间复杂度是O(1)；
（4）listNode链表节点使用了void* ptr指针保存节点值，并切块有通过list结构的dup、free、match函数指针为节点设置该节点类型的特定的函数，因此链表节点可以保存各种不同类型的值
【缺点】：
（1）链表每个节点之间内存都是不连续的，无法很好利用CPU缓存。能很好利用CPU缓存的数组就是数组，因为数组的内存是连续的，可以充分利用CPU缓存来加速访问。
（2）保存一个链表listNode结构体，都需要一个list结构头内存空间的分配，开销较大。

1.4说说压缩列表

压缩列表是Redis为了节约内存而开发的，由连续内存块组成的顺序型结构，有点类似于数组。
zlbytes：记录整个压缩列表占用的内存字节数；
zltail：压缩列表尾部的偏移量；
zllen：压缩列表包含的节点数量；
zlend：压缩列表的结束标志位。
在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头的三个字段直接定位，复杂度是O(1)。而查找其他元素时只能逐个查找，时间复杂度是O(n)，因此压缩列表不适合保存过多的元素。

压缩列表的节点包含三部分内容：
（1）prevlen：记录前一个节点的长度；
（2）encoding：记录当前节点实际数据的类型和长度；
（3）data：当前节点的实际数据；
当我们往压缩列表中插入数据时，压缩列表就会根据数据是字符串还是整数，以及数据的大小，会使用不同空间大小的prevlen和encoding这两个字段保存元素的信息，这种根据数据大小和类型进行不同空间大小分配的设计思想，正是Redis为了节约内存而采用的。
压缩列表中每个节点的prevlen属性记录了前一个节点的长度，而且prelen属性的空间大小跟前一个节点长度值有关：
如果前一个节点的长度小于254字节，那么prelen属性需要用1字节的空间记录这个长度值；
如果前一个节点的长度大于等于254字节，那么prelen属性需要用5字节的空间来记录这个长度值。
encoding属性的空间大小跟数据是字符串还是整数，以及字符串的长度有关；
如果当前节点的数据是整数，encoding会使用1字节的空间进行编码；
如果当前节点是字符串，根据字符串的长度大小，encoding会使用1字节、2字节、5字节的空间进行编码。
【压缩列表最大的缺陷】：连锁更新
压缩列表除了查找复杂度高以外，还有一个最大的问题就是连锁更新。
压缩列表新增某个元素或修改某个元素时，如果空间不够用，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的prevlen占用空间都发生变化，从而引起连锁更新的问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

打个比方，现在压缩列表中有多个连续的、长度在250-253字节之间的节点，如果节点的长度值小于254字节，prevlen属性用1字节的空间来保存这个长度值，这时候如果将1个254字节的新节点加入到压缩列表中的头结点，新节点成为e1的前继节点，那e1的prevlen属性就要从原来的1字节扩展为5字节。当扩展完了以后，e1节点的字节数就超过了254字节，就会导致e2、e3一直到数组的末尾节点，就类似于多米诺牌效应一样。

所以压缩列表虽然使用紧凑型的内存布局能节省内存开销，但如果保存的元素数量增加了，或者是元素变大了，就会导致内存重新分配，最糟糕的情况是连锁更新的问题。所以压缩列表只会用于保存节点数量不多或者是整个元素节点长度固定的场景。

1.5说说哈希表

1.6说说整数数组

整数数组保存元素的容器一个contents数组，虽然被声明为int8_t类型的数组，但实际上数组真正的类型取决于inset结构体里的encoding属性的值，比如：
（1）如果encoding属性值为int16_t类型，数组中每个元素的类型都是int16_t；同理32、64
【整数数组的升级操作】
当我们将一个新元素加入到整数集合里面的时候，如果新元素的类型int32_t比整数集合现在所有的元素类型int16_t，这个整数数组就需要先进行类型扩充contents数组的容量。

如果现在要加入一个需要用int32_t类型来保存的元素，整数集合需要先升级，在原来的基础上扩容至4*32，这样才能保存下个类型的元素，也就是说之前的元素也需要用int32_t类型来保存，并且不会进行降级操作。所以整数集合升级的好处也是为了能够节省内存。

1.7说说跳表这种数据结构

Redis只有在Zset数据类型中的底层使用到了跳表和哈希表，跳表的优势是能支持平均时间复杂度O(logN)的节点查找以及范围查找，以及快速的元素插入和删除操作，他的设计思想就是二路分治查找；而哈希表的优势是时间复杂度为O(1)的快速单点查询。比如通过zRangeByScore函数：根据元素权重返回一个范围内的元素，zRange根据权重排名返回一个范围内的元素；还有zscore函数通过哈希表快速定位元素的score。

Redis在设计zset结构体的时候，其中就包含了哈希表dict和跳表zskipList。
【跳表】

跳表就是在一个双向链表的基础上增加了多级索引，比如三层的跳表就有level0、level1和level2。最底层是level0，最高层是level2。每个层级的头结点和尾结点作为哑结点，头结点指向该层的第一个包含真实数据的节点。真实数据节点还包含了一个指针指向下一层级的结构体为zskiplistLevel的level数组的当前节点，以及跨度。跨度实际上是为了计算这个节点在跳表中的排位比如Zrank和ZreverseRank函数。比如计算节点33，他在level2的跨度是3，排名就是第三。

跳表中的每个节点都保存了元素的value值，以及double类型的权重值，前继节点，后驱节点的指针，好处是能够从尾节点从后往前遍历，倒序查找的时候很方便。

跳表的结构体定义了三个变量，分别表示跳表的头结点、尾结点以及跳表的长度和跳表的最大层数。这样就能以O(1)时间复杂度快速访问链表头结点和尾结点，获取链表长度的最大层数。
【跳表节点的查询过程】
查找一个跳表节点的过程时，会从头结点的最高层开始，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的SDS类型的元素和元素的权重来进行判断：
（1）如果当前节点的权重小于要查找的权重时，跳表就会访问该层的下一个节点。
（2）如果当前节点的权重等于要查找的权重时，并且当前节点的SDS数据类型小于要查找的SDS数据，就会访问该层的下一个节点
如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的level数组里的下一层指针，去下一层继续查找。

【跳表节点层数设置】
跳表的相邻两层的节点数量最理想的比例是2:1，比如level0有8个元素，level1有4个元素，这样查询的时间复杂度就可以降低到O(logN)。但维护2：1的代价就是一旦我们要插入或删除节点，后续节点的层数都需要进行调整，我们需要给level数组重新分配空间，这样就带来了额外的开销。


比如删除节点33，就需要把42节点新增level数组空间，保存3层的指针。为了避免上面的问题，跳表在创建节点的时候，会随机生成每个节点的层数，不需要维持严格的2：1关系。层数的初始值为1，如果生成的节点的随机数小于0.25，层数就增加1，这也意味着一层的概率不超过25%。
【跳表与哈希表的组合使用】

所以就需要考虑怎么保持哈希表与跳表中的元素一致性问题了，zset在创建的时候初始化哈希表和跳表两个数据结构。当往Zset中插入数据时，zsetAdd函数被调用，zsetAdd函数通过dictFind函数如果发现要插入的元素已经存在，那么zsetAdd函数会调用zslUpdateScore函数，更新跳表中元素权重值，然后把哈希表中该元素的value指向跳表节点中的权重值，这样哈希表和跳表都能保证最新值。

1.8quickList的设计说一下？

quickList与链表的结构体相似，都包含了头结点和尾结点

quicklistNode结构体里包含了前一个节点和后一个节点的指针，这样quickNode形成了一个双向链表，但是链表节点的元素不再保存单纯元素值，而是保存了一个压缩列表，所以在它中属性中有一个指向压缩列表的指针，以及保存了压缩列表的字节大小和元素个数。


所以在往quickList中添加元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能够容纳就可以直接保存到该节点的压缩列表中，如果不能容纳，才会新建一个新的quicklistNode结构。qucikList会控制结点中压缩队列的大小和元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题。

1.9说说ListPack的结构设计？

listpack头部包含两个属性，分别记录了listpack总字节数和元素数量，listpack末尾也有个结尾标识。
另外每个entry元素，由三部分组成：
（1）encoding：该元素的编码类型，会同不同长度的整数和字符串进行编码；
（2）data：实际存放的数据；
（3）len：encoding+data的长度。
listpack没有压缩列表中记录前一个节点长度的字段了，listpack只记录当前节点的长度，当我们向listpack中新添加一个元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。