Redis为什么这么快?
时至今日, 可以选择的数据库有很多, 为什么Redis能有这么突出的表现呢
一方面是因为它是内存数据库, 所有的操作都在内存上完成. 另一方面, 这要归功于它的数据结构.
Redis一共支持五种数据类型, 包括String(字符串), List(列表), Hash(哈希), Set(集合)和Sorted Set(有序集合). 而它们的底层实现数据结构其实有六种, 分别是简单动态字符串, 整数数组, 双向链表, 压缩列表, 哈希表和跳表. 它们和五种数据类型的对应关系如下图所示:
可以看到, String类型的底层只有一种数据结构, 而List/Hash/Set/Sorted Set都有两种底层实现结构. 通常情况下我们把这四种类型成为集合类型, 它们的特点是一个键对应了一个集合的数据.
如何组织键和值?
为了实现从键到值的快速访问, Redis使用了一个哈希表来保存所有键值对. 一个哈希表其实就是一个数组, 数组的每个元素称为一个哈希桶, 每个哈希桶中保存了键值对数据. 哈希桶中的元素并不是值本身, 而是指向具体值的指针
使用哈希表最大的好处很明显, 就是可以让我们以O(1)的时间复杂度来快速找到键值对
为什么哈希操作变慢了?
但是, 当你往Redis中写入大量数据后, 可能会发现有的操作突然变慢了, 这是因为哈希表的潜在风险点 —- 哈希冲突问题和rehash操作可能带来的阻塞.
Redis使用链式哈希来解决哈希冲突, 所谓链式哈希, 就是指同一个哈希桶中的多个元素用一个链表来保存, 它们之间依次用指针连接.
但即使如此, 仍然存在一个问题, 如果哈希表写入的数据越来越多, 哈希冲突也会越来越多, 这就导致某些哈希冲突链过长, 进而导致在这个链上查找元素耗时变长. 所以, Redis会对哈希表做rehash操作, 也及时增加现有的哈希桶数量, 让entry元素更加均匀地分散在哈希桶之间, 减少单个哈希桶中的元素数量, 从而减少哈希冲突的发生.
为了使rehash操作更高效, Redis默认使用了两个全局哈希表. 一开始, 当你插入数据时, 默认使用哈希表1, 此时哈希表2并没有分配空间. 随着数据量增加, Redis开始执行rehash, 这个过程分为三步:
1. 为哈希表2分配更大的空间, 例如当前哈希表1的两倍大小
2. 将哈希表1中的数据重新映射到哈希表2中
3. 释放哈希表1的空间, 并留作下一次rehash时备用
在这个过程中, 第二步涉及大量的数据拷贝, 如果一次性把哈希表1中的数据全都迁移到表2中, 会导致Redis线程阻塞. 为了避免这个问题, Redis采用了渐进式rehash. 简单来说, 就是在进行第二步数据拷贝时, Redis仍然正常处理客户端请求, 但是每处理一个请求, 就把对应的哈希桶上的所有entry拷贝到哈希表2中; 等处理下一个请求时, 再迁移对应数据
这样一来, 原本大量的迁移开销被分摊到了多次处理请求的过程中, 避免了耗时操作, 保证了数据的快速访问.
特殊的数据结构
在集合类型的物种底层数据结构中, 压缩列表和跳表比较少见.
压缩列表
压缩列表实际上类似于一个数据, 和数组不同的是压缩列表在表头有三个字段zlbytes, zltail和zllen, 分别表示列表长度/列表尾部的偏移量和列表中的entry数量. 在压缩列表表尾还有一个zlend, 表示列表结束
在压缩列表中, 如果我们要查找第一个元素和最后一个元素, 可以通过表头的三个字段直接定位, 复杂度是O(1). 而查找其他元素时只能逐个遍历, 此时复杂度是O(N).
跳表
跳表是在链表的基础上, 增加了多级索引, 通过索引位置的快速跳转, 实现数据的快速定位, 如图所示
跳表的时间复杂度是O(logN)
不同操作的时间复杂度
单元素操作
每一种集合类型对单个数据的增删改查操作的复杂度, 由实际集合所使用的数据结构决定. 例如对Hash类型而言, 使用压缩列表时, HGET/HSET和HDEL等操作的复杂度是O(N), 如果是对哈希表操作, 它们的复杂度就是O(1); 同样, 对Set类型来说, 当使用整数数组作为底层数据结构时, SADD/SREM/SRANDMEMBER等操作的复杂度是O(N), 当使用哈希表时, 复杂度就是O(1)
范围操作
范围操作是指集合类型中的遍历操作, 可以返回集合中的所有数据比如Hash类型的HGETALL和Set类型的SMEMBERS, 或者是返回一个范围内的部分数据, 比如List类型的LRANGE和ZSet类型的ZRANGE, 这类操作的复杂度一般都是O(N), 我们应该尽量避免这类耗时操作
不过Redis从2.8版本开始提供SCAN系列操作, 这类操作实现了渐进式遍历, 每次只返回有限数量的数据, 这样就避免了一次性返回所有元素而导致Redis阻塞.
统计操作
这类操作一般复杂度都是O(1), 这是因为压缩列表/双向链表/整数数组等数据结构中专门记录了元素的个数统计, 因此可以高效地完成相关操作.
例外情况
压缩列表和双向链表都会记录表头和表尾的偏移量, 这样一来, 对于List类型的LPOP/RPOP/LPUSH和RPUSH等操作而言, 它们的复杂度也只有O(1).
为什么使用整数数组和压缩列表?
整数数组和压缩列表在查找的时间复杂度方面并没有很大的优势, 为什么Redis还会把它们作为底层数据结构呢? 这有两方面原因
1. 内存利用率, 数据和压缩列表都是紧凑的数据结构, 它们比链表占用更少的内存.
Redis是内存数据库, 要做到尽可能的优化, 提高内存的利用率
2. 数组对CPU高速缓存的支持更加友好, 所以Redis在设计时, 在集合数据量较小默认采用内存紧凑排列的方式存储, 同时利用CPU高速缓存不会降低访问速度.
当数据元素超过设定阈值后, 避免查询时间复杂度过高, 转为哈希表和跳表来存储数据, 保证查询效率
