内容简介：hash值对象被创建的时候，都是以ziplist的编码方式存放的。注意这里说的是被创建，而不是一条创建hash的命令执行之后，一条命令可能创建了hash然后往里面写内容。这种编码类型的hash，把键、值当成ziplist里面的entry，依次存放，示意图如下。
hash值对象被创建的时候，都是以ziplist的编码方式存放的。
注意这里说的是被创建，而不是一条创建hash的命令执行之后，一条命令可能创建了hash然后往里面写内容。
这种编码类型的hash，把键、值当成ziplist里面的entry，依次存放，示意图如下。
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结构示意图如下
从图中可以看出，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类型》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- golang的值类型，指针类型和引用类型&值传递&指针传递
- Scala 类型的类型（三）
- Scala 类型的类型（二）
- Scala 类型的类型（三）
- Scala 类型的类型（二）
- golang: 类型转换和类型断言
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
