[TOC] ## 概述 redis的哈希对象的底层存储可以使用ziplist（压缩列表）和hashtable。当hash对象可以同时满足一下两个条件时，哈希对象使用ziplist编码。 * 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节 * 哈希对象保存的键值对数量小于512个 当不满足上述条件时，hash对象的底层数据为`hashtable` ## hashtable数据结构 ```c //节点 typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; /* 指向下一个节点, 链接表的方式解决Hash冲突*/ } dictEntry; typedef struct dictht { dictEntry **table; /* dictEntry*数组,Hash表 */ unsigned long size; /* Hash表总大小 */ unsigned long sizemask; /* 计算在table中索引的掩码, 值是size-1 */ unsigned long used; /* Hash表已使用的大小 */ } dictht; typedef struct dict { dictType *type; void *privdata; dictht ht[2]; /* 两个hash表,rehash时使用*/ long rehashidx; /* rehash的索引, -1表示没有进行rehash */ unsigned long iterators; /* number of iterators currently running */ } dict; ``` redis的hash架构就是标准的hashtable的结构，通过挂链解决冲突问题。 ## hash存储过程源码分析 以`hset`命令为例进行分析，整个过程如下： * 首先查看hset中key对应的value是否存在，`hashTypeLookupWriteOrCreate`。 * 判断`key`和`value`的长度确定是否需要从`zipList`到`hashtable`转换，`hashTypeTryConversion`。 * 对`key/value`进行`string`层面的编码，解决内存效率问题。 * `hashTypeSet`,判断是否使用ziplist或hashtable * 更新`hash`节点中`key/value`问题。 * 其他后续操作的问题 判断`key/value`的长度是否超过规定的长度64个字节，由`REDIS_HASH_MAX_ZIPLIST_VALUE`定义。如果超过64个字节那么久需要将`ziplist`转成`hashtab`对象。 ``` void hashTypeTryConversion(robj *o, robj **argv, int start, int end) { int i; if (o->encoding != OBJ_ENCODING_ZIPLIST) return; for (i = start; i <= end; i++) { if (sdsEncodedObject(argv[i]) && // #define REDIS_HASH_MAX_ZIPLIST_VALUE 64 sdslen(argv[i]->ptr) > server.hash_max_ziplist_value) { //将对象的编码转换成 REDIS_ENCODING_HT hashTypeConvert(o, OBJ_ENCODING_HT); break; } } } ``` `hash`底层的更新操作函数`hashTypeSet`内部会根据是`ziplist`还是`hashtable`进行不同的处理逻辑，在`ziplist`当中会判断`ziplist`存储数据的长度来判断是否需要转为`hashtable`数据结构，其中长度判断是通过`#define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512`定义的。 ``` /* * 将给定的 field-value 对添加到 hash 中， * 如果 field 已经存在，那么删除旧的值，并关联新值。 * 这个函数负责对 field 和 value 参数进行引用计数自增。 * 返回 0 表示元素已经存在，这次函数调用执行的是更新操作。 * 返回 1 则表示函数执行的是新添加操作。 */ int hashTypeSet(robj *o, robj *field, robj *value) { int update = 0; // 添加到 ziplist if (o->encoding == REDIS_ENCODING_ZIPLIST) { ... // 检查在添加操作完成之后，是否需要将 ZIPLIST 编码转换成 HT 编码 // #define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512 if (hashTypeLength(o) > server.hash_max_ziplist_entries) hashTypeConvert(o, REDIS_ENCODING_HT); // 添加到字典 } else if (o->encoding == REDIS_ENCODING_HT) { // 添加或替换键值对到字典 // 添加返回 1 ，替换返回 0 if (dictReplace(o->ptr, field, value)) { /* Insert */ incrRefCount(field); } else { /* Update */ update = 1; } incrRefCount(value); } else { redisPanic("Unknown hash encoding"); } // 更新/添加指示变量 return update; } ``` ## 渐进式hash说明 * `dict`中`ht[2]`中有两个`hash`表, 我们第一次存储数据的数据时, `ht[0]`会创建一个最小为4的`hash`表, * 一旦`ht[0]`中的`size`和`used`相等, 则`dict`中会在`ht[1]`创建一个`size*2`大小的`hash`表, 此时并不会直接将`ht[0]`中的数据`copy`进`ht[0]`中, 执行的是渐进式`rehash` * 即在以后的操作(find, set, get等)中慢慢的`copy`进去, 以后新添加的元素会添加进`ht[0]`, 因此在`ht[1]`被占满的时候定能确保`ht[0]`中所有的数据全部`copy`到`ht[1]`中.