尼恩说在前面

• 如何 统计一个 网站 的日活、月活数？ 亿级用户的日活、月活，如何统计？
• Bitmaps可用于统计日活吗？
• 亿级用户的日活、月活，Bitmaps可以统计吗？
• 如何 统计一个页面的每天被多少个不同账户访问量（Unique Visitor，UV））？
• 如何 统计用户每天搜索不同词条的个数？
• 如何 统计注册 IP 数？

最新《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请关注本公众号【技术自由圈】获取，回复：领电子书

本文目录

- 尼恩说在前面

- 首先回顾一下：redis 四大统计（基数统计，二值统计，排序统计、聚合统计）的原理 和应用场景

 - 第1大统计：基数统计

 - 第2大统计：二值统计

 - 第3大统计：排序统计

 - 第4大统计：聚合统计

- 日活月活，属于 基数统计的类型

- 使用 redis Set 进行基数统计

- 使用 redis bitmap 进行基数统计

- Bitmaps可用于统计日活吗？

- 使用 HyperLogLog进行基数统计

 - 亿级用户日活统计，HyperLogLog 的空间消耗是多大呢？

- HyperLogLog的基本用法

 - HyperLogLog三个命令

    -PFADD

    -PFCOUNT

    -PFMERGE

    -使用 HyperLogLog进行  统计网站日活月活

 - HyperLogLog命令示例

 - HyperLogLog  、Sets命令对比分析

    -HyperLogLog和Sets的区别

- HyperLogLog 使用的注意事项

    -HyperLogLog命令注意事项

- HyperLogLog原理

- HyperLogLog  数学原理 : 极大似然估计 和 伯努利实验

 - 伯努利实验 与  通过二进制位中的位信息来估计基数

 - 伯努利过程的总结

 - HyperLogLog 与 扔硬币实验反向推测的原理

 - HyperLogLog 使用hash算法完成 伯努利试验（/ 扔硬币）

 - HyperLogLog  使用hash算法 扔硬币演示

- HyperLogLog 的底层数据结构

- HyperLogLog 的Redis 源码分析

 - HyperLogLog 的 密集存储结构

 - HyperLogLog 的 稀疏存储结构

- 稀疏存储 转换到密集存储的条件是：

- 在线动态观察HyperLogLog算法

- 尼恩架构团队塔尖的redis 面试题

首先回顾一下：redis 四大统计（基数统计，二值统计，排序统计、聚合统计）的原理 和应用场景

第1大统计：基数统计

第2大统计：二值统计

第3大统计：排序统计

1. 可以 使用ZSET对文章的点赞数排序并分页展示
2. 对评论根据时间进行排序

第4大统计：聚合统计

日活月活，属于 基数统计的类型

• DAU日活：(Daily Active User)日活跃用户数量 常用于反映网站、互联网应用或网络游戏的运营情况。DAU通常统计一日（统计日）之内，登录或使用了某个产品的用户数（去除重复登录的用户）；
• MAU 月活：月活跃用户数量(Monthly Active User，MAU) 月活跃用户数量通常统计一个月（统计月）之内，登录或使用了某个产品的用户数（去除重复登录的用户）；
• PV（Page View）：页面浏览量 指网站页面被访问的总次数。用户每打开一个页面就会被记录一次 PV，多次打开同一页面则累计计数。例如，一个用户在一天内访问了网站的首页 5 次，那么这个首页在这一天的 PV 就是 5。
• UV（Unique Visitor） - 独立访客: 指在一定时间范围内访问网站的不同用户的数量。同一用户无论访问网站多少次，在统计周期内只计算一次 UV。例如，在一天内，用户 A 访问了网站 10 次，用户 B 访问了网站 3 次，那么这一天的 UV 就是 2。注意，DAU 是 UV 的一个子集。因为 DAU 强调的是在一天内有活跃行为的用户，而 UV 只是统计了不同的访问者，这些访问者不一定在当天有实际的活跃行为。

• 数据需要去重；
• 数据允许有一定的偏差，101W和102W差距不大；
• 占用空间尽可能小；

使用 redis Set 进行基数统计

import redis.clients.jedis.Jedis;

public class RedisSetCardinalityDemo {

