IT小东北

# Redis底层数据结构数据结构

# 动态字符串SDS

Redis构建了一种新的字符串结构，简单动态字符串，简称SDS。

Redis是C语言实现的，其中SDS是一个结构体，源码如下

例如，一个包含字符串“name”的sds结构如下

SDS之所以叫做动态字符串，是因为它具有动态扩容的能力。例如一个内容为“hi”的SDS

假如我们要给SDS追加一段字符串“AMY”。这里首先会申请新内存空间

  • 如果新字符串小于1M。则新空间为扩展后字符串长度的俩倍+1；
  • 如果新字符串大于1M。则新空间为扩展后字符串长度+1M+1。称为内存预分配。

优点：

  • 获取字符串长度的时间复杂度为O(1)
  • 支持动态扩容
  • 减少内存分配次数
  • 二进制安全

# IntSet

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。

结构如下：

其中的encoding包含三种模式，表示存储的整数大小不同：

为了方便查找，Redis会将Intset中所有的整数按照升序依次保存在contents数组中，结果如图

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为：encoding：4字节length：4字节contents：2字节 * 3 = 6字节

右侧黑色公式为InSet中数组的寻址公式 起始地址+（每个元素的大小*索引）

# IntSet升级

现在假设有一个Intset，元素为{5,10,20}.采用的编码是INTSET_ENC_INT16，则每个整数占2字节：

我们向其中添加一个数字50000，这个数字超出了int16_t的范围，intset会自动升级编码格式到合适的大小

流程如下：

  1. 升级编码为INTSET_ENC_INT32，每个整数占4字节，并按照新的编码方式及元素个数扩容数组
  2. 倒叙依次将数组中的元素拷贝的扩容后的正确位置
  3. 将待添加的元素放入数组末尾
  4. 最后，将intset的encoding属性改为INTSET_ENT_INT32，将length属性改为4

总结：

IntSet可以看做是特殊的整数数组，具备一些特点：

  1. Redis会确保IntSet的元素唯一、有序
  2. 具备类型升级机制，可以节省内存空间
  3. 底层采用二分查找方式来查询

# Dict

Redis是一个键值型的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。

Dict由三部分组成，分别是：哈希表，哈希节点，字段

当我们向Dict添加键值对时，Redis首先根据Key计算出hash值（h），然后利用h&sizemask来计算元素应该存储到哪个数组中的哪个索引位置。

具体存放格式如下

# Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突，链表过程，则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子，满足以下俩种情况时会触发哈希表扩容：

  • 哈希表的LoadFactory>=1，并且服务器没有执行BGSAVE或者BGREWRITEAOF等后台进程；
  • 哈希表的LoadFactory>5

# Dict的收缩

Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactory<1时，会做哈希表收缩。

# Dict的rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。

  1. 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
  • 如果是扩容，则新size为第一个大于等于dict.ht[0].used+1的2的n次方
  • 如果是收缩，则新zie为第一个大于等于dict.ht[0].used的2的n次方
  1. 按照新的realeSize申请内容空间，创建dictht，并赋值给dict.ht[1]
  2. 设置dict.rehashidx=0,标示开始rehash
  3. 每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]
  4. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
  5. 将rehashidx赋值为-1，代表rehash结束
  6. 在rehash过程中，新增操作，则直接写入ht[1],查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行，这样可以确保ht[0]的数据只增不减，随着rehash最终为空

# 总结

  • Dict的结构
    • 类似java的hashtable，底层是数组加链表来解决hash冲突。
  • Dict包含俩个哈希表，ht[0]平常用，ht[1]用来rehash
  • Dict的伸缩
-   当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容
-   当LoadFactor小于0.1时，Dict收缩
-   扩容大小为第一个大于等于user+1的2的n次方
-   收缩大小为第一个大于等于user的2的n次方
-   Dict采用渐进式rehash，每次访问Dict时执行一次rehash
-   rehash时ht[0]只增不减，新增操作只在ht[1]执行，其他操作在俩个哈希表

# ZipList

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

# ZipListEntry

ZipList中的Entry并不像普通链表那样记录前后节点的指针，因为记录俩个指针要占用16字节，浪费内存，而是采用了一种特殊结构

  • previous_entry_length：前一节点的长度，占一个或5个字节
    • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一节点的长度大于254，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
  • encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或者5个字节
  • contents：负责保存节点的数据，可以是字符串或整数

ZipList中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412

# Encoding编码

ZipListEntry中的encoding编码分为字符串和整数俩种

  • 字符串：如果encoding是以00、01或者10开头，则增明content是字符串

例如我们要保存字符串：“ab”和“bc”

  • 整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节

例如，一个ZipList中包含两个整数值：“2”和“5”

# ZipList的连锁更新问题

ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5哥字节

  • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一节点的长度大于等于254个字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

假设如果有N个连续的、长度为250～254字节的entry，这时entry的previous_entry_length属性用1个字节即可表示，如果这个时候字段内容改变变成255个字节，这种情况会发成多次扩容操作

ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新。新增，删除都可能导致连锁更新的发生。

# 总结

  1. 压缩列表的可以看做是一种连续内存空间的 双向链表
  2. 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址、内存占用较低
  3. 如果链表数据过多，导致链表过长，可能影响查询性能
  4. 增或删较大数据时有可能发生连续更新问题。

# QuickList

在Redis 3.2版本引入了新的数据结构QuickList，它是一个双端队列，只不过链表中的每个节点都是一个ZipList

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：

  • 如果值为正，则代表ZipList的允许的entry个数的最大值
  • 如果值为负，则代表ZipList 的最大内存大小，分5种其情况
  • -1: 每个ZipList的内存占用不能超过4kb
  • -2 每个ZipList的内存占用不能超过8kb
  • -3 每个ZipList的内存占用不能超过16kb
  • -4 每个ZipList的内存占用不能超过32kb
  • -8 每个ZipList的内存占用不能超过64kb
  • 默认值为-2

除了控制ZipList的大小，QuickList还可以对节点进行压缩。通过配置list-compress-depth来控制。因为链表一般是从首位访问的较多，所以首尾是不压缩的，这个参数是控制首尾不压缩的节点个数：

  • 0:特殊值，代表不压缩
  • 1:标示quickList的首位各有1个节点不压缩，中间节点压缩
  • 以此类推
  • 默认值是0

以下是QuickList和QuickListNode的源码

QuickList存储元素格式

# 总结

QuickList的特点

  • 是一个节点为ZipList的双端链表
  • 节点采用ZipList，解决了传统链表的内存占用问题
  • 控制了ZipList大小，解决连续内存空间申请效率问题
  • 中间节点可以压缩，进一步节省了空间

# SkipList

SkipList（跳表）首先是跳表，但与传统链表相比有几点差异

  • 元素按照升序排列存储
  • 节点可能包含多个指针，指针跨度不同

结构体如下

# 总结：

SkipList的特点：

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

# RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象，源码如下

# Redis的编码方式

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流

#