Redis教程(四)---全局数据结构
Redis 为了操作效率使用哈希表来存储键值对，访问时只需要 O(1) 时间复杂度。
1. 全局哈希表
为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。
哈希表由多个哈希桶组成，哈希桶中的 entry 元素中保存了*key和*value指针，分别指向了实际的键和值。
哈希表让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。
key-value 访问过程：
- 通过 key 计算出对应的哈希值
- 根据哈希值计算出对应的哈希桶索引
- 根据索引找到对应 entry，如果是哈希链则挨个查找到对应的 entry
- String 类型则 entry 中的 value 就是要查找的值，集合类型则需要在 value 中进一步查找
2. 哈希冲突
当你往哈希表中写入大量数据时，哈希冲突是不可避免的问题。
哈希冲突也就是指，两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。
Redis 解决哈希冲突的方式，就是链式哈希（链地址法）。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。
但是，这里依然存在一个问题，哈希冲突链上的元素只能通过指针逐一查找再操作。
如果哈希表里写入的数据越来越多，哈希冲突可能也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时长，效率降低。
所以，Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。
3. Rehash
为了使 rehash 操作更高效，Redis 默认使用了两个全局哈希表：哈希表 1 和哈希表 2，下文将当前正使用的称作主哈希表，用于扩容的称作备用哈希表。
一开始，当你刚插入数据时，默认使用哈希表 1，此时的哈希表 2 并没有被分配空间。随着数据逐步增多，Redis 开始执行 rehash，这个过程分为三步：
- 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；
- 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；
- 释放哈希表 1 的空间。
到此，我们就可以从哈希表 1 切换到哈希表 2，用增大的哈希表 2 保存更多数据，而原来的哈希表 1 留作下一次 rehash 扩容备用。
为了避免第二步拷贝数据阻塞 Redis 主线程，Redis 采用了 渐进式 Rehash。
简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求。
- 每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；
- 等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。
即 每处理一个请求就从主哈希表拷贝一个哈希桶到备用哈希表。将一次拷贝拆分为多次拷贝从而减少拷贝过程中对 Redis 主线程的影响。
注意：
因为在进行渐进式 rehash 的过程中， 字典会同时使用 ht[0] 和 ht[1] 两个哈希表， 所以在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。
另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作： 这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。
4. 小结
- Redis 使用哈希表存储键值对
- 采用链地址法解决哈希冲突
- 为避免阻塞主线程，采用渐进式 Rehash
5. 参考资料
《Redis 设计与实现》
Redis 核心技术实战
https://en.wikipedia.org/wiki/Hash_table