数据结构

12,237 字41 分钟interview-questions

数据结构

Redis 有哪些数据类型，使用场景分别是什么？

常见的有 string、hash、list、set、zset 五种数据类型

five-common-redis-data-structure

后续随着版本更新，新增了 BitMap、HyperLogLog、GEO、Stream 等数据类型

使用场景如下：

  • String
    • 缓存对象
    • 常规计数
    • 分布式锁
    • 共享 session 信息
  • List
    • 消息队列
      • 生产者需要自行实现全局唯一 id
      • 不能以消费组形式消费数据
  • Hash
    • 缓存对象
    • 购物车
  • Set
    • 聚合计算（并集、交集、差集）场景
      • 点赞
      • 共同关注
      • 抽奖
  • ZSet
    • 排序场景
      • 排行榜
      • 电话
      • 姓名排序
  • BitMap
    • 二值状态统计的场景
      • 签到
      • 判断用户登录状态
      • 连续签到用户总数
  • HyperLog
    • 海量数据基数统计的场景
      • 百万计网页 UV 计数
  • GEO
    • 存储地理位置信息的场景
      • 网约车
  • Stream
    • 消息队列
      • 会自动生成全局唯一消息 id
      • 支持以消费组形式消费数据

关于底层的数据结构实现，List 使用的是 quicklist，Hash 和 ZSet 使用的是 listpack，Set 使用的是哈希表或整数集合（如果集合中的元素都是整数并且元素个数小于 512，默认值就是 512，由 set-maxintset-entries 配置，就会使用整数集合，否则就使用哈希表）

Redis 的键值对数据库是怎么实现的？

Redis 键值对中的键是字符串对象，值可以是五种常见的数据类型中的任意一种，Redis 使用哈希桶来保存所有键值对，让我们可以用 O(1) 的时间复杂度来进行键的查找、插入和删除操作

哈希桶存放的是指向键值对的指针，键值对的数据结构中保存的也不是数据本身，而是分别指向实际的键对象和值对象的指针

redis-object-data

键值对的数据结构保存的节点我们称为 dictEntry，它包含了键对象指针 void* key 和值对象指针 void* value，它们指向的都是 Redis 对象，由 redisObject 结构体表示，里面包含 type，标识对象类型，encoding，标识对象的编码方式，ptr，指向底层数据结构的指针

SDS 是什么？

SDS （Simple Dynamic String，简单动态字符串）是 Redis 自定义实现的一种字符串数据结构，它解决了 C 语言字符串的缺陷

C 语言的字符串其实就是一个字符数组，最后一个字符由 \0 来标识字符串结束，这会导致如果字符串有 \0 字符本身时，字符串就会被截断，不能保存图片、音频和视频这样的二进制数据，并且获取字符串长度的时间复杂度也是 O(n)，需要遍历整个字符串来计算长度，另外 C 语言标准库中对字符串的操作函数也是不安全的，例如 strcat 这个函数，它可以将两个字符串拼接在一起，但由于 C 语言字符串不会记录自身的缓冲区大小，这个函数就会假定执行时已经为拼接后的字符串分配了足够的内存空间，如果实际空间不够，就会导致缓冲区溢出，造成程序崩溃，而且这个函数本身时间复杂度也很高

于是 Redis 封装了结构如下的 SDS：

sds-data-structure

其记录了字符串长度和分配给字符数组的空间长度，在修改字符串时就可以计算出剩余的空间大小，在判断出缓冲区大小不够时会自动扩容，如果所需的 SDS 长度小于 1 MB，就翻倍扩容，否则就线性扩容 1 MB，从而避免缓冲区溢出的问题，除了分配修改所必要的数据，还会分配额外的未使用空间，来减少内存分配次数，避免了手动修改 SDS 空间大小

SDS 获取字符串长度的时间复杂度是 O(1)，字节数组是用来保存实际数据的，并且因为 SDS 不需要以 \0 来标识字符串结束，所以它可以保存二进制数据，Redis 所有的字符串操作 API 也都是以处理二进制数据的方式来处理 SDS 的数据

flags 标识的则是使用的 SDS 类型，区别在于变量使用的数据类型不同，能够灵活保存不同大小的字符串，使用专门的编译优化来节省内存空间，它会让编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐，从而有效节省内存空间

alignment-alloc compact-alloc

Redis 里是怎么实现链表的？

