redis_原理

数据结构

1.动态字符串SDS

C语言字符串存在的问题：

获取字符串长度需要通过运算
非二进制安全
不可修改

redis构建了一种新的字符串结构，简单动态字符串Simple Dynamic String SDS

Redis是C语言实现的，其中SDS是一个结构体，属性包括：

uint8_t len：buf已保存的字符串字节数，不包含结束标示。
uint8_t alloc：buf申请的总的字节数，不包含结束结束标示。
unsigned char flags：不同SDS的头类型，用来控制SDS的头大小。
char buf[]

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力

动态扩容：

如果新字符串小于1M，则新空间为扩展后字符串长度的2倍+1（alloc=新字符串长度的2倍）+（结束字符\0的1位）
如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。

alloc=新空间大小-1（除去结束标示）

动态字符串优点

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

2.IntSet整数集合

IntSet是redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有效等特征。属性包括：

uint32_t encoding：编码方式，支持存放16位，32位，64位整数（2字节～类似short，4字节～类似int，8字节～类似long）
uint32_t length：元素个数
int8x _t contents[]：整数数组，保存集合数据（可能变成int16、int32...？）
为了方便查找，redis会将IntSet中所有的整数按照升序依次保存在content数组中。

IntSet升级
原元素：5、10、20（int16_t)，现在添加一个5000，超过int16_t的范围，intset会自动升级编码方式到合适的大小。流程如下：

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

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

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

3.Dict

我们知道redis是一个键值型（key-value pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。
Dict由三部分组成，分别是：哈希表DictHashTable、哈希节点DictEntry、字典Dict
字典dict属性：

dictType *type：dict类型，内置不同的hash函数
void *privdata：私有数据，在做特殊hash运算时使用
dictht ht[2]：一个dict包含2个哈希表，其中一个是当前数据，另一个一般是空，rehash时使用。
long rehashidx：rehash的进度，-1表示未进行
int16_t pauserehash：rehash是否暂停，1则暂停，0则继续

哈希表dictht的属性：

dictEntry **table：entry数组，数组中保存的是指向entry的指针
unsigned long size：哈希表大小
unsigned long sizemask：哈希表大小的掩码，总等于size-1
unsigned long used：entry个数

哈希节点dictEntry的属性：

void *key：键
union{*val,u64,s64,d}v：值
struct dictEntry *next：下一个Entry的指针

dict的扩容
Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。
Dict在每次新增键值对时都会检查负载因子LoadFactor=used/size，满足以下2种情况时会触发哈希表扩容：

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

扩容后：变为used+1，底层会对扩容大小做判断，实际上找的是第一个>=used+1的2^n

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

收缩后的大小：第一个大于等于used的2^n

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

计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
- 如果是扩容，则新size=第一个大于等于dict.ht[0].used + 1 的2^n
- 如果是收缩，则新size=第一个大于等于dict.ht[0].used的2^n(不得小于4)
按照新的realSize申请内存空间，创建dictht，并赋值给dict.ht[1]
设置dict.rehashidx = 0，标示开始rehash
将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存

渐进式rehash

总结
Dict的结构：

类似java的HashTable，底层是数组+链表来解决哈希冲突
Dict包含2个哈希表，ht[0]平常用，ht[1]用来rehash

Dict的伸缩：

当LoadFactor>5或者LoadFactor>1且没有子进程任务时，Dict扩容
当LoadFactor小于0.1时，Dict收缩
扩容后大小为第一个大于等于used + 1的2^n
收缩大小为第一个大于等于used的2^n
Dict采用渐进式rehash，每次访问Dict时执行一次rehash
rehash时ht[0]只减不增，新增操作只在ht[1]执行，其它操作在两个哈希表

4.ZipList

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

zlbytes：记录整个压缩列表占用的内存字节数
zltail：记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。
zllen：记录了压缩列表包含的节点数量。最大值为UINT16_MAX(65534)，如果超过这个值，此处会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。
entry：压缩列表包含的各个节点，节点的长度由节点保存的内容决定
zlend：特殊值0xFF（十进制255），用于标记压缩列表的末端

ZipListEntry
ZipList中的Entry并不像普通链表那样记录前后节点的指针，因为记录2个指针要占用16个字节，浪费内存，而是采用了下面的结构：
属性：

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

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

ZipList这样编码的目的：尽可能减少内存。

ZipList也有限制：遍历只能从前向后或者从后向前（如果长度过长，会出现问题，所以使用时ZipList会限制长度）

ZipList的连锁更新问题
ZipList的每一个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节。

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

假设我们有N个连续的、长度为250~253之间的entry，因此entry的previous_entry_length属性用1个字节即可表示。
现在在头部（左端）插入一个254字节的entry，后面节点的previous_entry_length都要依次变成5。ZipList在这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新。新增、删除都可能导致连锁更新的发生。
（目前这个问题，redis的作者并没有解决它，因为它发生的概率非常低）

总结-ZipList特性

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

QuickList

它是一个双端链表，只不过链表的每个节点都是一个ZipList

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制。

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

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

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

压缩的原因：一般我们对首尾的操作比较多，中间的节点一般用不到。

quicklist的属性：

*head：头节点指针
*tail：尾节点指针
count：所有ziplist的entry的数量
len： ziplists总数量
QL_FILL_BITS：ziplist的entry上限，默认值-2
QL_COMP_BITS：首尾不压缩的节点数量

quicklistNode的属性：

*prev：前一个节点指针
*next：下一个节点指针
*zl：当前节点的ZipList指针
sz：当前节点的ZipList的字节大小
count：当前节点的ZipList的entry个数
encoding：编码方式（1:ZipList。2:lzf压缩模式）

QuickList的特点

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

可以这样理解：QuickList兼具了链表和ZipList（压缩列表）的优点（内存不用连续+内存占用小）

SkipList

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

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

zskiplist属性：

*head：头节点指针
*tail：尾节点指针
length：节点数量
level：最大的索引层级，默认是1

skiplistNode属性：

ele：节点存储的值
score：节点分数，排序、查找用
*backward：前一个节点指针
level[]：多级索引数组（数组的每一个元素：1*forward：下一个节点指针。2span：索引跨度）

SkipList的特点

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

RedisObject

Redis中的任意数据类型的键和值都会被封装成一个RedisObject，也叫redis对象，属性如下：

type：对象类型（string，hash，list，set，zset）占4个bit
encoding：底层编码方式（11种）4bit
LRU_BITS：该对象最后一次被访问的时间，24bit
refcount：对象引用计数器，计数器为0说明对象无人引用，可以被回收。
*ptr：指针，指向存放实际数据的空间。

11种编码方式
0raw，1long，2hash，3已废弃，4双端链表，5压缩列表，6整数集合，7跳表，8embstr的动态字符串，9快速列表，10stream流

5种数据结构

string：编码方式int，embstr，raw
list：编码方式双端链表，快速列表
set：编码方式intset，ht
zset：编码方式压缩列表，ht，跳表
hash：编码方式压缩列表，ht

数据类型

1.String

RAW：（type、encoding、lru、refcount、ptr指向SDS）
EMBSTR：（type、encoding、lru、refcount、ptr后面紧接着SDS）
INT：（typr、encoding、lru、refcount、ptr里面直接存放数值）

2.List

类似于一个双端链表，可以从首尾操作列表中的元素

在3.2版本之前，redis采用ZipList和LinkedList来实现List，当元素数量小于512且越苏大小小于64字节时采用ZipList编码，超过则采用LinkedList编码
在3.2版本之后，redis统一采用QuickList来实现List

3.Set

Set是redis中的单列集合，满足下列特点：

不保证有序性
保证元素唯一（可以判断元素是否存在）
求交集、并集、差集

编码：

为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null。
当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries（默认512）时，Set会采用IntSet编码，以节省内存。

4.ZSet

ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值

可以根据score值排序
member必须唯一
可以根据member查询分数

因此，zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求，之前学的哪种编码结构可以满足？

SkipList：可以排序，并且可以同时存储score和ele值（member）
HT：可以键值存储，并且可以根据key找value

当元素数量不多时，HT和SkipList的优势不明想，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足2个条件：

元素数量小于zset_max_ziplist_entries，默认值128
每个元素都小于zset_max_ziplist_value字节，默认值64

ziplist本身没有排序功能，而且没有键值对概念，因此需要有zset通过编码实现：

ZipList是连续内存，因此score和element是紧挨在一起的2个entry，element在前，score在后
score越小越接近队首，越大越接近队尾，按照score升序排列

5.Hash

Hash结构和redis中的zset非常类似：

都是键值存储
都需求根据键获取值
键必须唯一

区别如下：

zset的键是member，值是score，hash的键和值都是任意值
zset要根据score排序，hash则无需排序

因此Hash底层采用的编码与Zset基本一致，只需要把排序有关的skiplist去掉即可：

Hash结构默认采用ZipList编码，用以节省内存，ZipList中相邻的2个entry分别保存field和value
当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有2个：
1. ziplist中的元素超过了hash-max-ziplist-entry（默认512）
2. ziplist中的任意entry大小超过了hash-max-ziplist-value（默认64字节）