Redis 数据结构(dict)实现

一、什么是字典?

字典又称为hash、或者映射(map)、是一种保存键值对的数据结构。
字典中的每一个key都是独一无二的,可以通过key进行、查询、添加、删除、修改操作。

二、哈希表

哈希表是最常用的数据结构之一,对于其用法,大家都非常熟悉,这里详细探讨一下其原理。哈希表的底层实际上是基于数组来存储的,当插入键值对时,并不是直接插入该数组中,而是通过对键进行Hash运算得到Hash值,然后和数组容量取模,得到在数组中的位置后再插入。取值时,先对指定的键求Hash值,再和容量取模得到底层数组中对应的位置,如果指定的键值与存贮的键相匹配,则返回该键值对,如果不匹配,则表示哈希表中没有对应的键值对。这样做的好处是在查找、插入等操作可以做到𝑂(1),最坏的情况是𝑂(𝑛),当然这种是最极端的情况,极少遇到。

1、hash函数

通过hash函数把不同的键转化为唯一的整数m,redis使用siphash算法、

问题:
我们很难保证把每一个 ”键“ 通过哈希函数转化为不同的”索引“, ”键“通过hash函数得到的”索引”分布越均匀越好。

不管是整数、浮点型、字符串等都可以转化为整型,

原则:
    1、一致性。
    2、高效性:计算高效简洁。
    3、均匀性:哈希值均匀分布。

hash冲突

  1. 两个不同的 ”键“ 通过 hash 函数转化为了同样的索引,这就叫 hash冲突。
  2. redis的哈希表的每个hash节点都有一个 next指针,把冲突的节点通过next连接起来,形成一个单向链表,这样就解决了hash冲突。
  3. redis考虑性能,如果有hash冲突,并且已经有新的节点,采用头插法,插入链表的第一个元素,时间复杂度为 o(1)。

    例如插入下标为0的的元素

    image

    如果下次通过hash函数计算出下标为还是为0,那么如下,采用头插法,把k2插入到k1之前,并形成单向链表。
    image

三、字典的结构体定义

redis字典结构体代码在dict.h中定义

1、hash表

typedef struct dictht {
    dictEntry **table; // hash表数组,指向 dictEntry结构体
    unsigned long size; // table 数组的大小。
    unsigned long sizemask; //掩码 = size - 1
    unsigned long used; // table数组已存在元素个数~~~~
} dictht;

image

2、hash表的节点

typedef struct dictEntry {
    void *key; 
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; //单链表~~~~
} dictEntry;
key保存的是键值对中的键,而v保存键值对中的值,next表示hash冲突时指向的另一对键值对,通过头插法,形成单向链表。

image

3、redis字典

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;

image

1、ht 是一个包含了 ht[0] 和 ht[1]两个hash桶,默认情况下是不会使用 ht[1]的,只有在 rehash的时候才会使用。
2、rehashidx字段,默认为 -1,表示没有进行rehash,否在会标记正在进行rehash的index。

二、基本操作

2、添加

流程图
image

代码

1、从 setKey开始:检查 key是否存在,不存在走dbAdd。

void setKey(redisDb *db, robj *key, robj *val) {
    if (lookupKeyWrite(db,key) == NULL) { //检查key是否存在
        dbAdd(db,key,val); //不存在插入
    } else {
        dbOverwrite(db,key,val);
    }
    incrRefCount(val);
    removeExpire(db,key);
    signalModifiedKey(db,key);
}

2、创建sds字符串,执行 dictAdd函数

void dbAdd(redisDb *db, robj *key, robj *val) {
    sds copy = sdsdup(key->ptr); //创建字符串
    int retval = dictAdd(db->dict, copy, val);//插入

    serverAssertWithInfo(NULL,key,retval == DICT_OK);
    if (val->type == OBJ_LIST ||
        val->type == OBJ_ZSET)
        signalKeyAsReady(db, key);
    if (server.cluster_enabled) slotToKeyAdd(key);
}

3、dictAdd调用 dictAddRaw 函数插入 key值。

int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

