【redis原理篇】底层数据结构

SDS

Redis是基于C语言实现的，但是Redis中大量使用的字符串并没有直接使用C语言字符串。

一、SDS 的设计动机

传统 C 字符串以 \0 结尾，存在以下问题：

1. 性能瓶颈：获取长度需遍历字符数组，时间复杂度 O(n)。
2. 缓冲区溢出：拼接操作可能覆盖相邻内存。
3. 二进制不安全：无法存储含 \0 的数据（如图片、音频）。
4. 内存重分配频繁：每次修改可能触发 realloc，影响性能。

SDS 通过 结构体封装元数据 和 内存预分配策略 解决这些问题。

二、SDS 的结构设计

SDS 的底层结构由 Header（元数据） 和 字符数组（实际数据） 组成。以 Redis 5.0 为例，其结构定义如下：

struct sdshdr {
    uint8_t len;     // 已使用的字节数（字符串真实长度）
    uint8_t alloc;   // 分配的总字节数（不含 Header）
    unsigned char flags; // SDS 类型标记（如 sdshdr5、sdshdr8）
    char buf[];      // 柔性数组，存储实际字符（以 '\0' 结尾）
};

内存布局

三、SDS 的核心原理

1. O(1) 时间复杂度获取长度

• 传统 C 字符串：需遍历直到 \0，时间复杂度 O(n)。
• SDS：直接读取 len 属性，时间复杂度 O(1)。

2. 杜绝缓冲区溢出

• 自动扩容检查：修改字符串前，检查 alloc - len 的剩余空间。
  • 空间不足时：触发扩容机制，扩展至 新长度 * 2（小于 1MB）或 新长度
  • + 1MB（大于 1MB）。
• 示例：
  原字符串长度 5MB，追加 2MB 数据，新分配空间为 5MB + 2MB + 1MB = 8MB。

3. 二进制安全

• 不依赖 \0 终止符：通过 len 记录真实长度，允许存储任意二进制数据（包括 \0）。
• 示例：
  存储 JPEG 图片数据时，即使内容含多个 \0，SDS 也能完整保存。

4. 内存优化策略

• 预分配（Pre-allocation）：
  扩容时预留额外空间，减少后续修改时的内存分配次数。
• 惰性释放（Lazy Free）：
  缩短字符串时不立即释放内存，仅减少 len，保留 alloc 供后续使用。

Intset

Redis 的 intset（整数集合） 是一种高效的有序整数存储结构，专门用于优化小规模整数集合的内存占用和查询性能。

一、intset 的结构设计

1. 内存布局

intset 由三部分组成：

typedef struct intset {
    uint32_t encoding;  // 编码方式（决定每个整数占用的字节数）
    uint32_t length;    // 元素数量
    int8_t contents[];  // 柔性数组，实际存储整数
} intset;

• encoding：编码类型，可选值：
  • INTSET_ENC_INT16（2 字节，范围 -32768~32767）
  • INTSET_ENC_INT32（4 字节，范围 -2^31~231-1）
  • INTSET_ENC_INT64（8 字节，范围 -2^63~263-1）
• contents：元素按升序排列，便于二分查找。

二、intset 的核心特性

1. 动态编码升级

• 触发条件：插入的整数超出当前编码范围时，自动升级编码（如从 INT16 升级到 INT32）。
• 升级过程：
  1. 计算新编码所需空间。
  2. 按新编码重新分配内存，并将旧数据转换为新格式。
  3. 插入新元素并保持有序。
• 示例：
  原编码为 INT16，插入 40000（超出 INT16 范围） → 升级为 INT32。

2. 有序存储

• 元素排序：所有整数按升序排列，支持 O(log n) 时间复杂度的二分查找。
• 插入复杂度：
  • 查找位置 O(log n) + 移动元素 O(n)（需保持有序性）。
  • 编码升级时还需 O(n) 时间转换数据。

3.案例分析

数组中先插入5,10,20

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为：
encoding：4字节
length：4字节
contents：2字节 * 3 = 6字节

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。
以当前案例来说流程如下：

• 升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
• 倒序依次将数组中的元素拷贝到扩容后的正确位置（防止覆盖后续元素）
• 将待添加的元素放入数组末尾
• 最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

