如何用 Redis 统计网站 UV

本贴最后更新于 1885 天前,其中的信息可能已经事过景迁

前言

网页 UV(Unique Visitor)就是指网站的独立用户访问量 Unique Visitor。即相同用户的多次访问需要去重。

思路

一想到 UV 去重,我猜大家都想到了 Set 集合类。

  1. 使用 Set 集合是一个不错的办法,Set 里面存储用户的 Id。每一个用户访问页面的时候,我们直接把 Id 存入 Set,最终获取 Set 的 size 即可。问题就是 Set 的容量需要设置多大呢?如果应用是分布式的,是否需要合并操作?第一个问题其实可以通过计算来估计,如果用户量上亿的话,存储空间也是需要非常大的。第二个问题其实可以通过 Redis、DB 等存储,如 Redis 的 Set 结构,DB 的 unique key。
  2. 我们上面提到的 DB 也是一种解决方案,不过写入量很大,数据库压力会比较大。用户如果很多,则 row 也相应的多,且可能需要对每天的数据进行分表。在用户访问量小的情况下也可以采用该处理方式。

上面两种方式虽然可以实现功能,但是一个比较占用内存,一个比较占用数据库资源。那我们如何规避这两个问题呢。这就来看我们今天要说的一个结构——HyperLogLog。
Redis 里面的 HyperLogLog 结构就提供了我们上面想要的功能,占用空间 12K。

HyperLogLog

HyperLogLog 的使用比较简单,实现略复杂。我们先看一下如何利用 HyperLogLog 来进行统计页面 UV。

Redis 命令使用

# 添加元素
127.0.0.1:6379> pfadd user zhangsan lisi wangwu
# 添加成功返回1,添加失败返回0
(integer) 1
# 统计数量
127.0.0.1:6379> pfcount user
# 返回现在数量
(integer) 3
# 再生成一个pfkey
127.0.0.1:6379> pfadd user2 zhangsan2 lisi2 wangwu
(integer) 1
127.0.0.1:6379> pfcount user2
(integer) 3
# pfmerge会将后面pfkey中的值合并到前面的pfkey中
127.0.0.1:6379> pfmerge user2 user
OK
# 查看merge后的user2
127.0.0.1:6379> pfcount user2
(integer) 5

Java 使用

下面展示是部分代码,完整代码参考 github

HyperLogLog 简单实现
  • 原理
    其实这是个概率问题。我们举个 Java 的例子,我每次将一个字符串放入 HyperLogLog,其实是把字符串转换成了一个值,可以把他当成 hash 值。
    将这个值转换成 2 进制,从后向前看第一个 1 出现的位置。我们假设为 K。那么 1 出现在第三个位置的时候(xxxx x100),概率是多少呢?(1/2)^3=1/8。也就是大概有八个数字进到这个数据结构时,第一个 1 曾出现 在第三个的位置的可能会比较大。
    所以我们只需要维护一个 1 出现位置的最大值(暂且称之为 max position),我们就可以知道整个 HyperLogLog 数量是多少了。

  • 那么去重是如何做的呢?
    我们上面讲到 hash 值,其实整个算法就是将一个固定的 value 固定的映射成一个数字就可以解决重复的问题了。如“zhangsan”对应 8,那么 max position=4,再来一个“zhangsan”,对应 8,则 max position 不变。

  • 特点
    因为是概率问题,总会出现不准确的情况。所以你在尝试 HyperLogLog 时,可以将 user 数量设置大一些,如 100W。所以有可能你看到的是不到 100W,也有可能计算出来的 uv 还比 100W 大。

Java 代码简单实现 HyperLogLog

public class PfTest {

    static class BitKeeper {
        private int maxBits;

        public void random() {
            // 这里的随机数可以当成一个对象的hashCode。long value = new Object().hashCode() ^ (2 << 32);
            long value = ThreadLocalRandom.current().nextLong(2L << 32);
            int bits = lowZeros(value);
            if (bits > this.maxBits) {
                this.maxBits = bits;
            }
        }

        /**
         * 低位有多少个连续0
         * 思路上 ≈ 倒数第一个1的位置
         *
         * @param value
         * @return
         */
        private int lowZeros(long value) {
            int i = 1;
            for (; i < 32; i++) {
                if (value >> i << i != value) {
                    break;
                }
            }
            return i - 1;
        }
    }

    static class Experiment {
        private int n;
        private BitKeeper keeper;

        public Experiment(int n) {
            this.n = n;
            this.keeper = new BitKeeper();
        }

        public void work() {
            for (int i = 0; i < n; i++) {
                this.keeper.random();
            }
        }

        public void debug() {
            double v = Math.log(this.n) / Math.log(2);
            System.out.printf("%d %.2f %d\n", this.n, v, this.keeper.maxBits);
        }
    }

    public static void main(String[] args) {
        for (int i = 10000; i < 1000000; i += 10000) {
            Experiment exp = new Experiment(i);
            exp.work();
            exp.debug();
        }
    }

}

从这段代码你可以看出来,如果只有一个 BitKeeper,那么精度很难控制,BitKeeper 越多,则越精确。所以 redis 在设置 HyperLogLog 的时候,设置了 16384 个桶,也就是 2^14,每个桶的 maxbits 需要 6 个 bits 来存储,最大可以表示 maxbits=63,于是总共占用内存就是 2^14 * 6 / 8 = 12k 字节。

小结

我们从应用场景开始,讲了 HyperLogLog 的使用和原理实现。也用 Java 做了一个简易实现。大家可以动手试试做一个多 BitKeeper 的 demo。

使用 HyperLogLog 需要注意的是

  • HyperLogLog 需要占用 12K 内存的(数据量大的时候),所以 HyperLogLog 不适合单独存储一个 user 相关的信息。
  • HyperLogLog 是有一定的精度损失的。可能比真实数量多,也可能比真实数量少。但是基本上都在 n‰(0<n<10)以内。
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    286 引用 • 248 回帖 • 62 关注
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖
  • uv
    1 引用
  • HyperLogLog
    1 引用

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...