本篇文章为你整理了Redis原理（redis原理面试题）的详细内容，包含有Redis原理详解 redis原理面试题 redis原理图 redis原理详细图解 Redis原理，希望能帮助你了解 Redis原理。

　　Redis数据结构

　　1. SDS

　　Redis 是用 C 语言写的，但是对于 Redis 的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis 的默认字符串表示

　　因为 C 语言字符串存在很多问题：

　　获取字符串长度的需要通过运算

　　非二进制安全

　　例如，我们执行命令：

127.0.0.1:6379 set name zhangsan

　　那么 Redis 将在底层创建两个 SDS，其中一个是包含 “name” 的 SDS，另一个是包含 “zhangsan” 的 SDS。

　　1.1 SDS 是什么

　　Redis 是 C 语言实现的，其中 SDS 是一个结构体，源码如下：

　　例如，一个包含字符串 “name” 的 sds 结构如下：第一次分配时并不会分配多余空间

　　SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为 “hi” 的 SDS：

　　假如我们要给 SDS 追加一段字符串 “,Amy”，这里首先会申请新内存空间：

　　如果新字符串小于 1M，则新空间为扩展后字符串长度的两倍 + 1；

　　如果新字符串大于 1M，则新空间为扩展后字符串长度 + 1M+1。称为内存预分配。

　　1.2 SDS 的优点

　　获取字符串长度的时间复杂度为 O (1)

　　支持动态扩容

　　支持内存预分配，减少用户线程与内核线程交互次数

　　二进制安全

　　一般来说，SDS 除了保存数据库中的字符串值以外，SDS 还可以作为缓冲区（buffer）：包括 AOF 模块中的 AOF 缓冲区以及客户端状态中的输入缓冲区

　　2. Inset

　　intset 是 set 集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。

　　2.1 Inset是什么？

　　结构如下：

　　其中的 encoding 包含三种模式，表示存储的整数大小不同：

　　为了方便查找，Redis 会将 intset 中所有的整数按照升序依次保存在 contents 数组中，结构如图：

　　现在，数组中每个数字都在 int16_t 的范围内，因此采用的编码方式是 INTSET_ENC_INT16，每部分占用的字节大小为：

　　encoding：4 字节 （可以理解为标识每个元素的类型）

　　length：4 字节

　　contents：2 字节 * 3 = 6 字节

　　2.2 inset自动升级

　　我们向该其中添加一个数字：50000，这个数字超出了 int16_t 的范围，intset 会自动升级编码方式到合适的大小。
 

　　以当前案例来说流程如下：

　　升级编码为 INTSET_ENC_INT32 , 每个整数占 4 字节，并按照新的编码方式及元素个数扩容数组

　　倒序依次将数组中的元素拷贝到扩容后的正确位置

　　将待添加的元素放入数组末尾

　　最后，将 inset 的 encoding 属性改为 INTSET_ENC_INT32，将 length 属性改为 4

　　那么如果我们删除掉刚加入的 int32 类型时，会不会做一个降级操作呢？

　　不会。主要还是减少开销的权衡

　　源码如下：

　　2.3 总结：

　　Intset 可以看做是特殊的整数数组，具备一些特点：

　　Redis 会确保 Intset 中的元素唯一、有序

　　具备类型升级机制，可以节省内存空间

　　底层采用二分查找方式来查询

　　3. Dict

　　我们知道 Redis 是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过 Dict 来实现的。是 set 和 hash 的实现方式之一

　　3.1 Dict是什么？

　　Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

　　当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash 值（h），然后利用 h sizemask 来计算元素应该存储到数组中的哪个索引位置。我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1 3 =1，因此 k1=v1 要存储到数组角标 1 位置。

　　注意这里还有一个指向下一个哈希表节点的指针，我们知道哈希表最大的问题是存在哈希冲突，如何解决哈希冲突，有开放地址法和链地址法。这里采用的便是链地址法，通过 next 这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。

　　Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）
 

　　3.2 深入理解

　　哈希算法：Redis 计算哈希值和索引值方法如下：

#1、使用字典设置的哈希函数，计算键 key 的哈希值

　　hash = dict- type- hashFunction(key);

　　#2、使用哈希表的sizemask属性和第一步得到的哈希值，计算索引值

