Redis怎么保存所有键值对的？——Redis系列(二)

一、Redis全局键值结构说明

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。

注意这个全局哈希表是存储所有的键值对的，所以，我也把它称为全局哈希表。

理论上哈希表能以 O(1) 的复杂度快速查询数据。Hash 表通过 Hash 函数的计算，就能定位数据在表中的位置，紧接着可以对数据进行操作，这就使得数据操作非常快速。

参考：吃透Redis（一）：数据结构篇-全局Hash表

全局hash表

二、 怎么解决hash冲突

当你往哈希表中写入更多数据时，哈希冲突是不可避免的问题。这里的哈希冲突，也就是指，两个 key 的哈希值和哈希桶计算对应关系时，正好落在了同一个哈希桶中。

毕竟，哈希桶的个数通常要少于 key 的数量，这也就是说，难免会有一些 key 的哈希值对应到了同一个哈希桶中。

2.1 方法一、链式哈希

Redis 解决哈希冲突的方式，就是链式哈希。链式哈希也很容易理解，就是指同一个哈希桶中的多个元素用一个链表来保存，它们之间依次用指针连接。

链式哈希的链不能太长，否则会降低 Hash 表性能

链式Hash

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

*key 指向键的指针

*val 指向值的指针 当值为整数或双精度浮点数时，由于其本身就是 64 位，就可以不用指针指向了，而是可以直接存在键值对的结构体中，这样就避免了再用一个指针，从而节省了内存空间。

如果不是整数或双精度浮点数时，*val 指针会指向 RedisObject

*dictEntry 结构体中包含了指向另一个 dictEntry 结构的指针 next，这就是用来实现链式哈希的。

RedisObject

Redis 的 key 是 String 类型，但 value 可以是很多类型（String/List/Hash/Set/ZSet等），所以 Redis 要想存储多种数据类型，就要设计一个通用的对象进行封装，这个对象就是 redisObject。结构体定义如下：

typedef struct redisObject {
    unsigned type:4; //redisObject的数据类型，4个bits
    unsigned encoding:4; //redisObject的编码类型，4个bits
    unsigned lru:LRU_BITS;  //redisObject的LRU时间，LRU_BITS为24个bits
    int refcount; //redisObject的引用计数，4个字节
    void *ptr; //指向值的指针，8个字节
} robj;

type：redisObject 的数据类型，面向用户的数据类型（String/List/Hash/Set/ZSet等）。占用 4 bit

encoding：redisObject 的编码类型，是 Redis 内部实现各种数据类型所用的数据结构，每一种数据类型，可以对应不同的底层数据结构来实现（SDS/ziplist/intset/hashtable/skiplist等）。占用4bit

lru：redisObject 的 LRU 时间。占用24bit

refcount：redisObject 的引用计数。占用4个字节

ptr：指向值的指针。占用8个字节

2.2 方法二、rehash

rehash过程

当链式哈希的链长达到一定长度时，我们可以使用 rehash

过程如下：

1、Redis 准备了两个哈希表，用于 rehash 时交替保存数据。

2、在正常服务请求阶段，所有的键值对写入哈希表1。

3、当进行 rehash 时，键值对被迁移到哈希表2中。

4、当迁移完成后，哈希表1的空间会被释放，并把 哈希表2的地址赋值给 哈希表1，哈希表2的表大小设置为 0。这样一来，又回到了正常服务请求的阶段，哈希表1接收和服务请求，哈希表2作为下一次 rehash 时的迁移表。

渐进式rehash

执行 rehash 本身开销比较大，所以就需要采用渐进式 rehash 设计。

简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries

这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问