Redis缓存中间件-Ⅱ

参考资料 JavaGuide、蛙课网、三太子敖丙、Redis 命令总结、github优质文章、知乎大黄蜂-redis数据结构、csdn-redis数据结构、博客-redis入门、redix在线练习

[TOC]

Redis 数据类型

五种类型：String 字符串、Hash 字典、List 列表、Set 集合、SortedSet（Zset） 有序集合

中高级：HyperLogLog、Geo、Pub/Sub。

扩充：Redis Module，像 BloomFilter，RedisSearch，Redis-ML

redis 内部使用一个 redisObject 对象来表示所有的 key 和value，redisObject 最主要的信息如上图所示：type 表示一个value 对象具体是何种数据类型，encoding 是不同数据类型在 redis 内部的存储方式。比如：type = string 表示 value 存储的是一个普通字符串，那么 encoding 可以是 raw 或者 int

1
2
3
4
5
6
7
typedef struct redisObject { 
    unsigned [type] 4; 
    unsigned [encoding] 4; 
    unsigned [lru] REDIS_LRU_BITS;
    int refcount; 
    void *ptr; 
} robj;

type：数据类型，就是我们熟悉的 string、hash、list 等

encoding：内部编码，其实就是本文要介绍的数据结构。指的是当前这个value底层是用的什么数据结构。因为同一个数据类型底层也有多种数据结构的实现，所以这里需要指定数据结构

REDIS_LRU_BITS：当前对象可以保留的时长。这个我们在后面讲键的过期策略的时候讲

refcount：对象引用计数，用于GC

ptr：指针，指向以 encoding 的方式实现这个对象的实际地址

String 字符串

在Redis内部，string 类型有两种底层储存结构。Redis会根据存储的数据及用户的操作指令自动选择合适的结构：

• int：存放整数类型;
• SDS：简单动态字符串 simple dynamic string ，存放浮点、字符串、字节类型;

Redis 中的字符串是一种 动态字符串，这意味着使用者可以修改，它的底层实现有点类似于 Java 中的 ArrayList，有一个字符数组，从源码的 sds.h/sdshdr 文件 中可以看到 Redis 底层对于字符串的定义 SDS，即 Simple Dynamic String (SDS)结构：

Redis 规定了字符串的长度不得超过 512 MB

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
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. 
 */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

同样一组结构 Redis 使用泛型定义了多次，为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。比如当字符串比较短的时候，len 和 alloc 可以使用 byte 和 short 来表示

SDS 的总体概览：

其中 sdshdr 是头部

buf 是真实存储用户数据的地方。另外注意, 从命名上能看出来, 这个数据结构除了能存储二进制数据, 显然是用于设计作为字符串使用的, 所以在 buf 中, 用户数据后总跟着一个 \0. 即图中 “数据” + “\0” 是为所谓的 buf

SDS 有五种不同的头部. 其中 sdshdr5 实际并未使用到. 所以实际上有四种不同的头部, 分别如下:

• len 分别以 uint8, uint16, uint32, uint64 表示用户数据的长度(不包括末尾的\0)
• alloc 分别以 uint8, uint16, uint32, uint64 表示整个SDS,除过头部与末尾的 \0 剩余的字节数
• flag 始终为一字节, 以低三位标示着头部的类型, 高5位未使用

当在程序中持有一个 SDS 实例时, 直接持有的是数据区的头指针, 这样做的用意是: 通过这个指针, 向前偏一个字节, 就能取到 flag, 通过判断 flag 低三位的值, 能迅速判断: 头部的类型, 已用字节数, 总字节数, 剩余字节数. 这也是为什么 sds 类型即是char * 指针类型别名的原因

SDS 与 C 字符串的区别

Redis 不直接使用 C 语言的字符串是因为 C 语言这种简单的字符串表示方式 不符合 Redis 对字符串在安全性、效率以及功能方面的要求

C 语言使用了一个长度为 N+1 的字符数组来表示长度为 N 的字符串，并且字符数组最后一个元素总是 ‘\0’。(下图就展示了 C 语言中值为 “Redis” 的一个字符数组)

这样简单的数据结构可能会造成以下一些问题：

• 获取字符串长度为 O(N) 级别的操作 → 因为 C 不保存数组的长度，每次都需要遍历一遍整个数组
• 不能很好的杜绝 缓冲区溢出/内存泄漏 的问题 → 跟上述问题原因一样，如果执行拼接 or 缩短字符串的操作，如果操作不当就很容易造成上述问题
• C 字符串 只能保存文本数据 → 因为 C 语言中的字符串必须符合某种编码（比如 ASCII），例如中间出现的 ‘\0’ 可能会被判定为提前结束的字符串而识别不了

