優(yōu)雅快速的統(tǒng)計(jì)千萬(wàn)級(jí)別uv

定義

PV是page view的縮寫(xiě)，即頁(yè)面瀏覽量，通常是衡量一個(gè)網(wǎng)絡(luò)新聞?lì)l道或網(wǎng)站甚至一條網(wǎng)絡(luò)新聞的主要指標(biāo)。網(wǎng)頁(yè)瀏覽數(shù)是評(píng)價(jià)網(wǎng)站流量最常用的指標(biāo)之一，簡(jiǎn)稱(chēng)為PV

UV是unique visitor的簡(jiǎn)寫(xiě)，是指通過(guò)互聯(lián)網(wǎng)訪問(wèn)、瀏覽這個(gè)網(wǎng)頁(yè)的自然人。

通過(guò)以上的概念，可以清晰的看出pv是比較好設(shè)計(jì)的，網(wǎng)站的每一次被訪問(wèn)，pv都會(huì)增加，但是uv就不一定會(huì)增加了，uv本質(zhì)上記錄的是按照某個(gè)標(biāo)準(zhǔn)劃分的自然人，這個(gè)標(biāo)準(zhǔn)其實(shí)我們可以自己去定義，比如：可以定義同一個(gè)IP的訪問(wèn)者為同一個(gè)UV，這也是最常見(jiàn)的uv定義之一，另外還有根據(jù)cookie定義等等。無(wú)論是pv還是uv，都需要一個(gè)時(shí)間段來(lái)加以描述，平時(shí)我們所說(shuō)的pv，uv數(shù)量指的都是24小時(shí)之內(nèi)（一個(gè)自然日）的數(shù)據(jù)。

pv相比較uv來(lái)說(shuō)，技術(shù)上比較容易一些，今天咱們就來(lái)說(shuō)一說(shuō)uv的統(tǒng)計(jì)，為什么說(shuō)uv的統(tǒng)計(jì)相對(duì)來(lái)說(shuō)比較難呢，因?yàn)閡v涉及到同一個(gè)標(biāo)準(zhǔn)下的自然人的去重，尤其是一個(gè)uv千萬(wàn)級(jí)別的網(wǎng)站，設(shè)計(jì)一個(gè)好的uv統(tǒng)計(jì)系統(tǒng)也許并非想象的那么容易。

那我們就來(lái)設(shè)計(jì)一個(gè)以一個(gè)自然日為時(shí)間段的uv統(tǒng)計(jì)系統(tǒng)，一個(gè)自然人（uv）的定義為同一個(gè)來(lái)源IP（當(dāng)然你也可以自定義其他標(biāo)準(zhǔn)），數(shù)據(jù)量級(jí)別假設(shè)為每日千萬(wàn)uv的量級(jí)。

注意：今天我們討論的重點(diǎn)是獲取到自然人定義的信息之后如何設(shè)計(jì)uv統(tǒng)計(jì)系統(tǒng)，并非是如何獲取自然人的定義。uv系統(tǒng)的設(shè)計(jì)并非想象的那么簡(jiǎn)單，因?yàn)閡v可能隨著網(wǎng)站的營(yíng)銷(xiāo)策略會(huì)出現(xiàn)瞬間大流量，比如網(wǎng)站舉辦了一個(gè)秒殺活動(dòng)。

基于DB方案

服務(wù)端編程有一句名言曰：沒(méi)有一個(gè)表解決不了的功能，如果有那就兩個(gè)表三個(gè)表。一個(gè)uv統(tǒng)計(jì)系統(tǒng)確實(shí)可以基于數(shù)據(jù)庫(kù)來(lái)實(shí)現(xiàn)，而且也不復(fù)雜，uv統(tǒng)計(jì)的記錄表可以類(lèi)似如下（不要太糾結(jié)以下表設(shè)計(jì)是否合理）：

當(dāng)一個(gè)請(qǐng)求到達(dá)服務(wù)器，服務(wù)端每次需要查詢(xún)一次數(shù)據(jù)庫(kù)是否有當(dāng)前IP和當(dāng)前時(shí)間的訪問(wèn)記錄，如果有，則說(shuō)明是同一個(gè)uv，如果沒(méi)有，則說(shuō)明是新的uv記錄，插入數(shù)據(jù)庫(kù)。當(dāng)然以上兩步也可以寫(xiě)到一個(gè)sql語(yǔ)句中：

if exists( select 1 from table where ip='ip' and dayid=dayid )
　　Begin
　　　　return 0
　　End
else
　　Begin
 　　　 insert into table .......
