近期，数据库畛域的顶级学术会议 ICDE 2023 在迪斯尼主题公园的故土 – 美国的安纳海姆（Anaheim）举办。由 OpenMLDB 开源社区和新加坡科技设计大学（Singapore University of Technology and Design）联结实现的钻研工作在 ICDE 2023 上作为工业界的惯例论文发表。该项钻研工作加强了 OpenMLDB 的流式特色计算能力，对其中的要害操作 Interval Join 进行了深度优化，获得了比目前工业界广泛应用的算法高达数量级的吞吐和提早优化。基于该优化算法，克服了流式计算在实时机器学习畛域所遇到的性能瓶颈，能够反对在金融、风控、举荐等畛域的毫秒级实时流式特色计算的需要。其论文预印版可在此链接浏览：Scalable Online Interval Join on Modern Multicore Processors in OpenMLDB
OpenMLDB 作为一个线上线下统一的实时特色计算平台，被广泛应用于如反欺诈、风控、实时举荐等场景。在本次的钻研工作中，单方单干对基于 OpenMLDB 进行流式特色的计算能力进行了深度优化。特地的，咱们关注其中的性能瓶颈，即 Interval Join 操作。下图为 Interval Join 的示意图。其基于数据流 S，定义一个往前两秒的工夫窗口，对数据流 R 上在对应工夫窗口内的数据进行 JOIN 或者聚合操作，实现须要的特色计算逻辑。该操作在 Flink 中即为 Interval Join，在 OpenMLDB 中是通过 WINDOW UNION 语法进行副表多行聚合特色的开发，或者也被称为 point-in-time join/aggregation。
Interval Join 在现有的工业界流式解决零碎中，个别应用 key-partitioned based join 算法，简称为 Key-OIJ。比方在工业界中广泛应用的流式计算框架 Flink，即应用了 Key-OIJ 的算法实现 Interval Join 的计算工作。此种算法对于一个 buffer 内的 R 和 S 做 partition，而后对于在雷同 partition 内的数据再进行 join 或者聚合操作。在此次钻研工作中，咱们发现 Key-OIJ 在很多真实世界的工作负载中存在重大的性能问题。次要总结为：
- 工作负载不均衡和数据歪斜。当 key 的数目较少时（甚至如 key 的数量小于线程数量），非常容易呈现数据歪斜的问题，从而导致整体零碎的效率大幅降落。
- 当存在工夫上的重叠窗口时，该算法会带来大量的反复计算，导致大窗口下整体计算效率低下。
- 因为数据无序，导致了整个计算过程的大量数据扫描；并且须要缓存更多的数据以保障后果的正确性。
在实时机器学习畛域，实时特色计算个别对性能的需要在毫秒级别。应用 Key-OIJ 算法进行线上实时计算，很可能会因为高提早而无奈满足业务需要。因而，咱们须要对该算法进行进一步的优化，以满足实时机器学习的需要。
为了克服以上 Key-OIJ 算法存在的问题，优化 Interval Join 的性能，咱们在 OpenMLDB 的现有算法根底上，提出了一个全新的算法，称为 Scalable Online Interval Join（Scale-OIJ）。该算法针对此类工作负载优化，基于 OpenMLDB 的外围数据结构 – 双层跳表，设计了一个反对高效率单写多读（Single-Writer-Multiple-Reader index，即 SWMR）优化的索引。如下图显示了该外围数据结构和 SWMR 机制。第一次跳表保护键值到第二次跳表的映射关系；第二次跳表保护工夫戳到数据行的映射关系，通过双层跳表的数据结构，能够以 log(N) 的工夫复杂度，定位到须要的窗口数据，防止了如 Key-OIJ 算法中的大量数据扫描。通过反对单写多读的无锁并行数据结构，能够更加轻量的在多线程间共享数据。
除了基于双层跳表的外围数据结构，咱们还引入了更多的优化技术。
- 动静调度：通过剖析实时数据流的散布状况，动静调整 partition 的策略，使得数据能够更平均地散布到所有线程上，防止了工作负载不均衡和数据歪斜。基于单写多读的数据结构，不同线程之间能够共享数据，协同对同一个 key 进行解决，即便当 key 的数目较少时，所有线程依然能够放弃较高的稳固的 CPU 利用率。
- 增量聚合：实在数据集中，会呈现大量的窗口重叠的状况，很大地节约了计算资源。通过利用之前计算的后果，增量地更新以后计算，从而防止了反复的数据扫描和计算。当窗口很大的状况下，极大地缩小了整体的数据拜访和计算。
基于以上的优化，咱们对 Scale-OIJ 算法进行了系统性的评估。咱们应用了三个具备不同个性的真实世界数据集进行测试，测试数据集和试验结果显示如下。能够看到，在三个不同的数据集下，咱们设计的 Scale-OIJ 算法比现有的 Key-OIJ 算法均有大幅的晋升：在吞吐方面，有多达 24 倍的晋升；在提早方面，最多缩短了 99% 的提早。
目前，该 paper 提出的 Scale-OIJ 算法曾经和 OpenMLDB 进行了局部整合。将来，咱们将实现最终的工程化整合，为流式特色在 OpenMLDB 的实时处理提供进一步的性能优化。咱们也欢送社区内的开发者和咱们进行前沿的学术单干，独特打造 OpenMLDB 在技术上的当先性。
扫描以下二维码退出咱们的社区技术探讨群
参考资料
- ICDE 论文原文：https://intellistream.github.io/downloads/papers/Zhang-2023-O…
- OpenMLDB 的外围数据结构：实时引擎外围数据结构和优化解析
- OpenMLDB 内基于 WINDOW UNION 语法结构副表多行聚合特色：https://openmldb.ai/docs/zh/main/tutorial/tutorial_sql_2.html…
- OpenMLDB 产品文档：https://openmldb.ai/docs/zh/main/
- OpenMLDB GitHub: https://github.com/4paradigm/OpenMLDB