AbutionGraph万亿数量毫秒级出入度基数统计算法-1.5K内存存储十亿统计数据

图数据仓库AbutionGraph的万亿数据出入度去重基数实时统计算法，毫秒级响应，不到1K内存，可存储数亿个统计数据。

什么是基数？

基数是指集合中不同值的数量。例如，在{ 4,3,6,2,2,6,4,3,6,2,2,3}的集合中，基数为4，不同的基数值为4、3、6、2。

再如，与A相关的联系{A->B,A->C,A->D,A->B,A->C}中，A联系过哪些人？（B,C,D）

改善 现有数据库基数实现 的理由

基数统计具有广泛的应用范围，在数据库中非常重要，在图数据库中更为重要，常常会有DistinctCount的操作，随着图数据集在应用程序中的比例不断增长，基本查询越来越难以响应。

瓶颈场景如：PV/UV的计算,PageView统计信息,各种TopN统计、一个用户与哪些用户有过关联？计算一周内访问过网站的不重复用户的数量？每个人一天登录活跃多少次？蛋白质在相互作用网络中的聚集程度如何？哪个超链接可以关联出大量可能的中间网页？社交网络中的特定个人信息有多少个朋友的朋友？许多这样的查询相当于对图中相邻顶点进行交集和并集的推理。但是，在计算时间和分布式实现中的通信中，准确地回答此类查询通常是超线性的，对于大型图谱来说是站不住脚的。特别是时序范围的出度入度几乎是图数据库绕不开的一项指标计算，更进一步统计时序范围的基数出度入度（譬如同比、环比等场景）该如何在现有的图数据库产品中快速实现并响应？

传统粗暴的做法我们一般会想到用HashSet，HashSet的size方法就是去重记录数，由测试可知，指定使用10M的内存，仅仅够存65000左右的cookieid，之后就报错，内存不够了。读取的时间复杂度为O(n)，随着数据量的增长，越大的串读的时间和资源花销越多，显而易见是不切实际的。此外，大图的简单存储会变得很麻烦，尤其是当无标度图包括其度数在图的顶点大小上呈线性时，更不用说传达关于这些顶点的邻域集信息了。而对于大数量有限的内存条件，根据实体和关系的统计指标过滤条件来实现准实时的路径检索、关联关系探测在高基数的实体关系图谱几乎是不可能完成的。

基数统计即需要计算大数据集中不同元素的数量，并估计历史数据的交并集，因其计算量大而成为很多数据库的性能瓶颈之一。

实时 DistinctCount 解决方案

在一些前沿的OLAP引擎中我们看到了成熟的高基数统计实时解决方案，HyperLogLog（HLL）算法，HLL可以只用几KB内存就能估算具有十亿个不同元素集合的基数，如Pig、Spark、Presto、Clickhose、Druid、Kylin、AbutionDB等都采用了HLL的函数实现，现已成为实时数仓的必备功能，但在图数据库领域，AbutionGraph还是一款支持此项功能的图库，并且实现了几种先进的方法来解决这一问题，HyperLogLogPlus和HllSketch等。从大型数据集中提取基数时，AbutionGraph还可以预聚合这些数据集，并将它们存储在表中，以加速查询。

OLAP引擎不是通过每次回答此类查询时都从原始数据开始，而是可以通过维护每个维度值元组的预聚合数据立方体来减少查询时间和内存使用。一些原始值存储的OLAP数据库则是通过写入/查询时对每条数据实例化一个HLL对象，然后查询时触发聚合，或者查询时实时插入统计字段值到HLL对象，终的查询性能取决于我们可以多快地合并这些字段值/摘要，以在请求的维度上计算DistinctCount。

浅谈 HLL 在业务场景中的性能提升

非重复计数度量对于许多场景非常重要，假设在内存限制内适应您的数据量以保证线性缩放，那么使用蛮力（例如HashSet）技术来计算特定的有限大小值列表中的不同值（DV）的数量是相当简单的，在计算少量数据的情况下，就足够了。但是，在许多其他情况下，简单的线性方法无法像我们期望的那样按比例缩放，因此需要一种更强大的算法。

Facebook **： **假设您需要确定过去一周中使用一台机器访问Facebook的不同人数。使用传统SQL查询来执行此操作，将需要花费数天和数TB的内存。为了加快这些查询的速度，我们在Presto（分布式SQL查询引擎）中实现了HyperLogLog算法，现今已贡献给社区。使用HLL，我们可以在12小时内用不到1 MB的内存执行相同的计算，进一步节省计算量，提升效率并降低成本。我们已经看到了巨大的改进，一些查询在几分钟之内即可运行，其中包括那些用于分析数千个A/B测试的查询。根据当前的问题，我们可以将速度提高7倍至1,000倍。

**国内某大型网站： **统计一个大型网站的独立访问次数。如果我们使用Redis中的集合来统计，当它每天有数千万级别的访问时，将会是一个巨大的问题。因为这些访问量不能被清空，我们运营人员可能会随时查看这些信息，那么随着时间的推移，这些统计数据所占用的空间会越来越大，逐渐超出我们能承载大空间。例如，我们用IP来作为独立访问的判断依据，那么我们就要把每个独立 IP 进行存储，以IP4来计算，IP4多需要15个字节来存储信息，例如：110.110.110.110。当有一千万个独立IP时，所占用的空间就是15 bit * 10000000 约定于143MB，但这只是一个页面的统计信息，假如我们有 1 万个这样的页面，那我们就需要 1T 以上的空间来存储这些数据。而且随着IP6的普及，这个存储数字会越来越大，那我们就不能用集合的方式来存储了，这个时候我们需要开发新的数据类型来做这件事了，而这个新的数据类型就是我们今天要介绍的HyperLogLog。在Redis里面，每个HyperLogLog键只需要花费12 KB内存，就可以计算接近 2^64 个不同元素的基数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。