4.插入元素以及扩容源码

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    int prepend = value < 0 ? 1 : 0;

    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);

    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

    /* Set the value at the beginning or the end. */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

Dict

Redis 中的 dict（字典） 是核心数据结构之一，用于实现键值存储（Key-Value）、哈希类型（Hash）及数据库键空间（Keyspace）等核心功能。

一、dict 的结构设计

1. 核心结构体定义

我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。
Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）和字典（Dict）

// 哈希表结构
typedef struct dictht {
    dictEntry **table;      // 哈希桶数组（链式存储）
    unsigned long size;     // 哈希表大小（桶数量，2^n）
    unsigned long sizemask; // 哈希掩码（size-1，用于计算索引）
    unsigned long used;     // 已使用的桶数量（含链表节点）
} dictht;

// 字典结构
typedef struct dict {
    dictType *type;         // 类型特定函数（如哈希函数、键比较函数）
    void *privdata;         // 私有数据（用于扩展）
    dictht ht[2];           // 两个哈希表（用于渐进式 rehash）
    long rehashidx;         // rehash 进度（-1 表示未进行）
    int iterators;          // 当前运行的迭代器数量
} dict;

// 哈希表节点（链表结构）
typedef struct dictEntry {
    void *key;              // 键
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;                    // 值（支持多种类型）
    struct dictEntry *next; // 指向下一个节点（解决哈希冲突）
} dictEntry;

二、dict 的核心机制

1. 哈希函数与冲突解决

• 哈希函数：Redis 默认使用 MurmurHash2 算法（非加密型，高性能，分布均匀）。
• 冲突解决：采用 链地址法（Separate Chaining），同一桶内的节点以链表连接。

2.扩容

触发条件

• 负载因子（Load Factor）：
  • 常规扩容：load_factor = used / size ≥ 1，且当前未在后台执行 BGSAVE 或 BGREWRITEAOF。
  • 强制扩容：load_factor ≥ 5（无论是否在执行持久化操作，避免哈希冲突严重导致性能骤降）。

扩容流程

1. 计算新表大小：

   • 新哈希表的大小为 第一个 ≥ used \* 2 的 2^n（如 used=3 → size=8）。
   • 若当前正在执行 BGSAVE 或 BGREWRITEAOF，Redis 会 延迟扩容（避免资源过度消耗）。

2. 初始化新哈希表（ht[1]）：

   // 分配新哈希表内存
   dictht *new_ht = &d->ht[1];
   new_ht->size = next_power(used * 2);
   new_ht->table = zcalloc(new_ht->size * sizeof(dictEntry*));
   new_ht->sizemask = new_ht->size - 1;
   

3. 启动渐进式 Rehash：

   • 设置 rehashidx = 0，表示开始从旧表 ht[0] 的第 0 号桶迁移数据到 ht[1]。
   • 后续每次对字典的增删改查操作，均迁移一个桶的数据，直到完成所有迁移。

扩容设计思想

• 2^n 大小：通过位运算（hash & sizemask）快速计算索引。
• 渐进式迁移：避免一次性迁移大量数据导致服务阻塞。

三、缩容

1. 触发条件

• 负载因子（Load Factor）：load_factor = used / size < 0.1（默认阈值）。

2. 缩容流程

1. 计算新表大小：

   • 新哈希表的大小为 第一个 ≥ used 的 2^n（如 used=3 → size=4）。
   • 若 used=0，则直接释放旧表，重置为初始状态。

2. 初始化新哈希表（ht[1]）：

   dictht *new_ht = &d->ht[1];
   new_ht->size = next_power(used);
   new_ht->table = zcalloc(new_ht->size * sizeof(dictEntry*));
   new_ht->sizemask = new_ht->size - 1;
   

3. 启动渐进式 Rehash：

   • 与扩容相同，逐步迁移数据到新表 ht[1]。
   • 迁移完成后，释放旧表 ht[0]，将 ht[1] 设为 ht[0]。

3. 缩容设计思想

• 节省内存：避免因数据删除后哈希表过大导致内存浪费。
• 延迟缩容：防止频繁缩容触发性能抖动。

四、渐进式 Rehash 的通用流程

