Redis源码阅读(十二) 哈希对象

发表于 | 更新于 | 分类于

Redis的哈希对象是一个string类型的field和value的映射表，特别适合用于存储对象，每个 hash 可以存储 2^32 - 1 键值对。

1. 编码

Redis中哈希对象的编码有ZIPLIST和HT。

ziplist编码的哈希对象使用压缩列表作为底层实现，有新的键值对插入时，现将键插入的压缩列表尾部，再将值插入的压缩列表尾部，这样键值对总是紧密挨在一起的。

hashtable编码的哈希对象使用字典作为底层实现，每个键值对都用字典的键值对保存。

2. 编码转换

当哈希对象满足以下条件时，使用ZIPLIST编码：

  1. 哈希对象保存的所有键值对的字符串长度小于64字节。
  2. 哈希对象保存的键值对个数小于512

这两个参数可以通过hash-max-ziplist-value和hash-max-ziplist-entries修改。

当对ziplist编码的哈希对象进行一些操作致使无法使用ziplist编码是，则将哈希对象转换成HT编码，ziplist中保存的键值对会移动到新的字典中。

目前仅实现了ZIPLIST ==> HT的编码转换

3. 命令

命令 作用
HDEL 删除一个或多个哈希表字段
HEXISTS 查看哈希表 key 中，指定的字段是否存在
HGET 获取存储在哈希表中指定字段的值
HGETALL 获取在哈希表中指定 key 的所有字段和值
HINCRBY 为哈希表 key 中的指定字段的整数值加上增量 increment
HINCRBYFLOAT 为哈希表 key 中的指定字段的浮点数值加上增量 increment
HKEYS 获取所有哈希表中的字段
HLEN 获取哈希表中字段的数量
HMGET 获取所有给定字段的值
HMSET 同时将多个 field-value (域-值)对设置到哈希表 key 中
HSET 将哈希表 key 中的字段 field 的值设为 value
HSETNX 只有在字段 field 不存在时，设置哈希表字段的值
HSTRLEN 获取哈希表字段值的长度
HVALS 获取哈希表中所有值
HSCAN 迭代哈希表中的键值对

4. 源码剖析

  • 哈希表中添加键值对
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
int hashTypeSet(robj *o, sds field, sds value, int flags) {
    int update = 0;

    // 根据编码的不同进行处理
    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *zl, *fptr, *vptr;

        zl = o->ptr;
        // 获取ziplist的头结点指针
        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) */
                vptr = ziplistNext(zl, fptr);
                serverAssert(vptr != NULL);
                // 找到该field
                update = 1;

                /* Delete value */
                // 删除ziplist中的field
                zl = ziplistDelete(zl, &vptr);

                /* Insert new value */
                // 插入新的值
                zl = ziplistInsert(zl, vptr, (unsigned char*)value,
                        sdslen(value));
            }
        }

        // 如果不是更新，则插入新的field和value到ziplist尾部
        if (!update) {
            /* 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;

        /* Check if the ziplist needs to be converted to a hash table */
        // 检查是否需要将ziplist转换为哈希表
        if (hashTypeLength(o) > server.hash_max_ziplist_entries)
            hashTypeConvert(o, OBJ_ENCODING_HT);
    } else if (o->encoding == OBJ_ENCODING_HT) {

        // 查找field结点
        dictEntry *de = dictFind(o->ptr,field);
        if (de) {
            // 找到则先释放之前的内容
            sdsfree(dictGetVal(de));

            // HASH_SET_TAKE_VALUE 表示拿走value的值
            if (flags & HASH_SET_TAKE_VALUE) {
                dictGetVal(de) = value;
                value = NULL;
            } else {
                // 其他的则是复制value
                dictGetVal(de) = sdsdup(value);
            }
            update = 1;
        } else {
            sds f,v;
            // HASH_SET_TAKE_FIELD 表示拿走field
            if (flags & HASH_SET_TAKE_FIELD) {
                f = field;
                field = NULL;
            } else {
                // 复制field
                f = sdsdup(field);
            }
            if (flags & HASH_SET_TAKE_VALUE) {
                // 拿走value
                v = value;
                value = NULL;
            } else {
                // 复制value
                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. */
    // 根据flags判断是否需要释放内存空间
    if (flags & HASH_SET_TAKE_FIELD && field) sdsfree(field);
    if (flags & HASH_SET_TAKE_VALUE && value) sdsfree(value);
    return update;
}
  • 哈希表中删除键值对
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int hashTypeDelete(robj *o, sds field) {
    int deleted = 0;

    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        unsigned char *zl, *fptr;

        zl = o->ptr;
        // 头结点地址
        fptr = ziplistIndex(zl, ZIPLIST_HEAD);
        if (fptr != NULL) {
            // 查找field的位置
            fptr = ziplistFind(fptr, (unsigned char*)field, sdslen(field), 1);
            if (fptr != NULL) {
                // 找到则删除key和value
                zl = ziplistDelete(zl,&fptr); /* Delete the key. */
                zl = ziplistDelete(zl,&fptr); /* Delete the value. */
                o->ptr = zl;
                deleted = 1;
            }
        }
    } else if (o->encoding == OBJ_ENCODING_HT) {
        // 删除字典中field
        if (dictDelete((dict*)o->ptr, field) == C_OK) {
            deleted = 1;

            /* Always check if the dictionary needs a resize after a delete. */
            // 判断字典是否需要进行resize
            if (htNeedsResize(o->ptr)) dictResize(o->ptr);
        }

    } else {
        serverPanic("Unknown hash encoding");
    }
    return deleted;
}
  • 迭代哈希表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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;

        // ZIPLIST编码则获取cursor
        if (fptr == NULL) {
            /* Initialize cursor */
            serverAssert(vptr == NULL);
            // 初始化头部
            fptr = ziplistIndex(zl, 0);
        } else {
            /* Advance cursor */
            serverAssert(vptr != NULL);
            // 获取下一个地址
            fptr = ziplistNext(zl, vptr);
        }
        // 迭代完成返回C_ERR
        if (fptr == NULL) return C_ERR;

        /* Grab pointer to the value (fptr points to the field) */
        // fptr指向key，获取对应的内容地址
        vptr = ziplistNext(zl, fptr);
        serverAssert(vptr != NULL);

        /* fptr, vptr now point to the first or next pair */
        hi->fptr = fptr;
        hi->vptr = vptr;
    } else if (hi->encoding == OBJ_ENCODING_HT) {
        // HT编码直接进行字典迭代
        if ((hi->de = dictNext(hi->di)) == NULL) return C_ERR;
    } else {
        serverPanic("Unknown hash encoding");
    }
    return C_OK;
}
  • 哈希对象编码转换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
