Redis-Sorted-Set底层数据结构

Sortedset底层存储结构

sortedset同时会由两种数据结构支持,ziplist和skiplist.

只有同时满足如下条件是,使用的是ziplist,其他时候则是使用skiplist

  • 有序集合保存的元素数量小于128个
  • 有序集合保存的所有元素的长度小于64字节

当ziplist作为存储结构时候,每个集合元素使用两个紧挨在一起的压缩列表结点来保存,第一个节点保存元素的成员,第二个元素保存元素的分值.

当使用skiplist作为存储结构时,使用skiplist按序保存元素分值,使用dict来保存元素和分值的对应关系

1 跳跃表

跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。

在大部分情况下,跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡树要来得更为简单。

Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员(member)是比较长的字符串时,Redis就会使用跳跃表来作为有序集合键的底层实现。

Redis只在两个地方用到了跳跃表,一个是实现有序集合键,另一个是在集群节点中用作内部数据结构,除此之外,跳跃表在Redis里面没有其他用途。

Redis的配置文件中关于有序集合底层实现的两个配置。
1)zset-max-ziplist-entries 128:zset采用压缩列表时,元素个数最大值。默认值为128。
2)zset-max-ziplist-value 64:zset采用压缩列表时,每个元素的字符串长度最大值。默认值为64。
zset插入第一个元素时,会判断下面两种条件:

  • zset-max-ziplist-entries的值是否等于0;
  • zset-max-ziplist-value小于要插入元素的字符串长度。满足任一条件Redis就会采用跳跃表作为底层实现,否则采用压缩列表作为底层实现方式。

一般情况下,不会将zset-max-ziplist-entries配置成0,元素的字符串长度也不会太长,所以在创建有序集合时,默认使用压缩列表的底层实现。zset新插入元素时,会判断以下两种条件:

  • zset中元素个数大于zset_max_ziplist_entries;
  • 插入元素的字符串长度大于zset_max_ziplist_value。当满足任一条件时,Redis便会将zset的底层实现由压缩列表转为跳跃表。

zset在转为跳跃表之后,即使元素被逐渐删除,也不会重新转为压缩列表。

2 跳跃表的结构

其c语言代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct zskiplistNode {
//成员对象
robj *obj;
double score;//分值
struct zskiplistNode *backward;//回退指针
//层
struct zskiplistLevel {
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
} level[];
} zskiplistNode;

1)obj:用于存储字符串类型的数据。
2)score:用于存储排序的分值。
3)backward:后退指针,只能指向当前节点最底层的前一个节点,头节点和第一个节点——backward指向NULL,从后向前遍历跳跃表时使用。
4)level:为柔性数组。每个节点的数组长度不一样,在生成跳跃表节点时,随机生成一个1~64的值,值越大出现的概率越低。
level数组的每项包含以下两个元素。

  • forward:指向本层下一个节点,尾节点的forward指向NULL。
  • span:forward指向的节点与本节点之间的元素个数。span值越大,跳过的节点个数越多。

除了跳跃表节点外,还需要一个跳跃表结构来管理节点,Redis使用zskiplist结构体,定义如下:

1
2
3
4
5
typedef struct zskiplist {
struct zskiplistNode *header, *tail;
unsigned long length;
int level;
} zskiplist;

1)header:指向跳跃表头节点。头节点是跳跃表的一个特殊节点,它的level数组元素个数为64。头节点在有序集合中不存储任何member和score值,ele值为NULL, score值为0;也不计入跳跃表的总长度。头节点在初始化时,64个元素的forward都指向NULL, span值都为0。
2)tail:指向跳跃表尾节点。
3)length:跳跃表长度,表示除头节点之外的节点总数。
4)level:跳跃表的高度。

查找从最高层开始,如果本层的next节点大于要查找的值或next节点为NULL,则从本节点开始,降低一层继续向后查找,依次类推,如果找到则返回节点;否则返回NULL。采用该原理查找节点,在节点数量比较多时,可以跳过一些节点,查询效率大大提升,这就是跳跃表的基本思想。

1)跳跃表由很多层构成。
2)跳跃表有一个头(header)节点,头节点中有一个64层的结构,每层的结构包含指向本层的下个节点的指针,指向本层下个节点中间所跨越的节点个数为本层的跨度(span)。
3)除头节点外,层数最多的节点的层高为跳跃表的高度(level)
4)每层都是一个有序链表,数据递增。
5)除header节点外,一个元素在上层有序链表中出现,则它一定会在下层有序链表中出现。
6)跳跃表每层最后一个节点指向NULL,表示本层有序链表的结束。
7)跳跃表拥有一个tail指针,指向跳跃表最后一个节点。
8)最底层的有序链表包含所有节点,最底层的节点个数为跳跃表的长度(length)(不包括头节点)。
9)每个节点包含一个后退指针,头节点和第一个节点指向NULL;其他节点指向最底层的前一个节点。

Redis通过zslRandomLevel函数随机生成一个1~64的值作为新建节点的高度

3 压缩列表

压缩列表ziplist本质上就是一个字节数组,是Redis为了节约内存而设计的一种线性数据结构,可以包含多个元素,每个元素可以是一个字节数组或一个整数。