Redis 中的 List 对象的底层实现之一就是链表，使用的是双向链表，在 listNode 结构体的基础上又封装了一层 list 结构，操作起来比较方便

redis-linked-list

Redis 的链表是无环链表，每个节点都可以很方便地获取其前置和后置节点，还保存了表头和表尾节点、节点数量，通过 void* 指针来保存节点值，可以保存任意类型的数据，但每个节点之间的内存是不连续的，也就是没办法很好地利用 CPU 缓存，另外内存开销也比较大，所以在数据量比较少的情况下 Redis 的 List 对象会使用 ziplist 压缩列表来保存数据，ziplist 在后续版本被 listpack 取代

ziplist 压缩列表是什么？

压缩列表是 Redis 中占用一块连续内存空间的紧凑型数据结构，是由连续内存块组成的顺序型数据结构，会记录其占用的内存字节数、尾节点偏移量和节点数量等属性

ziplist

在查找除了第一个元素和最后一个元素以外的时间复杂度都是 O(n)，因为需要从头节点或尾节点开始遍历，直到找到目标节点为止，其内部节点记录了前一个节点的长度、节点数据的编码方式和节点数据本身，会根据数据大小和类型进行不同的空间大小分配

ziplist 还有一个很严重的问题就是连锁更新，在新增或修改某个元素时，如果空间不足，ziplist 占用的内存空间就需要重新分配，这可能导致后续元素的 prevlen 的占用空间发生变化，导致每个元素的空间都要重新分配

chain-update1

如果前一个节点的长度小于 254 字节，那么 prevlen 就只需要占用 1 个字节，如果大于等于，就需要占用 5 个字节

chain-update2

内存的重新多次分配会直接影响到压缩列表的访问性能，所以虽然这种紧凑的内存布局可以节省内存开销，但如果保存的元素数量增加或变大了，就会带来连锁更新这样的问题，因此它只用于保存节点数量不多的场景，在 Redis 7.0 版本之后被 listpack 彻底取代

Redis 里是怎么实现哈希表的？

哈希表在 Redis 中是一个数组，数组里的元素是哈希桶，每个元素都是一个指向哈希表节点的指针，哈希表节点使用 dictEntry 结构体表示，包含了键对象指针 void* key、值对象指针 void* value 和指向下一个节点的指针 dictEntry* next，用于解决哈希冲突，其中值部分可以是一个指向实际值的指针，也可以是一个整数值或浮点数值，这样可以节省内存空间

hash-table

当一个键值对的键经过哈希函数计算后得到哈希值，再取模计算，就能得到值对应的是第几个哈希桶，如果这时有两个及以上的键被分配到了同一个哈希桶上时，就会发生哈希冲突

Redis 使用链式哈希的方法来解决这个问题，每个哈希表节点都有一个 next 指针用于指向下一个节点，当发生哈希冲突时，就会将新的键值对插入到对应哈希桶的多个节点组成的单向链表中

hash-conflict

在实际使用哈希表时，Redis 还会额外定义一个哈希表，方便进行 rehash

two-hash-tables

在正常服务阶段，插入的数据都会写入到哈希表 1，哈希表 2 并不会被分配空间，直到触发 rehash，会先给哈希表 2 分配哈希表 1 两倍的空间，然后逐步将哈希表 1 里的数据迁移到哈希表 2 中，迁移完成后就将哈希表 1 释放掉，并将哈希表 2 赋值给哈希表 1

rehash

为了避免在迁移时数据拷贝对 Redis 性能的影响，Redis 采用了渐进式 rehash 的方式，在每次对哈希表进行读写操作时，除了执行对应的操作以外，Redis 都会顺便迁移相对应索引的数据到另一张哈希表上，这样就能将 rehash 的开销分摊到多次读写操作中，避免一次性迁移带来的性能问题，在迁移过程中，哈希表 1 不会进行任何写入操作，查找则会先在哈希表 1 找，如果没有找到再去哈希表 2 找

rehash 的触发条件跟负载因子有关，负载因子 = 哈希表已保存节点数量 / 哈希表大小，当负载因子大于等于 1 时，并且 Redis 没有在执行 bgsave 或 bgrewriteaof 命令，也就是 RDB 快照或 AOF 重写这种持久化操作时，就会触发 rehash，或者当负载因子大于等于 5，无论有没有在执行持久化操作，都会强制触发 rehash

Redis 里是怎么实现整数集合的？

