Redis系列 - Redis底层数据结构(简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表)

转自：https://blog.csdn.net/u011485472/article/details/109460490

Redis系列 - Redis底层数据结构(简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表)

简单动态字符串(simple dynamic string,SDS)
链表
字典
跳跃表
整数集合
压缩列表

RedisObject

在介绍Redis底层的6种数据结构之前，我们先看先Redis存储数据时用的RedisObject是什么？没一个存储的Redis数据都与一个RedisObject相关联，这是Redis存储数据的基本结构。

1 typedef struct redisObject {
2     unsigned type:4;
3     unsigned encoding:4;
4     unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
5                             * LFU data (least significant 8 bits frequency
6                             * and most significant 16 bits access time). */
7     int refcount;
8     void *ptr;
9 } robj;

RedisObject中共有5个属性（元数据占用8字节，ptr指针占用8字节）

type(4bits)： type 记录了对象的类型，即字符串、列表、哈希、集合或有序集合对象；不同的对象会有不同的type(4bits)，同一个类型的type会有不同的存储形式encoding(4bits)
ptr指针(8bytes)：指向对象的底层实现数据结构，即上述6中基本数据结构中的一种
encoding(4bits)： encoding 表示 ptr 指向的具体数据结构，即这个对象使用了什么数据结构作为底层实现，共有10中存储格式
refcount(4bytes)： refcount 表示引用计数，C语言垃圾回收需要使用
lru(24bits)：表示对象最后一次被命令程序访问的时间

共有10中存储格式如下

简单动态字符串(simple dynamic string,SDS)

SDS的结构体（即不同header类型）如下：

 1 struct __attribute__ ((__packed__)) hisdshdr5 {
 2     unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
 3     char buf[];
 4 };
 5 struct __attribute__ ((__packed__)) hisdshdr8 {
 6     uint8_t len; /* used */
 7     uint8_t alloc; /* excluding the header and null terminator */
 8     unsigned char flags; /* 3 lsb of type, 5 unused bits */
 9     char buf[];
10 };
11 struct __attribute__ ((__packed__)) hisdshdr16 {
12     uint16_t len; /* used */
13     uint16_t alloc; /* excluding the header and null terminator */
14     unsigned char flags; /* 3 lsb of type, 5 unused bits */
15     char buf[];
16 };
17 struct __attribute__ ((__packed__)) hisdshdr32 {
18     uint32_t len; /* used */
19     uint32_t alloc; /* excluding the header and null terminator */
20     unsigned char flags; /* 3 lsb of type, 5 unused bits */
21     char buf[];
22 };
23 struct __attribute__ ((__packed__)) hisdshdr64 {
24     uint64_t len; /* used */
25     uint64_t alloc; /* excluding the header and null terminator */
26     unsigned char flags; /* 3 lsb of type, 5 unused bits */
27     char buf[];
28 };

SDS主要由以下4部分组成：

len：占 4 个字节，表示 buf 的已用长度（额外开销）
alloc：占个 4 字节，表示 buf 的实际分配长度，一般大于 len（额外开销）
buf：字节数组，保存实际数据。为了表示字节数组的结束，Redis 会自动在数组最后加一个“\0”，这就会额外占用 1 个字节的开销（保存实际数据）
flags：表示使用的是哪种header类型

当字符串长度小于 1M 时，扩容都是加倍现有的空间，如果超过 1M，扩容时一次只会多扩 1M 的空间。(字符串最大长度为 512M)。

SDS存储图如下：

由于sds的header共有五种，要想得到sds的header属性，就必须先知道header的类型，flags字段存储了header的类型。假如我们定义了sds* s，那么获取flags字段仅仅需要将s向前移动一个字节，即unsigned char flags = s[-1]。

注：SDS本质上就是char类型的数组，因为有了表头sdshdr结构的存在，所以SDS比传统C字符串在某些方面更加优秀，并且能够兼容传统C字符串。SDS在Redis中是实现字符串对象的工具，并且完全取代char*..SDS是二进制安全的，它可以存储任意二进制数据，不像C语言字符串那样以‘\0’来标识字符串结束，因为传统C字符串符合ASCII编码，这种编码的操作的特点就是：遇零则止。即，当读一个字符串时，只要遇到’\0’结尾，就认为到达末尾，就忽略’\0’结尾以后的所有字符。因此，如果传统字符串保存图片，视频等二进制文件，操作文件时就被截断了。

