Redis为什么那么快?

数据库有很多,为什么Redis能有如此突出的表现呢?一方面,因为它是内存数据库,所有操作都在内存上完成。另外一方面就要归功于他的数据结构。高效的数据结构是Redis快速处理的基础。今天我们就来聊聊了Redis的数据类型以及对应的数据结构。

首先Redis有5大基本类型:

1.String(字符串)

2.List(列表)

3.Hash(哈希)

4.Set(集合)

5.Zset(Sorted Set 有序集合)

他们的底层实现简单来说一共有6种,分别是简单的动态字符串、双向链表、压缩列表、哈希表、跳表以及整数数组。他们和数据类型的对应关系如下所示:

可以看到这些数据结构都是值的底层实现,那键和值之间是用什么数据结构来进行组织的呢?为了实现从键到值的快速访问,Redis使用了一个哈希表来保存所有的键值对。

哈希表的最大好处很明显,就是可以以O(1)的时间复杂度来快速查找到键值对。但他有一个潜在的风险点,当你往Redis里写入大量的数据就会出现哈希表的冲突问题以及rehash带来的操作阻塞问题。

Redis解决哈希冲突的方式,就是链式哈希。链式哈希很容易理解,就是指同一个hash桶中的多个元素用一个链表来保存。如下图所示:

这就出现一个问题,哈希冲突链表上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多,哈希冲突也会越来越多,这就会导致某些哈希冲突链过长,进而导致链上的元素查找耗时长,效率低。这对求快的redis来说是不能接受的。

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

为了使rehash更高效,Redis默认使用2个全局哈希表:哈希表1和哈希表2。一开始,当你刚插入数据时,默认使用哈希表1,此时哈希表2并没有分配空间。随着数据的增多,Redis开始执行Rehash。主要分为以下3步:

  1. 给哈希表2分配更大的空间。
  2. 把哈希表1的数据重新映射并拷贝到哈希表2。
  3. 释放哈希表1的空间。

到此我们可以从哈希表1切换到哈希表2,用容量更大的哈希表2来保存更多的数据,而原来的哈希表1留做下一次rehash扩容备用。

可以看到第二步会涉及到大量的数据拷贝,如果一次性把哈希表1全部都迁移完,会造成Redis线程阻塞,无法服务其他请求。为了避免这个问题,Redis采用了渐进式的Rehash。简单来说就是在第二步拷贝数据时,仍然正常处理客户端的请求,每处理一个请求,从哈希表1的第一个索引位置开始,顺带着将这个索引位置上的所有entries拷贝到哈希表2中;等处理下一个请求时,再顺带拷贝哈希表1的下一个索引位置的entries。这样就避免了一次性大量的数据拷贝,保证了数据的快速访问。

目前为止,你已经了解了Redis的键和值是怎么通过哈希表来组织的了,对于String类型来说,找到哈希桶就能直接增删改查了,所以哈希表O(1)的时间复杂度就是它的复杂度,但是对于集合类型来说,即使找到哈希桶了,还需要在集合中进一步操作。接下来我们就分别聊聊集合类型的底层数据结构和操作复杂度。

我们在上面已经了解到集合类型的底层结构主要有5种:整数数组、双向链表、哈希表、压缩列表和跳表。

其中,哈希表的操作特点我们已经学过;整数数组和双向链表也很常见,主要是通过数组下标和链表指针逐个访问元素,操作复杂度是O(N),操作效率比较低。压缩列表实际上类似于一个数组,和数组不同的是,压缩列表在表头有三个字段zlbytes、zltail和zllen,分别表示列表的长度、列表尾的偏移量和列表中元素的个数;压缩列表在表尾还有一个zlend表示列表结束。在压缩列表中,如果我们要查找定位第一个元素和最后一个元素,可以通过表头直接定位,时间复杂度为O(1)。而查找其它元素时,就没有那么高效了,只能逐个查询,时间复杂度为O(N)。

图片

下面我们来重点看一下跳表。有序链表只能逐一查找元素,导致操作起来非常缓慢,于是就出现了跳表。跳表是在链表的基础上增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位。如图所示:

图片

可以看到,这个查找过程就是在多级索引上跳来跳去,最后定位到元素。当数据量很大时,跳表的查找复杂度是O(logN)。

图片

好了,今天就分享到这里,如果有什么问题,可以在留言区留言。

Tags: