目录
动态字符串SDS
IntSet
Dict
ZipList
QuickList
SkipList
RedisObject
五种数据类型
String
List
Set
ZSet
Hash
动态字符串SDS
Redis构建了一种新的字符串结构,称为简单动态字符串(Simple Dynamic String),简称SDS
Redis是C语言实现的,其中SDS是一个结构体,源码如下:
例如,一个包含字符串“name”的sds结构如下:
SDS之所以叫做动态字符串,是因为它具备动态扩容的能力,例如一个内容为“hi”的SDS:
假如要给SDS追加一段字符串“,Amy”,这里首先会申请新内存空间:
- 如果新字符串小于1M,则新空间为扩展后字符串长度的两倍+1
- 如果新字符串大于1M,则新空间为扩展后字符串长度+1M+1,称为内存预分配
IntSet
IntSet是Redis中set集合的一种实现方式,基于整数数组来实现,并且具备长度可变、有序等特征
结构如下:
其中的encoding包含三种模式,表示存储的整数大小不同:
为了方便查找,Redis会将IntSet中所有的整数按照升序依次保存在contents数组中,结构如图:
数组中每个数字都在int16_t的范围内,因此采用的编码方式是INTSET_ENC_INT16,每部分占用的字节大小为: encoding:4字节 length:4字节 contents:2字节 * 3 = 6字节
假设有一个IntSet,元素为{5,10,20},采用的编码是INTSET_ENC_INT16,则每个整数占2字节:
向其中添加一个数字:50000,这个数字超出了int16_t的范围,IntSet会自动升级编码方式到合适的大小,以当前案例来说流程如下:
- 升级编码为INTSET_ENC_INT32, 每个整数占4字节,并按照新的编码方式及元素个数扩容数组
- 倒序依次将数组中的元素拷贝到扩容后的正确位置
- 将待添加的元素放入数组末尾
- 将IntSet的encoding属性改为INTSET_ENC_INT32,将length属性改为4
源码:
IntSet可以看做是特殊的整数数组,具备一些特点:
- Redis会确保IntSet中的元素唯一、有序
- 具备类型升级机制,可以节省内存空间
- 底层采用二分查找方式来查询
Dict
Redis是一个键值型(Key-Value Pair)的数据库,可以根据键实现快速的增删改查,而键与值的映射关系正是通过Dict来实现的
Dict由三部分组成,分别是:哈希表(DictHashTable)、哈希节点(DictEntry)、字典(Dict)
当向Dict添加键值对时,Redis首先根据key计算出hash值(h),然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置
存储k1=v1,假设k1的哈希值h =1,则1&3 =1,因此k1=v1要存储到数组角标1位置(头插法)
组成:
Dict的扩容
Dict中的HashTable就是数组结合单向链表的实现,当集合中元素较多时,必然导致哈希冲突增多,链表过长,则查询效率会大大降低
Dict在每次新增键值对时都会检查负载因子(LoadFactor = used/size),满足以下两种情况时会触发哈希表扩容:
- 哈希表的LoadFactor >= 1,并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程
- 哈希表的LoadFactor > 5
Dict的收缩
Dict除了扩容以外,每次删除元素时,也会对负载因子做检查,当LoadFactor < 0.1时,会做哈希表收缩:
Dict的rehash
不管是扩容还是收缩,必定会创建新的哈希表,导致哈希表的size和sizemask变化,而key的查询与sizemask有关,因此必须对哈希表中的每一个key重新计算索引,插入新的哈希表,这个过程称为rehash
过程:
-
计算新hash表的realSize,值取决于当前要做的是扩容还是收缩:
-
如果是扩容,则新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]的内存
Dict的rehash并不是一次性完成的,分多次、渐进式的完成,称为渐进式rehash
总结:
Dict的结构:
- 类似java的HashTable,底层是数组加链表来解决哈希冲突
- Dict包含两个哈希表,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]执行,其它操作在两个哈希表
ZipList
ZipList 是一种特殊的“双端链表” ,由一系列特殊编码的连续内存块组成,可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 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 ),用于标记压缩列表的末端 |
ZipListEntry
ZipList 中的Entry并不像普通链表那样记录前后节点的指针,因为记录两个指针要占用16个字节,浪费内存,而是采用了下面的结构:
-
previous_entry_length:前一节点的长度,占1个或5个字节
-
如果前一节点的长度小于254字节,则采用1个字节来保存这个长度值
-
如果前一节点的长度大于254字节,则采用5个字节来保存这个长度值,第一个字节为0xfe,后四个字节才是真实长度数据
-
-
encoding:编码属性,记录content的数据类型(字符串还是整数)以及长度,占用1个、2个或5个字节
-
content:负责保存节点的数据,可以是字符串或整数
ZipList中所有存储长度的数值均采用小端字节序,即低位字节在前,高位字节在后,例如:数值0x1234(16进制,12为一个字节,34为一个字节),采用小端字节序后实际存储值为:0x3412
Encoding编码
ZipListEntry中的encoding编码分为两种:
1.字符串:如果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 |
例如保存字符串:“ab”和 “bc”
2.整数:如果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后结果为实际值 |
例如,一个ZipList中包含两个整数值:2和5
ZipList的连锁更新问题
ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小,长度是1个或5个字节:
- 如果前一节点的长度小于254字节,则采用1个字节来保存这个长度值
- 如果前一节点的长度大于等于254字节,则采用5个字节来保存这个长度值,第一个字节为0xfe,后四个字节才是真实长度数据
现在,假设有N个连续的、长度为250~253字节之间的entry,因此entry的previous_entry_length属性用1个字节即可表示,保存由1个字节变成5个字节,如图所示:
ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新(Cascade Update),新增、删除都可能导致连锁更新的发生
总结
ZipList特性:
- 压缩列表的可以看做一种连续内存空间的"双向链表"
- 列表的节点之间不是通过指针连接,而是记录上一节点和本节点长度来寻址,内存占用较低
- 如果列表数据过多,导致链表过长,可能影响查询性能
- 增或删较大数据时有可能发生连续更新问题
QuickList
问题1:ZipList虽然节省内存,但申请内存必须是连续空间,如果内存占用较多,申请内存效率很低,怎么办?
答:限制ZipList的长度和entry大小
问题2:要存储大量数据,超出了ZipList最佳的上限,怎么办?
答:创建多个ZipList来分片存储数据。
问题3:数据拆分后比较分散,不方便管理和查找,这多个ZipList如何建立联系?
答:Redis在3.2版本引入了新的数据结构QuickList,它是一个双端链表,只不过链表中的每个节点都是一个ZipList
为了避免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
默认值为 -2
除了控制ZipList的大小,QuickList还可以对节点的ZipList做压缩,通过配置项list-compress-depth来控制,因为链表一般都是从首尾访问较多,所以首尾是不压缩的,这个参数是控制首尾不压缩的节点个数:
- 0:特殊值,代表不压缩
- 1:标示QuickList的首尾各有一个节点不压缩,中间节点压缩
- 2:标示QuickList的首尾各有两个节点不压缩,中间节点压缩
- 以此类推
默认值为0
QuickList的和QuickListNode的结构源码:
总结
QuickList的特点:
- 是一个节点为ZipList的双端链表
- 节点采用ZipList,解决了传统链表的内存占用问题
- 控制了ZipList大小,解决连续内存空间申请效率问题
- 中间节点可以压缩,进一步节省了内存
SkipList
SkipList(跳表)首先是链表,但与传统链表相比有几点差异:
- 元素按照升序排列存储
- 节点可能包含多个指针,指针跨度不同
总结
SkipList的特点:
- 跳跃表是一个双向链表,每个节点都包含score和ele值
- 节点按照score值排序,score值一样则按照ele字典排序
- 每个节点都可以包含多层指针,层数是1到32之间的随机数
- 不同层指针到下一个节点的跨度不同,层级越高,跨度越大
- 增删改查效率与红黑树基本一致,实现却更简单
RedisObject
Redis中的任意数据类型的键和值都会被封装为一个RedisObject,也叫做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流 |
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
String是Redis中最常见的数据存储类型
基本编码方式是RAW,基于简单动态字符串(SDS)实现,存储上限为512MB
如果存储的SDS长度小于44字节,则会采用EMBSTR编码,此时object head与SDS是一段连续空间,申请内存时只需要调用一次内存分配函数,效率更高
如果存储的字符串是整数值,并且大小在LONG_MAX范围内,则会采用INT编码,直接将数据保存在RedisObject的ptr指针位置(刚好8字节),不再需要SDS
List
Redis的List类型可以从首、尾操作列表中的元素:
能满足上述特征的数据结构:
- LinkedList :普通链表,可以从双端访问,内存占用较高,内存碎片较多
- ZipList :压缩列表,可以从双端访问,内存占用低,存储上限低
- QuickList:LinkedList + ZipList,可以从双端访问,内存占用较低,包含多个ZipList,存储上限高
Redis的List结构类似一个双端链表,可以从首、尾操作列表中的元素:
- 在3.2版本之前,Redis采用ZipList和LinkedList来实现List,当元素数量小于512并且元素大小小于64字节时采用ZipList编码,超过则采用LinkedList编码
- 在3.2版本之后,Redis统一采用QuickList来实现List:
Set
Set是Redis中的单列集合,满足下列特点:
- 不保证有序性
- 保证元素唯一
- 求交集、并集、差集
Set对查询元素的效率要求非常高,可以满足的数据结构:HashTable,也就是Redis中的Dict,不过Dict是双列集合(可以存键值对)
为了查询效率和唯一性,set采用HT编码(Dict),Dict中的key用来存储元素,value统一为null
当存储的所有数据都是整数,并且元素数量不超过set-max-intset-entries(默认值为512)时,Set会采用IntSet编码,以节省内存
ZSet
ZSet也就是SortedSet,其中每一个元素都需要指定一个score值和member值:
- 可以根据score值排序后
- member必须唯一
- 可以根据member查询分数
ZSet底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求
可以满足的编码结构:
- SkipList:可以排序,并且可以同时存储score和ele值(member)
- HT(Dict):可以键值存储,并且可以根据key找value
两者结合
当元素数量不多时,HT和SkipList的优势不明显,而且更耗内存,因此ZSet还会采用ZipList结构来节省内存,不过需要同时满足两个条件:
- 元素数量小于zset_max_ziplist_entries,默认值128
- 每个元素都小于zset_max_ziplist_value字节,默认值64
ZipList本身没有排序功能,而且没有键值对的概念,因此需要有ZSet通过编码实现:
- ZipList是连续内存,因此score和element是紧挨在一起的两个entry, element在前,score在后
- score越小越接近队首,score越大越接近队尾,按照score值升序排列
Hash
Hash结构与Redis中的ZSet非常类似:
- 都是键值存储
- 都需求根据键获取值
- 键必须唯一
Hash与ZSet的区别:
- zset的键是member,值是score;hash的键和值都是任意值
- zset要根据score排序;hash则无需排序
Hash底层采用的编码与ZSet也基本一致,只需要把排序有关的SkipList去掉即可:
Hash结构默认采用ZipList编码,用以节省内存, ZipList中相邻的两个entry分别保存field和value
当数据量较大时,Hash结构会转为HT编码,也就是Dict,触发条件有两个:
- ZipList中的元素数量超过了hash-max-ziplist-entries(默认512)
- ZipList中的任意entry大小超过了hash-max-ziplist-value(默认64字节)