图数据库AbutionGraph的毫秒级大数据去重方案

AbutionGraph是款OLAP实时图数据仓库，可以高效率的满足更多难点问题。

基数统计（不重复计数）是一个经典问题，AbutionGraph将其做到了的性能：查询响应速度提升几个量级，计算数据量级提升几个数量级，占用存储空间比存储原始集合少几个量级，总的来说，在几百亿的知识图谱数据上，使用AbutionGraph的高基数实时预计算存储技术，使得基数统计（可类比为degree基数）分析时效性提高到了毫秒级。譬如获知“张三”去年和今年都联系过的人有哪些，我们不用像以前把“张三”两年的数据都查出来计算一遍就可以立即得到结果，即使查询涉及整个图谱的所有“人”实体，甚至数据量扩增到十几亿个节点，我们依旧可以花费远远少于原本计算成本且秒级高速响应的查询过滤性能。

大数据精准去重的应用场景

基数统计是大数据分析的常用分析功能，它的作用是删除重复的值，因此得名“Distinct Count”，海量数据的判重和基数统计是大数据业务中绕不开的两个基础问题。

场景如：

1）在精准营销/用户行为分析领域，在投放广告的时候，需要根据地域、性别、年龄、兴趣、激活时间等条件进行圈选相似的人群包，其本质就是集合的快速交并补计算。每天要处理数以万计的人群包，根据每个目的不一样的营销活动，支持各种条件的互相组合，用户属性的交并集等，从几亿甚至数十亿的用户中筛选出你所需要的会员，达到社群划分用于辅助判断投放情况，进而确定投放预算。在生产人群包的时候做到快速准确，在业务可接受的时间（一般要求计算的时间不超过 5 秒）处理出来，且保证系统的扩展性，那就能抢占先机赢得效益大化。

2）在知识分享领域，对点赞用户去重，假设用户分享了一条视频，得到了很多粉丝的点赞，就会出现某些粉丝重复多次点赞的情况，我们不断的累加点赞值显然是不公平的，那么就需要后台实时的对这条视频的点赞情况去重，限制每个用户只能对每个作品点赞一次，并且可能还可以取消点赞，这也是基数统计的常见场景之一。

3）在金融风控领域，构建用户的资金交易行为画像，若只是根据转账信息生成“数据图谱”，可能只是将原本关系型数据库中的数据挪到了图数据库上，高度抽象的实体关系使得存储占用上升了，得到的只是更易于解释的数据检索方案，对于业务分析场景依然没有效率上的改变，可能会更加复杂。假设我们要对比库中一亿个用户昨天与今天交易的重复人大于5个的人群、过去一个月资金交易主要集中在沿海省份的人群、过去三年经常转账且相同姓氏占比较高的人群，这是风控模型常用的判别方法，您的做法应该是从传统图库的实体和关系中查找与每个用户相关的所有历史数据，再对一亿用户的十几亿交易数据进行Set的or,and等操作，这可能会耗费能装下几十亿数据的内存计算空间，且也很难在10秒内完成这么规模庞大的运算量。

在线统计分析的使用场景还有很多，如：有id分别为1, 2, 3, 4, 5, 6, 7, 8的用户, 其中1用户在今日登录了两次、 3用户在今日登录了5次, 统计今日登录用户（1,3），还有一些搜索词TopN分析，广告、投放收入数据的分析、异常用户的及时判别等等。在既有的资源成本下，为了满足高实效性的风控/广告等场景，需要探寻一种新的技术解决方案，特别是金融场景需要满足高效的同时，能够保证的基数统计方法，以尽量避免漏网之鱼。而在定向流量或广告投放中，费用是通过频道总数或来自观看者的点击次数的总和来计算的，买方担心支付太多，而供应商担心收到的钱太少，双方都无法容忍价值观上的错误，那就需要精准的大数据方案来解决此类问题。 

使用大数据进行非重复计数的挑战

由于“去重”操作涉及多个值的比较，大多数情况下数据还是分布式存储的，因此计算比上面的举例稍微复杂一些，我们不能把所有数据都拉取到一台服务器上再计算，一台计算机也几乎不能对少量数据执行这些计算，并且随着数据量的增加，基数集合的增加，时间跨度的增加，所需的时间和资源将大大增加，并且使用单个节点来处理数据变得很困难。

在这一点上，我们需要依靠像MapReduce或Spark这样的分布式框架进行并行处理来划分和理解大数据。假设我们有1000万个用户的1亿记录（每个用户10条），且用户id已为int值，那么一个简单的用户Distinct Count计算是100,000,000 * 4字节=3,200 Mb的数据要被shuffled。假设计算集群使用千兆网络，除了磁盘读取，排序，序列化和反序列化之外还有3秒的传输延迟，那么终的总时间将至少为10秒。

真实场景中要更复杂，需统计的指标更多、基数值大多为长字符串、计算资源可能正在被其它程序占用等。总体而言，大数据的去重操作通常是一个资源密集型计算过程，而完善此过程以在一秒钟内完成延迟非常困难。如果这样的查询变得越来越流行，那么我们肯定需要优化数据结构及其计算。

