Redis数据结构

发表于2019-04-04更新于2022-05-03阅读次数

简介

Redis常用的类型主要是 String、List、Hash、Set、ZSet 这5种。因为基于内存的缘故，所以为了平衡时间与空间的使用效率在元素数量较多或较少时采用不同的策略。
redis类型

Redis在互联网公司一般有以下应用:

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

Redis各数据结构概览

  • dict：字典
  • dictht：就是一个hashtable，以o(1)时间复杂度获取size，used当前数组里面用掉了多少空间
  • dictEntry：数组里面的元素，**table指针指向数组，redis中所有的key都是存在dictEntry中
  • *val：存储key对应的值，也是一个指针，指向redisObject结构进行数据存储，这个指针指向真实的数据存储
  • next：当key发生hash冲突时(比如都是数组0)，通过next指针建立一个单向的链表解决hash冲突

robj字段介绍：

  • type：对外的数据类型，string，list，hash，set，zset等
  • encoding：内部编码，raw，int，ziplist等，对内存利用率极致追求
  • LRU_BITS：内存淘汰策略
  • refcount：redis内存管理需要
  • *ptr：指向真实的数据存储结构，ziplist等，最终指向数据编码的对象

Redis的对象redisObject

对于每一个键，都会有一个结构去存储它的数据类型，当我们执行set hello world命令时，会有以下数据模型：
redisObject

  • dictEntry：Redis给每个key-value键值对分配一个dictEntry，里面有着key和val的指针，next指向下一个dictEntry形成链表，这个指针可以将多个哈希值相同的键值对链接在一起，由此来解决哈希冲突问题(链地址法)。

  • sds：键key“hello”是以SDS（简单动态字符串）存储。

  • redisObject：值val“world”存储在redisObject中。实际上，redis常用5种类型都是以redisObject来存储的；而redisObject中的type字段指明了Value对象的类型，ptr字段则指向对象所在的地址。

redisObject对象非常重要，Redis对象的类型、内部编码、内存回收、共享对象等功能，都需要redisObject支持。这样设计的好处是，可以针对不同的使用场景，对5种常用类型设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。

无论是dictEntry对象，还是redisObject、SDS对象，都需要内存分配器（如jemalloc）分配内存进行存储。jemalloc作为Redis的默认内存分配器，在减小内存碎片方面做的相对比较好。比如jemalloc在64位系统中，将内存空间划分为小、大、巨大三个范围；每个范围内又划分了许多小的内存块单位；当Redis存储数据时，会选择大小最合适的内存块进行存储。

redis数据结构与内部编码关系

Redis每个value对象由一个redisObject结构表示，它的ptr指针指向底层实现的数据结构，而数据结构由encoding属性决定。

String

字符串对象的底层实现可以是int、raw、embstr。embstr编码是通过调用一次内存分配函数来分配一块连续的空间，而raw需要调用两次。

  • 如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型表示，那么字符串对象将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long），并将字符串对象的编码方式设置为int
  • 如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值
  • 如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串保存这个值，并将对象的编码设置为raw

简单动态字符串（SDS）

简单动态字符串（SDS），这种结构更像C++的String或者Java的ArrayList，长度动态可变：

1
2
3
4
5
6
7
8
9
10
11
12
13
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特性

常数复杂度获取字符串长度：因为SDS在len属性中记录了长度，所以获取一个SDS长度时间复杂度仅为O(1)。

预空间分配：如果对一个SDS进行修改，分为一下两种情况：

1、SDS长度（len的值）小于1MB，那么程序将分配和len属性同样大小的未使用空间，这时free和len属性值相同。举个例子，SDS的len将变成15字节，则程序也会分配15字节的未使用空间，SDS的buf数组的实际长度变成15+15+1=31字节（额外一个字节用户保存空字符）。

2、SDS长度（len的值）大于等于1MB，程序会分配1MB的未使用空间。比如进行修改之后，SDS的len变成30MB，那么它的实际长度是30MB+1MB+1byte。