无论是扩容还是缩容，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。同时为了防止一次转移导致的性能抖动，采用渐进式 Rehash 完成数据迁移：

1. 每次操作触发迁移：

   • 对字典的 增、删、改、查 操作均可能触发迁移一个桶的数据。
   • 迁移的桶号为 rehashidx，完成后 rehashidx++。

2. 迁移单个桶的步骤：
   a. 遍历旧桶链表：处理 ht[0].table[rehashidx] 的所有节点。
   b. 重新哈希计算索引：对新表 ht[1] 计算每个节点的哈希值和索引。

   for (entry = old_table[rehashidx]; entry != NULL; entry = next_entry) {
       next_entry = entry->next;
       // 计算新索引
       uint64_t hash = dict->type->hashFunction(entry->key);
       uint64_t new_index = hash & new_sizemask;
       // 插入新表
       entry->next = new_table[new_index];
       new_table[new_index] = entry;
   }
   

   c. 清空旧桶：将 ht[0].table[rehashidx] 设为 NULL。
   d. 更新计数器：递减 ht[0].used，递增 ht[1].used。

3. 检查迁移完成：

   • 当 rehashidx >= ht[0].size 时，所有桶迁移完成。
   • 释放旧表：销毁 ht[0].table，将 ht[1] 设为 ht[0]，重置 ht[1] 为空。
   • 结束 Rehash：设置 rehashidx = -1。

三、添加键值对的核心流程

1. 检查 Rehash 状态

• 判断是否处于 Rehash：
  • 若字典的 rehashidx != -1，表示正在进行 渐进式 Rehash（数据从旧表 ht[0] 迁移到新表 ht[1]）。
  • 直接操作新表：所有新插入的键值对会写入 ht[1]，避免旧表 ht[0] 继续积累数据。
  • 触发迁移：每次插入操作后，顺带迁移 ht[0] 中的一个桶（Bucket）到 ht[1]，逐步完成数据迁移。

2. 计算哈希值与索引

• 哈希函数：使用预设的哈希算法（如 MurmurHash2）计算键的哈希值。

  hash = dict->type->hashFunction(key);  // 例如，MurmurHash2
  

• 确定桶索引：通过哈希值与当前哈希表的大小掩码（sizemask = size - 1）计算索引。

  index = hash & dict->ht[table].sizemask;  // table=0 或 1（取决于是否在 Rehash）
  

3. 处理键的存在性

• 遍历链表：在目标桶的链表中顺序查找键是否存在。

  • 键已存在：

    • 替换旧值，释放旧值内存（若配置了值释放函数）。
    • 返回 DICT_OK 表示更新成功。

  • 键不存在：

    • 创建新节点 dictEntry，将键值对存入。
    • 头插法插入链表：将新节点插入链表头部（时间复杂度 O(1)）。

    entry->next = ht->table[index];
    ht->table[index] = entry;
    

4. 更新计数器与触发扩容

• 更新计数器：递增哈希表的 used 计数器，表示已用桶数量增加。

  ht->used++;
  

• 检查扩容条件：

  • 负载因子：计算 load_factor = used / size。
  • 触发扩容：
    • 常规扩容：若 load_factor ≥ 1 且允许扩容。
    • 强制扩容：若 load_factor ≥ 5（避免哈希冲突严重导致性能骤降）。
  • 扩容操作：
    1. 创建新哈希表 ht[1]，大小为第一个 ≥ used * 2 的 2 的幂次（如 used=4 → size=8）。
    2. 设置 rehashidx=0，启动渐进式 Rehash。

5. 返回结果

• 成功：返回 DICT_OK。
• 失败：若内存分配失败（如无法创建新节点），返回 DICT_ERR。