    public static void main(String[] args) {
        // 连接到Redis服务器
        Jedis jedis = new Jedis("localhost", 6379);

        // 假设要统计用户的访问次数，这里模拟添加用户ID到Set中
        String setKey = "visited_users";

        // 添加一些用户ID到Set中
        jedis.sadd(setKey, "user1", "user2", "user2", "user3", "user4", "user4", "user4");

        // 获取Set的基数，即不同元素的数量
        long cardinality = jedis.scard(setKey);

        System.out.println("基数统计结果：不同元素的数量为 " + cardinality);

        // 关闭Redis连接
        jedis.close();
    }
}

1. 定义了一个 Set 的键名visited_users，用于模拟统计访问过的用户情况。
2. 使用sadd方法向 Set 中添加了多个用户 ID，注意其中有重复的 ID，这正是要通过基数统计来确定不同用户数量的场景。
3. 最后通过scard方法获取 Set 的基数，也就是不同元素（这里即不同用户）的数量，并将结果输出。

使用 redis bitmap 进行基数统计

import redis.clients.jedis.Jedis;

public class RedisBitmapDailyActiveUsersDemo {

    public static void main(String[] args) {
        // 连接到Redis服务器
        Jedis jedis = new Jedis("localhost", 6379);

        // 定义存储日活用户的Bitmap键名，格式可以是 "daily_active_users:日期"，这里假设日期为20241112
        String bitmapKey = "daily_active_users:20241112";

        // 模拟用户ID，这里简单用整数表示，实际应用中可能是更复杂的用户唯一标识
        int[] userIds = {1001, 1002, 1003, 1004, 1005};

        // 将每个用户ID对应的位设置为1，表示该用户当天活跃
        for (int userId : userIds) {
            // 使用SETBIT命令，将用户ID对应的位设置为1
            jedis.setbit(bitmapKey, userId, true);
        }

        // 统计日活用户数量，使用BITCOUNT命令
        long dailyActiveUsersCount = jedis.bitcount(bitmapKey);

        System.out.println("日活用户数量为: " + dailyActiveUsersCount);

        // 关闭Redis连接
        jedis.close();
    }
}

1. 定义了一个用于存储日活用户的 Bitmap 键名，这里按照daily_active_users:日期的格式进行定义，示例中假设日期为20241112。
2. 模拟了一些用户 ID，这里简单用整数表示，实际情况中应该是能唯一标识用户的信息。
3. 然后通过循环，使用SETBIT命令，将每个用户 ID 对应的位在 Bitmap 中设置为 1，表示该用户当天活跃。
4. 最后使用BITCOUNT命令，统计 Bitmap 中值为 1 的位的数量，也就是日活用户的数量，并将结果输出。

Bitmaps可用于统计日活吗？

• 计算日活：bitcount key获取key为1的数量；
• 计算月活：可把30天的所有bitmap做or计算，再进行bitcount计算；
• 计算留存率：昨日留存=昨天今天连续登录的人数/昨天登录的人数，即昨天的bitmap与今天的bitmap进行and计算，再除以昨天bitcount的数量。

使用 HyperLogLog进行基数统计

import redis.clients.jedis.Jedis;

public class RedisHyperLogLogDailyActiveUsersDemo {

    public static void main(String[] args) {
        // 连接到Redis服务器
        Jedis jedis = new Jedis("localhost", 6379);

        // 定义存储日活用户的HyperLogLog键名，格式可设为 "HLL:日期"，这里假设日期为20241112
        String hyperloglogKey = "HLL:20241112";

        // 模拟用户ID，实际应用中可能是从用户访问日志等获取真实的用户唯一标识
        int[] userIds = {1001, 1002, 1002, 1003, 1004, 1004, 1004};

        // 将每个用户ID对应的信息添加到HyperLogLog中，以统计日活
        for (int userId : userIds) {
            // 使用PFADD命令将用户ID添加到HyperLogLog结构中
            jedis.pfadd(hyperloglogKey, String.valueOf(userId));
        }

        // 获取日活用户的基数估计值，即不同用户的数量估计
        long dailyActiveUsersCount = jedis.pfcount(hyperloglogKey);

        System.out.println("日活用户数量估计值: " + dailyActiveUsersCount);

        // 关闭Redis连接
        jedis.close();
    }
}

