Redis5.0源码 - 数据结构 - 字典

 

字典,又称符号表、关联数组或映射,是一种用于保存键值对(key-value pair)的抽象数据结构。Redis使用的C语言并没有内置字典这种数据结构,所以Redis构建了自己的字典实现。

设计

  • 相关文件:dict.hdict.c

Redis的字典使用哈希表作为底层实现。一个哈希表里可以有多个哈希表节点。每个哈希表节点保存着一个键值对。

哈希表的实现

/* 哈希表节点,每个dictEntry结构都保存着一个键值对 */
typedef struct dictEntry {
    void *key;      // 键
    union {         // 值
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下一个哈希表节点,用于解决键冲突
} dictEntry;

/* 哈希表 */
typedef struct dictht {
    dictEntry **table;      // 哈希表节点数组
    unsigned long size;     // 哈希表大小
    unsigned long sizemask; // 哈希表大小掩码,用于计算索引值,总是等于size-1
    unsigned long used;     // 该hash表已有节点的数量
} dictht;

下图展示了一个大小为4的哈希表,其中k1和k0产生了键冲突,通过next形成了链表。

哈希表结构

字典的实现

typedef struct dictType {
    /* 计算hash值的函数 */
    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;

/* 字典 */
typedef struct dict {
    dictType *type;     // 特定于类型的处理函数
    void *privdata;     // 类型处理函数的私有数据
    dictht ht[2];       // 哈希表
    long rehashidx;     // rehash索引,当没进行rehash时,值为-1
    unsigned long iterators; // 当前正在运行的迭代器数量
} dict;

在这里可以看到,字典结构中用了两个哈希表,一般情况下只使用哈希表ht[0]ht[1]只会在对哈希表h[0]进行rehash时被使用。

哈希算法

// 计算hash值
#define dictHashKey(d, key) (d)->type->hashFunction(key)

在Redis5.0字典的哈希表底层实现时,计算hash值默认采用了SipHash 1-2算法替换了之前的Murmurhash2算法,并在siphash.c中实现。

rehash(重哈希)

rehash指的就是因为哈希表size的变化,导致需要重新计算键的哈希值和索引值。

// 是否正在rehash
#define dictIsRehashing(d) ((d)->rehashidx != -1)

随着不断的操作,哈希表保存的键值对会逐渐增加或减少。为了使哈希表的装载因子(load factor)维持在一个合理范围,Redis使用rehash对哈希表进行伸缩。这里的rehashidx用于记录rehash的进度(例如当前rehash到ht[0].table[idx]处,则rehashidx等于idx的值。每一个ht[0].table[idx]在代码注释中被称为bucket(桶),即每个桶对应一个键,即每个桶都对应一个键值对的链表)。

  1. 扩容和缩容

    • 扩容(_dictExpandIfNeeded):
      • 服务器没有执行bgsave或bgrewriteaof操作(dict_can_resize=1),当hash表中元素的个数大于等于ht[0].size时,就会开始扩容,扩容的新数组的大小为第一个不小于ht[0].size * 2的2^n的数。
      • 如果Redis正在做bgsave,为了减少内存页的过多分离 (Copy On Write),Redis尽量不去扩容(dict_can_resize=0)。但是当元素的个数已经达到了ht[0].size的5倍 (dict_force_resize_ratio),说明hash表已经过于拥挤了,这个时候就会强制扩容
    • 缩容(dictResize):ht[1]的大小为第一个大于等于ht[0].used的2^n的数。
  2. 将ht[0]上的所有键值对rehash到ht[1]上(旧表ht[0]上删一个,新表ht[1]上增一个)。并且rehash不是一次完成(每次重哈希n个桶)。

  3. 迁移全部完成后,释放哈希表ht[0],并将ht[1]设置成ht[0],然后为ht[1]设置空表。

:另外,字典rehash过程还会穿插到键值对的增加或删除操作中,即此时字典正在rehash,每次增加或删除操作过程中都会rehash一个bucket。

增加和删除键值对操作

  1. 增加
    1. 首先需要判断该键值对是否存在:如果没在rehash,只查找表0;正在rehash,顺序查找表0和表1;
    2. 若不存在,则进行插入操作:如果没在rehash,插入表0;正在rehash,插入表1;

常用API

函数 作用
dictCreate 创建一个新的字典
dictRelease 清空和释放字典
dictEmpty 清空字典
dictAdd 在字典中加入一个键值对
dictDelete 在字典中删除指定的键值对
dictReplace 增加或覆盖键值对
dictRehash 单次rehash
dictRehashMilliseconds rehash直到完成(每ms秒执行一次dictRehash
dictGetIterator 获取字典的迭代器对象
dictNext 根据提供的迭代器获取下一个键值对
dictReleaseIterator 释放迭代器

懵逼点

将二进制逆序的奇技淫巧

/* Function to reverse bits. Algorithm from:
 * http://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel */
static unsigned long rev(unsigned long v) {
    unsigned long s = 8 * sizeof(v); // bit size; must be power of 2
    unsigned long mask = ~0;
    while ((s >>= 1) > 0) {
        mask ^= (mask << s);
        v = ((v >> s) & mask) | ((v << s) & ~mask);
    }
    return v;
}

PS:这个注释中的链接指向的页面里都是一些处理二进制的奇技淫巧,代码精简高效,但晦涩难懂。