4、dictAddRaw 进行如下操作

  • 判断是否在 rehash,如果是,执行一次 rehash。
  • 获取新元素的索引,如果元素已经存在,否则返回-1。
  • 是否在进行 rehash,如果是插入 ht[1],否则插入 ht[0]
  • 申请新的内存给新的节点,并插入。
  • 给新创建的 dictEntry,赋值 key,并返回新的节点
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d); //判断是否在 rehash。

     //获取新元素的索引,如果元素已经存在,则返回-1
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    //是否在进行 rehash,如果是插入 ht[1],否则插入 ht[0]
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    //申请新的内存给新的节点,并插入
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;//加一个元素

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);
    return entry; //返回新的节点
}

设置 key

#define dictSetKey(d, entry, _key_) do { \
    if ((d)->type->keyDup) \
        (entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
    else \
        (entry)->key = (_key_); \
} while(0)

5、如果返回的节点不为null,给新的 entry设置 val

#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        (entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
    else \
        (entry)->v.val = (_val_); \
} while(0)

gdb
1、setkey,判断key是否存在,不存在走dbAdd。
image
2、dbAdd 插入键值对。调用 dictAddRaw 函数
image
3、dictAddRaw,添加键,如果不存在插入新的节点,存在,返回null
image
4、dictSetVal,根据返回的节点,设置 value。
image

3、修改。

流程图
image

代码

1、从 setKey开始:检查 key是否存在,存在走 dbOverwrite。

void setKey(redisDb *db, robj *key, robj *val) {
    if (lookupKeyWrite(db,key) == NULL) { //检查key是否存在
        dbAdd(db,key,val); //不存在插入
    } else {
        dbOverwrite(db,key,val);
    }
    incrRefCount(val);
    removeExpire(db,key);
    signalModifiedKey(db,key);
}

2、执行dbOverwrite,

  • 先调用 dictFind查找key是否存在
  • 不存在执行中断
  • 存在先获取老节点的值
  • 给节点设置新的值
  • 释放老节点的val
void dbOverwrite(redisDb *db, robj *key, robj *val) {
    dictEntry *de = dictFind(db->dict,key->ptr);//查找key的节点

    serverAssertWithInfo(NULL,key,de != NULL); //不存在执行中断
    dictEntry auxentry = *de; 
    robj *old = dictGetVal(de);//获取老节点的值
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        val->lru = old->lru;
    }
    dictSetVal(db->dict, de, val);//给节点设置新的值

    if (server.lazyfree_lazy_server_del) {
        freeObjAsync(old);
        dictSetVal(db->dict, &auxentry, NULL);
    }

    dictFreeVal(db->dict, &auxentry); //释放老节点的val
}

dictFind 查找 key是否存在

  • 如果 ht[0]和ht[1]没有节点,返回 null。
  • 是否在进行 rehash,如果是执行一次rehash。
  • 循环遍历获取 key的节点,找到返回,否则返回null。
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    uint64_t h, idx, table;

    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

gdb
image
image

4、删除

调用的是dictDelete中。实则调用的是 dictGenericDelete函数。

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    uint64_t h, idx;
    dictEntry *he, *prevHe;
    int table;

    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;

    if (dictIsRehashing(d)) _dictRehashStep(d);
    h = dictHashKey(d, key);

    //遍历 ht[0] 和 ht[1],循环遍历,找到节点,删除
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        prevHe = NULL;
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                /* Unlink the element from the list */
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                    zfree(he);
                }
                d->ht[table].used--;
                return he;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL; /* not found */
}

缩容:

htNeedsResize 判断当前的 dict是否需要缩容。

如:
HASHTABLE_MIN_FILL = 10
size = 16
used = 1
判断是否可以缩容,最小容量为4。
例如:
容量为16(size),当used为1,时,才能缩容。
如:(used*100/size < HASHTABLE_MIN_FILL)) = 100/16 < 10;

int htNeedsResize(dict *dict) {
    long long size, used;

    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}
void tryResizeHashTables(int dbid) {
    if (htNeedsResize(server.db[dbid].dict))
        dictResize(server.db[dbid].dict);
    if (htNeedsResize(server.db[dbid].expires))
        dictResize(server.db[dbid].expires);
}

gdb
缩容前 size = 16
image

缩容后 size = 4
image

5、扩容 和 渐进式 rehash。

扩容

