《Redis核心技术与实战》学习总结（1）

末蓝、 2022-08-28 01:58 188阅读 0赞

**目录**

0 写在开头

1 KV数据库的基本架构

2 Redis的数据结构

End 总结

参考资料

--------------------

# 0 写在开头 #

作为Key/Value键值数据库，Redis的应用非常广泛。在之前多年的工作生涯中，我也只是关注了零散的技术点，没有对Redis建立起一套整体观，但只有建立了系统整体观，才能更好地定位问题和解决问题，更重要的是应付面试。

刚好，极客时间推出了一门《Redis核心技术与实战》课程，于是我就入手了，这是我的学习总结，化繁为简，只留重点，分享与你。

# 1 KV数据库的基本架构 #

为了建立系统观，最好的方法就是对其总体架构和关键模块有一个全局认知，因此这门课在最开始便给出了一个简单的KV数据库的基本架构，它包括了：

**（1）访问框架**

**（2）索引模块**

**（3）操作模块**

**（4）存储模块**

![图片][a4a6b85513b78262bef3e5420349d949.png]

SimpleKV - 来自极客时间

为了支持更加丰富的业务场景，其实 Redis 对这些组件或者功能进行了扩展，或者说是进行了精细优化，从而满足了功能和性能等方面的要求。

下图展示了从SimpleKV到Redis的变化：

![图片][f4d04b82c7cfd6efda470e97185eeb82.png]

SimpleKV to Redis - 来自极客时间

上图中展示了几点变化：

一是Redis主要使用**网络框架来进行访问**，使得Redis可以作为一个独立的基础网络服务；

二是Redis数据模型中的**value类型更加丰富**，可以提供更多的接口；

三是Redis扩展了**持久化模块**，提供日志（AOF）和快照（RDB）。

四是Redis提供了**集群的支持**，使得HA和可扩展成为可能。

# 2 Redis的数据结构 #

Redis之所以“快”，**一方面因为它是内存数据库**，所有操作都在内存上完成，内存的访问速度本来就快。**另一方面则是因为高效的数据结构**，使得操作键值效率较高。

总体来说，Redis使用了一个用来保存每个Key/Value的全局哈希表结构，其中Value类型又包括了支持集合类型的双向链表、压缩列表、跳表等五大底层结构。

**K/V的组织结构：全局哈希表**

Redis使用了一个全局维度的哈希表来保存所有的Key/Value，**每个哈希表本质上都是一个数组，这个数组的每个元素称为一个哈希桶**。

哈希桶中的元素保存的并不是Value本身，而是**指向Value的指针**，如下图所示：

![图片][e0f4b916d157c9e25be5e17c378ca7bd.png]

由数据结构的知识可以知道，**哈希表的时间复杂度为O(1)，因此它非常适合快速查找的场景**。

**哈希冲突及其解决**

当往哈希表中写入的数据变的很多时，哈希冲突问题就会出现。所谓哈希冲突，就是两个Key的哈希值正好落到了同一个哈希桶中（哈希桶的个数毕竟通常少于Key的个数）。

因此，和我们在数据结构课程学到的一致，**Redis也采用了链式哈希来解决哈希冲突**。所谓链式哈希，就是同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接，如下图所示：

![图片][3459e636f847c4d93477b73644939bf4.png]

但是，**如果哈希表里写入的数据越来越多，哈希冲突链也会进而变得很长，**从而导致这个链条上得元素查找耗时长，效率降低。

因此，**Redis还会对哈希表做rehash操作**。所谓rehash，就是增加现有的哈希桶的数量，让逐渐增多的entry元素能够在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

在具体操作中，Redis会开辟一个新的哈希表（比如：大小为之前的两倍），然后把之前哈希表的数据重新映射到新的哈希表，最后释放之前的哈希表。

***画外音：****是不是跟.NET中的集合类型动态扩容的思想类似？*

![图片][a5574b6bb8c2fbb1aa7ec5593c256331.png]

But，在拷贝之前哈希表数据到新哈希表时，涉及到数据量过大，有可能会造成Redis的线程阻塞，从而无法服务其他的请求。因此，**Redis采用了渐进式哈希的解决方案**。

简单来说，所谓渐进式哈希就是不一次性把老哈希表中的数据迁移完，而是在每次处理一个请求时，从老哈希表中的第一个索引位置开始，顺带着将这个索引位置上的所有entries拷贝到新哈希表中；等下一个请求时，再顺带拷贝下一个索引位置的entries。如此，便**将一次性的大量拷贝的开销，分摊到多次处理请求的过程中，避免了耗时的操作 和 服务的中断**。

渐进式哈希的示例流程如下图所示：

![图片][0842d9293655313ffd95f6318f07863e.png]

