知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 数据结构与底层实现 ## Redis 是 CP 还是 AP ``` Redis 是 AP 系统(高可用 + 分区容错,牺牲强一致性)。 虽然单机 Redis 只有一个实例,一致性有保障,但一旦节点挂了就没有可用性。 Redis 的设计目标是高性能、高可扩展性和高可用性,一致性模型是最终一致性。 为什么不能保证强一致性? Redis 分布式设计采用异步复制 主节点写入后,异步将修改发送给从节点同步 由于网络延迟,从节点不一定能立即收到和执行 → 节点之间可能存在数据不一致 此外,节点故障时数据可能无法同步到其他节点 虽然有复制和哨兵机制提高可用性和容错性 但这些机制不能完全解决数据一致性问题 ``` ## Redis 和 Memcached 的区别  *图:Redis 与 Memcached 在七个维度上的对比* ``` 维度 Redis Memcached ────────────────────────────────────────────────────────────────── 数据结构 String/Hash/List/Set/ZSet 等 只支持简单键值对 持久化 支持 RDB 和 AOF 不支持持久化 数据分片 哈希槽分片,自动分片和负载均衡 只能手动分片 线程模型 单线程执行命令(6.0 网络 I/O 多线程) 多线程处理请求 高级功能 事务、Lua 脚本、发布订阅等 只支持基本 GET/SET 协议 自研 RESP 协议,支持多数据库 文本协议,只有一个数据库 内存管理 更复杂,支持更多优化策略 相对简单 ``` > 💬 **Q:Redis 什么情况下会做请求的路由转发?举出例子** > > 发生在 **Redis Cluster(集群模式)** 中,当客户端请求的 key 不在当前节点负责的 hash slot 上时,节点会返回重定向指令。 > > **核心机制:** Redis Cluster 将键空间划分为 16384 个 hash slot,每个节点负责一部分。客户端请求到错误节点时,节点返回 MOVED 或 ASK 重定向(注意:不是转发,是让客户端自己去找正确节点)。 ### Redis Cluster 拓扑与哈希槽分布  *图:Redis Cluster 三主三从拓扑与哈希槽路由规则* ``` 集群拓扑(3 主 3 从 示例): ┌──────────────────────┐ │ Redis Cluster │ └──────────────────────┘ │ ┌───────────────┼───────────────┐ │ │ │ ┌─────▼─────┐ ┌─────▼─────┐ ┌─────▼─────┐ │ Master A │ │ Master B │ │ Master C │ │ :6379 │ │ :6380 │ │ :6381 │ └─────┬─────┘ └─────┬─────┘ └─────┬─────┘ │ │ │ ┌─────┐ │ ┌─────┐ │ ┌─────┐ │ │从 A1│───┘ │从 B1│─────┘ │从 C1│─────┘ └─────┘ └─────┘ └─────┘ 哈希槽分配(16384 个 slot): ┌──────────────────────────────────────────────────────────────┐ │ slot 0 ── 5460 │ slot 5461 ── 10922 │ slot 10923 ── 16383 │ │ Master A │ Master B │ Master C │ └──────────────────────────────────────────────────────────────┘ 路由规则: hash_slot = CRC16(key) % 16384 示例: CRC16("product:88") % 16384 = 11200 → 属于 Master B CRC16("user:1001") % 16384 = 3444 → 属于 Master A CRC16("order:500") % 16384 = 12539 → 属于 Master C 客户端如何知道每个 slot 在哪个节点? 1. 启动时连接任意节点,执行 CLUSTER SLOTS 获取完整映射表 2. 本地缓存 slot → 节点 的映射 3. 收到 MOVED 重定向时更新本地缓存 4. 定期从节点拉取最新拓扑(处理节点变更) ``` > **1. MOVED 重定向(slot 已稳定归属另一个节点):** > ``` > 假设 3 节点集群:A(slot 0-5460)、B(slot 5461-10922)、C(slot 10923-16383) > > 客户端 → 节点A: GET product:88 > CRC16("product:88") % 16384 = 11200,属于节点B > 节点A → 客户端: MOVED 11200 192.168.1.2:6379 > 客户端 → 节点B: GET product:88 > 节点B → 客户端: "手机" > > 客户端收到 MOVED 后更新本地 slot 映射表,后续同 slot 请求直接发到 B。 > ``` > > **2. ASK 重定向(slot 正在迁移中,临时转移):** > ``` > 集群正在将 slot 12539 从节点A迁移到节点C: > > 客户端 → 节点A: GET order:500 > 节点A → 客户端: ASK 12539 192.168.1.3:6379 > 客户端 → 节点C: ASKING (必须先发 ASKING 命令) > 客户端 → 节点C: GET order:500 > 节点C → 客户端: "订单数据" > > ASK 是一次性的,客户端不更新映射表(迁移还没完成)。 > ``` > > **关键区别:** > | | MOVED | ASK | > |---|---|---| > | 含义 | slot 永久属于另一个节点 | slot 正在迁移,这次去目标节点试试 | > | 客户端行为 | 更新本地映射表 | 不更新,仅本次重定向 | > | 触发场景 | 正常请求到错误节点 | resharding 期间 | ## Redis 为什么这么快 ``` 1. 纯内存操作:数据全在内存,读写速度是磁盘的 10 万倍 2. 单线程模型:命令执行是单线程,避免了锁竞争和上下文切换 (Redis 6.0 引入多线程处理网络 I/O,但命令执行仍是单线程) 3. I/O 多路复用:用 epoll 同时监听大量连接,不阻塞 4. 高效的数据结构:针对不同场景选择最优的底层编码 ``` ### Redis 事件处理架构图(I/O 多路复用 + 单线程)  *图:客户端连接经 epoll 分派到读写处理器后单线程执行* ``` ┌─────────────────────────────────────────┐ │ Redis 服务端 │ │ │ ┌──────┐ │ ┌──────────────────────────────────┐ │ │客户端A│──socket───→│──│ │ │ └──────┘ │ │ epoll_wait(阻塞等待) │ │ ┌──────┐ │ │ 同时监听所有 socket 上的事件 │ │ │客户端B│──socket───→│──│ │ │ └──────┘ │ └──────────────┬───────────────────┘ │ ┌──────┐ │ │ 有事件就绪 │ │客户端C│──socket───→│──│ ↓ │ └──────┘ │ │ ┌──────────────────────────────────┐ │ │ │ │ 文件事件分派器 │ │ ...更多连接... │ │ │ (根据事件类型分派到对应 handler) │ │ │ │ └──────┬──────────┬──────────────┘ │ │ │ │ │ │ │ │ ┌────↓──┐ ┌───↓───┐ │ │ │ │读处理器│ │写处理器│ │ │ │ │(解析 │ │(将响应 │ │ │ │ │ 命令) │ │ 写回) │ │ │ │ └───┬───┘ └───┬───┘ │ │ │ │ │ │ │ │ ┌───↓──────────↓───┐ │ │ │ │ 单线程执行命令 │ │ │ │ │ (操作内存数据) │ │ │ │ └──────────────────┘ │ │ └──────────────────────────────────┘ │ │ │ │ ===== Redis 6.0+ 多线程 I/O ===== │ │ 读 socket 和写 socket 可以并行, │ │ 但命令执行始终是单线程 │ └─────────────────────────────────────────┘ 关键点: epoll 让单个线程同时监听数千连接 → 不是"一个连接一个线程" 事件驱动:只有活跃的连接才消耗 CPU,空闲连接不占资源 单线程执行命令 → 无需加锁,上下文切换开销为 0 ``` ### Redis 6.0 多线程 I/O 模型  *图:I/O 多线程读写 socket,命令执行仍单线程* ``` 多线程是读/写 socket 的字节流,命令执行永远是单线程。 ┌────────── 多线程并行 ──────────┐ ┌──────┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │客户端A│←socket→│读 │ │写 │ │ │ │ │ └──────┘ │线 │ │线 │ │ │ │ │ ┌──────┐ │程 │ │程 │ │ 主 │ │ 时 │ │客户端B│←socket→│1 │ │1 │ │ 线 │ │ 间 │ └──────┘ │ │ │ │ │ 程 │ │ 轴 │ ┌──────┐ │读 │ │写 │ │(单 │ │ ↓ │ │客户端C│←socket→│线 │ │线 │ │线) │ │ │ └──────┘ │程 │ │程 │ │ │ │ │ │2 │ │2 │ │ │ │ │ └───┘ └───┘ └────┴─────┴────┘ ↑ ↑ ↑ ↑ 读请求 写响应 解析命令 时间片轮转 (并行) (并行) 操作数据 (串行处理 所有命令) 执行流程(一次事件循环): 1. 主线程 epoll_wait,获取所有就绪事件 2. 主线程将读事件分发给 I/O 线程池(并行读取字节流) 3. 主线程串行解析所有读到的命令 → 执行 → 写内存 4. 主线程将响应交给 I/O 线程池(并行写回 socket) 5. 回到步骤 1 I/O 线程数和 CPU 核数相关(默认 1 个额外线程,配置 io-threads 4 等) ``` > 💬 **Q:举例说明什么操作是多线程的?** > > 多线程处理的是**网络 I/O 的读写操作**,即从 socket 读数据和往 socket 写数据。 > > ``` > 假设同时有 3 个客户端发来请求: > 客户端 A:SET name 张三 > 客户端 B:GET age > 客户端 C:INCR counter > > 多线程阶段(并行读取): > I/O 线程 1:从客户端 A 的 socket 读取字节流 "*3\r\n$3\r\nSET..." > I/O 线程 2:从客户端 B 的 socket 读取字节流 "*2\r\n$3\r\nGET..." > I/O 线程 3:从客户端 C 的 socket 读取字节流 "*2\r\n$4\r\nINCR..." > > 单线程阶段(串行执行命令): > 主线程:解析 SET name 张三 → 执行 → 写内存 > 主线程:解析 GET age → 执行 → 读内存 > 主线程:解析 INCR counter → 执行 → 修改内存 > > 多线程阶段(并行写回): > I/O 线程 1:把 "+OK\r\n" 写回客户端 A 的 socket > I/O 线程 2:把 "$2\r\n25\r\n" 写回客户端 B 的 socket > I/O 线程 3:把 ":1\r\n" 写回客户端 C 的 socket > ``` > > 简单记:**读字节、写字节是多线程的;解析命令、操作数据是单线程的**。 ``` ## Redis 为什么设计为单线程 ``` 这里说的单线程,指的是"网络 IO 和键值对读写由一个线程完成"。 其他模块如持久化存储、集群支撑等是多线程的。 多线程的目的是通过并发提升 I/O 和 CPU 利用率。 但 Redis 不需要提升 CPU 利用率: 操作基本都是基于内存的,CPU 不是性能瓶颈 Redis 确实是 I/O 密集型框架: 数据操作过程中有大量网络 I/O 和磁盘 I/O 要提升性能,关键是提升 I/O 利用率 → 通过 epoll I/O 多路复用解决,而不是多线程 单线程的好处: 避免锁竞争和上下文切换开销 数据结构操作不需要加锁,实现简单 命令执行顺序可预测,不会有并发问题 ``` ## RedisObject 对象系统 ``` RedisObject 是 Redis 对象系统的核心,所有数据类型的键和值都被封装为 RedisObject。 struct redisObject { type // 标识对象的类型(如 REDIS_STRING) 4 bit encoding // 对象的编码格式(如 REDIS_ENCODING_INT) 4 bit lru // 最后一次访问时间,内存淘汰时使用 24 bit refcount // 引用计数,用于内存自动回收 4 字节 ptr // 指向实际数据的指针 8 字节 } type 决定了这个对象是什么类型(String/List/Hash/Set/ZSet) encoding 决定了底层用什么数据结构存储(SDS/listpack/hashtable/skiplist 等) 同一个 type 可以有不同的 encoding,Redis 会根据数据特征自动选择最优编码 ``` ## 五种基本数据类型  ### String(字符串) ``` 底层实现:SDS(Simple Dynamic String,简单动态字符串) SDS 结构(Redis 3.2+ 根据字符串长度使用不同的 header): sdshdr5(长度 < 32): flags: uint8_t // 低 3 位存类型,高 5 位存长度 buf[] // 数据 sdshdr8(长度 < 256): len: uint8_t // 已使用长度 alloc: uint8_t // 分配的总长度(不含 header 和 \0) flags: uint8_t // 类型标识 buf[] // 数据 sdshdr16/32/64:类似,len/alloc 字段宽度不同 相比 C 字符串的优势: O(1) 获取长度(直接读 len,不用遍历) 预分配空间,减少内存重分配次数 二进制安全(可以存 \0 字节,不会截断) SDS 的内存预分配策略: 修改后长度 < 1MB:分配 2 倍空间(len * 2) 修改后长度 ≥ 1MB:额外分配 1MB 目的:减少频繁扩容的内存重分配次数 编码方式(根据值自动选择): int:整数值,如 SET count 100(直接用 long 存,不用 SDS) embstr:短字符串(≤ 44 字节),redisObject 和 SDS 一次性分配,连续内存 raw:长字符串(> 44 字节),redisObject 和 SDS 分开分配 embstr vs raw 的区别: embstr:一次 malloc,redisObject + sdshdr8 + buf 连续存放 读取时 CPU 缓存友好,只需一次内存分配/释放 raw:两次 malloc,redisObject 和 SDS 分开 embstr 是只读的,修改时会先转为 raw 再修改 embstr vs raw 内存布局对比: embstr(字符串 ≤ 44 字节,一次 malloc): ┌──────────────── 一次分配的内存块 ────────────────────┐ │ redisObject │ sdshdr8 │ buf[] (字符串数据) │ │ (16字节) │ (3字节) │ (≤ 44 字节) │ └──────────────────────────────────────────────────────┘ ptr ──→ 指向紧跟 redisObject 后的 sdshdr8 头部 总共 ≤ 16 + 3 + 44 = 63 字节,jemalloc 分配在同一个 64 字节块内 raw(字符串 > 44 字节,两次 malloc): ┌──────────────────┐ ┌──────────────────────────┐ │ redisObject │ │ sdshdr{16,32,64} │ │ (16字节) │ │ len │ alloc │ flags │ │ ptr ────────────┼──→ │ buf[] (字符串数据) │ └──────────────────┘ └──────────────────────────┘ 两次 malloc → 两块可能不相邻的内存 读取时可能触发两次 CPU 缓存行加载 embstr → raw 的转换触发条件: 1. 对 embstr 执行 APPEND 等修改操作 2. 原 embstr 字符串变长,超出 44 字节限制 3. 此时释放 embstr 内存,重新用 raw 分配 转换过程: SET key "hello" → embstr 编码 APPEND key " world ..." → 转为 raw 编码(不可逆,即使再变短也不会转回 embstr) ``` ```bash # 常用命令 SET key value [EX seconds] [NX] GET key INCR key # 原子自增(计数器) INCRBY key delta MSET k1 v1 k2 v2 # 批量设置 MGET k1 k2 # 批量获取 SETNX key value # 不存在才设置(分布式锁基础) GETSET key value # 设置新值,返回旧值 # 实战:计数器 INCR article:1001:views # 文章浏览量 +1 INCRBY user:1001:score 10 # 用户积分 +10 # 实战:缓存(带过期时间) SET user:1001 '{"name":"张三","age":25}' EX 3600 ``` > 💬 **Q:SET 和 MSET 的区别是什么?** > > 核心区别是**一次操作几个 key**: > > - `SET`:每次只设置一个 key,需要一次网络往返 > - `MSET`:一次设置多个 key,只需一次网络往返,是原子操作(要么全成功要么全失败) > > ```bash > # SET:3 次网络往返 > SET name 张三 > SET age 25 > SET city 北京 > > # MSET:1 次网络往返,性能好 3 倍 > MSET name 张三 age 25 city 北京 > ``` > > 注意:MSET 不支持 `EX`/`NX` 这些选项。如果需要批量设置带过期时间的 key,要用 Pipeline 或 Lua 脚本。 ### List(列表) ``` 底层实现: 元素少且小 → listpack(紧凑列表,连续内存) 元素多或大 → quicklist(双向链表,每个节点是一个 listpack) quicklist 结构: ┌──────┐ ┌──────┐ ┌──────┐ │listpack│←→│listpack│←→│listpack│ └──────┘ └──────┘ └──────┘ 每个 listpack 默认最多 128 个元素 特点: 有序(按插入顺序) 允许重复 支持两端 O(1) 插入/删除 中间操作 O(n) ``` ```bash # 常用命令 LPUSH key v1 v2 # 从左边插入 RPUSH key v1 v2 # 从右边插入 LPOP key # 从左边弹出 RPOP key # 从右边弹出 LRANGE key 0 -1 # 获取所有元素(-1 表示最后一个) LLEN key # 获取长度 BLPOP key timeout # 阻塞弹出(消息队列) # 实战:消息队列(简单版) RPUSH queue:email '{"to":"user@example.com","subject":"验证码"}' BLPOP queue:email 0 # 消费者阻塞等待 # 实战:最新 N 条记录(如最近浏览) LPUSH user:1001:history article:5001 LTRIM user:1001:history 0 9 # 只保留最新 10 条 ``` ### Hash(哈希) ``` 底层实现: 字段少且小 → listpack(紧凑存储) 字段多或大 → hashtable(哈希表) 转换阈值(默认): hash-max-listpack-entries = 128(字段数超过 128 转为 hashtable) hash-max-listpack-value = 64(字段值超过 64 字节转为 hashtable) listpack 内存布局(连续内存,无指针): ┌──────────┬──────────────────────────────────────────┬──────┐ │ total_bytes│ entry1 | entry2 | entry3 | ... | entryN │ 0xFF │ │ (4字节) │ │(结束)│ └──────────┴──────────────────────────────────────────┴──────┘ 每个 entry 的结构: ┌──────────────┬──────────────┬──────────────┐ │ prevlen │ encoding+len │ data │ │ (前一个entry │ (当前entry │ (实际数据) │ │ 的总长度) │ 的编码和长度)│ │ └──────────────┴──────────────┴──────────────┘ listpack 的优势: 无指针,内存紧凑,CPU 缓存友好 元素少时比 hashtable 节省大量内存(hashtable 每个节点有 3 个指针) hashtable 的渐进式 rehash(重点): Redis 的 dict 结构同时维护两个哈希表 ht[0] 和 ht[1] 触发条件: 扩容:负载因子 > 1(元素数 / 桶数 > 1),或正在 BGSAVE 时 > 5 缩容:负载因子 < 0.1 rehash 过程: 1. 为 ht[1] 分配新空间(扩容为 2 倍,缩容为合适大小) 2. 设置 rehashidx = 0(标记开始 rehash) 3. 每次对 dict 进行增删改查时,顺带迁移 ht[0][rehashidx] 的所有元素到 ht[1] 4. rehashidx++,直到 ht[0] 所有桶都迁移完 5. 释放 ht[0],将 ht[1] 设为 ht[0],rehashidx = -1 rehash 期间的读写: 查找:先查 ht[0],再查 ht[1] 新增:只写入 ht[1](保证 ht[0] 只减不增,最终清空) 删除/修改:两个表都操作 渐进式 rehash 分步图解: 初始状态(假设 size=4,有 3 个元素): ht[0]: ┌───┬───┬───┬───┐ │ 0 │ 1 │ 2 │ 3 │ used=3 └─┬─┴───┴─┬─┴─┬─┘ │ │ │ ↓ ↓ ↓ K1→V1 K3→V3 K4→V4 ht[1]: (未分配) rehashidx = -1 步骤 1:触发扩容,ht[1] 分配新空间(size=8),rehashidx = 0 ht[0]: ┌───┬───┬───┬───┐ │ 0 │ 1 │ 2 │ 3 │ ← rehashidx=0 指向当前要迁移的桶 └─┬─┴───┴─┬─┴─┬─┘ │ │ │ ↓ ↓ ↓ K1→V1 K3→V3 K4→V4 ht[1]: ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ └───┴───┴───┴───┴───┴───┴───┴───┘ 步骤 2:某次增删改查触发迁移 bucket[0] 将 K1:V1 从 ht[0] 迁移到 ht[1] 的对应位置 ht[0]: ┌───┬───┬───┬───┐ │ - │ 1 │ 2 │ 3 │ ← rehashidx=1(已迁移完 bucket[0]) └───┴───┴─┬─┴─┬─┘ │ │ ↓ ↓ K3→V3 K4→V4 ht[1]: ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ └───┴─┬─┴───┴───┴───┴───┴───┴───┘ │ ↓ K1→V1 used=1 步骤 3 & 4:每次操作顺带迁移 1 个桶,rehashidx 逐步递增 完成:ht[0] 所有桶迁移完毕,rehashidx = -1 ht[0] ← ht[1](ht[1] 成为新的 ht[0]) ht[1]: (释放) rehashidx = -1 这种设计的好处: 不会阻塞服务,每次迁移只花很少时间 即使不执行命令也能在定时任务中继续迁移(active rehashing) rehash 期间查找:先查 ht[0],ht[0] 没找到再查 ht[1] ``` ```bash # 常用命令 HSET key field value HGET key field HMSET key f1 v1 f2 v2 # 批量设置 HMGET key f1 f2 # 批量获取 HGETALL key # 获取所有字段和值 HDEL key field HINCRBY key field delta # 字段自增 # 实战:存储用户信息(比 String 更节省内存) HSET user:1001 name 张三 age 25 city 北京 HGET user:1001 name HINCRBY user:1001 login_count 1 # 登录次数 +1 ``` ### Set(集合) ``` 底层实现: 元素都是整数且数量少 → intset(整数集合,有序数组) 其他情况 → hashtable 特点: 无序 不允许重复 支持集合运算(交集、并集、差集) ``` #### IntSet(整数集合)详解 ``` IntSet 是 Set 的一种底层实现,基于有序整数数组,使用二分查找。 typedef struct intset { uint32_t encoding; // 编码方式:支持 16 位、32 位、64 位整数 uint32_t length; // 元素个数 int8_t contents[]; // 整数数组(实际类型由 encoding 决定) } 三种编码方式: INTSET_ENC_INT16 → 2 字节整数(对应 Java 的 short) INTSET_ENC_INT32 → 4 字节整数(对应 Java 的 int) INTSET_ENC_INT64 → 8 字节整数(对应 Java 的 long) 数据按升序存储在 contents 数组中,方便二分查找。 编码升级: 如果当前编码是 INT16,插入一个超出 INT16 范围的数 → 整个数组升级为 INT32,所有元素重新编码 升级是不可逆的(不会降级) IntSet 升级过程(倒序拷贝): 原状态(INT16 编码,3 个元素): ┌──────────────┬────────────────────────────┐ │ encoding=16 │ length=3 │ [1] [3] [5] │ └──────────────┴────────────────────────────┘ 每个元素 2 字节,起始偏移 = 8(header) 插入 70000(超出 INT16 范围 → 触发升级为 INT32): 步骤 1:分配新空间 ┌──────────────┬────────────────────────────────────────────┐ │ encoding=32 │ length=4 │ [?] [?] [?] [?] │ └──────────────┴────────────────────────────────────────────┘ 每个元素 4 字节,总空间 = 8 + 4*4 = 24 字节 步骤 2:倒序拷贝旧元素(从后往前,避免覆盖) 位置 3:把原 int16[2] = 5 → 扩展为 int32[2] = 5 位置 2:把原 int16[1] = 3 → 扩展为 int32[1] = 3 位置 1:把原 int16[0] = 1 → 扩展为 int32[0] = 1 ┌──────────────┬────────────────────────────────────────────┐ │ encoding=32 │ length=4 │ [1] [3] [5] [?] │ └──────────────┴────────────────────────────────────────────┘ 步骤 3:插入新元素 70000(二分查找确定位置 → 插入到末尾) ┌──────────────┬──────────────────────────────────────────────────┐ │ encoding=32 │ length=4 │ [1] [3] [5] [70000] │ └──────────────┴──────────────────────────────────────────────────┘ 为什么倒序拷贝?对比正序: 正序拷贝:先扩展 [1] 为 4 字节 → 需要 4 字节空间 但原 [3] 还占用着这 4 字节中的后 2 字节 → 会互相覆盖,导致数据损坏 倒序拷贝:先扩展 [5] 为新位置 → 旧位置暂时保留 再逐个向前迁移 → 安全 关键点: IntSet 不支持降级(INT32 → INT16),因为判断是否有降级需求的成本高 如果删除了所有大元素,仍然保持当前编码(除非用 OBJECT ENCODING 无法强制修改) 编码升级是单向的,这是空间换时间的取舍 ``` ### Dict(字典) ``` Redis 是键值型数据库,键与值的映射关系通过 Dict 实现。 Dict 由三部分组成:哈希表、哈希节点、字典。 typedef struct dictht { dictEntry **table; // entry 数组,保存指向 entry 的指针 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小的掩码,等于 size-1 unsigned long used; // entry 个数 } typedef struct dictEntry { void *key; // 键 union { void *val; uint64_t u64; double d; } v; // 值 struct dictEntry *next; // 下一个 entry 的指针(链地址法解决冲突) } dictEntry; Dict 的渐进式 rehash 详见 Hash 数据类型部分。 ``` ```bash # 常用命令 SADD key v1 v2 v3 SREM key value SMEMBERS key # 获取所有成员 SISMEMBER key value # 判断是否存在 SCARD key # 获取元素数量 SINTER k1 k2 # 交集 SUNION k1 k2 # 并集 SDIFF k1 k2 # 差集 # 实战:共同关注 SADD user:1001:following 2001 2002 2003 SADD user:1002:following 2002 2003 2004 SINTER user:1001:following user:1002:following # 结果:{2002, 2003}(共同关注的人) # 实战:抽奖(随机弹出) SADD lottery user1 user2 user3 user4 user5 SPOP lottery 3 # 随机抽取 3 个中奖者 ``` ### ZSet(有序集合) ``` 底层实现: 元素少且小 → listpack(紧凑存储) 元素多或大 → skiplist(跳表)+ hashtable 为什么同时用跳表和哈希表? 哈希表:O(1) 根据 member 查 score 跳表:O(log n) 按 score 范围查询、排名查询 两者互补,各取所长 ZSet 双结构协作机制: ┌──────────────────────────────────────────────────────────┐ │ ZSet (有序集合) │ │ │ │ ┌─────────────────┐ ┌──────────────────┐ │ │ │ dict (哈希表) │ │ zskiplist (跳表) │ │ │ │ │ │ │ │ │ │ member → score │ │ score → member │ │ │ │ O(1) 查分数 │ │ O(log n) 范围查询 │ │ │ └────────┬────────┘ └────────┬──────────┘ │ │ │ │ │ │ │ 共享同一个 member 和 score │ │ │ └──────────┬─────────────────┘ │ │ │ │ │ ┌───────↓────────┐ │ │ │ 节点数据复用 │ │ │ │ (不是两份拷贝) │ │ │ └────────────────┘ │ └──────────────────────────────────────────────────────────┘ 调用 ZSCORE member 时: → 只用 dict(哈希表),O(1) 直接查 score → 不需要跳表参与 调用 ZRANGEBYSCORE min max 时: → 只用 skiplist(跳表),O(log n) 找到起点,再遍历底层链表 → 不需要 dict 参与 调用 ZADD key score member 时: → 同时写入 dict 和 skiplist(插入/更新) → 两者保持同步 调用 ZREM key member 时: → 先从 dict 查到 score(O(1)) → 再用 score 从 skiplist 删除(O(log n)) → 最后从 dict 删除 内存角度: dict 和 skiplist 的节点共享 member 指针,不会 double 存储字符串数据 score 也只在 skiplist 节点中存一份,dict 的 value 也指向同一 score ``` #### 跳表(Skip List)原理 ``` 跳表是一种多层链表,通过随机化的多级索引实现 O(log n) 查找。 示例:存储 score 为 1, 3, 5, 7, 9 的元素 Level 3: 1 ─────────────────────────────→ 9 Level 2: 1 ──────────→ 5 ──────────────→ 9 Level 1: 1 ────→ 3 ────→ 5 ────→ 7 ────→ 9 Level 0: 1 ──→ 3 ──→ 5 ──→ 7 ──→ 9 查找 score=7 的过程: 从最高层(Level 3)开始 Level 3:1 → 9,7 < 9,下降到 Level 2 Level 2:1 → 5 → 9,7 < 9 且 7 > 5,下降到 Level 1 Level 1:5 → 7,找到! 时间复杂度:O(log n),比链表的 O(n) 快得多 跳表节点的 C 结构(zskiplistNode): typedef struct zskiplistNode { sds ele; // member 值(SDS 字符串) double score; // 分数 struct zskiplistNode *backward; // 后退指针(只有 Level 0 有) struct zskiplistLevel { struct zskiplistNode *forward; // 前进指针 unsigned long span; // 跨度(到下一个节点跳过了几个节点) } level[]; // 层数组(每个节点的层数随机决定) } zskiplistNode; span(跨度)的作用: 用于计算排名(rank) 从头节点到目标节点,沿途所有 span 之和 = 目标节点的排名 ZRANK 命令的 O(log n) 实现依赖 span 层数的随机化: 每个节点的层数通过随机算法决定 P = 0.25(每层晋升概率),最大层数 = 32 期望层数 = 1/(1-P) = 1.33 层 这保证了跳表的平均性能接近 O(log n) 为什么 Redis 用跳表而不用红黑树? 实现简单(红黑树旋转逻辑复杂) 范围查询更高效(跳表天然有序,范围查询只需遍历底层链表) 内存占用相近 span 字段天然支持 O(log n) 的排名查询(红黑树需要额外维护) 为什么不用 B+ 树做索引? 跳表实现相对简单,B+ 树涉及复杂的平衡和分裂操作 跳表更灵活,不需要保持节点的层级关系,内存占用可能更少 跳表在插入和删除时不需要频繁的节点分裂和合并,写性能更好 索引的动态更新: 往跳表中插入数据时,通过随机函数决定将节点插入到哪几级索引中 如果随机函数生成了值 K,就将节点添加到第 1 级到第 K 级索引中 这种随机化保证了跳表的平衡性,无需像 B+ 树那样做复杂的再平衡 ``` ```bash # 常用命令 ZADD key score member ZSCORE key member # 获取分数 ZRANK key member # 获取排名(从小到大,0 开始) ZREVRANK key member # 获取排名(从大到小) ZRANGE key 0 -1 WITHSCORES # 按排名范围获取 ZRANGEBYSCORE key min max # 按分数范围获取 ZINCRBY key delta member # 分数自增 ZCARD key # 获取元素数量 # 实战:排行榜 ZADD game:leaderboard 9500 user:1001 ZADD game:leaderboard 8800 user:1002 ZADD game:leaderboard 9200 user:1003 # 获取 Top 3 ZREVRANGE game:leaderboard 0 2 WITHSCORES # 结果:user:1001(9500), user:1003(9200), user:1002(8800) # 获取用户排名 ZREVRANK game:leaderboard user:1003 # 结果:1(第 2 名,0 开始) # 实战:延迟队列(score 存执行时间戳) ZADD delay:queue 1704067200 '{"task":"send_email","user":1001}' # 消费者定时查询到期任务 ZRANGEBYSCORE delay:queue 0 当前时间戳 ``` ## 三种特殊数据类型 ### Bitmap(位图) ```bash # 本质是 String,用位操作实现 SETBIT user:1001:login 20240115 1 # 记录 1 月 15 日登录 GETBIT user:1001:login 20240115 # 查询是否登录 BITCOUNT user:1001:login # 统计登录天数 BITOP AND result k1 k2 # 位运算(统计同时登录的用户) # 实战:用户签到(一年 365 天只需 46 字节) SETBIT sign:user:1001:2024 14 1 # 第 15 天签到(0 开始) BITCOUNT sign:user:1001:2024 # 今年签到总天数 ``` ### HyperLogLog(基数统计) ```bash # 用极小的内存(12KB)统计大量数据的基数(不重复元素数量) # 误差率约 0.81%,适合不需要精确值的场景 PFADD uv:page:home user1 user2 user3 # 记录访问用户 PFCOUNT uv:page:home # 统计 UV(不重复用户数) PFMERGE uv:total uv:page:home uv:page:about # 合并统计 # 实战:统计网站 UV(每天数百万访问,精确统计内存消耗太大) PFADD uv:20240115 user:1001 user:1002 user:1001 # 重复访问只算一次 PFCOUNT uv:20240115 # 结果:2 ``` ### Geo(地理位置) ```bash # 底层是 ZSet,score 存储 geohash 编码的经纬度 GEOADD locations 116.4 39.9 "北京" 121.5 31.2 "上海" GEODIST locations 北京 上海 km # 计算距离(约 1068 km) GEORADIUS locations 116.4 39.9 500 km # 查找 500km 内的地点 # 实战:附近的人 GEOADD users:location 116.4 39.9 user:1001 GEORADIUS users:location 116.4 39.9 5 km COUNT 10 # 5km 内最近的 10 个用户 ``` ## Redis 通信协议(RESP) ``` Redis 使用自己设计的文本协议 RESP(Redis Serialization Protocol) 基于 TCP 协议,采用请求/响应模式 每条请求由多个参数组成,以命令名称作为第一个参数 详细的 RESP 协议格式和示例见 09-io-model.md ``` ## 面试常见问题 **Q:Redis 是 CP 还是 AP?** A:Redis 是 AP 系统。采用异步复制,一致性模型是最终一致性。主节点写入后异步同步到从节点,网络延迟可能导致节点间数据不一致。Redis 的设计目标是高性能和高可用性,牺牲了强一致性。 **Q:Redis 和 Memcached 的区别?** A:① 数据结构:Redis 支持多种(String/Hash/List/Set/ZSet),Memcached 只支持键值对;② 持久化:Redis 支持 RDB/AOF,Memcached 不支持;③ 线程模型:Redis 单线程执行命令,Memcached 多线程;④ 分片:Redis 哈希槽自动分片,Memcached 手动分片。 **Q:Redis 为什么这么快?** A:① 纯内存操作;② 单线程命令执行,无锁竞争;③ epoll I/O 多路复用;④ 针对不同场景的高效数据结构(如 listpack、跳表)。 **Q:ZSet 的底层是什么?为什么用跳表而不用红黑树?** A:ZSet 底层是跳表 + 哈希表。跳表优势:① 实现简单;② 范围查询高效(天然有序,直接遍历底层链表);③ 内存占用与红黑树相近。哈希表用于 O(1) 查询 member 对应的 score。 **Q:Redis 的 Hash 底层什么时候从 listpack 转为 hashtable?** A:当字段数超过 128(hash-max-listpack-entries)或任意字段值超过 64 字节(hash-max-listpack-value)时,从 listpack 转为 hashtable。 --- 下一篇:[02 - 持久化:RDB 与 AOF](./02-persistence.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入