RedisHash数据结构的底层实现
⽂章⽬录
1.前⾔
redis的哈希对象的底层存储可以使⽤ziplist（压缩列表）和hashtable。当hash对象可以同时满⾜⼀下两个条件时，哈希对象使⽤ziplist编码。
哈希对象保存的所有键值对的键和值的字符串长度都⼩于64字节
哈希对象保存的键值对数量⼩于512个
2.hash数据结构图
redis的hash架构就是标准的hashtable的结构，通过挂链解决冲突问题。
2.1 hash数据结构
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存储。
3.1ziplist 存储结构
ziplist并没有定义明确的结构体, 根据存储结构我们可以定义ziplist如下, 只是进⾏演⽰使⽤.其中content字段存储实际的实体内容, 实体/*Hash 表⼀个节点包含Key,Value 数据对 */typedef struct dictEntry {    void *key;    union {        void *val;        uint64_t u64;        int64_t s64;        double d;    } v;    struct dictEntry *next; /* 指向下⼀个节点, 链接表的⽅式解决Hash 冲突 */} dictEntry; /* 存储不同数据类型对应不同操作的回调函数 */typedef struct dictType {    unsigned int (*hashFunction)(const void *key);   
void *(*keyDup)(void *privdata, const void *key);    void *(*valDup)(void *privdata, const void *obj);    int (*keyCompare)(void *privdata, const void *key1, const void *key2);    void (*keyDestructor)(void *privdata, void *key);    void (*valDestructor)(void *privdata, void *obj);} dictType; typedef struct dictht {    dictEntry **table; /* dictEntry*数组,Hash 表 */    unsigned long size; /* Hash 表总⼤⼩ */    unsigned long sizemask; /* 计算在table 中索引的掩码, 值是size-1 */    unsigned long used; /* Hash 表已使⽤的⼤⼩ */} dictht; typedef struct dict {    dictType *type;    void *privdata;    dictht ht[2]; /* 两个hash 表,rehash 时使⽤*/    long rehashidx; /* rehash 的索引, -1表⽰没有进⾏rehash */    int iterators; /*  */} dict;
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
redis五种数据结构27
28
29
30
31
32
33
34
35
36
3.2 连锁更新
前⾯说过，每个节点的previous_entry length 属性都记录了前⼀个节点的长度：
(1)如果前⼀节点的长度⼩于254 字节，那么previ ous  entry_length 属性需要⽤ 1字节长的空间来保存这个长度值。
(2)如果前⼀节点的长度⼤于等于254 字节，那么previous entry length 属性需要⽤5 字节长的空间来保存这个长度值。
如果我们将⼀个长度⼤于等于 254 字节的新节点 new 设置为压缩列表的表头节点，那么⿇烦的事情来了，由于previous entry length⼤⼩不够⽤(1->5B)，后⾯所有的节点可能都要重新分配内存⼤⼩。因为连锁更新在最坏情况下需要对压缩列表执⾏ N 次空间重分配操作，⽽每次空间重分配的最坏复杂度为 O(N) ， 所以连锁更新的最坏复杂度为 O(N^2) 。
但是呢，尽管连锁更新的复杂度较⾼，但它真正造成性能问题的⼏率是很低的。
(1)⾸先，压缩列表⾥要恰好有多个连续的、长度介于250 字节⾄253 宇节之间的节点，连锁更新才有可能被引发，在实际中，这种情况并不多见；
(2)其次，即使出现连锁更新，但只要被更新的节点数量不多，就不会对性能造成任何影响：⽐如说，对三五个节点进⾏连锁更新是绝对不会影响性能的；
因为以上原因， ziplistPush 等命令的平均复杂度仅为0（的，在实际中，我们可以放⼼地使⽤这些函数，⽽不必担⼼连锁更新会影响压缩列表的性能。
redis hash 存储过程源码分析以hset命令为例进⾏分析，整个过程如下：⾸先查看hset中key对应的val
ue是否存在，hashTypeLookupWriteOrCreate。判断key和value的长度确定是否需要从zipList到hashtable 转换，hashTypeTryConversion。对key/value进⾏string层⾯的编码，解决内存效率问题。更新hash节点中key/value问题。
其他后续操作的问题typedef struct ziplist{    /*ziplist 分配的内存⼤⼩*/    uint32_t bytes;    /*达到尾部的偏移量*/    uint32_t tail_offset;    /*存储元素实体个数*/    uint16_t length;    /*存储内容实体元素*/    unsigned char* content[];    /*尾部标识*/    unsigned char end;}ziplist;/*元素实体所有信息, 仅仅是描述使⽤, 内存中并⾮如此存储*/typedef struct zlentry {    /*前⼀个元素长度需要空间和前⼀个元素长度*/    unsigned int prevrawlensize, prevrawlen;    /*元素长度需要空间和元素长度*/    unsigned int lensize, len;    /*头部长度即prevrawlensize + lensize*/    unsigned int headersize;    /*元素内容编码*/    unsigned char encoding;    /*元素实际内容*/    unsigned char *p;}zlentry;
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
判断key/value的长度是否超过规定的长度64个字节，由REDIS_HASH_MAX_ZIPLIST_VALUE定义。如果超过64个字节那么久需要将ziplist转成hashtab对象。
hash底层的更新操作函数hashTypeSet内部会根据是ziplist还是hashtable进⾏不同的处理逻辑，在ziplist当中会判断ziplist存储数据的长度来判断是否需要转为hashtable 数据结构，其中长度判断是通过#define REDIS_HASH_MAX_ZIPLIST_ENTRIES 512定义的。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 ? : );    // 发送键修改信号    signalModifiedKey(c->db,c->argv[1]);    // 发送事件通知    notifyKeyspaceEvent(REDIS_NOTIFY_HASH,"hset",c->argv[1],c->db->id);    // 将服务器设为脏    server.dirty++;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2223
24
25
26
27
28/*  * 对 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;        }    }}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/*  * 将给定的 field-value 对添加到 hash 中， * 如果 field 已经存在，那么删除旧的值，并关联新值。
1
2
3
4
* * 这个函数负责对 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) {456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。