秒内大数据去重的方案

许多研究人员已经意识到这里的优化空间，并且已经开发了各种公式和数据结构作为新的解决方案。受欢迎的两个是HyperLogLog和Bitmap，两种算法都使用极其精细的结构来存储一组去重值，并且都可方便的扩展后续计算功能，合并、相减、昨天与今天的不同基数等。我们在上一篇文章中介绍了AbutionGraph基于HyperLogLog的两种基数统计实现方式，虽然它们节省空间（几十KB）并且效率高（毫秒级），但也付出了一定的代价，即：

² 只能插入元素，不能删除元素；

² 只能得到统计值，如计算沿海地市基数只得到数量，无法获取基数集合，显然是不能够很好的满足该场景；

² 不保证准确，由于HLL使用哈希函数和概率估计，因此HLL计算的结果注定是不准确的，AbutionDB中的误差为0.01-0.3%。

这些缺点可以说是所有概率性数据结构做出的trade-off，毕竟鱼与熊掌不可兼得，如果业务能接受些许误差，那么肯定优先选择我们提供的HLL方案。在开发AButionDB的时候就考虑到，仅仅进行良好的估算是不够的。如果无法支持准确的非重复计数，那么用户肯定会在进行重大计算时失去机会和在洞察决策中措施良机。基于此，AbutionDB开始尝试另一种方案，Bitmap，其实现思路是利用布隆过滤器和HyperLogLog的基础，Bitmap可能比HLL占用更多空间，也只能用于数字类型(int或者long)，但可以保证准确性。为了尽量优化这些缺点，出现了一些快速准确的完成Count Distinct查询的前沿方法，全球领先的例子则是AbutionDB中的查询加速解决方案。

Abution中的多维数据集毫秒级去重实现

如果您曾接触过Apache Kylin，那么您就会知道如何根据用户指定的维度和指标来预计算数据。相似的，AbutionGraph也采用预计算技术，且是一款使用预计算技术构建知识图谱的图数据库。除了实时的聚合统计数据，AbutionGraph还支持友好的历史明细数据管理，可以从任意实体或者关系出发，根据聚合指标查询明细数据、探寻数据关联性，反之亦然。将诸如每日销售记录,销售总额等聚合值存储在OLAP多维数据集中，查看某项TopN的销售总额时，可以直接二次查询到与其相关的明细销售账单，毫秒级的获取到关联数据，而不用扫描全表和匹配字段。

OLAP多维数据集存储示例

对于具有Distinct Count属性的维度（不管是实体维还是关系维），像传统数据库那样将每个属性值存储为每一行数据的某个固定字段上显然过于冗余，因为用户的查询可能需要遍历多条与各自实体相关的数据，然后依次合并，并且不能分解为简单的int数。在DistinctCountHll的实现中，AbutionGraph则是将HLL对象序列化，然后将其存储在具有匹配单元格的多维数据集的维值中。在执行与历史数据更新时，即与具有相同schema属性的历史数据合并，并更新到“立方体/数据格”中。这样一来，不但减少了存储空间，还能加速结果查询。在查询期间，AbutionGraph将进行反序列化，并将查询过滤下推到数据所在的各台服务器，之后将其移至GQL执行程序以执行post阶段指定的合并计算，如增大的时间窗口范围数据聚合（通过Abution的Aggregator Function）,这时的聚合client端拿到的数据已经远远少于相关的原始数据了，完全可以在单节点快速合并。返回终值后，它将返回HLL对象并提供基数集合和基数值。

使用相同的理论，我们将HLL转换为Bitmap的实现，使用小的单位bit来进行或者1的设置，以达到只存储基数的目的，那么从理论上讲，可以准确地存储或查询不同的计数。但是使用Bitmap，我们将会面临三个新的挑战：

1.Bitmap占用太多空间

不管业务中实际的元素基数有多少，它占用的内存空间都恒定不变。举个例子，如果一个10亿的集合内存占用约为128MB，若只存有一个元素，那么该Bitmap只有低位是1，其他位全为，但仍然会占用128MB内存。数据越稀疏，则空间浪费越严重。

解决方案：采用了一种新型的,可压缩的,也是目前性能好的改进版实现，RoaringBitmap，它的提出是在2016年，它将32位无符号整数按照高16位分桶，即多可能有216=65536个桶（container）。存储数据时，按照数据的高16位找到container（找不到就会新建一个），再将低16位放入container中。为了更高效地存储和查询数据，不同情况下会采用不同类型的container。此外，RMB还支持Kryo序列化方式，以便我们还可以将图数据方便的转化到Spark中。

2.Bitmap只接受int/long类型作为输入

如果需要删除重复数据的值不是这两种类型中的任何一种，则用户必须进行1：1映射，将非整型的值映射成的数值，这样做会大大增加复杂度，但是真实场景中的基数值大都是string类型，所以不得不作此优化。

解决方案：默认对基数属性构建数据字典（dictionary），通过字典将string等值1:1映射成int值，这样在后续运算和存储时，使用int值代替string值，可以大大减少空间占用。