Redis的有序集合、散列和列表都直接或者间接使用了压缩列表。当有序集合或散列表的元素个数比较少,且元素都是短字符串时,Redis便使用压缩列表作为其底层数据存储结构。列表使用快速链表(quicklist)数据结构存储,而快速链表就是双向链表与压缩列表的组合。

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

1)zlbytes:压缩列表的字节长度,占4个字节,因此压缩列表最多有232-1个字节。
2)zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量,占4个字节。3)zllen:压缩列表的元素个数,占2个字节。zllen无法存储元素个数超过65535(216-1)的压缩列表,必须遍历整个压缩列表才能获取到元素个数。4)entryX:压缩列表存储的元素,可以是字节数组或者整数,长度不限。entry的编码结构将在后面详细介绍。
5)zlend:压缩列表的结尾,占1个字节,恒为0xFF。

而压缩列表元素(entry)的编码结构:

  • previous_entry_length字段表示前一个元素的字节长度
    占1个或者5个字节,当前一个元素的长度小于254字节时,用1个字节表示;当前一个元素的长度大于或等于254字节时,用5个字节来表示。
  • encoding字段表示当前元素的编码
  • 数据内容存储在content字段

其中包含了很多复杂的解码运算,想详细了解的可以找对应的书来看。

连锁更新

每个节点的previous_entry_length属性都记录了前一个节点的长度,添加新节点可能会引发连锁更新之外,删除节点也可能会引发连锁更新。
因为某个可能的结点previous_entry_length属性仅长1字节,它没办法保存新节点new的长度,所以程序将对压缩列表执行空间重分配操作,并将则个节点的previous_entry_length属性从原来的1字节长扩展为5字节长。进而引发后面的连锁更新。
其最坏复杂度是O(N 2)。

尽管连锁更新的复杂度较高,但它真正造成性能问题的几率是很低的:

压缩列表里要恰好有多个连续的、长度介于250字节至253字节之间的节点,连锁更新才有可能被引发,在实际中,这种情况并不多见;
即使出现连锁更新,但只要被更新的节点数量不多,就不会对性能造成任何影响:比如说,对三五个节点进行连锁更新是绝对不会影响性能的;

4 quicklist

quicklist是Redis底层最重要的数据结构之一,它是Redis对外提供的6种基本数据结构中List的底层实现,在Redis 3.2版本中引入。

在引入quicklist之前,Redis采用压缩链表(ziplist)以及双向链表(adlist)作为List的底层实现。当元素个数比较少并且元素长度比较小时,Redis采用ziplist作为其底层存储;当任意一个条件不满足时,Redis采用adlist作为底层存储结构。

这么做的主要原因是,当元素长度较小时,采用ziplist可以有效节省存储空间,但ziplist的存储空间是连续的,当元素个数比较多时,修改元素时,必须重新分配存储空间,这无疑会影响Redis的执行效率,故而采用一般的双向链表。

结构如下:

代码如下

1
2
3
4
5
6
7
typedef struct quicklist{
quicklistNode *head;
quicklistNode *tail;
unsigned long count;//quicklist中元素总数
unsigned long len;//quicklist Node(节点)个数
int fill : 16;//每个quicklistNode中ziplist长度
}quicklist;
1
2
3
4
5
6
7
8
9
10
11
typedef struct quicklistNode{
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *zl;//zl指向该节点对应的ziplist结构;
unsigned int sz;//整个ziplist结构的大小
unsigned int count:16;//ziplist的个数
unsigned int coding:2;//1代表是原生的,2代表使用LZF进行压缩;
unsigned int containnr:2;//container为quicklistNode节点zl指向的容器类型:1代表none,2代表使用ziplist存储数据;
unsigned int recompress:1;//recompress代表这个节点之前是否是压缩节点
unsigned int extra:10;//extra为预留
}quicklistNode;

数据压缩

quicklist每个节点的实际数据存储结构为ziplist,这种结构的主要优势在于节省存储空间。为了进一步降低ziplist所占用的空间,Redis允许对ziplist进一步压缩,Redis采用的压缩算法是LZF,压缩过后的数据可以分成多个片段,每个片段有2部分:一部分是解释字段,另一部分是存放具体的数据字段。
解释字段可以占用1~3个字节,数据字段可能不存在。

1
2
3
4
typedef struct quicklistLZF{
unsigned int sz;//sz表示compressed所占字节大小
char compress[];
}quicklistLZF;

解释字段有3种:
1)字面型,解释字段占用1个字节,数据字段长度由解释字段后5位决定。
2)简短重复型,解释字段占用2个字节,没有数据字段,数据内容与前面数据内容重复,重复长度小于8。
3)批量重复型,解释字段占3个字节,没有数据字段,数据内容与前面内容重复。

压缩:
数据与前面重复的,记录重复位置以及重复长度,否则直接记录原始数据内容。压缩算法的流程如下:遍历输入字符串,对当前字符及其后面2个字符进行散列运算,如果在Hash表中找到曾经出现的记录,则计算重复字节的长度以及位置,反之直接输出数据。
解压:
可能存在重复数据与当前位置重叠的情况,例如在当前位置前的15个字节处,重复了20个字节,此时需要按位逐个复制。