　　End

所有基于數(shù)據(jù)庫(kù)的解決方案，在數(shù)據(jù)量大的情況下幾乎都更容易出現(xiàn)瓶頸。面對(duì)每天千萬(wàn)級(jí)別的uv統(tǒng)計(jì)，基于數(shù)據(jù)庫(kù)的這種方案也許并不是最優(yōu)的。

優(yōu)化方案

面對(duì)每一個(gè)系統(tǒng)的設(shè)計(jì)，我們都應(yīng)該沉下心來(lái)思考具體的業(yè)務(wù)。至于uv統(tǒng)計(jì)這個(gè)業(yè)務(wù)有幾個(gè)特點(diǎn)：

1. 每次請(qǐng)求都需要判斷是否已經(jīng)存在相同的uv記錄

2. 持久化uv數(shù)據(jù)不能影響正常的業(yè)務(wù)

3. uv數(shù)據(jù)的準(zhǔn)確性可以忍受一定程度的誤差

哈希表

基于數(shù)據(jù)庫(kù)的方案中，在大數(shù)據(jù)量的情況下，性能的瓶頸引發(fā)原因之一就是：判斷是否已經(jīng)存在相同記錄，所以要優(yōu)化這個(gè)系統(tǒng)，肯定首先是要優(yōu)化這個(gè)步驟。根據(jù)菜菜以前的文章，是否可以想到解決這個(gè)問(wèn)題的數(shù)據(jù)結(jié)構(gòu)，對(duì)，就是哈希表。哈希表根據(jù)key來(lái)查找value的時(shí)間復(fù)雜度為O（1）常數(shù)級(jí)別，可以完美的解決查找相同記錄的操作瓶頸。

也許在uv數(shù)據(jù)量比較小的時(shí)候，哈希表也許是個(gè)不錯(cuò)的選擇，但是面對(duì)千萬(wàn)級(jí)別的uv數(shù)據(jù)量，哈希表的哈希沖突和擴(kuò)容，以及哈希表占用的內(nèi)存也許并不是好的選擇了。假設(shè)哈希表的每個(gè)key和value 占用10字節(jié)，1千萬(wàn)的uv數(shù)據(jù)大約占用 100M，對(duì)于現(xiàn)代計(jì)算機(jī)來(lái)說(shuō)，100M其實(shí)不算大，但是有沒(méi)有更好的方案呢？

優(yōu)化哈希表

基于哈希表的方案，在千萬(wàn)級(jí)別數(shù)據(jù)量的情況下，只能算是勉強(qiáng)應(yīng)付，如果是10億的數(shù)據(jù)量呢？那有沒(méi)有更好的辦法搞定10億級(jí)數(shù)據(jù)量的uv統(tǒng)計(jì)呢？這里拋開(kāi)持久化數(shù)據(jù)，因?yàn)槌志没O(shè)計(jì)到數(shù)據(jù)庫(kù)的分表分庫(kù)等優(yōu)化策略了，咱們以后再談。有沒(méi)有更好的辦法去快速判斷在10億級(jí)別的uv中某條記錄是否存在呢？

為了盡量縮小使用的內(nèi)存，我們可以這樣設(shè)計(jì)，可以預(yù)先分配bit類(lèi)型的數(shù)組，數(shù)組的大小是統(tǒng)計(jì)的最大數(shù)據(jù)量的一個(gè)倍數(shù)，這個(gè)倍數(shù)可以自定義調(diào)整。現(xiàn)在假設(shè)系統(tǒng)的uv最大數(shù)據(jù)量為1千萬(wàn)，系統(tǒng)可以預(yù)先分配一個(gè)長(zhǎng)度為5千萬(wàn)的bit數(shù)組，bit占用的內(nèi)存最小，只占用一位。按照一個(gè)哈希沖突比較小的哈希函數(shù)計(jì)算每一個(gè)數(shù)據(jù)的哈希值，并設(shè)置bit數(shù)組相應(yīng)哈希值位置的值為1。由于哈希函數(shù)都有沖突，有可能不同的數(shù)據(jù)會(huì)出現(xiàn)相同的哈希值，出現(xiàn)誤判，但是我們可以用多個(gè)不同的哈希函數(shù)來(lái)計(jì)算同一個(gè)數(shù)據(jù)，來(lái)產(chǎn)生不同的哈希值，同時(shí)把這多個(gè)哈希值的數(shù)組位置都設(shè)置為1，從而大大減少了誤判率，剛才新建的數(shù)組為最大數(shù)據(jù)量的一個(gè)倍數(shù)也是為了減小沖突的一種方式（容量越大，沖突越小）。當(dāng)一個(gè)1千萬(wàn)的uv數(shù)據(jù)量級(jí)，5千萬(wàn)的bit數(shù)組占用內(nèi)存才幾十M而已，比哈希表要小很多，在10億級(jí)別下內(nèi)存占用差距將會(huì)更大。

