Redis 简介

2020-01-30
11 min read
techs

数据结构

基础数据结构

Redis 可以为数据设置过期时间，但这个过期时间是以对象为粒度的。比如我们可以为一个 hash 对象设置过期时间但不能为 hash 对象的某一个键值对设置过期时间。重新 set 会使得已设置的过期时间失效

  • SDS
    • 字符串、整数、浮点数、位图
      • 因为位图由 SDS 实现，所以位图也可以使用字符串的指令进行操作。位图也由自身的特有命令，例如：bitfield
    • GET/SET/DEL
  • 容器类，drop if empty
    • List，具体实现和 C++ 中的 deque 是类似的
    • Set
    • ZSet，skiplist
      • (score, value) 集合
    • Hash
      • redis 中的 rehash 是渐进式的，新的 hash 表和旧的哈希表在 rehash 过程同时存在

通信协议 RESP

redis 客户端和服务端使用的协议是 RESP (REdis Serialization Protocol)，cluster 场景下不同实例间的通信协议与 RESP 不同。RESP 也在不断的进化中，下面以 RESP3 为例做简单的介绍

RESP 的优点是协议不需要使用工具进行转化就可以阅读，但其也有一些缺点，比如：

  1. 无法表述数据的类型，RESP 只能使用数组表示集合类数据类型，使用 RESP 无法识别数据的原始类型 set/map/list
  2. 无法返回二进制兼容的错误信息且错误信息字符串中不能包含换行
  3. RESP 没有类似于整型的浮点数据结构，浮点使用字符串进行传输；布尔类型也使用整数进行传输

大部分场景下 RESP 都是简单的 request-response，不过下面两个场景需要额外注意

  1. pipeline
  2. 客户端与服务端的订阅/推送通道

格式说明

  • 客户端和服务器发送的命令或数据一律以 \r\n （CRLF）结尾 ，且所有参数都是二进制安全的
  • RESP 协议的不同部分也使用 \r\n 进行分隔

Request-response

在简单的交互模式下，客户端只会向服务端发送由 Bulk String 组成的数组；服务器端则可能返回下面任意类型的数据

  1. 简单字符串，数据的首字母为 +
    1. 非二进制安全，可以使用 Bulk String 传输二进制串；不能包含 \r 或者 \n
    2. 例如 set 命令设置成功后，server 将返回 +OK\r\n
  2. Errors，- ，示例，-false\r\n
    1. 除了起始的减号，Errors 和简单字符串属性几乎一样
  3. 整数，: ，示例，:999\r\n ，redis 保证返回的整数可以用 int64 表示
    1. redis 中很多命令会返回整数，比如 INCR
    2. 很多命令使用 1 表示执行成功，0 表示执行失败
  4. Bulk String，$，NULL 值可以使用 Bulk String 表示，空串：$0\r\n\r\n
    1. Bulk String 主要用于保存长度不超过 512MB 的二进制字符串
    2. $6\r\nfoobar\r\n，Bulk String 由若干部分组成
      1. 二进制串长度，这里是 6
      2. \r\n 之后即为实际数据
    3. Bulk String 可以表示 NULL：$-1\r\n
  5. 数组，* ，客户端使用 RESP 中的数组向服务端传输命令，RESP 数组中的元素类型可以不同
    1. 示例：*2\r\n$3\r\nfoo\r\n$3\r\nbar\r\n
    2. 数组为空的表示：*0\r\n；NULL 数组：*-1\r\n

客户端与服务端示例

client 发送 LLEN mylist ：*2\r\n$4\r\nLLEN\r\n$6\r\nmylist\r\n

server 返回值：:48293\r\n

inline command

redis 支持 telnet 连接与操作，简单的命令可以直接使用 telnet 进行操作；复杂的命令使用 telnet 进行操作比较麻烦，因为像传输数组，需要自行构造满足 RESP 要求的命令

Pipeline

虽然 pipeline 可以减少 RTT，但同时海量的操作，redis 会消耗大量的内存。使用 pipeline 时 redis 会记录每一个子请求的 reply 从而消耗比一次请求更多的内存

pipeline 比分次请求速度快的原因有如下几个：

  1. 减少 RTT（Round Trip Time）
  2. 减少系统函数的调用，pipeline 是集合所有 reply 后调用一次系统调用向客户端发送消息