默认为4个dictEntry,当插入的元素主键增多,容量上限时,会触发扩容。
image
image

  • 通过调用栈可以看到,通过dictAdd,dictAddRaw,会执行 _dictExpandIfNeeded,判断是否需要扩容,走到dictExpand。
  • 通过 gdb可以看到需要当前库容 为 p d->ht[0].used*2 = 18
  • 执行_dictNextPower,检查库容后的值,必须为 2 的 N 次方。最小为4。
  • 申请一个新的 dictEntry,并赋值给 ht[1]。
  • 把前的 rehashidx 复制为 0,表示正在进行rehash。
  • 前面的添加操作可以看到添加时,会判断是否在rehahash,如果是,会添加到ht[1]上,而修改、删除、查询、则会在两个ht中查找。
static int _dictExpandIfNeeded(dict *ht) {
    /* If the hash table is empty expand it to the initial size,
     * if the table is "full" dobule its size. */
    if (ht->size == 0)
        return dictExpand(ht, DICT_HT_INITIAL_SIZE);
    if (ht->used == ht->size)
        return dictExpand(ht, ht->size*2);
    return DICT_OK;
}
int dictExpand(dict *d, unsigned long size)
{
    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}
   

满 8 后,后续插入到 ht[1]中,如下:
image

(gdb) p d
$10 = (dict *) 0x7ff810c0b360
(gdb) p *d
$11 = {type = 0x786a40 <dbDictType>, privdata = 0x0, ht = {{table = 0x7ff810c15100, size = 8, sizemask = 7, used = 8}, {table = 0x7ff8088c4000, size = 16, 
      sizemask = 15, used = 1}}, rehashidx = 0, iterators = 0}

渐进式rehash

  • 创建足够的空间,给ht[1],如果上述 8扩容至16,每次*2。
  • 把 rehashidx 从 -1 改为 1,表示正在进行rehash。
  • 重新计算 ht[0] 中 键对应的hash值,依次添加到 ht[1]。
  • rehash操作完成后,清空ht[0],对调一下ht[1]和ht[0]
  • 把rehashidex 修改为-1

rehash完成的结果

(gdb) 
$18 = {type = 0x786a40 <dbDictType>, privdata = 0x0, ht = {{table = 0x7ff8088c4000, size = 16, sizemask = 15, used = 9}, {table = 0x0, size = 0, sizemask = 0, 
      used = 0}}, rehashidx = -1, iterators = 0}

image


 6、迭代器(待补充)
 

思考:

1、php和redis实现的区别及rehash的区别?为什么要这么做?

区别:

php的数组结构,分为索引数组和bucket两个,索引数组用来记录存数据真正放在 bucket的那一个索引。如果通过hash函数计算的值有冲突通过, 通过 zval 的 next 链接起来,解决了hash冲突,这一点和redis一样的原理,php这种方式保证了是有序存放的,而redis的字典存储是无序的。

image

php 的rehash是一次性扩容,只有一个ht,把旧的ht直接放到新的ht。

测试在php脚本中(使用一个比较大的数组测试扩容)耗时

<?php
 ini_set('memory_limit','256M');
 //$start = microtime(true);

 $startMemory = memory_get_usage();
 $t1 = microtime(true);
 $arr = [];
 for ($i = 0 ; $i < 2097152; $i ++) {
   $arr[$i] = $i;
 }
 
 $arr[] = '触发扩容';

//结束
$t2 = microtime(true);
$endMemory = memory_get_usage();

//输出
echo sprintf("内存使用: %f kb<br>", ($endMemory - $startMemory) / 1024);
echo sprintf("耗时: %f秒<br>", round($t2-$t1,3));
扩容前:
内存使用: 65540.187500 kb 耗时: 0.303000秒
扩容后:
内存使用: 131076.187500 kb 耗时: 0.396000秒

可以看到 大概扩容耗时在 50- 100 毫秒。

为什么这么做?

因为php是多进程模型的(master、worker),而在php业务中,数组的大小普遍会比较小,就算是在一个rehash一个比较大的数组,因为是多进程模型是可以接受的,不会堵塞所有的进程。 而redis是单进程、单线程,dict是存储数据库的,会存储海量的数据,几百万,几千万、甚至几个亿,这个时候如果不采用渐进式的rehash,而是使用php的rehash的操作,有很大的可能会造成服务器的短暂瘫痪,这对于高性能的redis是不可接受的。

评论

暂无评论