redis存储结构

一、存储结构

 存储转换：

1. string

   • int：字符串长度 ≤ 20 且能转成整数
   • raw：字符串长度 > 44
   • embstr：字符串长度 ≤ 44
   • 附加：CPU 缓存中基本单位为 cacheline 64 字节

2. list

   • quicklist（双向链表）
   • ziplist（压缩列表）：间接使用

3. hash

   • dict（字典）：节点数量 > 512 或字符串长度 > 64
   • ziplist（压缩列表）：节点数量 ≤ 512（hash - max - ziplist - entries）且字符串长度 ≤ 64（hash - max - ziplist - value）

4. set

   • intset（整数数组）：元素都为整数且节点数量 ≤ 512（set - max - intset - entries）
   • dict（字典）：元素有一个不为整数或数量 > 512

5. zset

   • skiplist（跳表）：数量 > 128 或者有一个字符串长度 > 64
   • ziplist（压缩列表）：子节点数量 ≤ 128（zset - max - ziplist - entries）且字符串长度 ≤ 64（zset - max - ziplist - value）

二、字典实现 

        redis 中 KV 组织是通过字典来实现的；hash 结构当节点超过 512 个或者单个字符串长度大于 64 时，hash 结构采用字典实现；

typedef struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;
} dictEntry;typedef struct dictht {dictEntry **table;unsigned long size;// 数组长度unsigned long sizemask; //size-1unsigned long used;//当前数组当中包含的元素
} dictht;typedef struct dict {dictType *type;void *privdata;dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 */int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error)用于安全遍历*/
} dict;

         负载因子 = used / size ； used 是数组存储元素的个数， size 是数组的长度；

扩容

缩容

五、scan

scan cursor [MATCH pattern] [COUNT count] [TYPE type]

Redis 的 SCAN 命令是一种渐进式遍历键的机制，用于替代 KEYS 命令（KEYS 会阻塞服务器，不适用于生产环境）。它通过游标逐步遍历数据库中的键，不会对服务器性能造成长时间阻塞。以下是其原理和示例：

---

一、SCAN 机制原理

1. 游标（Cursor）
   SCAN 使用一个游标 cursor 来记录遍历的位置。每次调用 SCAN，都会返回一个新的游标，用于下一次遍历。当游标为 0 时，表示遍历结束。

2. 哈希表槽位遍历
   Redis 的数据库是一个哈希表，SCAN 通过遍历哈希表的槽位（slot）来查找键。它采用 高位进位加法 的顺序遍历槽位，这种算法确保在哈希表 rehash（扩容或缩容）后，槽位的遍历顺序仍然相邻，从而尽量保证对 SCAN 开始时已存在的数据 不重复、不遗漏（特殊情况除外，如两次缩容可能导致重复）。

3. 参数控制

   • MATCH pattern：用于筛选符合特定模式的键（如 user:* 表示以 user: 开头的键）。
   • COUNT count：提示 Redis 每次遍历的大致数量，但实际返回的键数量可能因哈希表结构而有所不同。

4. 数据变更处理

   • SCAN 仅保证对 SCAN 开始时已存在的数据进行遍历，不保证遍历过程中新增的键会被扫描到。
   • 扩容或缩容会改变键的映射，但高位进位加法算法能确保对 SCAN 开始时已存在的数据的遍历正确性。

---

二、具体示例

假设 Redis 中有以下键：user:1、user:2、order:1、order:2、cache:1。

示例 1：基本 SCAN 遍历

1. 第一次调用：

2. SCAN 0
   

   假设返回 10 和部分键（如 ["user:1", "order:1"]），表示游标移动到 10。

3. 第二次调用：

4. SCAN 10
   

   假设返回 0 和剩余键（如 ["user:2", "order:2", "cache:1"]），表示遍历结束（游标回到 0）。

示例 2：带模式匹配的 SCAN

查找所有以 user: 开头的键：

SCAN 0 MATCH "user:*"

假设返回 10 和 ["user:1", "user:2"]，继续用新游标 10 遍历，直到游标为 0。

示例 3：带 COUNT 提示的 SCAN

