hash底层存储结构
redis的哈希对象的底层存储可以使用ziplist（压缩列表）和hashtable。当hash对象可以同时满足一下两个条件时，哈希对象使用ziplist编码。
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对数量小于512个
redis hash数据结构
redis的hash架构就是标准的hashtab的结构，通过挂链解决冲突问题。
hashtab.png
redis ziplist数据结构
ziplist的数据结构主要包括两层，ziplist和zipEntry。
- ziplist包括zip header、zip entry、zip end三个模块。
- zip entry由prevlen、encoding&length、value三部分组成。
- prevlen主要是指前面zipEntry的长度，coding&length是指编码字段长度和实际- 存储value的长度，value是指真正的内容。
- 每个key/value存储结果中key用一个zipEntry存储，value用一个zipEntry存储。
ziplist
zipEntry
redis hash存储过程源码分析
以hset命令为例进行分析，整个过程如下：
- 首先查看hset中key对应的value是否存在，hashTypeLookupWriteOrCreate。
- 判断key和value的长度确定是否需要从zipList到hashtab转换，hashTypeTryConversion。
- 对key/value进行string层面的编码，解决内存效率问题。
- 更新hash节点中key/value问题。
- 其他后续操作的问题
void hsetCommand(redisClient *c) {
int update;
robj *o;
// 取出或新创建哈希对象
if ((o = hashTypeLookupWriteOrCreate(c,c->argv[1])) == NULL) return;
// 如果需要的话，转换哈希对象的编码
hashTypeTryConversion(o,c->argv,2,3);
// 编码 field 和 value 对象以节约空间
hashTypeTryObjectEncoding(o,&c->argv[2], &c->argv[3]);
// 设置 field 和 value 到 hash
update = hashTypeSet(o,c->argv[2],c->argv[3]);
// 返回状态：显示 field-value 对是新添加还是更新
addReply(c, update ? shared.czero : shared.cone);
// 发送键修改信号
signalModifiedKey(c->db,c->argv[1]);
// 发送事件通知
notifyKeyspaceEvent(REDIS_NOTIFY_HASH,"hset",c->argv[1],c->db->id);
// 将服务器设为脏
server.dirty++;
}
判断key/value的长度是否超过规定的长度64个字节，由REDIS_HASH_MAX_ZIPLIST_VALUE定义。如果超过64个字节那么久需要将ziplist转成hashtab对象。
/*
* 对 argv 数组中的多个对象进行检查，
* 看是否需要将对象的编码从 REDIS_ENCODING_ZIPLIST 转换成 REDIS_ENCODING_HT
* 注意程序只检查字符串值，因为它们的长度可以在常数时间内取得。
*/
void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
int i;
// 如果对象不是 ziplist 编码，那么直接返回
if (o->encoding != REDIS_ENCODING_ZIPLIST) return;
// 检查所有输入对象，看它们的字符串值是否超过了指定长度
for (i = start; i <= end; i++) {
// #define REDIS_HASH_MAX_ZIPLIST_VALUE 64
if (sdsEncodedObject(argv[i]) &&
sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)
{
// 将对象的编码转换成 REDIS_ENCODING_HT
hashTypeConvert(o, REDIS_ENCODING_HT);
break;
}
}
}
hash底层的更新操作函数hashTypeSet内部会根据是ziplist还是hashtab进行不同的处理逻辑，在ziplist当中会判断ziplist存储数据的长度来判断是否需要转为hashtab数据结构，其中长度判断是通过#define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512定义的。
/*
* 将给定的 field-value 对添加到 hash 中，
* 如果 field 已经存在，那么删除旧的值，并关联新值。
*
* 这个函数负责对 field 和 value 参数进行引用计数自增。
*
* 返回 0 表示元素已经存在，这次函数调用执行的是更新操作。
*
* 返回 1 则表示函数执行的是新添加操作。
*/
int hashTypeSet(robj *o, robj *field, robj *value) {
int update = 0;
// 添加到 ziplist
if (o->encoding == REDIS_ENCODING_ZIPLIST) {
unsigned char *zl, *fptr, *vptr;
// 解码成字符串或者数字
field = getDecodedObject(field);
value = getDecodedObject(value);
// 遍历整个 ziplist ，尝试查找并更新 field （如果它已经存在的话）
zl = o->ptr;
fptr = ziplistIndex(zl, ZIPLIST_HEAD);
if (fptr != NULL) {
// 定位到域 field
fptr = ziplistFind(fptr, field->ptr, sdslen(field->ptr), 1);
if (fptr != NULL) {
/* Grab pointer to the value (fptr points to the field) */
// 定位到域的值
vptr = ziplistNext(zl, fptr);
redisAssert(vptr != NULL);
// 标识这次操作为更新操作
update = 1;
/* Delete value */
// 删除旧的键值对
zl = ziplistDelete(zl, &vptr);
/* Insert new value */
// 添加新的键值对
zl = ziplistInsert(zl, vptr, value->ptr, sdslen(value->ptr));
}
}
// 如果这不是更新操作，那么这就是一个添加操作
if (!update) {
/* Push new field/value pair onto the tail of the ziplist */
// 将新的 field-value 对推入到 ziplist 的末尾
zl = ziplistPush(zl, field->ptr, sdslen(field->ptr), ZIPLIST_TAIL);
zl = ziplistPush(zl, value->ptr, sdslen(value->ptr), ZIPLIST_TAIL);
}
// 更新对象指针
o->ptr = zl;
// 释放临时对象
decrRefCount(field);
decrRefCount(value);
// 检查在添加操作完成之后，是否需要将 ZIPLIST 编码转换成 HT 编码
// #define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512
if (hashTypeLength(o) > server.hash_max_ziplist_entries)
hashTypeConvert(o, REDIS_ENCODING_HT);
// 添加到字典
} else if (o->encoding == REDIS_ENCODING_HT) {
// 添加或替换键值对到字典
// 添加返回 1 ，替换返回 0
if (dictReplace(o->ptr, field, value)) { /* Insert */
incrRefCount(field);
} else { /* Update */
update = 1;
}
incrRefCount(value);
} else {
redisPanic("Unknown hash encoding");
}
// 更新/添加指示变量
return update;
}
网友评论