Redis数据都是怎么存储的？

1 Redis中的数据结构

Redis是目前最流行的内存数据库之一，而redis成为最流行的原因就是’快’，即在微妙级别就能够通过键找到对应的值并返回。那么很多人就会问redis为何这么快呢？除了其读写操作都在内存中执行和独特的网络模型设计，以及其巧妙的数据结构之外，还要归功于独特的键值对存储结构。对于redis的网络模型和具体的数据结构后续篇幅再进行讲解，此篇文章仅对于redis中键值对数据的存储进行分析。

2 键值对数据如何存储的

相信大多数人都知道redis的值有5种数据结构，分别为String(字符串)，List(列表)，Hash(哈希)，Set(集合)，Sorted Set(有序集合)，而此篇文章主要探讨redis中的键值对数据是如何保存的。其实redis使用的是一个哈希表来存储所有的键值对数据，如下图所示：

看到这张图相信大家会想到另外一个Java中的数据结构HashMap，是的优秀的数据结构设计总是被应用到各个地方。好了下面来分析一下为何redis也采用这种设计来保存键值对数据：

首先，能够在O(1)的时间复杂度内快速找到需要的键值对数据，只需要将需要找的键通过hash算法找到对应的hash桶，即可找到对应的entry键值对数据。
其次entry中存储的并非实际的键值对数据值，而是键值对对应的指针，这样不管采用哪种数据结构都能通过指针找到对应的值。

那么是不是这种设计就没有缺点了呢？相信很多了解HashMap数据结构的同学开始battle了，那就是随着数据的增多必然会出现哈希冲突，也就是可能会出现多个key的哈希值相同，那么多个entry就会同时出现在一个哈希桶中。当然我们能够想到这一点，redis作者肯定也就想到了这一点，那么是怎么进行设计呢？肯定很多同学都会想到了跟HashMap一样，将key哈希值相同的entry用链表进行保存(最新java版本的HashMap使用的为红黑树代替链表)，每个entry之间使用指针进行相连，如下图所示

从图中可以看出当多个entry同时出现在一个哈希桶时，每个entry之间使用指针相连接，如图中所示的entry1，entry2，entry3使用next指针进行相连，因此无论有多少entry落入相同的哈希桶中都可以使用指针进行连接形成entry链表，也即是哈希冲突链。

解决了哈希冲突是不是就万事大吉了呢？相信有心的同学肯定会给出否定的答案。试想一下如果如果落入同一个哈希桶中的key很多，那么哈希冲突链就会变得很长，当查询的时候会遍历此链表(哈希冲突链)，而链表的遍历最坏的情况时O(n)的，这对于快速读取数据的redis来说是不可能接受的。那redis是如何来解决这种情况呢？相信了解HashMap数据结构的已经给出了答案，那就是rehash操作，那么下面就来讲解一下redis是如何进行rehash操作的。

3 redis的rehash操作

rehash其实就是增加哈希桶的数量，从而使entry能够更分散的分布在不同的哈希桶中，从而将少entry在单个哈希桶中的冲突。

那么redis何时进行rehash呢？这个要取决于哈希表的负载因子(used/size)，其中used为哈希表中保存的节点数量，size为哈希表大小。

a. 如果没有进行bgsave 元素数量达到hash长度时就会扩容（负载因子大于等于 1）

b. 如果进行bgsave，元素数量达到hash长度的5倍会进行扩容（负载因子大于等于 5）

仔细思考会发现哈希表的负载因子其实是动态变化的，那么就有人考虑，如果负载因子很低是不是会进行收缩操作呢？答案是会的，当负载因子小于0.1的时候redis就会进行收缩操作。

了解了redis何时进行rehash操作，那redis是如何进行rehash操作的呢？redis会分配两个hash表，比如为hash_table1和hash_table2，首先使用的hash_table1进行数据的插入和读取，初始时候hash_table2的大小为hahs_table1的两倍，在rehash过程中将hash_table1的数据进行重新分配到hash_table2中，然后使用hash_table2进行redis’数据的读取和写入，最后将hash_table1的空间释放做后续rehash使用。

看了上面的过程觉得rehash也挺简单的嘛，但事实却并非如此，试想一下在将hash_table1中的数据拷贝到hash_table2并进行重新分配的过程中，redis是阻塞的即不能对外提供服务，这对于高性能要求的redis是绝对不可能的，所以就出现了下面要讲解的渐进式rehash操作。

4 渐进式rehash

简单来讲就是redis每处理一个客户端请求，就将hash_table1中从第一个索引位置开始，将此索引下面所有entry重新映射到hash_table2中对应的索引位置。然后接着处理下一个客户端请求时候将第二个索引位置下面entry重新映射并拷贝到hash_table2上，以此进行直到hash_table1上所有entry都拷贝到对应的hash_table2的索引位置上，如下图所示。