graph TD
    subgraph 添加键值对核心流程
    start([开始]) --> check_rehash{检查Rehash状态}
    
    check_rehash --> |rehashidx != -1| new_table[操作新表ht<x-preset class="no-tts reference-tag disable-to-doc" data-index="1">1</x-preset>]
    new_table --> migrate[迁移ht<x-preset class="no-tts reference-tag disable-to-doc" data-index="0">0</x-preset>的一个桶到ht<x-preset class="no-tts reference-tag disable-to-doc" data-index="1">1</x-preset>]
    
    check_rehash --> |rehashidx = -1| compute_hash[计算哈希值]
    migrate --> compute_hash
    
    compute_hash --> get_index[计算桶索引: hash & sizemask]
    
    get_index --> key_check{键是否存在?}
    
    key_check --> |存在| replace[替换旧值并释放内存]
    replace --> return_ok[返回DICT_OK]
    
    key_check --> |不存在| create_entry[创建新dictEntry]
    create_entry --> insert[头插法插入链表]
    insert --> update_counter[更新used计数器]
    
    update_counter --> check_expand{检查扩容条件}
    
    check_expand --> |load_factor ≥1| normal_expand[常规扩容]
    check_expand --> |load_factor ≥5| force_expand[强制扩容]
    
    normal_expand --> create_ht1[创建ht<x-preset class="no-tts reference-tag disable-to-doc" data-index="1">1</x-preset>\n大小为used*2的2^n]
    force_expand --> create_ht1
    create_ht1 --> start_rehash[设置rehashidx=0]
    
    start_rehash --> return_ok
    return_ok --> end_process([结束])
    
    check_expand --> |无需扩容| return_ok
    end_process
    end

Ziplist

一、ziplist的结构设计

1.整体布局

• **zlbytes（4字节）😗*总字节数，用于快速获取列表大小。
• **zltail（4字节）😗*尾节点偏移量，用于定位尾节点。
• **zllen（2字节）😗*节点长度（数量）（若超过65535，需遍历计算）。
• **entry:**节点单元，存储数据。
• **zlend（1字节）😗*结束标识（0xFF）。

2.Entry结构

• **previous_entry_length（1或5字节）😗*前一节点单元大小。
  • 前驱长度≤ 253:prelen占一字节。
  • 前驱长度 > 253：prevlen 首字节固定为 0xFE，后4字节存储实际长度。
• **encoding（1、2、5字节）😗*编码属性，用于标识content的类型（字符串或整数）和长度。
• **content:**保存数据（字符串或整数）。

3.Encoding编码

分为字符串和整数两种

字符串类型编码

字符串类型以00（1字节）、01（2字节）、10（5字节）开头，除前两位外其余位均记录字符串大小。

整数类型编码

整数类型以11开头，固定为1字节，其余六位标识五种整数类型分别占据了00|0000、01|0000、10|0000。这样我们就能用11|xxxx直接保存数据在后四位，而11|0000和11|1110、0xff（结束标识）被占据所以具体可存储值有13个。

二、ziplist 的核心特性

1. 内存紧凑

• 连续存储：消除指针开销，内存利用率高。
• 变长编码：根据数据动态调整存储空间（如小整数用1字节）。

2. 双向遍历

• 前驱指针模拟：通过 prevlen 字段反向计算前驱 entry 起始位置。
• 正向遍历：利用 encoding 解析当前 entry 长度，跳至下一 entry。

3. 自动编码转换

• 阈值控制：当元素数量或大小超过配置（如 hash-max-ziplist-entries），转为标准结构（如哈希表）。

三、ziplist 的操作机制

1. 插入操作

• 定位插入点：遍历找到位置，计算所需空间。
• 内存重分配：扩展 ziplist 内存，移动后续 entry。
• 更新前后 entry：
  • 修改后继 entry 的 prevlen。
  • 可能触发 级联更新（Cascade Update）：若新 entry 导致后继 entry 的 prevlen 扩容（1→5字节），需递归处理后续 entry。

2. 删除操作

• 内存缩容：移除 entry 后，前移后续数据。
• 级联更新风险：类似插入，可能触发后继 entry 的 prevlen 调整。

3. 查询操作

• 顺序遍历：从头或尾（利用 zltail）开始，解析每个 entry 的 encoding 和 prevlen。

四、级联更新（Cascade Update）

1. 触发条件

插入或删除 entry 导致后继 entry 的 prevlen 从1字节扩展为5字节（或反向收缩）

例如连续节点大小为250-253（前驱节点大小1字节），有一节点数据变更超出253字节，后续节点的prelen变为5字节存储，变更后这个节点的大小也超过了253字节，循环往复。

