redis学习笔记（一）数据结构

redis的快主要体现在我们可以根据键值对能以微妙级别的速度找到数据，并快速完成操作。

redis这样迅速的表现主要体现在以下几点：

（1）他是内存模式的非关系型数据库，所有操作都在内存上完成，内存的访问速度本身就很快。

（2）取决于redis合理的数据结构特性，键值对按一定的数据结构来存储，我们操作redis的键值对最终就是对数据结构进行增删改查操作，所以在合适的场景我们也应该采用合适的数据结构。

在平常开发中我们主要会用到这些数据结构，即：

（1）String - 字符串

（2）List - 列表

（3）Hash - 哈希

（4）Set - 集合

（5）Sorted Set - 有序集合

上述的数据结构中他们的底层也有着底层数据结构的实现，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数集合。他们对应的redis数据结构如下图所示：

可以看到，String类型的底层实现只有一种数据结构即简单动态字符串。其余四种数据结构底层实现都有两种实现结构。并且他们的相同点在于都属于集合类型，一个key对应这样一个集合的数据。

一、键值对如何存储

为了实现redis的快速访问，所以redis会使用一个哈希表来存储所有的键值对。

这里的哈希表和hashMap的思想一样，一个哈希表是一个数组，数组的每个元素叫做哈希桶，哈希桶中的元素保存的不是值的本身，而是指向具体值的指针。

redis的哈希表如下图所示：

Hash表最大好处在于可以以时间复杂度为O(1)来根据key快速查找到键值对，因为我们只需要计算key对应的hash值，在映射到hash桶位置，就可以访问这个key对应的entry元素。

但是Hash表的存在避免不了hash冲突问题，如果每一时刻往redis中插入了大量数据后，发现性能突然慢了，也有可能是hash表的冲突问题和扩容操作导致了操作阻塞。

二、redis的哈希表如何解决hash冲突

redis的哈希冲突示意图：

上述桶6中出现了hash冲突，hash冲突的存在会导致要查找entry3的key对应的value值时，只能先找到第一个entry1，再通过next指针依次进行查找。如果冲突越来越多，会导致这条链越来越长，查找性能降低。

为了解决上述的问题，redis采用了rehash操作，即对hash桶进行扩容，使entry数据更加散列保存在数组中。

先来看下普通的hashMap扩容的思想。

普通的hashMap是当entry数量达到一定阈值时，进行扩容，扩容后数组 = 扩容前数组 * 2。然后依次计算key的hash值，将value放到正确的位置中。

如果redis采用这种思想，可能会涉及到大量的数据拷贝，如果需要将扩容前的数据全部迁移完，会造成redis线程的阻塞，这在redis的使用中不是我们希望看到的。

· 渐进式rehash

为了避免上述的问题，redis采用了渐进式扩容方式。

redis默认使用了2个全局hash表，哈希表1和哈希表2。当扩容前或者刚插入数据时，默认使用hash表1。随着数据增多，开始进行rehash。进行如下操作：

1、给hash表2分配更大的空间，一般是hash表1的2倍。

2、如果没有请求，后台会有个子线程开启定时任务将hash表1中的数据重新映射并拷贝到hash表2中。

如果有请求，就不能一下子将hash表1中的数据全部拷贝给hash表2中，否则会造成阻塞。

此时redis仍可以正常处理客户端请求，每处理一个请求，从hash表1中的第一个索引位置开始，将这个索引下面的entry数据全部进行重新映射并拷贝给hash表2。

等处理下一个请求时，开始进行hash表1中下一个索引位置的entry数据的映射与拷贝。依次类推。

3、全部数据拷贝完毕，释放hash表1中的空间。

渐进式rehash如下图所示：

redis通过渐进式rehash的方式将一次性大量拷贝的开销分摊到了多次请求拷贝中，避免了阻塞操作。

三、集合数据操作效率 集合类型底层的数据结构主要分为整数数组、双向链表、哈希表、压缩列表和跳表。

整数数组、双向链表、哈希表比较常见，并且前2个的查询时间复杂度都是O(n)，哈希表的查询复杂度是0(1)。这里我们主要看下压缩列表和跳表。

· 压缩列表

压缩列表实际上和数组类似，数组中的每一个元素都保存数据，但是和数组不同的是有四个特殊字段zlbytes、zltail、zllen、alend分别来表示列表长度，列表尾的偏移量，列表中的entry个数，列表结束标记。

压缩列表如下图所示：

在压缩列表中，如果我们需要定位第一个元素或者最后一个元素可以通过表头的三个字段来直接进行定位，复杂度为O(1)，查找其他元素的话只能依次遍历查找，复杂度变为了O(n)。

· 跳表

有序列表只能遍历依次进行查找数据，而跳表是在有序列表的基础上建立多级索引，通过索引快速定位到数据。

跳表如下图所示：

如果不使用跳表，只使用普通的有序列表，那么查找50这个值，就需要遍历8次才能查询到。

如上图所示的跳表，只需要先在二级索引中判断50处于索引13和索引55之间。然后再去一级索引中判断50处于索引25和索引55之间，最后查找到50。只需要查找4次就可以查询到。

跳表的时间复杂度为O(logn)

· 数据结构的读取时间复杂度

1、哈希表 - O(1)

2、跳表 - O(logn)

3、双向链表 - O(n)

4、压缩列表 - O(n)

5、数组 - O(n)

四、总结

本文主要学习了redis的底层数据结构，首先是全局用来保存键值对的hash表，其次是底层的集合数据结构 - 双向链表、压缩列表、整数数组、哈希表和跳表。redis之所以能快速操作键值对，一方面可以通过键值对从hash表中快速的定位到元素。另一方面底层的数据结构也起到了决定作用。

比如支持排序的sorted set采用了压缩列表和跳表，set采用了哈希表和数组，hash采用了哈希表和压缩列表，list采用了双向链表和压缩列表。

问题一：整数数组和压缩列表在查找时间复杂度方面没有很大的优势，为什么redis还会把他们当做底层数据结构？

整数数组和压缩列表的设计，主要体现了redis可用这两个数据结构来节省空间，因为这2个数据结构，都是在内存中分配一块地址连续的空间，然后把集合一个接一个的放在这块空间内，非常紧凑，正式由于这个连续的空间和数据连续的放置我们不用像其他数据结构一样使用指针来串接起来，减少了创建指针时带来的空间开销。

问题二：redis什么时候做rehash？

redis会使用装载因子来判断是否需要rehash，装载因子 = 所有entry个数 ÷ 哈希桶的个数。结果分为2种情况。

1、装载因子 >= 1。

2、装载因子 >= 5。

第一种情况装载因子大于等于1，小于5的情况。如果计算结果是1，可以假设一个哈希桶保存了一个数据。如果有新的数据写入时，就需要采用链式哈希。如果此时redis没有进行aof和rdb的写入，那么就可以进行rehash。

第二种情况，装载因子大于等于5，表示当前的数据量远远大于哈希桶的个数，会有大量的哈希链存在，需要马上进行rehash操作。

问题三：采用渐进式rehash时，如果没有收到新的请求，是不是无法进行rehash？

redis的子线程会开启定时任务，在rehash被触发后，即使没有收到新请求，redis也会定时执行一次rehash操作。而且每次的rehash操作不会超过1ms，以免对其他操作造成影响。

参考资料 - 《Redis核心技术与实战》（数据结构：快速的Redis有哪些慢操作）