1. 定义了一个用于存储日活用户的 HyperLogLog 键名，按照HLL:日期的格式进行定义，示例中假设日期为20241112。
2. 模拟了一些用户 ID，这里简单用整数表示，实际情况应从真实的用户访问日志等获取能唯一标识用户的信息。
3. 然后通过循环，使用PFADD命令将每个用户 ID 对应的信息添加到 HyperLogLog 结构中，以此来统计日活用户。
4. 最后使用PFCOUNT命令获取 HyperLogLog 的基数估计值，也就是日活用户数量的估计值，并将结果输出。

亿级用户日活统计，HyperLogLog 的空间消耗是多大呢？

HyperLogLog的基本用法

HyperLogLog三个命令

HLL操作命令中的PF含义：HyperLogLog 数据结构的发明人 Philippe Flajolet 的首字母缩写。

PFADD

PFCOUNT

需要注意的是：该命令会改变HyperLogLog，因此使用8个字节来存储上一次计算的基数。所以，从技术角度来讲，PFCOUNT是一个写命令。而多数PFADD命令不会更新寄存器，PFCOUNT 才进行 基数统计 ，这样PFADD 才可以达到每秒上百次请求的效果。不过，虽然PFCOUNT慢，但是 PFCOUNT会缓存上一次结算的基数结果。

PFMERGE

PFMERGE  HLL:20241110   …  HLL:20241129    HLL:20241130     HLL:20241131

使用 HyperLogLog进行 统计网站日活月活

HyperLogLog命令示例

127.0.0.1:6379> pfadd hll 1
(integer) 1
127.0.0.1:6379> pfadd hll 1
(integer) 0
127.0.0.1:6379> pfadd hll 2 3 4
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 4
127.0.0.1:6379> pfcount hll:notexist
(integer) 0
127.0.0.1:6379> pfadd hll2 a b
(integer) 1
127.0.0.1:6379> pfcount hll2
(integer) 2
127.0.0.1:6379> pfcount hll hll2
(integer) 6
127.0.0.1:6379> get hll
"HYLL\x01\x00\x00\x00\x04\x00\x00\x00\x00\x00\x00\x00A\xee\x84[v\x80Mt\x80Q,\x8cC\xf3"
127.0.0.1:6379> set hll:error error666
OK
127.0.0.1:6379> pfcount hll:error
(error) WRONGTYPE Key is not a valid HyperLogLog string value.

127.0.0.1:6379> pfadd hllm1 1 2 3 4 5
(integer) 1
127.0.0.1:6379> pfadd hllm2 5 6 7 8
(integer) 1
127.0.0.1:6379> pfmerge hllm3 hllm1 hllm2
OK
127.0.0.1:6379> pfcount hllm3
(integer) 8

127.0.0.1:6379> pfadd hllm4 7 8 9 10 11 12 14 14
(integer) 1
127.0.0.1:6379> pfmerge hllm4 hllm1 hllm2
OK
127.0.0.1:6379> pfcount hllm4
(integer) 13

HyperLogLog 、Sets命令对比分析

HyperLogLog和Sets的区别

HyperLogLog 使用的注意事项

HyperLogLog命令注意事项

• PFADD仅存储标记，不存储元素本身；
• PFCOUNT实际是一个write命令，执行PFCOUNT时可能会重新计算计数值并存储；
• key有多个时，PFCOUNT会动态合并计算，并且计算结果不会被缓存，所以生产环境执行PFCOUNT时尽量避免带多个key；
• key有多个时，PFCOUNT是先合并再计算，结果为多个对象合并<去重>后的基数值（注意：不是基数值之和）；
• PFMERGE计算的是sourcekey的并集；
• 如果destkey已存在，则PFMERGE执行后destkey最终的结果是dest+source的并集；

HyperLogLog原理

HyperLogLog 数学原理 : 极大似然估计 和 伯努利实验

• A口袋中是99个白球1个黑球
• B口袋中是99个黑球1个白球。

• 如果拿出的球是 白色的，那么我们可以说“大概率”我们取出的是A口袋。
• 如果拿出的球是 黑色的，那么我们可以说“大概率”我们取出的是B口袋。