3. Bitmap去重后的基数集不再是原始值

如2的做法，我们已经将原始的string值映射成了int进行存储，此后的计算都是基于int值，Bitmap无法回溯int到string的映射。因为，同时又保存一份原始值，那么我们的这些优化工作都是多余了。当然，我们也可以存储一份反向的映射字典来作为回溯使用，这样会加大一倍的字典构建时间和存储成本，进而降低数据的写入速率。

解决方案：构建分布式内存字典，利用内存的快速计算来得到原始key，庆幸的是，AbutionGraph具有数据中台AbutionGRS，不仅是一个接口平台，更是一个分布式的缓存系统，无需任何安装调整，即可充分的利用上每台服务器的剩余内存作为一个分布式key-value数据库使用，类似于Redis，且包含类似于Spark/Flink的分布式计算操作可用，只需几MB就可以部署一个新节点，也可以充当一个边缘计算系统来使用。有了AbutionGRS，我们就可以实时的与磁盘字典同步，使用缓存来加速全局字典的构建和检索查询，而不必每次都从磁盘索引读取字典。也不用担心每台服务器局部构建字典时，字典越来越大而导致单节点OOM。当然，对于内存很吃紧的场景，您还可以随时禁用此功能，AbutionGraph将从磁盘字典中完成这一切。 

AbutionGraph全局字典的实现

当我们将所有的困难都想出了解决方案，接下来就是实施它，难点就只剩下全局字典的构建了。需要满足的功能点：

1. 支持上卷（分区聚合）操作，即每台服务器的字典映射都必须一样，否则合并时将出错。譬如，将张三1月份与2月份使用过的银行卡号交集，若两份数据的卡号映射id不一样则会出错，也就无法实现扩大时间窗口聚合的功能。

我们参考了Apache Kylin的相关实现，因为全球只有它做到了1秒内的去重，相比于HDFS+Hive/Spark的字典存储方案，我们省去了Hive，因为它不在AbutionGraph的生态中，没必要仅为这一个功能加入一套全新的大数据框架，而对于Spark，我们有图数据中台AbutionGRS可以实现同等效果。

再有就是技术的核心，全局id（bitindex）的生成，AppendTrieDictionary的树形结构设计可以很方便得到字符串的值，但是跟普通字典相比，它放弃了保序性，无法支持双向映射（从int再解码回原始string值）。再有，每次获取或者映射bitindex都需要在本地内存中重新构建一遍，对于较大的基数字典开销也较大。

基于这些问题，我们也没有采用这种方案，而是重新设计了一种更轻量且支持双向映射的bitindex构建方法，使用一个hash table来表示一个map。该表将填充到指定的负载系数，然后大小加倍以容纳新条目。如果清空表的空间小于负载因子的四分之一，则其大小减半；但是，该表的大小永远不会小于创建时的大小：这种方法使创建具有大容量的映射成为可能，在这种映射中，插入和删除操作不会立即导致重新哈希。此外，还可以通过一系列的trimming methods来控制表的大小。当addItem时，如果此Item已经存在，则以-1退出，否则返回映射值。另一个好处是，构建的bitindex是有序自增的，RoaringBitmap中对有序的bitindex压缩效果要好得多。

对于字典的持久化，AbutionGraph会向本地磁盘（局部字典）或者HDFS（全局字典）生成不同的字典版本，按照生成时间排序，字典版本会按照数据过期时间自动删除旧的版本，同时只保留新的三个版本，这样一来，我们可以控制字典占用过多不必要的空间。对于分布式缓存Dictionary，以分布式方式创建全局词典，从而减少工作时间。除了自带的本地集群AbutionGRS，您也可以将字典部署在任何的集群上，并且只需提供集群密钥就可以无缝的将字典保存到另一个AbutionGraph集群上，同时可以复用其它集群的Dictionary。对于性能不一，或者有正在计算任务的节点，支持指定在集群中的任意节点调取和构建bitindex，只需提供节点ip即可实现。而对于从int再解码回原始string值，您也可以只提供节点ip就可以从任意节点的缓存中完成解码，另一种方式是从HDFS中使用流缓冲来进行解码。

另外一点优化：当数据量特别大的时候，在生成bitindex的时候可能会有性能延迟，为了快速度构建Dictionary，我们可以预先构建BitIndex，使用并执行conversionIndex()函数即可把你的数据库当中的大部分用户id生成1：1映射，也可以预先用本地程序或者flink批处理任务，高效生成映射，当写入数据时无需构建新的bitindex，就能直接获取到映射id，对写入数据时将会有较低的初始性能开销。

简而言之，AbutionGraph是一款且能够在超大数据集上做到亚秒级低延迟的GraphOLAP分析引擎。我们使用了尽可能简便且优化的方式实现了大数据场景下的去重基数计算，经反复测试验证，效果可以达到亚秒至秒级低延迟，也使其成为能做到秒级去重的图数据库引擎，和为数不多的秒级去重OLAP引擎。

来源 https://www.modb.pro/db/47966