Redis缓存中间件-Ⅱ

这一篇从 Redis 的数据结构视角继续往下展开，重点梳理 String、Hash、List、Set、ZSet 的底层编码思路，以及 HyperLogLog、Bloom Filter、分布式锁这些在工程里高频出现但又容易混淆的主题。

内容更偏向“概念与机制对应起来”的笔记：既关注命令层面的使用方式，也关注底层编码、适用边界和常见误区，便于后续把缓存、去重、统计和并发控制这些问题放到同一个认知框架里理解。

参考资料：

官方文档：Redis Data Types 、 Redis Memory Optimization 、 Redis Probabilistic Data Types 、 Distributed Locks with Redis

实践资料：Redis 命令参考 、 Redis 设计与实现 、 RedisBloom Documentation 、 try.redis.io

[TOC]

Redis 数据类型

从业务最常见的视角看，Redis 的核心数据类型仍然可以概括为五类：String、Hash、List、Set、Sorted Set（ZSet）。

但工程实践里也经常会看到 HyperLogLog、Bitmap、Geo、Pub/Sub、Stream 这些能力。它们和“五种核心类型”不是同一层概念，有些是建立在已有结构上的特殊命令集合，有些是概率型数据结构，有些则更接近消息通信模型。

可以先用下表把这一层关系区分开：

Redis 内部使用 redisObject 来描述对象的逻辑类型与底层编码方式。type 决定对外语义属于 string、hash、list、set 还是 zset；encoding 决定底层究竟采用哪种紧凑结构或数据结构来保存数据。比如同样是 string，对外都是字符串对象，但内部可能使用 int、embstr 或 raw 编码。

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

type：数据类型，也就是 string、hash、list 等逻辑类型

encoding：内部编码，用于说明当前 value 底层到底采用什么结构实现。之所以需要这个字段，是因为同一种逻辑数据类型在不同数据规模下通常会使用不同编码。

LRU_BITS：用于记录对象的 LRU/LFU 相关信息，它服务于内存淘汰近似算法，并不等于“这个对象还能保留多久”。

refcount：对象引用计数，用于对象生命周期管理，而不是 Java 语义里的垃圾回收器。

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

同一个逻辑类型在 Redis 中往往存在多种底层编码，这也是理解 Redis “既快又省内存”的关键：

String 字符串

在 Redis 内部，string 类型常见的底层编码可以分为三类，Redis 会根据值的内容和长度自动选择：

• int：存放整数类型;
• embstr：适合较短字符串，对象头和 SDS 一次性连续分配;
• raw：基于 SDS，适合较长字符串;

其中 embstr 和 raw 本质上都依赖 SDS（Simple Dynamic String）来保存字符串内容；如果 value 本身是整数且适合整数编码，就没有必要额外维护一段 SDS。

Redis 中的字符串是一种动态字符串，它的底层实现和 Java 中“会自动扩容的字符数组”有相似之处，但会额外显式记录长度与剩余空间，以换取更稳定的时间复杂度和更好的二进制安全性。从源码 sds.h 中可以看到 Redis 对 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 key 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
"value1"            # 没有改变 

计数

如果 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"

例如，可以把某个时间窗口内的访问量累加在一个计数 key 上；到统计时刻，再通过 GETSET 取出旧值并把计数器重置为 0。这样既能拿到上一周期的结果，也能立刻开始下一周期计数。

list 列表

很多旧资料会把 Redis 的 list 直接等同于 Java 里的 LinkedList，这种说法对理解两端插入、两端弹出的语义有帮助，但和现代 Redis 的底层实现并不完全一致。

当前主流版本中，list 对象主要使用 quicklist 编码。它可以理解为“链表骨架 + 紧凑连续存储块”的组合结构：既保留了从头尾快速插入删除的能力，也避免了为每个元素单独分配链表节点带来的额外指针开销。

因此，list 的逻辑行为依旧表现为双端队列，头尾插入删除很快；但按下标随机定位中间元素，整体仍然不如数组结构高效。

从源码的 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 字典