伯努利实验 与 通过二进制位中的位信息来估计基数

• 如果我们扔2次硬币， 2次都是正面 的概率为1/4。
• 如果我们扔10次硬币呢， 10次都是正面 的 概率为1/1024。
• 扔100次硬币 ， 可能10次都是正面 ，概率为 1/(2^100)。
• 假如扔了n次，那么n次都是正面的概率为 1/(2^n )。

• 抛了5次硬币，前4次都是正面朝上，第5次是反面朝上，我们就记录下次数5，概率为1/(2^5)，就是 1/32。
• 扔10次硬币 ，前9次都是正面朝上，第10次是反面朝上，概率为1/1024。
• 假如扔了n次，那么n-1次都是正面的概率为，第n次是反面朝上，概率为 1/(2^n)。

• 抛硬币实验，前4次都是正面朝上，第5次是反面朝上的概率是 1/32， 我们如果要实现这个结果，条件是 需要抛出 32次硬币。
• 抛硬币实验，前9次都是正面朝上，第10次是反面朝上的概率是1/1024， 我们如果要实现这个结果，条件是 需要抛出 1024 次硬币。
• 抛硬币实验，前n-1次都是正面朝上，第n次是反面朝上的概率是1/(2^n)， 我们如果要实现这个结果，条件是 需要抛出2^n次硬币。

伯努利过程的总结

HyperLogLog 与 扔硬币实验反向推测的原理

HyperLogLog 使用hash算法完成 伯努利试验（/ 扔硬币）

• 从右边开始，第一个为1的bit出现的位数是第5位，相当于 第5次是反面朝上的概率是 1/32， 我们如果要实现这个结果，条件是 需要抛出 32次硬币， 集合基数为 32 。
• 从右边开始，第一个为1的bit出现的位数是第10位，相当于第10次是反面朝上的概率是1/1024， 我们如果要实现这个结果，条件是 需要抛出 1024 次硬币， 集合基数为 1024 。
• 从右边开始，第一个为1的bit出现的位数是第n位，相当于第n次是反面朝上的概率是1/(2^n)， 我们如果要实现这个结果，条件是 需要抛出2^n次硬币， 集合基数为 2^n。
• 从右边开始，第一个为1的bit出现的位数是第40位，相当于第40次是反面朝上的概率是1/(2^40)， 我们如果要实现这个结果，条件是 需要抛出2^40次硬币， 集合基数为 2^40。

说句题外话，依托于20年+技术内功，简历神僧 尼恩团队 经常性的、把复杂的问题做清晰深入的穿透式、起底式的分析：

• 比如 Netty的内存池和对象池
• 比如DDD的建模和落地，
• 比如Caffeine的底层架构，
• 比如高性能葵花宝典
• 比如 Thread Local 学习圣经 等等等等。

上面的很多难点， 超级难， 超级难，其实穷其一生，很多人 都搞 懂， 尼恩团队用深厚的 技术内功，给大家把难题化解了。具体，请参见尼恩的 各种技术圣经 PDF。

HyperLogLog 使用hash算法 扔硬币演示

10100100

01101000

HyperLogLog 的底层数据结构

switch (p) {
   case 4:
       constant = 0.673 * m * m;
   case 5:
       constant = 0.697 * m * m;
   case 6:
       constant = 0.709 * m * m;
   default:
       constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}

HyperLogLog 的Redis 源码分析

struct hllhdr {
    char magic[4];      /* 魔法值 "HYLL" */
    uint8_t encoding;   /* 密集结构或者稀疏结构 HLL_DENSE or HLL_SPARSE. */
    uint8_t notused[3]; /* 保留位, 全为0. */
    uint8_t card[8];    /* 基数大小的缓存 */
    uint8_t registers[]; /* 数据字节数组 */
};

• magic[4]
  这是一个长度为 4 的字符数组，用于存储魔法值（Magic Number）。
  在这里，魔法值被定义为"HYLL"。
  魔法值的主要作用是在程序运行过程中，用于识别数据结构的类型， 尤其是从 文件中进行 hyll 结构的反序列化的场景。
  当读取数据时，通过检查这个魔法值，可以快速确定数据是否是期望的 HyperLogLog 结构。
  例如，在从存储介质（尤其是文件）中读取数据时，如果前 4 个字节不是"HYLL"，就可以判断数据可能损坏或者不是 HyperLogLog 结构的数据。
