Redis Hash原理 作者: nbboy 时间: 2022-02-27 分类: 默认分类,C > 分析的Redis版本基于6.0 ## Redis Hash #### 应用场景 哈希列表结构是一般在编程上非常重要的结构，因为它的查询性能接近O(1)，所以是一种非常高效的数据结构。我们平时用的字典（dict）往往都是通过哈希列表去实现的，而redis中自己实现的hash结构也非常重要。在redis中所有的键值都是通过hash结构去管理的，比如我们键入命令set a hello时，其实在redis server用结构redisDb->dict来进行维护，其键和值都是redisObject： ```c typedef struct redisDb { dict *dict; /* The keyspace for this DB */ dict *expires; /* Timeout of keys with a timeout set */ ... } redisDb; ``` #### Hash结构 redis hash结构和普通的hash结构还是非常像的，但是因为它有一个渐进式hash过程（下面会讲），所以它其实有两个hash table。 ```c //字典采用链表处理冲突，而且在数据过多的时候会自动进行渐进式重新hash typedef struct dict { //一些函数指针 dictType *type; void *privdata; //rehash的oldhash和newhash dictht ht[2]; //rehash的进度(hash槽索引), 如果是-1, 则表示没有进行rehash, 否则就是在rehash long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */ } dict; typedef struct dictht { //指向hash槽的头部 dictEntry **table; //分配的hash槽总数量 unsigned long size; //计算hash槽的掩码值, 它等于size - 1 unsigned long sizemask; //在用的hash槽数量 unsigned long used; } dictht; //字典的每个元素 typedef struct dictEntry { //元素的健 void *key; //指向的值,或是指向一个对象，或者数值... union { void *val; uint64_t u64; int64_t s64; double d; } v; //采用链表的方式，next指向hash槽内的下个元素 struct dictEntry *next; } dictEntry; ``` 比如size=6的hash表按照字母顺序进行编码（比如a:1,b:2,c:3,d:4,e:5,f:6,g:1...)，并且插入到hash列表中后的图示如下：  #### 键冲突处理 我们知道所有的hash列表都会冲突，冲突是由于key被hash到一个bucket（有些资料里叫hash槽）里引起的。Redis采用如下的技术处理键的冲突： - 选择好的Hash函数,尽量让键分布均匀 - 用拉链的方式处理冲突，即使键值过载，也会被分散到bucket内的链表里 - 设定一个阈值，如果元素过载，则会进行自动扩容 散列表的处理冲突方式一般有两种，开放定址和拉链法，而Redis采用的是拉链法，实现上用链表来管理冲突的键值对。Redis在Hash函数的选取上则用的是SipHash，这种算法有较强的安全性，可以用来防御“Hash-flooding”。 #### 扩容/缩容 当随着元素的增加，如果Hash列表不进行扩张，则必然会增加单个Bucket的元素数量，而这会导致命中该Bucket的检索操作退化到查询列表的操作，而这是不能被接受的，所以Redis设计了自动扩容的机制。 扩容是在添加操作完成的，当元素使用比例过了设定的阈值，则进行自动扩容： ```c //超过阈值，开始进行hash扩展，扩展长度为两倍，里面会进行微调整 if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { return dictExpand(d, d->ht[0].used*2); } ``` Redis扩容本身并不复杂，它会把散列的空间扩大到现有元素的2倍左右大小。相比扩容，缩容采用了更加主动的方式，采用定时器进行周期性的空间回收，具体操作在tryResizeHashTables函数，收缩的条件为空间利用率下降为10%，就会进行一次收缩，收缩过后的大小刚好大于原有键值对数量的2的n次。([dictResize](https://github.com/redis/redis/blob/6.0/src/dict.c#L135 "dictResize")) ```c //低于10%的时候，会进行缩容 int htNeedsResize(dict *dict) { long long size, used; size = dictSlots(dict); used = dictSize(dict); //use/size < 0.10 return (size > DICT_HT_INITIAL_SIZE && (used*100/size < HASHTABLE_MIN_FILL)); } ``` #### 渐进式Rehash 作为hash列表，已有的功能都是完整的，但是作为高性能的Redis服务器如果只是容许暂停服务进行rehash，那将是不可承受的。Redis在设计上采用了渐进式的结构，也就是在rehash阶段，会有两个散列表存在，一个用来存目前用的健值对ht1，另外一个则是新扩张后的ht2。在这个阶段两个ht都需要去查找和更新，当完成这个阶段只需要考虑ht1。 可以用一个例子来图示一下，假设为了方便演示，resize比例为1的时候就进行扩张，初始化hash大小为2个Bucket，插入3个键值对后的hash状态如下：  这时候，其实hash列表里的键值对已经达到扩容的零界点，当请求插入l=33的时候，根据used/size=4/2=2>1(dict_force_resize_ratio )，所以会分配一个2倍空间(2*used)大小给新的ht1，并且启动**渐进式hash迁移**。而在hash迁移期间，所有的插入请求的键值对都会放到新的ht1。  当我们请求删除e为健的键值对时，其实它会进行两步操作(其实如果一旦进入hash迁移，则对于查找/添加/替换都会有下面的第一步)： 1. 依次获取ht0的一个bucket，并且迁移到ht1中 2. 在ht0和ht1中查找是否有健，如果找到的话进行删除  *图画的不是很好，表达的是2个键值对迁移过来后，其中一个被删除（画叉的是被删除，画加号的是被正常迁移过来，顺序是先迁移，后删除）* 这时候如果来个检索操作，比如检索b为健的值是多少，同样检索操作也需要执行一次迁移操作，也即： 1. 依次获取ht0的一个bucket，并且迁移到ht1中 2. 在ht0和ht1中查找是否有健，如果找到的话返回 对于这里的例子，本次操作会迁移Bucket2，操作后会使ht0没有键值对（used==0）。而当ht0为空时候，ht1被作为新的ht0(ht1指针给ht0)，ht1清空作为下一次迁移用，本轮迁移标记rehashidx置空。  需要说明的是如果在迁移阶段进行检索，并且第一步之后迁移也没有完成，则查找的时候会对h0和h1两个hash表都进行检索，因为键值有可能在h0也有可能在h1。 最后再补充一点，渐进式迁移不光光在查找/添加/替换等操作里有，而且在定时任务里也会给予一定的时间（1ms）进行迁移。 ### 参考 《算法》散列表部分 《数据结构与算法之美》散列表部分 标签: Redis, hash, dict, 哈希列表
评论已关闭