《Redis设计与实现》读书笔记（二）
——Redis中的字典（Hash）
（原创内容，转载请注明来源，谢谢）
一、概述
字典，又称符号表、关联数组、映射，是一种保存键值对的抽象数据结构。每个键（key）和唯一的值（value）关联，键是独一无二的，通过对键的操作可以对值进行增删改查。
redis中字典应用广泛，对redis数据库的增删改查就是通过字典实现的。即redis数据库的存储，和大部分关系型数据库不同，不采用B+tree进行处理，而是采用hash的方式进行处理。
另外，毫无疑问，redis的hash数据类型也是通过字典方式实现。
二、字典的实现
redis的字典，底层是使用哈希表实现，每个哈希表有多个哈希节点，每个哈希节点保存了一个键值对。
1、哈希表
typedef structdictht{
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
}dictht;
其中，table是一个数组，里面的每个元素指向dictEntry（哈希表节点）结构的指针，dictEntry结构是键值对的结构；size表示哈希表的大小，也是table数组的大小；used表示table目前已有的键值对节点数量；sizemask一直等于size-1，该值与哈希值一起决定一个属性应该放到table的哪个位置。
大小为4的空哈希表结构如下图（左边一列的图）所示：
2、哈希表节点
typedef structdictEntry{
void *key;
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
struct dictEntry *next;
}dictEntry;
其中，key表示节点的键；union表示key对应的值，可以是指针、uint64_t整数或int64_t整数；next是指向另一个哈希表节点的指针，该指针将多个哈希值相同的键值对连接在一起，避免因为哈希值相同导致的冲突。
哈希表节点如下图（左边第一列是哈希表结构，表节点结构从左边第二列开始）所示：
3、字典
1）dict
typedef structdict{
dictType *type;
void *privdata;
dictht ht[2];
int rehashidx;
}dict;
其中，type用于存放用于处理特定类型的处理函数，下面会提；privdata用于存放私有数据，保存传给type内的函数的数据；rehash是一个索引，当没有在rehash进行时，值是-1；ht是包含两个项的数组，每个项是一个哈希表，一般情况下只是用ht[0]，只有在对ht[0]进行rehash时，才会使用ht[1]。
2）dictType
typedef structdictType{
unsigned int (*hashFunction) (const void *key);
void *(*keyDup) (void *privdata, const void *key);
void *(*valDup) (void *privdata, const void *obj);
int *(*keyCompare) (void *privdata, const void *key1, const void*key2);
void *(*keyDestructor) (void *privdata, void *key);
void *(*valDestructor) (void *privdata, void *obj);
}dictType;
该结构体定义了字典的各种操作函数，hashFunction是哈希值计算函数，keyDup是键复制，valDup是值复制，keyCompare是键比较，keyDestructor是键销毁，valDestructor是值销毁。
完整的字典结构如下图所示：
三、哈希算法
要将新的键值对加到字典，程序要先对键进行哈希算法，算出哈希值和索引值，再根据索引值，把包含新键值对的哈希表节点放到哈希表数组指定的索引上。
redis实现哈希的代码是：
hash =dict->type->hashFunction(key);
index = hash& dict->ht[x].sizemask;
算出来的结果中，index的值是多少，则key会落在table里面的第index个位置（第一个位置index是0）。
其中，redis的hashFunction，采用的是murmurhash2算法，是一种非加密型hash算法，其具有高速的特点。
而hash的结果，还需要和sizemask进行二进制的&计算，由于sizemask一直都是size-1，因此保证没有数据的情况下必定放在table的第一个位置，而其后的值按照表格顺序往下排的可能性也很大。
四、键冲突解决
当两个或者以上的键，算出来的第三步的index的值一样，则称为有冲突。
为了解决此问题，redis采用链地址法，每个哈希表节点都有一个指向next的指针，当发生冲突时，直接将当前哈希表节点的next指针指向新的结果。后面如果还有冲突的键，则当前键的next会指向下一个哈希表节点。
五、rehash（重新散列）
随着操作进行，哈希表保存的键值对会增加或减少，为了让哈希表的负载因子（load factor）维持在一个合理范围，当一个哈希表保存的键太多或者太少，需要对哈希表进行扩展或者收缩。扩展或收缩哈希表的过程，就称为rehash。
rehash步骤如下：
1、给字典的ht[1]申请存储空间，大小取决于要进行的操作，以及ht[0]当前键值对的数量（ht[0].used）。假设当前ht[0].used=x。
1）如果是扩展，则ht[1]的值是第一个大于等于x*2的2n的值。例如x是30，则ht[1]的大小是第一个大于等于30*2的2n的值，即64。
2）如果是收缩，则ht[1]的值是第一个大于等于x的2n的值。例如x是30，则ht[1]的大小是第一个大于等于30的2n的值，即32。
2、将保存在ht[0]上面的所有键值对，rehash到ht[1]，即对每个键重新采用第三大点哈希算法的方式计算哈希值（index的值），再放到相应的ht[1]的表格指定位置。
3、当ht[0]的所有键值对都rehash到ht[1]后，释放ht[0]，并将ht[1]设置为ht[0]，再新建一个空的ht[1]，用于下一次rehash。
六、rehash条件
1、负载因子（load factor）计算
load_factor =ht[0].used / ht[0].size，即负载因子大小等于当前哈希表的键值对数量，除以当前哈希表的大小。
2、扩展
当以下任一条件满足，哈希表会自动进行扩展操作：
1）服务器目前没有在执行BGSAVE或者BGREWRITEAOF命令，且负载因子大于等于1。
2）服务器目前正在在执行BGSAVE或者BGREWRITEAOF命令，且负载因子大于等于5。
要判断是否在进行bgsave或bgwriteaof，是因为这两个命令执行过程中，redis需要创建当前服务器进程的子进程，而大多数操作系统又都是用写时复制（copy-on-write）技术优化子进程的使用效率。
因此，在执行这两个命令期间，redis会提高哈希表扩展操作的负载因子，以避免不必要的数据写入内存（例如ht[1]建立好而ht[0]尚未清空清空下，同时存在两份数据），最大限度节约内存。
3、收缩
当负载因子小于0.1时，redis自动开始哈希表的收缩工作。
4、copy-on-write简介
写时复制技术，是操作系统层面，为了提升性能而进行的一个策略。
策略如下：每次写文件操作，都写在特定大小的一块内存中（磁盘缓存），并不是直接写到磁盘中。只有当我们关闭文件时，才写到磁盘上（这就是为什么如果文件不关闭，所写的东西会丢失的原因）。更有甚者是文件关闭时都不写磁盘，而一直等到关机或是内存不够时才写磁盘，Unix就是这样一个系统，如果非正常退出，那么数据就会丢失，文件就会损坏。
写时复制技术，大大降低了磁盘I/O的次数，而I/O往往是性能瓶颈，这样一来就最大程度上避免了此瓶颈。
七、渐进式rehash
redis对ht[0]扩展或收缩到ht[1]的过程，并不是一次性完成的，而是渐进式、分多次的完成，以避免如果哈希表中存有大量键值对，一次性复制过程中，占用资源较多，会导致redis服务停用的问题。
渐进式rehash过程如下：
1、为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两张哈希表。
2、将字典中的rehashidx设置成0，表示正在rehash。rehashidx的值默认是-1，表示没有在rehash。
3、在rehash进行期间，程序处理正常对字典进行增删改查以外，还会顺带将ht[0]哈希表上，rehashidx索引上，所有的键值对数据rehash到ht[1]，并且rehashidx的值加1。
4、当某个时间节点，全部的ht[0]都迁移到ht[1]后，rehashidx的值重新设定为-1，表示rehash完成。
渐进式rehash采用分而治之的工作方式，将哈希表的迁移工作所耗费的时间，平摊到增删改查中，避免集中rehash导致的庞大计算量。
在rehash期间，对哈希表的查找、修改、删除，会先在ht[0]进行。如果ht[0]中没找到相应的内容，则会去ht[1]查找，并进行相关的修改、删除操作。而增加的操作，会直接增加到ht[1]中，目的是让ht[0]只减不增，加快迁移的速度。
八、总结
字典在redis中广泛应用，包括数据库和hash数据结构。每个字典有两个哈希表，一个是正常使用，一个用于rehash期间使用。当redis计算哈希时，采用的是MurmurHash2哈希算法。哈希表采用链地址法避免键的冲突，被分配到同一个地址的键会构成一个单向链表。在rehash对哈希表进行扩展或者收缩过程中，会将所有键值对进行迁移，并且这个迁移是渐进式的迁移。
——written by linhxx 2017.08.29