Redis 字符串追加操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
    // 获取原字符串的长度
    size_t curlen = sdslen(s);
  
    // 按需调整空间，如果容量不够容纳追加的内容，就会重新分配字节数组并复制原字符串的内容到新数组中
    s = sdsMakeRoomFor(s,len); 
    if (s == NULL) return NULL;   // 内存不足
    memcpy(s+curlen, t, len);     // 追加目标字符串到字节数组中
    sdssetlen(s, curlen+len);     // 设置追加后的长度
    s[curlen+len] = '\0';         // 让字符串以 \0 结尾，便于调试打印
    return s;
}

扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sds sdsMakeRoomFor(sds s, size_t addlen) {
    ...
    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    ...
}

在扩充空间时：

• 先保证至少有 addlen 可用
• 然后再进一步扩充，在总体占用空间不超过阈 SDS_MAC_PREALLOC时，申请空间再翻一倍。若总体空间已经过了阈值，则步进增长SDS_MAC_PREALLOC。这个阈值的默认为 1024 * 1024

字符串的基本操作：

设置和获取键值对

1
2
3
4
5
> SET key value
OK
> GET key
"value"

EXISTS 和 DEL 关键字来查询是否存在和删除键值对：

1
2
3
4
5
6
> EXISTS key
(integer) 1
> DEL key
(integer) 1
> GET key
(nil)

批量设置键值对

1
2
3
4
5
6
7
8
9
10
11
12
> SET key1 value1
OK
> SET key2 value2
OK
> MGET key1 key2 key3    # 返回一个列表
1) "value1"
2) "value2"
3) (nil)
> MSET key1 value1 key2 value2
> MGET key1 key2
1) "value1"
2) "value2"

过期和 SET 命令扩展

1
2
3
4
5
6
7
> SET key value1
> GET key
"value1"
> EXPIRE name 5    # 5s 后过期
...                # 等待 5s
> GET key
(nil)

等价于 SET + EXPIRE 的 SETEX 命令：

1
2
3
4
5
6
7
8
9
10
11
> SETEX key 5 value1
...                # 等待 5s 后获取
> GET key
(nil)

> SETNX key value1  # 如果 key 不存在则 SET 成功
(integer) 1
> SETNX key value1  # 如果 key 存在则 SET 失败
(integer) 0
> GET key
"value"             # 没有改变 

计数

如果 value 是一个整数，还可以对它使用 INCR 命令进行原子性 的自增操作，这意味着及时多个客户端对同一个 key 进行操作，也决不会导致竞争的情况

1
2
3
4
5
> SET counter 100
> INCR counter
(integer) 101
> INCRBY counter 50
(integer) 151

返回原值的 GETSET 命令：为 key 设置一个值并返回原值

1
2
3
> SET key value
> GETSET key value1
"value"

例如：系统每当由用户进入的时候你就是用 INCR 命令操作一个 key，当需要统计时候你就把这个 key 使用 GETSET 命令重新赋值为 0，这样就达到了统计的目的

list 列表

Redis 的列表相当于 Java 语言中的 LinkedList，注意它是链表而不是数组。这意味着 list 的插入和删除操作非常快，时间复杂度为 O(1)，但是索引定位很慢，时间复杂度为 O(n)

从源码的 adlist.h/listNode 来看到对其的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

typedef struct list {
    listNode *head;
    listNode *tail;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

多个 listNode 可以通过 prev 和 next 指针组成双向链表：

虽然仅仅使用多个 listNode 结构就可以组成链表，但是使用 adlist.h/list 结构来持有链表的话，操作起来会更加方便：

链表的基本操作：

• LPUSH 和 RPUSH 分别可以向 list 的左边（头部）和右边（尾部）添加一个新元素
• LRANGE 命令可以从 list 中取出一定范围的元素
• LINDEX 命令可以从 list 中取出指定下表的元素，相当于 Java 链表操作中的 get(int index) 操作

1
2
3
4
5
6
7
8
9
10
> rpush mylist A
(integer) 1
> rpush mylist B
(integer) 2
> lpush mylist first
(integer) 3
> lrange mylist 0 -1    # -1 表示倒数第一个元素, 这里表示从第一个元素到最后一个元素，即所有
1) "first"
2) "A"
3) "B"