典型应用

示例

分布式锁

相对于 ZooKeeper 等工具，Redis 并不是为分布式锁而设计的，所以在特殊场合下还是使用 ZK 比较好

Redis 能用于锁的原因在于 Redis 的单线程模型，直接使用 setnx（set if not exists）设置变量，如果设置成功则表示加锁成功

需要考虑死锁的问题，例如已经加锁的业务崩溃了，这样会造成其他业务无法获得锁，一个解决办法是为锁变量设置超时时间

set lock_name true ex 5 nx # set 支持 ex 子命令，设置变量的同时设置过期时间

为了避免某个业务设置的锁被其他业务释放，上面的命令可以使用随机变量进行改进

set lock_name <rand num> ex 5 nx # 只有当前业务知道随机值，所以避免了其他业务释放锁的可能，当然，不能恶意删除

redis 实现分布式锁的缺点比较多，但在一些简单的场景下也不失为一个不错的解决方案

队列

使用 Redis 的 List 数据结构可以实现简单的队列

  • 非阻塞： lpop/rpop
  • 阻塞：blpop/brpop
    • 在网络资源比较紧张时 Redis 会释放一些未使用的链接，部分阻塞请求可能会被断开，所以程序中需要处理这种情况
延时队列

使用 ZSet 可以实现延时队列 ，将时间设置为 ZSet 中的 key，具体数据设置为 value，从 ZSet 中获取数据时只获取满足时间要求的数据，即可实现延时队列

使用 zset 实现限流

如果一个行为在一段时间内只能发生固定的次数，则可以使用 redis 的 zset 实现限流：将 key 设置为时间戳，每次插入行为时先判断某个时间区间内的数据量

HyperLogLog

常用命令：pfadd、pfcount、pfmerge

HyperLogLog（HLL）算法使用统计方法估算基数。基数就是 DV（Distinct value）的个数。举个例子，集合 \(\{1,3,3,4,5,5,5\}\) 的基数为 4，分别为 \(\{1,3,4,5\}\)

少量数据我们一般使用 set 来计算基数，例如上面的集合，使用 C++/Java 统计时，将所有数据插入 set<int> 中，然后调用成员函数 set<int>::size() 即可实现基数统计，而且求得的是精确值

std::vector<int> data = {1,2,2,3,3,3,4,4,4,4,5,5,5,5};
std::set<int> dv_set;
for (auto& x : data) dv_set.insert(x);
std::cout << dv_set.size() << std::endl; // 5

如果数据是整型且范围有限，使用 bitmap 也可以统计基数

如果数据量非常大，使用上面两种方式都将消耗海量的存储资源，而且最终我们只需要获得基数值，实际的数据存储是没有意义的

HLL 利用统计方法，使用固定大小的内存空间来估计基数，因为基于统计学所以有一定的误差，但设置得当这个误差在 2% 以下

原理简介

HLL 的实现可以使用概率进行简单的解释。随机取一个 64bit 的 int 型整数并将其转化为二进制，这个二进制最右侧或者最左侧连续 0 的个数是满足一定概率分布的，假设一个数二进制表示下左侧连续 0 的个数为 \(n\) 那么可得：

\[p(n)=({\frac 1 2})^{n+1}, n \in \{1 \sim 63\}\\ p(n)=({\frac 1 2})^{64}, n=64 \]

随机取 \(m\) 个整数并转化为二进制数，所有样本中左侧最大连续 0 个数为 \(l\ (l<64)\) 的概率为：

\[C_{m}^{i}\left((\frac{1} {2})^{l+1}\right)^{i}\left(\sum_{0}^{l-1}\left(\frac{1}{2}\right)^{l}\right)^{m-i} \]

其中 \(i\) 表示 \(m\) 个样本中一共有 \(i\) 个左侧最大连续 0 为 \(l\) 的整数

取 \(i=1\) 已知 \(C_m^1 = m\)， 简化上述公式使用 \(x\) 替换 \(m\) 作为自由变量，可得：\(y=a \cdot x \cdot b^x, x \in [0,+\infty)\)，其中 \(a\) 和 \(b\) 皆为大于 0 小于 1 的常量。简化后的公式有全局极大值 。可以使用下面的 python 代码验证这个函数在 \(x\) 大于 0 时有全局极大值