整数集合是 Set 对象的底层实现之一，它本质上是一块连续的内存空间，包括 encoding、length 和保存元素的数组，encoding 标识保存的整数类型，可以是 16 位、32 位或 64 位整数，length 标识保存的整数个数，数组部分则是实际保存的整数值

整数集合有一个升级规则，当插入的整数值超出当前 encoding 能表示的范围时，就会将整个整数集合升级为更大范围的 encoding，例如从 16 位升级到 32 位，或者从 32 位升级到 64 位，它并不会重新分配一个新类型的数组，而是直接在原有的内存空间上进行扩展，然后将原有的整数值转换为新的 encoding 类型保存到扩展后的内存空间中

integer-upgrade

这样做的好处是可以节省内存资源，但它是不支持降级操作的

Redis 里是怎么实现跳表的？

跳表是 ZSet 对象的底层实现之一，它是由多层有序链表组成的，最底层是一条完整的有序链表，保存了所有节点，上层的链表则是对下层链表的抽样索引，可以加快查找速度，跳表的节点使用 zskiplistNode 结构体表示，包含了节点的值、权重值、后向指针和 level 数组，level 数组中保存的是每层的前向指针和跨度

skip-list

level 数组中的每个元素表示跳表的一层，包含 forward 前向指针和 span 跨度，forward 指针指向当前层的下一个节点，span 跨度表示从当前节点到下一个节点之间跨越了多少个底层节点，在查找某个节点时，通过将沿途访问过所有层的节点的跨度累加起来，就能计算出该节点在底层链表中的排位，跳表结构体里除了包含头尾节点和长度，还包含了当前跳表的最大层数

在查询一个节点时，跳表会从头节点的最高层开始逐层遍历，比较当前节点的下一个节点的权重值和目标节点的权重值，如果下一个节点的权重值小于目标节点的权重值，就继续沿着当前层向前遍历，直到找到一个节点的下一个节点的权重值大于等于目标节点的权重值或当前节点的 SDS 类型数据大于要查找的数据时，就会下降到下一层，继续重复这个过程，直到到达底层链表

跳表相邻两层节点最理想的数量是 2:1，查询的平均时间复杂度是 O(log n)，但 Redis 在创建节点时会生成范围为 0~1 的随机数，如果随机数小于 0.25，就会增加一层，然后继续生成下一个随机数，直到随机数大于等于 0.25 或达到最大层数为止，但一般来说在创建跳表头节点时，会直接创建最大层高，在 7.0 版本之后，最大层数是 32 层

ZSet 的实现之所以用跳表而不是平衡树，比如 AVL 树或者红黑树，是因为从内存占用的角度，跳表会比平衡树更加灵活，每个节点平均包含的指针数量更少，内存开销更小，并且在做范围查找时，跳表的操作会更简单高效，在平衡树上找到指定范围的节点后，还需要通过中序遍历来获取范围内的所有节点，如果不对平衡树进行改造，那这里的中序遍历并不容易实现，而跳表只需要找到范围的起点，然后顺着底层链表向后遍历就可以了，另外从算法实现难度上比较，跳表的实现也要比平衡树简单很多，跳表只需要修改相邻节点的指针，而平衡树在插入或删除节点时，可能会涉及到多次旋转操作和子树的调整

quicklist 和 listpack 分别是什么，有什么作用？

在 Redis 3.2 版本之前，List 底层的实现方式会根据数据量自动切换，当元素少并且小的时候会使用 ziplist 压缩列表，它的内存是连续的，可以节省内存空间，但修改数据时，特别是中间插入，会导致昂贵的内存重新分配和连锁更新问题，当数据量很大时则会使用双向链表，修改效率比较高，但每个节点都需要额外的指针，内存开销极大，甚至可能超过数据本身，并且节点在内存中并不连续，任意产生内存碎片

quicklist 的出现就是为了融合两者的优点，保留双向链表头尾插入删除的高效的同时，利用 ziplist 的内存紧凑特性来节省内存空间，我们可以把它想象成一列火车，火车的整体是一个双向链表，每节车厢是一个节点，车厢内部是一个 ziplist，存放具体的数据元素

quicklist-data-structure

quicklist 会通过控制每个链表节点中压缩列表的大小或元素个数来解决连锁更新的问题，它的结构体会包含头节点、尾节点、节点数量和总元素数量等属性，quicklist 节点结构体会包含前后节点指针、指向 ziplist 的指针、压缩列表数据和元素个数等属性

