从源码看redis的'map'结构

1,833 阅读5分钟

hset用来往map结构存入数据

> hset user:100 name paxi
(integer) 1

user:100是整个map结构的key,name是map中的一项字段值,通过hget就可以获取存入的结果

> hget user:100 name
"paxi"

hset命令执行追踪

hset的执行入口在 hsetCommand

Code.SLICE.source("robj *o = lookupKeyWrite(c->db,key);")
.interpretation("根据提供的dict本身的key,注意这里不是dict中元素的key,而是查找dict的key,比如 user:100 age 12 这里的key是 user:100");

Code.SLICE.source("if (o == NULL) {\n" +
        "        o = createHashObject();\n" +
        "        dbAdd(c->db,key,o);\n" +
        "    } else {\n" +
        "        if (o->type != OBJ_HASH) {\n" +
        "            addReply(c,shared.wrongtypeerr);\n" +
        "            return NULL;\n" +
        "        }\n" +
        "    }")
.interpretation("如果存在就仅校验是否是hash,满足条件返回;如果不存在就创建一个hash对象,并把这个key的关系存到了自己的db中");

map是不能存在key是一样的元素的,因而会先检查是否有同样的key,没有就再创建一个HashObject

Code.SLICE.source("unsigned char *zl = ziplistNew();\n" +
                "    robj *o = createObject(OBJ_HASH, zl);\n" +
                "    o->encoding = OBJ_ENCODING_ZIPLIST;\n" +
                "    return o;")
    .interpretation("默认创建的hash结构,它的编码方式使用的是ziplist");

默认的map结构使用的是ziplist的编码方式,当超过hash_max_ziplist_value(默认64)时则会将编码方式替换成 OBJ_ENCODING_HT

key存储

key这里指的是map整个结构的key,而不是map中的一个字段

为了方便区分分别以key和field区分,比如 user:100是整个map结构的key,name是map中的一项字段

lookupKeyWritedbAdd 追踪进去,key其实也是存在了一个dict的结构中

  Code.SLICE.source("typedef struct dict {\n" +
                "    dictType *type;\n" +
                "    void *privdata;\n" +
                "    dictht ht[2];\n" +
                "    long rehashidx; /* rehashing not in progress if rehashidx == -1 */\n" +
                "    unsigned long iterators; /* number of iterators currently running */\n" +
                "} dict;")
    .interpretation("字典结构")
    .interpretation("dictType使得redis可以对任意类型的key和value对应类型来操作")
    .interpretation("privdata存储用户传进来的值,key就是key,value就是value")
    .interpretation("dictht数组存储两个ht,在rehash的时候,ht[0]表示旧的,ht[1]表示新的,当rehash完成,再将ht[1]地址给ht[0]")
    .interpretation("rehashidx用来标识是否正在进行rehash,没有进行的时候是-1")
    .interpretation("iterators表示当前正在进行遍历的iterator的个数,如果要进行rehash,但是当前有迭代器正在进行遍历,不会进行rehash");

注意到 dicthtrehashidx 这两个字段的存在,使得redis方便进行扩容,dictht是redis存储数据的地方,rehashidx用来表示,当前扩容到哪儿了,如果一个map的filed非常的多,那么扩容过程中需要的拷贝量非常大,所以redis选择了使用两个 dictht 来是想逐步的拷贝

field与value的存储

map结构首先存储的方式是使用ziplist,当数据过大,不适合ziplist的时候才选用 OBJ_ENCODING_HT,在存储的时候也需要对应的做不同的处理

  //...
Code.SLICE.source("if (o->encoding == OBJ_ENCODING_ZIPLIST){" +
        "..." +
        " if (hashTypeLength(o) > server.hash_max_ziplist_entries)\n" +
        "            hashTypeConvert(o, OBJ_ENCODING_HT);" +
        "}")
        .interpretation("根据编码方式来做不同的set,如果是 ZIPLIST,插入完成之后,会统计当前存储的个数,如果超过了 hash_max_ziplist_entries (512) 那么转换为  OBJ_ENCODING_HT ");
Code.SLICE.source("} else if (o->encoding == OBJ_ENCODING_HT) {")
    .interpretation("处理 HashTable的编码方式");
Code.SLICE.source("         dictEntry *de = dictFind(o->ptr,field);")
    .interpretation("在当前key对应的dict中去查找,有没有这个字段对应的值");
Code.SLICE.source("         if (de) {\n" +
                "            sdsfree(dictGetVal(de));\n" +
                "            if (flags & HASH_SET_TAKE_VALUE) {\n" +
                "                dictGetVal(de) = value;\n" +
                "                value = NULL;\n" +
                "            } else {\n" +
                "                dictGetVal(de) = sdsdup(value);\n" +
                "            }\n" +
                "            update = 1;\n" +
                "        }")
.interpretation("如果存在释放原来的dict中值的空间,插入新的值,并标识是更新");
//...
Code.SLICE.source("dictAdd(o->ptr,f,v);")
    .interpretation("将key和value加入到dict中");
//...

以HT为例,field存储之前,先要看容量是不是够,不够就需要先进行扩容

Code.SLICE.source("if (dictIsRehashing(d)) return DICT_OK;")
                .interpretation("如果已经在rehash了,那么不需要再次扩容");
Code.SLICE.source("if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);")
        .interpretation("如果dict当前没有分配空间,默认扩容为为4个数组长度");
Code.SLICE.source("  if (d->ht[0].used >= d->ht[0].size &&\n" +
        "        (dict_can_resize ||\n" +
        "         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))")
        .interpretation("当已经使用的量不小于分配的量,并且比例已经超过默认占比(默认值为5)进行扩容或者可以进行resize");
Code.SLICE.source(" return dictExpand(d, d->ht[0].used*2);")
        .interpretation("扩容为使用量的2倍");
  • size:分配的空间,也就是每个table的数组个数它一定是2的幂次方
  • used:表示map中已经添加了的元素个数

当遇到满足的条件则进行扩容,扩容后再选择存储

Code.SLICE.source("if (dictIsRehashing(d)) _dictRehashStep(d);")
            .interpretation("如果dict正在执行Rehash先执行一步rehash");
Code.SLICE.source("if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)\n" +
                 "        return NULL;")
        .interpretation("计算出当前key在dict中的下标,如果在那个下标已经有这个key了,返回添加失败");
Code.SLICE.source("ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];")
        .interpretation("根据是否在rehash来保证新的元素只会放在心的entry列表里面");
Code.SLICE.source(" entry = zmalloc(sizeof(*entry));")
        .interpretation("分配新的entry的空间");
Code.SLICE.source(" entry->next = ht->table[index];\n" +
                "    ht->table[index] = entry;\n" +
                "    ht->used++;")
        .interpretation("将新的entry放在第一个dict链表的第一位,并增加使用量");
Code.SLICE.source(" dictSetKey(d, entry, key);")
        .interpretation("把key存入entry");

field按照上述方式存储完毕后,再存入value到dictEntry

结论

hash底部使用dict的结构存储,每个dict会自带当前的数据类型对应hash计算函数等,以及是否正在进行rehash,为了实现Rehash,它自己会有两个hash表的引用,每个hash表都存一个entry的数组,当遇到冲突的时候,就使用链表的方式来解决

附录

redis命令使用测试地址
hset源码追踪细节
Redis内部数据结构详解(1)——dict -- 张铁蕾