提示每次遍历约 3 个键：

 

SCAN 0 COUNT 3

 

Redis 会尽量返回接近 3 个键，但实际数量可能因哈希表结构而变化。

---

三、注意事项

• 不保证顺序：SCAN 返回的键顺序是不确定的，因为它基于哈希表槽位的遍历。
• 数据变更影响：若在 SCAN 过程中大量新增或删除键，新增键可能不会被遍历，删除键若已被扫描则会被返回（但实际已不存在，需业务层过滤）。
• 缩容重复问题：理论上，若在 SCAN 过程中发生两次缩容，可能出现重复键（但这种情况极少，属于特殊场景）。

---

假设场景

• 初始哈希表 ht[0] 有 4 个槽（编号 0~3，二进制表示为 2 位：00, 01, 10, 11）。
• 触发扩容后，新表 ht[1] 有 8 个槽（编号 0~7，二进制表示为 3 位）。
• 假设 ht[0] 的槽 0 有键 A，槽 2 有键 B。扩容后，槽 0 对应 ht[1] 的槽 0 和 4（高位为 0 和 1），槽 2 对应 ht[1] 的槽 2 和 6（高位为 0 和 1）。

高位进位加法的遍历逻辑

1. ht[0] 阶段（4 个槽，2 位二进制）
   遍历顺序按高位进位加法：
   0（00） → 2（10） → 1（01） → 3（11）。
   此时能覆盖 ht[0] 所有槽。

2. 扩容到 ht[1]（8 个槽，3 位二进制）
   高位进位加法的遍历顺序为：
   0（000） → 4（100） → 2（010） → 6（110） → 1（001） → 5（101） → 3（011） → 7（111）。

   • 原 ht[0] 槽 0 对应 ht[1] 的 0 和 4，在遍历顺序中是连续的（0 → 4）。
   • 原 ht[0] 槽 2 对应 ht[1] 的 2 和 6，在遍历顺序中也是连续的（2 → 6）。

   这样，ht[0] 中每个槽的数据在 ht[1] 中对应的新槽会被连续遍历，确保 SCAN 开始时已存在的键（如 A 和 B）不会遗漏。

六、expire机制

# 只支持对最外层key过期；
expire key seconds
pexpire key milliseconds
ttl key
pttl key

Redis 的 expire 机制用于管理键的生命周期，允许为键设置生存时间（TTL），当时间到期后自动删除键，从而节省内存资源。以下是其详细介绍及示例：

一、设置过期时间的命令

• EXPIRE key seconds：以秒为单位设置键的过期时间。
  例如：EXPIRE mykey 60，表示 mykey 会在 60 秒后过期。
• PEXPIRE key milliseconds：以毫秒为单位设置过期时间。
• EXPIREAT key timestamp：使用 UNIX 时间戳（秒）设置过期时间。
• PEXPIREAT key timestamp：使用 UNIX 时间戳（毫秒）设置过期时间。
• TTL key / PTTL key：分别以秒、毫秒为单位返回键的剩余生存时间。若键未设置过期时间，返回 -1；若键不存在，返回 -2。

二、过期键的存储

        Redis 内部使用一个名为 expires 的字典存储键的过期时间。字典的键是数据库中的键，值是对应键的过期时间（以毫秒为单位的 UNIX 时间戳）。例如，设置 mykey 60 秒后过期，expires 字典会记录 mykey 对应的过期时间戳。

三、过期键的删除策略

1. 惰性删除（Lazy Expiration）
   当客户端尝试访问一个键时，Redis 会检查该键是否过期。若过期，则删除该键并返回空值。

   • 优点：仅在访问时检查，减少不必要的 CPU 开销。
   • 缺点：若键长期不被访问，可能导致内存泄漏（过期键一直占用内存）。

2. 定期删除（Periodic Expiration）
   Redis 定期随机抽取一部分键，检查其是否过期，若过期则删除。

   • 检查频率和每次检查的键数量可通过配置调整（默认每秒检查 10 次，每次检查 20 个键）。
   • 若一批检查中发现有过期键，会继续检查下一批，直到无过期键或达到最大检查次数。
   • 平衡了 CPU 开销和内存回收效率，避免过期键长时间留存。