quicklist 会限制每个节点里的 ziplist 能存储数据的大小，可以通过 list-max-ziplist-size 配置项来设置，负数表示限制字节大小，正数表示限制每个节点中元素的个数，另外 quicklist 还会做节点压缩，因为 List 的典型使用场景通常是队头队尾操作，中间数据访问频率相对较低，list-compress-depth 配置项可以设置压缩的深度，默认值是 0，表示不压缩，设置为 1 表示头尾各保留一个节点不压缩，其他节点都压缩，设置为 2 表示头尾各保留两个节点不压缩，其他节点都压缩，以此类推

在插入时，quicklist 会先检查插入位置的 ziplist 是否还有空间，有的话就直接在对应的 ziplist 里插入数据，如果没有空间了，就会新建一个 ziplist 节点，然后将其插入到 quicklist 的合适位置

虽然 quicklist 解决了链表内存过大的问题，但它内部使用的 ziplist 还有一个连锁更新的性能缺陷，由于它把多个元素存储在一块连续的内存中，为了能双向遍历，ziplist 每个节点都会记录前一个节点的长度 prevlen，如果前一个节点的长度小于 254 字节，那么 prevlen 就只需要占用 1 个字节，如果前一个节点的长度大于等于 254 字节，那么 prevlen 就需要占用 5 个字节

如果一个 ziplist 里有一排连续的节点的长度都在这个边界值附近，当我们把第一个节点的数据改大了一些，超过了阈值，导致长度增加了 4 字节，第二个节点发现前一个节点变大了就也会扩展自己的 prevlen，以此类推，导致后续所有节点都需要重新分配内存并移动数据，这就是连锁更新的性能缺陷，在数据量大时它会导致 redis 服务器卡顿

于是 Redis 引入了 listpack，它保留了 ziplist 使用一整块连续的内存空间来紧凑地保存数据、支持双向遍历的优点，但移除了 prevlen 字段，切断了节点之间的依赖关系，彻底避免了连锁更新的问题

listpack-data-structure

它把存储前一个节点的长度改成了存储自身的长度在节点尾部，再通过一种特殊的变长编码方式可以从后往前解析出数值，从而实现双向遍历，listpack 还引入了新的编码方式来进一步节省内存空间，在 Redis 7.0 版本之后彻底代替了 ziplist 成为紧凑型数据的唯一标准，List、Hash、ZSet 和 Stream 都有使用 listpack 来存储紧凑型数据

String 在 Redis 中底层的实现方式是什么样的？

String 是最基本的键值对结构，它的值除了字符串以外也可以是整数或浮点数，值最多可以容纳的数据长度是 512 MB

底层的数据结构使用的主要是 int 和 SDS（Simple Dynamic String，简单动态字符串），它和 C 字符串不太一样

SDS 不仅可以保存文本数据，还可以保存二进制数据，它使用 len 属性的值而不是空字符串来判断字符串是否结束，并且它所有的 API 都会以处理二进制的方式来处理其存放在 buf[] 数组里的数据，所以它除了能存放文本数据以外，还可以保存图片、音频、视频和压缩文件这样的二进制数据

SDS 获取字符串长度的时间复杂度是 O(1)，因为它用 len 属性记录了字符串长度，并且 Redis 的 SDS API 是安全的，拼接字符串不会造成缓冲区溢出，因为它在拼接之前会检查 SDS 空间是否满足要求，如果空间不够就会自动扩容

字符串对象的内部编码有 int、raw 和 embstr 三种

string-encoding

如果一个字符串对象保存的是整数，并且这个整数可以用 long 类型来表示，字符串对象就会将其保存在字符串对象结构的 ptr 属性里，将 void* 转换成 long，并且将字符串对象的编码方式设置为 int

string-int-encoding

如果保存的是字符串，并且长度小于等于一定阈值，就会使用 SDS，将编码设置为 embstr，这是一种专门用于保存短字符串的优化编码方式

string-embstr-encoding

如果保存的是字符串，并且长度大于一定阈值，就会使用 SDS，将编码设置为 raw

string-raw-encoding

embstr 和 raw 的编码阈值边界在不同的 Redis 版本里是不一样的，它们都会使用 SDS 来保存字符串，但 embstr 会通过一次内存分配函数来分配一块连续的内存空间来保存字符串对象结构和 SDS 字符串数据，而 raw 则是分开两次调用来分别分配两块内存空间存储对象结构和 SDS 字符串数据

