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

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