2. 性能影响

• 最坏时间复杂度：O(n²)（如所有 entry 的 prevlen 均需调整）。
• 实际场景：概率极低，通常在小规模 ziplist 中影响有限。

QuickList

quicklist 是 Redis 用于实现 列表（List） 数据类型的核心数据结构，结合了 ziplist（压缩列表）和 linkedlist（双向链表）的优势，在内存效率与操作性能之间取得平衡。

一、qiucklist的设计背景

1.早期列表实现的不足

• ziplist
  • **优点：**内存紧凑，不需要指针占据额外内存空间。
  • **缺点：**插入、删除操作需重分配内存，移动后续节点，大规模数据下性能差。
• linedlist
  • 优点：插入、删除高效。
  • 缺点：内存碎片多，指针占据额外空间。

2.qiucklist的优势

​ 保留ziplist的内存紧凑优势，同时限制ziplist大小，将多个ziplist通过双向链表连接，避免了单个ziplist在大规模数据下内存重分配带来的性能差的弊端。

二、quicklist的结构

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。
如果值为正，则代表ZipList的允许的entry个数的最大值
如果值为负，则代表ZipList的最大内存大小，分5种情况：

• -1：每个ZipList的内存占用不能超过4kb
• -2：每个ZipList的内存占用不能超过8kb
• -3：每个ZipList的内存占用不能超过16kb
• -4：每个ZipList的内存占用不能超过32kb
• -5：每个ZipList的内存占用不能超过64kb

其默认值为 -2

三、quicklist 的核心机制

1. 动态节点管理

• 节点分裂：当插入元素导致单个 ziplist 超过 fill 阈值时，分裂为两个节点。
• 节点合并：当删除元素导致相邻节点容量过小时，合并以减少内存碎片。

2. 压缩优化

• LZF 压缩算法：对中间节点进行压缩（compress 参数控制压缩深度）。
  • 压缩深度为 0：不压缩。
  • 压缩深度为 1：头尾各保留 1 个节点不压缩，其余压缩。
  • 压缩深度为 2：头尾各保留 2 个节点不压缩，其余压缩。

SkipList

一、跳表的核心设计

1. 基本概念

跳表通过 多层链表 实现有序数据的快速访问。每个节点包含多个 层级，每层维护一个指向后续节点的指针，高层指针可跨越多个低层节点，从而加速查找。

2. 节点结构

3. 层数生成规则

• 幂次定律：新节点的层数随机生成，概率逐层减半。
  • 第 1 层概率：100%
  • 第 2 层概率：50%
  • 第 3 层概率：25%
  • …
  • 最大层数：ZSKIPLIST_MAXLEVEL = 32（Redis 默认限制）

二、跳表的操作机制

1. 查找操作

• 从最高层开始：逐层遍历，若当前层的下个节点分值大于目标值，则下降一层继续查找。
• 时间复杂度：平均 O(log n)，最坏 O(n)。

2. 插入操作

1. 确定插入位置：查找过程中记录每层的前驱节点。
2. 生成随机层数：根据幂次定律确定新节点层数。
3. 调整指针：将新节点插入各层链表，更新前后节点的指针和跨度。

3. 删除操作

1. 定位节点：查找目标节点，并记录各层前驱节点。
2. 更新指针：将前驱节点的指针指向目标节点的后继节点。
3. 释放内存：若节点无其他引用，释放内存。

RedisObject

Redis 的 redisObject 是管理所有数据类型（如字符串、列表、哈希等）的核心结构，它通过统一的接口抽象，实现了内存优化、编码转换等操作。

一、redisObject 的结构定义

二、核心字段详解

1. 数据类型（type）

Redis 支持 5 种基础数据类型，由 type 标识：

• OBJ_STRING：字符串（简单值、计数器、二进制数据）。
• OBJ_LIST：列表（队列、栈、阻塞队列）。
• OBJ_HASH：哈希（对象属性存储）。
• OBJ_SET：集合（唯一性集合、交并差运算）。
• OBJ_ZSET：有序集合（排行榜、范围查询）。

2. 编码方式（encoding）

同一数据类型可对应多种底层编码，Redis 根据数据特征自动选择最优编码：