背景

Redis是一个键值对KV型数据库，数据都是保存在内存中的，可以支持海量数据的存储和读取

通过键key，可以O(1)时间复杂度获取到对应的值value

那么Redis是如何做到O(1)时间复杂度的查询？又是如何存储海量数据的？本文将从底层分析Redis是如何实现的

海量数据的存储

1. 键值对key - value
2. O(1)时间复杂度获取数据

从1和2，我们可以大概想到哈希表，Redis确实也是这么做的

底层数据结构

哈希表dictht

Redis是使用C语言编写的，C语言不像其他的高级语言自带了哈希表，所以Redis作者自己实现了哈希表

源码路径：src/dict.h

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
 // 哈希表
typedef struct dictht {
    // 节点数组
    dictEntry **table;
    // 数组大小，空间换时间
    unsigned long size;
    // 数组大小size - 1，用于计算节点下标索引，空间换时间
    unsigned long sizemask;
    // 节点数量，计算负载因子
    unsigned long used;
} dictht;

// 节点
typedef struct dictEntry {
    // key
    void *key;
    // value
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下一个节点的指针，形成链表
    struct dictEntry *next;
} dictEntry;

Redis的哈希表dictht，实现原理和java中的HashMap是类似的，核心都是：数组 + 链表

另外，还需要解决以下两个问题：

1. 如何确定key，放到数组的哪个下标下面
2. 不同的key，也可能放到相同的数组下标，如何解决

计算key的数组下标

主要是两个步骤：

1. 计算key的hashcode：依据哈希函数，计算key的哈希值hashcode
2. 计算数组下标：hashcode & sizemask(数组大小 - 1)，位运算更高效

额外扩展：为什么hashcode % size的结果和hashcode & sizemask是一样的

hashcode % size，取模操作，结果肯定在 [0，size - 1] 范围内

重点看下hashcode & sizemask

假设size = 4，此时sizemask = size - 1 = 3，3对应的二进制为11，一个数和11进行&运算，最小结果为00，最大结果为11，也是 [0， 3] 范围，也就是 [0，size - 1] 范围内

解决下标冲突

多个不同的key，也可能计算出相同的数组下标，比如：

1. 不同的key，计算出的hashcode相同。也就是哈希冲突
2. 不同的key，计算出的hashcode不同，但 hashcode & sizemask 的结果相同

Redis使用链表来解决这类问题，数组下标内如果有多个不同的key的话，形成单向链表

字典dict

使用哈希表存储数据，可以O(1)时间复杂度获取数据。但还存在以下问题：

1. 节点数量很多，数组大小很小时，哈希冲突严重，需要遍历链表判断key是否相同，获取数据的性能下降
2. 节点数量很少，数组大小很大时，空间浪费严重

所以，我们还需要一个自动扩容/缩容并迁移节点的机制，一般称之为rehash

Redis的字典dict，其实就是对哈希表dictht + rehash的封装

源码路径：src/dict.h

typedef struct dict {
    dictType *type;
    void *privdata;
    // 两个哈希表
    dictht ht[2];
    // rehash索引，当rehash不在进行时，值为-1
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

Redis的字典dict，持有两个哈希表ht[0]和ht[1]，rehash操作就是把ht[0]数据迁移到ht[1]中

渐进式rehash

Redis中所有的key都是存在哈希表中的，哈希表可能存储百万、千万的量级。如果一次性、集中式的进行数据迁移，则可能会非常耗时，导致Redis服务响应变慢

渐进式rehash，就是分多次、渐进式的完成rehash

核心设计思想：分治

针对海量数据的处理，很难一次完成，可以拆分成多次完成，平摊处理耗时

渐进式rehash的步骤：

1. 为ht[1]分配空间，字典同时持有ht[0]和ht[1]两个哈希表
2. 将rehash索引rehashidx从-1改为0，表示rehash进行中

1. rehash进行中时，所有对字典的增删改查，除了执行原有的操作，还会做额外的操作

   a. 把rehashidx下标上的所有节点，从ht[0]迁移到ht[1]

   b. rehashidx + 1

1. 随着对字典操作的不断执行，最终在某个时间点，ht[0]所有的键值对都迁移到了ht[1]上，此时把ht[1]赋值给ht[0]，然后把ht[1]释放内存空间，rehashidx设置为-1，代表rehash完成

渐进式rehash过程中，字典的增删改查操作如何使用哈希表

• 删除/修改/查询：先操作哈希表ht[0]，没有再操作哈希表ht[1]

• 新增：只在哈希表ht[1]上操作，保证哈希表ht[0]节点只减不增

负载因子：节点个数ht[0].used / 数组大小ht[0].size，用来判断是否需要触发渐进式rehash

• 负载因子 >= 1，Redis没有在执行bgsave或bgrewriteaof命令时，进行渐进式rehash扩容
• 负载因子 >= 5，直接进行渐进式rehash扩容，即使Redis正在执行bgsave或bgrewriteaof命令
• 负载因子 = 0.1，进行渐进式rehash缩容

数据库

Redis可以有多个数据库，默认是16个

每个数据库中包含一个dict字段，用来存储数据库中所有的键值对

源码路径：src/server.h

struct redisServer {
    // 一个数组，保存着服务器中所有的数据库
    redisDb *db;
    // 数据库数量，默认是16个
    int dbnum;                      /* Total number of configured DBs */
    ...
};

/* Redis database representation. There are multiple databases identified
 * by integers from 0 (the default database) up to the max configured
 * database. The database number is the 'id' field in the structure. */
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;

总结

• 哈希表使用数组 + 链表实现，使用链表解决哈希冲突
• 哈希表负载因子 = 节点个数used / 数组大小size，太大节点冲突严重，太小浪费空间，使用rehash来解决
• Redis字典其实就是对哈希表dictht + rehash的封装，持有两个哈希表ht[0]和ht[1]，rehash操作就是把ht[0]数据迁移到ht[1]中
• 渐进式rehash，就是分多次、渐进式的完成rehash
• Redis可以有多个数据库，默认是16个
• 每个数据库中包含一个字典dict字段，用来存储数据库中所有的键值对