Redis-hash类型

栏目: 数据库 · 发布时间: 5年前

内容简介：hash值对象被创建的时候，都是以ziplist的编码方式存放的。注意这里说的是被创建，而不是一条创建hash的命令执行之后，一条命令可能创建了hash然后往里面写内容。这种编码类型的hash，把键、值当成ziplist里面的entry，依次存放，示意图如下。

hash值对象被创建的时候，都是以ziplist的编码方式存放的。

注意这里说的是被创建，而不是一条创建hash的命令执行之后，一条命令可能创建了hash然后往里面写内容。

这种编码类型的hash，把键、值当成ziplist里面的entry，依次存放，示意图如下。

Redis-hash类型

hashtable型hash

如果hash中存储的键长度或者值长度大于某个阈值，或者ziplist中的entry数量大于某个阈值，那么这个hash会被转换成hashtable编码。

这个两个阈值分别是

#define OBJ_HASH_MAX_ZIPLIST_VALUE 64
#define OBJ_HASH_MAX_ZIPLIST_ENTRIES 512

当以hashtable的编码方式存储的时候，robj键对象的ptr指向的是一个dict。

dict相关的结构体定义如下：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

redis在管理键值对的map的时候，也是使用的dict这种结构，采用hashtable编码的hash结构示意图如下

Redis-hash类型

从图中可以看出，hashtable的 hash 体现在利用索引在对应的ht[]中以O(1)的时间找到对象。而处理冲突，则是在这个表之后形成一条链，其实这和 Java 中的HashMap类似。

在访问hash中的 <field:value> 对的时候，首先使用dict中type字段里面的hash函数对 field 求hash值，这个值即为索引值。拿着这个索引值，在对应的table（根据是否rehash选择对应table，见下文）中找到链表。遍历链表查找 field 对应的entry。

rehash

从上面的代码和图中可以看到，dict中有两个table，为什么有两个table？是为了做rehash。

所谓的rehash，字面上理解，就是重新hash，那么何时会用到重新映射？扩容。

当存储的数据越来越多，那么hash碰撞发生的概率也会越来越大，此时就需要rehash，使用更大的表。

当不需要rehash的时候，第二个table（即ht[1].table）是NULL，所有的数据都往ht[0].table中存储，dict的rehashidx字段为-1。

当需要rehash的时候，redis会把dict中的rehashidx设置为0，这标志着进入了rehash状态，此时会为ht[1].table分配空间。

在进入rehash状态之后的所有写操作，都将会被存储到新创建的ht[1].table中，原来的ht[0].table中的数据会被搬运到ht[1].table中。待全部搬运结束之后，释放ht[0].table，重新赋值为ht[1].table，设置ht[1].table为NULL。

注意

由于 redis 是单线程的，如果在需要rehash的时候专门停下来进行完整的搬运操作，如果这个表非常大，这显然是会影响性能的，所以redis采用了一种 增量rehash 的策略。

增量，即多次rehash，既然redis是单线程，在不影响性能的情况下实现增量，那就只有把rehash的工作分散放到执行各个命令中了。所以在看源码的时候会看到 if (dictIsRehashing(d)) _dictRehashStep(d); 这种执行增量式rehash的代码。

在扩容之后，从相同的键中获取的hash值可能发生变化（不变化怎么能叫扩容呢？）可以想到，这里说的搬运，不是简单的遍历一遍ht[0].table然后把表中的作用的内容都放到新表中，具体细节打算下次再写写。

源码

下面看一下hset的执行过程，以创建一个新的hash为例： hset person name charles

和hset对应的命令是hsetCommand

// t_hash.c
void hsetCommand(client *c) {
    int i, created = 0;
    robj *o;

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

    // 查找person键对应的hash
    // 如果person没有对应的值，创建robj对象
    // 如果有，但是不是hash类型，返回NULL
    if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
    
    // 如果可以的话，把ziplist编码的hash转换成真正的hash
    // 如果这里是新建的hash的话，是不会被转成hashtable编码的，因为里面还没有元素
    hashTypeTryConversion(o,c->argv,2,c->argc-1);	/*** 编码转换 ***/

    for (i = 2; i < c->argc; i += 2)
        // 把field:value加入到hash中
        // 注意：在hashTypeSet函数的调用过程中有编码转换检查
        created += !hashTypeSet(o,c->argv[i]->ptr,c->argv[i+1]->ptr,HASH_SET_COPY);
    	/*** 编码转换^ ***/

    /* HMSET (deprecated) and HSET return value is different. */
    char *cmdname = c->argv[0]->ptr;
    if (cmdname[1] == 's' || cmdname[1] == 'S') {
        /* HSET */
        addReplyLongLong(c, created);
    } else {
        /* HMSET */
        addReply(c, shared.ok);
    }
    signalModifiedKey(c->db,c->argv[1]);
    notifyKeyspaceEvent(NOTIFY_HASH,"hset",c->argv[1],c->db->id);
    server.dirty++;
}

上面这段代码，大概就做了三件事，

  • 按照给定的键查找hash的robj对象，如果不存在则创建
  • 编码转换
  • 向hash里面添加键值对

