在移动互联网业务场景中，数据量很大，我们需要保存这样的信息：一个key关联一个数据集，同时对数据进行统计。统计APP的日活跃用户数和月活跃用户数；计算每天有多少不同的帐户访问一个页面（独立访客，UV））；统计用户每天搜索的不同条目的数量；计算注册IP的数量。通常，我们面对的用户数量和访问量都是巨大的，比如百万级、千万级的用户量，或者是千万级甚至亿级的访问信息量。今天《码哥》使用不同的数据类型实现了统计每天有多少不同账号访问一个页面的功能，并逐步介绍了HyperLogLog的原理，并在Java中集成了Redission。告诉你一个技巧，Redis官网现在可以在线运行Redis命令了：https://redis.io/。如图：Redis在线运行，使用Set实现一天多次访问一个网站的用户只能统计一次，所以很容易想到通过Redis的Set集合来实现。比如当微信ID是“小菜鸡”访问《Redis为什么这么快》一文时，我们将这些信息保存在Set中。SADDRedis为什么这么快：uv小菜鸡谢八哥小菜鸡(整数)1“小菜鸡”多次访问“Redis为什么这么快”页面，Set的去重功能保证不会重复记录同一个“微信”ID”。使用SCARD命令统计《为什么Redis这么快》的页面UVs。命令返回一个集合中元素的个数（即用户ID）。为什么SCARDRedis这么快：uv(integer)2使用Hash实现老湿代码，也可以使用Hash类型来实现，使用用户ID作为Hash集合的key，访问页面时执行HSET命令将值设置为1。即使“小菜鸡”多次访问页面，重复执行命令，只会将等于“小菜鸡”的key的值设置为1。最后使用HLEN命令统计Hash集合中的元素个数为UV.如下：HSETRedis为什么这么快小菜鸡1//统计UVHLENRedis为什么这么快使用Bitmap实现Bitmap的底层数据结构使用String类型的SDS数据结构来存储位数组，Redis存储每个8字节字节数组的每一位代表一个元素的二进制状态（0或1）。Bitmap提供了GETBIT和SETBIT操作，通过一个偏移值offset来读写位数组偏移位置的位。需要注意的是，偏移量是从0开始的。Bitmap可以看作是一个位单元数组，数组的每个单元只能存储0或1，数组的下标在Bitmap中称为偏移量。为了直观显示，我们可以理解为buf数组的每个字节用一行来表示，每一行有8位，8个格子代表这个字节中的8位，如下图所示：Bitmap8bitsFormaByte,所以Bitmap会大大节省存储空间。这就是Bitmap的优势。如何使用Bitmap统计页面的唯一用户访问量？Bitmap提供SETBIT和BITCOUNT操作。前者使用一个偏移值offset，将位写入位数组的偏移位置。需要注意的是offset是从0开始的，后者统计给定的指定位数组中value=1的位数。注意我们需要把“微信ID”转换成数字，因为offset是下标。假设我们将“小菜集”转换为代码6，第一步是执行如下命令，指明“小菜集”的代码为6，访问《使用Redis数据类型实现亿级数据统计》一文。SETBIT巧妙利用Redis数据类型实现亿级数据统计61第二步统计页面访问次数，使用BITCOUNT命令。该命令用于计算给定位数组中值为1的位数。BITCOUNT巧妙利用Redis数据类型实现亿级数据统计HyperLogLogKingSet不错，但是如果文章很火，达到几千万，一个Set就省下几千万的用户ID，太多消耗的内存页面会太大。Hash数据类型也是如此。至于Bitmap，更适合“二进制状态统计”的使用场景，统计精度高。虽然内存占用比HashMap少，但是对于大量的数据来说还是会占用大量的内存。该怎么办？这些就是“基数统计”的典型应用场景。基数统计：计算集合中唯一元素的数量。HyperLogLog的优点是它所需要的内存不会因为集合的大小而改变。无论集合包含多少个元素，HyperLogLog计算所需要的内存总是固定的，而且很小。每个HyperLogLog最多只需要花费12KB的内存，在标准误差0.81%的前提下，可以计算出2的64次方元素的基数。Redis实战HyperLogLog使用起来太简单了。PFADD、PFCOUNT、PFMERGE这三个命令独领风骚。PFADD将访问页面的每个用户ID添加到HyperLogLog。PFADDRedis主从同步原理：uvuserID1userID2useID3PFCOUNT使用PFCOUNT获取《Redis主从同步原理》一文的UV值。PFCOUNTRedis主从同步原理：uvPFMERGE使用场景HyperLogLog除了上面的PFADD和PFCOIUNT，还提供了PFMERGE语法PFMERGEdestkeysourcekey[sourcekey...]比如我们网站有两个内容相似的页面，和操作说这是需要合并两个页面的数据。页面的UV访问也需要合并，这时PFMERGE就可以派上用场了，即同一个用户只访问这两个页面一次。如下图：Redis和MySQL的两个HyperLogLog集合分别保存了两个页面的用户访问数据。PFADDRedisdatauser1user2user3PFADDMySQLdatauser1user2user4PFMERGEdatabaseRedisdataMySQLdataPFCOUNTdatabase//returnvalue=4将多个HyperLogLog合并（merge）成一个HyperLogLog，合并后的Hy??perLogLog的基数接近所有输入HyperLogLog的可见集合（观察集）的并集。user1和user2都访问过Redis和MySQL，只统计一次访问。Redission的实际详细源码《码哥》已经上传到GitHub：https://github.com/MageByte-Zero/springboot-parent-pom.git。pom依赖org.redissonredisson-spring-boot-starter3.16.7AdddatatoLog//添加单个元素publicvoidadd(StringlogName,Titem){RHyperLogLoghyperLogLog=redissonClient.getHyperLogLog(logName);hyperLogLog.add(item);}//向HyperLogLog添加采集数据publicvoidaddAll(StringlogName,Listitems){RHyperLogLoghyperLogLog=redissonClient.getHyperLogLog(logName);hyperLogLog.addAll(items);}Merge/***将otherLogNames的日志合并到logName中**@paramlogName当前日志*@paramotherLogNames其他需要合并到当前日志中的日志*@param*/publicvoidmerge(StringlogName,String...otherLogNames){RHyperLogLoghyperLogLog=redissonClient.getHyperLogLog(logName);hyperLogLog.mergeWith(otherLogNames);}统计基础publiclongcount(StringlogName){RHyperLogLoghyperLogLog=redissonClient.getHyperLogLog(logName);返回hyperLogLog.count();}单元测试@Slf4j@RunWith(SpringRunner.class)@SpringBootTest(classes=RedissionApplication.class)publicclassHyperLogLogTest{@AutowiredprivateHyperLogLogServicehyperLogLogService;@TestpublicvoidtestAdd(){StringlogName="Byte:为什么Redis这么快：uv";Stringitem="小菜鸡";hyperLogLogService.add(logName,item);log.info("添加元素[{}]到log[{}]",item,logName);}@TestpublicvoidtestCount(){StringlogName="码哥字节：为什么Redis这么快：uv";longcount=hyperLogLogService.count(logName);log.info("logName={}count={}.",logName,count);}@TestpublicvoidtestMerge(){ArrayListitems=newArrayList<>();items.add("小菜鸡");items.add("谢八哥");items.add("陈小白");StringotherLogName="字节跳动：Redis多线程模型原理与实践：uv";hyperLogLogService.addAll(otherLogName,items);log.info("Add{}要记录的元素[{}]。",items.size(),otherLogName);StringlogName="Code:为什么Redis这么快：uv";hyperLogLogService.merge(logName,otherLogName);log.info("Merge{}into{}.",otherLogName,logName);longcount=hyperLogLogService.count(logName);log.info("Mergedcount={}.",count);}}基本原理HyperLogLog是一种概率数据结构，它使用概率算法来计算集合的近似基数。其算法的起源这就是伯努利过程。伯努利过程是一个抛硬币实验过程。当抛掷一枚普通硬币时，它可能会正面朝上或反面朝上，两者的概率均为1/2。伯努利过程是抛硬币直到正面朝上，记录抛硬币的次数k。例如，抛一次硬币，会出现正面朝上，此时k为1；如果第一次抛硬币是反面，然后继续抛，直到第三次出现正面，此时k为3。对于n个伯努利过程，我们得到n个头k1，k2...kn，其中最大值为k_max。根据数学推导，我们可以得出结论：2^{k_max}作为n的估计值。也就是说，你可以根据抛出的最大次数来估算执行了多少次伯努利过程。因此，HyperLogLog的基本思想是利用集合中数字位串的第1个出现位置的最大值来估计整体的基数，但这种估计方法存在较大的误差。为了改善错误情况，HyperLogLog引入了bucketaverage计算m个桶的调和平均值的概念。Redis中的HyperLogLog一共有2^14个桶，也就是16384个桶。每个桶都是一个6位的数组，如下图所示。图片来源：程序员李小兵HyperLogLog的原理太复杂了，想了解请前往：https://www.zhihu.com/question/53416615https://en.wikipedia.org/wiki/HyperLogLogUser如何实现统计每日和每月的活动——RedisHyperLogLog详解Redis优化了HyperLogLog的存储。当计数比较小时，存储空间采用系数矩阵，占用空间小。只有当count很大，稀疏矩阵占用的空间超过阈值时，才会转化为稠密矩阵，占用12KB的空间。为什么只需要12KB？HyperLogLog实现使用16384个桶，即2^14。每个bucket的maxbits需要6位来存储，最大可以表示maxbits=63，所以总的内存使用量为2^14*6/8=12k字节。综上所述，Hash、Bitmap、HyperLogLog用于实现：Hash：算法简单，统计精度高，数据量小，海量数据会占用大量内存；Bitmap：位图算法，适用于“二进制统计场景”，具体可以参考我的文章。大量不同页面的数据统计仍然会占用大量内存。Set：使用去重特性实现。一个Set可以存储几千万个用户ID，页面太多消耗的内存太大。在Redis中，每个HyperLogLogkey只需要12KB的内存就可以计算出将近2^64个不同元素的基数。因为HyperLogLog只是根据输入元素计算基数，并没有存储输入元素本身，所以HyperLogLog不能像集合一样返回输入的单个元素。HyperLogLog是一种算法，并不是Redis独有的。目的是做基数统计，所以不是集合，不会保存元数据，只记录数量不记录值。它占用的空间非常小，并且支持非常大量的数据输入。核心是基数估计算法，主要表现在内存的使用和计算时数据合并的处理上。最终值存在一定误差。Redis中每个Hyperloglogkey占用12K内存用于标记基数（官方文档）。pfadd命令并不是一次性分配12k内存，而是随着基数的增加逐渐增加内存分配；而pfmerge操作会合并sourcekey并存储在一个12k的key中，根据hyperloglog合并操作的原理（两个Hyperloglog合并时，需要分别比较每个bucket的值）可以很容易理解。误差说明：基本估计的结果是标准误差为0.81%的近似值。这是一个可以接受的范围。Redis优化了HyperLogLog的存储。当计数比较小时，存储空间用稀疏矩阵存储，占用空间小。只有当计数逐渐增加，稀疏矩阵占用的空间逐渐超过阈值时才会使用一次。只有当属性转化为稠密矩阵时才会占用12k空间。