这样做可以降低 embstr 的内存分配次数和释放内存次数，也可以更好地利用 CPU 缓存提升性能，因为被保存在一块连续的内存中，但如果字符串的长度增加需要重新分配内存，整个对象结构和 SDS 就要被重新分配空间，所以 embstr 编码的字符串对象实际上是只读的，当我们对其执行任何修改命令时，Redis 会将其重新编码为 raw 编码，然后再执行修改命令

字符串的常用指令如下：

string-common-commands

主要的应用场景有缓存对象、常规计数、分布式锁、共享 session 信息等，String 可以直接缓存整个对象的 JSON，例如 SET user:1 '{"name":"Alice","age":30}'，也可以将 key 分离，例如 MSET user:1:name "Alice" user:1:age 30，然后使用 MGET 获取不同属性的值

因为 Redis 是单线程处理命令，执行命令的过程是原子的，所以 String 适合计数场景，比如计算访问次数、点赞、转发、库存数量等，例如：

INCR page:view:count
INCR post:123:like:count
DECR product:456:stock
GET product:456:stock

也可以用作分布式锁，通过 SET 命令的 NX 参数实现 key 不存在时才插入的功能，再加上过期时间，例如 SET lock_key unique_value NX PX 30000，表示设置一个锁，锁的 key 是 lock_key，锁的值是 unique_value，只有当 lock_key 不存在时才会设置成功，并且锁的过期时间是 30 秒，解锁的过程就是把这个键值对删除，但要注意只能删除加锁的客户端标识的键值对，解锁时要用 Lua 脚本来保证原子性，例如：

if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

最后的共享 Session 信息是指，在分布式系统中，多个应用服务器需要共享用户的 Session 信息，而不是让用户每次都重复登陆，我们可以用 Redis 来对其进行统一的存储和管理，这样无论请求发送到哪台服务器，都会通过同一个 Redis 获取相关的 Session 信息

shared-session

List 在 Redis 中底层的实现方式是什么样的？

List 列表是简单的字符串列表，按照插入顺序排序，可以在头部或尾部添加元素，它的底层实现是 quicklist，常用命令如下：

list-common-commands

List 主要的应用场景是消息队列，消息队列在存取消息时必须满足保证顺序、处理重复的消息和保证消息可靠性这三个需求，List 本身就是按照先进先出的顺序来存储数据的，可以通过 LPUSH 命令在队列头部插入消息，通过 RPOP 命令在队列尾部取出消息，保证了消息的顺序性

list-message-queue1

但生产者在往 List 中写入数据时，并不会主动通知消费者有新消息写入，而是需要消费者一直调用 RPOP 命令来轮询获取消息，这样会带来不必要的性能损失，于是 Redis 提供了 BRPOP 命令来实现阻塞式的消息获取，消费者在调用这些命令时，如果队列中没有消息，就会阻塞等待，直到有新消息写入队列才会返回

brpop-queue

List 也不会为每个消息生成 ID 号，所以我们需要自行为每个消息生成一个全局唯一 ID 来让消费者比对判断当前收到的消息是否已经处理过，另外当消费者从 List 里读取一条消息之后，List 就不会再保存这条消息了，如果消费者在处理消息时出现宕机等异常情况，导致消息没有被成功处理，那这条消息就会丢失，无法保证消息的可靠性，于是 Redis 提供了 RPOPLPUSH 命令来解决这个问题，它可以将消息从源队列尾部弹出并推入到另一个临时队列的头部，这样即使消费者在处理消息时出现异常，消息也不会丢失，还保存在临时队列中，等消费者恢复之后，可以从临时队列中继续处理未完成的消息

但 List 不支持多个消费者消费同一条消息，也不支持消费组的实现，所以后续 Redis 引入了 Stream 数据类型来更好地支持消息队列场景

Hash 在 Redis 中底层的实现方式是什么样的？

hash 是一个键值对集合，底层是由 listpack 或哈希表实现的，如果元素个数少并且小的时候会使用 listpack 来保存数据，否则就会使用哈希表

hash-compare-string

常用命令如下：

hash-common-commands

