Redis

Redis数据结构-字典

Redis源码学习

Posted by Simon on July 3, 2020

“Better code, better life. ”

Redis数据结构–字典

字典（Dictionary）在程序语言中又被称为哈希表（Hash Table）或者映射（Map），是一种用于保存键值对的抽象数据结构。字典中的每个键都是唯一的，可以通过键查找与之关联的值，或者更新键所苦暗恋的值。

字典在Redis中的使用也相当广泛，Redis最终要的数据库就是用字典来作为底层实现的，对数据库的增删改查也都建立在对字典的操作之上。其次，哈希键的底层实现也用到了字典。

定义

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    uint64_t (*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;

/* This is our hash table structure. Every dictionary has two of this as we  
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

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;

/* If safe is set to 1 this is a safe iterator, that means, you can call  
 * dictAdd, dictFind, and other functions against the dictionary even while  
 * iterating. Otherwise it is a non safe iterator, and only dictNext()   
 * should be called while iterating. */
typedef struct dictIterator {
    dict *d;
    long index;
    int table, safe;
    dictEntry *entry, *nextEntry;
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;
} dictIterator;

上面是redis/src/dict.h中关于字典的一些定义。

  • 其中dictEntry保存字典中的键值对，key显然为键值对中的键，而键值对的值由一个union保存，它可以是一个指针，也可以是一个64位的整数。最后有一个next指针，它是用来解决hash冲突的，所有hash值相同的键值对会被放在这个链表上。
  • dictType是针对不同类型的键值对，为创建多态字典而设置的。dictType中有5个函数指针，分别是哈希函数、键的复制函数、值的复制函数、键的对比函数、值的对比函数。
  • dictht是字典底层结构的定义。第一个元素table是一个数组，数组的元素是指向dictEntry结构的指针。size是哈希表大小，sizemask是哈希表大小掩码，总是等于size-1，used是已有的节点数目。
  • dict是我们操作用的字典的定义，在dictht上层封装一个dict主要是出于辅助rehash的目的。其中type和privdata是用来针对不同类型的键值对；ht是一个含有两个元素的数组，一般情况下只会用到ht[0]，h[1]只有当对h[0]做rehash操作时才会使用；rehashidx是用来标记当前rehash的进度，如果没有在进行rehash操作，其为-1；最后一个是一个字典元素的迭代器，类似rehashidx。
  • dictIterator是字典迭代器，其持有一个dict类型的指针，两个dictEntry类型的指针，以及一系列标志位。其中值得注意的就是safe字段，正如注释中所说，如果safe为1，表明这是一个安全的迭代器，你可以在迭代过程中调用add、find之类的函数，否则，只能调用dictNext()。

哈希算法

对一个哈希表来说，其最关键的算法就是哈希算法。一个好的哈希算法应该符合以下条件：

  • 算法本身计算量小。
  • 对所有的键尽可能的减少哈希冲突。
  • 尽可能的节省空间。

我们来看一下源码中对字典键值对的操作函数：

//以下代码位于redis/src/dict.c文件中
/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);
	//#define DICT_ERR 1
    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry.  
     * Insert the element in top, with the assumption that in a database   
     * system it is more likely that recently added entries are accessed  
     * more frequently. */
    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;
}

static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    for (table = 0; table <= 1; table++) {
        idx = hash & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

#define dictHashKey(d, key) (d)->type->hashFunction(key)

#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)

上面的源码里一共有三个函数和一个宏，其中dictAdd是往一个字典里插入一个键值对的入口函数。dictAdd先是调用了addRaw去尝试添加一个新元素，而在addRaw中又判断需要插入的key是否已经存在，_dictKeyIndex这个函数会返回key在字典中的索引，如果key已经存在，则返回-1。综上所述，dictAdd方法只能成功插入新的节点，如果key已存在，会返回DICT_ERR。

再看下面几个函数：

dictEntry *dictAddOrFind(dict *d, void *key) {
    dictEntry *entry, *existing;
    entry = dictAddRaw(d,key,&existing);
    return entry ? entry : existing;
}

int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;
 
    /* Try to add the element. If the key  
     * does not exists dictAdd will succeed. */
    entry = dictAddRaw(d,key,&existing);
    if (entry) {
        dictSetVal(d, entry, val);
        return 1;
    }

    /* Set the new value and free the old one. Note that it is important  
     * to do that in this order, as the value may just be exactly the same  
     * as the previous one. In this context, think to reference counting,  
     * you want to increment (set), and then decrement (free), and not the  
     * reverse. */
    auxentry = *existing;
    dictSetVal(d, existing, val);
    dictFreeVal(d, &auxentry);
    return 0;
}

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);

    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 */
}