from sympy.plotting import plot
from sympy import symbols
x = symbols('x')
p = plot(x*0.5**x,(x,0,10))

根据极大似然原理，当一件事发生时，我们认为是概率最大的那件事发生了 （即全局最大值点事件）。所以，随机取 \(m\) 个数并记录这 \(m\) 个数中左侧最大连续 0 的个数 \(l\)，使用极大似然估计法，我们可以通过 \(l\) 估算出 \(m\) 的值

HLL 就是使用 \(l\) 估算 \(m\) （基数），但朴素的方法误差比较大，HLL 通过各种手段来提高统计的精度

redis 中的 HLL 使用 \(2^{14}\) 个 6bits bitmap 分别统计子样本中最大连续 0 的个数（\(2^6\)可以表示的最大正整数为 63），所以 redis 中的 HLL 最大需要 \(2^{14} \times (\frac 6 8)\) 字节，即 12KB 的内存空间

redis 先求所有输入数据（数据类型不限，string，double等都可以）的 Hash 值（64bits，int64），不同数据的 hash 值不同即相当于随机取了一个 int64 的整数，随后利用 HLL 即可实现数据的基数统计。这说明 HLL 对 hash 也是敏感的，hash 函数必须是均衡的

其他关于基数计算的资料可以参考：Count-Distinct Problem ppt

布隆过滤器

布隆过滤器（Bloom Filter）， 利用 bitmap 和 hash 函数实现的非精确的过滤器：布隆过滤器可能对数据是否真的存在产生误判（不同的数据产生了相同的 hash 值），但数据不存在一定不会产生误判

redis 4.0 中，布隆过滤器使用插件的形式实现。可以通过配置来设定布隆过滤器的属性，比如 initial_size 参数用来设定预计放入的元素；error_rate 用来设定错误率。更低的错误率与更大的预计元素数都会提高布隆过滤器对内存的使用，可以使用在线工具预估一下布隆过滤器的内存使用情况

举个列子：预估有 1000 个数据，设定错误率为十万分之一，则需要大概 16 个 hash 函数和 2.92KB 的存储空间。如果使用的普通的存储方式，1000 个 64bits 的数据大概需要 8KB 的内存，这还不算数据结构自身的消耗，由此可见布隆过滤器对内存的节约还是很可观的

在数据量变化比较大时可以考虑传统方法和布隆过滤器的结合，比如数据量比较小时可以考虑传统数据结构（redis hash、bitmap 等），数据量逐渐增长时直至传统数据结构占用的内存空间不小于布隆过滤器时再使用布隆过滤器

布隆过滤器结合传统数据结构可以实现较为精确的过滤，以曝光队列为例（元素为 int64）：

  1. 短期曝光数据使用传统数据结构进行保存，短期数据量一般不大
  2. 长期曝光数据使用布隆过滤器，虽然有一定的误差但可以节约内存空间

如果可以接受二次曝光而不允许更多次的曝光，那么布隆过滤器之后新增一个传统数据结构再次进行过滤可以进一步提高去重的概率，即除去二次曝光，一段时间内不会出现三次曝光的可能

漏斗限流

使用 zset 实现的限流有一定的局限性，例如高并发场景下偶然的流浪涌动，使用 zset 方法将直接忽略用户的部分请求，这有时候是不合理的，比如在可接受范围内我们可以将请求延后，用时间换取一定的计算资源

漏斗算法比较形象，突然有大量请求时可以将请求保存在漏斗中，峰值消失后再逐渐处理漏斗中的数据。漏斗容量的设置需要考虑可接受的延时和系统的处理能力

redis 中的漏斗算法是使用插件实现的：Redis-Cell

GeoHash

根据康托尔的无穷大比较方法，线段、正方形和立方体内点数的多少与它们的大小无关，所以平面上的点可以映射到线段上

GeoHash 算法将平面上的点映射到线段上，并使得平面上相邻的点在目标线段上也相邻，故实现了相邻点的快速排序与查找

GeoHash 算法的实现有多种，比如“二刀法”，本文不做详细介绍，具体内容可以参考其他资料，比如这里

redis 中的 GeoHash 由 zset 实现，在存在海量数据时要考虑数据迁移的问题

Scan

