Redis源码剖析--哈希对象t_hash实现

落日映苍穹つ 2022-05-23 11:11 230阅读 0赞

## hash对象概述 ##

哈希对象的实现有点类似于版本3.2之前的列表对象实现，它的底层编码也有两种格式：ziplist 和 hashtable。

当哈希对象可以同时满足以下两个条件时， 哈希对象使用 ziplist 编码：

哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；  
哈希对象保存的键值对数量小于 512 个；  
不能满足这两个条件的哈希对象需要使用 hashtable 编码。

当然，这两个阈值都是可以用户自行设置的：

/* redis.conf文件中的阈值 */
    hash-max-ziplist-value 64 // ziplist中最大能存放的值长度
    hash-max-ziplist-entries 512 // ziplist中最多能存放的entry节点数量

对于使用 ziplist 编码的列表对象来说， 当使用 ziplist 编码所需的两个条件的任意一个不能被满足时， 对象的编码转换操作就会被执行： 原本保存在压缩列表里的所有键值对都会被转移并保存到字典里面， 对象的编码也会从 ziplist 变为 hashtable 。并且这个转换过程也是一个不可逆的过程。

哈希对象的结构如下：

typedef struct redisObject {
        unsigned type:4; // hash类型
        unsigned encoding:4;  // //对象的编码类型，分别为 OBJ_ENCODING_ZIPLIST 或 OBJ_ENCODING_HT
        unsigned lru:LRU_BITS;  // 上一次操作的时间
        int refcount; // 引用计数，便于内存管理
        void *ptr;  // 指向底层的数据结构
    } robj;

## ziplist 编码的哈希对象 ##

当哈希对象底层采用ziplist的实现的时候，每次插入一个新的键值对，程序会先将保存了键的压缩列表节点推入到压缩列表表尾， 然后再将保存了值的压缩列表节点推入到压缩列表表尾。类似下图所示

## hashtable 编码的哈希对象 ##

当哈希对象底层采用hashtable实现的时候，哈希对象中的指针ptr会指向一个dict，哈希对象中的每个键值对都使用一个字典键值对来保存， 每个键和值都是一个字符串对象。

## hashtable 的实现 ##

<table> 
 <thead> 
  <tr> 
   <th>命令</th> 
   <th>ziplist 编码实现方法</th> 
   <th>hashtable 编码的实现方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>HSET</td> 
   <td>首先调用 ziplistPush 函数， 将键推入到压缩列表的表尾， 然后再次调用 ziplistPush 函数， 将值推入到压缩列表的表尾。</td> 
   <td>调用 dictAdd 函数， 将新节点添加到字典里面。</td> 
  </tr> 
  <tr> 
   <td>HGET</td> 
   <td>首先调用 ziplistFind 函数， 在压缩列表中查找指定键所对应的节点， 然后调用 ziplistNext 函数， 将指针移动到键节点旁边的值节点， 最后返回值节点。</td> 
   <td>调用 dictFind 函数， 在字典中查找给定键， 然后调用 dictGetVal 函数， 返回该键所对应的值。</td> 
  </tr> 
  <tr> 
   <td>HEXISTS</td> 
   <td>调用 ziplistFind 函数， 在压缩列表中查找指定键所对应的节点， 如果找到的话说明键值对存在， 没找到的话就说明键值对不存在。</td> 
   <td>调用 dictFind 函数， 在字典中查找给定键， 如果找到的话说明键值对存在， 没找到的话就说明键值对不存在。</td> 
  </tr> 
  <tr> 
   <td>HDEL</td> 
   <td>调用 ziplistFind 函数， 在压缩列表中查找指定键所对应的节点， 然后将相应的键节点、 以及键节点旁边的值节点都删除掉。</td> 
   <td>调用 dictDelete 函数， 将指定键所对应的键值对从字典中删除掉。</td> 
  </tr> 
  <tr> 
   <td>HLEN</td> 
   <td>调用 ziplistLen 函数， 取得压缩列表包含节点的总数量， 将这个数量除以 2 ， 得出的结果就是压缩列表保存的键值对的数量。</td> 
   <td>调用 dictSize 函数， 返回字典包含的键值对数量， 这个数量就是哈希对象包含的键值对数量。</td> 
  </tr> 
  <tr> 
   <td>HGETALL</td> 
   <td>遍历整个压缩列表， 用 ziplistGet 函数返回所有键和值（都是节点）。</td> 
   <td>遍历整个字典， 用 dictGetKey 函数返回字典的键， 用 dictGetVal 函数返回字典的值。</td> 
  </tr> 
 </tbody> 
</table>

### HSET 实现分析 ###

