redis key-value 存储结构及扩容
# 全局key-value存储结构
redis 是一个key-value数据库（当然value本身也支持很多数据类型），和 java 的 HashMap 一样，内部是使用数组+链表实现的 hash 存储结构。
# redis 如何解决哈希冲突问题
随着元素数量增加，哈希冲突的元素会比较多，查询复杂度会从O(1)退化成O(N)。这时候就需要考虑如何扩容数组数量来减少哈希冲突。
redis 对全局哈希表做扩容，称为rehash。内部会有两个哈希表，一个用于数据存储（ht[0]），另一个用来扩容（ht[1]）。
扩容步骤：
- 为ht[1]分配一个更大的空间
- 将ht[0]数据拷贝到ht[1]
- 释放ht[0]，作为下次
rehash的扩容哈希表
在第二部迁移数据时，redis 会阻塞用户请求，如果数据量比较大，会影响性能，所以 redis 采用了渐进式迁移方案。
- 次接收用户请求时，就会从ht[0]的数组下标0的位置开始迁移 entry 数据，每次只迁移一部分，避免长时间阻塞用户请求
- 后台线程周期性迁移数据
在rehash过程中，查找、删除、更新操作会在两个哈希表进行（双写），新增操作只在ht[1]进行。
源码：https://github.com/redis/redis/blob/unstable/src/dict.c#L1063 (opens new window)