暂无图片
暂无图片
1
暂无图片
暂无图片
暂无图片

一文理解Redis底层数据结构

全菜工程师小辉 2021-06-21
5793

Redis的5种常见数据结构:字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)。这些都是Redis对外暴露的数据结构,本文将介绍这些数据结构的底层数据结构的实现。

Redis底层数据结构有六种:

  • 简单动态字符串(SDS)

  • 列表

  • 字典

  • 整数集合

  • 跳跃表

  • 压缩列表

  • 快速列表

简单动态字符串(SDS)

SDS是"simple dynamic string"的缩写。Redis中所有场景中出现的字符串,基本都是由SDS来实现的。

使用场景:

  • 所有非数字的key。例如:set msg "hello world"
    中的key msg.

  • 字符串数据类型的值。例如:set msg "hello world"
    中的msg的值"hello wolrd"

  • 非字符串数据类型中的“字符串值”。例如:RPUSH fruits "apple" "banana" "cherry"
    中的"apple" "banana" "cherry"

SDS结构图:

  • len:记录当前已使用的字节数(不包括'\0'),获取SDS长度的复杂度为O(1)(C 语言中获取字符串长度的时间复杂度为 O(N))。此外,len值还避免了二进制安全与缓存区溢出的问题。

  • alloc:记录当前字节数组总共分配的字节数量(不包括'\0')。

  • flags:标记当前字节数组的属性,是sdshdr8还是sdshdr16等。

  • buf:字节数组,用于保存字符串,包括结尾空白字符'\0'。

// flags值定义(为了节约头部空间,在Redis3.2开始,增加flag字段。SDS由一种数据结构变成了5种数据结构,会根据SDS存储的内容长度来选择不同的结构,以达到节省内存的效果)
#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

注:

  1. 二进制安全:通俗的讲,C语言中,用“\0”表示字符串的结束,如果字符串本身就有“\0”字符,字符串就会被截断,即非二进制安全;若通过某种机制,保证读写字符串时不损害其内容,这就是二进制安全。

  2. 因为C字符串不记录自身的长度,所以strcat会假定用户在执行这个函数时,已经为dest分配足够多的内存了,可以容纳src字符串中的所有内容,而一旦这个假设不成立,就会产生缓存区溢出。

频繁内存分配问题处理

每次增长或者缩短一个字符,程序都需要对保存这个字符串的数组进行一次内存重新分配操作。因为内存重分配涉及复杂的算法,并且可能需要执行系统调用,所以它通常是一个比较耗时的操作。

为了避免C字符串的这种缺陷,SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。通过未使用空间,SDS实现了空间预分配和惰性空间释放两种优化策略。

  1. 空间预分配

空间预分配用于优化SDS的字符串增长操作。当SDS的API对一个SDS进行修改,并且需要对SDS进行空间扩展的时候,程序不仅会为SDS分配修改所必须要的空间,还会为SDS分配额外的未使用空间。其中,额外分配的未使用空间数量由以下公式决定:

  • 如果对SDS进行修改之后,SDS的长度将小于1MB,那么程序分配和len属性同样大小的未使用空间。

  • 如果对SDS进行修改之后,SDS的长度将大于等于1MB,那么程序会分配1MB的未使用空间。

在扩展SDS空间之前,SDS API会先检查未使用空间是否足够,如果足够的话,API就会直接使用未使用空间,而无需执行内存重分配。通过空间预分配策略,Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

  1. 惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作。当SDS的API需要缩短SDS保存的字符串时,程序不会立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录下来,并等待将来使用。

通过惰性空间释放策略,SDS避免了缩短字符串时所需的内存重分配操作,并为将来可能的增长操作提供了优化。

与此同时,SDS也提供了响应的API可以在有需要时,真正的释放SDS里面的未使用空间,所以不用担心惰性空间释放策略会造成内存浪费。

列表

列表在Redis中应用的非常广,列表的底层实现就是链表。此外,Redis的发布与订阅、慢查询、监视器等功能也用到了链表。

