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类型》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！

查看所有标签

猜你喜欢:

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

码农书籍
An Introduction to Probability Theory and Its Applications

An Introduction to Probability Theory and Its Applications

William Feller / Wiley / 1991-1-1 / USD 120.00

Major changes in this edition include the substitution of probabilistic arguments for combinatorial artifices, and the addition of new sections on branching processes, Markov chains, and the De Moivre......一起来看看 《An Introduction to Probability Theory and Its Applications》 这本书的介绍吧!

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

在线 JSON 格式化工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

html转js在线工具
html转js在线工具

html转js在线工具

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