Redis的底层数据结构

发布于：2022-11-13 ⋅ 阅读:(639) ⋅ 点赞:(0)

要搞懂redis，首先得了解他的常用的数据类型，以及对应的底层的存储结构，看看它到底是如何实现如此高效且多样的数据结构，今天就用着一篇文章来揭开redis的面纱。

字典表

redis单机服务端有16个数据库，每个数据库都有一个字典结构，这个字典里存着两个hash表（为了之后的扩缩容），而这个hash表里有一个dictEntry 组成的数组，里面存放的就是所有的键值对。这个dictEntry还有指向下一个节点的指针，就是为了在hash冲突的情况，采用拉链法扩展出一个链表。

/*
 * 字典
 */
typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;
/*
 * 哈希表
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;
/*
 * 哈希表节点
 */
typedef struct dictEntry {
    
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

img

向字典表再添加一个元素 set name abin我们会先对key做散列运算，将得到的值再对哈希表的大小4做一个取余，假设得到的值是3，那么这个key就会落在3的位置，比如：

img

渐进式rehash

当我们哈希表中存的数据越来越多，哈希冲突的概率就会越来越大。这样所有的键值对冲突后会形成一个链表，查询的效率就由原先的O(1)变成了O(n)，所以我们要有一个评估的标准，用来判断是否需要扩缩容。

负载因子=used / size

扩容：

  1. 程序没有执行BGSAVE命令或者BGREWRITEAOF(AOF重写)命令，并且哈希表的负载因子大于等于1
  2. 如果程序正在执行BGSAVE或者BGREWRITEAOF(AOF重写)命令并且哈希表的负载因子大于等于5。在执行RDB或者AOF重写操作时，redis会创建当前服务器的子进程执行相应操作，为了避免在子进程存在期间对哈希表进行扩展操作，将扩展因子提高。可以避RDB或者AOF重写时不必要的内存写入操作，最大限度的节约内存。

缩容：当负载因子小于0.1

为什么需要渐进式rehash

然而redis并不像我画的那样，只有一两个key。一个生产使用的redis可以达到几百上千万个。而redis的核心计算是单线程的，一次性重新散列这么多的key会造成长时间的服务不可用，因此需要采用渐进式的rehash。

具体步骤

  1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
  2. 在字典中维持-一个索引计数器变量rehashidx,并将它的值设置为0，表示rehash工作正式开始。
  3. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增-一。
  4. 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作已完成。
  5. 最后将h[1]的地址设置给h[0]，并将h[1]设置为null，也就是将新哈希表替换旧hash表。

渐进式rehash的好处在于它采取分而治之，的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

共存的策略

因为在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表,所以在渐进式rehash进行期间：

  • 所有增删改查都会先访问ht[0],再访问ht[1].比如查询会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找，诸如此类
  • rehash期间所有新增的键值对都会添加到h[1]里，保证ht [0]的键值对数量会只减不增，最终会变成空表

scan-高位进位扫描

为了高效地匹配出数据库中所有符合给定模式的Key，Redis提供了Scan命令。该命令会在每次调用的时候返回符合规则的部分Key以及一个游标值Cursor（初始值使用0），使用每次返回Cursor不断迭代，直到Cursor的返回值为0代表遍历结束。

Redis官方定义Scan特点如下：

  1. 整个遍历从开始到结束期间， 一直存在于Redis数据集内的且符合匹配模式的所有Key都会被返回；
  2. 如果发生了rehash，同一个元素可能会被返回多次，遍历过程中新增或者删除的Key可能会被返回，也可能不会。

扫描的方式有两种，一种是顺序扫描，一种是高位进位的方式扫描，对应如下两种情况。而scan采用高位进位扫描法，尽可能的减少重复的概率。

img

假设某时刻，哈希表的长度由h[4]扩展到h[8]。看看高位进位法的扫描结果

img

  1. 先在h[4]中扫描到00
  2. 在扫描到10时发生了rehash
  3. 于是在h[8]中扫描010-110-001-101以此类推

再来看看如果按照顺序扫描会发生什么样的情况

img

  1. 先在h[4]中扫描到00-01
  2. 在扫描10的时候发生rehash
  3. 于是在h[8]中扫描010-011以此类推，这样会重新扫描到100，101等位置的key，造成大量重复

RedisObject

redis数据库中的每个键值对的键和值都是一个对象

  • 每个对象都有相应的类型，这些类型决定了你能对他们操作的指令，比如string类型的对象只能用set命令设置。
  • 每种类型的对象又有两种以上的编码，不同编码可以在不同场景上优化使用效率
/*
 * Redis 对象
 */
typedef struct redisObject {

    // 类型
    unsigned type:4;

    // 编码方式
    unsigned encoding:4;

    // LRU - 24位, 记录最末一次访问时间（相对于lru_clock）; 或者 LFU（最少使用的数据：8位频率，16位访问时间）
    unsigned lru:LRU_BITS; // LRU_BITS: 24

    // 引用计数
    int refcount;

    // 指向底层数据结构实例
    void *ptr;

} robj;

这里的每个字段都很重要，比如类型和编码，有一个基于6.0的关系图

img

比如我们执行一个命令 hset user age 25在字典上的数据结构大概是这样,为了方便，string类型的对象就简画成了stringobject。

img

核心就是搞明白，无论是key还是value，都是一个redisObject即可。

LRU

lru字段只对键对象起作用，存放的是这个键的最后访问时间戳，根据这个时间戳就可以了解这个对象多久没被访问过了

img

并且在内存淘汰开启了volatile-lru或allkeys-lru时，会将更久没被访问的那部分键优先释放，这部分下章会介绍。

对象共享

refcount存放的是这个对象的被引用次数，当这个值为0后才能真正释放内存。对象共享可以极大的改善redis的内存占用，特别是使用频率高的string对象。目前redis在初始化服务器时就会初始化1w个对象分别是0-9999的字符串对象。

数据类型

String字符串

String是redis中最基本的数据类型，一个key对应一个value。

String类型是二进制安全的，意思是 redis 的 string 可以包含任何数据。如数字，字符串，jpg图片或者序列化的对象。

编码方式

字符串对象的编码可以是int、raw或者embstr。

1）如果一个字符串对象保存的是整数值，并且这个整数值可以用lon类型表示，那么字符串对象将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long），并将字符串对象的编码方式设置为int。

2）如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于32字节，那么字符串对象将使用一个简单动态字符串保存这个值，并将对象的编码设置为raw。

3）如果字符串对象保存的是一个字符串值，并且这个字符串值的长度小于32字节，那么字符串对象将使用embstr编码的方式来保存这个字符串值。

编码的转换

int编码和embstr编码的字符串对象在满足条件的情况下，会转换为raw编码的字符串对象。

1）int编码转为raw编码:原对象保存的值不再是整数值，而是一个字符串值，那么会发生编码从int变为raw

2）redis没有为embstr编码的字符串对象编写任何相应的修改程序（只有int转为raw），所以，embstr编码字符串实际上是只读的，当对embstr编码的字符从执行修改命令时，

程序会先将对象的embstr转换成raw，然后再执行修改命令。（embstr编码的字符串对象执行APPEND命令后，对象的编码会从embstr变为raw）。

  • 命令使用
命令 简述 使用
GET 获取存储在给定键中的值 GET name
SET 设置存储在给定键中的值 SET name value
DEL 删除存储在给定键中的值 DEL name
INCR 将键存储的值加1 INCR key
DECR 将键存储的值减1 DECR key
INCRBY 将键存储的值加上整数 INCRBY key amount
DECRBY 将键存储的值减去整数 DECRBY key amount
  • 命令执行
127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> get hello
"world"
127.0.0.1:6379> del hello
(integer) 1
127.0.0.1:6379> get hello
(nil)
127.0.0.1:6379> set counter 2
OK
127.0.0.1:6379> get counter
"2"
127.0.0.1:6379> incr counter
(integer) 3
127.0.0.1:6379> get counter
"3"
127.0.0.1:6379> incrby counter 100
(integer) 103
127.0.0.1:6379> get counter
"103"
127.0.0.1:6379> decr counter
(integer) 102
127.0.0.1:6379> get counter
"102"

  • 实战场景

    • 缓存： 经典使用场景，把常用信息，字符串，图片或者视频等信息放到redis中，redis作为缓存层，mysql做持久化层，降低mysql的读写压力。
    • 计数器：redis是单线程模型，一个命令执行完才会执行下一个，同时数据可以一步落地到其他的数据源。
    • session：常见方案spring session + redis实现session共享，

List列表

Redis中的List其实就是链表（Redis用双端链表实现List）。

使用List结构，我们可以轻松地实现最新消息排队功能（比如新浪微博的TimeLine）。List的另一个应用就是消息队列，可以利用List的 PUSH 操作，将任务存放在List中，然后工作线程再用 POP 操作将任务取出进行执行。

对象的编码：

列表对象的编码在在3.2前是ziplist或者linkedlist，3.2后采用quicklist。

ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点保存一个列表节点。

linkedlist编码的列表对象使用双端链表作为底层

quicklist采用两者的结合

实现。每个双端链表节点（node）都保存一个字符串对象，而每个字符串对象都保存了一个列表元素。

编码的转换

**当列表对象可以同时满足一下两个条件时，列表对象使用ziplist编码，**不能满足这两个条件的列表对象需要使用linkedlist编码。

1）列表对象保存的所有字符串元素的长度都小于64字节

2）列表对象保存的元素数量小于512个，

  • 命令使用
命令 简述 使用
RPUSH 将给定值推入到列表右端 RPUSH key value
LPUSH 将给定值推入到列表左端 LPUSH key value
RPOP 从列表的右端弹出一个值，并返回被弹出的值 RPOP key
LPOP 从列表的左端弹出一个值，并返回被弹出的值 LPOP key
LRANGE 获取列表在给定范围上的所有值 LRANGE key 0 -1
LINDEX 通过索引获取列表中的元素。你也可以使用负数下标，以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。 LINDEX key index

  • 使用列表的技巧

    • lpush+lpop=Stack(栈)
    • lpush+rpop=Queue（队列）
    • lpush+ltrim=Capped Collection（有限集合）
    • lpush+brpop=Message Queue（消息队列）

  • 命令执行

127.0.0.1:6379> lpush mylist 1 2 ll ls mem
(integer) 5
127.0.0.1:6379> lrange mylist 0 -1
1) "mem"
2) "ls"
3) "ll"
4) "2"
5) "1"
127.0.0.1:6379> lindex mylist -1
"1"
127.0.0.1:6379> lindex mylist 10        # index不在 mylist 的区间范围内
(nil)

  • 实战场景

    • 微博TimeLine: 有人发布微博，用lpush加入时间轴，展示新的列表信息。
    • 消息队列