hash 类型的 (key, field, value) 结构与对象结构体的对象 id、属性和值比较相似，其可以用来存储缓存对象，下图表示的存储可以通过 HMSET uid:1 name Tom age 15 和 HMSET uid:2 name Jerry age 13 这两个命令来保存两个用户对象的信息

redis-hash

在存储对象时，一般对象都是用 String + Json 来存储，但对象中某些频繁变化的属性就可以考虑抽出来用 Hash 类型来存储

hash 也可以应用在购物车场景，主要涉及以下命令：

  • 添加商品：HSET cart:user_id product_id quantity
  • 添加数量：HINCRBY cart:user_id product_id increment
  • 减少数量：HINCRBY cart:user_id product_id -decrement
  • 删除商品：HDEL cart:user_id product_id
  • 获取商品总数：HLEN cart:user_id
  • 获取所有商品：HGETALL cart:user_id

shopping-cart

当然，Redis 存储的只是商品 ID，在回显商品具体信息时还需要用商品 ID 去查询一次数据库获取完整的商品信息

Set 在 Redis 中底层的实现方式是什么样的？

Set 类型是一个无序并唯一的键值集合，它不会按照插入的先后顺序进行存储，除了集合内的增删查改以外，还支持多个集合取交集、并集和差集，和 List 的区别是 List 是可以存储重复元素，并且是按照元素的先后顺序来存储的

set-data-structure

Set 的底层数据结构是哈希表或整数集合，如果集合中的元素都是整数并且元素个数小于 512，默认值就是 512，由 set-maxintset-entries 配置，就会使用整数集合，否则就使用哈希表，常用命令如下：

set-common-commands

Set 主要的应用场景是聚合计算，例如点赞、共同关注和抽奖等场景，当存储的数据无序并且需要去重的情况下就适合用集合类型进行存储，但差并交这种集合运算的复杂度较高，在数据量较大的情况下如果直接执行就会导致 Redis 阻塞，所以一般是让从库或客户端来做聚合统计

点赞场景下，可以通过 SADD article:1 uid:1 命令来表示用户 1 给文章 1 点赞，通过 SREM article:1 uid:1 来表示用户 1 取消点赞，通过 SMEMBERS article:1 来获取文章 1 的所有点赞用户，通过 SCARD article:1 来获取文章 1 的点赞总数，通过 SISMEMBER article:1 uid:1 来判断用户 1 是否给文章 1 点过赞

共同关注场景下，可以通过 SADD uid:1 5 6 7 8 9 命令来表示用户 1 关注的 ID 为 5、6、7、8、9，通过 SINTER uid:1 uid:2 来获取用户 1 和用户 2 的共同关注列表，通过 SDIFF uid:1 uid:2 来获取用户 1 关注但用户 2 没有关注的用户列表，通过 SISMEMBER uid:1 5 来判断用户 1 是否关注了 ID 为 5 的用户

抽奖场景下，可以通过 SADD lottery:2026 uid:1 uid:2 uid:3 ... 命令来表示参与 2026 年抽奖的用户列表，通过 SRANDMEMBER lottery:2026 3 来随机获取 3 个中奖用户，这样可以允许重复中奖，通过 SPOP lottery:2026 1 来随机弹出 1 个中奖用户，这样就是不允许重复中奖

ZSet 在 Redis 中底层的实现方式是什么样的？

ZSet 比 Set 类型多了一个排序属性 score，所以它存储的是有序且唯一的键值对集合，底层的数据结构是由 listpack 或跳表来实现的

zset-data-structure

常用操作如下：

zset-common-commands

ZSet 主要的应用场景是排序场景，例如排行榜、电话和姓名排序等场景

排行榜场景下，可以通过 ZADD user:1:ranking 200 arcticle:1 命令来表示用户 1 的文章 1 获得了 200 个赞，通过 ZINCRBY user:1:ranking 50 arcticle:1 来表示用户 1 的文章 1 又获得了 50 个赞，通过 ZRANGE user:1:ranking 0 9 WITHSCORES 来获取用户 1 的前 10 名文章及其赞数，通过 ZREVRANGE user:1:ranking 0 9 WITHSCORES 来获取用户 1 的后 10 名文章及其赞数，通过 ZRANK user:1:ranking arcticle:1 来获取用户 1 的文章 1 在排行榜中的排名，通过 ZSCORE user:1:ranking arcticle:1 来获取用户 1 的文章 1 获得的赞数，通过 ZRANGEBYSCORE user:1:ranking 100 500 来获取用户 1 获得赞数在 100 到 500 之间的文章列表