杜绝缓冲区溢出：使用C字符串的操作时，如果字符串长度增加（如strcat操作）而忘记重新分配内存，很容易造成缓冲区的溢出；而SDS由于记录了长度，相应的操作在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。

Redis 3.2后SDS特性

Redis 3.2后使用了sdshdr8数据结构

1
2
3
4
5
6
struct sdshdr8 {
	    uint8_t_len; /*used*/ 
        uint8_t_alloc; /*excluding the header and null terminator*/ 
        unsigned char flags; /*3 lsb of type, 5 unused bits */ 
        char buf[];
}


type定义的0，1，2表示type占用的bit位，可以减少空间占用

embstr

比如当执行SET key foobar时，在64位linux系统下，存储键值需要占用的空间是sizeof(redisObject)+sizeof(sdshdr8)+strlen("foobar")=16字节+4字节+6字节=26字节。存储结构如下:


在linux操作系统，cpu缓存行大小占64byte，而sizeof(redisObject)+sizeof(sdshdr8)正好占用20个字节，所以当业务数据大小在64-20=44字节之内的话，可以利用cpu缓存行特性。linux分配内存的时候，就会挨着redisObject进行分配，开辟一块连续的空间存储，利用cpu的缓存行一次读取到数据，减少申请释放内存次数，减少内存IO，这样数据整合就在cpu缓存行范围内，这样在进行数据读取的时候，cpu第一次寻址到val，通过val找到redisObject，通过redisObject我们可以直接拿到值，而不用通过指针再一次寻址去拿数据，这就是embstr做的事情。

raw

raw类型是和redisObject不在一块连续的内存空间，如下：

当字符串长度大于44时就变成了raw，就不适用cpu缓存行优化的方式了

int

当键值内容可以用一个64位有符号整数表示时，Redis会将键值转换成long类型来存储。如SET key 123456，实际占用的空间是sizeof(redisObject)=16字节，比存储”foobar”节省了 一半的存储空间，如下所示：

redisObject中的refcount字段存储的是该键值被引用数量，即一个键值可以被多个键引用。Redis启动后会预先建立10000个redisObject类型变量作为共享对象，分别存储从0到9999。如果要设置的字符串键值在这10000个数字内，如SET key1 123，则可以直接引用共享对象而不用再建立一个redisObject了，也就是说存储键值占用的空间是0字节。

由此可见，使用字符串类型键存储对象ID这种小数字是非常节省存储空间的，Redis只需存储键名和一个对共享对象的引用即可。 虽然整形底层存储encoding是int类型，但是在获取长度计算时会转换为字符串计算长度。

注意：当通过配置文件参数maxmemory设置了Redis可用的最大空间大小时，Redis不会使用共享对象，因为对于每一个键值都需要使用一个redisObject来记录其LRU信息。

字符串扩容

  • 当字符串大小小于1M时，每次扩容一倍
  • 大于1M时，每次增加1M，比如现在5M，扩容后就是6M

List

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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: listAddNodeHead —O(1)

  • lpush: listAddNodeTail —O(1)

  • push:listInsertNode —O(1)

  • index : listIndex —O(N)

  • pop:ListFirst/listLast —O(1)

  • llen:listLength —O(N)

linkedlist（双端链表）

List

从图中可以看出Redis的linkedlist双端链表有以下特性：节点带有prev、next指针、head指针和tail指针，获取前置节点、后置节点、表头节点和表尾节点的复杂度都是O（1）。len属性获取节点数量也为O（1）。

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

ziplist（压缩列表）

当一个列表键只包含少量列表项，且是小整数值或长度比较短的字符串时，那么redis就使用ziplist（压缩列表）来做列表键的底层实现。

ziplist是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块(而不是像双端链表一样每个节点是指针)组成的顺序型数据结构

