发布于 2年前

Redis内部数据结构——词典dictType以及哈希算法的选择

词典dict概览提到了使用Hash Table作为Redis 词典的内部实现,需要考虑三个要点。这章讨论第一个问题:Redis哈希算法的选择。

哈希是把任意长度的输入通过哈希算法转换为固定长度的值。根据不同的使用场景,人们设计出了多种哈希算法,我们常见的有CRC,MD5,HMAC,SHA-256等等,关于多种哈希算法,可以在查看wiki

Redis作为一个高性能的key-value内存服务器,哈希算法需要从计算效率以及减少碰撞的角度选择。

dictType

dict的数据结构:

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

dictType *type;一个指向dictType结构的指针(type)。它通过自定义的方式使得dict的key和value能够存储任何类型的数据。其中包括自定义的哈希函数。

dict.h/dictType的数据结构:

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);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
} dictType;

dictType结构包含几个函数指针,允许dict的调用者自定义涉及key和value的操作。

  • hashFunction:定义对key进行哈希值计算的哈希算法。
  • keyDup和valDup:定义key和value的拷贝函数,用于对key和value进行深拷贝,而不仅仅是传递对象指针。
  • keyCompare:定义key的比较操作,在根据key进行查找时会用到。
  • keyDestructor和valDestructor:定义对key和value的析构函数。
    私有数据指针(privdata)就是在dictType的某些操作被调用时会传回给调用者。

dict.c Redis哈希算法siphash

从dictType数据结构,我们知道Redis的哈希算法是由dictType的函数指针*hashFunction定义。在dict.c中有dictType的实现:

dictType BenchmarkDictType = {
    hashCallback,
    NULL,
    NULL,
    compareCallback,
    freeCallback,
    NULL,
    NULL
};
uint64_t hashCallback(const void *key) {
    return dictGenHashFunction((unsigned char*)key, strlen((char*)key));
}
uint64_t dictGenHashFunction(const void *key, int len) {
    return siphash(key,len,dict_hash_function_seed);
}

在dict.c定义了BenchmarkDictType,最后我们跟到提供哈希算法的是siphash。

如果对Redis历史版本了解,在3.2, 3.0, 2.8, 2.6 使用的MurmurHash2 哈希算法,而4.0以后改为了siphash。以下是Redis作者antirez对选择siphash的一个解释:

Redis uses a reduced rounds version of siphash that is faster than the hashing fucntion we were using, so upgrading was actually a speedup (verified experimentally). AFAIK there are no known attacks on the reduced rounds we use, so for know the current approach sounds good.

大意是:Redis对siphash做了部分删减,经实验验证,改后的siphash要比旧版本的哈希算法(murmurhash2)要快,并且没有发现一些已知的攻击。

这里要提一下哈希洪水攻击(Hash-Flooding Attack),n个key通过hash计算出来的值都相同,那么就会退化成链表,这样查找1个数的时候复杂度就是O(n)。哈希碰撞攻击在知道hash算法的前提下恶意构造n个相同hash值的key,这样hash表的查找效率就被拖慢到了O(n^2)。

查了一些资料,siphash是计算快,计算的哈希值分布均匀良好且不可以预测。可以认为是碰撞极少的一种哈希算法。

©2020 edoou.com   京ICP备16001874号-3