图解Redis数据结构之对象系统

Redis基于其基础数据结构创建了对象系统。这个对象系统包含了字符串对象、列表对象、哈希对象、集合对象和有序集合对象,每一种对象都使用到了至少一种基础数据结构。

一、对象的类型与编码

1、Redis对象结构

图解Redis数据结构之对象系统插图
Redis对象结构

2、对象编码和底层实现

Redis命令查询:http://www.redis.cn/commands.html

类型编码对象的名称
REDIS_STRING[字符串对象]REDIS_ENCODING_INT使用整数实现的字符串对象
REDIS_ENCODING_EMBSTR使用embstr编码的简单动态字符串实现的字符串对象
REDIS_ENCODING_RAW使用简单动态字符串实现的字符串对象
REDIS_LIST[列表对象]REDIS_ENCODING_ZIPLIST使用压缩列表实现的列表对象
REDIS_ENCODING_LINKEDLIST使用双端链表实现的列表对象
REDIS_HASH[哈希对象]REDIS_ENCODING_ZIPLIST使用压缩列表实现的哈希对象
REDIS_ENCODING_HT使用字典实现的哈希对象
REDIS_SET[集合对象]REDIS_ENCODING_INTSET使用整数集合实现的集合对象
REDIS_ENCODING_HT使用字典实现的集合对象
REDIS_ZSET[有序集合对象]REDIS_ENCODING_ZIPLIST使用压缩列表实现的有序集合对象
REDIS_ENCODING_SKIPLIST使用跳跃表和字典实现的有序集合对象

二、底层数据结构与对象关系

图解Redis数据结构之对象系统插图2
数据结构与对象关系

1、字符串对象

1)编码介绍

  • 字符串对象有三种编码:int、embstr、raw
  • int编码的字符串和embstr编码的字符串对象可以转换为raw编码的字符串
  • embstr编码的字符串是只读的,且会分配一个连续的内存空间存储,因此分配和回收都只需要一次,而raw需要两次
  • 编码转换:当字符串值的长度大于32字节时采用raw编码存储,否则采用embstr编码,若为int类型值则采用int编码
图解Redis数据结构之对象系统插图4
int编码字符串对象
图解Redis数据结构之对象系统插图6
raw编码字符串对象
图解Redis数据结构之对象系统插图8
embstr编码字符串对象

2)应用场景

  • 缓存:经典使用场景,把常用信息,字符串,图片或者视频等信息放到Redis中,Redis作为缓存层,mysql做持久化层,降低mysql的读写压力
  • 计数器:Redis是单线程模型,一个命令执行完才会执行下一个,可用作秒杀库存扣减等
  • 分布式锁:常见分布式锁解决方案,这也得益于Redis的单线程模型

2、列表对象

1)编码介绍

  • 列表对象有两种编码:ziplist、linkedlist
  • ziplist编码的列表对象使用压缩列表作为底层实现,每一个压缩列表节点(entry)保存一个列表元素
  • linkedlist编码的列表对象使用双端链表作为底层实现,每一个链表节点(node)保存一个字符串对象,每个字符串对象保存一个列表元素
  • 编码转换:当列表对象所有元素的长度小于64字节且列表的元素数量小于512个时使用ziplist,否则使用linkedlist编码
图解Redis数据结构之对象系统插图10
ziplist编码的列表对象
图解Redis数据结构之对象系统插图12
linkedlist编码的列表对象

2)应用场景

  • :lpush+lpop
  • 队列:lpush+rpop
  • 有限集合:lpush+ltrim
  • 消息队列:lpush+brpop
  • timeline:例如微博的时间轴,有人发布微博,用lpush加入时间轴,展示新的列表信息。

3、哈希对象

1)编码介绍

  • 哈希对象有两种编码:ziplist、hashtable
  • ziplist编码的哈希对象使用压缩列表作为底层实现,当有节点加入时,会推入两个节点一个是键一个是值到表尾
  • hashtable编码的哈希对象使用字典作为底层实现,哈希对象中的每一个键值对都使用一个字典键值对来保存
  • 编码转换:和列表对象的转换条件类似,当所有元素的长度小于64字节且列表的元素数量小于512个时使用ziplist,否则使用hashtable编码