/* Add a new field, overwrite the old with the new value if it already exists.
     * Return 0 on insert and 1 on update.
     *
     * By default, the key and value SDS strings are copied if needed, so the
     * caller retains ownership of the strings passed. However this behavior
     * can be effected by passing appropriate flags (possibly bitwise OR-ed):
     *
     * HASH_SET_TAKE_FIELD -- The SDS field ownership passes to the function.
     * HASH_SET_TAKE_VALUE -- The SDS value ownership passes to the function.
     *
     * When the flags are used the caller does not need to release the passed
     * SDS string(s). It's up to the function to use the string to create a new
     * entry or to free the SDS string before returning to the caller.
     *
     * HASH_SET_COPY corresponds to no flags passed, and means the default
     * semantics of copying the values if needed.
     *
     */
    #define HASH_SET_TAKE_FIELD (1<<0)
    #define HASH_SET_TAKE_VALUE (1<<1)
    #define HASH_SET_COPY 0
    int hashTypeSet(robj *o, sds field, sds value, int flags) {
        int update = 0;
        // 如果底层是ziplist编码
        if (o->encoding == OBJ_ENCODING_ZIPLIST) {
            unsigned char *zl, *fptr, *vptr;
    
            zl = o->ptr;
            // 得到ziplist的head
            fptr = ziplistIndex(zl, ZIPLIST_HEAD);
            if (fptr != NULL) {
                    // 查看是否已经存在了该field
                fptr = ziplistFind(fptr, (unsigned char*)field, sdslen(field), 1);
                if (fptr != NULL) {
                    /* Grab pointer to the value (fptr points to the field) */
                    // 如果已经存在，取ziplist的next，即对应的value
                    vptr = ziplistNext(zl, fptr);
                    serverAssert(vptr != NULL);
                    // 标记这次为更新操作
                    update = 1;
    
                    /* 删除旧的值 */
                    zl = ziplistDelete(zl, &vptr);
    
                    /* 插入新的值 */
                    zl = ziplistInsert(zl, vptr, (unsigned char*)value,
                            sdslen(value));
                }
            }
    
            if (!update) {
                // 如果不是一个更新操作，需要把键值对插入到ziplist的尾部
                /* Push new field/value pair onto the tail of the ziplist */
                // 先插入键
                zl = ziplistPush(zl, (unsigned char*)field, sdslen(field),
                        ZIPLIST_TAIL);
                // 后插入值
                zl = ziplistPush(zl, (unsigned char*)value, sdslen(value),
                        ZIPLIST_TAIL);
            }
            o->ptr = zl;
    
            /* 检查ziplist中存放的节点个数，如果超过512(默认值)则转换成OBJ_ENCODING_HT编码 */
            if (hashTypeLength(o) > server.hash_max_ziplist_entries)
                hashTypeConvert(o, OBJ_ENCODING_HT);
        } else if (o->encoding == OBJ_ENCODING_HT) {
            // 如果底层是hashtable编码实现
            // 在dict中查找对应的field
            dictEntry *de = dictFind(o->ptr,field);
            if (de) {
                    // 如果已经存在，执行更新操作
                sdsfree(dictGetVal(de));
                if (flags & HASH_SET_TAKE_VALUE) {
                    dictGetVal(de) = value;
                    value = NULL;
                } else {
                    dictGetVal(de) = sdsdup(value);
                }
                update = 1;
            } else {
                    // 如果不存在，dictAdd添加键值对
                sds f,v;
                if (flags & HASH_SET_TAKE_FIELD) {
                    f = field;
                    field = NULL;
                } else {
                    f = sdsdup(field);
                }
                if (flags & HASH_SET_TAKE_VALUE) {
                    v = value;
                    value = NULL;
                } else {
                    v = sdsdup(value);
                }
                dictAdd(o->ptr,f,v);
            }
        } else {
            serverPanic("Unknown hash encoding");
        }
    
        /* Free SDS strings we did not referenced elsewhere if the flags
         * want this function to be responsible. */
        if (flags & HASH_SET_TAKE_FIELD && field) sdsfree(field);
        if (flags & HASH_SET_TAKE_VALUE && value) sdsfree(value);
        return update;
    }

这边相比之前的版本多了一个flag的参数， 针对这个flag有对应的三个宏定义

#define HASH_SET_TAKE_FIELD (1<<0)
    #define HASH_SET_TAKE_VALUE (1<<1)
    #define HASH_SET_COPY 0

这几个宏用于定义用于传进去的field与value是以拷贝的方法赋值，还是直接将找到的field与value直接以指针赋值的方式设置值。

*  若flag为HASH\_SET\_COPY，field与value没有释放掉空间
 *  若以HASH\_SET\_TAKE\_VALUE则value的值会释放掉
 *  若以HASH\_SET\_TAKE\_FIELD则field的值会释放掉

这样我们就能理解在hashtable编码格式中，更新和插入的操作中，会根据flag来区别对待：是dictGetVal(de) = value 之后value置空还是 dictGetVal(de) = sdsdup(value)。 并且在函数的最后，也需要根据flag值来判断是否需要释放对应的field和value。

### 转换函数 ###

