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

redis 底层数据结构

news 来源：原创 2025/5/9 19:16:00

概述

Redis 6 和 Redis 7 之间对比：

Redis6 和 Redis7 最大的区别就在于 Redis7 已经用 listpack 替代了 ziplist.

以下是基于 Redis 7基础分析。

RedisObject

Redis是⼀个<k,v>型的数据库，其中key通常都是string类型的字符串对象，⽽value在底层就统⼀是redisObject对象。Redis中的任意数据类型都会被封装为⼀个RedisObject，也叫做Redis对象， redisObject结构，实际上就是Redis内部抽象出来的⼀个封装所有底层数据结构的统⼀对象。这就类似于Java的⾯向对象的设计⽅式。

源码如下：

这⾥⾯⼏个核⼼字段意义如下：

type：Redis的上层数据类型。⽐如string,hash,set等，可以使⽤指令type key查看。

127.0.0.1:6379> set userid 1594
OK
127.0.0.1:6379> type userid
string

encoding： Redis内部的数据类型。可以使⽤指令 object encoding key查看。

127.0.0.1:6379> set userid 1594
OK
127.0.0.1:6379> object encoding userid
"int"

lru：当内存超限时会采⽤LRU算法清除内存中的对象。关于LRU与LFU，在redis.conf中有描述

# LRU means Least Recently Used

# LFU means Least Frequently Used

refcount：表示对象的引⽤次数。可以使⽤OBJECT REFCOUNT key 指令查看。
ptr：这是⼀个指针，指向真正底层的数据结构。encoding只是⼀个类型描述。实际数据是保存在ptr指向的具体结构⾥。

encoding 底层编码方式如下:

编码方式	说明
0BJ_ENCODING_RAW	raw编码动态字符串
OBJ_ENCODING_INT	long类型的整数的字符串
OBJ_ENCODING_HT	hash表(字典dict)
OBJ_ENCODING_ZIPMAP	已废弃
OBJ_ENCODING_LINKEDLIST	双端链表 (已废弃)
0BJ_ENCODING_ZIPLIST	压缩列表(7.0 已废弃)
OBJ_ENCODING_INTSET	整数集合
OBJ_ENCODING_SKIPLIST	跳表
0BJ_ENCODING_EMBSTR	embstr的动态字符串
0BJ_ENCODING_QUICKLIST	快速列表
0BJ_ENCODING_STREAM	Stream流
OBJ_ENCODING_LISTPACK	紧凑列表

String 数据结构

SDS

Redis 没有直接使⽤ C 语⾔中的字符串，因为 C 语⾔字符串存在很多问题：

获取字符串⻓度的需要通过运算
⾮⼆进制安全
不可修改

Redis 构建了⼀种新的字符串结构，称为简单动态字符串 (Simple Dynamic String)SDS 。

例如，我们执行命令：

127.0.0.1:6379> set name hi
OK

那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“hi”的SDS。

Redis是C语言实现的，其中SDS是一个结构体，源码如下：

例如，一个包含字符串“name”的sds结构如下：

1653984648404

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS：

1653984787383

假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：

如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；

如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

1653984822363

优点：

获取字符串长度的时间复杂度为O(1)
支持动态扩容
减少内存分配次数
二进制安全

String底层结构之int

如果存储的字符串是整数值，并且⼤⼩在LONG_MAX范围内，则会采⽤INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

String底层结构之embstr

如果存储的SDS⻓度⼩于44字节，则会采⽤EMBSTR编码，此时object head与SDS是⼀段连续空间。申请内存时只需要调⽤⼀次内存分配函数，效率更⾼。

String底层结构之Raw

基本编码⽅式是RAW基于简单动态字符串（ SDS）实现，存储上限为512mb。

Hash 数据结构

Hash 结构默认采⽤ listpack 编码，⽤以节省内存。

• 当数据量较⼤时， Hash 结构会转为 HT 编码，也就是 Dict ，触发条件有两个：

① listpack 中的元素数量超过了hash-max-listpack-entries （默认512 ）

