关于java:Redis-HyperLogLog-是什么这些场景使用它让我枪出如龙一笑破苍穹

在挪动互联网的业务场景中，数据量很大，咱们须要保留这样的信息：一个 key 关联了一个数据汇合，同时对这个数据汇合做统计。

比方：

统计一个 APP 的日活、月活数；
统计一个页面的每天被多少个不同账户访问量（Unique Visitor，UV））；
统计用户每天搜寻不同词条的个数；
统计注册 IP 数。

通常状况下，咱们面临的用户数量以及访问量都是微小的，比方 百万、千万级别的用户数量，或者千万级别、甚至亿级别 的访问信息。

明天「码哥」别离应用不同的数据类型来实现：统计一个页面的每天被多少个不同账户访问量这个性能，循序渐进的引出 HyperLogLog的原理与 Java 中整合 Redission 实战。

通知大家一个技巧，Redis 官方网站当初能在线运行 Redis 指令了：https://redis.io/。如图：

一个用户一天内屡次拜访一个网站只能算作一次 ，所以很容易就想到通过 Redis 的 Set 汇合 来实现。

比方微信 ID 为「肖菜鸡」拜访「Redis 为什么这么快」这篇文章时，咱们把这个信息存到 Set 中。

SADD Redis 为什么这么快:uv 肖菜鸡 谢霸哥 肖菜鸡
(integer) 1

「肖菜鸡」屡次拜访「Redis 为什么这么快」页面，Set 的去重性能保障不会重复记录同一个「微信 ID」。

通过 SCARD 命令，统计「Redis 为什么这么快」页面 UV。指令返回一个汇合的元素个数（也就是用户 ID）。

SCARD Redis 为什么这么快:uv
(integer) 2

码老湿，还能够利用 Hash 类型实现，将用户 ID 作为 Hash 汇合的 key，拜访页面则执行 HSET 命令将 value 设置成 1。

即便「肖菜鸡」反复拜访页面，反复执行命令，也只会把 key 等于「肖菜鸡」的 value 设置成 1。

最初，利用 HLEN 命令统计 Hash 汇合中的元素个数就是 UV。

如下：

HSET Redis 为什么这么快 肖菜鸡 1
// 统计 UV
HLEN Redis 为什么这么快

Bitmap 的底层数据结构用的是 String 类型的 SDS 数据结构来保留位数组，Redis 把每个字节数组的 8 个 bit 位利用起来，每个 bit 位示意一个元素的二值状态（不是 0 就是 1）。

Bitmap 提供了 GETBIT、SETBIT 操作，通过一个偏移值 offset 对 bit 数组的 offset 地位的 bit 位进行读写操作，须要留神的是 offset 从 0 开始。

能够将 Bitmap 看成是一个 bit 为单位的数组，数组的每个单元只能存储 0 或者 1，数组的下标在 Bitmap 中叫做 offset 偏移量。

为了直观展现，咱们能够了解成 buf 数组的每个字节用一行示意，每一行有 8 个 bit 位，8 个格子别离示意这个字节中的 8 个 bit 位，如下图所示：

8 个 bit 组成一个 Byte，所以 Bitmap 会极大地节俭存储空间。 这就是 Bitmap 的劣势。

如何应用 Bitmap 来统计页面的独立用户访问量呢？

Bitmap 提供了 SETBIT 和 BITCOUNT 操作，前者通过一个偏移值 offset 对 bit 数组的 offset 地位的 bit 位进行写操作，须要留神的是 offset 从 0 开始。

后者统计给定指定的 bit 数组中，值 = 1 的 bit 位的数量。

须要留神的事，咱们须要把「微信 ID」转换成数字，因为offset 是下标。

假如咱们将「肖菜鸡」转换成编码6。

第一步，执行上面指令示意「肖菜鸡」的编码为 6 并拜访「巧用 Redis 数据类型实现亿级数据统计」这篇文章。

SETBIT 巧用 Redis 数据类型实现亿级数据统计 6 1

第二步，统计页面拜访次数，应用 BITCOUNT 指令。该指令用于统计给定的 bit 数组中，值 = 1 的 bit 位的数量。

BITCOUNT 巧用 Redis 数据类型实现亿级数据统计

Set 虽好，如果文章十分火爆达到千万级别，一个 Set 就保留了千万个用户的 ID，页面多了耗费的内存也太大了。

同理，Hash 数据类型也是如此。

至于 Bitmap，它更适宜于「二值状态统计」的应用场景，统计精度高，尽管内存占用要比 HashMap 少，然而对于大量数据还是会占用较大内存。

咋办呢？

