9、Redis 高级数据结构 HyperLogLog 和事务

1. HyperLogLog

简介

HyperLogLog 是一种用于基数估计的概率数据结构。它并不是一种新的数据结构，而是 Redis 中的一种字符串类型。HyperLogLog 的主要优点是能够利用极少的内存空间完成对独立总数的统计，适用于统计大量数据的独立元素数量，例如统计网站的 UV（Unique Visitor）。

使用场景

假设你需要开发一个统计网站每天 UV 的模块。统计 PV（Page View）非常简单，每个网页一个独立的 Redis 计数器即可。但统计 UV 则需要去重，同一个用户一天内多次访问只计数一次。这就要求每个网页请求都要带上用户的 ID。

一种简单的方案是为每个页面一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。当一个请求过来时，使用 SADD 命令将用户 ID 塞进去，通过 SCARD 命令取出集合的大小即可获得 UV 数据。然而，如果页面访问量非常大，这种方案会非常浪费内存。

HyperLogLog 的优点

HyperLogLog 提供了不精确的去重计数方案，虽然不精确但误差极小（0.81%）。这种精确度已经足以满足 UV 统计需求。例如，通过 HyperLogLog，可以用 12KB 的内存统计多达 2^64 个数据。

操作命令

1. PFADD

   PFADD key element [element ...]
   

   向 HyperLogLog 添加元素。例如：

   PFADD 08-15:u:id "u1" "u2" "u3" "u4"
   

2. PFCOUNT

   PFCOUNT key [key ...]
   

   计算一个或多个 HyperLogLog 的独立总数。例如：

   PFCOUNT 08-15:u:id
   

3. PFMERGE

   PFMERGE destkey sourcekey [sourcekey ...]
   

   求出多个 HyperLogLog 的并集并赋值给 destkey。

原理概述

HyperLogLog 基于概率论中的伯努利试验，结合了极大似然估算方法，并做了分桶优化。具体来说，HyperLogLog 通过分桶、估算、调和平均数等方法实现了高效的基数估计。

1. 数学原理

   通过 hash 函数将数据转为比特串，从而模拟抛硬币实验。比特串中的 0 和 1 分别代表硬币的反面和正面，通过统计出现正面的位置来估算实验次数。

2. 结合实例理解实现原理

   通过 hash 函数，将用户 ID 转化为比特串，前 14 位用来分桶，剩下的比特位记录首次出现 1 的位置。每个桶中记录 k_max 值，然后通过调和平均数计算总体估算值。

3. Redis 中的 HyperLogLog 实现

   Redis 的 HyperLogLog 实现中，采用 16384 个桶，每个桶 6 位，内存占用 12KB。具体实现中，value 被 hash 成 64 位，前 14 位用于分桶，剩下 50 位记录首次出现 1 的位置。通过多次估算并求平均值，可以得出较为精确的统计结果。

2. Redis 事务

简介

Redis 提供了简单的事务功能，允许将一组命令作为一个整体执行，要么全部执行，要么全部不执行。这对于需要原子性操作的场景非常重要。

事务的基本命令

1. MULTI

   开始事务。例如：

   MULTI
   

2. EXEC

   提交事务，执行事务中的所有命令。例如：

   EXEC
   

3. DISCARD

   取消事务，丢弃事务中的所有命令。例如：

   DISCARD
   

事务中的命令错误处理

1. 命令错误

   如果事务中的命令有语法错误（如将 SET 写成 SETT），整个事务不会执行。

2. 运行时错误

   如果事务中的命令有运行时错误（如将 SADD 写成 ZADD），事务会执行正确的部分，错误部分会返回错误，但不会回滚已经执行的命令。

WATCH 命令

为了确保事务中的 key 没有被其他客户端修改，可以使用 WATCH 命令。WATCH 命令会监视指定的 key，如果在事务执行之前 key 被修改，事务将不会执行。例如：

WATCH key
MULTI
SET key value
EXEC

如果在 MULTI 和 EXEC 之间，其他客户端修改了 key，则 EXEC 将不会执行，返回 nil。

Pipeline 和事务的区别

1. Pipeline

   Pipeline 是客户端的行为，通过将多个命令一起发送，减少网络延迟。服务器无法区分命令是否通过 pipeline 发送，因此无法保证命令的原子性。

2. 事务

   事务是在服务器端实现的，通过 MULTI 和 EXEC 命令保证一组命令的原子性执行。事务中的命令会被服务器缓存，直到 EXEC 命令执行时，才依次执行缓存的命令。

结合使用

可以将事务和 pipeline 结合使用，减少事务命令在网络上的传输时间，提高 Redis 处理查询请求的能力。

3. Redis 7.0 前瞻

Redis 7.0 引入了多个性能优化和新功能，包括降低写入时复制内存的开销、提升内存效率、改进 fsync 避免大量磁盘写入、优化延迟表现、Redis 函数、细粒度权限、改进子命令处理和 Lua 脚本等。

Redis 主从复制原理

1. 全量同步

   主库通过 fork 子进程生成内存快照，将数据序列化为 RDB 格式同步到从库。

2. 命令传播

   主从完成全量同步后，主库将变更数据的命令发送到从库，使从库数据与主库保持一致。

Redis 复制缓存区相关问题分析

1. 多从库时主库内存占用过多

   主库为每个从库分配独立的复制缓冲区，导致内存占用过多。

2. OutputBuffer 拷贝和释放的堵塞问题

   OutputBuffer 数据量大时，拷贝和释放操作可能造成堵塞，影响性能。

3. ReplicationBacklog 的限制

   ReplicationBacklog 是实现部分重同步的基础，但其大小限制和拷贝问题需要解决。

Redis 7.0 共享复制缓存区的设计与实现

Redis 7.0 引入共享复制缓存区方案，通过将复制数据放在全局的缓冲区中，多个从库共享这份数据，减少内存占用。

1. ReplicationBuffer 的裁剪和释放

   Redis 通过减少引用计数来裁剪和释放 ReplicationBuffer。具体来说，当从库使用完某个数据块时，减少其引用计数，引用计数为 0 时释放数据块。

2. 数据结构的选择

   Redis 7.0 使用 rax 树实现 replBufBlock 的索引，提高查询效率。rax 树占用内存少，查询效率高，适用于大规模数据的索引和查询。

4. 总结

HyperLogLog 和事务是 Redis 中两个重要的高级功能。HyperLogLog 提供了高效的基数估计算法，适用于大数据场景的去重统计。Redis 事务提供了简单的原子性操作，适用于需要保证数据一致性的场景。通过 Redis 7.0 的优化和新功能，Redis 的性能和扩展性进一步提升，适用于更多复杂的应用场景。