而Redis 的字符串共有两种存储方式，在长度特别短时，使用 emb 形式存储 (embedded)，当长度超过 44 时，使用 raw 形式存储。

embstr 存储形式是这样一种存储形式，它将 RedisObject 对象头和 SDS 对象连续存在一起，使用 malloc 方法一次分配。而 raw 存储形式不一样，它需要两次 malloc，两个对象头在内存地址上一般是不连续的。

在字符串比较小时，SDS 对象头的大小是capacity+3——SDS结构体的内存大小至少是 3。意味着分配一个字符串的最小空间占用为 19 字节 (16+3)。

如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。而64-19-结尾的\0，所以empstr只能容纳44字节。

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

链表在Redis 中的应用非常广泛，比如列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis 就会使用链表作为列表键的底层实现。

每个链表节点使用一个 listNode结构表示（adlist.h/listNode）：

1 typedef struct listNode {
2     struct listNode *prev;
3     struct listNode *next;
4     void *value;
5 } listNode;

我们可以通过直接操作list 来操作链表会更加方便：

1 typedef struct list {
2     listNode *head;                     //表头节点
3     listNode *tail;                     //表尾节点
4     void *(*dup)(void *ptr);            //节点值复制函数
5     void (*free)(void *ptr);            //节点值释放函数
6     int (*match)(void *ptr, void *key); //节点值对比函数
7     unsigned long len;                  //链表长度
8 } list;

list 组成的结构如下图：

特性：

双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O(N)
无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止
表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)
长度计数器：链表中存有记录链表长度的属性 len
多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

哈希表

哈希表是一种用于保存键值对的抽象数据结构。哈希中的每一个键 key 都是唯一的，通过 key 可以对值来进行查找或修改。

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

哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：

 1 typedef struct dictEntry {
 2     void *key;            //键
 3     union {               //值
 4         void *val;
 5         uint64_t u64;
 6         int64_t s64;
 7         double d;
 8     } v;
 9     struct dictEntry *next;   //指向下一个哈希表节点，形成链表
10 } dictEntry;

key 用来保存键，val 属性用来保存值，值可以是一个指针，也可以是uint64_t整数，也可以是int64_t整数。

注意这里还有一个指向下一个哈希表节点的指针，我们知道哈希表最大的问题是存在哈希冲突，如何解决哈希冲突，有开放地址法和链地址法。这里采用的便是链地址法，通过next这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。

解决哈希冲突：这个问题上面我们介绍了，方法是链地址法。通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点。
扩容和收缩：1. 给哈希表 2 分配更大的空间，例如是当前哈希表 1 大小的两倍；2. 把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中；3. 释放哈希表 1 的空间。
触发扩容的条件：1. 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。2. 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。 ps：负载因子 = 哈希表已保存节点数量 / 哈希表大小。
渐近式 rehash：简单来说就是在第二步拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表 1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个索引位置的 entries。这样就巧妙地把一次性大量拷贝的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

跳跃表

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

跳跃表在链表的基础上增加了多级索引以提升查找的效率，但其是一个空间换时间的方案，必然会带来一个问题——索引是占内存的。原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值值和几个指针，并不需要存储对象，因此当节点本身比较大或者元素数量比较多的时候，其优势必然会被放大，而缺点则可以忽略。

Redis的跳跃表由zskiplistNode和skiplist两个结构定义,其中 zskiplistNode结构用于表示跳跃表节点,而 zskiplist结构则用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等。

skiplist结构如下：

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

header:指向跳跃表的表头节点，通过这个指针程序定位表头节点的时间复杂度就为O(1)
tail:指向跳跃表的表尾节点,通过这个指针程序定位表尾节点的时间复杂度就为O(1)
level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)，通过这个属性可以再O(1)的时间复杂度内获取层高最好的节点的层数。
length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)，通过这个属性，程序可以再O(1)的时间复杂度内返回跳跃表的长度。

1 typedef struct zskiplistNode {
2     sds ele;                                //成员对象 （robj *obj;） 指向一个sds
3     double score;                           //分值 用于实现zset
4     struct zskiplistNode *backward;         //后退指针 指向前一个节点
5     struct zskiplistLevel {                 //层  用一个结构体数组来表示各层中节点的关系
6         struct zskiplistNode *forward;        //前进指针
7         unsigned long span;                   //跨度实际上是用来计算元素排名(rank)的，在查找某个节点的过程中，将沿途访过的所有层的跨度累积起来，得到的结果就是目标节点在跳跃表中的排位
8     } level[];
9 } zskiplistNode;