Set集合

Redis 的 Set 是 String 类型的无序集合。集合成员是唯一的，这就意味着集合中不能出现重复的数据。

Redis 中集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是 O(1)。

编码：

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

1）intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。

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

编码的转换

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

1）集合对象保存的所有值都是整数值

2）集合对象保存的元素数量不超过512个

  • 命令使用
命令 简述 使用
SADD 向集合添加一个或多个成员 SADD key value
SCARD 获取集合的成员数 SCARD key
SMEMBERS 返回集合中的所有成员 SMEMBERS key member
SISMEMBER 判断 member 元素是否是集合 key 的成员 SISMEMBER key member

其它一些集合操作，请参考这里https://www.runoob.com/redis/redis-sets.html

  • 命令执行
127.0.0.1:6379> sadd myset hao hao1 xiaohao hao
(integer) 3
127.0.0.1:6379> smembers myset
1) "xiaohao"
2) "hao1"
3) "hao"
127.0.0.1:6379> sismember myset hao
(integer) 1

  • 实战场景

    • 标签（tag）,给用户添加标签，或者用户给消息添加标签，这样有同一标签或者类似标签的可以给推荐关注的事或者关注的人。
    • 点赞，或点踩，收藏等，可以放到set中实现

Hash散列

Redis hash 是一个 string 类型的 field（字段） 和 value（值） 的映射表，hash 特别适合用于存储对象。

