扩展ASOF连接

Daft 现在原生支持 ASOF 连接，这是一种对齐时间序列数据的操作，例如以不同速率滴答的传感器流。在这篇文章中，我们将介绍如何实现 ASOF 连接，使其速度提高了 6 倍，并将内存使用量减半。我们将深入探讨三项优化（哈希分组、二分搜索和多线程并行），并展示相同的架构如何扩展到分布式集群。

首先，什么是 ASOF 连接？ASOF 连接通过将每个时间戳与另一个表中的最近时间戳匹配来关联两个数据集。在下面的示例中，左右表中的数据不完全对齐，ASOF 连接试图回答“对于每个视频帧，我们机器人的最新关节角度和夹爪状态是什么？”

如何使用 ASOF 连接在 Daft 中，使用 .join_asof() 方法。on 参数指定匹配的列（通常是时间戳），by 参数指定分区列，使得行仅在同一实体（例如 robot_id）内匹配。

构建 V1：排序+双指针 最初的实现是排序后的双指针搜索。按复合键 (by, on) 对左右表排序，然后使用两个指针遍历。对于每个左行，在右表中找到最后一个时间戳不超过左行时间戳的行。复杂度为 O(N log N + N)。 V2：哈希分组+索引搜索 将数据按 by 键分组到哈希表中，每组内对时间戳排序。对每个左行，在对应组内使用二分搜索找到最接近的右行。复杂度 O(N log K)，K 是组大小。 V3：多任务并行 V3 重新设计了 V2，引入任务并行。哈希映射的每个分区成为一个独立任务，使用与 V1 和 V2 相同的哈希分组方法。每个任务存储自己的结果，允许并行运行。完成后，合并步骤为每个左行选择最佳匹配。V3 的并行度不依赖于数据基数，即使只有两个 by 键也能利用多核。此外，还有内存优化：尽早剪枝右表中的不必要列，使用轻量指针跟踪候选结果。结果：本地 ASOF 连接在速度上优化，同时最小化内存占用。

分布式 ASOF 连接某些数据集无法放入单机内存。一天的机器人数据可能包含 1-10TB 视频和 5-500GB 传感器数据。为此，我们开发了 V4 范围分区 ASOF 连接。它先对键进行采样以估计全局分布，然后计算 N-1 个范围边界，将数据均匀分发给每个工作节点。为了处理跨分区的 by 键，引入“结转”概念：每个工作节点预先挂载前一个分区的最近记录，保证正确性。这样，即使数据倾斜，也能水平扩展，没有热点和长尾延迟。

基准测试显示，在中等规模（左表 1000 万行，右表 1 亿行）上，V3 比 V2 快 1.7 倍，内存减少一半以上。分布式基准测试中，从 2 节点扩展到 8 节点，速度线性提升。

尝试一下吧！包含代码示例。欢迎反馈。