四、示例

127.0.0.1:6379> SET mykey "hello"  # 创建键值对
OK
127.0.0.1:6379> EXPIRE mykey 10     # 设置 mykey 10 秒后过期
(integer) 1
127.0.0.1:6379> TTL mykey           # 查看剩余生存时间（秒）
(integer) 8
127.0.0.1:6379> PTTL mykey          # 查看剩余生存时间（毫秒）
(integer) 7890
# 等待 10 秒后再次操作
127.0.0.1:6379> GET mykey           # 键已过期删除，返回 (nil)
(nil)
127.0.0.1:6379> TTL mykey           # 键不存在，返回 -2
(integer) -2

 

        通过 expire 机制，Redis 能有效管理过期数据，结合惰性删除和定期删除策略，在性能和内存管理上取得平衡，适用于缓存失效、限时数据等场景（如购物车超时自动清理、验证码有效期控制等）。

七、大KEY

        在 redis 实例中形成了很大的对象，比如一个很大的 hash 或很大的 zset，这样的对象在扩容的时 候，会一次性申请更大的一块内存，这会导致卡顿；如果这个大 key 被删除，内存会一次性回收， 卡顿现象会再次产生；

# 每隔0.1秒 执行100条scan命令
redis-cli -h 127.0.0.1 --bigkeys -i 0.1

八、跳表

 一、跳表的作用与特性

跳表是一种 多层有序链表结构，主要用于实现有序集合（如 Redis 中的有序集合类型），支持高效的范围查询（如 zrange、zrevrange）。其设计目标是在节点间建立直接连接，确保增删改操作后结构依然有序，同时维持较低的时间复杂度。

二、理想跳表

• 结构特点：
  每隔一个节点生成一个层级节点，模拟二叉树结构。例如，底层链表包含所有节点，上一层级每隔一个节点抽取一个形成高层链表，以此类推。这种结构使得搜索时间复杂度达到 O(log2​n)，通过 “空间换时间” 提升查询效率。
• 操作问题：
  若对理想跳表直接进行删除或增加操作，容易破坏其结构，重构代价巨大。因此，引入概率方法优化。
• 概率优化：
  从每个节点出发，每增加一个节点都有 21​ 的概率增加一个层级，41​ 的概率增加两个层级，81​ 的概率增加三个层级，以此类推。当数据量足够大（如 128 个节点时），通过概率构造的跳表趋近于理想跳表。此时，若删除节点，无需重构跳表结构，时间复杂度为 (1−w1​)∗O(log2​n)（w 为平均层级宽度）。

三、Redis 跳表的优化

• 结构扁平化：
  为节约内存，Redis 牺牲少许时间复杂度，使跳表结构更扁平（类似将二叉堆改为四叉堆），减少层级数量。
• 层级限制：
  Redis 限制跳表的最高层级为 32，避免层级过多导致内存浪费。
• 使用条件：
  当节点数量大于 128 或有一个字符串长度大于 64 时，Redis 会使用跳表。这种设计在内存占用和操作效率间取得平衡。

四、与其他结构的对比

• 有序数组：通过二分查找可获得 O(log2​n) 的时间复杂度，但增删操作代价高（需移动大量元素）。
• 平衡二叉树：也能达到 O(log2​n) 的时间复杂度，但实现复杂，插入、删除时需频繁调整树结构（如旋转操作）。
• B+ 树：时间复杂度为 h∗O(log2​n)（h 为树高），但存在复杂的节点分裂操作，实现难度大。
  跳表则通过链表层级结构，在保证接近上述结构时间复杂度的同时，简化了增删改操作的实现，尤其适合 Redis 对有序集合的操作需求。

数据结构：

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {sds ele;double score; // WRN: score 只能是浮点数struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned long span; // 用于 zrank} level[];
} zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length; // zcardint level; // 最高层
} zskiplist;typedef struct zset {dict *dict; // 帮助快速索引到节点zskiplist *zsl;
} zset;

0voice · GitHub