计算机基础

Appearance

Redis 常见数据类型和应用场景 ​

  • String：kv 结构（value最长 512M）

    • 底层实现：int和 SDS（simple dynamic string，简单动态字符串）
      • len属性判定字符串是否结束，获取长度时间复杂度 O(1)
        • C语言通过\0，所以不能存放该字符，且获取长度时间复杂度 O(n)
      • alloc 属性表示分配给字符串数组的长度
        • 用 alloc-len 计算剩余空间，拼接字符串会检查 SDS 是否容量够，不够自动扩容
        • 长度低于 1MB，翻倍扩容，大于 1MB，每次增加 1MB 扩容
      • buf[] 字符数组保存实际数据，可以存放任意数据，如文本、图片
    • 编码方式：
      • int：如果字符串对象保存的是整数，且可以用long类型来表示
      • embstr：字符串对象保存的是一个长度小于等于32字节的字符串
      • raw： 字符串对象保存的是一个长度大于32字节的字符串
    • 应用场景：
      • 缓存、计数、分布式锁：使用setnx和Lua脚本实现（删锁需要先查再删）

  • List:

    • 底层实现：由 quicklist 实现
    • 应用场景：一般要求顺序的业务中，如消息（由Stream或者mq替代）或者排行榜（由zset替换）

  • Hash：键值对集合

    • 底层实现：由压缩列表或哈希表实现
      • 当数据量较小时用 listpack 实现，数据量较大时使用哈希表实现
      • 阈值可以进行配置
    • 应用场景：
      • 缓存对象：相较于String的优势在于可以更灵活改变值
        • 比如购物车，用户id是key，商品id 是field，商品数量是value

  • Set：无序并唯一的键值集合

    • 支持交集、并集、差集计算
      • 但是复杂度较高，数据量大容易阻塞
      • 可以用从库做，或者客户端进行
    • 底层实现：
      • 如果数据都是整数且小于一定值，用整数集合，否则用哈希表
        • 整数集合，一个有限长度的数组，直接按照数据的值放在对应的索引位置
      • 阈值可以进行配置(set-maxintset-entries)
    • 应用场景：需要去重保障数据唯一性的场合
      • 点赞：保证一个用户一个赞
      • 共同关注：交集计算共同关注的好友、公众号等
      • 抽奖活动：避免一个用户重复中奖

  • Zset：有序的Set，又称为 SortedSet

    • 底层实现：数据量小：listpack，大：跳表+hash
      • 哈希保证了高效单点查询，查询到后，可以到跳表高效范围查询
      • 使用跳表是因为跳表比较简单，范围查找更加简单
      • 跳表每次查找，从最高层开始，如果当前层没有，依次找下一层，类似于二分查找
    • 应用场景：需要按照权重排序的场景
      • 排行榜：按照特定维度进行排序

  • BitMap：位图，一连串连续二进制数组（0和1），可以通过偏移量

    • 底层实现：String类型
    • 应用场景：需要记录海量二维数据的场景
      • 签到统计：每个用户每天的签到一个 bit 位就能表示，月/年签到也能很快的表示，连续签到直接 & 即可，很简单
      • 用户登录状态：将 id 作为offset，为 1 表示上线，0表示下线，很容易获得用户是否在线，海量用户只要很小的空间

  • HyperLogLog：不精确的统计不重复元素的个数，误算率 0.81%

    • 计算基数所需的内存空间总是固定并很小，非常省空间
    • 常用于统计如日活、UV等不需要很准确的场景

  • GEO：存储地理位置信息

    • 使用的 sorted Set 集合类型
    • 应用场景：滴滴叫车

Redis 数据结构 ​

Redis 为什么那么快？

  • 内存数据库，所有操作都在内存上进行
  • 使用了高效的数据结构

哈希 ​

  • key 就是字符串对象，而 value 可以是字符串对象，也可以是集合数据类型的对象，比如 List 对象
  • Redis 使用一个「哈希表」保存所有键值对，哈希桶存放的是指向键值对数据的指针（dictEntry*），保存了 void * key 和 void * value 指针，分别指向了实际的键对象和值对象。
    • 其实有两个，另一个是更新时使用
    • Redis采用链式哈希解决哈希冲突，每一个元素有一个 next 指针指向下一个元素
      • 因为红黑树比较复杂，节点比直接链表节点占用内存也要搞
    • 其中 dictEntry 是一个联合体 v，如果值对象是整数或者浮点数，不需要指针，直接内嵌在结构体内，可以节省空间

