当前位置：首页 > news >正文

Redis面试精讲 Day 10：Redis数据结构底层实现原理

news 2025/8/4 10:25:12

【Redis面试精讲 Day 10】Redis数据结构底层实现原理

文章标签

Redis,数据结构,底层原理,面试技巧,源码分析,内存优化

文章简述

本文是"Redis面试精讲"系列第10天，深入解析Redis核心数据结构的底层实现机制。文章详细讲解SDS、字典、跳跃表等关键数据结构的设计原理，分析不同数据类型在不同场景下的编码转换策略。提供Redis源码级分析及内存优化实践，包含5个高频面试题深度解析和微博热搜榜案例实现。通过对比不同版本的实现差异，帮助读者透彻理解Redis高效存储背后的秘密，掌握面试中数据结构相关问题的回答技巧。

开篇引言

Redis的卓越性能很大程度上源于其精心设计的数据结构。今天我们将深入Redis内核，探索String、Hash、List等数据类型背后的实现原理，这是考察Redis底层机制的核心面试内容。

一、概念解析：Redis对象系统

1.1 Redis对象结构

所有Redis键值都存储为redisObject结构：

字段	类型	描述
type	4bits	数据类型（String/Hash/List等）
encoding	4bits	编码方式（raw/int/ht等）
lru	24bits	最近访问时间/LFU计数
refcount	32bits	引用计数
ptr	void*	指向实际数据的指针

// redisObject源码定义（redis.h）
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:LRU_BITS;
int refcount;
void *ptr;
} robj;

1.2 数据类型与编码映射

数据类型	可能编码	适用条件
String	int/embstr/raw	数值/短字符串/长字符串
List	ziplist/quicklist	元素少/元素多
Hash	ziplist/hashtable	字段少/字段多
Set	intset/hashtable	纯数字/混合类型
ZSet	ziplist/skiplist	元素少/元素多

二、原理剖析：核心数据结构

2.1 SDS（简单动态字符串）

struct sdshdr {
int len;    // 已用长度
int free;   // 剩余空间
char buf[]; // 字节数组
};

特性优势：

O(1)时间复杂度获取长度
杜绝缓冲区溢出
减少内存重分配次数
二进制安全

2.2 字典（hashtable）

Redis使用渐进式rehash的双哈希表实现：

typedef struct dict {
dictType *type;
dictht ht[2];    // 两个哈希表
long rehashidx;  // rehash进度
} dict;

rehash过程：

准备ht[1]空间
维持索引计数器rehashidx
每次操作迁移一个桶
完成时切换主表

2.3 跳跃表（skiplist）

ZSet的底层实现之一，平均O(logN)复杂度：

typedef struct zskiplistNode {
sds ele;
double score;
struct zskiplistNode *backward;
struct zskiplistLevel {
struct zskiplistNode *forward;
unsigned int span;
} level[];
} zskiplistNode;

三、代码实现：编码转换实战

3.1 观察编码转换

# 字符串编码演示
127.0.0.1:6379> SET num 123
OK
127.0.0.1:6379> OBJECT ENCODING num
"int"127.0.0.1:6379> SET short "hello"
OK
127.0.0.1:6379> OBJECT ENCODING short
"embstr"127.0.0.1:6379> SET long "a very long string..."
OK
127.0.0.1:6379> OBJECT ENCODING long
"raw"# Hash编码转换
127.0.0.1:6379> HMSET small f1 v1 f2 v2
OK
127.0.0.1:6379> OBJECT ENCODING small
"ziplist"127.0.0.1:6379> HMSET big f1 v1 ... f65 v65
OK
127.0.0.1:6379> OBJECT ENCODING big
"hashtable"

3.2 配置编码阈值

# redis.conf配置示例
hash-max-ziplist-entries 512  # Hash字段数阈值
hash-max-ziplist-value 64     # 字段值长度阈值
list-max-ziplist-size -2      # Quicklist节点大小
set-max-intset-entries 512    # intset元素数阈值

四、面试题解析

4.1 Redis为什么自研SDS而不直接用C字符串？

面试官意图：考察对Redis设计哲学的理解

参考答案：

安全性：

避免缓冲区溢出
二进制安全（含\0的数据）

性能：

O(1)获取长度
空间预分配（减少alloc）

兼容性：

兼容部分C字符串函数
自动追加\0

4.2 渐进式rehash如何保证操作不被阻塞？

考察点：高可用设计思想

结构化回答：

双表机制：

同时维护ht[0]和ht[1]
查询操作访问双表

分步迁移：

每次操作迁移1个桶
定时任务辅助迁移

最终一致性：

迁移完成前新旧数据共存
保证服务不中断

4.3 ZSet为什么同时使用跳跃表和字典？

解决方案：

跳跃表：

范围操作高效（ZRANGE）
有序性维护

字典：

O(1)单点查询（ZSCORE）
成员唯一性保证

数据共享：

元素对象被两者引用
通过refcount管理

五、实践案例：微博热搜榜

5.1 基于ZSet的实现

// 添加热搜事件
public void addHotSearch(String event, double score) {
jedis.zadd("hotsearch", score, event);
}// 获取TOP10热搜
public List<String> getTop10() {
return jedis.zrevrange("hotsearch", 0, 9);
}// 模拟热度计算
public void calculateHot() {
Set<Tuple> events = jedis.zrangeWithScores("hotsearch", 0, -1);
for (Tuple event : events) {
double newScore = event.getScore() * 0.9 + random.nextDouble();
jedis.zadd("hotsearch", newScore, event.getElement());
}
}