int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

dictAddOrFind函数是addRaw的简化版，先尝试添加一个entry，如果添加失败则返回已有元素的地址；dictReplace是先添加元素，如果key不存在，则直接调用dictSetVal后返回成功，否则dictSetVal后要对原entry做释放操作，注意是先set在free，原因在注释中说的很清楚；dictGenericDelete是从一个字典中删除一个元素，并返回删除的节点，如果Key不存在则返回null。

rehash

前面一节讲了字典增删改查的基本操作，通过源码也能看出，redis的字典通过链地址法哈希冲突，每个节点都有一个next指针，多个hash值相同的哈希表节点可以通过next指针构建成一个单向链表。

随着哈希表保存的键值对不断增加，哈希碰撞的情况也会不断增加，链表的长度越长，则操作的时间复杂度越高；如果哈希表键值对不断减少，那么原来申请的大量的空间就会浪费掉。redis用负载因子来表述这一复杂度。为了让负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩，也就是我们将要介绍的rehash。

rehash主要有以下几个步骤：

  • 为h[1]哈希表分配空间，分配的大小取决于要执行的操作，以及ht[0]当前包含的键值对的数量（也即是h[0].used这个属性值）：如果执行的操作是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n；如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n。
  • 将保存在ht[0中的所有键值对rehash到ht[1]上面：rehash指的是重新计算哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置。
  • 迁移完毕后释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]的位置新创建一个空白的哈希表，为下一次rehash做准备。

源码

static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;

static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* If we reached the 1:1 ratio, and we are allowed to resize the hash    
     * table (global setting) or we should avoid it but the ratio between  
     * elements/buckets is over the "safe" threshold, we resize doubling  
     * the number of buckets. */
    if (d->ht[0].used >= d->ht[0].size &&
        (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
    {
        return dictExpand(d, d->ht[0].used*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;
}

static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX + 1LU;
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}

_dictExpandIfNeeded是判断当前dict是否需要扩张，其判断条件写的很清楚

if (d->ht[0].used >= d->ht[0].size &&
    (dict_can_resize ||
     d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
    return dictExpand(d, d->ht[0].used*2);
}

  1. 当前entry数量大于ht的大小

  2. dict_can_resize为真或者entry数量大于ht大小的5倍

_dictNextPower方法的功能很清楚，给定一个数，返回第一个大于它的2的n次幂。

所以字典的扩张和收缩都是用dictExpand这一个函数！收缩的时候只要传一个较小的值就可以！

渐进式rehash

上一部分说过，扩展或者收缩字典需要将字典的一个个entry从ht[0]重新散列到ht[1]，这一部分我们来仔细的讲一下这个过程。

首先，重新散列的过程不是一次性的，而是分多次、渐进式的。这么做的原因在于，如果ht[0]里只保存着四个键值对，那服务器可以瞬间完成rehash动作，但如果存放了四百万甚至四亿个键值对呢？一次性rehash所有键值对的庞大计算量可能会导致服务器在一段时间内停止工作，这是不能接受的。

所以就有了所谓的渐进式rehash。下面是字典渐进式rehash的详细步骤：

  • 为h[1]分配空间。
  • 在字典中维持一个索引计数器变量rehashidx，并将它置为0，表示rehash正式开始。
  • 在rehash期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]上，完成后将rehashidx加1。
  • 随着操作的不断执行，最终在某个时间点上，ht[0]的所有字段都rehash完成，会把ht[1]替换为新的ht[0]。

注意：

  1. 在渐进式rehash的过程中，字典会同时使用两个哈希表，所以在这期间的所有查找、删除等操作，除了在 ht[0] 上进行，还需要在 ht[1] 上进行。

  2. 在执行添加操作时，新的节点会直接添加到 ht[1] 而不是 ht[0] ，这样保证 ht[0] 的节点数量在整个 rehash 过程中都只减不增。

CATALOG
    FEATURED TAGS
    生活 Python VNPY Data Analyse Linux OS Program Trading Notes Fantasy Data Structure Boost C++11 ARTS Redis 随笔 数据库 Golang C++ 分布式系统 gRPC Protobuf golang 6.S081
    FRIENDS