图解Redis数据结构之对象系统插图14
ziplist编码的哈希对象
图解Redis数据结构之对象系统插图16
hashtable编码的哈希对象

2)应用场景

  • 缓存: 经典使用场景,把常用信息,字符串,图片或者视频等信息放到redis中,Redis作为缓存层,mysql做持久化层,降低mysql的读写压力
  • 计数器:redis是单线程模型,hash结构的每一个小key可以原子的累计,也可用于秒杀场景,购物车等
  • session:常见方案spring session + redis实现session共享

4、集合对象

1)编码介绍

  • 集合对象有两种编码:intset、hashtable
  • intset编码的集合对象使用整数集合作为底层实现
  • hashtable编码的集合对象使用字典作为底层实现,字典的每一个键都是一个字符串对象,每个字符串对象包含了一个集合元素,而字典的值全部被设置为NULL
  • 编码转换:所有集合元素都是数值,且元素的数量不超过512个时使用intset,否则使用hashtable
图解Redis数据结构之对象系统插图18
intset编码的集合对象
图解Redis数据结构之对象系统插图20
hashtable编码的集合对象

2)应用场景

  • 标签(tag),给用户添加标签,或者用户给消息添加标签,这样有同一标签或者类似标签的可以给推荐关注的事或者关注的人
  • 点赞,或点踩,收藏等,可以放到set中实现

5、有序集合对象

1)编码介绍

  • 有序集合对象有两种编码:ziplist、skiplist
  • ziplist编码的有序集合对象使用压缩列表作为底层实现,每一个集合元素使用两个紧挨在一起的压缩列表节点保存,元素按照分值由小到大顺序排列
  • skiplist编码的有序集合对象比较特殊,其采用skiplist&dict的组合方式实现有序集合,每个跳跃表节点object属性保存一个集合元素,且其score属性则保存元素的分值,通过跳表可以实现范围查询。为了实现 O(1) 复杂度的节点查询,该实现引入了字典,字典的每一个键值对保存一个集合元素,字典键用于保存元素,字典值用于保存分值
  • 编码转换:当所有元素的长度小于128个且集合的所有元素长度都小于64字节时使用ziplist,否则使用skiplist编码
图解Redis数据结构之对象系统插图22
ziplist编码的有序集合对象
图解Redis数据结构之对象系统插图24
skiplist编码的有序集合对象

2)应用场景

  • 排行榜:有序集合经典使用场景。例如小说视频等网站需要对用户上传的小说视频做排行榜,榜单可以按照用户关注数,更新时间,字数等打分,做排行。

6、特殊数据结构

  • HyperLogLog(基数统计)
  • Geo(地理空间信息)
  • Pub/Sub(发布订阅)
  • BloomFilter(布隆过滤)
  • Bitmap(位图)

三、内存回收

C语言并不具备自动内存回收功能,所以Redis在自己的对象系统中构建了一个引用计数来实现的内存回收机制,通过这一机制,程序可以追踪对象的引用计数信息,在适当的时候自动释放对象并进行内存回收。在redisObject中属性refcount用作引用计数。

四、对象共享

对象的引用计数属性带有对象共享的机制,共享对象的前提条件必须是将要创建的对象和已存在对象完全一致,那么越复杂的对象验证操作的复杂度越高。尽管共享更复杂的对象更能节约更多的内存,但受到CPU时间限制,Redis只对包含整数值的字符串对象(0-9999的字符串对象)进行共享。

五、对象的空转时长

Redis对象属性后只能够还包含一个lru属性,该属性记录了对象最后一次被命令程序访问的时间,该属性被用作于服务器内存回收,volatile2-lru或者allkeys-lru内存回收算法就是在服务器内存超过了maxmemory值时,空转时长高的键内存空间将被回收(空转时长=当前时间-lru时间)。

发表评论