乐趣区

程序员修仙之路优雅快速的统计千万级别uv留言送书

jiezi

定义

PV 是 page view 的缩写，即页面浏览量，通常是衡量一个网络新闻频道或网站甚至一条网络新闻的主要指标。网页浏览数是评价网站流量最常用的指标之一，简称为 PV

UV 是 unique visitor 的简写，是指通过互联网访问、浏览这个网页的自然人。

通过以上的概念，可以清晰的看出 pv 是比较好设计的，网站的每一次被访问，pv 都会增加，但是 uv 就不一定会增加了，uv 本质上记录的是按照某个标准划分的自然人，这个标准其实我们可以自己去定义，比如：可以定义同一个 IP 的访问者为同一个 UV，这也是最常见的 uv 定义之一，另外还有根据 cookie 定义等等。无论是 pv 还是 uv，都需要一个时间段来加以描述，平时我们所说的 pv，uv 数量指的都是 24 小时之内（一个自然日）的数据。

pv 相比较 uv 来说，技术上比较容易一些，今天咱们就来说一说 uv 的统计，为什么说 uv 的统计相对来说比较难呢，因为 uv 涉及到同一个标准下的自然人的去重，尤其是一个 uv 千万级别的网站，设计一个好的 uv 统计系统也许并非想象的那么容易。

那我们就来设计一个以一个自然日为时间段的 uv 统计系统，一个自然人（uv）的定义为同一个来源 IP（当然你也可以自定义其他标准），数据量级别假设为每日千万 uv 的量级。

注意：今天我们讨论的重点是获取到自然人定义的信息之后如何设计 uv 统计系统，并非是如何获取自然人的定义。uv 系统的设计并非想象的那么简单，因为 uv 可能随着网站的营销策略会出现瞬间大流量，比如网站举办了一个秒杀活动。

基于 DB 方案

服务端编程有一句名言曰：没有一个表解决不了的功能，如果有那就两个表三个表。一个 uv 统计系统确实可以基于数据库来实现，而且也不复杂，uv 统计的记录表可以类似如下（不要太纠结以下表设计是否合理）：

字段 类型 描述
IP varchar(30) 客户端来源 ip
DayID int 时间的简写，例如 20190629
其他字段 int 其他字段描述

当一个请求到达服务器，服务端每次需要查询一次数据库是否有当前 IP 和当前时间的访问记录，如果有，则说明是同一个 uv，如果没有，则说明是新的 uv 记录，插入数据库。当然以上两步也可以写到一个 sql 语句中：

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

所有基于数据库的解决方案，在数据量大的情况下几乎都更容易出现瓶颈。面对每天千万级别的 uv 统计，基于数据库的这种方案也许并不是最优的。

优化方案

面对每一个系统的设计，我们都应该沉下心来思考具体的业务。至于 uv 统计这个业务有几个特点：

  1. 每次请求都需要判断是否已经存在相同的 uv 记录
  2. 持久化 uv 数据不能影响正常的业务
  3. uv 数据的准确性可以忍受一定程度的误差
哈希表

基于数据库的方案中，在大数据量的情况下，性能的瓶颈引发原因之一就是：判断是否已经存在相同记录，所以要优化这个系统，肯定首先是要优化这个步骤。根据菜菜以前的文章，是否可以想到解决这个问题的数据结构，对，就是哈希表。哈希表根据 key 来查找 value 的时间复杂度为 O（1）常数级别，可以完美的解决查找相同记录的操作瓶颈。
也许在 uv 数据量比较小的时候，哈希表也许是个不错的选择，但是面对千万级别的 uv 数据量，哈希表的哈希冲突和扩容，以及哈希表占用的内存也许并不是好的选择了。假设哈希表的每个 key 和 value 占用 10 字节，1 千万的 uv 数据大约占用 100M，对于现代计算机来说，100M 其实不算大，但是有没有更好的方案呢？

优化哈希表

基于哈希表的方案，在千万级别数据量的情况下，只能算是勉强应付，如果是 10 亿的数据量呢？那有没有更好的办法搞定 10 亿级数据量的 uv 统计呢？这里抛开持久化数据，因为持久化设计到数据库的分表分库等优化策略了，咱们以后再谈。有没有更好的办法去快速判断在 10 亿级别的 uv 中某条记录是否存在呢？
为了尽量缩小使用的内存，我们可以这样设计，可以预先分配 bit 类型的数组，数组的大小是统计的最大数据量的一个倍数，这个倍数可以自定义调整。现在假设系统的 uv 最大数据量为 1 千万，系统可以预先分配一个长度为 5 千万的 bit 数组，bit 占用的内存最小，只占用一位。按照一个哈希冲突比较小的哈希函数计算每一个数据的哈希值，并设置 bit 数组相应哈希值位置的值为 1。由于哈希函数都有冲突，有可能不同的数据会出现相同的哈希值，出现误判，但是我们可以用多个不同的哈希函数来计算同一个数据，来产生不同的哈希值，同时把这多个哈希值的数组位置都设置为 1，从而大大减少了误判率，刚才新建的数组为最大数据量的一个倍数也是为了减小冲突的一种方式（容量越大，冲突越小）。当一个 1 千万的 uv 数据量级，5 千万的 bit 数组占用内存才几十 M 而已，比哈希表要小很多，在 10 亿级别下内存占用差距将会更大。

以下为代码示例：

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

        public void Set(string key)
        {var h1 = Hash1(key);
            var h2 = Hash2(key);
            var h3 = Hash3(key);
            var h4 = Hash4(key);
            container[h1] = true;
            container[h2] = true;
            container[h3] = true;
            container[h4] = true;
            
        }
        public bool Get(string key)
        {var h1 = Hash1(key);
            var h2 = Hash2(key);
            var h3 = Hash3(key);
            var h4 = Hash4(key);

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

        // 模拟哈希函数 1
         int Hash1(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 Hash2(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 Hash3(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 Hash4(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;
        }
    }

测试程序为：

 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($"判断存在的数据量：{exsitNumber}");
            Console.WriteLine($"判断不存在的数据量：{noExsitNumber}");

测试结果：

 判断存在的数据量：7017
判断不存在的数据量：9992983

占用内存 40M，误判率不到 千分之 1，在这个业务场景下在可接受范围之内。在真正的业务当中，系统并不会在启动之初就分配这么大的 bit 数组，而是随着冲突增多慢慢扩容到一定容量的。

异步优化

当判断一个数据是否已经存在这个过程解决之后，下一个步骤就是把数据持久化到 DB，如果数据量较大或者瞬间数据量较大，可以考虑使用 mq 或者读写 IO 比较大的 NOSql 来代替直接插入关系型数据库。

思路一转，整个的 uv 流程其实也都可以异步化，而且也推荐这么做。

点击添加关注，留言送技术书啦

退出移动版