基础结构

动态字符串SDS

  1. 字符串是redis中比较常见的有一种结构，比如string类型的key和value都是字符串。
  2. Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。
  3. Redis是C语言实现的，其中SDS是一个结构体。

  1. SDS之所以叫做动态字符串，是因为它具备动态扩容的能力。
    • 如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1。
    • 如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。
  2. redis不推荐键值对存储音频视频这种大内存数据。

整数集合Intset

  1. IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。
  2. 为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中。

  1. Intset可以看做是特殊的整数数组，具备一些特点：
    • Redis会确保Intset中的元素唯一、有序。
    • 具备类型升级机制，可以节省内存空间。
    • 底层采用二分查找方式来查询。

字典Dict

  1. Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。
  2. Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）。
  3. 当我们向Dict添加键值对时，Redis首先根据key计算出hash值（h），然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。
  4. 我们存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置。

双端链表ZipList

  1. ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。
  2. 可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

属性 类型 长度 用途
zlbytes uint32_t 4 字节 记录整个压缩列表占用的内存字节数
zltail uint32_t 4 字节 记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。
zllen uint16_t 2 字节 记录了压缩列表包含的节点数量。 最大值为UINT16_MAX （65534），如果超过这个值，此处会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。
entry 列表节点 不定 压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend uint8_t 1 字节 特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。
  1. ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：
    • previous_entry_length：前一节点的长度，占1个或5个字节。
      • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值。
      • 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长
    • encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节。
    • contents：负责保存节点的数据，可以是字符串或整数。

  1. ZipListEntry中的encoding编码分为字符串和整数两种：字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串。
编码 编码长度 字符串大小
|00pppppp| 1 bytes <= 63 bytes
|01pppppp|qqqqqqqq| 2 bytes <= 16383 bytes
|10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt| 5 bytes <= 4294967295 bytes
  1. 整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节
编码 编码长度 整数类型
11000000 1 int16_t（2 bytes）
11010000 1 int32_t（4 bytes）
11100000 1 int64_t（8 bytes）
11110000 1 24位有符整数(3 bytes)
11111110 1 8位有符整数(1 bytes)
1111xxxx 1 直接在xxxx位置保存数值，范围从0001~1101，减1后结果为实际值

双端链表QuickList

  1. ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。

  1. 为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。如果值为正，则代表ZipList的允许的entry个数的最大值。如果值为负，则代表ZipList的最大内存大小，分5种情况：
    • -1：每个ZipList的内存占用不能超过4kb
    • -2：每个ZipList的内存占用不能超过8kb
    • -3：每个ZipList的内存占用不能超过16kb
    • -4：每个ZipList的内存占用不能超过32kb
    • -5：每个ZipList的内存占用不能超过64kb

跳表SkipList

  1. SkipList（跳表）首先是链表，但与传统链表相比有几点差异：元素按照升序排列存储、节点可能包含多个指针，指针跨度不同。

  1. SkipList的特点：
    • 跳跃表是一个双向链表，每个节点都包含score和ele值
    • 节点按照score值排序，score值一样则按照ele字典排序
    • 每个节点都可以包含多层指针，层数是1到32之间的随机数
    • 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
    • 增删改查效率与红黑树基本一致，实现却更简单

RedisObject

  1. Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象。

  1. Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型。
编号 编码方式 说明
0 OBJ_ENCODING_RAW raw编码动态字符串
1 OBJ_ENCODING_INT long类型的整数的字符串
2 OBJ_ENCODING_HT hash表（字典dict）
3 OBJ_ENCODING_ZIPMAP 已废弃
4 OBJ_ENCODING_LINKEDLIST 双端链表
5 OBJ_ENCODING_ZIPLIST 压缩列表
6 OBJ_ENCODING_INTSET 整数集合
7 OBJ_ENCODING_SKIPLIST 跳表
8 OBJ_ENCODING_EMBSTR embstr的动态字符串
9 OBJ_ENCODING_QUICKLIST 快速列表
10 OBJ_ENCODING_STREAM Stream流
  1. Redis中会根据存储的数据类型不同，选择不同的编码方式。
数据类型 编码方式
OBJ_STRING int、embstr、raw
OBJ_LIST LinkedList和ZipList(3.2以前)、QuickList（3.2以后）
OBJ_SET intset、HT
OBJ_ZSET ZipList、HT、SkipList
OBJ_HASH ZipList、HT

String

  1. String是Redis中最常见的数据存储类型：其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。
  2. 如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。

  1. 如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

Set

  1. Set是Redis中的单列集合，满足下列特点：不保证有序性、保证元素唯一、求交集，并集，差集。

List

  1. Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素。

Hash

  1. 底层实现方式：压缩列表ziplist 或者 字典dict。
  2. 当Hash中数据项比较少的情况下，Hash底层才⽤压缩列表ziplist进⾏存储数据，当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：
    • ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
    • ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）
  3. Redis的hash之所以这样设计，是因为当ziplist变得很⼤的时候，它有如下几个缺点：
    • 每次插⼊或修改引发的realloc操作会有更⼤的概率造成内存拷贝，从而降低性能。
    • ⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据。
    • 当ziplist数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历。
  4. 总之，ziplist本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发⽣改动，就会引发内存realloc，可能导致内存拷贝。

ZSet

  1. ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值：
    • 可以根据score值排序后
    • member必须唯一
    • 可以根据member查询分数
  2. 因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求。之前学习的哪种编码结构可以满足？
    • SkipList：可以排序，并且可以同时存储score和ele值（member）
    • HT（Dict）：可以键值存储，并且可以根据key找value

  1. 当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：
    • 元素数量小于zset_max_ziplist_entries，默认值128
    • 每个元素都小于zset_max_ziplist_value字节，默认值64
  2. ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：
    • ZipList是连续内存，因此score和element是紧挨在一起的两个entry， element在前，score在后
    • score越小越接近队首，score越大越接近队尾，按照score值升序排列