哈希对象的编码：

哈希对象的编码可以是ziplist或者hashtable。

  1. ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入压缩列表表尾。因此

    1. 保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；
    2. 先添加到哈希对象中的键值对会放在压缩列表的表头方向，而后添加的哈希对象中的键指对会被放在压缩列表的链表方向。

  3. hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存

    1. 字典的每个键都是一个字符串对象，对象中保存了键值对的键。
    2. 字典中每个值都是一个字符串对象，对象中保存了键值对的值。

编码的转换

当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码，否则使用hashtable编码

1）哈希对象保存的所有键值对的键和值的字符串长度都小于64个字节

2）哈希对象保存的键值对数量小于512个。

  • 命令使用
命令 简述 使用
HSET 添加键值对 HSET hash-key sub-key1 value1
HGET 获取指定散列键的值 HGET hash-key key1
HGETALL 获取散列中包含的所有键值对 HGETALL hash-key
HDEL 如果给定键存在于散列中，那么就移除这个键 HDEL hash-key sub-key1
  • 命令执行
127.0.0.1:6379> hset user name1 hao
(integer) 1
127.0.0.1:6379> hset user email1 hao@163.com
(integer) 1
127.0.0.1:6379> hgetall user
1) "name1"
2) "hao"
3) "email1"
4) "hao@163.com"
127.0.0.1:6379> hget user user
(nil)
127.0.0.1:6379> hget user name1
"hao"
127.0.0.1:6379> hset user name2 xiaohao
(integer) 1
127.0.0.1:6379> hset user email2 xiaohao@163.com
(integer) 1
127.0.0.1:6379> hgetall user
1) "name1"
2) "hao"
3) "email1"
4) "hao@163.com"
5) "name2"
6) "xiaohao"
7) "email2"
8) "xiaohao@163.com"

  • 实战场景

    • 缓存： 能直观，相比string更节省空间，的维护缓存信息，如用户信息，视频信息等。

