擴展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 節點，速度線性提升。

嘗試一下吧！包含代碼示例。歡迎反饋。