Redis 字典

Redis 字典 dict 用途有两个，首先实现数据库键空间（Key space），Redis 是一个保存键值对的数据库，数据库的键值对由字典保存，每个数据库都有一个对应的字典， 这个字典被称之为键空间（key space）。

其次字典 dict 还作为 Hash 类型键的底层实现之一，当 Hash 类型的键使用 hashtable 编码时，也使用 dict 进行存储。

Redis 采用链地址法解决 key hash 冲突问题，以头插的方式插入到冲突节点的前面。

底层源码

单机 Redis 默认有 16 个 redisDb ，通过 select(n) 选择使用哪个 redisDb cluster 模式下只有一个 redisDb，每个 redisDb 里面都有一个字典 dict，用于保存 set 进来的键值对。

typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    dict *expires;              /* Timeout of keys with a timeout set */
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/
    dict *ready_keys;           /* Blocked keys that received a PUSH */
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    int id;                     /* Database ID */
    long long avg_ttl;          /* Average TTL, just for stats */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

字典 dict 里面包含两个 dictht，ht[0]，ht[1]，ht[1] 用于渐进式 rehash；

typedef struct dict {
    dictType *type; // 字典类型
    void *privdata; // 私有数据
    dictht ht[2];  // 哈希表[两个]
    long rehashidx; // 记录rehash 进度的标志，值为-1表示rehash未进行
    unsigned long iterators; //  当前正在迭代的迭代器数
} dict;

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;

哈希表 dictht 里面包含一个 table，里面的节点就是哈希表节点 dicEntry，dictEntry 里面保存着元素的地址 *val，和指向下一个 dictEntry 的指针，这个指针将哈希值相同的键值对连接在一起。

typedef struct dictht {
    dictEntry **table; // 哈希表数组
    unsigned long size; // 哈希表的大小
    unsigned long sizemask; // 哈希表大小掩码
    unsigned long used; // 哈希表现有节点的数量
} dictht;

typedef struct dictEntry {
    void *key;  // 键定义
    // 值定义
    union {
        void *val; // 自定义类型
        uint64_t u64;  // 无符号整形
        int64_t s64; // 有符号整形
        double d; // 浮点型
    } v;
    struct dictEntry *next; //指向下一个哈希表节点
} dictEntry;

所以 Redis Key 的分布，可以用下图表示：

rehash 过程

当哈希表 dict 需要扩展或者收缩时，Redis 会进行 rehash 操作，即将 h[0] 里面的元素移到 h[1]

rehash 的过程不是一次性的，而是将 rehash 所需的计算工作分摊到每次对字典进行增删改查的操作上。

字典维护 rehashidx 字段，从 0 开始，每次将 rehashidx 上面的键值对 rehash 到 ht[1]，然后 rehashidx++，最终 ht[0] 所有键值对移到 ht[1]，那么 rehashidx = -1，表示 rehash 完成。

渐进式 rehash 过程中，Redis 会同时使用 ht[0] 和 ht[1] 两张表，delete，find，update 操作会在两个哈希表上运行。rehash 过程中，新增的键值对保存到 ht[1]，保证 rehash 执行完成时，ht[0] 为空表，然后将 ht[1] = ht[0]。

Rehash 时机

负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

当服务器没有执行 BGSAVE or BGREWRITEAOF 命令时，若负载因子 >=1，哈希表将会执行扩展操作；

当服务器 执行 BGSAVE or BGREWRITEAOF 命令时，若负载因子 >= 5，哈希表将会执行扩展操作。