【Redis】键值对数据库实现

1、背景

redis是一个（key-value）键值对数据库，其中value可以是五大基本数据类型：string、list、hash、set、zset，这五大基本数据类型对应着不同的底层结构，接下来就来讲解一下redis如何存储这些数据类型的。

2、五种基本数据类型对应底层实现

redis数据结构	旧版本（≤3.0）底层实现	新版本（≥3.2+）底层实现	说明
string	简单动态字符串（SDS）	简单动态字符串（SDS）	SDS是二进制安全的动态字符串，支持高效追加和预分配
list	双向链表（LinkedList）或压缩列表（Ziplist）	快速列表（Quicklist）	新版本统一用Quicklist（双向链表 + Ziplist的混合结构），平衡内存和访问效率
hash	压缩列表（Ziplist）或哈希表（Hashtable）	Ziplist或Hashtable，优化阈值	新版本调整了Ziplist转hashtable的阈值（如hash-max-ziplist-entries等配置）
set	整数集合（Intset）或哈希表（Hashtable）	Intset或Hashable，优化阈值	新版本优化了Intset的升级策略（如元素类型超出int16时自动转Hashtable）
zset	压缩列表（Ziplist）或跳跃表（SkipList）+ 哈希表	Ziplist或SkipList + Hashtable	新版本调整了Ziplist转SkipList的阈值（如zset-max-ziplist-entries）

关键变化说明如下：
1、List的优化

旧版本：大列表用LinkedList（内存碎片多），小列表用Ziplist（节省内存但修改效率低）。
新版本：统一用Quicklist（双向链表节点内嵌Ziplist），兼顾内存和操作效率。

2、Hash/Set/ZSet的阈值调整

新版本通过配置参数优化了Ziplist和Intset的转换条件，减少内存浪费。

3、String保持不变

始终使用SDS，但新版本可能优化了内存分配策略（如惰性释放）。

3、redis数据结构

redis数据结构如下（6.2.18版本），所有键值对都存储在其中:

typedef struct redisDb {dict *dict; //存储当前数据库的所有键值对dict *expires; //存储所有设置了过期时间的键及过期时间戳dict *blocking_keys; //记录因阻塞操作（如BLPOP）被阻塞的客户端及其监听的键dict *ready_keys; //暂存已收到数据且准备解除阻塞的键（如LPUSH触发的BLPOP唤醒）dict *watched_keys; //实现事务的WATCH机制（乐观锁），记录被监视的键及关联的客户端int id; //当前数据库的编号（如0-15，默认16个库）long long avg_ttl; //统计当前数据库键的平均TTL（毫秒），用于INFO命令展示unsigned long expires_cursor; //记录渐进式过期检查的游标（避免长时间阻塞）list *defrag_later; //存储待内存碎片整理的键名列表（逐步整理，避免阻塞主线程）
} redisDb;

核心存储结构为dict *dict，dict结构体组成为：

typedef struct dict {dictType *type; //定义字典操作的函数指针（如哈函数、键比较函数）void *privdata; //存储字典的私有数据，传递给type中的函数dictht ht[2]; //存储实际数据的哈希表，ht[0]是主哈希，ht[1]仅在rehash时使用long rehashidx; //标记rehash的进度（-1表示为进行rehash，≥0表示当前rehash的桶索引）int16_t pauserehash; //控制rehash的暂停状态（>0暂停，=0正常，<0表示错误）
} dict;

核心存储结构为两个哈希表dictht ht[2]，哈希表dictht的结构为：

typedef struct dictht {dictEntry **table; //存储实际键值对数据的哈希桶数组，每个元素是链表头指针（解决哈希冲突）unsigned long size; //哈希表的大小（桶的总数量）unsigned long sizemask; //哈希掩码，用于计算键的索引unsigned long used; //当前哈希表中已使用的节点数量（所有链表的节点总数）
} dictht;

核心存储结构dictEntry **table里存放了哈希表数组，dictEntry 结构如下：

typedef struct dictEntry {void *key; //存储键的指针（实际指向redis的字符串对象）union {void *val; //指向redis对象的指针（如string、list、hash等复杂类型）uint64_t u64; //直接存储整数值（避免额外内存分配）int64_t s64; //直接存储有符号整数值（如时间戳）double d; //直接存储浮点数值} v;struct dictEntry *next; //指向下一个dictEntry节点（形成链表，解决哈希冲突）
} dictEntry;

void *key和void *val分别指向了实际的键对象和值对象robj，robj结构如下：

typedef struct redisObject {unsigned type:4; //标识redis对象的类型（如string、list、hash等）unsigned encoding:4; //表示底层实现的编码方式unsigned lru:LRU_BITS; //记录对象的访问时间或频率（用于内存淘汰策略）int refcount; //引用计数（实现内存回收垃圾回收机制）void *ptr; //指向实际存储数据的底层结构（如SDS、ziplist、dict等）
} robj;

void *ptr存储真正的数据，unsigned type:4为reids数据类型，其定义如下：

#define OBJ_STRING 0    /* String object. */
#define OBJ_LIST 1      /* List object. */
#define OBJ_SET 2       /* Set object. */
#define OBJ_ZSET 3      /* Sorted set object. */
#define OBJ_HASH 4      /* Hash object. */