Redis数据结构与对象

参考《Redis设计与实现》

系列文章目录和关于我

一丶简单动态字符串

当redis需要的不仅仅是一个字符串字面量,而是一个可以被修改的字符串值时,就会使用SDS(simple dynamic string)来表示字符串值。比如set msg "hello world"将创建一个新键值对,键值对的键是一个字符串对象(存储着msg),值也是一个字符串对象(存储者hello world)

1.SDS的结构

Redis数据结构与对象插图

  • free属性记录buf数组剩余未使用的字节数量
  • len属性记录当前buf数据已经使用的字符数量
  • buf属性是char类型的数组,最后一个字节保存空字符

2.SDS的优点

2.1 常数时间复杂度获取字符串长度

传统C语言的字符串,需要遍历整个字符串遇到字符串结尾的结束计数,但是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.链表结构

Redis数据结构与对象插图1

2.链表的优点

  • 双端,获取某个节点的前置后置都是常数时间复杂度
  • 无环
  • 带表头指针和,表尾指针
  • 带链表长度计数器
  • 多态,链表节点使用void*指针保存节点值

三丶字典

字典是一种用于保存键值对的数据结构,一个key可以和一个value进行关联。

字典在redis中使用广泛,redis数据库就是使用字典作为底层实现的,对数据库的增删改查都是构建在字典这种数据结构之上,字典还是哈希键的底层实现,当哈希键包含的键值对比较多,又或者键值对中的元素都是较长的字符串是,redis使用字典作为哈希键的底层实现。

1.字典的结构

Redis数据结构与对象插图2

可以看到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.跳跃表的结构

Redis数据结构与对象插图3

2.跳跃表中的分值和成员

跳跃表是有序的结构,其中的分值便是排序的依据,多个节点可以包含相同的分值,分值相同的时候根据节点保存对象的大小进行排序,每个节点保存的对象必须唯一

五丶整数集合

整数集合是集合键的底层实现之一,当一个集合只有整数元素,且集合元素不多的适合,redis使用整数集合作为集合键底层实现

1.整数集合的结构

Redis数据结构与对象插图4

2.整数集合encoding编码方式

属性值表示contents数组中,整数的类型是int8_t,int16_t,int32_t,还是int64_t。

3.升级

当一个新元素添加到整数集合中,并且新元素的类型比整数集合中其他元素的类型都要长时,整数集合会进行升级,然后把新元素添加到集合中。升级的步骤:

  • 根据新元素的类型,扩展整数集合底层数组的空间大小,并且为新元素分配空间
  • 底层contents元素的类型转换到新元素相同类型,并放到争取的位置上,有序性不变
  • 新元素添加到contents数组中

升级的好处:

  1. 提升灵活性

    整数集合可以通过升级保存不同类型的新元素

  2. 节约内存

    在需要的适合才会升级,才需要更大的内存空间,可以减少内存的占用

整数集合,不会进行降级。

六丶压缩列表

压缩列表ziplist是列表建和哈希键的底层实现之一。

当一个列表只包含少量列表项的,并且每一个列表项是小整数或者长度段的字符串,redis使用压缩列表作为列表键的底层实现(相比于链表,少前继后继指针更加节约内存)

当一个哈希键只包含少量键值对的适合,并且每个键值对的键和值都是小整数,或者段字符串的适合,redis使用压缩列表作为哈希键的底层实现

1.压缩列表的结构

Redis数据结构与对象插图5

2.连锁更新

每一个节点的previous_entry_length记录了前一个节点的长度,如果前一个节点的长度小于254字节,那么此属性使用一个字节进行记录,如果大于254字节那么使用五字节进行记录,所有如果新的节点的插入,也许这个节点的长度大于1字节,那么其后面的节点需要更新previous_entry_length为5字节大小,可能导致后续的节点也需要更新previous_entry_length,引发连锁更新

七丶对象

前面我们学习了简单动态字符串,链表,字典,跳跃表,整数集合,压缩列表的数据结构,但是redis并没有使用整个数据结构直接实现键值对数据库,而是基于这些数据结构实现了对象系统,包含:字符串对象列表对象哈希对象集合对象有序集合对象,这样做的好处是,可以针对不同的使用场景使用不同的数据结构,优化效率。

redis还实现引用计数器的内存回收机制,并且会让多个数据库键共享一个对来节约内存。

redis中的对象还带有访问时记录信息,在服务器其余maxmemory功能的时候,根据此信息会删除长时间没有被访问的对象

Redis数据结构与对象插图6

1.对象的结构

Redis数据结构与对象插图7

  • 类型

    redis数据库中,键固定式字符串对象,但是键可能是字符串,列表,哈希,集合,有序集合对象等。type字段就记录了到底是什么对象(redis客户端使用Type 键名 将返回对象类型)

  • 编码

    encoding字段记录了,底层实现使用了什么编码,每种类型的对象至少使用了两种不同类型的编码。

    使用object encoding 键名可以获取对象的编码

    使用编码,可以让redis在不同的情况下,使用不同的底层数据结构,优化效率

    比如在列表元素比较少的时候,redis使用压缩列表,也不是使用链表,就是因为压缩列表相比链表,少了前继,后继指针,使用连续的内存存储,压缩列表更加节约内存。随着元素越来越多,redis将转化使用双端链表进行保存

  • 底层实现

    redis使用一个指针,指向底层实现的数据结构