list 实现队列

队列是先进先出的数据结构，常用于消息排队和异步逻辑处理，它会确保元素的访问顺序：

1
2
3
4
5
6
7
8
9
10
> RPUSH books python java golang
(integer) 3
> LPOP books
"python"
> LPOP books
"java"
> LPOP books
"golang"
> LPOP books
(nil)

list 实现栈

栈是先进后出的数据结构，跟队列正好相反：

1
2
3
4
5
6
7
8
9
> RPUSH books python java golang
> RPOP books
"golang"
> RPOP books
"java"
> RPOP books
"python"
> RPOP books
(nil)

hash 字典

Redis 中的字典相当于 Java 中的 HashMap，内部实现也差不多类似，都是通过 “数组 + 链表” 的链地址法来解决部分哈希冲突，同时这样的结构也吸收了两种不同数据结构的优点

源码定义如 dict.h/dictht 定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值，总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    // 内部有两个 dictht 结构
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

table 属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针，而每个 dictEntry 结构保存着一个键值对：

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

可以从上面的源码中看到，实际上字典结构的内部包含两个 hashtable，通常情况下只有一个 hashtable 是有值的，但是在字典扩容缩容时，需要分配新的 hashtable，然后进行 渐进式搬迁

渐进式 rehash

大字典的扩容是比较耗时间的，需要重新申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下面，这是一个 O(n) 级别的操作，作为单线程的 Redis 很难承受这样耗时的过程，所以 Redis 使用 渐进式 rehash 小步搬迁：

渐进式 rehash 会在 rehash 的同时，保留新旧两个 hash 结构，如上图所示，查询时会同时查询两个 hash 结构，然后在后续的定时任务以及 hash 操作指令中，循序渐进的把旧字典的内容迁移到新字典中。当搬迁完成了，就会使用新的 hash 结构取而代之

扩缩容的条件

正常情况下，当 hash 表中元素的个数等于第一维数组的长度时，就会开始扩容

扩容的新数组是 原数组大小的 2 倍。不过如果 Redis 正在做 bgsave(持久化命令)，为了减少内存也得过多分离，Redis 尽量不去扩容，但是如果 hash 表非常满了，达到了第一维数组长度的 5 倍了，这个时候就会 强制扩容

当 hash 表因为元素逐渐被删除变得越来越稀疏时，Redis 会对 hash 表进行缩容来减少 hash 表的第一维数组空间占用。所用的条件是 元素个数低于数组长度的 10%，缩容不会考虑 Redis 是否在做 bgsave(持久化命令)

字典的基本操作

hash 也有缺点，hash 结构的存储消耗要高于单个字符串，所以到底该使用 hash 还是字符串，需要根据实际情况再三权衡：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
> HSET books java "think in java"    # 命令行的字符串如果包含空格则需要使用引号包裹
(integer) 1
> HSET books python "python cookbook"
(integer) 1
> HGETALL books    # key 和 value 间隔出现
1) "java"
2) "think in java"
3) "python"
4) "python cookbook"
> HGET books java
"think in java"
> HSET books java "head first java"  
(integer) 0        # 因为是更新操作，所以返回 0
> HMSET books java "effetive  java" python "learning python"    # 批量操作
OK

set 集合

Redis 的集合相当于 Java 语言中的 HashSet，它内部的键值对是无序、唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值 NULL

集合 set 的基本使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
> SADD books java
(integer) 1
> SADD books java    # 重复
(integer) 0
> SADD books python golang
(integer) 2
> SMEMBERS books    # 注意顺序，set 是无序的 
1) "java"
2) "python"
3) "golang"
> SISMEMBER books java    # 查询某个 value 是否存在，相当于 contains
(integer) 1
> SCARD books    # 获取长度
(integer) 3
> SPOP books     # 弹出一个
"java"

zset 有序列表

这可能使 Redis 最具特色的一个数据结构了，它类似于 Java 中 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以为每个 value 赋予一个 score 值，用来代表排序的权重。

它的内部实现用的是一种叫做 跳跃表 的数据结构，由于比较复杂，所以在这里简单提一下原理就好了：

例如一家创业公司，刚开始只有几个人，大家都平起平坐。后来随着公司的发展，人数越来越多，团队沟通成本逐渐增加，渐渐地引入了组长制，对团队进行划分，于是有一些人又是员工又有组长的身份

再后来，公司规模进一步扩大，公司需要再进入一个层级：部门。于是每个部门又会从组长中推举一位选出部长