• encoding
  这是一个uint8_t类型（无符号 8 位整数）的变量。
  它用于指示 HyperLogLog 数据结构是密集型（HLL_DENSE）还是稀疏型（HLL_SPARSE）类型。
  这种区分很重要，因为 HyperLogLog 在不同的数据分布和规模下，可能会采用不同的内部存储方式来优化空间和计算效率。
  在密集型结构中，数据的存储和处理方式可能更偏向于紧凑和高效的数组形式；
  而在稀疏型结构中，可能会采用更节省空间的方式来存储相对较少的元素信息，以适应元素数量较少或者分布比较特殊的情况。
• notused[3]
  这是一个长度为 3 的uint8_t数组，被标记为保留位（Reserved Bits），并且全部初始化为 0。
  这些保留位的存在通常是为了未来可能的扩展或者结构调整。
  在当前版本的定义中，它们没有被使用，但在对数据结构进行升级或者修改时，可以利用这些位来添加新的功能或者属性，而不会破坏现有的数据兼容性。
• card[8]
  这是一个长度为 8 的uint8_t数组 ，总计 64位，用于缓存基数（Cardinality）的大小。
  基数是 HyperLogLog 算法的一个核心概念，它用于估计集合中不同元素的数量。
  通过缓存基数，可以在某些操作中快速获取估计值，而不需要重新计算整个 HyperLogLog 数据结构。
  这种缓存机制有助于提高频繁查询基数操作的效率, 不需要每次都进行计算。
  例如，在需要多次统计集合中不同元素数量的应用场景中，直接从card数组中读取缓存的估计值可以节省计算时间。
• registers[]
  这是一个字节数组，用于存储实际的数据 。
  具体存储的数据内容和格式取决于encoding所指示的结构类型（密集型或稀疏型）。
  在密集型结构中，这些寄存器可能以一种紧密排列的方式，存储元素的哈希信息的 概率位信息，用于基数估计的计算；
  在稀疏型结构中，存储方式进行 了相邻概率位 的压缩，以适应较少元素的情况。
  这些寄存器是 HyperLogLog 算法进行基数估计的关键部分，通过对寄存器中的数据进行分析和计算，可以得出集合中不同元素数量的估计值。

HyperLogLog 的 密集存储结构

HyperLogLog 的 稀疏存储结构

• 压缩结构 ZERO : 一字节，8位，00打头，表示连续多少个桶计数为0，前两位为标志00，后6位表示有多少个桶，最大为64。
• 压缩结构 XZERO : 两个字节，16位，01打头，表示连续多少个桶计数为0，前两位为标志01，后14位表示有多少个桶，最大为16384。
• 压缩结构 VAL : 一字节，8位，1打头，表示连续多少个桶的计数为多少，前一位为标志1，四位表示连桶内计数，所以最大表示桶的计数为32。后两位表示连续多少个桶。

稀疏存储 转换到密集存储的条件是：

• 任意一个计数值从 32 变成 33，因为 VAL 指令已经无法容纳，它能表示的计数值最大为 32
• 稀疏存储占用的总字节数超过 3000 字节，这个阈值可以通过 hll_sparse_max_bytes 参数进行调整。

在线动态观察HyperLogLog算法

尼恩架构团队塔尖的redis 面试题

说在最后：有问题找老架构 / 简历神僧 尼恩  取经‍

亿级用户的日活、月活，如何统计？

按照上面 简历神僧  尼恩的的套路去回答，一定会 吊打面试官，让面试官爱到 “不能自已、口水直流”，然后实现”offer直提”。

空窗8月：中厂大龄34岁，被裁8月收一大厂offer， 年薪65W，转架构后逆天改命!

空窗2年：42岁被裁2年，天快塌了，急救1个月，拿到开发经理offer，起死回生

空窗半年：35岁被裁6个月， 职业绝望，转架构急救上岸，DDD和3高项目太重要了

空窗1.5年：失业15个月，学习40天拿offer， 绝境翻盘，如何实现？