Redis 为何这么快?
Redis 到底快在哪?它接收到一个键值对操作后,能以微秒级速度找到数据,并快速完成操作。
为啥就 Redis 这么突出?
它是内存数据库,所有操作都在内存上完成,内存的访问速度本身就很快
数据结构键值对是按一定的数据结构来组织的,操作键值对最终就是对数据结构进行增删改查操作,所以高效的数据结构是 Redis 快速处理数据的基础
String(字符串)、List(列表)、Hash(哈希)、Set(集合)和 Sorted Set(有序集合)只是 Redis 键值对中值的数据类型,即数据的保存形式。本文的数据结构,是研究其底层实现。
底层数据结构一共 6 种:简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。
List、Hash、Set 和 Sorted Set 这四种数据类型都有两种底层实现结构。通常称为集合类型:一个 K 对应一个集合的数据。
这些数据结构都是 V 的底层实现,K.V 之间用什么组织的?
为什么集合类型有这么多底层结构,是怎么组织数据的,都很快吗?什么是简单动态字符串,和常用的字符串是一回事吗?Redis 中有哪些潜在的“慢操作”,最大化 Redis 的性能优势。
键和值用什么结构组织?
为了实现从 K 到 V 快速访问,Redis 使用哈希表保存所有 KV 对。
其实就是一个数组,数组元素称为哈希桶。一个哈希表由多个哈希桶组成,每个哈希桶中保存 KV 对。
如果值是集合类型,数组元素的哈希桶怎么保存呢的?哈希桶中的元素保存的并非值本身,而是指向具体值的指针。即不管值是 String,还是集合类型,哈希桶中的元素都是指向它们的指针。
哈希桶中的 entry 元素中保存了*key
和*value
,分别指向实际的 K、V。即使值是个集合,也可通过*value
指针查到。
因为这哈希表保存了所有的键值对,所以,我也把它称为全局哈希表。全局指 Redis 数据库中的所有 kv,是由一个哈希表来索引的。通过在这个哈希表中查询 key,就可以找到对应 v。然后根据 v 具体类型(如 Hash,Set,List),再通过 v 的底层数据结构来读取具体的 value 数据,例如 List 通过双向链表来读取数据。
哈希表造就 O(1)快速查找 KV 对,只需计算 K 的哈希值,即可知其对应哈希桶位置,然后就能访问相应 entry 元素。
这个查找过程主要依赖哈希计算,和数据量无直接关系。不管哈希表有 10 万个 K 还是 100 万,只需一次计算,就能找到对应 K。
若你只是了解哈希表的 O(1)复杂度和快速查找特性,那当你往 Redis 写入大量数据后,就可能发现操作有时候会突然变慢。因为你忽略了潜在风险:哈希表冲突问题和 rehash 可能带来操作阻塞。
为什么哈希表操作变慢了?
当你往哈希表中写入更多数据,就会哈希冲突。Redis 通过链式哈希解决:同一哈希桶中的多个元素用链表保存。
entry1、entry2 和 entry3 都要保存在哈希桶 3:entry1 会通过一个*next
指向 entry2,以此类推。这就形成了一个链表,也叫哈希冲突链。
哈希表数据越多,哈希冲突可能也越多,导致某些哈希冲突链过长,该链上的元素查找耗时长,效率降低。这对求“快”的 Redis 无法接受。
所以,Redis 会对哈希表做
rehash
增加现有哈希桶数量,让逐渐增多的 entry 元素能在更多的桶之间分散保存,减少单个桶中的元素数量,从而减少单个桶中的冲突。
为使 rehash 操作更高效,Redis 默认使用了两个全局哈希表:刚插入数据时,默认使用哈希表 1,哈希表 2 尚未被分配空间。随着数据逐步增多,Redis 开始执行 rehash:
给哈希表 2 分配更大的空间,例如是当前哈希表 1 大小的两倍
把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中
释放哈希表 1 的空间
至此,即可从哈希表 1 切换到哈希表 2:
更大的哈希表 2 保存数据
哈希表 1 留作下次 rehash 扩容备用
step2 涉及大量数据拷贝,若一次性把哈希表 1 中的数据都迁移完,会造成 Redis 线程阻塞,无法服务其他请求,Redis 就无法快速访问数据了。为解决该问题,Redis 采用渐进式 rehash。
step2 拷贝数据时,Redis 仍可正常处理客户端请求:
每处理一个请求时,从哈希表 1 中的第一个索引位置开始,顺带将该索引位置的所有节点复制到哈希表 2
等到处理下一个请求时,再复制哈希表 1 中的下一个索引位置的节点们
这就把一次性大量拷贝开销,分摊到多次处理请求过程:
避免了耗时操作
保证了数据访问的快
对 String,找到哈希桶就能直接增删改查了,所以,哈希表的 O(1)操作复杂度也就是它的复杂度了。
但对集合类型,即使找到哈希桶了,还要在集合中进步操作。
dict 的渐进式 rehash 是为了避免扩容时的整体拷贝,这会给内存带来较大压力。
集合数据操作效率
一个集合类型的值:
通过全局哈希表找到对应的哈希桶位置
在集合中再增删改查
影响因素
底层数据结构
使用哈希表实现的集合,要比使用链表实现的集合访问效率更高。操作效率和这些操作本身的执行特点有关,比如读写一个元素的操作要比读写所有元素的效率高。
整数数组和双向链表都是顺序读写,时间复杂度基本是 O(N),效率较低。
压缩列表
类似数组,数组中每个元素对应一个数据。而压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。
第一个元素、最后一个元素,可通过表头三字段的长度直接定位,复杂度 O(1)
查找其他元素时,就只能逐个查找,复杂度 O(N)
跳表
有序链表只能逐一查找元素,非常慢,于是出现跳表。跳表基于链表,增加多级索引,通过索引位置跳转,快速定位数据:
查找过程就是在多级索引上跳来跳去,最后定位到元素。故名“跳”表。数据量很大时,跳表查找复杂度 O(logN)。
不同操作的复杂度
不同操作的复杂度
集合类型的操作类型:
读写单个集合元素的如 HGET、HSET
操作多个元素的如 SADD
遍历整个集合操作如 SMEMBERS
各种骚操作复杂度不尽相同,事关选型。
单元素操作
每种集合类型对单个数据实现的 crud 操作。例如,Hash 类型的 HGET、HSET 和 HDEL,Set 类型的 SADD、SREM、SRANDMEMBER 等。这些操作的复杂度由集合采用的数据结构决定,如:
HGET、HSET 和 HDEL 操作哈希表,所以复杂度都是 O(1)
Set 类型用哈希表作为底层数据结构时,SADD、SREM、SRANDMEMBER 复杂度也是 O(1)
集合类型支持同时对多个元素进行增删改查,如:
Hash 类型的 HMGET 和 HMSET
Set 类型的 SADD 也支持同时增加多个元素
这些操作的复杂度,就是由单个元素操作复杂度和元素个数决定的。如 HMSET 增加 M 个元素时,复杂度就从 O(1)变成 O(M)。
范围操作
集合类型中的遍历操作,可返回集合所有数据,如 Hash 类型的 HGETALL 和 Set 类型的 SMEMBERS,或者返回一个范围内的部分数据,如:
List 类型的 LRANGE
ZSet 类型的 ZRANGE
复杂度一般是 O(N),应尽量避免。
Redis 从 2.8 版本开始提供 SCAN 系操作(HSCAN,SSCAN 和 ZSCAN),实现渐进式遍历,每次只返回有限数量的数据。这相比 HGETALL、SMEMBERS,避免了一次性返回所有元素而导致 Redis 过久阻塞。
统计操作
集合类型对集合中所有元素个数的记录,例如 LLEN 和 SCARD。
复杂度只有 O(1),因为当集合类型采用压缩列表、双向链表、整数数组这些数据结构时,这些结构中专门记录了元素的个数统计,可高效完成。
例外情况
某些数据结构的特殊记录,例如压缩列表和双向链表都会记录表头和表尾的偏移量。这样一来,对于 List 类型的 LPOP、RPOP、LPUSH、RPUSH 这四个操作来说,它们是在列表的头尾增删元素,这就可以通过偏移量直接定位,所以它们的复杂度也只有 O(1),可以实现快速操作。
总结
Redis 之所以能快速操作键值对,因为:
O(1)复杂度的哈希表被广泛使用,包括 String、Hash 和 Set,它们的操作复杂度基本由哈希表决定
Sorted Set 也采用了 O(logN)复杂度的跳表
集合类型的范围操作,因为要遍历底层数据结构,复杂度通常是 O(N)。建议用其他命令来替代,如 SCAN 来代替,避免在 Redis 内部产生费时的全集合遍历操作。
List 底层实现结构:双向链表和压缩列表的操作复杂度都是 O(N)。因地制宜使用 List 类型。既然它的 POP/PUSH 效率很高,那就将它主要用于 FIFO 队列场景,而不是作为一个可随机读写的集合。
版权声明: 本文为 InfoQ 作者【JavaEdge】的原创文章。
原文链接:【http://xie.infoq.cn/article/04c1f4a2832706e3d08b83c6d】。文章转载请联系作者。
评论