Levon's Blog

微信: L6241425

0%

redis数据对象和底层数据结构

发表于 更新于 分类于 ， 阅读次数： Valine：
本文字数： 6.3k 阅读时长 ≈ 6 分钟

1. 基础对象

Redis的存储是以key-value的形式的。Redis中的key一定是字符串，value可以是string、list、hash、set、sortset这几种常用的。

类型作用底层数据结构
string简单的key-valueint, embstr(sds), raw
list有序列表,可做简单队列压缩列表,双向链表
hash哈希表, 存储结构化数据压缩列表,哈希 table
set无序列表(去重), 提供一系列的交集、并集、差集的命令整数集合,哈希 table
sortset有序集合映射, 排行榜压缩列表, 跳跃表

1.1 string

  • int 编码：保存的是可以用 long 类型表示的整数值。

  • embstr 编码：保存长度小于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）。

  • raw 编码：保存长度大于44字节的字符串（redis3.2版本之前是39字节，之后是44字节）

使用场景

  • 缓存： 经典使用场景，把常用信息，字符串，图片或者视频等信息放到redis中，redis作为缓存层，mysql做持久化层，降低mysql的读写压力。
  • 计数器：redis是单线程模型，一个命令执行完才会执行下一个，同时数据可以一步落地到其他的数据源。
  • session：常见方案spring session + redis实现session共享，

1.2 list

列表对象的编码可以是 ziplist 或者 linkedlist。新版本列表对象的编码是quicklist。

使用技巧

lpush+lpop=Stack(栈)

lpush+rpop=Queue（队列）

lpush+ltrim=Capped Collection（有限集合）

lpush+brpop=Message Queue（消息队列）

使用场景

  • 微博TimeLine: 有人发布微博，用lpush加入时间轴，展示新的列表信息。
  • 消息队列

1.3 hash

  • ziplist：key和value的字符串长度都小于64字节&&键值对总数量小于512
  • hashtable：key和value的字符串长度大于64字节||键值对总数量大于512

使用场景

  • 缓存： 直观，相比string更节省空间，的维护缓存信息，如用户信息，视频信息等。

1.4 set

  • intset：保存的元素全都是整数&&总数量小于512
  • hashtable：保存的元素不是整数||总数量大于512

使用场景

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

1.5 zset

  • ziplist：元素长度小于64&&总数量小于128
  • skiplist：元素长度大于64||总数量大于128

skiplist能够达到插入的时间复杂度为O(logn)，根据成员查分值的时间复杂度为O(1)

使用场景

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

2.底层数据结构

image-20230831144857220

2.1 简单动态字符串 - SDS

  • 常数复杂度获取字符串长度

    由于 len 属性的存在，我们获取 SDS 字符串的长度只需要读取 len 属性，时间复杂度为 O(1)。

  • 杜绝缓冲区溢出

  • 减少修改字符串的内存重新分配次数

    由于len属性和alloc属性的存在，对于修改字符串SDS实现了空间预分配和惰性空间释放两种策略。

  • 二进制安全
  • 兼容部分 C 字符串函数

2.2 压缩列表 - ZipList

Ziplist 是内存紧凑型列表，节省内存空间、提升内存使用率。适用列表数量较少，元素size较小的场景。

  1. 连续存储：Ziplist中的元素是连续存储的，不像普通的双向链表那样使用指针进行连接。这样可以减少指针的使用，从而节省内存。

  2. 紧凑存储：Ziplist通过使用紧凑的存储格式，可以节省内存空间。它将不同长度的字符串和整数存储在一起，使用特定的编码方式进行压缩，从而减少了存储空间的占用。

  3. 快速访问：由于Ziplist使用连续存储，可以通过偏移量（offset）快速访问到指定位置的元素，而无需像普通链表那样遍历。

2.3 快表 - QuickList

quicklist这个结构是Redis在3.2版本后新加的, 之前的版本是list(即linkedlist)， 用于String数据类型中。

它是一种以ziplist为结点的双端链表结构. 宏观上, quicklist是一个链表, 微观上, 链表中的每个结点都是一个ziplist。

2.4 字典/哈希表 - Dict

1. 解决哈希冲突

链地址法。通过字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点。

2. 扩容和收缩

当哈希表保存的键值对太多或者太少时，就要通过 rerehash(重新散列）来对哈希表进行相应的扩展或者收缩。具体步骤：

qq075484-0

ht[0].used当前的值为4，4*2=8，而8（2 3）恰好是第一个大于等于4的2的n次方，所以程序会将ht[1]哈希表的大小设置为8。图4-9展示了ht[1]在分配空间之后，字典的样子。

qq075484-1

将ht[0]包含的四个键值对都rehash到ht[1]

qq075484-2

释放ht[0]，并将ht[1]设置为ht[0]，然后为ht[1]分配一个空白哈希表。至此，对哈希表的扩展操作执行完毕，程序成功将哈希表的大小从原来的4改为了现在的8。

qq075484-3

3. 触发扩容的条件

1、服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。

2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。

ps：负载因子 = 哈希表已保存节点数量 / 哈希表大小。

对于一个大小为512，包含256个键值对的哈希表来说，这个哈希表的负载因子为：load_factor = 256 / 512 = 0.5

另一方面，当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。

4. 渐近式 rehash

如果保存在Redis中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成Redis一段时间内不能进行别的操作。

渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。

Redis采用渐进式 rehash，在渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行增加操作，一定是在新的哈希表上进行的。

2.5 整数集 - IntSet

整数集合（intset）是集合类型的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

2.6 跳表 - ZSkipList

  1. 跳跃表是一种平衡的数据结构：与平衡二叉搜索树相比，跳跃表的插入、删除和查找操作的平均时间复杂度都是O(log n)，其中n是元素的数量。
  2. 跳跃表是一种有序数据结构：跳跃表中的元素是有序排列的，使得查找操作可以通过跳跃的方式快速定位到目标元素。
  3. 跳跃表通过多级索引实现快速查找：跳跃表中的每一层都是原始链表的一个子集，每一级索引的元素数量逐渐减少。通过在不同级别之间跳跃，可以快速定位到目标元素。
  4. 跳跃表支持高效的插入和删除操作：相比平衡二叉搜索树，跳跃表的插入和删除操作更加简单高效，不需要进行平衡操作，只需要更新索引层的指针即可。
  5. 跳跃表相对简单易实现：相比其他平衡数据结构如红黑树等，跳跃表的实现相对简单，容易理解和实现。
  6. 跳跃表相对于其他数据结构，可能会占用更多的内存空间来存储额外的索引层。
image-20230831151230763

为什么Redis选择使用跳表而不是红黑树来实现有序集合?

Redis 中的有序集合(zset) 支持的操作：插入一个元素，删除一个元素，查找一个元素，有序输出所有元素，按照范围区间查找元素（比如查找值在 [100, 356] 之间的数据）。

其中，前四个操作红黑树也可以完成，且时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。按照区间查找数据时，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，非常高效。

3. 其他数据对象

3.1 HyperLogLogs（基数统计)

