1，概述
Redis是一个键值对（key-value pair）数据库服务器，Redis服务器结构是redis.h/redisServer结构表示，Redis服务器中的所有数据库保存在db数组中，数据库的结构是redis.h/redisDb，其中，redisDb结构的dict字典保存了数据库中的所有键值对，所以，说起Redis的扩容机制，指的就是字典中哈希表的rehash（重新散列）操作。
struct redisServer{
//..
//服务器的数据库数量
int dbnum;
//一个数组，保存着服务器中的所有数据库
redisDb *db;
//..
}
struct redisDb{
//..
//数据库键空间，保存着数据库中的所有键值对
dict *dict;
//..
}
2，字典的扩容机制
2.1，普通状态下的字典：
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privedata;
// 哈希表
dictht ht[2];
// rehash 索引
in trehashidx;
}
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}
typeof struct dictEntry{
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}
struct dictEntry *next;
}
2.2，解决哈希冲突
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上。
当有两个或以上数量的键被分配到了哈希表数组的同一个索引上时，称为哈希冲突，Redis的哈希表使用单向链表解决冲突，使用哈希表节点的next指针将冲突的节点连接起来，因为dictEntry节点组成的链表没有指向链表表尾的指针，为了速度考虑，总是将新节点添加的链表的表头位置（复杂度为O(1)）。
2.3，rehash
为了让哈希表的负载因子（load factor）维持在一个合理的范围内，会使用rehash（重新散列）操作对哈希表进行相应的扩展或收缩。
2.3.1，哈希表被扩展的条件：
1）Redis服务器目前没有在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
2）Redis服务器目前在执行BGSAVE命令或BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。
负载因子=哈希表已保存节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size
当哈希表的负载因子小于0.1时，对哈希表执行收缩操作。
2.3.2，rehash的操作步骤
1）为字典的ht[1]哈希表分配空间。
如果执行的是扩展操作，那么ht[1] 的大小为第一个大于等于ht[0] .used*2的2的n次幂
如果执行的是收缩操作，那么ht[1] 的大小为第一个大于等于ht[0].used 的2的n次幂
因此这里我们为ht[1] 分配 空间为8
2)将ht[0]中的数据转移到ht[1]中，在转移的过程中，重新计算键的哈希值和索引值，然后将键值对放置到ht[1]的指定位置。
数据转移后的结果：
3）当ht[0]的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），将ht[0]释放，然后将ht[1]设置成ht[0]，最后为ht[1]分配一个空白哈希表：
2.3.3，渐近式rehash
上面我们说到，在进行拓展或者压缩的时候，可以直接将所有的键值对rehash 到ht[1]中，这是因为数据量比较小。在实际开发过程中，这个rehash 操作并不是一次性、集中式完成的，而是分多次、渐进式地完成的。
渐进式rehash 的详细步骤：
1、为ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
2、在几点钟维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash 开始
3、在rehash 进行期间，每次对字典执行CRUD操作时，程序除了执行指定的操作以外，还会将ht[0]中的数据rehash 到ht[1]表中，并且将rehashidx加一
4、当ht[0]中所有数据转移到ht[1]中时，将rehashidx 设置成-1，表示rehash 结束
采用渐进式rehash 的好处在于它采取分而治之的方式，避免了集中式rehash 带来的庞大计算量。
参考书籍【Redis设计与实现】
文章：http://www.cnblogs.com/jaycekon/p/6227442.html
如有错误，请批评指正。
