深度剖析：从底层数据结构看Redis高性能的存储设计

Redis 以其卓越的性能闻名，这背后与其精巧的数据存储设计密不可分。它是一种基于 ANSI C 语言编写、支持网络和持久化的键值对内存数据库，并提供了丰富的 API。其核心数据类型主要就是五种：String（字符串）、List（列表）、Hash（哈希）、Set（集合）和 ZSet（有序集合）。

在互联网业务中，这些数据类型有着广泛的应用：

• String： 缓存、限流、计数器、分布式锁、分布式 Session
• Hash： 存储用户信息、用户主页访问量、组合查询
• List： 微博关注人时间轴列表、简单队列
• Set： 点赞、点踩、标签、好友关系
• Zset： 排行榜

例如，在电商大促等高并发场景下，为了保证系统稳定，库存扣减可以这样设计：

这个设计中，直接在 Redis 中完成库存扣减，然后记录操作日志，再通过一个 Worker 程序异步同步到数据库中。在设计这个同步 Worker 时，必须仔细考虑如何处理并发和重复消费等问题。

从这些应用可以看出 Redis 的高效与稳定。那么，它的底层到底是如何实现的呢？

Redis 的对象：redisObject

当我们执行 set hello world 这条命令时，数据在内存中的模型可以这样理解：

• dictEntry： Redis 为每一个键值对分配一个 dictEntry 结构，里面包含 key 和 val 的指针。next 指针指向下一个 dictEntry，形成一个链表。这个机制可以将哈希值相同的多个键值对链接在一起，以此来解决哈希冲突，也就是我们常说的“链地址法”。
• sds： 键 key “hello” 是以 SDS（Simple Dynamic String，简单动态字符串）格式存储的。
• redisObject： 值 val “world” 存储在 redisObject 中。实际上，Redis 常用的五种数据类型，其值都是以 redisObject 对象的形式来存储的。redisObject 中的 type 字段指明了值对象的类型（如字符串、列表等），ptr 指针则指向对象实际所在的内存地址。

redisObject 对象至关重要，Redis 对象的类型识别、内部编码、内存回收、共享对象等功能都依赖于它。这种设计的精妙之处在于，它可以针对不同的使用场景，为五种基本类型设置多种不同的底层数据结构实现，从而最大程度地优化对象在不同场景下的使用效率。

无论是 dictEntry、redisObject 还是 SDS 对象，都需要内存分配器（如 jemalloc）来分配内存。jemalloc 是 Redis 的默认内存分配器，它在减少内存碎片方面表现优异。例如，在 64 位系统中，jemalloc 将内存空间划分为小、大、巨大三个范围，每个范围又细分为许多小的内存块单位。当 Redis 存储数据时，会选择大小最合适的内存块进行分配，以提高内存利用率。

如前所述，每个对象都由一个 redisObject 结构表示，其 ptr 指针指向底层的数据结构，而具体是哪种数据结构则由 encoding 属性决定。例如，我们执行以下命令查看键“hello”的编码：

Redis 所有底层数据结构对应的编码常量如下（这对于理解后续内容很重要）：

String（字符串）

字符串对象的底层实现可以是 int、raw 或 embstr（上表中有对应名称）。其中，embstr 编码通过一次内存分配函数调用，分配一块连续的空间来存储 redisObject 和 SDS；而 raw 编码则需要两次调用。

int 编码和 embstr 编码的字符串对象在一定条件下会转化为 raw 编码。

• embstr： 用于存储长度小于等于 39 字节的字符串。
• int： 用于存储 8 字节的长整型数值。
• raw： 用于存储长度大于 39 字节的字符串。

简单动态字符串（SDS）是 Redis 对字符串的底层实现，其结构类似于 C++ 的 std::string 或 Java 的 ArrayList<Character>，长度动态可变：

struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[]; // 以 ‘\0’ 空字符结尾
};

其关键操作复杂度如下：

• get (sdsrange): O(n)
• set (sdscpy): O(n)
• create (sdsnew): O(1)
• len (sdslen): O(1)

SDS 相比 C 原生字符串的优势：

