redis7.0源码阅读：redis的基本存储结构

redis的基本存储结构

内存数据库：redisDb
键值对：dict
键值对的数据类型：dictType
键值对实体：dictEntry

数据库redisDb

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 */
    unsigned long expires_cursor; /* Cursor of the active expire cycle. */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
    clusterSlotToKeyMapping *slots_to_keys; /* Array of slots to keys. Only used in cluster mode (db 0). */
} redisDb;

1
2
3
4
5
6
7
8
9
10
11
12
13

• dict *dict 用来组织所有数据的键值对(dict)
• dict *expires 过期的dict
• dict *blocking_keys 阻塞的dict (比如BRPOP等命令，会阻塞，只有当要取的数组结构不为空，才会解除阻塞)
• dict *ready_keys解除阻塞的dict
• dict *watched_keys 监控(watch)的dict （事务前可以加watch）

哈希表dict

struct dict {
    dictType *type;
    
    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2];//* exponent of size. (size = 1<
};
1
2
3
4
5
6
7
8
9
10
11
12

• dictType *type 键值对的类型，可以进行自定义（hash，key，val操作），使得dict能够存储任意类型的数据
• dictEntry **ht_table[2] 首先，先看dictEntry,这是一个dict实体，也就是说存放的是键值对，那么dictEntry **ht_table就可以理解为一张哈希表(数组，有1个号)，哈希表中的元素是一个指针（第2个号），dictEntry **ht_table这个哈希表是通过,数组+哈希函数(指针)的方式组织起来的。 那么dictEntry **ht_table[2] 就很好理解了，也就是两张哈希表(为了做rehash)。
• ht_used[2]:两张哈希表中，分别使用了多少（比如数组长度16,只使用了10）
• rehashidx：记录 rehash 进度的标志（每移动一个桶,rehashidx++），值为 -1 表示 rehash 未进行。
• pauserehash rehash是否暂停
• ht_size_exp[2]:以ht_size_exp[0]为例，这是哈希表的长度，长度是2的倍数，因为这样可以将n%size优化成n&(size-1)从而加快运算速度

哈希数据类型dictType

dictType中是一个存放函数的结构体，定义了一些函数指针。
可以通过设置自定义函数，使得dict的key和value能够存储任何类型的数据

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);//哈希函数
    void *(*keyDup)(dict *d, const void *key);//复制key
    void *(*valDup)(dict *d, const void *obj);//复制val
    int (*keyCompare)(dict *d, const void *key1, const void *key2);//比较key
    void (*keyDestructor)(dict *d, void *key);//删除key
    void (*valDestructor)(dict *d, void *obj);//删除val
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    /* Allow a dictEntry to carry extra caller-defined metadata.  The
     * extra memory is initialized to 0 when a dictEntry is allocated. */
    size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;
1
2
3
4
5
6
7
8
9
10
11
12

哈希实体（键值对）dictEntry

存放键值对

哈希冲突：当哈希表中数据增加，新增的数据 key 哈希计算出的哈希值和老数据 key 的哈希值会在同一个哈希桶中，也就是说多个 key 对应同一个哈希桶

next中存储的是哈希值相同的key/val对（出现哈希冲突），使用拉链法，通过链表串起来。
链式哈希会产生一个问题，随着哈希表数据越来越多，哈希冲突越来越多，单个哈希桶链表上数据越来越多。

typedef struct dictEntry {
    void *key;//键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;//值
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
} dictEntry;
1
2
3
4
5
6
7
8
9
10
11
12
13