列表特点:

  • 双端链表:带有指向前置节点和后置节点的指针,获取这两个节点的复杂度为O(1)。

  • 无环:表头节点的prev和表尾节点的next都指向NULL,对链表的访问以NULL结束。

  • 链表长度计数器:带有len属性,获取链表长度的复杂度为O(1)。

  • 多态:链表节点使用 void*指针保存节点值,可以保存不同类型的值。

列表结构图:

列表的数据结构(adlist.h/listNode与adlist.h/list):

listNode:

  • prev:前置节点。

  • next:后置节点。

  • value:节点值。

list:

  • head:链表头节点。

  • tail:链表尾节点。

  • len:链表所包含的节点数量。

  • dup:函数,用于复制ptr值,实现深度复制。

  • free:函数,用于释放对应类型结构的内存。

  • match:函数,用于对比链表节点所保存的值和另一个输入值是否相等。

字典

字典,又称为符号表(symbol table)、关联数组(associative array)或映射(map),是一种用于保存键值对的抽象数据结构。字典中的每一个键都是唯一的,可以通过键查找与之关联的值,并对其修改或删除。

Redis的键值对存储就是用字典实现的,散列(Hash)的底层实现之一也是字典。

字典的结构图(与JDk中的HashMap结构很相似):

字典的数据结构(dict.h/dictht与dict.h/dict):

dict:

  • type:针对不同类型的键值对,用于创建多类型的字典

  • privdata:针对不同类型的键值对,用于创建多类型的字典

  • ht:两个元素的数组,包含两个dictht哈希表,一般字典只使用ht[0]哈希表,ht[1]哈希表会在对ht[0]哈希表进行rehash(重哈希)的时候使用,即当哈希表的键值对数量超过负载数量过多的时候,会将键值对迁移到ht[1]上

  • rehashidx:rehashidx也是跟rehash相关的,rehash的操作不是瞬间完成的,rehashidx记录着rehash的进度,图中没有进行rehash,它的值为-1

dictht:

  • table:哈希链表(包含了一个节点类型为dictEntry的链表)

  • size:哈希链表大小

  • sizemask:哈希链表大小掩码,用于计算索引值,等于size-1

  • used:哈希链表已有节点的数量

dictEntry:

  • key:键

  • next:下一个dictEntry节点

  • value:union类型,支持不同类型的值

渐进式hash

字典类型容量变化过程叫做rehash。需要满足一定的条件才能触发扩容机制:

  1. 服务器当前没有进行BGWRITEAOF或者BGSAVE命令,且当前键值对个数超过一维数组的大小,才会触发扩容。

  2. 如果当前键值对个数超过一维数组大小的五倍,无论是否在进行BGWRITEAOF或者BGSAVE命令,都会强制扩容。

  3. 如果当前键值对个数少于一维数组大小的十分之一,则触发缩容过程。缩容不会考虑当前服务器是否在进行BGWRITEAOF或者BGSAVE命令。

渐进式hash的过程,简单来说类似数据库的迁移,读的时候先读ht[0],读不到读ht[1];写的时候只写ht[1];ht[0]数据慢慢地往ht[1]上搬。

当ht[0]的所有键值都迁至ht[1]之后,ht[0]变为空表,释放ht[0]。并将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,将rehashidx属性的值设为-1,表示rehash操作已完成。

具体步骤如下:

  1. 为字典的备用哈希表分配空间:如果执行的是扩展操作,那么备用哈希表的大小为第一个大于等于(已用节点个数)*2的2n(2的n次方幂) 如果执行的是收缩操作,那么备用哈希表的大小为第一个大于等于(已用节点个数)的2n

  2. 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始(为-1时表示没有进行rehash)。

  3. rehash进行期间,每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当一次rehash工作完成之后,程序将rehashidx属性的值+1。同时在serverCron中调用rehash相关函数,在1ms的时间内,进行rehash处理,每次仅处理少量的转移任务(100个元素)。随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作已完成。

这里比较下Redis的渐进hash与JDk中HashMap的resize过程。如果对HashMap不了解,可以查看《详解并发下的HashMap以及JDK8的优化》。

整数集合

整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,可以保存类型为int16_t、int32_t、int64_t的整数值,并且保证集合中不会出现重复元素 整数集合是集合(Set)的底层实现之一,如果一个集合只包含整数值元素,且元素数量不多时,会使用整数集合作为底层实现