使用有序集合的 ZRANGEBYLEX 或 ZREVRANGEBYLEX 命令可以实现电话号码或姓名的排序，通过 ZADD phone 0 13100111100 0 13110114300 0 13132110901 命令来添加电话号码，通过 ZRANGEBYLEX phone - + 来获取所有电话号码，通过 ZRANGEBYLEX phone [131 (132 来获取 131 开头的电话号码列表，通过 ZADD name 0 "Alice" 0 "Bob" 0 "Charlie" 命令来添加姓名，通过 ZRANGEBYLEX name - + 来获取所有姓名，通过 ZRANGEBYLEX name [B [D 来获取 B 到 D 开头的姓名列表

BitMap 在 Redis 中底层的实现方式是什么样的？

BitMap 是一串连续的二进制数组，称为位图，它可以通过偏移量 offset 定位元素，通过最小的单位 bit 来进行 0 和 1 的设置，表示某个元素的值或状态，它非常节省空间，特别适合一些数据量大且使用二值统计的场景，它的底层实现是String 类型，常用命令如下：

bitmap-common-commands

BitMap 的应用场景主要是二值状态统计，也就是集合元素的取值只有 0 和 1，例如签到统计、判断用户登录态和连续签到用户总数等场景

在签到统计场景下，每个用户签到的天数对应 bit 的位数，可以通过 SETBIT uid:sign:100:202206 2 1 命令来表示用户 100 在 2022 年 6 月的第 3 天签到过（偏移量从 0 开始），通过 GETBIT uid:sign:100:202206 2 来判断用户 100 在 2022 年 6 月的第 3 天是否签到过，通过 BITCOUNT uid:sign:100:202206 来获取用户 100 在 2022 年 6 月的总签到天数，通过 BITPOS uid:sign:100:202206 0 来获取用户 100 在 2022 年 6 月第一次未签到的日期

在判断用户登录态场景下，海量用户只需要非常小的内存空间就能保存登录状态，可以通过 SETBIT login_status 1001 1 命令来表示用户 1001 已登录，通过 GETBIT login_status 1001 来判断用户 1001 是否登录，通过 BITCOUNT login_status 来获取当前已登录的用户总数

在连续签到用户总数场景下，把每天的日期作为 key，userID 作为偏移量，如果打卡就将对应偏移量位置的 bit 设置为 1，这样如果要连续统计三天连续打卡用户的总数，就一共会有三个这样的 BitMap，然后通过 BITOP AND destmap bitmap:01 bitmap:02 bitmap:03 命令来对这三个 BitMap 进行 AND 操作，得到一个新的 BitMap，最后通过 BITCOUNT destmap 来获取连续三天打卡的用户总数

HyperLogLog 在 Redis 中底层的实现方式是什么样的？

HyperLogLog 是一种用于统计基数的数据集合类型，也就是统计一个集合中不重复的元素个数，但它的统计规则是基于概率完成的，误差率在 0.81% 左右，它的优点是节省内存空间，在输入元素的数量或体积非常庞大时，计算基数所需的内存空间总是固定并且很小的

但 HyperLogLog 的底层实现过于复杂，这里就不展开介绍了，常用命令如下：

hyperloglog-common-commands

它的主要应用场景是百万级的网页 UV（Unique Visitors） 计数，它只需要花费 12 KB 内存，就可以计算接近 2^64 个元素的基数，统计时可以通过 PFADD page:uv user1 user2 user3 ... 命令来添加用户，通过 PFCOUNT page:uv 来获取网页的独立访客数量

GEO 在 Redis 中底层的实现方式是什么样的？

GEO 是用来存储地理位置信息的数据类型，它底层直接使用了 ZSet 来实现，通过 GeoHash 编码方式实现了经纬度到分值 score 的映射，其中的两个关键机制就是对二维地图做区间划分和对区间进行编码

我们可以通过 GEOADD city:location 116.407526 39.90403 "Beijing" 命令来添加地理位置信息，通过 GEOPOS city:location "Beijing" 来获取北京的经纬度，通过 GEODIST city:location "Beijing" "Shanghai" km 来获取北京和上海之间的距离，通过 GEORADIUS city:location 116.407526 39.90403 500 km WITHCOORD WITHDIST 来获取以北京为中心，半径 500 公里范围内的所有城市信息,主要应用场景就是打车或者地图、外卖等场景下的地理位置存储和查询

Stream 在 Redis 中底层的实现方式是什么样的？

Stream 是 Redis 专门为消息队列设计的数据类型，它支持消息的持久化、全局唯一 ID 自动生成、ACK 确认消息机制和消费组模式等功能

常用命令包括 XADD 插入消息的同时保证有序并自动生成全局唯一 ID，XLEN 查询消息长度，XREAD 按 ID 读取数据消息，XDEL 根据消息 ID 删除消息，XRANGE 按 ID 范围查询消息，XREADGROUP 从消费组中读取消息，XPENDING 查看每个消费组中所有消费者已读取但未确认的消息，XACK 确认消息已被消费等

例如通过 XADD mymq * name ethan 命令来向消息队列 mymq 中添加一条消息，消息内容是 name=ethan，* 表示让 Redis 自动生成全局唯一 ID，这个命令会返回由两部分组成的全局唯一 ID 1624512345678-0，前半部分是数据插入时以毫秒为单位计算的当前服务器时间，后半部分是同一毫秒内的序列号，如果在同一毫秒内插入多条数据，序列号会依次递增，消费者在通过 XREAD STREAMS mymq 1624512345678-0 命令读取消息时，可以指定消息 ID，Redis 会从这个 ID 的下一条消息开始读取，也可以在调用 XREAD 命令时设定 BLOCK 配置项，实现类似于 BRPOP 的阻塞式读取消息功能

Stream 可以通过 XGROUP CREATE mymq mygroup 0-0 命令来创建一个消费组 mygroup，0-0 表示从消息队列的第一条消息开始消费，消费者可以通过 XREADGROUP GROUP mygroup consumer1 STREAMS mymq > 命令来从消费组 mygroup 中以消费者 consumer1 的身份读取消息，> 表示从第一条没有被消费的消息开始读取，消息一旦被一个消费者读取，就不能被同一个消费组内的其他消费者读取了，但只要在创建消息组时，不同消费组指定了相同位置开始读取消息，那不同消费组的消费者就可以消费同一条消息，使用消费组的目的就是让组内的多个消费者共同分担读取消息，让负载在多个消费者之间均衡分配

Stream 会自动使用内部队列 PENDING List 来保存每个消费组中所有消费者已读取但未确认的消息，直到消费者使用 XACK 命令通知 Stream 消息已经处理完成，这种消费确认的机制增加了消息的可靠性，消费者在重启后可以通过 XPENDING mymq mygroup 命令来查看当前消费组 mygroup 中所有消费者已读取但未确认的消息列表，然后继续处理这些未确认的消息，避免消息丢失

message-handling

一个消息队列主要分为生产者、消息队列和消费者三个部分，Redis Stream 实现的消息队列可以保证生产者和消费者端都不会丢失消息，因为生产者本身可以处理异常情况，只要能收到 MQ 中间件的 ACK 确认响应就表示发送成功，如果异常重发就可以了，而消费者则可以通过内部队列实现确认机制，也能保证消息的不丢失

message-queue

但 Redis 作为消息中间件本身是没办法保证消息不丢失的，例如 AOF 持久化配置为每秒写盘时，写盘过程是异步的，如果宕机就可能丢失数据，主从复制本身也是异步的，主从切换时也存在丢失数据的可能，并且 Redis 的数据都存储在内存中，一旦发生消息积压，就可能出现 OOM 问题，所以 Stream 提供了可以指定队列的最大长度的功能，这会导致队列长度超过上限后，旧消息会被删除

而像 RabbitMQ 和 Kafka 这样的专业消息中间件则是在使用时部署一个集群，生产者在发布消息时队列中间件会写多个节点，从而形成多个副本，即使某个节点挂了集群的数据也不会丢失，并且它们的数据都是存储在磁盘上，不会有内存不足的问题

所以如果业务场景比较简单，对于数据丢失也不是特别敏感，消息积压概率也比较小的情况下，就可以使用 Redis Stream 来实现消息队列功能，但 Redis 的发布/订阅机制（Pub/Sub）没有基于任何数据类型实现，不具备数据持久化的能力，而且是发后即忘的工作模式，如果订阅者离线重连是不能消费之前的历史消息的，另外如果有一定的消息积压，消费端是会被强行断开的，所以它只适合即时通讯的场景，比如构建哨兵集群

目录