ziplist数据结构说明：

  • zlbytes:32bit表示ziplist占用的字节总数

  • zltail:32bit表示ziplist表中最后一项entry在ziplist中的偏移字节数。通过zltail我们可以很方便地找到最后一项，从而可以在ziplist尾端快速地执行push或pop操作

  • zlen:16bit表示ziplist中数据项entry的个数

  • entry：表示真正存放数据的数据项，长度不定

  • zlend：ziplist最后一个字节，是一个结束标记，值固定等于255

  • prerawlen：前一个entry的数据长度

  • len：entry中数据的长度

  • data：真实数据存储

根据len字段的第一个字节分的9种情况：

  • 00xxxxxx：len字段前2个高位 bit为0，剩余的6个bit用来表示长度，即最大长度可以到2^6 - 1

  • 01xxxxxx xxxxxxxx：len字段的前2个高位是01，则len字段占2个byte，共有14个bit表示，数据长度最多2^14 - 1

  • 10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx：len字段前2个高位bit是10，则len字段占5个byte，共有32个bit表示，数据长度最多2^32 - 1，第一个字节的剩余6个bit舍弃不用

  • 11000000：len字段前2个高位bit是11，值为OXC0，则len字段占1个byte，后面的data为2字节的int16_t类型

  • 11010000：len字段前4个高位bit是1101，值为OXD0，则len字段占1个byte，后面的data为4字节的int32_t类型

  • 11100000：len字段前4个高位bit是1110，值为OXE0，则len字段占1个byte，后面的data为8字节的int64_t类型

  • 11110000：len字段前4个高位bit是1111，值为OXF0，则len字段占1个byte，后面的data为3字节的整数

  • 11111110：len字段前7个高位bit是1111111，值为OXFE，则len字段占1个byte，后面的data为1字节的整数

  • 1111xxxx：len字段前4个字节是1111，后4个bit的范围是(0001-1101)，这时xxxx从1到13，一共13个值，这时就用这13个值来表示data的数据，真正的数值大小为对应的bit位数值-1，代表真实的业务数据

ziplist是非常紧凑的一种数据类型，为了节省内存空间。而非常紧凑的数据结构的缺点是：

  • 空间必须是连续的

  • 数据量非常大的时候往里面加元素，数据迁移很麻烦

  • 频繁的内存分配与释放是不划算的，所以redis针对这个问题进行了优化

quicklist

在新版本中list链表使用 quicklist 代替了 ziplist和 linkedlist，quickList 是 zipList 和 linkedList 的混合体。它将 linkedList 按段切分，每一段使用 zipList 来紧凑存储，多个 zipList 之间使用双向指针串接起来。因为链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。


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

在配置文件中可以设置每个ziplist的最大容量和quickList的数据压缩范围，提升数据存取效率。

1
2
list-max-ziplist-size -2 
list-compress-depth 0
  • 0默认不压缩
  • 1表示不压缩头尾节点，压缩中间数据
  • 2表示头尾节点和头尾相邻的一个节点不压缩，压缩初次之外中间的

注意：列表类型实现阻塞队列使用的是redisDb结构中的字段blocking_keys，维护的是key与客户端的关系，不会阻塞redis进程

Hash

Hash对象的底层实现可以是ziplist（压缩列表）或者hashtable（字典或者也叫哈希表）。
Hash对象只有同时满足下面两个条件时，才会使用ziplist（压缩列表）：1、哈希中元素数量小于512个；2、哈希中所有键值对的键和值字符串长度都小于64字节。

ziplist结构

ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入压缩列表表尾。因此保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后。牺牲了部分读取性能以换取极高的空间利用率，适合在元素较少时使用。该编码类型同样还在List类型和zSet类型中使用。

  • zlbytes是uint32_t类型， 表示整个结构占用的空间
  • zltail也是uint32_t类型，表示到最后一个元素的偏移，记录zltail使得程序可以直接定位到尾部元素而无需遍历整个结构，执行从尾部弹出(对列表类型而言)等操作时速度更快
  • zllen是uint16_t类型，存储的是元素的数量
  • zlend是一个单字节标识，标记结构的末尾，值永远是255

