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 分布式锁的问题：

锁超时：

假设现在我们有两台平行的服务 A B，其中 A 服务在 获取锁之后 由于未知神秘力量突然 挂了，那么 B 服务就永远无法获取到锁了：

所以需要额外设置一个超时时间，来保证服务的可用性

但是另一个问题随即而来：如果在加锁和释放锁之间的逻辑执行得太长，以至于超出了锁的超时限制，也会出现问题。因为这时候第一个线程持有锁过期了，而临界区的逻辑还没有执行完，与此同时第二个线程就提前拥有了这把锁，导致临界区的代码不能得到严格的串行执行

为了避免这个问题，Redis 分布式锁不要用于较长时间的任务。如果真的偶尔出现了问题，造成的数据小错乱可能就需要人工的干预

有一个稍微安全一点的方案是 将锁的 value 值设置为一个随机数，释放锁时先匹配随机数是否一致，然后再删除 key，这是为了 确保当前线程占有的锁不会被其他线程释放，除非这个锁是因为过期了而被服务器自动释放的

但是匹配 value 和删除 key 在 Redis 中并不是一个原子性的操作，也没有类似保证原子性的指令，所以可能需要使用像 Lua 这样的脚本来处理了，因为 Lua 脚本可以 保证多个指令的原子性执行

GC 可能引发的安全问题：

Java中在 GC 的时候会发生 STW(Stop-The-World)，这本身是为了保障垃圾回收器的正常执行，但可能会引发如下的问题：

服务 A 获取了锁并设置了超时时间，但是服务 A 出现了 STW 且时间较长，导致了分布式锁进行了超时释放，在这个期间服务 B 获取到了锁，待服务 A STW 结束之后又恢复了锁，这就导致了 服务 A 和服务 B 同时获取到了锁，这个时候分布式锁就不安全了

不仅仅局限于 Redis，Zookeeper 和 MySQL 有同样的问题

单点/多点问题：

如果 Redis 采用单机部署模式，那就意味着当 Redis 故障了，就会导致整个服务不可用

而如果采用主从模式部署，我们想象一个这样的场景：服务 A 申请到一把锁之后，如果作为主机的 Redis 宕机了，那么 服务 B 在申请锁的时候就会从从机那里获取到这把锁，为了解决这个问题，Redis 作者提出了一种 RedLock 红锁 的算法 (Redission 同 Jedis)：

1
2
3
4
5
6
7
8
9
// 三个 Redis 集群
RLock lock1 = redissionInstance1.getLock("lock1");
RLock lock2 = redissionInstance2.getLock("lock2");
RLock lock3 = redissionInstance3.getLock("lock3");

RedissionRedLock lock = new RedissionLock(lock1, lock2, lock2);
lock.lock();
// do something....
lock.unlock();

在之前版本的 Redis 中，由于 SETNX 和 EXPIRE 并不是 原子指令，所以在一起执行会出现问题

也许你会想到使用 Redis 事务来解决，但在这里不行，因为 EXPIRE 命令依赖于 SETNX 的执行结果，而事务中没有 if-else 的分支逻辑，如果 SETNX 没有抢到锁，EXPIRE 就不应该执行

为了解决这个疑难问题，Redis 开源社区涌现了许多分布式锁的 library，为了治理这个乱象，后来在 Redis 2.8 的版本中，加入了 SET 指令的扩展参数，使得 SETNX 可以和 EXPIRE 指令一起执行了

1
>set test name ex 2 nx;

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