Redis概率数据结构之计数器HyperLogLog
first 流行的开源数据库Redis提供了一个多样化和可扩展的数据类型工具箱，包括工程师工具带中的一些最前沿的工具：概率数据结构。
如果某些商品在接受客户订单之前就发现已经缺货，货运部门应该提前立即知道; 营销系统可能需要一个实时仪表板显示各个用户细分的总计数；而工程部门可能需要一种快速的方法来删除来自不友好客户端的请求。这些只是概率数据结构提高效率的几种情况。
在本文中，我们将介绍三种概率数据结构，它们解决了大数据集的两个常见用例：1）跟踪集合计数; 2）测试数据项是否具备集合成员资格。
概率数据结构快速入门
下面探讨概率数据结构的一些反直觉属性：
1. 这些数据结构的行为很大程度上取决于散列函数，有时也是随机源，散列在分布存储不同的数据时具有更大的灵活性，通常可以提高效率。不幸的是，这也使其行为更难以预测。
2. 概率数据结构不存储整个数据条目，因此你无法使用它们来检索先前添加的数据项，这也意味着（与非概率数据结构的期望相反）概率数据结构可以在一定空间量中存储更多的数据量，这是因为它们仅存储解决其特定问题所需的最少量数据（例如，计算或设置成员资格）。
3. 最后，值得注意的是，概率数据结构只为你提供了模糊的数据视图。因此，比如对于单个单元计数将不精确，并且设置成员资格测试可能会给出错误的答案。虽然不是最优的，但这不是问题，因为这些错误率具有特定的结构，可以量化，并且还可以通过调整一些参数来调整。当你更关心速度或低内存占用而不是精确定位时，概率数据结构非常适合；当你确实需要完整的正确性时，你始终可以与传统数据结构配对，并将概率数据结构用作优化层。
我们将深入研究三种强大数据结构的实际示例：HyperLogLog，Bloom 过滤器和Cuckoo过滤器。
用于实现计数器的HyperLogLog
当你有大量用户与巨大的数据项进行交互时，并且你想要保存这些交互的数量时，HyperLogLog是一个很好的数据结构，此外，此数据类型可以保持各种集合的计数，并快速计算其并集或交集的结果数值。它内置于Redis，因此你可以立即使用它。每个计数器需要12千字节的内存，标准错误为0.81％，可以计算几乎无限量的独立数据项（2 ^ 64）。
案例：
1. YouTube，Reddit，亚马逊的页面浏览量
2. 用户组的高效联合/交叉
基本用法
创建新计数器就像向redis添加第一个数据项一样简单。如果没有指定key，Redis将为你创建key。命令结构如下：
PFADD <key> <item>
计算唯一视图
假设希望统计浏览某个视频的某个用户的唯一浏览量，要将user01的视图添加到视频42，请使用：
PFADD video42 user01
这将创建一个以包含事件user01，以视频命名的key, 要获取它的唯一视图计数，请使用：
PFCOUNT video42
这将返回之前添加的总数。由于我们按userID标识每个事件，因此同一用户的多次浏览仅当做一次。
[b]每天不同的浏览量[/b]
如果你对唯一性的定义更加细致，则只需将所有相关信息打包到标识每个视图事件的字符串中。假设希望将不同日期的浏览量也视为不同的浏览计数，即使它们来自同一用户。在这种情况下，你的命令结构可能是：
PFADD video42 user01:2018-08-22
这样，user01：2018-08-22和user01：2018-08-23将计为两个单独的事件，另一种方法可能是为每天创建一个不同的计数器：
PFADD video42:2018-08-22 user01
请注意日期如何从数据项值的一部分移动到成为key键的一部分，使用这种方法，你可以轻松绘制直方图，但要注意你是为每天创建一个新计数器，要获得跨越多天的总视图计数，你可以通过在每个计数器上调用PFCOUNT来对结果求和，如果你仍想知道仅限唯一身份用户的总观看次数，你可以使用：
PFCOUNT video42：2018-08-22 video42：2018-08-23
此调用返回所有给定计数器的并集的基数。由于我们仅通过用户ID存储每个视图事件，因此该计数将对应于我们对唯一性的第一个定义。
[b]合并计数器[/b]
你还可以将多个计数器合并为一个，这对于跟踪多个粒度级别和玩转旧计数非常有用。例如：
PFMERGE video42：2018-08 video42：2018-08-22 video42：2018-08-23 ......
此调用将在video42：2018-08中存储所有指定集合的并集，通过压缩旧指标，你可以保留历史数据，同时仍将大部分内存分配给最近的事件，我们所有的示例都是关于按日期切片数据，但相同的概念可以应用于任何其他维度，例如类别，视频长度，年龄范围等。