hash 对象对外语义很像编程语言中的 Map<String, String>。当 field/value 数量较少且内容较短时，Redis 会优先使用 listpack 做紧凑存储；只有当元素数量或长度超过阈值时，才会转成 hashtable 编码。

下面这组 dict 结构更适合用来理解“大 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
> HSET books java "effective java" python "learning python"    # 批量操作
(integer) 0

set 集合

Redis 的 set 相当于无序且元素唯一的集合。它并不总是直接使用哈希表：如果集合里的元素都是整数并且规模较小，Redis 会优先使用 intset；当元素类型更复杂或者数量变大时，才会转换为 hashtable 编码。

因此，“set 本质上是 value 为空的字典”更准确地说是 set 在 hashtable 编码下的实现方式。

集合 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 最具特色的一个数据结构了。它有点像 SortedSet 和 HashMap 的结合体：一方面它保证 member 唯一，另一方面它又为每个 member 维护一个 score，用来代表排序权重。

需要注意的是，zset 也不是任何时候都直接使用跳表。数据量较小时，Redis 会使用 listpack；当元素增多后，通常会同时维护 skiplist + dict 两部分结构：

• dict 负责按 member 快速定位 score
• skiplist 负责按 score 有序遍历和范围查询

因此，zset 的强项不只是“能排序”，而是“既能查单点，也能做范围检索”。

它的大型编码实现里最有代表性的结构是 跳跃表，这里简单提一下它的直观原理：

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

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

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

有序列表 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 数据类型应用场景总结

Bitmap、Geo、Pub/Sub 与 Stream 的定位

除了上面的五种基础类型，Redis 里还有几类非常常见、但容易和“核心数据类型”混在一起的能力：

其中 Bitmap 和 Geo 更像是建立在既有结构之上的专用能力；Pub/Sub 与 Stream 则更偏向消息模型。尤其是 Stream，在 Redis 5.0 之后已经成为比 list + BRPOP 更完整的消息流方案。

HyperLogLog

HyperLogLog 最早由 Flajolet 及其同事在 2007 年提出，它本质上是一类用于估算基数的概率算法。落到 Redis 语境里，通常也会把它当作一种“面向基数统计的数据结构能力”来理解。

关于基数统计：

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

一个很典型的场景是页面 UV（独立访客）统计。它和 PV 不同，PV 只需要计数即可；而 UV 的关键在于去重后再计数。

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

但是 UV 不同，它要去重，同一个用户一天之内的多次访问只能记一次。这要求系统能够识别“今天这个用户是否已经来过”。

如果为每一个页面设置一个独立的 set 集合 来存储当天访问过此页面的用户 ID，那么语义上是最直接的。

但这样将带来的问题是：

• 存储空间巨大： 页面一多、访问量一大，set 占用的内存会迅速膨胀
• 统计复杂： 这么多 set 集合如果要聚合统计一下，又是一个复杂的事情

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

基数统计的常用方法：

第一种：B 树

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

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

第二种：bitmap（位图）

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

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

只需要对多个结果求按位或（OR） 就可以得到并集结果，也可以大大减少存储内存。可以简单做一个计算，如果要统计 1 亿个数据的基数值，大约需要的内存：100_000_000 / 8 / 1024 / 1024 ≈ 12 MB；如果用 32 bit 的 int 来存储每一个统计对象，大约需要内存：32 * 100_000_000 / 8 / 1024 / 1024 ≈ 381 MB

可以看到 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 的价值就在于：它不保存成员本身，也不支持枚举成员，而是用极小的固定空间去近似估算基数。在 Redis 中，HyperLogLog 稠密编码下占用大约 12 KB 内存，标准误差约为 0.81%，适合做海量去重计数这类“允许小误差、不能接受大内存”的场景。

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
(integer) 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 user5
(integer) 1
> PFCOUNT codehole
(integer) 5

如果需要把多个统计结果合并在一起，还可以使用 PFMERGE。这一点非常适合做“分天统计后按周汇总”或者“分节点统计后做全局聚合”。