redis 提供了一个查询 key 的命令：keys ，这个命令会遍历所有已有的 key ，如果 redis 中的数据量比较大时，这将造成 redis 服务的卡顿。故 redis 提供了另一个批量查询的命令：scan

redis 的 key 保存在一个全局的 hash 表中，使用 scan 命令时可以指定 hash 表中的游标位置与此次遍历 hash 表槽的个数。这里需要注意一点， hash 表的每个槽位保存的元素个数是不同的，redis 使用的是链地址法，相同 hash 值的数据会保存在相同槽对应的链表中，所以**同样是遍历 m 个槽，scan 返回的元素个数很可能不同，也可能是 0 **

scan 返回的数据可能有重复，需要客户端自行去重

Scan 的遍历顺序

scan 不是按照从0 到 1 到 2 这样依次遍历所有 hash 槽的，scan 使用的是 高位进位加法。以 3 bits 为例，遍历顺序依次为：000、100、010、110、001、101、011、111

这种遍历思想是优先遍历高槽位的数据。与低位进位法相同，高位进位法也将覆盖所有元素。高位地位进位法都不会重复访问已经遍历过的槽位，但地位进位法在槽位扩展后

redis 中的数据经过 hash 函数处理后会返回一个 64bit （或者 128bit）的整型值，根据当前 hash 表槽位总数取整型值的低若干位（故 redis 中 hash 表长度必然为 2 的幂次），hash 链表每扩容一辈，就向左多取整型值的一个 bit。由此操作，扩容前位于同一个槽内的部分数据可能会被重新分配到不同的槽中

假设扩容前 hash 表有 8 个槽位，则取 hash 值低 3bit 就可以将数据散列到这些槽中，hash 值为 0001 1011/0010 0011 的两个数据都将被散列到地址为 011 的槽中；扩容一倍，现在有 16 个槽位，需要取 hash 值的低 4 bit，则前面两个数据会被散列到 1011 和 0011 这不同的槽中，其中后者的槽位不变。这说明扩容后散列地址发生变化的元素会被散列到高位槽中

scan 使用的遍历方式可以保证扩容前后遍历元素重复的次数比较少。使用常规顺序（低位加法），一旦扩容，已经遍历过的低位元素有近一般的元素会被散列到高位，会被重复遍历

Scan 可用于容器集合

处了用于遍历所有 key ，scan 命令也可以用于容器类元素的遍历，必然 set/zset 等待

大 key 扫描

redis 中不要使用大 key（占用空间比较大的 key 元素），这会对数据的迁移造成影响。大 key 元素分配内存（回收内存）会影响 redis 的性能

可以使用 redis-cli 指令扫描 redis 中的大 key 元素

redis-cli -h 127.0.0.1 -p 1036 --bigkeys -i 0.1 # -i 表示每隔 100 条 scan 命令就休眠 0.1s

我们也可以使用 scan 命令编写脚本，实现更精细的扫描

命令拾遗

String

SET & GET & APPEND

  • SET 命令的时间复杂度是 \(O(1)\)，SET 有三种模式，默认/NX/XX
    • NX 模式结合超时与随机字符串可以实现简单的分布式锁
  • GETSET，返回旧值并设置新值
  • MSET，使用一次网络请求设置多个 KEY
  • MSETNX，同时这是多个不存在的键，只有所有键都不存在才会触发设置

INCRBY /DECRBY & INCR/DECR

只能操作可以被 reids 识别为整数的数据

如果操作的数据不存在则先初始化为 0 ，然后进行 增/减 操作

INCR/DECR 直接加一减一，是 INCRBY/DECRBY 的简化版

INCRBYFLOAT

如果键不存在，预设为 0.0 然后执行操作。减法操作通过增加负数实现：INCRBYFLOAT pi -0.7

Range

  • GETRANGE/SETRANGE，获得子串（闭空间，注意与 C++ 迭代器前闭后开的区别），实现文章预览功能
    • GETRANGE key 0 -1，start/end 对应的字符也会返回
    • SETRANGE，未主动设置值的部分会默认填充 0

Hash（略）

List

使用 List 实现简单的消息或者任务队列

  • BLPOP：阻塞式左端弹出操作，BLPOP list [list ...] timeout
  • BRPOPLPUSH：阻塞式弹出并推入操作

待续…

参考

#redis #cache #DV Count #HLL
Next C++ 对象模型