redis规定集合长度_Redis数据结构和对象系统，记住这12张
图就够啦
专注于Java领域优质技术，欢迎关注
来⾃：⽯杉的架构笔记
Redis是⼀个开源的 key-value 存储系统，它使⽤六种底层数据结构构建了包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象的对象系统。
今天我们就通过12张图来全⾯了解⼀下它的数据结构和对象系统的实现原理。
本⽂的内容如下：
⾸先介绍六种基础数据结构：动态字符串，链表，字典，跳跃表，整数集合和压缩列表。
其次介绍 Redis 的对象系统中的字符串对象(String)、列表对象(List)、哈希对象(Hash)、集合对象(Set)和有序集合对象(ZSet)。
最后介绍 Redis 的键空间和过期键( expire )实现。
数据结构
简单动态字符串
Redis 使⽤动态字符串 SDS 来表⽰字符串值。下图展⽰了⼀个值为 Redis 的 SDS结构 :
len: 表⽰字符串的真正长度(不包含NULL结束符在内)。
alloc: 表⽰字符串的最⼤容量(不包含最后多余的那个字节)。
flags: 总是占⽤⼀个字节。其中的最低3个bit⽤来表⽰header的类型。
buf: 字符数组。
SDS 的结构可以减少修改字符串时带来的内存重分配的次数，这依赖于内存预分配和惰性空间释放两⼤机制。
当 SDS 需要被修改，并且要对 SDS 进⾏空间扩展时，Redis 不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使⽤的空间。
如果修改后， SDS 的长度(也就是len属性的值)将⼩于 1MB ，那么 Redis 预分配和 len 属性相同⼤⼩的未使⽤空间。
如果修改后， SDS 的长度将⼤于 1MB ，那么 Redis 会分配 1MB 的未使⽤空间。
⽐如说，进⾏修改后 SDS 的 len 长度为20字节，⼩于 1MB，那么 Redis 会预先再分配 20 字节的空间， SDS 的 buf数组的实际长度(除去最后⼀字节)变为 20 + 20 = 40 字节。当 SDS的 len 长度⼤于 1MB时，则只会再多分配 1MB的空间。
类似的，当 SDS 缩短其保存的字符串长度时，并不会⽴即释放多出来的字节，⽽是等待之后使⽤。
链表
链表在 Redis 中的应⽤⾮常⼴泛，⽐如列表对象的底层实现之⼀就是链表。除了链表对象外，发布和订阅、慢查询、监视器等功能也⽤到了链表。
Redis 的链表是双向链表，⽰意图如上图所⽰。链表是最为常见的数据结构，这⾥就不在细说。
Redis 的链表结构的dup 、 free 和 match 成员属性是⽤于实现多态链表所需的类型特定函数：
dup 函数⽤于复制链表节点所保存的值，⽤于深度拷贝。
free 函数⽤于释放链表节点所保存的值。
match 函数则⽤于对⽐链表节点所保存的值和另⼀个输⼊值是否相等。
字典
字典被⼴泛⽤于实现 Redis 的各种功能，包括键空间和哈希对象。其⽰意图如下所⽰。
Redis 使⽤ MurmurHash2 算法来计算键的哈希值，并且使⽤链地址法来解决键冲突，被分配到同⼀个索引的多个键值对会连接成⼀个单向链表。
跳跃表
Redis 使⽤跳跃表作为有序集合对象的底层实现之⼀。它以有序的⽅式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查、删除、添加等操作都可以在对数期望时间下完成， 并且⽐起平衡树来说， 跳跃表的实现要简单直观得多。
跳表的⽰意图如上图所⽰，这⾥只简单说⼀下它的核⼼思想，并不进⾏详细的解释。
如⽰意图所⽰，zskiplistNode 是跳跃表的节点，其 ele 是保持的元素值，score 是分值，节点按照其 score 值进⾏有序排列，⽽ level 数组就是其所谓的层次化链表的体现。
每个 node 的 level 数组⼤⼩都不同， level 数组中的值是指向下⼀个 node 的指针和 跨度值 (span)，跨度值是两个节点的score的差值。越⾼层的 level 数组值的跨度值就越⼤，底层的 level 数组值的跨度值越⼩。
level 数组就像是不同刻度的尺⼦。度量长度时，先⽤⼤刻度估计范围，再不断地⽤缩⼩刻度，进⾏精
确逼近。
当在跳跃表中查询⼀个元素值时，都先从第⼀个节点的最顶层的 level 开始。⽐如说，在上图的跳表中查询 o2 元素时，先从o1 的节点开始，因为 zskiplist 的 header 指针指向它。
先从其 level[3] 开始查询，发现其跨度是 2，o1 节点的 score 是1.0，所以加起来为 3.0，⼤于 o2 的 score 值2.0。所以，我们可以知道 o2 节点在 o1 和 o3 节点之间。这时，就改⽤⼩刻度的尺⼦了。就⽤level[1]的指针，顺利到 o2 节点。
整数集合
整数集合 intset 是集合对象的底层实现之⼀，当⼀个集合只包含整数值元素，并且这个集合的元素数量不多时， Redis 就会使⽤整数集合作为集合对象的底层实现。
如上图所⽰，整数集合的 encoding 表⽰它的类型，有int16t，int32t 或者int64_t。其每个元素都是 contents 数组的⼀个数组项，各个项在数组中按值的⼤⼩从⼩到⼤有序的排列，并且数组中不包含任何重复项。length 属性就是整数集合包含的元素数量。
压缩列表
压缩队列 ziplist 是列表对象和哈希对象的底层实现之⼀。当满⾜⼀定条件时，列表对象和哈希对象都会以压缩队列为底层实现。
压缩队列是 Redis 为了节约内存⽽开发的，是由⼀系列特殊编码的连续内存块组成的顺序型数据结构。它的属性值有：
zlbytes : 长度为 4 字节，记录整个压缩数组的内存字节数。
zltail : 长度为 4 字节，记录压缩队列表尾节点距离压缩队列的起始地址有多少字节，通过该属性可以直接确定尾节点的地址。
zllen : 长度为 2 字节，包含的节点数。当属性值⼩于 INT16_MAX时，该值就是节点总数，否则需要遍历整个队列才能确定总数。
zlend : 长度为 1 字节，特殊值，⽤于标记压缩队列的末端。
中间每个节点 entry 由三部分组成：
previous_entry_length : 压缩列表中前⼀个节点的长度，和当前的地址进⾏指针运算，计算出前⼀个节点的起始地址。
encoding： 节点保存数据的类型和长度
content ：节点值，可以为⼀个字节数组或者整数。
对象
上⾯介绍了 6 种底层数据结构，Redis 并没有直接使⽤这些数据结构来实现键值数据库，⽽是基于这些数据结构创建了⼀个对象系统.
这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合这五种类型的对象，每个对象都使⽤到了⾄少⼀种前边讲的底层数据结构。
Redis 根据不同的使⽤场景和内容⼤⼩来判断对象使⽤哪种数据结构，从⽽优化对象在不同场景下的使⽤效率和内存占⽤。
Redis 的 redisObject 结构的定义如下所⽰。
typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; int refcount; void *ptr;} robj;
其中 type 是对象类型，包括REDISSTRING, REDISLIST, REDISHASH, REDISSET 和 REDIS_ZSET。
encoding是指对象使⽤的数据结构，全集如下。
字符串对象
我们⾸先来看字符串对象的实现，如下图所⽰。
如果⼀个字符串对象保存的是⼀个字符串值，并且长度⼤于32字节，那么该字符串对象将使⽤ SDS 进⾏保存，并将对象的编码设置为raw，如图的上半部分所⽰。
如果字符串的长度⼩于32字节，那么字符串对象将使⽤embstr 编码⽅式来保存。
embstr 编码是专门⽤于保存短字符串的⼀种优化编码⽅式，这个编码的组成和 raw 编码⼀致，都使⽤ redisObject 结构和 sdshdr 结构来保存字符串，如上图的下半部所⽰。
但是 raw 编码会调⽤两次内存分配来分别创建上述两个结构，⽽ embstr 则通过⼀次内存分配来分配⼀块连续的空间，空间中⼀次包含两个结构。
embstr 只需⼀次内存分配，⽽且在同⼀块连续的内存中，更好的利⽤缓存带来的优势，但是 embstr 是只读的，不能进⾏修改，当⼀个embstr 编码的字符串对象进⾏ append 操作时， redis 会现将其转变为 raw 编码再进⾏操作。
列表对象
列表对象的编码可以是 ziplist 或 linkedlist。其⽰意图如下所⽰。
当列表对象可以同时满⾜以下两个条件时，列表对象使⽤ ziplist 编码：
列表对象保存的所有字符串元素的长度都⼩于 64 字节。
列表对象保存的元素数量数量⼩于 512 个。
redis五种数据结构不能满⾜这两个条件的列表对象需要使⽤ linkedlist 编码或者转换为 linkedlist 编码。
哈希对象
哈希对象的编码可以使⽤ ziplist 或 dict。其⽰意图如下所⽰。
当哈希对象使⽤压缩队列作为底层实现时，程序将键值对紧挨着插⼊到压缩队列中，保存键的节点在前，保存值的节点在后。如下图的上半部分所⽰，该哈希有两个键值对，分别是 name:Tom 和 age:25。
当哈希对象可以同时满⾜以下两个条件时，哈希对象使⽤ ziplist 编码:
哈希对象保存的所有键值对的键和值的字符串长度都⼩于64字节。
哈希对象保存的键值对数量⼩于512个。
不能满⾜这两个条件的哈希对象需要使⽤ dict 编码或者转换为 dict 编码。
集合对象
集合对象的编码可以使⽤ intset 或者 dict。
intset 编码的集合对象使⽤整数集合最为底层实现，所有元素都被保存在整数集合⾥边。
⽽使⽤ dict 进⾏编码时，字典的每⼀个键都是⼀个字符串对象，每个字符串对象就是⼀个集合元素，⽽字典的值全部都被设置为NULL。如下图所⽰。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。