Redis 数据结构与用途

一、简介

Redis 是一个开源的，内存中的数据结构存储系统，它可以用做数据库，缓存和消息中间件，支持每秒 10w 次查询请求。

支持多种类型的数据结构

• 字符串 strings
• 散列 hashes
• 列表 lists
• 集合 sets
• 有序集合 sorted sets
• bitmaps
• hyperloglogs
• 地理空间 geospatial 索引半径查询

二、数据类型及应用

String 字符串

存储原理

假设存储 key = hello vlaue = word

set hello word

String 的三种编码

• int，存储 8 个字节的长整型（long，2^63-1）
• embstr，embstr 格式的 SDS（Simple Dynamic String）
• raw，SDS，存储大于 44 个字节的字符串

redis 为什么要自己写一个 SDS 的数据类型

主要是为了解决 C 语言 char[] 的四个问题

1. 字符数组必须先给目标变量分配足够的空间，否则可能会溢出
2. 查询字符数组长度 时间复杂度 O(n)
3. 长度变化，需要重新分配内存
4. 通过从字符串开始到结尾碰到的第一个 \0 来标记字符串的结束，因此不能保存图片、音频、视频、压缩文件等二进制(bytes)保存的内容，二进制不安全

redis SDS

1. 不用担心内存溢出问题，如果需要会对 SDS 进行扩容
2. 因为定义了 len 属性，查询数组长度时间复杂度 O(1) 固定长度
3. 空间预分配，惰性空间释放
4. 根据长度 len 来判断是结束，而不是 \0

应用场景

• 缓存，热点数据

• 分布式 session

• set key value NX EX 分布式锁

• INCR 计数器

  • 文章的阅读量，微博点赞数，允许一定的延迟，先写入 Redis 再定时同步到数据库

• 全局 ID

  • INT 类型，INCRBY，利用原子性

• INCR 限流

  • 以访问者的 IP 和其他信息作为 key，访问一次增加一次计数，超过次数则返回 false。

• setbit 位操作

Hash 哈希

对于这种类似于 数据库表 的结构，redis 中可以使用 hash 进行存储

批量设置

 hmset coder:px age 30 addr wuhan tag java

批量获取

 hmget coder:px age addr tag

同样是存储字符串，Hash 与 String 的主要区别？

1. 把所有相关的值聚集到一个 key 中，节省内存空间
2. 只使用一个 key，减少 key 冲突
3. 当需要批量获取值的时候，只需要使用一个命令，减少内存/IO/CPU 的消耗

Hash 不适合的场景

1. Field 不能单独设置过期时间
2. 没有 bit 操作
3. 需要考虑数据量分布的问题（value 值非常大的时候，无法分布到多个节点）

Hash 的两种数据结构

如果 Field 的个数超过 512 个 或者 Field 中任意一个 键或者值 的长度大于 64 个字节，hash表 会用 ht 来存储

ziplist 压缩列表

ziplist 是一个经过特殊编码的双向链表，它不存储指向上一个链表节点和指向下一 个链表节点的指针，而是存储上一个节点长度和当前节点长度，通过牺牲部分读写性能， 来换取高效的内存空间利用率，是一种时间换空间的思想。只用在字段个数少，字段值小的场景里面。

ht(hashtable) 哈希表

在 Redis 中，hashtable 被称为字典（dictionary），它是一个 数组+链表 的结构。

为什么有 ht[0] 和 ht[1] 两个 hash 表，是为了扩容。

应用场景

购物车

List 列表

有序，左边是列表头，从左到右

存储有序的字符串（从左到右），元素可以重复。可以充当队列和栈的角色。

List 存储原理

内部是一个双向链表，*zl 指针指向的是 ziplist 压缩列表，数据真正还是存储在 ziplist 中。

应用场景

• 时间线
• 队列
• 栈

Set 集合

一个 set 集合可以存储 2^63-1 个元素

127.0.0.1:6379> sadd keyset 123 a b c d e f g 456
(integer) 9
127.0.0.1:6379> smembers keyset
1) "e"
2) "f"
3) "b"
4) "d"
5) "g"
6) "123"
7) "a"
8) "c"
9) "456"

存储结构

• intset
• hashtable

127.0.0.1:6379> object encoding keyset
"hashtable"
127.0.0.1:6379> sadd intsets 1 2 3
(integer) 3
127.0.0.1:6379> object encoding intsets
"intset"

应用场景

1.知乎点赞数

2.京东的商品筛选

127.0.0.1:6379> sadd brand:apple iPhone11
(integer) 1
127.0.0.1:6379> sadd brand:ios iPhone11
(integer) 1
127.0.0.1:6379> sadd screensize:6.0-6.24 iPhone11
(integer) 1
127.0.0.1:6379> sadd memorysize:256GB iPhone11
(integer) 1
127.0.0.1:6379> sinter brand:apple brand:ios screensize:6.0-6.24 memorysize:256GB
1) "iPhone11"

筛选商品(sinter 交集)，苹果，IOS，屏幕 6.0-6.24，内存大小 256G

sinter brand:apple brand:ios screensize:6.0-6.24 memorysize:256GB

ZSet 有序集合

每个元素有一个对应的分数，基于分数进行排序；如果分数相等，以 key 值的 ascii 值进行排序。

数据结构对比（list、set、zset）

存储结构

• ziplist
• skiplist+dict 跳表 + 字典

redis 配置文件

如果元素的个数超过 128 个 或者 元素中任意一个 value 的大小超过 64 个字节，存储会采用 skiplist 跳表

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

什么是 skiplist ?

上面的是普通的链表，下面的是跳表，level 是随机的

普通链表查找一个元素的时间复杂度为 O(n)

跳表的时间复杂度为 O(m*log2n)

假设我们找元素 19

1.先从起始的 level3 指针中查找 26 大于 19

2.退回到起始的 level2 的指针，大于 7 继续往后，找到 19

3.通过三次就找到了 19

应用场景

1.商品的评价标签，可以记录商品的标签，统计标签次数，增加标签次数，按标签的分值进行排序

#添加商品(编号i5001)的标签tag和对应标签的评价次数
127.0.0.1:6379> zadd good_tag:i5001 442 tag1 265 tag2 264 tag3
(integer) 3
#不带分数
127.0.0.1:6379> zrange good_tag:i5001 0 -1
1) "tag3"
2) "tag2"
3) "tag1"
#带分数
127.0.0.1:6379> zrange good_tag:i5001 0 -1 withscores
1) "tag3"
2) "264"
3) "tag2"
4) "265"
5) "tag1"
6) "442"

2.百度搜索热点

127.0.0.1:6379> zadd hotspot:20230906 520 pot1 263 pot2 244 pot3
(integer) 3
127.0.0.1:6379> zrange hotspot:20230906 0 -1 withscores
1) "pot3"
2) "244"
3) "pot2"
4) "263"
5) "pot1"
6) "520"
#增加点击次数
127.0.0.1:6379> ZINCRBY hotspot 1 pot1
"521"

BitMaps

Bitmaps 是在字符串类型上面定义的位操作。一个字节由 8 个二进制位组成。

应用场景：

• 用户访问统计
• 在线用户统计

Hyperloglogs

Hyperloglogs：提供了一种不太准确的基数统计方法，比如统计网站的 UV，存在一定的误差。

Streams

5.0 推出的数据类型。支持多播的可持久化的消息队列，用于实现发布订阅功能，借鉴了 kafka 的设计。

总结

数据结构

编码转换