上面我们能够看到ziplist在一定条件下会抓换成hashtable的编码，并且目前仍旧是一个不可逆的过程， 看一下转换的函数

void hashTypeConvertZiplist(robj *o, int enc) {  
        //用于类型的转化，根据enc，一般是从ziplist转化为dict 
        serverAssert(o->encoding == OBJ_ENCODING_ZIPLIST);  
    
        if (enc == OBJ_ENCODING_ZIPLIST) {  
            //原来就是ziplist则不转换 
            /* Nothing to do... */  
    
        } else if (enc == OBJ_ENCODING_HT) {  
    
            hashTypeIterator *hi;  
            dict *dict;  
            int ret;  
    
            hi = hashTypeInitIterator(o);  
            dict = dictCreate(&hashDictType, NULL);  
            //初始化迭代器，创建新的表 
    
            while (hashTypeNext(hi) != C_ERR) {  
                sds key, value;  
                //不断找到key-value并且插入。 
    
                key = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY);  
                value = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);  
                ret = dictAdd(dict, key, value);  
                if (ret != DICT_OK) {  
                    serverLogHexDump(LL_WARNING,"ziplist with dup elements dump",  
                        o->ptr,ziplistBlobLen(o->ptr));  
                    serverPanic("Ziplist corruption detected");  
                }  
            }  
            hashTypeReleaseIterator(hi);  
            //释放迭代器 
            zfree(o->ptr);  
            o->encoding = OBJ_ENCODING_HT;//将robj中的元素重新赋值 
            o->ptr = dict;  
    
        } else {  
            serverPanic("Unknown hash encoding");  
        }  
    }  
    
    void hashTypeConvert(robj *o, int enc) {  
        //类型转换api 
        if (o->encoding == OBJ_ENCODING_ZIPLIST) {  
            hashTypeConvertZiplist(o, enc);  
        } else if (o->encoding == OBJ_ENCODING_HT) {  
            serverPanic("Not implemented");  
        } else {  
            serverPanic("Unknown hash encoding");  
        }  
    }

### 迭代器 ###

在转换的过程中， 看到又引入了一个迭代器的概念， 我们来具体看一下相关的实现。

迭代器的定义如下

typedef struct {
        robj *subject;  // 指向的hash对象
        int encoding;  // 编码类型
        // 用于迭代ziplist结构
        unsigned char *fptr, *vptr; // 域指针和值指针
        // 用于迭代dict结构
        dictIterator *di; // 字典迭代器
        dictEntry *de;  // 指向当前迭代字典节点的指针
    } hashTypeIterator;

初始化迭代器：

// 返回一个初始化的哈希类型的迭代器
    hashTypeIterator *hashTypeInitIterator(robj *subject) {
        // 分配空间初始化成员
        hashTypeIterator *hi = zmalloc(sizeof(hashTypeIterator));
        hi->subject = subject;
        hi->encoding = subject->encoding;
    
        // 根据不同的编码设置不同的成员
        if (hi->encoding == OBJ_ENCODING_ZIPLIST) {
            hi->fptr = NULL;
            hi->vptr = NULL;
        } else if (hi->encoding == OBJ_ENCODING_HT) {
            // 初始化一个字典迭代器返回给di成员
            hi->di = dictGetIterator(subject->ptr);
        } else {
            serverPanic("Unknown hash encoding");
        }
    
        return hi;
    }

迭代器释放：

/* 释放一个迭代器 */
    void hashTypeReleaseIterator(hashTypeIterator *hi) {
        if (hi->encoding == OBJ_ENCODING_HT) {
            dictReleaseIterator(hi->di);
        }
        zfree(hi);
    }

迭代步骤：

/* 迭代到下一个节点 */ 
    int hashTypeNext(hashTypeIterator *hi) {
        if (hi->encoding == OBJ_ENCODING_ZIPLIST) {
            unsigned char *zl;
            unsigned char *fptr, *vptr;
            zl = hi->subject->ptr;
            fptr = hi->fptr;
            vptr = hi->vptr;
            if (fptr == NULL) {
                // 如果当前迭代器为空，则初始化指向ziplist的第一个节点
                serverAssert(vptr == NULL);
                fptr = ziplistIndex(zl, 0);
            } else {
                // 反之指向下一个key节点
                serverAssert(vptr != NULL);
                fptr = ziplistNext(zl, vptr);
            }
            if (fptr == NULL) return C_ERR;
            // fptr的下一个节点就是值节点
            vptr = ziplistNext(zl, fptr);
            serverAssert(vptr != NULL);
            // 更新参数
            hi->fptr = fptr;
            hi->vptr = vptr;
        } else if (hi->encoding == OBJ_ENCODING_HT) {
            // OBJ_ENCODING_HT编码的时候就直接调用哈希的迭代器即可
            if ((hi->de = dictNext(hi->di)) == NULL) return C_ERR;
        } else {
            serverPanic("Unknown hash encoding");
        }
        return C_OK;
    }