整数集合的结构图:

整数集合的数据结构(inset.h/inset):

intset:

  • encoding:决定contents数组的真正类型,如INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64。

  • length:记录整数集合的元素数量,即contents数组长度

  • contents:整数集合的每个元素在数组中按值的大小从小到大排序,且不包含重复项。

整数集合的升级

当想要添加一个新元素到整数集合中时,并且新元素的类型比整数集合现有的所有元素的类型都要长,整数集合需要先进行升级,才能将新元素添加到整数集合里面。每次想整数集合中添加新元素都有可能会引起升级,每次升级都需要对底层数组已有的所有元素进行类型转换。

升级添加新元素:

  • 根据新元素类型,扩展整数集合底层数组的空间大小,并为新元素分配空间。

  • 把数组现有的元素都转换成新元素的类型,并将转换后的元素放到正确的位置,且要保持数组的有序性。

  • 添加新元素到底层数组。

整数集合的升级策略可以提升整数集合的灵活性,并尽可能的节约内存。另外,整数集合不支持降级,一旦升级,编码就会一直保持升级后的状态。

跳跃表

一个普通的单链表查询一个元素的时间复杂度为O(N),即便该单链表是有序的。使用跳跃表(SkipList)是来解决查找问题的,它是一种有序的数据结构,不属于平衡树结构,也不属于Hash结构,它通过在每个节点维持多个指向其他节点的指针,而达到快速访问节点的目的 跳跃表是有序集合(Sorted Set)的底层实现之一,如果有序集合包含的元素比较多,或者元素的成员是比较长的字符串时,Redis会使用跳跃表做有序集合的底层实现。

跳跃表其实可以把它理解为多层的链表,它有如下的性质:

  • 多层的结构组成,每层是一个有序的链表

  • 最底层(level 1)的链表包含所有的元素

  • 跳跃表的查找次数近似于层数,时间复杂度为O(logn),插入、删除也为 O(logn)

  • 跳跃表是一种随机化的数据结构(通过抛硬币来决定层数)

有关跳跃表的讲解,可以查看《有关跳跃表的干货都在这里

跳跃表的结构图:

  • 每个跳跃表节点的层数在1-32之间

  • 一个跳跃表中,节点按照分值大小排序,多个节点的分值是可以相同的,相同时,节点按成员对象大小排序

  • 每个节点的成员变量必须是唯一的

压缩列表

压缩列表(ziplist)是为了节约内存而设计的,是由一系列特殊编码的连续内存块组成的顺序性(sequential)数据结构,一个压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者一个整数值。

压缩列表是列表(List)和散列(Hash)的底层实现之一,一个列表只包含少量列表项,并且每个列表项是小整数值或比较短的字符串,会使用压缩列表作为底层实现(在3.2版本之后是使用quicklist实现)。

压缩列表的结构图:

一个压缩列表可以包含多个节点(entry),每个节点可以保存一个字节数组或者一个整数值。

压缩列表的数据结构:

  • zlbytes:记录整个压缩列表占用的内存字节数,在压缩列表内存重分配,或者计算zlend的位置时使用。

  • zltail:记录压缩列表表尾节点距离压缩列表的起始地址有多少字节,通过该偏移量,可以不用遍历整个压缩列表就可以确定表尾节点的地址。

  • zllen:记录压缩列表包含的节点数量,但该属性值小于UINT16_MAX(65535)时,该值就是压缩列表的节点数量,否则需要遍历整个压缩列表才能计算出真实的节点数量。

  • entryX:压缩列表的节点。

  • zlend:特殊值0xFF(十进制255),用于标记压缩列表的末端。

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数字或者一个整数值。压缩列表节点的数据结构:

  • previous_entry_ength:记录压缩列表前一个字节的长度。

  • encoding:节点的encoding保存的是节点的content的内容类型。

  • content:content区域用于保存节点的内容,节点内容类型和长度由encoding决定。

快速列表

考虑到链表的附加空间相对太高,prev和next指针就要占去16个字节(64bit系统的指针是8个字节)。另外每个节点的内存都是单独分配,会加剧内存的碎片化,影响内存管理效率。因此Redis3.2版本开始对列表数据结构进行了改造,使用快速列表(quicklist)代替了压缩列表和列表。