以下為代碼示例：

class BloomFilter
    {
        BitArray container = null;
      public BloomFilter(int length)
        {
            container = new BitArray(length);
        }

        public void Set(string key)
        {
            var h2 = Hash2(key);
            var h3 = Hash3(key);
            var h4 = Hash4(key);
            var h5 = Hash5(key);
            container[h2] = true;
            container[h3] = true;
            container[h4] = true;
            container[h5] = true;

        }
        public bool Get(string key)
        {
            var h2 = Hash2(key);
            var h3 = Hash3(key);
            var h4 = Hash4(key);
            var h5 = Hash5(key);

            return container[h2] && container[h3] && container[h4] && container[h5];
        }

        //模擬哈希函數(shù)1
         int Hash2(string key)
        {
            int hash = 5381;
            int i;
            int count;
            char[] bitarray = key.ToCharArray();
            count = bitarray.Length;
            while (count > 0)
            {
                hash += (hash << 5) + (bitarray[bitarray.Length - count]);
                count--;
            }
            return (hash & 0x7FFFFFFF) % container.Length;

        }
         int Hash3(string key)
        {
            int seed = 131; // 31 131 1313 13131 131313 etc..
            int hash = 0;
            int count;
            char[] bitarray = (key+"key2").ToCharArray();
            count = bitarray.Length;
            while (count > 0)
            {
                hash = hash * seed + (bitarray[bitarray.Length - count]);
                count--;
            }

            return (hash & 0x7FFFFFFF)% container.Length;
        }
         int Hash4(string key)
        {
            int hash = 0;
            int i;
            int count;
            char[] bitarray = (key + "keykey3").ToCharArray();
            count = bitarray.Length;
            for (i = 0; i < count; i++)
            {
                if ((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ (bitarray[i]) ^ (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash << 11) ^ (bitarray[i]) ^ (hash >> 5)));
                }
                count--;
            }

            return (hash & 0x7FFFFFFF) % container.Length;

        }
        int Hash5(string key)
        {
            int hash = 5381;
            int i;
            int count;
            char[] bitarray = (key + "keykeyke4").ToCharArray();
            count = bitarray.Length;
            while (count > 0)
            {
                hash += (hash << 5) + (bitarray[bitarray.Length - count]);
                count--;
            }
            return (hash & 0x7FFFFFFF) % container.Length;
        }
    }

測(cè)試程序?yàn)椋?/p>

BloomFilter bf = new BloomFilter(200000000);
            int exsitNumber = 0;
            int noExsitNumber = 0;

            for (int i=0;i < 10000000; i++)
            {
                string key = $"ip_{i}";
                var isExsit= bf.Get(key);
                if (isExsit)
                {
                    exsitNumber += 1;
                }
                else
                {
                    bf.Set(key);
                    noExsitNumber += 1;
                }
            }
            Console.WriteLine($"判斷存在的數(shù)據(jù)量：{exsitNumber}");
            Console.WriteLine($"判斷不存在的數(shù)據(jù)量：{noExsitNumber}");

測(cè)試結(jié)果：

判斷存在的數(shù)據(jù)量：7017
判斷不存在的數(shù)據(jù)量：×××983

占用內(nèi)存40M，誤判率不到 千分之1，在這個(gè)業(yè)務(wù)場(chǎng)景下在可接受范圍之內(nèi)。在真正的業(yè)務(wù)當(dāng)中，系統(tǒng)并不會(huì)在啟動(dòng)之初就分配這么大的bit數(shù)組，而是隨著沖突增多慢慢擴(kuò)容到一定容量的。

異步優(yōu)化

當(dāng)判斷一個(gè)數(shù)據(jù)是否已經(jīng)存在這個(gè)過(guò)程解決之后，下一個(gè)步驟就是把數(shù)據(jù)持久化到DB，如果數(shù)據(jù)量較大或者瞬間數(shù)據(jù)量較大，可以考慮使用mq或者讀寫(xiě)IO比較大的NOSql來(lái)代替直接插入關(guān)系型數(shù)據(jù)庫(kù)。

思路一轉(zhuǎn)，整個(gè)的uv流程其實(shí)也都可以異步化，而且也推薦這么做。