Zset有序集合

Redis 有序集合和集合一样也是 string 类型元素的集合,且不允许重复的成员。不同的是每个元素都会关联一个 double 类型的分数。redis 正是通过分数来为集合中的成员进行从小到大的排序。

有序集合的成员是唯一的, 但分数(score)却可以重复。有序集合是通过两种数据结构实现：

  1. 压缩列表(ziplist): ziplist是为了提高存储效率而设计的一种特殊编码的双向链表。它可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。它能在O(1)的时间复杂度下完成list两端的push和pop操作。但是因为每次操作都需要重新分配ziplist的内存，所以实际复杂度和ziplist的内存使用量相关
  2. 跳跃表（zSkiplist): 跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这是采用跳跃表的主要原因。跳跃表的复杂度是O(log(n))。
  • 命令使用
命令 简述 使用
ZADD 将一个带有给定分值的成员添加到有序集合里面 ZADD zset-key 178 member1
ZRANGE 根据元素在有序集合中所处的位置，从有序集合中获取多个元素 ZRANGE zset-key 0-1 withccores
ZREM 如果给定元素成员存在于有序集合中，那么就移除这个元素 ZREM zset-key member1

更多命令请参考这里 https://www.runoob.com/redis/redis-sorted-sets.html

  • 命令执行
127.0.0.1:6379> zadd myscoreset 100 hao 90 xiaohao
(integer) 2
127.0.0.1:6379> ZRANGE myscoreset 0 -1
1) "xiaohao"
2) "hao"
127.0.0.1:6379> ZSCORE myscoreset hao
"100"

  • 实战场景

    • 排行榜：有序集合经典使用场景。例如小说视频等网站需要对用户上传的小说视频做排行榜，榜单可以按照用户关注数，更新时间，字数等打分，做排行。

数据结构

简单动态字符串 - sds

Redis 是用 C 语言写的，但是对于Redis的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是自己构建了一种名为 简单动态字符串（simple dynamic string,SDS）的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

struct sdshdr {
    uint8_t len; /* 当前字符串大小（单位字节）*/
    uint8_t alloc; /* 内存分配大小（单位字节） */
    unsigned char flags; /* 头类型分配8，16，32，64字节四种类型（其中5字节这种类型被弃用） */
    char buf[]; /* 字符串数组 */
};

sds有四种类型uint8, uint16, uint32, uint64，分别表示len以及alloc字段的长度。如果是uint8类型，那么len和alloc字段能存的数据最多为2的8次方，也就是256字节。这样在分配的内存很少的情况下，也能尽可能的节省字段的长度。

SDS比起C语言的字符串实现有啥优势？

  • 常数复杂度获取字符串长度