② listpack 中的任意entry⼤⼩超过了hash-max-listpack-value （默认64 字节）

127.0.0.1:6379> config get has*
3) "hash-max-listpack-value"
4) "64"
7) "hash-max-listpack-entries"
8) "512"

Hash数据结构之 listpack

listpack(紧凑列表)可以理解为一个替代版本的ziplist，由于ziplist中有着致命的缺陷-连锁更新，在极端条件下会有着极差的性能，导致整个redis响应变慢。因此在redis5中引入了新的数据结构listpack，作为ziplist的替代版。listpack在6以后已经作为t_hash的基础底层结构。

listpack的整体结构如下：

和 ziplist 列表项类似，listpack 列表项也包含了元数据信息和数据本身。不过，为了避免 ziplist 引起的连锁更新问题，listpack 中的每个列表项不再像 ziplist 列表项那样，保存其前一个列表项的长度，它只会包含三个方面内容：

当前元素的编码类型（entry-encoding）
元素数据 (entry-content)
编码类型和元素数据这两部分的长度 (entry-length)

核⼼是entry中原本记录前⼀个entry的⻓度，现在改为记录⾃⼰的⻓度。这样，就不会再因为前⼀个entry变化⽽影响⾃⼰的⻓度。这样也就没有了连锁更新的问题。

Hash数据结构之 hashtable

在Redis中hashtable就是字典dict，Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）。

代码

结构图

当我们向 Dict 添加键值对时， Redis ⾸先根据 key 计算出 hash 值 (h ），然后利⽤ h& sizemask来计算元素应该存储到数组中的哪个索引位置。

Dict 中的 HashTable 就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过⻓，则效率会⼤⼤降低。

Dict 在每次新增键值对时都会检查负载因⼦（ LoadFactor =used/size ），满⾜以下两种情况时会触发哈希表扩容：

• 哈希表的 LoadFactor >= 1 ，并且服务器没有执⾏ SAVE 或 REWRITEAOF

等进程

• 哈希表的 LoadFactor>5 ；

Dict 除了扩容以外，每次删除元素时，也会对负载因⼦做检查，当 LoadFactor ＜ 0.1 时，会做哈希表收缩：

if个⼤于等于minimal的 2 n

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的 size 和 sizemask 变化，⽽ key 的查询与 sizemask 有关。因此必须对哈希表中的每⼀个 key 重新计算索引，插⼊新的哈希表，这个过程称为 rehash 。过程是这样的：

计算新hash表的realsize，即第⼀个⼤于等于dict.ht[0].used的2n
按照新的realsize申请内存空间，创建dictht，并赋值给dict.ht[1]
设置rehashidx= 0，标示开始rehash
将dict.ht[0]中的每⼀个dictEntry都rehash到dict.ht[1]每次执⾏新增、查询、修改、删除操作时，都检查⼀下dict.rehashidx是否⼤于 -1，如果是则将ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，井且将 rehashidx++。直⾄dict.ht[0]的所有数据都rehash到dict.ht[1]
将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表
将rehashidx赋值为-1，代表rehash结束
在rehash过程中，新增操作，则直接写⼊ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执⾏。这样可以确保h[0]的数据只减不增，随着 rehash最终为空

RedisObject

List 数据结构

List 结构默认采⽤ listpack 编码，⽤以节省内存。

• 当数据量较⼤时，List 结构会转为 quicklist，触发条件有1个：

list-max-listpack-size 每个 list 中包含的节点⼤⼩或个数。正数表示个数，负数 -1 到 -5 表示⼤⼩。

- 5：每个quicklist节点上的listpack大小不能超过64Kb（1kb=1024 bytes，即64*1024 bytes）
-4：每个quicklist节点上的listpack大小不能超过32Kb（1kb=1024 bytes，即32*1024 bytes）
-3：每个quicklist节点上的listpack大小不能超过16Kb（1kb=1024 bytes，即16*1024 bytes）
-2：默认值，每个quicklist节点上的listpack大小不能超过8Kb（1kb=1024 bytes，即8*1024 bytes）
-1：每个quicklist节点上的listpack大小不能超过4Kb（1kb=1024 bytes，即4*1024 bytes）

127.0.0.1:6379> config get lis*
3) "list-compress-depth"
4) "0"
5) "list-max-listpack-size"
6) "-2"