跳跃表就类似于这样的机制，最下面一层所有的元素都会串起来，都是员工，然后每隔几个元素就会挑选出一个代表，再把这几个代表使用另外一级指针串起来。然后再在这些代表里面挑出二级代表，再串起来。最终形成了一个金字塔的结构

有序列表 zset 基础操作

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
36
37
38
> ZADD books 9.0 "think in java"
> ZADD books 8.9 "java concurrency"
> ZADD books 8.6 "java cookbook"

> ZRANGE books 0 -1     # 按 score 排序列出，参数区间为排名范围
1) "java cookbook"
2) "java concurrency"
3) "think in java"

> ZREVRANGE books 0 -1  # 按 score 逆序列出，参数区间为排名范围
1) "think in java"
2) "java concurrency"
3) "java cookbook"

> ZCARD books           # 相当于 count()
(integer) 3

> ZSCORE books "java concurrency"   # 获取指定 value 的 score
"8.9000000000000004"                # 内部 score 使用 double 类型进行存储，所以存在小数点精度问题

> ZRANK books "java concurrency"    # 排名
(integer) 1

> ZRANGEBYSCORE books 0 8.91        # 根据分值区间遍历 zset
1) "java cookbook"
2) "java concurrency"

> ZRANGEBYSCORE books -inf 8.91 withscores  # 根据分值区间 (-∞, 8.91] 遍历 zset，同时返回分值。inf 代表 infinite，无穷大的意思。
1) "java cookbook"
2) "8.5999999999999996"
3) "java concurrency"
4) "8.9000000000000004"

> ZREM books "java concurrency"             # 删除 value
(integer) 1
> ZRANGE books 0 -1
1) "java cookbook"
2) "think in java"

Redis 数据类型应用场景总结

HyperLogLog

HyperLogLog 最早由 Flajolet 及其同事在 2007 年提出的一种 估算基数的近似最优算法。但跟原版论文不同的是，很多书包括 Redis 作者都把它称为一种 新的数据结构(new datastruct) (算法实现确实需要一种特定的数据结构来实现)

关于基数统计：

基数统计(Cardinality Counting) 通常是用来统计一个集合中不重复的元素个数

思考这样的一个场景： 如果你负责开发维护一个大型的网站，有一天老板找产品经理要网站上每个网页的 UV(独立访客，每个用户每天只记录一次)，然后让你来开发这个统计模块，你会如何实现？

如果统计 PV(浏览量，用户每点一次记录一次)，那非常好办，给每个页面配置一个独立的 Redis 计数器就可以了，把这个计数器的 key 后缀加上当天的日期。这样每来一个请求，就执行 INCRBY 指令一次，最终就可以统计出所有的 PV 数据了

但是 UV 不同，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就要求了每一个网页请求都需要带上用户的 ID，无论是登录用户还是未登录的用户，都需要一个唯一 ID 来标识

如果为每一个页面设置一个独立的 set 集合 来存储所有当天访问过此页面的用户 ID

但这样将带来的问题是：

• 存储空间巨大： 如果网站访问量一大，你需要用来存储的 set 集合就会非常大，如果页面再一多.. 为了一个去重功能耗费的资源非常大
• 统计复杂： 这么多 set 集合如果要聚合统计一下，又是一个复杂的事情

对于上述这样需要 基数统计 的事情，通常来说有两种比 set 集合更好的解决方案

基数统计的常用方法：

第一种：B 树

B 树最大的优势就是插入和查找效率很高，如果用 B 树存储要统计的数据，可以快速判断新来的数据是否存在，并快速将元素插入 B 树。要计算基础值，只需要计算 B 树的节点个数就行了

不过将 B 树结构维护到内存中，能够解决统计和计算的问题，但是 并没有节省内存

第二种：bitmap（位图）

bitmap 可以理解为通过一个 bit 数组来存储特定数据的一种数据结构，每一个 bit 位都能独立包含信息，bit 是数据的最小存储单位，因此能大量节省空间，也可以将整个 bit 数据一次性 load 到内存计算。如果定义一个很大的 bit 数组，基础统计中 每一个元素对应到 bit 数组中的一位，例如：

bitmap 还有一个明显的优势是可以轻松合并多个统计结果