由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。而对于 C 语言，获取字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。通过 strlen key 命令可以获取 key 的字符串长度。

  • 杜绝缓冲区溢出

我们知道在 C 语言中使用 strcat 函数来进行两个字符串的拼接，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。而对于 SDS 数据类型，在进行字符修改的时候，会首先根据记录的 len 属性检查内存空间是否满足需求，如果不满足，会进行相应的空间扩展，然后在进行修改操作，所以不会出现缓冲区溢出。

  • 减少修改字符串的内存重新分配次数

C语言由于不记录字符串的长度，所以如果要修改字符串，必须要重新分配内存（先释放再申请），因为如果没有重新分配，字符串长度增大时会造成内存缓冲区溢出，字符串长度减小时会造成内存泄露。

而对于SDS，由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略：

1、空间预分配：对字符串进行空间扩展的时候，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。

2、惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节的数量记录下来，等待后续使用。（当然SDS也提供了相应的API，当我们有需要时，也可以手动释放这些未使用的空间。）

  • 二进制安全

因为C字符串以“\0”字符串结束的标识，而对于一些二进制文件（如图片等），内容可能包括“\0”，因此C字符串无法正确存取；而所有 SDS 的API 都是以处理二进制的方式来处理 buf 里面的元素，并且 SDS 不是以“\0”来判断是否结束，而是以 len 属性表示的长度来判断字符串是否结束。

  • 兼容部分 C 字符串函数

虽然 SDS 是二进制安全的，但是一样遵从每个字符串都是以“\0”结尾的惯例，这样可以重用 C 语言库<string.h> 中的一部分函数。

sds主要用于redis的string类型的底层结构

字典/哈希表 - Dict

字典本质上也是hash表，这里的哈希表和上文说的字典是一模一样的

img

哈希表主要有两个作用：

1、作为我们数据库的字典的底层实现，他每个字典有两个哈希表，一个在rehash时使用

2、作为redis的hash类型的底层实现

整数集 - IntSet

整数集合（intset）是集合类型的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
encoding `表示编码方式，的取值有三个：`INTSET_ENC_INT16`, `INTSET_ENC_INT32`, `INTSET_ENC_INT64

length 代表其中存储的整数的个数

contents 指向实际存储数值的连续内存区域, 就是一个数组；整数集合的每个元素都是 contents 数组的一个数组项（item），各个项在数组中按值得大小从小到大有序排序，且数组中不包含任何重复项。（虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组，但实际上 contents 数组并不保存任何 int8_t 类型的值，contents 数组的真正类型取决于 encoding 属性的值）

img

整数级的升级

当在一个int16类型的整数集合中插入一个int32类型的值，整个集合的所有元素都会转换成32类型。 整个过程有三步：

  • 根据新元素的类型（比如int32），扩展整数集合底层数组的空间大小，并为新元素分配空间。
  • 将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。
  • 最后改变encoding的值，length+1。

相反，redis并不会考虑降级，主要出于效率的考虑。

整数级主要作为redis的set类型的底层实现

双向链表-linkedlist

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

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;
typedef struct listNode {
    struct listNode *prev;//前驱指针
    struct listNode *next;//后继指针
    void *value; //节点的值
} listNode;

list 结构为链表提供了表头指针 head、表尾指针 tail，以及链表长度计数器 len，而 dup、free 和 match 成员则是用于实现多态链表所需的类型特定函数：

1、dup 函数用于复制链表节点所保存的值；

2、free 函数用于释放链表节点所保存的值；

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

图像如图所示：

img

双端链表 linkedlist 主要有两个作用：

1、3.2版本以前作为 Redis 的 list 数据类型底层实现方法之一；

2、作为通用数据结构可以被其他功能模块使用；

压缩列表 - ZipList

ziplist是为了提高存储效率而设计的一种特殊编码的双向链表。它可以存储字符串或者整数，存储整数时是采用整数的二进制而不是字符串形式存储。它能在O(1)的时间复杂度下完成list两端的push和pop操作。但是因为每次操作都需要重新分配ziplist的内存，所以实际复杂度和ziplist的内存使用量相关。