void hashTypeConvertZiplist(robj *o, int enc) {
    serverAssert(o->encoding == OBJ_ENCODING_ZIPLIST);

    if (enc == OBJ_ENCODING_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
            key = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY);
            // 创建新的value
            value = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);
            // 添加kv到字典
            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;
        // 指向新的字典
        o->ptr = dict;
    } else {
        serverPanic("Unknown hash encoding");
    }
}
  • HGETALL底层实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void genericHgetallCommand(client *c, int flags) {
    robj *o;
    hashTypeIterator *hi;
    int multiplier = 0;
    int length, count = 0;

    // 获取指定key的哈希对象
    if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.emptymultibulk)) == NULL
        || checkType(c,o,OBJ_HASH)) return;

    // 计算一对键值对要返回的个数
    if (flags & OBJ_HASH_KEY) multiplier++;
    if (flags & OBJ_HASH_VALUE) multiplier++;

    // 计算整个哈希对象所有键值对返回的个数
    length = hashTypeLength(o) * multiplier;
    // 回复客户端要返回的个数
    addReplyMultiBulkLen(c, length);

    // 初始化迭代器
    hi = hashTypeInitIterator(o);
    // 迭代并回去结点，回复客户端
    while (hashTypeNext(hi) != C_ERR) {
        if (flags & OBJ_HASH_KEY) {
            addHashIteratorCursorToReply(c, hi, OBJ_HASH_KEY);
            count++;
        }
        if (flags & OBJ_HASH_VALUE) {
            addHashIteratorCursorToReply(c, hi, OBJ_HASH_VALUE);
            count++;
        }
    }

    // 释放迭代器
    hashTypeReleaseIterator(hi);
    serverAssert(count == length);
}
  • HSET命令
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void hsetCommand(client *c) {
    int i, created = 0;
    robj *o;

    if ((c->argc % 2) == 1) {
        addReplyError(c,"wrong number of arguments for HMSET");
        return;
    }

    // 获取指定key的哈希对象，不存在则创建
    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;

    // 判断是否需要编码转换
    hashTypeTryConversion(o,c->argv,2,c->argc-1);

    // 添加多个kv对
    for (i = 2; i < c->argc; i += 2)
        created += !hashTypeSet(o,c->argv[i]->ptr,c->argv[i+1]->ptr,HASH_SET_COPY);

    /* HMSET (deprecated) and HSET return value is different. */
    // 实现了HMSET和HSET
    char *cmdname = c->argv[0]->ptr;
    if (cmdname[1] == 's' || cmdname[1] == 'S') {
        /* HSET */
        addReplyLongLong(c, created);
    } else {
        /* HMSET */
        addReply(c, shared.ok);
    }
    // 通知数据库有key发生修改
    signalModifiedKey(c->db,c->argv[1]);

    // 发送"hset"事件通知
    notifyKeyspaceEvent(NOTIFY_HASH,"hset",c->argv[1],c->db->id);
    server.dirty++;
}