参考《Redis设计与实现》
一丶简单动态字符串
当redis需要的不仅仅是一个字符串字面量,而是一个可以被修改的字符串值时,就会使用SDS(simple dynamic string)来表示字符串值。比如set msg "hello world"
将创建一个新键值对,键值对的键是一个字符串对象(存储着msg),值也是一个字符串对象(存储者hello world)
1.SDS的结构
- free属性记录buf数组剩余未使用的字节数量
- len属性记录当前buf数据已经使用的字符数量
- buf属性是char类型的数组,最后一个字节保存空字符
\0
2.SDS的优点
2.1 常数时间复杂度获取字符串长度
传统C语言的字符串,需要遍历整个字符串遇到字符串结尾的\0
结束计数,但是SDS的len属性便记录了字符串的长度,可以常数时间获取字符串长度
2.2杜绝缓冲区溢出
传统C语言修改字符串可能导致缓冲区溢出(多个字符串相邻的时候,修改到了相邻位置的其他字符串)但是SDS进行修改的时候,会先检查SDS空间是否满足修改需要的要求,如果不满足九自动扩容到需要的大小,然后才执行修改操作
2.3减少修改字符串带来的内存重分配次数
SDS实现了空间预分配和惰性空间释放
-
空间预分配
如果对SDS修改后,SDS的长度小于1mb(len属性)那么程序分配和len相同大小的未使用空间。如果SDS修改后长度大于1mb那么程序分配1mb大小的未使用空间。空间预分配减少连续执行字符串操作需要的内存分配次数。
-
惰性空间释放
当SDS进行字符串缩操作的时候,并不会立即将不需要的空间进行内存重分配,而是修改free属性进行记录。
二丶链表
链表在redis中始于广泛,当前列表键包含了较多元素,又或者包含的元素都是较长的字符串的时候,redis将始于链表作为列表键(xx键表示键对应的值是xx类型)的实现。
发布订阅,慢查询等功能就是基于链表实现的
1.链表结构
2.链表的优点
- 双端,获取某个节点的前置后置都是常数时间复杂度
- 无环
- 带表头指针和,表尾指针
- 带链表长度计数器
- 多态,链表节点使用void*指针保存节点值
三丶字典
字典是一种用于保存键值对的数据结构,一个key可以和一个value进行关联。
字典在redis中使用广泛,redis数据库就是使用字典作为底层实现的,对数据库的增删改查都是构建在字典这种数据结构之上,字典还是哈希键的底层实现,当哈希键包含的键值对比较多,又或者键值对中的元素都是较长的字符串是,redis使用字典作为哈希键的底层实现。
1.字典的结构
可以看到redis的字典使用拉链法解决哈希冲突,一个字典存在两个dictht,一个用于存储数据,一个用于渐进式rehash
2.哈希算法
redis使用MurmurHash2算法计算key的hash值,然后将hash值于sizemask进行且操作,相当于一次对数组大小的取模,可以得到当前key应该落在哈希表数组的那个下标位置
3.解决hash冲突
redis使用拉链发来解决hash冲突,每一个哈希节点具备一个next节点,多个哈希节点使用next指针串联成单向链表,从而解决hash冲突的问题
4.渐进式rehash
随着操作不断进行,哈希表可能存储很多数据,为了让哈希表的负载因子维持在一个合理的范围,当哈希表保存的键值太多的时候,程序需要对哈希表的大小进行相应的扩展或者收缩。
4.1渐进式rehash的步骤
- 为ht[1]分配空间
- 字典中维护一个索引计数器rehashidx,设置为0,表示渐进式rehash正式开始
- 在rehash的期间,对字典进行的增删改查,除了完成迁移哈希数组中的内容到ht[1]之外,还会将顺带将rehashidx索引上的所有键值对rehash到ht[1],然后将rehashidx自增1
- 随着字典操作的不断进行,最终会完全rehash完ht[0]中的所有元素,rehashidx置为-1,表示结束
4.2渐进式rehash期间哈希表的使用
由于渐进式rehash的期间,字典具备两个哈希表,字典的增删改查都需要在两个哈希表中进行,如果ht[0]不存在数据,还需要去ht[1]中寻找,
4.3哈希表扩容或者收缩的前提
当下列条件中满足任意一个的时候,程序会自动进行哈希表的扩容
- 服务器没有执行BGSAVE(RDB持久化),或者BGREWRITEAOF(AOF持久化)并且哈希表负载因子大于等于1
- 服务器正在执行BGSAVE(RDB持久化),或者BGREWRITEAOF(AOF持久化)但是哈希表负载因子大于等于5
负载因子 = 哈希表存储的节点数量 / 哈希表大小
BGSAVE,或者BGREWRITEAOF进行的途中,进来不进行rehash的原因是,这两个命令进行的过程中,redis需要创建服务器子进程,采用写时复制的技术优化子进程的使用效率,避免子进程运行的途中进行rehash可以节约内存
当负载因子小于0.1的时候,redis会对哈希表进行收缩
四丶跳跃表
跳跃表是一种有序的数据结构,支持O(log N)时间复杂度进行节点查找。
redis使用跳跃表作为有序集合键的底层实现之一,如果有序集合包含的元素,或者有序集合中元素的成员都是较长的字符串的时候,redis使用跳跃表作为有序集合键的底层实现。此外集群节点中也了使用跳表。
1.跳跃表的结构
2.跳跃表中的分值和成员
跳跃表是有序的结构,其中的分值便是排序的依据,多个节点可以包含相同的分值,分值相同的时候根据节点保存对象的大小进行排序,每个节点保存的对象必须唯一
五丶整数集合
整数集合是集合键的底层实现之一,当一个集合只有整数元素,且集合元素不多的适合,redis使用整数集合作为集合键底层实现
1.整数集合的结构
2.整数集合encoding编码方式
属性值表示contents数组中,整数的类型是int8_t,int16_t,int32_t,还是int64_t。
3.升级
当一个新元素添加到整数集合中,并且新元素的类型比整数集合中其他元素的类型都要长时,整数集合会进行升级,然后把新元素添加到集合中。升级的步骤:
- 根据新元素的类型,扩展整数集合底层数组的空间大小,并且为新元素分配空间
- 底层contents元素的类型转换到新元素相同类型,并放到争取的位置上,有序性不变
- 新元素添加到contents数组中
升级的好处:
-
提升灵活性
整数集合可以通过升级保存不同类型的新元素
-
节约内存
在需要的适合才会升级,才需要更大的内存空间,可以减少内存的占用
整数集合,不会进行降级。
六丶压缩列表
压缩列表ziplist是列表建和哈希键的底层实现之一。
当一个列表只包含少量列表项的,并且每一个列表项是小整数或者长度段的字符串,redis使用压缩列表作为列表键的底层实现(相比于链表,少前继后继指针更加节约内存)
当一个哈希键只包含少量键值对的适合,并且每个键值对的键和值都是小整数,或者段字符串的适合,redis使用压缩列表作为哈希键的底层实现
1.压缩列表的结构
2.连锁更新
每一个节点的previous_entry_length记录了前一个节点的长度,如果前一个节点的长度小于254字节,那么此属性使用一个字节进行记录,如果大于254字节那么使用五字节进行记录,所有如果新的节点的插入,也许这个节点的长度大于1字节,那么其后面的节点需要更新previous_entry_length为5字节大小,可能导致后续的节点也需要更新previous_entry_length,引发连锁更新
七丶对象
前面我们学习了简单动态字符串,链表,字典,跳跃表,整数集合,压缩列表的数据结构,但是redis并没有使用整个数据结构直接实现键值对数据库,而是基于这些数据结构实现了对象系统,包含:字符串对象
,列表对象
,哈希对象
,集合对象
,有序集合对象
,这样做的好处是,可以针对不同的使用场景使用不同的数据结构,优化效率。
redis还实现引用计数器的内存回收机制,并且会让多个数据库键共享一个对来节约内存。
redis中的对象还带有访问时记录信息,在服务器其余maxmemory功能的时候,根据此信息会删除长时间没有被访问的对象
1.对象的结构
-
类型
redis数据库中,键固定式字符串对象,但是键可能是字符串,列表,哈希,集合,有序集合对象等。type字段就记录了到底是什么对象(redis客户端使用
Type 键名
将返回对象类型) -
编码
encoding字段记录了,底层实现使用了什么编码,每种类型的对象至少使用了两种不同类型的编码。
使用
object encoding 键名
可以获取对象的编码使用编码,可以让redis在不同的情况下,使用不同的底层数据结构,优化效率
比如在列表元素比较少的时候,redis使用压缩列表,也不是使用链表,就是因为压缩列表相比链表,少了前继,后继指针,使用连续的内存存储,压缩列表更加节约内存。随着元素越来越多,redis将转化使用双端链表进行保存
-
底层实现
redis使用一个指针,指向底层实现的数据结构
2.字符串对象String
2.1字符串对象的结构
字符串对象的编码可以使用int
,raw
,embstr
-
当字符串对象保存一个字符串值,并且长度大于39字节的时候,字符串对象将使用简单动态字符串来保存,并且指定编码为raw
-
当保存的内容是一个字符串值,但是字符串长度小于等于39字节的时候,redis使用
embstr
来保存使用SDS的raw编码,会使用两次内存分配函数,分别创建redisObject,和SDS,但是embStr编码则只需要一次内存分配获取一块连续的空间,一次存储redisObject和字符串内容
-
当字符串对象保存的是一个整数值,并且整数值可以使用long来表示,这是redis会使用int类型编码
2.2字符串对象命令
-
set
redis根据情况使用不同的编码保存字符串对象
-
get
返回值
-
append
在尾部追加,对于int编码或者embstr编码会将对象编码转化为raw,然后进行拼接
-
incrbyFloat
redis会尝试将字符串转化为long double类型的数字,然后进行加法运算
-
incrby
只有int编码可以进行此操作,进行整数加法运算
-
decrby
只有int编码可以进行此操作,进行整数减法运算
-
strlen
返回字符串长度
-
setrange
设置特定索引上的值,int 和 embstr编码都会先转换为raw然后进行操作
-
getrange
返回特定索引下的值
3.列表对象list
3.1列表对象的结构
列表对象的编码可以是ziplist,或者linkedlist
- 当列表中的字符串元素都小于64字节的时候,且数量小于521的时候使用ziplist进行保存
-
当列表中的字符串元素存在大于64字节的元素时候,或者数量大于等于521的时候使用linkedlist进行保存
3.2列表命令
-
lpush
将新元素压入列表头部
-
rpush
将新元素压入列表尾部
-
lpop
返回表头元素,并删除表头元素
-
rpop
返回表尾元素,并删除表尾元素
-
LIndex
定位列表指定节点,并返回节点保存的元素
-
LLen
返回列表长度
-
LInsert
插入新节点到指定位置
-
LREM
删除给定元素的节点
-
LTRIM
删除不在索引范围内的节点
-
LSET
设置指定索引位置的值
4.哈希对象hash
4.1哈希对象的结构
哈希对象的编码可以是ziplist,也可以是hashtable
-
ziplist编码底层使用压缩链表,当新元素加入的时候,现在压缩链表中存储key然后存储value
当键值字符串长度都小于64字节,且数量小于512的时候,使用此种编码
-
hashtable编码底层使用字典,每一个键都是字符串对象,每一个值也是字符串对象
当键值字符串长度存在大于等于64字节的,或者数量大于512的时候,使用此种编码
4.2哈希对象的命令
-
hset
设置哈希对象 key和对应的值
-
hget
获取哈希对象key对应的值
-
hexists
判断哈希对象是否存在key
-
hdel
删除哈希对象 key和对应的值
-
hlen
返回哈希对象具备的key数量
-
hgetall
返回哈希对象索引的键和队友的值
5.集合对象set
5.1集合对象的结构
集合对象编码可以是intset,或者hashtable
-
intset编码底层使用整数集合
当集合保存的全是整数,并且数量不超过512个的时候使用此种编码
-
hashtable底层使用字典,但是value全为null
当集合保存的不全是整数,或者数量超过512个的时候使用此种编码
5.2集合对象的命令
-
SCARD
返回集合元素的数量
-
SISMEMBER
判断元素是否存在于集合
-
SMENBERS
返回所有集合元素
-
SRANDMEMBER
从集合中随机返回一个
-
SPOP
随机删除一个元素,并返回
-
SREM
删除给定元素
6.有序集合对象ZSET
6.1有序集合对象的结构
有序集合的编码有ziplist或者skiplist
-
ziplist底层使用压缩列表,每一个集合元素使用两个紧挨在一起的压缩列表节点表示,一个保存集合成员,一个保存分值
当有序集合元素少于128个,且元素长度都小于64字节的时候使用此种编码
-
skiplist编码,使用zset结构作为底层实现,一个zset包含一个字典,和一个跳跃表
当有序集合元素不少于128个,或者元素长度存在大于等于64字节的时候使用此种编码
跳跃表按照分值从小到大保存了所有集合元素,字典为有序集合创建了成员到分值的映射
二者的结合保证,范围查找和获取成员的分值都有较高的速度,范围型操作比如ZRANK,ZRANGE基于跳表进行,获取成员分值这种操作基于字典进行
二者保存的对象是共享的,不会使用两份空间进行保存
6.2有序集合对象的命令
-
ZADD
向有序集合存入元素和对应的分值
-
ZCARD
返回有序集合元素数量
-
ZCOUNT
返回有序集合指定分值范围元素的个数
-
ZRANGE
返回指定分值范围内的元素
-
ZRANK
返回元素和对应的排名
-
ZREM
删除元素
-
ZSCORE
返回给定元素的分值
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Redis数据结构与对象 - Python技术站