后端经典面试题合集, 如何用 Redis 中的 HyperLogLog 统计页面 UV?
后端经典面试题合集, 如何用 Redis 中的 HyperLogLog 统计页面 UV?
QA
Step 1
Q:: 如何用 Redis 中的 HyperLogLog 统计页面 UV？
A:: Redis 的 HyperLogLog 是一种基于概率的数据结构，用于估计集合中不同元素的基数（也就是独立元素的数量）。相比传统的数据结构，HyperLogLog 的优势在于它的内存占用非常小，约为 12KB，即使是处理数十亿级别的数据，它也能保持这个大小。使用 HyperLogLog 统计页面 UV（独立访问用户数）时，只需要将每个用户的唯一标识（如用户ID、IP地址等）加入到 HyperLogLog 结构中。使用 Redis 命令 PFADD 可以将元素添加到 HyperLogLog，使用 PFCOUNT 可以获取独立元素的估算数量。例如：
PFADD page_uv user_id_1
PFADD page_uv user_id_2
...
PFCOUNT page_uv
这将返回页面的 UV 估算值。
Step 2
Q:: HyperLogLog 为什么在计算 UV 时比 Set 更优？
A:: 虽然 Redis 的 Set 数据结构可以精确地统计独立元素，但随着数据量的增大，Set 的内存占用会急剧增加。而 HyperLogLog 的优点在于它的内存占用几乎不变，无论数据量多大，其内存占用大约为 12KB。然而，HyperLogLog 是一种近似算法，会有极小的误差（误差率约为 0.81%），但对于大多数场景，这种误差是可以接受的。
Step 3
Q:: HyperLogLog 的误差来源是什么？
A:: HyperLogLog 是一种基于哈希技术的概率算法，它通过哈希碰撞和位图记录的方法来估算基数。其误差主要来源于哈希碰撞，因为不同的输入可能会被哈希到同一个位置，导致统计的基数略小于实际值。不过，通过对算法的改进和多个哈希函数的组合使用，这种误差可以被控制在较低范围内，通常在 1% 左右。
Step 4
Q:: 如何减少 HyperLogLog 的误差？
A:: 要减少 HyperLogLog 的误差，可以使用更好的哈希函数以减少哈希碰撞的概率，同时可以通过增加 HyperLogLog 的寄存器数量（Redis 中默认是 2^14 个寄存器）来提高统计精度。这些调整通常会增加内存消耗，但也会显著减少误差。