rehash ​

正常服务只会用到「哈希表 1」，当容量不够时触发了 rehash 操作，这个过程分为三步：

  • 给「哈希表 2」分配空间，一般会比「哈希表 1」大 2 倍；

  • 将「哈希表 1」的数据迁移到「哈希表 2」中；

    • 直接迁移如果数据量非常大，会涉及大量的数据拷贝，对 Redis 造成阻塞
    • 渐进式 rehash：每次增删改查，会执行操作并迁移数据，慢慢的会将表 1 的数据迁移到表 2
      • 新增操作，都只保存在表 2
      • 可以配合闲时迁移，加快进度
      • 但是增删改查会先在表 1 查，没有就到表 2，会复杂度略高

  • 迁移完成后，「哈希表 1」的空间会被释放，并把「哈希表 2」设置为「哈希表 1」，然后在「哈希表 2」新创建一个空白的哈希表，为下次 rehash 做准备。

  • 触发条件：r = 节点数量/哈希表数量

    • 一般如果 r >= 1 就会开始进行迁移，前提是如果没有 RDB 或者 AOF 任务
    • 如果 r > 10 ，表明冲突严重，无论有没有日志任务都会迁移

  • flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在说明区别之处。

    • 灵活保存不同大小的字符串，从而有效节省内存空间。

quicklist ​

双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

quicklist 通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

quicklist 结构设计 ​

quicklist 的结构体跟链表的结构体类似，都包含了表头和表尾，区别在于 quicklist 的节点是 quicklistNode。

quicklistNode 结构体里包含了前一个节点和下一个节点指针，这样每个 quicklistNode 形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表，所以 quicklistNode 结构体里有个指向压缩列表的指针 *zl。

我画了一张图，方便你理解 quicklist 数据结构。

在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。

quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题。

listpack ​

压缩列表连锁更新的问题，来源于它的结构设计，所以要想彻底解决这个问题，需要设计一个新的数据结构，而quicklistNode 还是用了压缩列表来保存元素，并没有完全解决这个问题。

于是，Redis 在 5.0 新设计一个数据结构叫 listpack，目的是替代压缩列表，它最大特点是 listpack 中每个节点不再包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

listpack 结构设计 ​

listpack 采用了压缩列表的很多优秀的设计，比如还是用一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采用不同的编码方式保存不同大小的数据。

我们先看看 listpack 结构：

listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量，然后 listpack 末尾也有个结尾标识。图中的 listpack entry 就是 listpack 的节点了。

每个 listpack 节点结构如下：

主要包含三个方面内容：

  • encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码；
  • data，实际存放的数据；
  • len，encoding+data 的总长度；
    • 通过累加每个节点的len字段值来回溯到前一个节点的起始位置。压缩列表只保存前一个数据的长度，没有保存当前数据的长度，插入的时候只有插入的元素需要变化长度

可以看到，listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

延迟队列 ​

基于 Redis 实现延时任务：

  • Redis 过期事件监听
    • Redis 发布订阅中有 channel，类似于消息队列的 topic
    • 有一个过期事件的 channel，如果一个 key 过期，就会发布一个 key 过期时间到这个 channel，通过监听这个 channel 就能实现延迟任务
    • 缺点：
      • 时效性差：一个过期 key 不会立刻被删除，如果惰性删除或者定期删除，就会出现消费延迟
      • 丢消息：发布订阅不支持持久化，宕机会丢消息
      • 重复消费：发布订阅只有广播模式，所有消费者都会收到消息，导致重复消费
  • Redisson 内置的延时队列
    • edisson ：开源的 Java 语言 Redis 客户端，提供了如多种分布式锁的实现、延时队列
    • 延迟队列：RDelayedQueue，基于 Redis 的 SortedSet 来实现，通过分数权重对应过期时间实现。
    • 由于 redis 具有持久化，宕机了也没关系
    • 多个客户端从一个目标队列中获取任务，不存在重复消费

正在精进

Copyright © 2025 菜鸟