1. 常数复杂度获取字符串长度： 因为 SDS 在 len 属性中直接记录了字符串长度，所以获取长度的时间复杂度仅为 O(1)。
2. 预空间分配： 当修改一个 SDS 时，分为两种情况分配额外空间：
   • 如果 SDS 的 len 小于 1MB，程序会分配和 len 同样大小的未使用空间（free 值等于 len）。例如，修改后 len 为 15 字节，则实际分配的 buf 数组长度为 15(used) + 15(free) + 1(\0) = 31 字节。
   • 如果 SDS 的 len 大于等于 1MB，程序会固定分配 1MB 的未使用空间。例如，修改后 len 为 30MB，则实际长度为 30MB + 1MB + 1byte。
3. 惰性释放空间： 当执行如 sdstrim（截取字符串）操作后，SDS 不会立即释放多出来的空间。如果后续进行字符串拼接操作，且新内容大小不超过之前释放的空间，则可以直接复用这些空间，避免了频繁的内存重分配。
4. 杜绝缓冲区溢出： C 字符串操作（如 strcat）在忘记重分配内存时极易造成缓冲区溢出。而 SDS 的 API 在可能造成溢出时会自动进行内存重分配，从根本上杜绝了此问题。

List（列表）

List 对象的底层实现是 quicklist（快速列表），它是 ziplist（压缩列表）和 linkedlist（双端链表）的组合。Redis 的列表支持两端插入和弹出，能获取指定位置（或范围）的元素，可以充当数组、队列、栈等多种角色。

typedef struct listNode {
     // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
 } listNode;

 typedef struct list {
     // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
     // 节点值对比函数
    int (*match)(void *ptr, void *key);
     // 链表所包含的节点数量
    unsigned long len;
 } list;

其关键操作复杂度：

• rpush / lpush (listAddNodeHead/Tail): O(1)
• insert (listInsertNode): O(1)
• index (listIndex): O(N)
• pop (ListFirst/Last): O(1)
• llen (listLength): O(1) // 注：得益于 list.len 属性

4.1 linkedlist（双端链表）

这种结构类似于 Java 的 LinkedList。

从图中可以看出 Redis 的 linkedlist 特性：每个节点都有 prev 和 next 指针，链表本身持有 head 和 tail 指针。因此，获取前置、后置、表头、表尾节点的复杂度都是 O(1)。通过 len 属性获取节点数量的复杂度也是 O(1)。

与双端链表相比，压缩列表更节省内存，但进行修改或增删操作时复杂度较高。因此，当节点数量较少时，使用压缩列表更划算；节点数量多时，则使用双端链表。

4.2 ziplist（压缩列表）

当一个列表键只包含少量列表项，并且这些项要么是小整数值，要么是长度较短的字符串时，Redis 就会使用 ziplist 作为底层实现。

ziplist 是 Redis 为节约内存而开发的，它是由一系列特殊编码的连续内存块组成的顺序型数据结构（不像双端链表那样每个节点都是独立分配内存的指针）。其具体结构比较复杂。

在新版本的 Redis 中，列表的底层已经统一用 quicklist 替代了 ziplist 和 linkedlist：

quicklist 是 ziplist 和 linkedlist 的混合体。它将 linkedlist 按段切分，每一段使用一个 ziplist 来紧凑存储数据，多个 ziplist 之间再用双向指针连接起来。传统的链表每个节点的附加空间（prev 和 next 指针）就占了 16 个字节（64位系统），且每个节点单独分配内存，容易加剧内存碎片化，影响内存管理效率。

quicklist 默认的压缩深度是 0，即不压缩。为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 通常不压缩（此时深度为 1）。为了进一步节约空间，Redis 还可以使用 LZF 算法对中间的 ziplist 节点进行压缩存储。

Hash（哈希）

Hash 对象的底层实现可以是 ziplist（压缩列表）或者 hashtable（字典/哈希表）。

Hash 对象只有同时满足以下两个条件时，才会使用 ziplist：

1. 哈希中元素数量小于 512 个。
2. 哈希中所有键值对的键和值的字符串长度都小于 64 字节。

否则，将使用 hashtable。hashtable 可以实现 O(1) 复杂度的读写操作，因此效率极高。其核心源码如下：

typedef struct dict {
    // 类型特定函数
    dictType *type;
     // 私有数据
    void *privdata;
     // 哈希表（通常使用ht[0]，ht[1]用于rehash）
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
     // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
 } dict;

 typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
     // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

