一种基于布隆过滤器的大表计算优化方法

在大数据行业内，尤其是数仓建设中，一直有一个绕不开的难题，就是大表的分析计算（这里的大表指亿级以上）。特别是大表之间的 Join 分析，对任何公司数据部门都是一个挑战！,主要有以下挑战：,优点：简单粗暴，对业务和数据开发人员友好，不用调整。,缺点：费钱，看你公司是否有钱。,优点：可以在不大幅增加计算集群成本的情况下，完成日常计算任务。,缺点：对数据和业务都有一定要求，数据一般要求是日志类数据。或者具有一定的生命周期数据（历史数据可归档）。,Spark 经典算法 SortMergeJoin（以大表间的 Join 分析为例）。,该算法也可以简化流程为： Map 一> Shuffle 一> Sort 一> Merge 一> Reduce,,该算法的性能瓶颈主要在 Sort Merge Shuffle 阶段(红色流程部分)，数据量越大，资源要求越高，性能越低。,大数据计算优化思路，核心无非就三条：增加计算资源；减少被计算数据量；优化计算算法。其中前两条是我们普通人最常用的方法。,两个大表的 Join ，是不是真的每天都有大量的数据有变更呢？如果是的话，那我们的业务就应该思考一下是否合理了。,其实在我们的日常实践场景中，大部分是两个表里面的数据每天只有少量（十万百万至千万级）数据随机变化，大部分数据是不变的。,说到这里，很多人的第一想法是，我们增加分区，按数据是否有变化进行区分，计算有变化的（今日有更新的业务数据），合并未变化的（昨日计算完成的历史数据），不就可以解决问题了。其实这个想法存在以下问题：,图片,问题读到这里，如果我们分别把表 A、表 B 的有变化记录的关联主键取出来合并在一起，形成一个数组变量。计算的时候用这个变量分别从表 A 和表 B 中过滤出有变化的数据进行计算，并从未变化的表（昨日计算完成的历史数据）中过滤出不存在的（即未变化历史结果数据）。这样两份数据简单合并到一起，不就是表 A 和表 B 全量 Join 计算的结果了吗！,也许这里有人会有疑惑，不是说布隆过滤器是命中并不代表一定存在，不命中才代表一定不存在！其实这个命中不代表一定存在，是一个极少量概率问题，即极少量没有更新的数据也会命中布隆过滤器，从而参与了接下来的数据计算，实际上只要所有变化的数据能命中即可。这个不影响它已经帮我买过滤了绝大部分不需要计算的数据。,大家可以根据需要参考、修改和优化，有更好的实现方式欢迎大家分享交流。,程序流程图,图片,图片,从理论分析和实测效果来看，使用布隆过滤器的解决方案可以大幅提升任务的性能，并减少集群资源的使用。,该方案不仅适用大表间 Join 分析计算，也适用大表相关的其它分析计算需求，核心思想就是计算有必要的数据，排除没必要数据，减小无效的计算损耗。