散列类型的ziplist数据结构如下图所示：

在REDIS_ENCODING_ZIPLIST中每个元素由4个部分组成：

第一个部分用来存储前一个元素的大小以实现倒序查找，当前一个元素的大小小于254字节时第一个部分占用1个字节，否则会占用5个字节

第二、三个部分分别是元素的编码类型和元素的大小

  • 当元素的大小<=63个字节时，元素的编码类型是ZIP_STR_06B(即0＜＜6)，同时第三个部分用6个二进制位来记录元素的长度，所以第二、三个部分总占用空间是1字节
  • 当元素的大小>63 && <=16383字节时，第二、三个部分总占用空间是2字节
  • 当元素的大小>16383字节时，第二、三个部分总占用空间是5字节

第四个部分是元素的实际内容，如果元素可以转换成数字的话Redis会使用相应的数字类型来存储以节省空间，并用第二、三个部分来表示数字的类型(int16_t、int32_t等)

使用REDIS_ENCODING_ZIPLIST编码存储散列类型时元素的排列方式是：元素1存储字段1，元素2存储字段1的值，依次类推。例如，当执行命令HSET hkey foo bar命令后，hkey键值的内存结构如下所示：

下次需要执行HSET hkey foo anothervalue时，Redis需要从头开始找到值为foo的元素(查找 时每次都会跳过一个元素以保证只查找字段名)，找到后删除其下一个元素，并将新值anothervalue插入。删除和插入都需要移动后面的内存数据，而且查找操作也需要遍历才能完成，可想而知当散列键中数据多时性能将很低，所以不宜将hash-max-ziplist-entries和hash-max- ziplist-value两个参数设置得很大。

hashtable结构

hashtable哈希表可以实现O(1)复杂度的读写操作，因此效率很高。

Redis也使用链地址法来解决键冲突。即每个哈希表节点都有一个next指针，多个哈希表节点用next指针构成一个单项链表，链地址法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位。

Redis中的字典使用hashtable作为底层实现的话，每个字典会带有两个哈希表，一个平时使用，另一个仅在rehash（重新散列）时使用。随着对哈希表的操作，键会逐渐增多或减少。为了让哈希表的负载因子维持在一个合理范围内，Redis会对哈希表的大小进行扩展或收缩（rehash），也就是将ht【0】里面所有的键值对分多次、渐进式的rehash到ht【1】里。

hashtable其字段和字段值都是使用redisObject存储的，所以前面讲到的字符串类型键值的优化方法同样适用于散列类型键的字段和字段值。
注意：Redis的键值对存储也是通过散列表实现的，与REDIS_ENCODING_HT编码方式类似，但键名并非使用redisObject存储，所以键名”123456”并不会比”abcdef”占用更少的空间。之所以不对键名进行优化是因为绝大多数情况下键名都不会是纯数字。

Redis支持多数据库，每个数据库中的数据都是通过结构体redisDb存储的。redisDb的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct redisDb 
{
	dict * dict;
	/** The keyspace for this DB */
	dict * expires;
	/** Timeout of keys with a timeout set */
	dict * blocking_keys;
	/** Keys with clients waiting for data (BLPOP) */
	dict * ready_keys;
	/** Blocked keys that received a PUSH */
	dict * watched_keys;
	/** WATCHED keys for MULTI/EXEC CAS */
	int id;
}
redisDb;
  • dict类型就是散列表结构
  • expires存储的是过期时间的散列表结构
    当Redis启动时会根据配置文件中databases参数指定的数量创建若干个redisDb类型变量存储不同数据库中的数据。

Set

Set集合对象的底层实现可以是intset（整数集合）或者hashtable（字典或者也叫哈希表）。
intset数据结构如下：