只需要对多个结果求异或（a、b两个值不相同，异或结果为 1。a、b两个值相同，异或结果为 0） 就可以了，也可以大大减少存储内存。可以简单做一个计算，如果要统计 1 亿 个数据的基数值，大约需要的内存：100_000_000/ 8/ 1024/ 1024 ≈ 12 M，如果用 32 bit 的 int 代表 每一个 统计的数据，大约需要内存：32 * 100_000_000/ 8/ 1024/ 1024 ≈ 381 M

可以看到 bitmap 对于内存的节省显而易见，但仍然不够。统计一个对象的基数值就需要 12 M，如果统计 1 万个对象，就需要接近 120 G，对于大数据的场景仍然不适用

概率算法

实际上目前还没有发现更好的在 大数据场景 中 准确计算 基数的高效算法，因此在不追求绝对精确的情况下，使用概率算法算是一个不错的解决方案

概率算法 不直接存储 数据集合本身，通过一定的 概率统计方法预估基数值，这种方法可以大大节省内存，同时保证误差控制在一定范围内。目前用于基数计数的概率算法包括：

• Linear Counting(LC)：早期的基数估计算法，LC 在空间复杂度方面并不算优秀，实际上 LC 的空间复杂度与上文中简单 bitmap 方法是一样的（但是有个常数项级别的降低），都是 O(Nmax)
• LogLog Counting(LLC)：LogLog Counting 相比于 LC 更加节省内存，空间复杂度只有 O(log2(log2(Nmax)))
• HyperLogLog Counting(HLL)：HyperLogLog Counting 是基于 LLC 的优化和改进，在同样空间复杂度情况下，能够比 LLC 的基数估计误差更小

其中，HyperLogLog 的表现是惊人的，上面我们简单计算过用 bitmap 存储 1 个亿 统计数据大概需要 12 M 内存，而在 HyperLoglog 中，只需要不到 1 K 内存就能够做到！在 Redis 中实现的 HyperLoglog 也只需要 12 K 内存，在标准误差 0.81% 的前提下，能够统计 2^64 个数据

HyperLogLog 的使用：

HyperLogLog 提供了两个指令 PFADD和 PFCOUNT，字面意思就是一个是增加，另一个是获取计数。PFADD 和 set 集合的 SADD 的用法是一样的，来一个用户 ID，就将用户 ID 塞进去就是，PFCOUNT 和 SCARD 的用法是一致的，直接获取计数值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
> PFADD codehole user1
(interger) 1
> PFCOUNT codehole
(integer) 1
> PFADD codehole user2
(integer) 1
> PFCOUNT codehole
(integer) 2
> PFADD codehole user3
(integer) 1
> PFCOUNT codehole
(integer) 3
> PFADD codehole user4 user 5
(integer) 1
> PFCOUNT codehole
(integer) 5

BloomFilter（布隆过滤器）

场景：抖音推送去重

有 刷到过重复的推荐内容 吗？这么多的推荐内容要推荐给这么多的用户，它是怎么保证每个用户在看推荐内容时，保证不会出现之前已经看过的推荐视频呢？也就是说，抖音是如何实现 推送去重 的呢？

你会想到服务器 记录 了用户看过的 所有历史记录，当推荐系统推荐短视频时会从每个用户的历史记录里进行 筛选，过滤掉那些已经存在的记录。问题是当 用户量很大，每个用户看过的短视频又很多的情况下，这种方式，推荐系统的去重工作 在性能上跟的上么？

实际上，如果历史记录存储在关系数据库里，去重就需要频繁地对数据库进行 exists 查询，当系统并发量很高时，数据库是很难抗住压力的

你可能又想到了 缓存，但是这么多用户这么多的历史记录，如果全部缓存起来，那得需要 浪费多大的空间 啊.. (可能老板看一眼账单，看一眼你..) 并且这个存储空间会随着时间呈线性增长，就算你用缓存撑得住一个月，但是又能继续撑多久呢？不缓存性能又跟不上，咋办呢？

如上图所示，布隆过滤器(Bloom Filter) 就是这样一种专门用来解决去重问题的高级数据结构。但是跟 HyperLogLog 一样，它也一样有那么一点点不精确，也存在一定的误判概率，但它能在解决去重的同时，在 空间上能节省 90% 以上，也是非常值得的

什么是布隆过滤器

布隆过滤器（Bloom Filter） 是 1970 年由布隆提出的。它 实际上 是一个很长的二进制向量和一系列随机映射函数，实际上也可以把它 简单理解 为一个不怎么精确的 set 结构，当使用它的 contains 方法判断某个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合理，它的精确度可以控制的相对足够精确，只会有小小的误判概率