List 数据结构之 listpack

同Hash数据结构之 listpack 一样，参考上文。

List 数据结构之 quicklist

listpack 虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。但是我们要存储大量数据，超出了listpack最佳的上限，那怎么办？

Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个 listpack。我们就可以将数据存到多个 listpack中。

quicklistNode中间保存的数据结构。在Redis6以前是ziplist，到Redis7中改为了listpack。

总结：

QuickList的特点：

是一个节点为listpack的双端链表
节点采用listpack，解决了传统链表的内存占用问题
控制了listpack大小，解决连续内存空间申请效率问题
中间节点可以压缩，进一步节省了内存

Set 数据结构

如果set的数据都是不超过64位的数字(⼀个long数字).就使⽤intset存储 IntSet 。
如果set的数据不是数字，并且数据的数量没有大于128且数据⼤⼩小于64，就⽤listpack存储。
如果数据的数量大于128或数据⼤⼩小于64，就改为使⽤hashtable存储。

127.0.0.1:6379> config get set*
3) "set-max-listpack-value"
4) "64"
5) "set-max-listpack-entries"
6) "128"
7) "set-max-intset-entries"
8) "512"

Set 数据结构之 IntSet

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。
结构如下：

其中的encoding包含三种模式，表示存储的整数大小不同：

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

总结：

Intset可以看做是特殊的整数数组，具备一些特点：

Redis会确保Intset中的元素唯一、有序
具备类型升级机制，可以节省内存空间
底层采用二分查找方式来查询

Set 数据结构之 listpask

同Hash数据结构之 listpack 一样，参考上文。

Set 数据结构之 hashtable

同Hash数据结构之 hashtable一样，参考上文。

ZSet 数据结构

如果set 数据的数量没有大于128且数据⼤⼩小于64，就⽤listpack存储。
如果数据的数量大于128或数据⼤⼩小于64，就改为使⽤skiplist 存储。

127.0.0.1:6379> config get zset*
1) "zset-max-listpack-entries"
2) "128"
7) "zset-max-listpack-value"
8) "64"

ZSet 数据结构之 listpask

同Hash数据结构之 listpack 一样，参考上文。

ZSet 数据结构之 skiplist

zset类型的数据，底层需要先按照score进⾏排序。排序过程中是需要移动内存的。如果节

点数据不是太多，将这些内存移动完后，重新整理成⼀个类似数据Array的listpack结果是

可以接受的。但是如果数据量太⼤(节点数和数据⼤⼩)，那么频繁移动内存，开销就⽐较⼤

了。这时，显然以链表这种零散的数据结构是⽐较合适的。

但是，对于⼀个单链表结构来说，要检索链表中的某⼀个数据，只能从头到尾遍历链表。

时间复杂度是O(N)，性能是⽐较低的。

如何对链表结构进⾏优化呢？skiplist跳表就是⼀种思路。skiplist的优化思路是构建多层逐

级缩减的⼦索引，⽤更多的索引来提升搜索的性能。

skiplist是⼀种典型的⽤空间换时间的解决⽅案，优点是数据检索的性能⽐较⾼。时间复杂

度是O(logN)，空间复杂度是O(N)。但是他的缺点也很明显，就是更新链表时，维护索引

的成本相对更⾼。因此，skiplist适合那些数据量⽐较⼤，且是读多写少的应⽤场景。

概述

RedisObject

String 数据结构

SDS

String底层结构之int

String底层结构之embstr

String底层结构之Raw

Hash 数据结构

Hash数据结构之 listpack

Hash数据结构之 hashtable

List 数据结构

List 数据结构之 listpack

List 数据结构之 quicklist

Set 数据结构

Set 数据结构之 IntSet

Set 数据结构之 listpask

Set 数据结构之 hashtable

ZSet 数据结构

ZSet 数据结构之 listpask

ZSet 数据结构之 skiplist

相关文章：