这些就是典型的「基数统计」利用场景，基数统计：统计一个汇合中不反复元素的个数。

HyperLogLog 的长处在于 它所需的内存并不会因为汇合的大小而扭转，无论汇合蕴含的元素有多少个，HyperLogLog 进行计算所需的内存总是固定的，并且是非常少的。

每个 HyperLogLog 最多只须要破费 12KB 内存，在标准误差 0.81%的前提下，就能够计算 2 的 64 次方个元素的基数。

HyperLogLog 应用太简略了。PFADD、PFCOUNT、PFMERGE三个指令打天下。

将拜访页面的每个用户 ID 增加到 HyperLogLog 中。

PFADD Redis 主从同步原理:uv userID1 userID 2 useID3

利用 PFCOUNT 获取「Redis 主从同步原理」文章的 UV 值。

PFCOUNT Redis 主从同步原理:uv

HyperLogLog` 除了下面的 `PFADD` 和 `PFCOIUNT` 外，还提供了 `PFMERGE

PFMERGE destkey sourcekey [sourcekey ...]

比方在网站中咱们有两个内容差不多的页面，经营说须要这两个页面的数据进行合并。

其中页面的 UV 访问量也须要合并，那这个时候 PFMERGE 就能够派上用场了，也就是 同样的用户拜访这两个页面则只算做一次。

如下所示：Redis、MySQL 两个 HyperLogLog 汇合别离保留了两个页面用户拜访数据。

PFADD Redis 数据 user1 user2 user3
PFADD MySQL 数据 user1 user2 user4
PFMERGE 数据库 Redis 数据 MySQL 数据
PFCOUNT 数据库 // 返回值 = 4

将多个 HyperLogLog 合并（merge）为一个 HyperLogLog，合并后的 HyperLogLog 的基数靠近于所有输出 HyperLogLog 的可见汇合（observed set）的并集。

user1、user2 都拜访了 Redis 和 MySQL，只算拜访了一次。

具体源码「码哥」上传到 GitHub 了：https://github.com/MageByte-Z…

<dependency>
  <groupId>org.redisson</groupId>
  <artifactId>redisson-spring-boot-starter</artifactId>
  <version>3.16.7</version>
</dependency>

// 增加单个元素
public <T> void add(String logName, T item) {RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
  hyperLogLog.add(item);
}

// 将汇合数据增加到 HyperLogLog
public <T> void addAll(String logName, List<T> items) {RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
  hyperLogLog.addAll(items);
}

/**
 * 将 otherLogNames 的 log 合并到 logName
 *
 * @param logName       以后 log
 * @param otherLogNames 须要合并到以后 log 的其余 logs
 * @param <T>
 */
public <T> void merge(String logName, String... otherLogNames) {RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
  hyperLogLog.mergeWith(otherLogNames);
}

public <T> long count(String logName) {RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
  return hyperLogLog.count();}

@Slf4j
@RunWith(SpringRunner.class)
@SpringBootTest(classes = RedissionApplication.class)
public class HyperLogLogTest {

    @Autowired
    private HyperLogLogService hyperLogLogService;

    @Test
    public void testAdd() {
        String logName = "码哥字节:Redis 为什么这么快:uv";
        String item = "肖菜鸡";
        hyperLogLogService.add(logName, item);
        log.info("增加元素 [{}] 到 log [{}] 中。", item, logName);
    }

    @Test
    public void testCount() {
        String logName = "码哥字节:Redis 为什么这么快:uv";
        long count = hyperLogLogService.count(logName);
        log.info("logName = {} count = {}.", logName, count);
    }

    @Test
    public void testMerge() {ArrayList<String> items = new ArrayList<>();
        items.add("肖菜鸡");
        items.add("谢霸哥");
        items.add("陈小白");

        String otherLogName = "码哥字节:Redis 多线程模型原理与实战:uv";
        hyperLogLogService.addAll(otherLogName, items);
        log.info("增加 {} 个元素到 log [{}] 中。", items.size(), otherLogName);

        String logName = "码哥字节:Redis 为什么这么快:uv";
        hyperLogLogService.merge(logName, otherLogName);
        log.info("将 {} 合并到 {}.", otherLogName, logName);

        long count = hyperLogLogService.count(logName);
        log.info("合并后的 count = {}.", count);
    }
}

HyperLogLog 是一种概率数据结构，它应用概率算法来统计汇合的近似基数。而它算法的最根源则是伯努利过程。

伯努利过程就是一个抛硬币试验的过程。抛一枚失常硬币，落地可能是侧面，也可能是背面，二者的概率都是 1/2。