关键点一–hash对象的创建

对于一个新的hash对象，它是在hashTypeLookupWriteOrCreate被创建的，这个新建的hash对象，其实是以ziplist的形式存在的。

// t_hash.c
robj *hashTypeLookupWriteOrCreate(client *c, robj *key) {
    robj *o = lookupKeyWrite(c->db,key);
    if (o == NULL) {
        o = createHashObject();
        dbAdd(c->db,key,o);
    } else {
        if (o->type != OBJ_HASH) {
            addReply(c,shared.wrongtypeerr);
            return NULL;
        }
    }
    return o;
}

// object.c
robj *createHashObject(void) {
    unsigned char *zl = ziplistNew();
    robj *o = createObject(OBJ_HASH, zl);
    o->encoding = OBJ_ENCODING_ZIPLIST;
    return o;
}

关键点二–设置field:value

设置field:value到hash中使用的是hashTypeSet，而根据编码的不同，可能会调用ziplist相关方法或者调用dict相关方法。

// 这三个define表示是否将sds的控制权转交给hashTypeSet
#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;

    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        // ziplist编码
        // 1. 找到field对应的entry
        // 2. 如果没有对应的field，在ziplist尾部插入field、value
        // 3. 如果找到，删除原来value，插入新value
        // 4. 最后检查编码转换
        unsigned char *zl, *fptr, *vptr;

        zl = o->ptr;
        fptr = ziplistIndex(zl, ZIPLIST_HEAD);
        if (fptr != NULL) {
            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);
                update = 1;

                /* Delete value */
                zl = ziplistDelete(zl, &vptr);

                /* Insert new value */
                zl = ziplistInsert(zl, vptr, (unsigned char*)value,
                        sdslen(value));
            }
        }

        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 */
        // 检查是否需要编码转换
        if (hashTypeLength(o) > server.hash_max_ziplist_entries)
            hashTypeConvert(o, OBJ_ENCODING_HT);
    } else if (o->encoding == OBJ_ENCODING_HT) {
        dictEntry *de = dictFind(o->ptr,field);
        if (de) {
            // 存在field
            sdsfree(dictGetVal(de));	// 释放原来的value
            // 设置新value
            if (flags & HASH_SET_TAKE_VALUE) {
                dictGetVal(de) = value;
                value = NULL;
            } else {
                dictGetVal(de) = sdsdup(value);
            }
            update = 1;
        } else {
            sds f,v;
            // dict中没有field，加入到dict中
            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;
}

关键点二–转换为hash table编码

在上面的hsetCommand源码中，有两处函数调用可能会转换编码，一个是hashTypeTryConversion，代码如下

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]) &&
            sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)	// 长度大于阈值，默认是64
        {
            hashTypeConvert(o, OBJ_ENCODING_HT);
            break;
        }
    }
}

还一个是hashTypeSet，相关代码如下

int hashTypeSet(robj *o, sds field, sds value, int flags) {
	// ...
    
    // 当存储的<field:value>对数大于阈值时，转换编码，默认阈值512
	if (hashTypeLength(o) > server.hash_max_ziplist_entries)
            hashTypeConvert(o, OBJ_ENCODING_HT);
    // ...
}

从上面两个函数中可以看到，编码转换最终都是hashTypeConvert这个函数来完成的。

void hashTypeConvert(robj *o, int enc) {
    if (o->encoding == OBJ_ENCODING_ZIPLIST) {
        hashTypeConvertZiplist(o, enc);		
    } else if (o->encoding == OBJ_ENCODING_HT) {
        serverPanic("Not implemented");
    } else {
        serverPanic("Unknown hash encoding");
    }
}

void hashTypeConvertZiplist(robj *o, int enc) {
    // 把ziplist编码的hash转换成hashtable编码
    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);	// 分配dict

        // 遍历ziplist
        while (hashTypeNext(hi) != C_ERR) {
            sds key, value;

            key = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY);
            value = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);
            ret = dictAdd(dict, key, value);	// 把field:value加入到dict中，如果dict.ht[?].table还没有分配，分配。
            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");
    }
}

以上所述就是小编给大家介绍的《Redis-hash类型》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍
Unix/Linux编程实践教程

Unix/Linux编程实践教程

Bruce Molay、杨宗源、黄海涛 / 杨宗源、黄海涛 / 清华大学出版社 / 2004-10-1 / 56.00元

操作系统是计算机最重要的系统软件。Unix操作系统历经了几十年，至今仍是主流的操作系统。本书通过解释Unix的工作原理，循序渐进地讲解实现Unix中系统命令的方法，让读者理解并逐步精通Unix系统编程，进而具有编制Unix应用程序的能力。书中采用启发式、举一反三、图示讲解等多种方法讲授，语言生动、结构合理、易于理解。每一章后均附有大量的习题和编程练习，以供参考。 本书适合作为高等院校计算机及......一起来看看 《Unix/Linux编程实践教程》 这本书的介绍吧!

码农工具
JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

  • New
  • 文章
  • 话题
  • 教程
    • 关注 码农网 公众号
    版权所有，保留一切权利！© 2018-2024 码农网 粤ICP备17054400号-3