struct ziplist<T>{
    int32 zlbytes;           //整个压缩列表占用的字节数
    int32 zltail;     //最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllen;          //元素个数
    T[] entries;             //元素内容列表，紧密存储
    int8 zlend;              //标志压缩列表的结束，值恒为0XFF
}
struct entry {
    int<var> prevlen;         //前一个元素长度，用于快速定位到下一个元素的位置
    int<var> encoding;          //元素类型编码
    optional byte[] content;  //内容
}

ziplist：

  • zlbytes字段的类型是uint32_t, 这个字段中存储的是整个ziplist所占用的内存的字节数
  • zltail字段的类型是uint32_t, 它指的是ziplist中最后一个entry的偏移量. 用于快速定位最后一个entry, 以快速完成pop等操作
  • zllen字段的类型是uint16_t, 它指的是整个ziplit中entry的数量. 这个值只占2bytes（16位）: 如果ziplist中entry的数目小于65535(2的16次方), 那么该字段中存储的就是实际entry的值. 若等于或超过65535, 那么该字段的值固定为65535, 但实际数量需要一个个entry的去遍历所有entry才能得到.
  • zlend是一个终止字节, 其值为全F, 即0xff. ziplist保证任何情况下, 一个entry的首字节都不会是255

entry：

prevlen：前一个entry的大小，字段长度有多个等级；

encoding：不同的情况下值不同，用于表示当前entry的类型和长度；

entry-data：真是用于存储entry表示的数据；

img

大概内存结构长这样，支持快速定位到尾部，同时还支持双向遍历。

通过entry，我们了解到，每个节点都存了上一个节点的长度，由此才能双向遍历，通过本节点指针P-prelen=上个节点位置。

级联更新

并且prelen为了最大程度减小内存，有多个长度的等级，如果每个节点都是254个字节，第一个节点突然变成255字节，那么为了能存下这么长的长度，下一个节点需要扩充prevlen字段长度，导致下一个节点长度也超过255，最终导致级联更新。所以后面还出了listpack来实现该功能，listpack最大的区别在于保存的是本字段的长度，不会产生级联效果

在hash类型下的ziplist存储结构

img

在zset类型下的ziplist存储结构

img

本质上都是用了两个entry，第一个键，第二个值，紧密相连。

压缩列表ziplist主要用于hash和zset类型的某些简单场景的底层结构

3.2以前，还作为list的底层结构

快表 - QuickList

quicklist这个结构是Redis在3.2版本后新加的, 之前的版本是list(即linkedlist)， 用于String数据类型中。

它是一种以ziplist为结点的双端链表结构. 宏观上, quicklist是一个链表, 微观上, 链表中的每个结点都是一个ziplist。

早起的版本list的实现元素少用ziplist，元素多用linkedlist。后面改成了quicklist。

img

看图就能知道，是ziplist和linkedlist的结合。 考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的 指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管 理效率。后续版本对列表数据结构进行了改造，使用 quicklist 代替了 ziplist 和 linkedlist。

跳表 - ZSkipList

跳跃表结构在 Redis 中的运用场景只有一个，那就是作为有序列表 (Zset) 的使用。跳跃表的性能可以保证在查找，删除，添加等操作的时候在对数期望时间内完成，这个性能是可以和平衡树来相比较的，而且在实现方面比平衡树要优雅，这就是跳跃表的长处。跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构。

// server.h
// 最高层数为64层
#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
// 大概每隔4个节点向上抽象一层
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

typedef struct zskiplistNode {
	// 字符串类型的member值
    sds ele;
    // 分值
    double score;
    // 后向指针
    struct zskiplistNode *backward;
    struct zskiplistLevel {
    	// 前向指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned long span;
    } level[];
} zskiplistNode;

img

跳表的层数并没有严格的要求，否则每次删除节点，都有可能要降低别的节点的层数，复杂度就高了。

所以跳表的层数用的是随机算法，每次插入一个节点，每层是否生成都采用的随机算法计算。

可以思考两个问题，答案在八股文处解答：

  • redis为啥用跳表，不用平衡二叉树？
  • mysql为啥用平衡二叉树不用跳表？

参考资料

《redis设计与实现》

美团针对Redis Rehash机制的探索和实践

Redis进阶 - 数据结构：对象机制详解

Redis五种数据结构

redis基础数据结构及编码方式

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布