Redis索引模型-Redis是怎么根据key查找到对应value的？
(1) redis整体存储结构
(2) Redis索引模型源码解读
当查询时是怎么根据key查找到对应的value的？
(2.1) redis查找key方法
(2.1.1) 从redisDb的dict查找key
// redis 6.0
// file: /src/db.c
/*
* 低级key查找API
* 实际上并没有直接从应该依赖lookupKeyRead()、lookupKeyWrite()和lookupKeyReadWithFlags()的命令实现中调用。
*
* Low level key lookup API, not actually called directly from commands
* implementations that should instead rely on lookupKeyRead(),
* lookupKeyWrite() and lookupKeyReadWithFlags().
*/
robj *lookupKey(redisDb *db, robj *key, int flags) {
// 从db的dict里去找key对应的桶/链表节点
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) { // 如果节点存在
// 从节点里获取对应的对象
robj *val = dictGetVal(de);
/* Update the access time for the ageing algorithm.
* Don't do it if we have a saving child, as this will trigger
* a copy on write madness. */
if (!hasActiveChildProcess() && !(flags & LOOKUP_NOTOUCH)){
//
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
// 更新lfu
updateLFU(val);
} else {
// 更新lru
val->lru = LRU_CLOCK();
}
}
// 返回查到的值
return val;
} else {
return NULL;
}
}(2.1.2) 从dict查找key
// redis 6.0
// file: /src/dict.c
/*
* 从db的dict里去找key对应的节点
*
* @param *d 字段
* @param *key 键
*/
dictEntry *dictFind(dict *d, const void *key)
{
// 链表节点 可能为空
dictEntry *he;
uint64_t h, idx, table;
// 字典是空的，字典里两个哈希表都是空的
if (dictSize(d) == 0) return NULL;
// 如果正在rehash，执行一小步rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 计算key的hash
h = dictHashKey(d, key);
// 有2个哈希表 ht[0] ht[1]，有可能正在rehash，所以都要查，对应代码是 table=0 table<=1
for (table = 0; table <= 1; table++) {
// 获取数组索引下标
idx = h & d->ht[table].sizemask;
// 桶/链表头结点
he = d->ht[table].table[idx];
// 遍历链表
while(he) {
// key相同 或 key对比相等
if (key==he->key || dictCompareKeys(d, key, he->key))
return he; // 返回对应节点
he = he->next;
}
/* */
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}// redis 6.0
// file: dict.h
/* 从节点里获取对应的对象 */
#define dictGetVal(he) ((he)->v.val)(2.2) 用到的结构体
(2.2.1) Redis服务端结构体-redisServer
// file: /src/server.h
struct redisServer {
/* General */
pid_t pid; /* 主进程pid */
pthread_t main_thread_id; /* 主线程id */
char *configfile; /* 配置文件绝对路径，或 NULL */
char *executable; /* 可执行文件绝对路径。 */
char **exec_argv; /* 可执行 argv 向量（副本）。 */
int dynamic_hz; /* 根据客户端数量更改 hz 值。 */
int config_hz; /* 配置的 HZ 值。如果启用了动态hz，则可能与实际的“hz”字段值不同。 */
mode_t umask; /* 进程启动时的 umask 值 */
int hz; /* serverCron() 调用频率 */
int in_fork_child; /* 复制的子进程 */
redisDb *db; /* 数据库 */
dict *commands; /* 命令表 */
...
};(2.2.2) Redis数据库-redisDb
// file: src/server.h
/* Redis数据库表示。
有多个数据库由从 0（默认数据库）到最大配置数据库的整数标识。
数据库编号是结构中的“id”字段。
*/
typedef struct redisDb {
dict *dict; /* 这个数据库存储的key集合 */
dict *expires; /* 设置了超时时间的key集合 */
dict *blocking_keys; /* 客户端等待数据的key集合 (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. */
} redisDb;redis默认有16个db，每个db里保存了
(2.2.3) 字典-dict
// file: /src/dict.h
/*
* 字典结构体
*/
typedef struct dict {
dictType *type; /* 字典类型 */
void *privdata; /* 私有数据 */
dictht ht[2]; /* 全局哈希表 2个 默认使用第0个，扩容时使用第1个 */
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;(2.2.4) 哈希表-dictht
Redis里的哈希表数据结构的实现是dictht
哈希函数使用 ``
哈希冲突使用 链地址法
// file: /src/dict.h
/*
* 这是哈希表结构。
* 每个字典都有两个这样的字典，因为我们实现了增量重新哈希，从旧表到新表。
*/
typedef struct dictht {
dictEntry **table; // 一维数组的指针
unsigned long size; // 哈希表大小
unsigned long sizemask; // size-1 = (2^n - 1)，比2^n少1，用于计算key对应桶的下标
unsigned long used; // 已使用个数
} dictht;(2.2.5) dictEntry
// file: src/dict.h
/*
* 哈希表节点/Entry实体
*/
typedef struct dictEntry {
void *key; // key的指针
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // value 联合结构体(不同场景使用不同大小，省内存)
struct dictEntry *next; // 链表的下一个节点的指针
} dictEntry; uint64_t 8字节无符号整数
int64_t 8字节带符号整数
double 8字节
dictEntry里保存了key指针、next指针，各8字节
(2.2.6) Redis对象类型-redisObject
/*
* Redis对象类型
*/
typedef struct redisObject {
unsigned type:4; // 数据类型 4个bits
unsigned encoding:4; // 编码方式 4个bits
unsigned lru:LRU_BITS; // LRU时间(相对于全局 lru_clock) 或 LFU数据(低8位保存频率 和 高16位保存访问时间)。 LRU_BITS为24个bits
int refcount; // 引用计数 4字节
void *ptr; // 指针 指向对象的值 8字节
} robj;redisObject保存了
(3) Redis索引模型
Redis怎么根据key定位到value
(3.1) 哈希函数
Redis使用的siphash.c文件里的siphash
(3.2) 哈希冲突解决
1.Redis的hash表是全局的，所以当写入大量的key时，将会带来哈希冲突，已经rehash可能带来的操作阻塞
2.Redis解决hash冲突的方式，是链式哈希：同一个哈希桶中的多个元素用一个链表来保存
3.当哈希冲突链过长时，Redis会对hash表进行rehash操作。rehash就是增加现有的hash桶数量，分散entry元素。
(3.3) 哈希表扩容-渐进式rehash
dict的渐进式rehash是为了避免扩容时的整体拷贝，这会给内存带来较大压力。
渐进式rehash执行时，除了根据键值对的操作来进行数据迁移，Redis本身还会有一个定时任务在执行rehash，如果没有键值对操作时，这个定时任务会周期性地（例如每100ms一次）搬移一些数据到新的哈希表中，这样可以缩短整个rehash的过程。
1.在进行渐进式 rehash 的过程中， 字典会同时使用 ht[0] 和 ht[1] 两个哈希表
2.在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行：
比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。
3.在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作： 这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。
参考资料
[1] redis源码-github