比如数据集 {1, 3, 5, 7, 5, 7, 8}， 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。 基数估计就是在误差可接受的范围内，快速计算基数。

1
2
3
4
5
6
7
8
9
10
11
12
127.0.0.1:6379> pfadd key1 a b c d e f g h i	# 创建第一组元素
(integer) 1
127.0.0.1:6379> pfcount key1					# 统计元素的基数数量
(integer) 9
127.0.0.1:6379> pfadd key2 c j k l m e g a		# 创建第二组元素
(integer) 1
127.0.0.1:6379> pfcount key2
(integer) 8
127.0.0.1:6379> pfmerge key3 key1 key2			# 合并两组：key1 key2 -> key3 并集
OK
127.0.0.1:6379> pfcount key3
(integer) 13

HyperLogLog只能统计基数的大小（也就是数据集的大小，集合的个数），他不能存储元素的本身，不能向set集合那样存储元素本身，也就是说无法返回元素。

3.2 Bitmap （位存储）

Bitmap 即位图数据结构，都是操作二进制位来进行记录，只有0 和 1 两个状态。

两个状态的，都可以使用 Bitmaps！如果存储一年的打卡状态需要多少内存呢？ 365 天 = 365 bit 1字节 = 8bit 46 个字节左右！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
127.0.0.1:6379> setbit sign 0 1
(integer) 0
127.0.0.1:6379> setbit sign 1 1
(integer) 0
127.0.0.1:6379> setbit sign 2 0
(integer) 0
127.0.0.1:6379> setbit sign 3 1
(integer) 0
127.0.0.1:6379> setbit sign 4 0
(integer) 0
127.0.0.1:6379> setbit sign 5 0
(integer) 0
127.0.0.1:6379> setbit sign 6 1
(integer) 0


127.0.0.1:6379> bitcount sign # 统计这周的打卡记录，就可以看到是否有全勤！
(integer) 4

3.3 geospatial (地理位置)

geo底层的实现原理实际上就是Zset。

Redis 的 Geo 在 Redis 3.2 版本就推出了! 这个功能可以推算地理位置的信息: 两地之间的距离, 方圆几里的人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 添加地理位置
127.0.0.1:6379> geoadd china:city 118.76 32.04 manjing 112.55 37.86 taiyuan 123.43 41.80 shenyang
(integer) 3
127.0.0.1:6379> geoadd china:city 144.05 22.52 shengzhen 120.16 30.24 hangzhou 108.96 34.26 xian
(integer) 3


# 获取指定的成员的经度和纬度
127.0.0.1:6379> geopos china:city taiyuan manjing
1) 1) "112.54999905824661255"
   1) "37.86000073876942196"
2) 1) "118.75999957323074341"
   1) "32.03999960287850968"

# 获得所有附近的人的地址, 定位, 通过半径来查询， 以 100,30 这个坐标为中心, 寻找半径为1000km的城市
127.0.0.1:6379> georadius china:city 110 30 1000 km			
1) "xian"
2) "hangzhou"
3) "manjing"
4) "taiyuan"

127.0.0.1:6379> georadius china:city 110 30 500 km
1) "xian"
127.0.0.1:6379> georadius china:city 110 30 500 km withdist
1) 1) "xian"
   2) "483.8340"
127.0.0.1:6379> georadius china:city 110 30 1000 km withcoord withdist count 2
1) 1) "xian"
   2) "483.8340"
   3) 1) "108.96000176668167114"
      2) "34.25999964418929977"
2) 1) "manjing"
   2) "864.9816"
   3) 1) "118.75999957323074341"
      2) "32.03999960287850968"

3.4 Stream

Redis5.0 中还增加了一个数据结构Stream，从字面上看是流类型，但其实从功能上看，应该是Redis对消息队列（MQ，Message Queue）的完善实现。

用过Redis做消息队列的都了解，基于Reids的消息队列实现有很多种，例如：

  • PUB/SUB，订阅/发布模式 : 但是发布订阅模式是无法持久化的，如果出现网络断开、Redis 宕机等，消息就会被丢弃；
  • 基于List LPUSH+BRPOP 或者 基于Sorted-Set的实现 ，支持了持久化，但是不支持多播，分组消费等。

4. 参考资料

给作者打赏，可以加首页微信，咨询作者相关问题！