Redis跳跃表示例如下：

成员对象(ele)：各个节点中的o1、o2和o3是节点所保存的成员对象。在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的:分值相同的节点将按照成员对象在字典序中的大小来进行排序,成员对象较小的节点会排在前面(靠近表头的方向),而成员对象较大的节点则会排在后面(靠近表尾的方向)
分值(score)：各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列
后退(backward)指针：节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。与前进指针所不同的是每个节点只有一个后退指针，因此每次只能后退一个节点
层(level)：节点中用1、2、L3等字样标记节点的各个层,L1代表第一层,L代表第二层,以此类推。

每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离(跨度越大、距离越远)。在上图中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。

每次创建一个新跳跃表节点的时候,程序都根据幂次定律(powerlaw,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的“高度”。

注：

跳跃表基于单链表加索引的方式实现
跳跃表以空间换时间的方式提升了查找速度
Redis有序集合在节点元素较大或者元素数量较多时使用跳跃表实现
Redis的跳跃表实现由 zskiplist和 zskiplistnode两个结构组成,其中 zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistnode则用于表示跳跃表节点
Redis每个跳跃表节点的层高都是1至32之间的随机数
在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。

整数集合

整数集合（intset）是Redis用于保存整数值的集合抽象数据类型，它可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。

整数集合是集合的实现方式之一，当一个集合里面的内容全部是整数，且集合的大小不超过512的时候，使用整数集合来实现集合。

1 typedef struct intset {
2     uint32_t encoding;      //编码方式
3     uint32_t length;        //集合包含的元素数量
4     int8_t contents[];      //保存元素的数组
5 } intset;

contents里面保存了整数集合内的数据，且按照大小升序排列。
encoding指示了contents里面保存的证书的类型，如果encoding是INTSET_ENC_INT16，那么contents里面的元素就都是16位的整数，假设存储了5个元素，那么占用的空间大小就是16*5=80

整数集合升级

之所以使用最小的int8_t来作为数组的最基本元素，是为了节约空间，但是当放入的整数太大int8_t放不下时集合就要通过调整编码的格式来升级。

例如当前的整数集合保存了1，2，3，4这几个整数，当前编码是16位整数，现在要将85631放入，85631需要用int32_t来表示，所以需要升级，升级分为三个步骤：

重新分配数组空间，由于类型变化了，那么需要的空间也要相应地调整，如之前是416=64，变化后应该是532=160
将已有的元素按新类型重新编码，然后调整他们的位置。需要注意的是，如果从前往后调整，那么有可能会覆盖到后面的数据，所以Redis是从后往前调整，调整位置的同时修改编码。
将新的元素插入到数组中去。在第三步插入的时候会根据每个元素原来的位置计算得出在新的数组中的位置，注意引发升级的时候新插入的数据一定是大于或者小于所有元素的，是正的就大是负的就小。

需要注意的是整数集合只有升级，没有降级。

压缩列表

压缩列表（ziplist）是Redis为了节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值。

压缩列表的原理：压缩列表并不是对数据利用某种算法进行压缩，而是将数据按照一定规则编码在一块连续的内存区域，目的是节省内存。

ziplist数据结构如下：

压缩列表的数据结构：

previous_entry_ength：记录压缩列表前一个字节的长度。previous_entry_ength的长度可能是1个字节或者是5个字节，如果上一个节点的长度小于254，则该节点只需要一个字节就可以表示前一个节点的长度了，如果前一个节点的长度大于等于254，则previous length的第一个字节为254，后面用四个字节表示当前节点前一个节点的长度。利用此原理即当前节点位置减去上一个节点的长度即得到上一个节点的起始位置，压缩列表可以从尾部向头部遍历。这么做很有效地减少了内存的浪费。
encoding：节点的encoding保存的是节点的content的内容类型以及长度，encoding类型一共有两种，一种字节数组一种是整数，encoding区域长度为1字节、2字节或者5字节长。
content：content区域用于保存节点的内容，节点内容类型和长度由encoding决定。

Redis常用的五种数据类型与底层数据结构对应关系如下：

标签：SDS,Redis,链表,哈希,跳跃,节点,指针
From： https://www.cnblogs.com/fnlingnzb-learner/p/17733024.html

Redis系列 - Redis底层数据结构(简单动态字符串(SDS)、链表、字典、跳跃表、整数集合、压缩列表)