2.字符串对象String

2.1字符串对象的结构

字符串对象的编码可以使用int,raw,embstr

  • 当字符串对象保存一个字符串值,并且长度大于39字节的时候,字符串对象将使用简单动态字符串来保存,并且指定编码为raw

    Redis数据结构与对象插图8

  • 当保存的内容是一个字符串值,但是字符串长度小于等于39字节的时候,redis使用embstr来保存

    Redis数据结构与对象插图9

    使用SDS的raw编码,会使用两次内存分配函数,分别创建redisObject,和SDS,但是embStr编码则只需要一次内存分配获取一块连续的空间,一次存储redisObject和字符串内容

  • 当字符串对象保存的是一个整数值,并且整数值可以使用long来表示,这是redis会使用int类型编码

    Redis数据结构与对象插图10

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进行保存

Redis数据结构与对象插图11

  • 当列表中的字符串元素存在大于64字节的元素时候,或者数量大于等于521的时候使用linkedlist进行保存

    Redis数据结构与对象插图12

3.2列表命令

  • lpush

    将新元素压入列表头部

  • rpush

    将新元素压入列表尾部

  • lpop

    返回表头元素,并删除表头元素

  • rpop

    返回表尾元素,并删除表尾元素

  • LIndex

    定位列表指定节点,并返回节点保存的元素

  • LLen

    返回列表长度

  • LInsert

    插入新节点到指定位置

  • LREM

    删除给定元素的节点

  • LTRIM

    删除不在索引范围内的节点

  • LSET

    设置指定索引位置的值

4.哈希对象hash

4.1哈希对象的结构

哈希对象的编码可以是ziplist,也可以是hashtable

  • ziplist编码底层使用压缩链表,当新元素加入的时候,现在压缩链表中存储key然后存储value

    当键值字符串长度都小于64字节,且数量小于512的时候,使用此种编码

    Redis数据结构与对象插图11

  • hashtable编码底层使用字典,每一个键都是字符串对象,每一个值也是字符串对象

    当键值字符串长度存在大于等于64字节的,或者数量大于512的时候,使用此种编码

    Redis数据结构与对象插图13

4.2哈希对象的命令

  • hset

    设置哈希对象 key和对应的值

  • hget

    获取哈希对象key对应的值

  • hexists

    判断哈希对象是否存在key

  • hdel

    删除哈希对象 key和对应的值

  • hlen

    返回哈希对象具备的key数量

  • hgetall

    返回哈希对象索引的键和队友的值

5.集合对象set

5.1集合对象的结构

集合对象编码可以是intset,或者hashtable

  • intset编码底层使用整数集合

    当集合保存的全是整数,并且数量不超过512个的时候使用此种编码

    Redis数据结构与对象插图14

  • hashtable底层使用字典,但是value全为null

    当集合保存的不全是整数,或者数量超过512个的时候使用此种编码

    Redis数据结构与对象插图13

5.2集合对象的命令

  • SCARD

    返回集合元素的数量

  • SISMEMBER

    判断元素是否存在于集合

  • SMENBERS

    返回所有集合元素

  • SRANDMEMBER

    从集合中随机返回一个

  • SPOP

    随机删除一个元素,并返回

  • SREM

    删除给定元素

6.有序集合对象ZSET

6.1有序集合对象的结构

有序集合的编码有ziplist或者skiplist

  • ziplist底层使用压缩列表,每一个集合元素使用两个紧挨在一起的压缩列表节点表示,一个保存集合成员,一个保存分值

    当有序集合元素少于128个,且元素长度都小于64字节的时候使用此种编码

    Redis数据结构与对象插图11

  • skiplist编码,使用zset结构作为底层实现,一个zset包含一个字典,和一个跳跃表

    当有序集合元素不少于128个,或者元素长度存在大于等于64字节的时候使用此种编码

    跳跃表按照分值从小到大保存了所有集合元素,字典为有序集合创建了成员到分值的映射

    二者的结合保证,范围查找和获取成员的分值都有较高的速度,范围型操作比如ZRANK,ZRANGE基于跳表进行,获取成员分值这种操作基于字典进行

    二者保存的对象是共享的,不会使用两份空间进行保存

    Redis数据结构与对象插图15

6.2有序集合对象的命令

  • ZADD

    向有序集合存入元素和对应的分值

  • ZCARD

    返回有序集合元素数量

  • ZCOUNT

    返回有序集合指定分值范围元素的个数

  • ZRANGE

    返回指定分值范围内的元素

  • ZRANK

    返回元素和对应的排名

  • ZREM

    删除元素

  • ZSCORE

    返回给定元素的分值

文章来源于互联网:Redis数据结构与对象

THE END
分享
二维码