更新于 2020-04-22

# Introduce

Redis 是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。 它支持多种类型的数据结构,如 字符串(strings), 散列(hashes), 列表(lists), 集合(sets), 有序集合(sorted sets) 与范围查询, bitmaps, hyperloglogs 和 地理空间(geospatial) 索引半径查询。 Redis 内置了 复制(replication),LUA脚本(Lua scripting), LRU驱动事件(LRU eviction),事务(transactions) 和不同级别的 磁盘持久化(persistence), 并通过 Redis哨兵(Sentinel)和自动 分区(Cluster)提供高可用性(high availability)。

# 数据类型-String

# 介绍

官方文档介绍

字符串类型是 Reids最基础的数据结构,字符串类型的值可以是字符串(简单字符串、复杂字符串如Json-XML)、 数字(整数、浮点数),甚至是二进制(图片,音频,视频)。

# 数据结构

在 Redis 中字符串的存储结构为 SDS(Simple Dynamic String),其代码实现在 redis/src/sds.h 中,代码如下:

对应的结构如下

# 数据结构的选择

Redis 定义了五种类型的 sds 数据结构是为了满足不同长度的字符串可以使用不同大小的结构类型,从而节省内存空间。

sdshdr5 表示最多能存储 2^5 -1 = 31 个字符,最后一个字符存储 '\0' 结束标识。

sdshdr8 表示最多能存储 2^8 -1 = 255 个字符,最后一个字符存储 '\0' 结束标识。

以此类推。

所以 Redis 在进行字符串存储的时候会根据字符长度,使用不同的 sds 结构对象,代码在 redis/src/sds.c 中,如下:

# 扩容

随着字符串长度的增加,原本的 sds_x 不满足需要进行扩容,相关代码在 redis/src/sds.c 中,如下:

在字符串扩容时

  • 如果当前占用空间 < 1M ,扩容直接翻倍
  • 如果当前占用空间 > 1M,扩容 + 1M。

随着字符串的增加,可以一种扩容空间来存放该字符串,但是字符串的存储空间存在上限,官方也提到了最大上限为 512 M

# 使用案例

  • IP 限制
  • 短信验证
  • token 存储

# 数据类型-List

# 介绍

官方文档介绍

Redis lists基于Linked Lists(双向链表)实现。

在头部或尾部添加一个元素的操作,其时间复杂度也是常数级别的。

# 数据结构

在 Redis 3.2 以前,List 在 Reids 中有两种数据结构

  • ziplist(压缩列表)
  • linkedlist(双向链表)

当列表元素的个数小与 list-max-ziplist-entries 配置(默认512个),同时列表中的每个元素的值都小于 list-max-ziplist-value(默认64字节),Redis 会选择 ziplist 作为内部结构来减少内存的使用。

当列表类型无法满足 ziplist 的条件时,Redis 会使用 linkedlist 作为列表的内部实现。

在 Reids 3.2 后,Redis 通过 quicklist 结构结合 ziplist 和 linkedlist。quicklist 以 ziplist 作为节点结构组成 linkedlist。

# quicklist 结构在 redis/src/quicklist.h 相关代码如下

其中代码注释中有一段话:

quicklistNode is a 32 byte struct describing a ziplist for a quicklist

quicklist 大体结构图如下:

不过在使用中,节点不一定是用 ziplist 作为压缩节点,当设置为节点不压缩时,节点使用 quicklistLZF 作为节点数据结构。

# 使用案例

  • lpush+lpop=Stack(栈)
  • lpush+rpop=Queue(队列)
  • lpsh+ltrim=Capped Collection(有限集合)
  • lpush+brpop=Message Queue(消息队列)

# 数据类型-hash

# 介绍

官方介绍

Hash 类型指键值本身又是一个键值对结构,如:

{
	{'field1','value1'},
	{'field2','value2'},
	{'fieldN','valueN'}
}

同样是存储用户的多个字段,字符串对比于 hash 如下:

# 数据结构

hash 类型存在两种数据结构

  • ziplist(压缩列表)
  • hashtable(哈希表)

当 hash 类型元素个数小与 hash-max-ziplist-entries (默认 512) && 所有值都小于 hash-max-ziplist-value(默认64字节)时,Redis 使用 ziplist 作为 hash 的内部结构实现(ziplist使用更加紧凑的结构实现多个元素的连续存储,在节省内存方面比hashtable更优秀)。

当 hash 无法满足 ziplist 条件,Redis 使用hashtable 作为 hash 的内部结构实现。(因为此时 ziplist 的读写效率下降,二 hashtable 的读写时间复杂度为 O(1))。

# ziplist 结构

特点:

  • 内部表现为数据紧凑排列的一块连续内存数组
  • 可以模拟双向链表结构,以O(1)时间复杂度入队和出队
  • 新增删除操作涉及内存重新分配或释放,加大了操作复杂度
  • 读写操作设计复杂的指针移动,最欢时间复杂度O(n^2)
  • 适合存储小对象和长度有限的数据

# hashtable 数据结构在 redis/src/dict.h 中的代码

对应存储结构如下

通常情况下只使用到 ht[0] ,在扩容的时候才会使用 ht[1]

# 使用案例

  • 存储用户信息

# 数据类型-set

# 介绍

官方介绍

集合(set)类型用来保存多个字符串元素,其特点

  • 不允许有重复元素
  • 集合中的元素是无序的
  • 无法通过索引下标获取元素

一个集合最多存储 2^32 -1 个元素

存储方式如下

集合能够求交集、并集、差集

# 数据结构

set 存在两种数据结构

  • intset(整数集合)
  • hashtable(哈希表)

当 set 中的元素都是整数且元素个数小与 set-max-intset-entries(默认512)配置时,Redis 使用 intset 作为集合的内部结构实现,从而减少内存使用。

当 集合类型无法满足 intset 条件时,Redis 使用 hashtable 作为集合的内部结构。

# intset 数据结构在 redis/src/intset.h 中的代码

其实际上就是一个数组。

# 使用案例

  • sadd=Tagging(标签)
  • spop/srandmember=Random item(生成随机数,比如抽奖)
  • sadd+sinter=Social Graph(社交需求)

# 数据结构-有序集合

# 介绍

官方介绍

有序集合的特点

  • 集合内成员不能重复
  • 集合可以排序(通过 score 排序)

# 数据结构

有序集合存在2中数据结构

  • ziplist(压缩列表)
  • skiplist(跳跃表)

当有序集合的元素个数小于 zset-max-ziplist-entries (默认 128)配置 && 每个元素的值都小于 zset-max-ziplist-value(默认64字节)时,Redis 使用 ziplist 作为有序集合的内部结构。

当不满足 ziplis 条件时使用 skiplist。

# skiplist 结构对应 redis/src/server.h 代码如下

对应的结构如下

# 使用案例

  • 排行榜

# 列表-集合-有序集合异同

精彩内容推送,请关注公众号!
最近更新时间: 4/25/2020, 9:12:43 PM