伯努利过程就是始终抛硬币，直到落地时呈现侧面地位，并记录下抛掷次数k。

比如说，抛一次硬币就呈现侧面了，此时 k 为 1; 第一次抛硬币是背面，则持续抛，直到第三次才呈现侧面，此时 k 为 3。

对于 n 次伯努利过程，咱们会失去 n 个呈现侧面的投掷次数值 k1, k2 ... kn , 其中这里的最大值是 k_max。

依据一顿数学推导，咱们能够得出一个论断：2^{k_ max} 来作为 n 的估计值。

也就是说你能够依据最大投掷次数近似的推算出进行了几次伯努利过程。

所以 HyperLogLog 的根本思维是利用汇合中数字的比特串第一个 1 呈现地位的最大值来预估整体基数，然而这种预估办法存在较大误差，为了改善误差状况，HyperLogLog 中引入分桶均匀的概念，计算 m 个桶的和谐平均值。

Redis 中 HyperLogLog 一共分了 2^14 个桶，也就是 16384 个桶。每个桶中是一个 6 bit 的数组，如下图所示。

对于 HyperLogLog 的原理过于简单，如果想要理解的请移步：

https://www.zhihu.com/questio…
https://en.wikipedia.org/wiki…
用户日活月活怎么统计 – Redis HyperLogLog 详解

Redis 对 HyperLogLog 的存储进行了优化，在计数比拟小的时候，存储空间采纳系数矩阵，占用空间很小。

只有在计数很大，稠密矩阵占用的空间超过了阈值才会转变成浓密矩阵，占用 12KB 空间。

为何只须要 12 KB 呀？

HyperLogLog 实现中用到的是 16384 个桶，也就是 2^14，每个桶的 maxbits 须要 6 个 bits 来存储，最大能够示意 maxbits=63，于是总共占用内存就是 2^14 * 6 / 8 = 12k 字节。

别离应用了 Hash、Bitmap、HyperLogLog 来实现：

Hash：算法简略，统计精度高，大量数据下应用，对于海量数据会占据大量内存；
Bitmap：位图算法，适宜用于「二值统计场景」，具体可参考我这篇文章，对于大量不同页面数据统计还是会占用较大内存。
Set：利用去重个性实现，一个 Set 就保留了千万个用户的 ID，页面多了耗费的内存也太大了。在 Redis 外面，每个 HyperLogLog 键只须要破费 12 KB 内存，就能够计算靠近 2^64 个不同元素的基数。因为 HyperLogLog 只会依据输出元素来计算基数，而不会贮存输出元素自身，所以 HyperLogLog 不能像汇合那样，返回输出的各个元素。
HyperLogLog是一种算法，并非 Redis 独有
目标是做基数统计，故不是汇合，不会保留元数据，只记录数量而不是数值
耗空间极小，反对输出十分体积的数据量
外围是基数估算算法，次要体现为计算时内存的应用和数据合并的解决。最终数值存在肯定误差
Redis中每个Hyperloglog key 占用了 12K 的内存用于标记基数（官网文档）
pfadd 命令并不会一次性调配 12k 内存，而是随着基数的减少而逐步减少内存调配；而 pfmerge 操作则会将 sourcekey 合并后存储在 12k 大小的 key 中，由 hyperloglog 合并操作的原理（两个 Hyperloglog 合并时须要独自比拟每个桶的值）能够很容易了解。
误差阐明：基数预计的后果是一个带有 0.81% 规范谬误（standard error）的近似值。是可承受的范畴
Redis 对 HyperLogLog 的存储进行优化，在计数比拟小时，存储空间采纳稠密矩阵存储，空间占用很小，仅仅在计数缓缓变大，稠密矩阵占用空间慢慢超过了阈值时才会一次性转变成浓密矩阵，才会占用 12k 的空间

Redis 实战篇：巧用数据类型实现亿级数据统计
硬核 | Redis 布隆（Bloom Filter）过滤器原理与实战
Redis 实战篇：巧用 Bitmap 实现亿级海量数据统计
Redis 实战篇：通过 Geo 类型实现左近的人邂逅女神
Redis 分布式锁的正确实现原理演变历程与 Redisson 实战总结

参考资料

关于java:Redis-HyperLogLog-是什么这些场景使用它让我枪出如龙一笑破苍穹

应用 Set 实现

应用 Hash 实现

应用 Bitmap 实现

HyperLogLog 王者计划

Redis 实战

PFADD

PFCOUNT

PFMERGE 应用场景

语法

Redission 实战

pom 依赖

增加数据到 Log

合并

统计基数

单元测试

基本原理

总结

好文举荐