当布隆过滤器说某个值存在时，这个值 可能不存在；当它说不存在时，那么一定不存在。打个比方，当它说不认识你时，那就是真的不认识，但是当它说认识你的时候，可能是因为你长得像它认识的另外一个朋友 (脸长得有些相似)，所以误判认识你

布隆过滤器的使用场景：

• 大数据判断是否存在：这就可以实现出上述的去重功能，如果你的服务器内存足够大的话，那么使用 HashMap 可能是一个不错的解决方案，理论上时间复杂度可以达到 O(1 的级别，但是当数据量起来之后，还是只能考虑布隆过滤器。
• 解决缓存穿透：我们经常会把一些热点数据放在 Redis 中当作缓存，例如产品详情。 通常一个请求过来之后我们会先查询缓存，而不用直接读取数据库，这是提升性能最简单也是最普遍的做法，但是 如果一直请求一个不存在的缓存，那么此时一定不存在缓存，那就会有 大量请求直接打到数据库 上，造成 缓存穿透，布隆过滤器也可以用来解决此类问题。
• 爬虫/ 邮箱等系统的过滤：平时不知道你有没有注意到有一些正常的邮件也会被放进垃圾邮件目录中，这就是使用布隆过滤器 误判 导致的 … …

布隆过滤器原理解析：

布隆过滤器 本质上 是由长度为 m 的位向量或位列表（仅包含 0 或 1 位值的列表）组成，最初所有的值均设置为 0，所以先来创建一个稍微长一些的位向量用作展示：

当我们向布隆过滤器中添加数据时，会使用 多个 hash 函数对 key 进行运算，算得一个证书索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作，例如，我们添加一个 wmyskxz：

向布隆过滤器查询 key 是否存在时，跟 add 操作一样，会把这个 key 通过相同的多个 hash 函数进行运算，查看 对应的位置 是否 都 为 1，只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在。如果这几个位置都是 1，并不能说明这个 key 一定存在，只能说极有可能存在，因为这些位置的 1 可能是因为其他的 key 存在导致的

就比如我们在 add 了一定的数据之后，查询一个 不存在 的 key：

很明显，1/3/5 这几个位置的 1 是因为上面第一次添加的 wmyskxz 而导致的，所以这里就存在 误判。幸运的是，布隆过滤器有一个可以预判误判率的公式，比较复杂，感兴趣的朋友可以自行去阅读，比较烧脑.. 只需要记住以下几点就好了：

• 使用时 不要让实际元素数量远大于初始化数量；
• 当实际元素数量超过初始化数量时，应该对布隆过滤器进行 重建，重新分配一个 size 更大的过滤器，再将所有的历史元素批量 add 进去

布隆过滤器的使用

redis 官方 提供的布隆过滤器到了 Redis 4.0 提供了插件功能之后才正式登场。布隆过滤器作为一个插件加载到 Redis Server 中，给 Redis 提供了强大的布隆去重功能

布隆过滤器的基本用法：

布隆过滤器有两个基本指令，bf.add 添加元素，bf.exists 查询元素是否存在，它的用法和 set 集合的 sadd 和 sismember 差不多。注意 bf.add 只能一次添加一个元素，如果想要一次添加多个，就需要用到 bf.madd 指令。同样如果需要一次查询多个元素是否存在，就需要用到 bf.mexists 指令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
127.0.0.1:6379> bf.add codehole user1
(integer) 1
127.0.0.1:6379> bf.add codehole user2
(integer) 1
127.0.0.1:6379> bf.add codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user1
(integer) 1
127.0.0.1:6379> bf.exists codehole user2
(integer) 1
127.0.0.1:6379> bf.exists codehole user3
(integer) 1
127.0.0.1:6379> bf.exists codehole user4
(integer) 0
127.0.0.1:6379> bf.madd codehole user4 user5 user6
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379> bf.mexists codehole user4 user5 user6 user7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

上面使用的布隆过过滤器只是默认参数的布隆过滤器，它在我们第一次 add 的时候自动创建。Redis 也提供了可以自定义参数的布隆过滤器，只需要在 add 之前使用 bf.reserve 指令显式创建就好了。如果对应的 key 已经存在，bf.reserve 会报错

bf.reserve 有三个参数，分别是 key、error_rate (错误率) 和 initial_size：

• error_rate 越低，需要的空间越大，对于不需要过于精确的场合，设置稍大一些也没有关系，比如上面说的推送系统，只会让一小部分的内容被过滤掉，整体的观看体验还是不会受到很大影响的
• initial_size 表示预计放入的元素数量，当实际数量超过这个值时，误判率就会提升，所以需要提前设置一个较大的数值避免超出导致误判率升高

如果不适用 bf.reserve，默认的 error_rate 是 0.01，默认的 initial_size 是 100

Redis 实现分布式锁

一般情况下，使用分布式锁主要有两个场景：

1. 避免不同节点重复相同的工作： 比如用户执行了某个操作有可能不同节点会发送多封邮件
2. 避免破坏数据的正确性： 如果两个节点在同一条数据上同时进行操作，可能会造成数据错误或不一致的情况出现

Java 中实现的常见方式

锁的本质：同一时间只允许一个用户操作。 所以理论上，能够满足这个需求的工具我们都能够使用 (就是其他应用能帮我们加锁的)：

1. 基于 MySQL 中的锁：MySQL 本身有自带的悲观锁 for update 关键字，也可以自己实现悲观/乐观锁来达到目的
2. 基于 Zookeeper 有序节点：Zookeeper 允许临时创建有序的子节点，这样客户端获取节点列表时，就能够当前子节点列表中的序号判断是否能够获得锁
3. 基于 Redis 的单线程：由于 Redis 是单线程，所以命令会以串行的方式执行，并且本身提供了像 SETNX(set if not exists) 这样的指令，本身具有互斥性

每个方案都有各自的优缺点，例如 MySQL 虽然直观理解容易，但是实现起来却需要额外考虑 锁超时、加事务 等，并且性能局限于数据库

Redis 的实现思路看起来很直接，但它更适合做 高性能、短临界区、允许少量业务补偿 的锁。如果业务要求的是强一致，只要出错一次就完全不可接受，那么 Redis 往往不是第一选择，通常会更偏向 Zookeeper、etcd 这一类一致性更强的协调组件。

单实例 Redis 的正确加锁方式

在较早的实现里，很多文章会把 SETNX 和 EXPIRE 拆成两条命令：

1
2
SETNX lock_key 1
EXPIRE lock_key 30

这个写法有一个明显问题：如果 SETNX 成功了，但客户端在执行 EXPIRE 之前宕机，那么这个锁就可能变成一个没有过期时间的死锁。

因此更安全的方式是把“抢锁”和“设置过期时间”合并成一条原子命令：

1
SET lock_key request_id NX PX 30000

这里有两个点很重要：

1. NX 表示只有 key 不存在时才设置成功
2. PX 30000 表示设置 30 秒过期时间，避免服务宕机后锁永远不释放

其中 request_id 不能随便写一个固定值，最好是每次加锁时生成的唯一随机值，比如 UUID。这样做的目的，是为了让“谁加的锁，谁来解锁”。

释放锁时也不能直接 DEL lock_key，因为可能出现下面的时序问题：

1. 服务 A 拿到锁，value 是 uuid-a
2. 锁因为超时自动过期了
3. 服务 B 又拿到了同一个锁，value 是 uuid-b
4. 这时服务 A 才执行 DEL lock_key

如果直接删除，那么服务 A 会把服务 B 正在持有的锁误删掉。正确做法是先比对 value，再删除 key，并且这两个动作必须是原子操作，通常通过 Lua 脚本实现：

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

Redis 分布式锁的几个典型问题

1. 服务宕机后锁无法释放

假设现在有两台服务 A、B，A 在获取锁之后突然挂掉，如果这个锁没有过期时间，那么 B 就可能永远拿不到锁：

所以 Redis 锁几乎都必须带过期时间，用来保证系统最终可恢复。

2. 业务还没执行完，锁先过期了

这才是 Redis 分布式锁里更麻烦的问题。

假设 A 拿到锁之后开始处理业务，锁的超时时间是 30 秒；如果这个业务实际执行了 45 秒，那么在第 31 秒时锁就已经自动释放，此时 B 完全可能重新拿到锁并进入临界区。这样一来，A 和 B 就会在一段时间里同时执行本应串行的代码。

这意味着 Redis 锁从本质上说是一个带租约的锁，而不是“只要业务没结束就绝对没人能进来”的强锁。

常见的应对方式有几种：

1. 只把 Redis 锁用于短任务。 临界区越短，越容易控制风险
2. 把过期时间设置得比业务耗时上界更宽裕。 但这只能降低概率，不能从根本上消灭问题
3. 使用自动续期机制。 例如 Redisson 的 watchdog 会在业务还存活时为锁续租
4. 业务层再做兜底。 比如幂等校验、状态机检查、唯一索引、版本号 CAS 等

其中第 4 点非常关键。Redis 锁最多只能帮助我们减少并发冲突，它通常不能代替业务数据本身的一致性设计。

3. GC、STW、网络抖动也会放大锁过期问题

Java 在 GC 时可能发生 STW(Stop-The-World)，这会让线程在一段时间内完全暂停：

服务 A 已经拿到了锁，但在执行业务期间发生了较长时间的 STW，此时锁可能先过期，服务 B 则重新获得了锁。等 A 恢复之后，它并不知道自己其实已经“失去锁资格”了，于是继续执行业务，最终就会和 B 同时操作共享数据。

类似的问题不只来自 GC，长时间的 Full GC、线程调度延迟、网络阻塞、机器负载过高，都会导致“客户端自认为还持有锁，但实际上租约已经失效”。

所以 Redis 分布式锁真正需要防的不是“解锁失败”，而是“锁已经失效，但旧持有者还在继续工作”。

主从切换、哨兵、Cluster 与锁安全

很多人第一次接触 Redis 锁时，都会担心这样一个问题：服务 A 在某个 Redis 节点上拿到了锁，结果 Redis 宕机或主从切换之后，服务 B 又在另一个节点上拿到了同一把锁，这是不是和 Redis 集群有关？

答案是：有关系，但根本原因不是“节点变多了”，而是 Redis 复制默认是异步的。

来看一个典型场景：

1. 服务 A 在主节点上成功加锁
2. 这条锁记录还没来得及复制到从节点
3. 主节点突然宕机
4. 从节点被提升为新的主节点
5. 服务 B 在新主节点上再次加锁成功

这样就会出现两个客户端都认为自己拿到了锁的情况。

这个问题会出现在：

1. Redis 主从复制
2. Sentinel 故障转移
3. Redis Cluster 中某个主分片故障并切换副本

也就是说，Redis Cluster 并不会天然让分布式锁更安全。对于单个锁 key 来说，它始终只落在某一个哈希槽对应的主节点上；一旦这个主节点发生故障切换，异步复制带来的锁丢失风险依然存在。

因此，“宕机后锁出现在不同 Redis 节点上”并不是因为 Cluster 把一把锁拆成了多份，而是因为故障切换后新的主节点上可能根本没有旧锁的数据。

RedLock 的思路与边界

为了解决单点 Redis 故障带来的可用性问题，Redis 作者提出过 RedLock。它的核心思路不是依赖一个主从集群，而是依赖多个彼此独立的 Redis 主节点，客户端只有在多数节点上都加锁成功时，才认为自己真正拿到了锁。

这个思路确实可以在一定程度上降低“单个 Redis 节点故障”造成的问题，但它也有明显边界：

1. 它主要改善的是节点故障下的可用性和容错性
2. 它并不能彻底消除 GC、长暂停、网络分区、时钟漂移等问题
3. 社区对于 RedLock 的适用场景一直有争议，因此更适合“高可用优先”的业务，而不是“强一致绝对正确”的场景

如果业务属于库存扣减、账户余额、核心状态机切换这类特别敏感的操作，通常不能只依赖 Redis 锁本身，还要引入数据库约束、幂等设计，或者直接选择一致性更强的协调组件。

实践中的几个注意点

最后把 Redis 分布式锁的常见经验整理成几条：

1. 加锁使用原子命令： SET key value NX PX timeout
2. value 必须唯一： 解锁时要校验 value，避免删掉别人的锁
3. 解锁使用 Lua： “比较 + 删除”必须是原子操作
4. 锁只保护短临界区： 不适合超长任务，也不适合作业型批处理
5. 必要时做自动续期： 但续期只是降低风险，不是绝对安全
6. 业务层必须有兜底： 幂等、唯一索引、状态机、版本号校验一个都不能少
7. 主从/Cluster 要考虑故障切换： 异步复制下可能出现锁丢失，不要误以为“上了集群就更安全”
8. 优先使用成熟客户端： 例如 Redisson，而不是手写一套不完整的锁逻辑

所以，Redis 分布式锁并不是不能用，而是要清楚它解决的是“协调并发”的大部分问题，而不是“保证绝对正确”的全部问题。只要场景选得合适、过期时间合理、解锁方式正确，再配合业务层的幂等和约束，它依然是一个非常常用、非常高效的方案。

• Previous
  Redis缓存中间件-Ⅰ
• Next
  IO总结