　　index = hash dict- ht[x].sizemask;

　　
解决哈希冲突：这个问题上面我们介绍了，方法是链地址法。通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点。

　　
扩容和收缩：当哈希表保存的键值对太多或者太少时，就要通过 rerehash (重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤：

　　
如果是扩容，则新 size 为第一个大于等于 dict.ht [0].used + 1 的 2^n

　　如果是收缩，则新 size 为第一个小于等于 dict.ht [0].used 的 2^n （不得小于 4）

　　
按照新的 realeSize 申请内存空间，创建 dictht ，并赋值给 dict.ht [1]

　　设置 dict.rehashidx = 0，标示开始 rehash

　　将 dict.ht [0] 中的每一个 dictEntry 都 rehash 到 dict.ht [1]

　　将 dict.ht [1] 赋值给 dict.ht [0]，给 dict.ht [1] 初始化为空哈希表，释放原来的 dict.ht [0] 的内存

　　将 rehashidx 赋值为 - 1，代表 rehash 结束

　　在 rehash 过程中，新增操作，则直接写入 ht [1]，查询、修改和删除则会在 dict.ht [0] 和 dict.ht [1] 依次查找并执行。这样可以确保 ht [0] 的数据只减不增，随着 rehash 最终为空

　　
服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于 1。

　　服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于 5。

　　
什么叫渐进式 rehash？也就是说扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。如果保存在 Redis 中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成 Redis 一段时间内不能进行别的操作。所以 Redis 采用渐进式 rehash, 这样在进行渐进式 rehash 期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行 增加操作，一定是在新的哈希表上进行的。

　　3.3 总结：

　　Dict 的结构：

　　类似 java 的 HashTable，底层是数组加链表来解决哈希冲突

　　Dict 包含两个哈希表，ht [0] 平常用，ht [1] 用来 rehash

　　Dict 的伸缩：

　　当 LoadFactor 大于 5 或者 LoadFactor 大于 1 并且没有子进程任务时，Dict 扩容

　　当 LoadFactor 小于 0.1 时，Dict 收缩

　　扩容大小为第一个大于等于 used + 1 的 2n

　　收缩大小为第一个大于等于 used 的 2n

　　Dict 采用渐进式 rehash，每次访问 Dict 时执行一次 rehash

　　rehash 时 ht [0] 只减不增，新增操作只在 ht [1] 执行，其它操作在两个哈希表

　　4. ZipList

　　ZipList 是一种特殊的 “双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入 / 弹出操作，并且该操作的时间复杂度为 O (1)。

　　4.1 ZipList 是什么？

　　zlbytes : 字段的类型是 uint32_t , 这个字段中存储的是整个 ziplist 所占用的内存的字节数

　　zltail : 字段的类型是 uint32_t , 它指的是 ziplist 中最后一个 entry 的偏移量。用于快速定位最后一个 entry, 以快速完成 pop 等操作

　　zllen : 字段的类型是 uint16_t , 它指的是整个 ziplit 中 entry 的数量。这个值只占 2bytes（16 位）: 如果 ziplist 中 entry 的数目小于 65535 (2 的 16 次方), 那么该字段中存储的就是实际 entry 的值。若等于或超过 65535, 那么该字段的值固定为 65535, 但实际数量需要一个个 entry 的去遍历所有 entry 才能得到。

　　zlend 是一个终止字节，其值为全 F, 即 0xff. ziplist 保证任何情况下，一个 entry 的首字节都不会是 255

　　4.2 ZipListEntry

　　ZipList 中的 Entry 并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用 16 个字节，浪费内存。而是采用了下面的结构：

　　previous_entry_length：前一节点的长度，占 1 个或 5 个字节。

　　如果前一节点的长度小于 254 字节，则采用 1 个字节来保存这个长度值

　　如果前一节点的长度大于 254 字节，则采用 5 个字节来保存这个长度值，第一个字节为 0xfe，后四个字节才是真实长度数据

　　
encoding：编码属性，记录 content 的数据类型（字符串还是整数）以及长度，占用 1 个、2 个或 5 个字节

　　contents：负责保存节点的数据，可以是字符串或整数

　　第一种情况：一般结构

　　​ prevlen：前一个 entry 的大小，编码方式见下文；

　　​ encoding：不同的情况下值不同，用于表示当前 entry 的类型和长度；

　　​ entry-data：真是用于存储 entry 表示的数据；

　　第二种情况：在 entry 中存储的是 int 类型时，encoding 和 entry-data 会合并在 encoding 中表示，此时没有 entry-data 字段；

　　redis 中，在存储数据时，会先尝试将 string 转换成 int 存储，节省空间；此时 entry 结构：

　　prevlen编码

　　当前一个元素长度小于 254（255 用于 zlend）的时候，prevlen 长度为 1 个字节，值即为前一个 entry 的长度，如果长度大于等于 254 的时候，prevlen 用 5 个字节表示，第一字节设置为 254，后面 4 个字节存储一个小端的无符号整型，表示前一个 entry 的长度；

 prevlen from 0 to 253 encoding entry //长度小于254结构

　　0xFE 4 bytes unsigned little endian prevlen encoding entry //长度大于等于254

　　encoding 编码

　　encoding 的长度和值根据保存的是 int 还是 string，还有数据的长度而定；

　　前两位用来表示类型，当为 “11” 时，表示 entry 存储的是 int 类型，其它表示存储的是 string；

　　存储string时：

　　00xxxxxx ：此时 encoding 长度为 1 个字节，该字节的后六位表示 entry 中存储的 string 长度，因为是 6 位，所以 entry 中存储的 string 长度不能超过 63；

　　01xxxxxxxxxxxxxx 此时 encoding 长度为两个字节；此时 encoding 的后 14 位用来存储 string 长度，长度不能超过 16383；

　　10000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 此时 encoding 长度为 5 个字节，后面的 4 个字节用来表示 encoding 中存储的字符串长度，长度不能超过 2^32 - 1;

　　存储int时：

　　11000000 encoding 为 3 个字节，后 2 个字节表示一个 int16；

　　11010000 encoding 为 5 个字节，后 4 个字节表示一个 int32;

　　11100000 encoding 为 9 个字节，后 8 字节表示一个 int64;

　　11110000 encoding 为 4 个字节，后 3 个字节表示一个有符号整型；

　　11111110 encoding 为 2 字节，后 1 个字节表示一个有符号整型；

　　1111xxxx encoding 长度就只有 1 个字节，xxxx 表示一个 0 - 12 的整数值；

　　11111111 zlend

　　4.3 ZipList 的连锁更新问题

　　ZipList 的每个 Entry 都包含 previous_entry_length 来记录上一个节点的大小，长度是 1 个或 5 个字节：

　　如果前一节点的长度小于 254 字节，则采用 1 个字节来保存这个长度值

　　如果前一节点的长度大于等于 254 字节，则采用 5 个字节来保存这个长度值，第一个字节为 0xfe，后四个字节才是真实长度数据

　　现在，假设我们有 N 个连续的、长度为 250~253 字节之间的 entry，因此 entry 的 previous_entry_length 属性用 1 个字节即可表示，如图所示：

　　ZipList 这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。新增、删除都可能导致连锁更新的发生。虽然发生的条件非常苛刻，但不代表不会发生

　　4.4 总结：

　　ZipList 特性：

　　压缩列表的可以看做一种连续内存空间的” 双向链表”

　　列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低

　　如果列表数据过多，导致链表过长，可能影响查询性能

　　增或删较大数据时有可能发生连续更新问题

　　5. QuickList

　　5.1 QuickList 是什么？

　　ZipList 虽然节省内存，但申请内存必须是连续空间，但是我们要存储大量数据，内存中碎片比较多，很难找到一块大的连续空间。于是 ，大数据量下，内存申请效率低成了 ziplist 的最大问题，而 quickList 就是为了帮助 zipList 摆脱困境的。

　　为了缓解内存申请效率低的问题，QuickList 提供了可限制 ZipList 的最大节点数 和 每个 entry 的大小的方式。

　　那么对于大数据量 ，我们可以采用分片的思想，存储在多个 ZipList 中 ，而 QuickList 可以将这些 ZipList 作为节点连接起来。

　　为了避免 QuickList 中的每个 ZipList 中 entry 过多，Redis 提供了一个配置项：list-max-ziplist-size 来限制。

　　如果值为正，则代表 ZipList 的允许的 entry 个数的最大值

　　如果值为负，则代表 ZipList 的最大内存大小，分 5 种情况：

　　-1：每个 ZipList 的内存占用不能超过 4kb

　　-2：每个 ZipList 的内存占用不能超过 8kb

　　-3：每个 ZipList 的内存占用不能超过 16kb

　　-4：每个 ZipList 的内存占用不能超过 32kb

　　-5：每个 ZipList 的内存占用不能超过 64kb

　　
其默认值为 -2：

　　以下是 QuickList 的和 QuickListNode 的结构源码：

　　5.2 QuickList 内存布局

　　5.3 总结：

　　QuickList 的特点：

　　是一个节点为 ZipList 的双端链表

　　节点采用 ZipList ，解决了传统链表的内存占用问题

　　控制了 ZipList 大小，解决连续内存空间申请效率问题

　　中间节点可以压缩，进一步节省了内存

　　6. SkipList

　　跳跃表结构在 Redis 中的运用场景只有一个，那就是作为有序列表 (Zset) 的使用。跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这就是跳跃表的长处。跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构

　　6.1 SkipList 是什么？

　　SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

　　元素按照升序排列存储

　　节点可能包含多个指针，指针跨度不同。

　　6.2 SkipListNode 结构

　　ele 字段，持有数据，是 sds 类型

　　score 字段，其标示着结点的得分，结点之间凭借得分来判断先后顺序，跳跃表中的结点按结点的得分升序排列.

　　backward 指针，这是原版跳跃表中所没有的。该指针指向结点的前一个紧邻结点.

　　level 字段，用以记录所有结点 (除过头节点外)；每个结点中最多持有 32 个 zskiplistLevel 结构。实际数量在结点创建时，按幂次定律随机生成 (不超过 32). 每个 zskiplistLevel 中有两个字段

　　forward 字段指向比自己得分高的某个结点 (不一定是紧邻的), 并且，若当前 zskiplistLevel 实例在 level [] 中的索引为 X, 则其 forward 字段指向的结点，其 level [] 字段的容量至少是 X+1. 这也是上图中，为什么 forward 指针总是画的水平的原因.

　　span 字段代表 forward 字段指向的结点，距离当前结点的距离。紧邻的两个结点之间的距离定义为 1.

　　6.3 skiplist 与平衡树、哈希表的比较

　　skiplist 和各种平衡树（如 AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个 key 的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

　　在做范围查找的时候，平衡树比 skiplist 操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在 skiplist 上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。

　　平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而 skiplist 的插入和删除只需要修改相邻节点的指针，操作简单又快速。

　　从内存占用上来说，skiplist 比平衡树更灵活一些。一般来说，平衡树每个节点包含 2 个指针（分别指向左右子树），而 skiplist 每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis 里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。

　　查找单个 key，skiplist 和 平衡树 的时间复杂度都为 O (log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近 O (1)，性能更高一些。所以我们平常使用的各 Map 或 dictionary 结构，大都是基于哈希表实现的。

　　从算法实现难度上来比较，skiplist 比平衡树要简单得多。

　　6.4 总结：

　　SkipList 的特点：

　　跳跃表是一个双向链表，每个节点都包含 score 和 ele 值

　　节点按照 score 值排序，score 值一样则按照 ele 字典排序

　　每个节点都可以包含多层指针，层数是 1 到 32 之间的随机数

　　不同层指针到下一个节点的跨度不同，层级越高，跨度越大

　　增删改查效率与红黑树基本一致，实现却更简单

　　7. RedisObject

　　7.1 RedisObject 是什么？

　　Redis 中的任意数据类型的键和值都会被封装为一个 RedisObject，也叫做 Redis 对象

　　从 Redis 的使用者的角度来看，⼀个 Redis 节点包含多个 database（非 cluster 模式下默认是 16 个，cluster 模式下只能是 1 个），而一个 database 维护了从 key space 到 object space 的映射关系。这个映射关系的 key 是 string 类型，⽽ value 可以是多种数据类型，比如：string, list, hash、set、sorted set 等。我们可以看到，key 的类型固定是 string ，而 value 可能的类型是多个。

　　⽽从 Redis 内部实现的⾓度来看，database 内的这个映射关系是用⼀个 dict 来维护的。dict 的 key 固定用⼀种数据结构来表达就够了，这就是动态字符串 sds。而 value 则比较复杂，为了在同⼀个 dict 内能够存储不同类型的 value，这就需要⼀个通⽤的数据结构，这个通用的数据结构就是 robj，全名是 redisObject。

　　!

　　type : 占 4bit , 五个取值类型，表示对象类型 String , Hash , List , set , zset。

　　encoding : 占 4bit ，十一种编码方式

　　lru : 占用 3 字节，记录最后一次被访问的时间，主要用于 lru 算法，最近最少使用

　　refcount ：占用 4 字节，引用计数器，无人用就回收

　　*ptr：占用 8 字节 ，只想存放实际数据的空间

　　redis 的头部占用 16 字节

　　7.2 encoding 取值：

　　Redis 中会根据存储的数据类型不同，选择不同的编码方式，共包含 11 种不同类型：

　　
7.3 五种数据结构

　　Redis 中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

　　
本文由传智教育博学谷教研团队发布。

　　如果本文对您有帮助，欢迎关注和点赞；如果您有任何建议也可留言评论或私信，您的支持是我坚持创作的动力。

　　转载请注明出处！

　　以上就是Redis原理（redis原理面试题）的详细内容，想要了解更多 Redis原理的内容，请持续关注盛行IT软件开发工作室。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。