Redis有哪些潜在的慢操作？

周末的时间，学了一下redis。

Redis作为内存数据库，访问速度快是最大的特点，那么，什么情况下，Redis也会变慢呢？

Redis底层数据结构

Redis有5种基本数据类型：String，List，Hash，Set，ZSet

有6种底层数据结构：

• • 简单动态字符串SDS
• • 压缩列表 ZipList
• • 快表 QuickList
• • 字典/哈希表 Dict
• • 整数集 IntSet
• • 跳表 ZSkipList

键值访问

Redis用了一个全局的哈希表保存所有的键值对，一个哈希表，其实是一个数组，数组里的每一个元素对应为一个哈希桶。每个哈希桶保存键值对数据。

哈希桶中元素保存的是指向值的地址指针，这样即使值是一个集合，也能通过指针找到。

如图是全局哈希表的键值访问过程：

哈希表的查找依赖哈希计算，O(1)的时间复杂度找到键值对。

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

既然是哈希表，可能存在哈希冲突。redis解决哈希冲突的方法是链地址法，即同一个哈希桶中的多个元素用一个链表来保存，它们之间用指针相连。

看到这，肯定有个疑问，如果冲突的元素越来越多，就会导致在这个链上查找的耗时变长，对于追求快的Redis来说，这是不能接受的。

所以，Redis会对哈希表做rehash操作。可以理解为和Java里的HashMap扩容一样。增加现有哈希桶数量，让增多的元素在更多的桶之间分散保存。

redis中rehash的方法是：

1. redis默认使用了2个全局哈希表
2. 当插入数据时，默认使用哈希表1
3. 随着数据增多，redis进行rehash操作，为哈希表2分配更大的内存空间，如是哈希表1的两倍；
4. 把哈希表1中的数据重新映射到哈希表2中
5. 释放哈希表1的内存

其中 数据重新映射 这一步涉及大量数据拷贝，如果让主线程一次全部迁移完，会造成redis线程阻塞。

为了避免这一问题，redis使用了渐进式rehash

简单地说，就是在拷贝数据过程中，不是一次拷贝完。而是每处理一个请求时，从哈希表1的第一个索引位置开始，将这个位置上所有元素拷贝到哈希表2中，等处理下一请求时，再拷贝下一索引位置的数据，整个过程如下：

集合数据结构的操作

集合类型的底层结构是：整数数组，双向链表，哈希表，压缩列表，跳表

哈希表、整数列表、双向链表的操作特征都是顺序读写，操作复杂度是O(N)，效率比较低。

压缩列表：

• • 类似数组，表头有3个字段zlbytes、zltail、zllen，分别表示列表长度、列表尾的偏移量、列表中entry个数。
• • 表尾还有一个zlend，表示列表结束

查找定位列表的第一个元素和最后一个元素，可以通过表头3个字段的长度直接定位，复杂度O(1)，查找其他元素时，只能逐个查找了，复杂度O(N)。

跳表

• • 跳表是在链表的基础上，增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位

如图所示，

• • 单链表查找元素33，需要找6次；
• • 增加一级索引（每两个元素选一个出来作为索引，索引再通过指针指向原始链表），只需要找4次；
• • 增加二级索引（从一级索引中再抽取部分元素作为二级索引），只需要找3次；

当数据量很大时，跳表查找的复杂度是O(logN)

redis底层数据结构查找的时间复杂度如下表：

思考：压缩列表和整数数组的查找时间复杂度比较高，为什么redis还要用它们呢？

• • 内存利用率数组和压缩列表都是非常紧凑的数据结构，比起链表，占用的内存更少，而redis是内存数据库，需要尽可能的优化，提高内存利用率；
• • 数组对CPU高速缓存支持更友好