快速列表的结构图:

快速列表的数据结构:

quicklistNode:

  • prev: 指向链表前一个节点的指针。

  • next: 指向链表后一个节点的指针。

  • zl: 数据指针。如果当前节点的数据没有压缩,那么它指向一个ziplist结构;否则,它指向一个quicklistLZF结构。

  • sz: 表示zl指向的ziplist的总大小(包括zlbytes, zltail, zllen, zlend和各个数据项)。需要注意的是:如果ziplist被压缩了,那么这个sz的值仍然是压缩前的ziplist大小。

  • count: 表示ziplist里面包含的数据项个数。这个字段只有16bit。稍后我们会一起计算一下这16bit是否够用。

  • encoding: 表示ziplist是否压缩了(以及用了哪个压缩算法)。目前只有两种取值:2表示被压缩了(而且用的是LZF压缩算法),1表示没有压缩。

  • container: 是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据,还是使用ziplist存数据,或者用其它的结构来存数据(用作一个数据容器,所以叫container)。但是,在目前的实现中,这个值是一个固定的值2,表示使用ziplist作为数据容器。

  • recompress: 当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时,需要把数据暂时解压,这时就设置recompress=1做一个标记,等有机会再把数据重新压缩。

  • attempted_compress: 这个值只对Redis的自动化测试程序有用。

  • extra: 其它扩展字段。

quickList:

  • head: 指向头节点(左侧第一个节点)的指针。

  • tail: 指向尾节点(右侧第一个节点)的指针。

  • count: 所有ziplist数据项的个数总和。

  • len: quicklist节点的个数。

  • fill: 16bit,ziplist大小设置,存放list-max-ziplist-size参数的值。

  • compress: 16bit,节点压缩深度设置,存放list-compress-depth参数的值。

压缩深度

quicklist默认的压缩深度是0,也就是不压缩。压缩的实际深度由配置参数list-compress-depth
决定。为了支持快速的push/pop操作,quicklist的首尾两个ziplist不压缩,此时深度就是1;如果深度为2,就表示quicklist的首尾第一个 ziplist以及首尾第二个ziplist都不压缩。

zipList长度

quicklist 内部默认单个ziplist长度为8k字节,超出了这个字节数,就会新起一个ziplist。ziplist的长度由配置参数list-max-ziplist-size
决定。

编码

上面介绍了Redis的主要底层数据结构,包括简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表。但是Redis并没有直接使用这些数据结构来构建数据库,而是基于这些数据结构创建不同的编码,然后由不同条件下的不同编码来实现Redis的这些数据类型:字符串(String)、列表(List)、散列(Hash)、集合(Set)、有序集合(Sorted Set)。

接下来就介绍Redis五种数据结构对应的编码。

字符串对象的编码

上面介绍了SDS,但这只是字符串对象的其中一种实现。字符串对象的编码可能有三种:int、raw、embstr。

  1. int
    如果一个字符串对象,保存的值是一个整数值,并且这个整数值在long的范围内,那么Redis用整数值来保存这个信息,并且将字符串编码设置为 int。

  2. raw
    如果字符串对象保存的是一个字符串, 并且长度大于32个字节,它就会使用前面讲过的SDS(简单动态字符串)数据结构来保存这个字符串值,并且将字符串对象的编码设置为raw。

  3. embstr
    如果字符串对象保存的是一个字符串,但是长度小于32个字节,它就会使用embstr来保存了,embstr编码不是一个数据结构,而是对SDS的一个小优化,当使用SDS 的时候,程序需要调用两次内存分配,来给字符串对象和SDS各自分配一块空间,而embstr只需要一次内存分配,因为他需要的空间很少,所以采用连续的空间保存,即将SDS的值和字符串对象的值放在一块连续的内存空间上。这样能在短字符串的时候提高一些效率。

浮点数如何保存:

Redis的字符串数据类型是支持保存浮点数,并且支持对浮点数进行加减操作,但是Redis在底层是把浮点数转换成字符串值,然后按照上述编码规则。对浮点数进行操作时,也是从字符串转换成浮点数进行计算,然后再转换成字符串进行保存的。