此外，渐进式rehash执行时，除了根据键值对的操作来进行数据迁移，**Redis本身还会有一个定时任务在执行rehash**，如果没有键值对操作时，这个定时任务会周期性地（例如每100ms一次）搬移一些数据到新的哈希表中，这样可以缩短整个rehash的过程。

**底层数据结构概览**

Redis的Key/Value是通过哈希表进行组织的，对于String类型，找到哈希桶就可以直接CRUD了，因此O(1)就是String类型的操作复杂度了。

但是，对于集合类型来说，还需要进一步操作。在此之前，我们先了解一下都有哪些底层数据结构。

我们所熟知的String、List、Hash、Sorted Set 和 Set其实只是Redis中数据的保存形式，而**一般所说的数据结构其实是它们的底层实现**。

如下图所示，Redis的底层数据结构一共有6种，其和常见数据类型的对应关系已经清晰地体现在了下面这张图片里（给个赞）。

![图片][0929bbb7ed845084f19bde8adf710169.png]

Redis数据类型与底层数据结构 - 来自极客时间

除了String类型的底层实现只有一种，即简单动态字符串。其余数据类型（List、Hash、Sorted Set和Set）都有两种底层实现，他们又被称为**集合类型**，即**一个键对应了一个集合的数据**。

**底层数据结构复杂度**

通过上面的描述，我们可以知道哈希表的复杂度是O(1)，而数组 和 双向链表 也很常见，其复杂度基本是O(N)。学习过数据结构课程的都知道，O(N)的操作效率并不高，因此Redis引入了压缩列表 和 跳表。虽然压缩列表和跳表并不为我们所熟知，但它俩却是对整数数组和双向链表所做的优化。

![图片][c8930fba430e2ad4d0462e03b2c35f7b.png]

首先，来看压缩列表，压缩列表也类似于一个数组，但和数组不同的是，**压缩列表在表头有三个字段，分别表示列表长度、列表尾的偏移量 和 列表中entry的个数。压缩列表在表尾还有一个字段，表示列表结束**，如下图所示：

![图片][c05846beeeed42dd074f232d22546ce2.png]

由上图可知，在压缩列表中定位第一个和最后一个元素，只需要通过表头三个字段即可直接定位，无须遍历一次，因此查找首元素和尾元素的复杂度为O(1)。而需要查找其他元素时，就只能遍历查找了，此情景的复杂度退化为O(N)。

然后，来看跳表。**跳表是在链表的基础之上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位**。一个具体的查找案例，如下图所示：

![图片][d8ef40ce794180600635c4312e43e776.png]

从上图可以看到，这个查找过程其实是在多级索引上跳来跳去，最后定位到具体的要查找的元素。我们常听到，没有什么不是一顿火锅解决不了的事情，如果不行，那就两顿。对于跳表来说，没有什么不是增加索引解决不了的查询，如果不够快，那就再加一级索引。

当数据量非常大时，跳表的查找复杂度就是O(logN)，学过数据结构的都知道，它比O(N)效率要高。因此，我们也可以知道Sorted Set类型在数据元素较少时采用压缩列表，而一旦超过阈值，就会转为跳表结构来保证查询效率不受影响。

# End 总结 #

本文总结了Redis的基础架构 和 底层数据结构，这部分内容通常也是后端开发面试中的常见内容，希望对你有所帮助。

# **参考资料** #

极客时间，蒋德钧《Redis核心技术与实战》

[a4a6b85513b78262bef3e5420349d949.png]: /images/20220828/3b96143f10094a2eab29073828c5bde6.png
[f4d04b82c7cfd6efda470e97185eeb82.png]: /images/20220828/9bd99ed5a0714681b481263a5334b03a.png
[e0f4b916d157c9e25be5e17c378ca7bd.png]: /images/20220828/d38da8a8f83d4192bc0358b6e732b325.png
[3459e636f847c4d93477b73644939bf4.png]: /images/20220828/b07c6dc25f8844d29656eb4779816899.png
[a5574b6bb8c2fbb1aa7ec5593c256331.png]: /images/20220828/36bd6688971840e5839860efc94218b0.png
[0842d9293655313ffd95f6318f07863e.png]: /images/20220828/8f18907ef1a044b88cf717ffd7665644.png
[0929bbb7ed845084f19bde8adf710169.png]: /images/20220828/b388d39ae873409f8d029a805a450876.png
[c8930fba430e2ad4d0462e03b2c35f7b.png]: /images/20220828/de65696d37cc4b408b507dcde9d9a5ef.png
[c05846beeeed42dd074f232d22546ce2.png]: /images/20220828/3bda4b1215c94736ae8530fb5fad4b27.png
[d8ef40ce794180600635c4312e43e776.png]: /images/20220828/9b4da08c33614ae3b9a0a70234166143.png