BloomFilter（布隆过滤器）

场景：抖音推送去重

推荐系统里的“用户是否已经看过某条内容”就是一个很典型的存在性判断问题。最直接的做法当然是保存完整历史记录，再在推荐时执行去重过滤。

问题在于，当用户量和内容量同时增大时，完整历史集合会变得非常庞大。无论把这份历史放在关系数据库还是普通缓存里，空间成本和查询成本都会快速上升。

这类场景需要的往往不是“拿到完整历史明细”，而是“快速判断某个元素大概率是否出现过”。Bloom Filter 正是为这种场景准备的空间换精度方案。

如上图所示，布隆过滤器（Bloom Filter）是一种专门用来做“存在性判断”的概率型数据结构。它也和 HyperLogLog 一样并不追求绝对精确，但它换来的好处是非常高的空间利用率。

什么是布隆过滤器

布隆过滤器（Bloom Filter）是 1970 年提出的一类概率型数据结构。它可以理解为“一个很长的位数组 + 多个哈希函数”的组合，用来回答“某个元素是否可能存在”。

它最重要的性质是：

• 如果布隆过滤器判断某个值不存在，那么这个值一定不存在
• 如果布隆过滤器判断某个值存在，那么这个值只是大概率存在，仍然可能是误判

布隆过滤器的使用场景：

• 大数据量下的存在性预检：例如推荐去重、历史访问判重、反作弊名录预筛
• 解决缓存穿透：先用布隆过滤器判断 key 是否可能存在，再决定是否继续访问缓存和数据库
• 爬虫、邮箱、黑名单系统的过滤：用较低的误判率换取更高的空间效率

它也有很明确的边界：标准布隆过滤器不支持精确删除，也不能把所有已加入元素再完整枚举出来。如果场景同时要求“低误判 + 可删除”，通常要继续评估 Cuckoo Filter 等其他结构。

布隆过滤器原理解析：

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

当向布隆过滤器中添加数据时，会使用多个 hash 函数对 key 进行运算，得到多个整数索引值，再对位数组长度取模，映射到若干个位置上。把这些位置全部置为 1，就完成了一次 add 操作，例如添加一个 wmyskxz：

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

假设已经加入了一定的数据，再去查询一个实际上并不存在的 key：

很明显，1/3/5 这几个位置的 1 可能是由其他元素留下的，所以这里就出现了误判。实际使用时，不一定需要手推误判率公式，先记住下面两点更重要：

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

布隆过滤器的使用

Redis 官方生态里的 Bloom Filter 能力主要由 RedisBloom 模块提供。也就是说，它不是早期 Redis 内核里天然自带的五种基础类型之一，而是通过模块机制扩展进来的能力。

布隆过滤器的基本用法：

布隆过滤器有两个基本指令，BF.ADD 添加元素，BF.EXISTS 查询元素是否存在。它们的语义和 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

上面使用的是默认参数的布隆过滤器，它会在第一次 BF.ADD 时自动创建。如果希望显式控制误判率和容量，可以在写入前通过 BF.RESERVE 提前创建；如果对应的 key 已经存在，BF.RESERVE 会报错。

BF.RESERVE 有三个核心参数，分别是 key、error_rate（错误率）和 initial_size：

• error_rate 越低，需要的空间越大；如果场景容忍少量误判，可以适当放宽这个值，换取更小内存
• initial_size 表示预计放入的元素数量，当实际数量超过这个值时，误判率就会提升，所以需要提前设置一个较大的数值避免超出导致误判率升高

如果实际数据规模会持续增长，那么初始化时就需要把容量规划考虑进去，否则过滤器会过早逼近设计上限，误判率也会更快上升。

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，而不是手写一套不完整的锁逻辑

如果业务还需要进一步防止“旧持有者在锁失效后继续写入下游系统”，那么通常还要引入 fencing token 或版本号机制，让下游资源只接受更新鲜的操作请求。Redis 锁本身负责的是并发协调，而不是自动替代这类业务侧时序防护。

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

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