位图的使用
当接到这样的需求时，第一时间我想到的就是使用Redis来应对这样的需求，用户一年的签到记录， 签了是 1，没签是 0，要记录 365 天。如果使用普通的 key/value，每个用户要记录 365 个，当用户上亿的时候，需要的存储空间是惊人的。而这时Redis的位图数据结构就派上用场了，这样每天的签到记录只占据一个位， 365 天就是 365 个位，一个字节是8位，也就是一个用户签到一年，差不多46 个字节就可以完全容纳下，这就大大节约了存储空间。
位图不是特殊的数据结构，它的内容其实就是普通的字符串，也就是 byte 数组。我们可以使用普通的 get/set 直接获取和设置整个位图的内容，也可以使用位图操作 getbit/setbit 等将 byte 数组看成「位数组」来处理。
操作：设置（setbit）和获取（getbit）：
图片.png
操作：统计（bitcount）和查找（bitpos）：
图片.png
以上就是Redis提供给我们位图的数据结构，当然还是其他操作，这里就不再赘述，下面来讲一下另外一个需求，那就是统计网站的UV数据，当接到这样一个需求时，相信大部分程序员都会漏出自信的微笑，我用一个Redis的计数器就可以实现了，其实不然，如果统计 PV 那非常好办，给每个网页一个独立的 Redis 计数器就可以了，这个计数器 的 key 后缀加上当天的日期。这样来一个请求，incrby 一次，最终就可以统计出所有的 PV 数据。但是 UV 不一样，它要去重，同一个用户一天之内的多次访问请求只能计数一次。这就 要求每一个网页请求都需要带上用户的 ID，无论是登陆用户还是未登陆用户都需要一个唯一 ID 来标识。可能你会想到另外一个简单的方案，那就是为每一个页面一个独立的 set 集合来存储所有当天访问过此页面的用户 ID。当一个请求过来时，我们使用 sadd 将用户 ID 塞进去就可 以了。通过 scard 可以取出这个集合的大小，这个数字就是这个页面的 UV 数据。不错，这也是一个实现方案，但这个方案也有缺点，那就是数据量比较大时，如果你的页面访问量非常大，比如一个爆款页面几千万的 UV，你需要一个很大 的 set 集合来统计，这就非常浪费空间。
铺垫了那么久，其实就是为了引出这个解决方案的主角，那就是HyperLogLog，Redis 提供了 HyperLogLog 数据结构就是用来解决 这种统计问题的。HyperLogLog 提供不精确的去重计数方案，虽然不精确但是也不是非常不精确，标准误差是不到1%，这样的精确度已经可以满足上面的 UV 统计需求了。
操作：增加（pfadd）和统计（pfcount）：
图片.png
大家看了会说，这部挺准确的，添加了3个，统计出来的就是3个，量大了就不行了
HyperLogLog 主要的应用场景就是进行基数统计。这个问题的应用场景其实是十分广泛的。例如：对于 Google 主页面而言，同一个账户可能会访问 Google 主页面多次。于是，在诸多的访问流水中，如何计算出 Google 主页面每天被多少个不同的账户访问过就是一个重要的问题。那么对于 Google 这种访问量巨大的网页而言，其实统计出有十亿 的访问量或者十亿零十万的访问量其实是没有太多的区别的，因此，在这种业务场景下，为了节省成本，其实可以只计算出一个大概的值，而没有必要计算出精准的值。
对于上面的场景，可以使用HashMap、BitMap和HyperLogLog 来解决。对于这三种解决方案，这边做下对比：
-
HashMap：算法简单，统计精度高，对于少量数据建议使用，但是对于大量的数据会占用很大内存空间； -
BitMap：位图算法，统计精度高，虽然内存占用要比HashMap少，但是对于大量数据还是会占用较大内存； -
HyperLogLog：存在一定误差，占用内存少，稳定占用 12k 左右内存，可以统计 2^64 个元素，对于上面举例的应用场景，建议使用。
网友评论