redis的字典

发表于

字典

字典在redis中的应用比较广泛，比如redis的数据库，哈希键的底层实现等等

字典的实现

redis的字典用哈希表表示，一个哈希表有多个哈希表结点，每个结点保存一个键值对。

哈希表

1
2
3
4
5
6
typedef struct dictht {
    dictEntry **table;//哈希表数组，每个元素为指向dictEntry的指针
    unsigned long size;
    unsigned long sizemask;//等于size-1，与哈希值一起决定key应该放在哪个索引
    unsigned long used;
} dictht;

哈希表结点

1
2
3
4
5
6
7
8
9
typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next;//可用于解决哈希冲突
}dictEntry;

字典

1
2
3
4
5
6
typedef struct dict {
    dictType *type;
    void* privdata;
    dictht ht[2];
    int trehashidx;
}

type属性是一个指向dictType的指针，dictType结构保存了一组用于操作特定类型键值对的函数，实现多台。

pricdata则保存了需要传给那些类型特定参数的可选参数。

ht保存了两个dictht，一般只是用第一个，第二个会在第一个rehash的时候被使用。

trehashidx则是记录了目前是否在进行rehash。

哈希算法

当添加一个新的键值对到字典的时候，程序依次计算出哈希值和索引值，再根据索引值把包含新键值对的哈希表结点加到哈希数组指定索引上面

1
2
hash = dict->type->hashFunction(key);
index = hash & dict->ht[x].sizemask;

ht[x]是因为有可能在第一个字典或者第二个。

另外，redis使用murmurhash2算法来计算哈希值。

解决键冲突

redis解决hash冲突的方法是链地址法，则产生冲突时使用next指针将索引值相同的结点连起来。

rehash

哈希表的负载因子=哈希表已保存的结点数量/哈希表大小

为了使得哈希表的负载因子维持在一个合理的范围内，哈希表需要扩展或者缩小。

步骤为

  1. 为ht[1]分配空间，大小取决于：
  • 扩展：大小为 大于或等于ht[0].used*2 = 2^n
  • 收缩：大小为 大于或等于ht[0].used = 2^n
  1. 将保存在ht[0]的所有键值对rehash到ht[1]上，重新计算哈希值和索引值；
  2. 释放ht[0]，将ht[1]设置为ht[0]，并新创建一个空白ht[1]，为下次rehash做准备

另外，当下列条件满足时，会进行扩展：

  • 服务器目前没有执行BGSAVE或者BGREWRITEAOF，并且哈希表负载因子大于等于1；
  • 服务器目前正在执行BGSAVE或者BGREWRITEAOF，并且哈希表负载因子大于等于5；

这是因为这些命令执行时，子进程会运行中，由于写时复制的操作系统特性，过多或者过快地扩展会带来过多的内存写入操作；

当哈希表负载因子小于0.1时，执行收缩。

渐进式rehash

由于哈希表可能非常大，所以不能一次性rehash成功，而是使用渐进式的方法。

步骤如下：

  1. 为ht[1]分配号空间后，dict结构体同时持有两个哈希表；
  2. 然后dict结构的rehashidx记为0，开始rehash；
  3. 进行期间，会逐个将ht[0]的结点rehash到ht[1]，每次成功都会使rehashidx递增一；
  4. 直到rehash完全，rehashidx设为-1，表示完成；

如果此时有新增的键值对，一律保存到ht[1]中。