typedef struct dictEntry {
    void *key;
    union {void *val;uint64_t u64;int64_t s64;} v;
    // 指向下个哈希表节点，形成链表（解决哈希冲突）
    struct dictEntry *next;
 } dictEntry;

 typedef struct dictType {
     // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
     // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
     // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
     // 对比键的函数
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

上面的结构可以简化为如下示意图：

这个结构类似于 JDK7 之前的 HashMap<String,Object>。当两个或以上的键被哈希函数分配到数组的同一个索引（桶）上时，会产生哈希冲突。Redis 同样使用链地址法来解决冲突，即每个哈希表节点（dictEntry）都有一个 next 指针，多个节点用 next 指针构成一个单向链表。

Redis 的字典使用 hashtable 作为底层实现时，会持有两个哈希表（ht[0] 和 ht[1]）。ht[0] 是平时主要使用的，ht[1] 仅在 rehash（重新散列）时使用。随着对哈希表的不断操作，键会逐渐增多或减少。为了让哈希表的负载因子维持在一个合理范围内，Redis 会通过 rehash 操作对哈希表的大小进行扩展或收缩。这个过程是渐进式的，分多次、逐步地将 ht[0] 里的所有键值对 rehash 到 ht[1] 中。

Set（集合）

Set 集合对象的底层实现可以是 intset（整数集合）或者 hashtable。

intset 当一个集合只包含整数元素，并且元素数量不多时，Redis 会使用 intset 作为底层实现。

typedef struct intset {
    // 编码方式（决定contents数组的整数类型）
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组（按值从小到大有序排列）
    int8_t contents[];
} intset;

其关键操作复杂度：

• sadd (intsetAdd): O(1) 平均
• smembers (intsetGet): O(N) // 遍历整个数组
• srem (intsetRemove): O(N) 平均
• scard (intsetLen): O(1) // 直接返回 length

intset 底层是一个有序、无重复的整数数组。contents 数组的类型可以是 16位、32位或64位的整数。如果数组里所有整数都是16位的，当新加入一个32位的整数时，整个数组将“升级”成32位的数组。这种升级机制既提升了 intset 的灵活性（可以存放不同类型整数），又节约了内存（按需分配），但升级是不可逆的。

ZSet（有序集合）

ZSet 有序集合对象的底层实现可以是 ziplist 或者 skiplist（跳跃表）。

当一个有序集合的元素数量较多，或者成员是较长的字符串时，Redis 就会使用 skiplist 作为底层实现。

typedef struct zskiplist {
     // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
 } zskiplist;

typedef struct zskiplistNode {
    // 成员对象
    robj *obj;
    // 分值（用于排序）
    double score;
     // 后退指针（用于从表尾向表头遍历）
    struct zskiplistNode *backward;
    // 层（Level数组）
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
         // 跨度（前进指针所指向节点与当前节点的距离/排名）
        unsigned int span;
    } level[];
} zskiplistNode;

其关键操作复杂度：

• zadd (zslInsert): 平均 O(log N)，最坏 O(N)
• zrem (zslDelete): 平均 O(log N)，最坏 O(N)
• zrank (zslGetRank): 平均 O(log N)，最坏 O(N)

skiplist 的查找时间复杂度是 O(log N)，可以与平衡二叉树媲美，但实现起来更为简单。跳跃表是一种有序数据结构，它通过在节点中维持多个指向其他节点的指针（即“层”），从而达到快速访问节点的目的。这种高效的数据结构选择，是 Redis 能够应对复杂排序和快速检索需求的关键，也是其在高并发场景下保持高性能的重要基石之一。理解这些底层实现，对于在 系统设计 中合理运用 Redis 至关重要。

总结

Redis 的快，绝非偶然。从本文对五种核心数据类型底层实现的深度剖析可以看出，其高性能的秘诀在于对 数据结构 的极致优化。每种数据类型都针对不同的使用场景，配备了最合适的底层结构（如 SDS、quicklist、hashtable、intset、skiplist），并在内存分配（jemalloc）、编码转换、渐进式 rehash 等细节上做了大量精妙的设计。这些设计共同作用，使得 Redis 在内存操作、时间复杂度、空间利用率和实现复杂度之间取得了绝佳的平衡。深入理解这些 数据结构 与算法，不仅能帮助我们更好地使用 Redis，也是提升后端开发与架构设计能力的关键一步。