HyperLogLog 的优点是，在输入元素的数量或者体积非常大时，计算基数所需的空间总是固定的、并且是很小的。

AbutionGraph 中的高基数统计算法实现

众所周知，任何为具有n个元素的多重数据集基数提供相对错误保证的数据结构都需要O（n）空间，且HyperLogLog在低基数范围不那么准确（无优化的HLL标准误差为3%，经过改良后的HLL标准误差高为0.81%），相比于其它数仓中的HLL实现，在AbutionGraph则是采用了Google先进的基数统计算法HyperLogLog++和HyperLogLog两种实现方式来解决此类问题。

1）DistinctCountHllp（HyperLogLog++）

AbutionGraph中的数据类型DistinctCountHllp是基于HyperLogLog++的实现，HyperLogLogPlus（HLLP）是Google引入的一种流算法，它基于HLL的DV统计功能，对HyperLogLog进行了多项改进，对于较小的基数，错误率要低得多，提高了准确性和可伸缩性，且可使用恒定空间进行有效的基数和交点估计。HLLP不仅适用于非常大的数据集（认为是万亿），而且适用于较小的基数集。此外，HLLP还提供了轻松合并统计集的功能。尽管数据流初可能不需要HLLP提供的高基数统计，但是如果数据量开始超过内存限制，它仍然可以在较小的卷上准确有效地工作，而无需重写代码。此处为描述算法的论文-research.google.com/pubs/pub406…

AbutionGraph是一款混合的OLAP图数仓，它融合了预计算的建模方式（类似于Apache Kylin），对于其它实时数仓系统中的高基数统计（Presto、Clickhose、Druid、Kylin等），可以提高很大的查询时响应速度，底层的流式存储模式也更加的适合HLLP这种流算法，因为在大规模的实时流式数据写入时，就可以让AbutionGraph触发HLLP的并集操作了，而不是在查询时触发HLLP的并集操作，对于很大的时间窗口查询也仅需要对预计算好的少量HLLP求交并集，这省去了重复查询时的重复计算开销，尽管HLLP的求并集已经比以往方案快了几个数量级，但是每次查询都在内存执行一遍基数统计函数依旧是一个不可忽视的响应开销，使得AbutionGraph可以满足更实时的查询场景。

Ps：AbutionGraph虽然是图数据库，但是大多数真实业务场景的实体与关系存储、建模和解决方案都与实时数仓适用，既往的图库还未具有这些功能，所以经常拿实时数仓做比较。

2）DistinctCountHll（HyperLogLog）

AbutionGraph中的数据类型DistinctCountHll是基于apache.datasketches.HyperLogLogSketch（简称Hlls）的实现，是HyperLogLog算法密集的实现，内部具有自动稀疏的优化方式，即存储以稀疏的布局开始，以节省内存，如果输入数据结构超出了稀疏格式的预定内存限制，则AbutionGraph会自动切换到密集布局，且改善了错误率和增强了速度性能，而Hllp需要手动调节稀疏性-通过sp参数。

Hllp具有很好的线性扩展，对管理特大型基数效果突出（可达万亿级），使用Hlls的一个重要原因是，序列化速度要比Hllp快1-3个数量级，可为AbutionGraph的存储和预计算速度保持更高的时效性。此处为算法的功能描述-datasketches.apache.org/docs/HLL/HL…

AbutionGraph中的高基数建模

DistinctCountHll可包含列类型为INT/LONG/FLOAT/DOUBLE/STRING的值，AbutionGraph会将update中的每个值视为要添加到DistinctCountHll对象中的单个条目，然后通过调用方法cardinality()来获得近似值。

DistinctCountHll sketch1 = new DistinctCountHll();
sketch1.update("aa");
sketch1.update("aa");

DistinctCountHll sketch2 = new DistinctCountHll();
sketch2.update("cc");
sketch2.update("bb");

System.out.println(sketch1.cardinality()); // 结果为：1
System.out.println(sketch2.cardinality()); // 结果为：2
复制代码

假设我们使用一个具有聚合时间窗口的Schema实体（TimeWindowHll测试）维度（dim）来实时统计degree和hll：

那么，当有实时数据流（Flink、Kafka、Spark等）接入时，AbutionGraph将会对窗口范围的所有DistinctCountHll对象执行预聚合，待查询时，可毫秒即获取到指定时间窗口范围的基数统计结果。

总结

以上便是AbutionGraph的超高基数实时统计实现，尽管HyperLogLog算法仅使用几十kb就将此业务做到了毫秒级统计，但它的缺点也很明显，即只能得到一个估算值，具有一定误差，不支持基数查看/回溯，HLL只得到了HashSet的size，只得到了图属性的出度入度，但获取不到HashSet的去重集合，因为存储一个Set集合将是一个很庞大的内存和磁盘消耗，若一个大的用户画像图谱具有一千万用户，每天都有一个时序的去重字段，那么存储将会很快上升，这也是其它数仓难以实现此功能的原因之一。那对于需要快速去重且基数统计的场景就没有别的办法了吗？答案是否定的，除了DistinctCountHll和DistinctCountHllp，在AbutionGraph中，突破了以上所有高基数统计的难点，DistinctCountPlus数据类型同时实现千亿用户画像图谱毫秒级响应的精准高基数统计和基数去重集合存储\回溯\查看\聚合，这对于实现同比/环比等业务场景非常有用且使用起来简单便捷，将在下一篇文章中具体介绍其算法实现。

相关文章