Redis有哪些慢操作

￡神魔★判官ぃ 2022-12-20 01:29 262阅读 0赞

## redis 数据类型与底层数据结构的关系 ##

![在这里插入图片描述][2020110911112178.png_pic_center]  
可以看到，String 类型的底层实现只有一种数据结构，也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。redis 3.2后引入了quicklist结构

## 键和值用什么结构组织 ##

Redis 使用了一个哈希表来保存所有键值对。  
一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。所以，我们常说，一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。  
**哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center]  
潜在的风险点:

1.  哈希表的冲突问题
2.  rehash 可能带来的操作阻塞

## 为什么哈希表操作变慢了？ ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center 1]  
当哈希冲突变多后，将哈希遍历退化成链表遍历，导致查询变慢，这时需要rehash来重建哈希表。  
Redis 会对哈希表做 rehash 操作, 为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表:

1.  哈希表 1
2.  哈希表 2

一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：

1.  给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
2.  把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中，**Redis 采用了渐进式 rehash。**
3.  释放哈希表 1 的空间。

### 渐进式 rehash ###

简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center 2]

1.  对于 String 类型来说，找到哈希桶就能直接增删改查了，所以，哈希表的 O(1) 操作复杂度也就是它的复杂度了。
2.  对于集合类型来说，即使找到哈希桶了，还要在集合中再进一步操作。

## 集合数据操作效率 ##

## 有哪些底层数据结构？ ##

集合类型的底层数据结构主要有 5 种：

1.  整数数组
2.  双向链表
3.  哈希表
4.  压缩列表
5.  跳表

### 压缩列表 ###

压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail 和 zllen，分别表示列表长度、列表尾的偏移量和列表中的 entry 个数；压缩列表在表尾还有一个 zlend，表示列表结束。  
![在这里插入图片描述][20201109113140586.png_pic_center]

1.  查找第一个或最后一个元素可以根据属性, O(1)
2.  其它位置, O(n)

### 跳表 ###

跳表在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位，如下图所示  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center 3]

## 数据结构的时间复杂度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center 4]

## 不同操作的复杂度 ##

集合常见操作的复杂度:

1.  单元素操作是基础；O(1)
2.  范围操作非常耗时；O(n)
3.  统计操作通常高效；O(1), 比如计算集合的长度, 因为内部记录统计信息, 可以直接获取
4.  例外情况只有几个；O(1), 比如操作双向链表的头/尾

## 小结 ##

Redis 之所以能快速操作键值对，一方面是因为 O(1) 复杂度的哈希表被广泛使用，包括 String、Hash 和 Set，它们的操作复杂度基本由哈希表决定，另一方面，Sorted Set 也采用了 O(logN) 复杂度的跳表。不过，集合类型的范围操作，因为要遍历底层数据结构，复杂度通常是 O(N)。这里，我的建议是：用其他命令来替代，例如可以用 SCAN 来代替，避免在 Redis 内部产生费时的全集合遍历操作。

[2020110911112178.png_pic_center]: /images/20221120/67ca266940fa4c848e588a69651cb38c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201109112149436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201109112323666.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201109112808883.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg=,size_16,color_FFFFFF,t_70#pic_center
[20201109113140586.png_pic_center]: https://img-blog.csdnimg.cn/20201109113140586.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201109113240351.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201109113354926.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNDY4OTg=,size_16,color_FFFFFF,t_70#pic_center