1
2
3
4
5
6
7
typedef struct intset 
{
	uint32_t encoding;
	uint32_t length;
	int8_t contents[];
}
intset;


其中contents存储的就是集合中的元素值，根据encoding的不同，每个元素占用的字节大小不同。
默认的encoding是INTSET_ENC_INT16(即2个字节)，当新增加的整数元素无法使用2个字节表示时，Redis会将该集合的encoding升级为INTSET_ENC_INT32(即4个字节)并调整之前所有元素的位置和长度，同样集合的encoding还可升级为INTSET_ENC_INT64(即8个字节)。 并且contents[]内存储的整数元素是顺序存储的。

REDIS_ENCODING_INTSET编码以有序的方式存储元素(所以使用SMEMBERS命令获得的结果是有序的)，使得可以使用二分算法查找元素。但是无论是添加还是删除元素，Redis都需要调整后面元素的内存位置，所以当集合中的元素太多时性能较差。当新增加的元素不是整数或集合中的元素数量超过了set-max-intset-entries参数指定值时，Redis会自动将该集合的存储结构转换成REDIS_ENCODING_HT。

intset底层实现为有序，无重复数组保存集合元素。 intset这个结构里的整数数组的类型可以是16位的，32位的，64位的。如果数组里所有的整数都是16位长度的，如果新加入一个32位的整数，那么整个16的数组将升级成一个32位的数组。升级可以提升intset的灵活性，又可以节约内存，但不可逆。

注意：当集合的存储结构转換成REDIS_ENCODING_HT后，即使将集合中的所有非整数元素删除，Redis也不会自动将存储结构转換回REDIS_ENCODING_INTSET。因为如果要支持自动回转，就意味着Redis在每次删除元素时都需要遍历集合中的键来判断是否可以转換回原来的编码，这会使得删除元素变成了时间复杂度为O(n)的操作。

hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象都包含一个集合元素，而字典的值则被全部设置为NULL。

同时满足两个条件使用intset，否则使用hashtable

  • 集合对象保存的所有值都是整数值
  • 集合对象保存的元素数量不超过512个

ZSet

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

ziplist编码

ziplist编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），第二个元素保存元素的分值（score），压缩列表内的集合元素按照分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则放置在靠近表尾的方向。

skiplist编码

skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。

  • *forward：前进指针
  • span：跨越元素，比如rank操作就是通过span跨越元素来计算的
  • 头结点不存储数据，起到索引的作用，中间和尾结点存储数据
  • L2找到了120，如果找150，下降一层，找到了200，则数据就在150就在120-200之间

其中包括允许跳跃列表中的元素(即分数)相同，还有为跳跃链表每个节点增加了指向前一个元素的指针以实现倒序查找。 采用此种编码方式时，元素值是使用redisObject存储的，所以可以使用字符串类型键值的优化方式优化元素值，而元素的分数是使用double类型存储的。 使用REDIS_ENCODING_ZIPLIST编码时有序集合存储的方式按照”元素1的值，元素1的分数，元素2的值，元素2的分数”这样的顺序排列，并且分数是有序的。

zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存一个集合元素：跳跃表即诶单的object属性保存了元素成员，而跳跃表节点的score属性则保存了元素的分值。通过跳跃表，程序可以对有序集合进行范围型操作，比如ZRANK、ZRANGE等命令就是基于跳跃表API来实现的。

zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过字典，程序可以用O（1）复杂度查找给定成员的分值，ZSCORE命令就是根据这一特性是实现的。

当一个有序集合的元素数量比较多或者成员是比较长的字符串时，Redis就使用skiplist（跳跃表）作为ZSet对象的底层实现。skiplist的查找时间复杂度是LogN，可以和平衡二叉树相当，但实现起来又比它简单。跳跃表(skiplist)是一种有序数据结构，它通过在某个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。