14.高级特性HyperLoglog

一灰灰blog约 1620 字大约 5 分钟

hyperloglog算法，利用非常少的空间，实现比较大的数据量级统计；比如我们前面在介绍bitmap的过程中，说到了日活的统计，当数据量达到百万时，最佳的存储方式是hyperloglog，本文将介绍一下hyperloglog的基本原理，以及redis中的使用姿势

I. 基本使用

1. 配置

我们使用SpringBoot 2.2.1.RELEASE来搭建项目环境，直接在pom.xml中添加redis依赖

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

如果我们的redis是默认配置，则可以不额外添加任何配置；也可以直接在application.yml配置中，如下

spring:
  redis:
    host: 127.0.0.1
    port: 6379
    password:

2. 使用姿势

我们下来看使用姿势，原理放在后面说明

redis中，hyperlolog使用非常简单，一般就两个操作命令，添加pfadd + 计数pfcount；另外还有一个不常用的merge

a. add

添加一条记录

public boolean add(String key, String obj) {
    // pfadd key obj
    return stringRedisTemplate.opsForHyperLogLog().add(key, obj) > 0;
}

b. pfcount

非精准的计数统计

public long count(String key) {
    // pfcount 非精准统计 key的计数
    return stringRedisTemplate.opsForHyperLogLog().size(key);
}

a. merge

将多个hyperloglog合并成一个新的hyperloglog；感觉用的场景并不会特别多

public boolean merge(String out, String... key) {
    // pfmerge out key1 key2  ---> 将key1 key2 合并成一个新的hyperloglog out
    return stringRedisTemplate.opsForHyperLogLog().union(out, key) > 0;
}

3. 原理说明

关于HyperLogLog的原理我这里也不进行详细赘述，说实话那一套算法以及调和平均公式我自己也没太整明白；下面大致说一下我个人的朴素理解

Redis中的HyperLogLog一共分了2^14=16384个桶，每个桶占6个bit

一个数据，塞入HyperLogLog之前，先hash一下，得到一个64位的二进制数据

取低14位，用来定位桶的index
高50位，从低到高数，找到第一个为1出现的位置n
- 若桶中值 > n，则丢掉
- 反之，则设置桶中的值为n

那么怎么进行计数统计呢？

拿所有桶中的值，代入下面的公式进行计算

上面这个公式怎么得出的?

之前看到一篇文章，感觉不错，有兴趣了解原理的，可以移步: https://www.jianshu.com/p/55defda6dcd2open in new window

4. 应用场景

hyperloglog通常是用来非精确的计数统计，前面介绍了日活统计的case，当时使用的是bitmap来作为数据统计，然而当userId分散不均匀，小的特别小，大的特别大的时候，并不适用

在数据量级很大的情况下，hyperloglog的优势非常大，它所占用的存储空间是固定的2^14 下图引用博文《用户日活月活怎么统计》open in new window

使用HyperLogLog进行日活统计的设计思路比较简单

每日生成一个key
某个用户访问之后，执行 pfadd key userId
统计总数: pfcount key

II. 其他

0. 项目

系列博文

工程源码

14.高级特性HyperLoglog

# I. 基本使用

# 1. 配置

# 2. 使用姿势

# a. add

# b. pfcount

# a. merge

# 3. 原理说明

# 4. 应用场景

# II. 其他

# 0. 项目