循序渐进——探索“字典”内部

字典是Redis服务器中出现最为频繁的复合型数据结构。

除了hash结构的数据会用到字典外。
整个Redis数据库的所有key和value也组成了一个全局字典。
还有带过期时间的key集合也是一个字典。
zset集合中存储value和score值的映射关系也是通过字典结构实现。

字典内部结构

字典结构内部包含两个hashtable，通常情况只有一个hashtable有值，但在字典扩容缩容时，需要分配新的hashtable，然后渐进式搬迁，这时候两个hashtable存储的分别是旧的hashtable和新的hashtable。待搬迁结束后，旧的hashtable被删除，新的hashtable取而代之。

hashtable的结构是通过分桶的方式解决hash冲突。第一维是数组，第二维是链表。数组中存储的第二维链表的第一个元素的指针。

渐进式rehash

大字典的扩容是比较耗时间的，需要重写申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下面，这是一个O（n）级别的操作，作为单线程的Redis很难承受这样耗时的过程，所以Redis使用渐进式rehash小步搬迁。

搬迁操作埋伏在当前字典的后续指令中（hset、hdel），就算客户端没有这些指令，Redis还会在定时任务中对字典进行主动搬迁。

查找过程

插入和删除操作都依赖于查找，必须先把元素找到，才可以进行数据结构的修改操作。hashtable的元素是在第二维的链表上，所以我们首先要定位元素在哪个链表上。

func get(key){
	let index = hash_func(key) % size;
	let entry = table[index];
	while(entry != NULL){
		if entry.key == target{
			return entry.value;
		}
		entry = entry.next;
	}
}

hash_func会将key映射为一个整数，不同的key会被映射成分布比较均匀散乱的整数。只有hash值均匀了，整个hashtable才是平衡的，二维链表的长度就不会差很远，查找算法的性能也比较稳定。

hash函数

hashtable的性能好不好完全取决于hash函数的质量。如果hash函数可以将key打散得比较均匀，那么这个hash函数就是好函数。Redis的字典默认的hash函数是siphash。siphash算法即使在输入key很小的情况下，也可以产生随机性特别好的输出，而且它的性能也非常突出。

hash攻击

如果hash函数存在偏向性，黑客利用这种偏向性对服务器进行攻击。存在偏向性的hash函数在特定模式下输入会导致hash第二维长度极为不均匀，甚至所有的元素都集中到个别链表中，直接导致查找效率急剧下降，从O（1）退化到O（n），有限的服务器计算能力将被hashtable的查找效率彻底拖垮。

扩容条件

当Hash表中元素的个数等于第一维数组的长度时，就会开始扩容，扩容的数组时原数组大小的2倍。不过Redis正在做bgsave，为了减少内存页的过多分离，Redis尽量不去扩容
但是如果hash表已经非常满了，元素的个数已经达到了第一维数组长度的5倍，说明hash表已经过于拥挤了，这个时候就会强制扩容

缩容条件

当hash表因为元素逐渐被删除变得越来越稀疏时，Redis会对hash表进行缩容来减少hash表的第一维数组空间占用。缩容的条件时元素个数低于数组长度的10%。缩容不会考虑Redis是否正在做bgsave。

set的结构

Redis里面set的结构底层实现也是字典，只不过所有value都是NULL，其他特性和字典一模一样