编码转换条件:

如果对一个int编码的字符串对象,修改它成非整数值,则对象就会使用raw编码。而Redis没有为embstr编码提供任何的修改操作,embstr编码的值是只读的,只要发生修改,立刻将编码转换成raw。

编码使用条件
int可以用long保存的整数
raw长度大于32的字符串
embstr字符串长度小于32字节(或者浮点数转换后满足)

列表对象的编码

在 Redis 3.2 版本之前,列表对象底层由 压缩列表和双向链表配合实现,当元素数量较少的时候,使用压缩列表,当元素数量增多,就开始使用普通的双向链表保存数据。

但是这种实现方式不够好,双向链表中的每个节点,都需要保存前后指针,这个内存的使用量 对于Redis这个内存数据库来说极其不友好。

因此在 3.2 之后的版本,Redis新实现了一个数据结构,叫做快速列表(quicklist)。所有列表的底层实现都是这个数据结构了。它的底层实现基本上就是将 双向链表和压缩列表进行了结合,用双向的指针将压缩列表进行连接,这样不仅避免了压缩列表存储大量元素的性能压力,同时避免了双向链表连接指针占用空间过多的问题。

编码使用条件
quicklist

集合对象的编码

集合对象的编码可以是intset或者hashtable。

当集合中的所有元素都是整数,且元素的数量不大于512个的时候,使用intset编码。

当元素不符合全部为整数值且元素个数小于512时,集合对象使用的编码方式为 hashtable。

编码使用条件
intset所有元素都是整数且元素个数小于 512
hashtable其他数据

有序集合对象的编码

有序集合对象的编码可以是ziplist以及skiplist。

当使用ziplist编码时,有序集合对象的实现数据结构为压缩列表。当条件变化,ziplist编码会转换成skiplist编码。

当使用skiplist编码的时候,内部使用zset 来实现数据的保存,zset的定义如下:

typedef struct zset{
zskiplist *zsl;
dict *dict;
}zset;

为什么需要同时使用跳跃表以及字典呢?

  • 当只使用字典来实现,可以以O(1)的时间复杂度获取成员的分值,但是由于字典是无序的,当需要进行范围性操作的时候,需要对字典中的所有元素进行排序,这个时间复杂度至少需要 O(nlogn)。

  • 当只使用跳跃表来实现,可以在O(logn)的时间进行范围排序操作,但是如果要获取到某个元素的分值,时间复杂度也是O(logn)。

因此,将字典和跳跃表结合进行使用,可以在O(1)的时间复杂度下完成查询分值操作,而对一些范围操作使用跳跃表可以达到O(logn)的时间复杂度。

编码使用条件
ziplist元素数量少于128且所有元素成员的长度小于64字节
skiplist不满足上述条件的其他情况

散列对象

散列对象的编码可以是ziplist或者hashtable.

ziplist编码下的哈希对象,使用了压缩列表作为底层实现数据结构,用两个连续的压缩列表节点来表示哈希对象中的一个键值对。实现方式类似于上面的有序集合的场景。

哈希结构本身在结构上和字典颇为相似,因此哈希对象中的每一个键值对都是字典中的一个键值对。

  • 字典的每一个键都是一个字符串对象,对象中保存了键值对的键。

  • 字典的每一个值都是一个字符串对象,对象中保存了键值对的值。

编码使用条件
ziplist键值对的键和值的长度都小于64字节,且键值对个数小于512
hastable不满足上述条件的其他情况

总结

基础数据类型可能的编码方式
字符串int, raw, embstr
列表之前是 ziplist, linkedlist。3.2开始都是quicklist
集合intset, hashtable
有序集合ziplist, skiplist
散列ziplist, hashtable

参考文档:

  1. 《Redis设计与实现》

  2. https://github.com/redis/redis

  3. 《Redis 深度历险:核心原理和应用实践》


文章转载自全菜工程师小辉,如果涉嫌侵权,请发送邮件至:contact@modb.pro进行举报,并提供相关证据,一经查实,墨天轮将立刻删除相关内容。

评论