使用 Redis 統(tǒng)計網(wǎng)站 UV 的方法(概率算法)

文章目錄

• • 前言
  • 思路
  • HyperLogLog
  • • 使用 Redis 命令操作
    • 使用 Java 代碼操作
  • HyperLogLog 實現(xiàn)原理及特點
  • 使用 Java 實現(xiàn) HyperLogLog
  • 小結(jié)

前言

網(wǎng)站 UV 就是指網(wǎng)站的獨(dú)立用戶訪問量Unique Visitor，即相同用戶的多次訪問需要去重。

思路

提到 UV 去重，猜大家都會想到Set集合類。

• 使用Set集合是一個不錯的辦法，Set里面存儲用戶的id。每一個用戶訪問頁面的時候，我們直接把id存入Set，最終獲取Set的size即可。問題就是Set的容量需要設(shè)置多大呢？如果應(yīng)用是分布式的，是否需要合并操作？第一個問題其實可以通過計算來估計，如果用戶量上億的話，存儲空間也是需要非常大的；第二個問題其實可以通過 Redis、DB 等存儲，如 Redis 的Set結(jié)構(gòu)，DB 的唯一鍵。
• 我們上面提到的 DB 也是一種解決方案，不過寫入量很大時，數(shù)據(jù)庫壓力會比較大。用戶如果很多，則row也相應(yīng)的多，且可能需要對每天的數(shù)據(jù)進(jìn)行分表。在用戶訪問量小的情況下，可以采用該處理方式。

上面兩種方式雖然可以實現(xiàn)統(tǒng)計網(wǎng)站 UV 的功能，但是一個比較占用內(nèi)存，一個比較占用數(shù)據(jù)庫資源。那我們該如何規(guī)避這兩個問題呢？在這里，我們就介紹另外一種實現(xiàn)方法，即使用 Redis 里面的HyperLogLog結(jié)構(gòu)，且僅占用12k的空間。

HyperLogLog

HyperLogLog的使用比較簡單，實現(xiàn)略復(fù)雜。我們先看一下如何利用HyperLogLog來進(jìn)行頁面 UV 的統(tǒng)計。

使用 Redis 命令操作

# 添加元素
127.0.0.1:6379> pfadd user zhangsan lisi wangwu
# 添加成功返回1，添加失敗返回0
(integer) 1
# 統(tǒng)計數(shù)量
127.0.0.1:6379> pfcount user
# 返回現(xiàn)在數(shù)量
(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 代碼操作

import org.springframework.data.redis.core.HyperLogLogOperations;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.stereotype.Service;
import javax.annotation.Resource;
@Service
public class RedisService {
    @Resource
    private RedisTemplate < String, String > redisTemplate;
    /*** 記錄用戶訪問** @param user*/
    public long statistic(String Key, String user) {
          HyperLogLogOperations<String,String>hyperLogLog=redisTemplate.opsForHyperLogLog();
            return hyperLogLog.add(Key, user);
        }
        /*** 統(tǒng)計當(dāng)前 UV** @return*/
    public long size(String Key) {
          HyperLogLogOperations<String,String>hyperLogLog=redisTemplate.opsForHyperLogLog();
            return hyperLogLog.size(Key);
        }
        /*** 刪除當(dāng)前 key*/
    public void clear(String Key) {
        HyperLogLogOperations < String,String>hyperLogLog=redisTemplate.opsForHyperLogLog();
        hyperLogLog.delete(Key);
    }
}

HyperLogLog 實現(xiàn)原理及特點

• 原理：其實這是個概率問題。舉個 Java 的例子，我們每次將一個字符串放入HyperLogLog，其實是把字符串轉(zhuǎn)換成了一個值，可以把它當(dāng)成hash值，將這個值轉(zhuǎn)換成 2 進(jìn)制，從后向前看第一個 1 出現(xiàn)的位置。那么 1 出現(xiàn)在第三個位置的時候（xxxx x100），概率是多少呢？(1/2)^3=1/8，也就是大概有八個數(shù)字進(jìn)到這個數(shù)據(jù)結(jié)構(gòu)時，第一個 1 曾出現(xiàn)在第三個的位置的可能會比較大，所以我們只需要維護(hù)一個 1 出現(xiàn)位置的最大值（暫且稱之為max position），我們就可以知道整個HyperLogLog數(shù)量是多少了。
• 去重：我們上面講到hash值，其實整個算法就是將一個固定的value固定的映射成一個數(shù)字就可以解決重復(fù)的問題了。如zhangsan對應(yīng)8，那么max position=4，再來一個zhangsan，還是對應(yīng)8，則max position不變。
• 特點：因為是概率問題，總會出現(xiàn)不準(zhǔn)確的情況，所以你在使用HyperLogLog時，可以將user數(shù)量設(shè)置大一些，如 100W。但是其結(jié)果，有可能你看到的是不到 100W，也有可能計算出來的 UV 還比 100W 大。

使用 Java 實現(xiàn) HyperLogLog

public class HyperLogLogSelf {
    static class BitKeeper {
        private int maxBits;

        public void random() {// 這里的隨機(jī)數(shù)可以當(dāng)成一個對象的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;
            }
        }

        /*** 低位有多少個連續(xù)0* 思路上 ≈ 倒數(shù)第一個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 在設(shè)置HyperLogLog的時候，設(shè)置了16384個桶，也就是2^14，每個桶的maxbits需要 6 個bit來存儲，最大可以表示maxbits=63，于是總共占用內(nèi)存就是2^14 * 6 / 8 = 12k字節(jié)。

小結(jié)

我們從應(yīng)用場景開始，講述了HyperLogLog的使用方法和實現(xiàn)原理，還給出了HyperLogLog的 Java 簡單實現(xiàn)。

最后，我們在使用HyperLogLog的時候，需要注意：文章來源地址http://www.zghlxwxcb.cn/news/detail-480884.html

• HyperLogLog需要占用12k內(nèi)存的（數(shù)據(jù)量大的時候），所以HyperLogLog不適合單獨(dú)存儲一個user相關(guān)的信息；
• HyperLogLog是有一定精度損失的，可能比真實數(shù)量多，也可能比真實數(shù)量少，但基本上都在n‰（0<n<10）以內(nèi)。

到了這里，關(guān)于使用 Redis 統(tǒng)計網(wǎng)站 UV 的方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！