Roblox 如何透過機器學習優化的布隆篩選器降低 Spark 聯結查詢成本

摘要

在 Roblox 上，每天有 7,000 萬名使用者參與數百萬種體驗，每季總計達 160 億小時。這些互動產生了規模達 1 拍字節的資料湖，並經過豐富處理以供分析與機器學習 (ML) 之用。在我們的資料湖中，將事實表與維度表進行聯結是一項資源密集型的作業，因此為了優化此流程並減少資料挪移，我們採用了「學習型布隆濾波器」[1]——一種運用機器學習的智慧型資料結構。 透過預測資料存在性，這些篩選器能大幅精簡聯結資料，從而提升效率並降低成本。在此過程中，我們亦改進了模型架構，並證實其能顯著減少處理所需的記憶體與 CPU 運算時間，同時提升運作穩定性。

引言

在我們的資料湖中，事實表和資料立方體會進行時間分區以提升存取效率，但維度表缺乏此類分區，因此在更新時將其與事實表進行聯結會消耗大量資源。聯結的關鍵範圍取決於被聯結的事實表的時間分區。 該時間分區中所包含的維度實體，僅是整個維度資料集中的一小部分。因此，這些聯結中大部分經過洗牌的維度資料最終都會被捨棄。為優化此流程並減少不必要的洗牌，我們曾考慮在不同的聯結鍵上使用布隆篩（Bloom Filters），但面臨篩選器大小與記憶體佔用空間的問題。

為解決這些問題，我們探索了「學習型布隆篩（Learned Bloom Filters）」，這是一種基於機器學習的解決方案，能在維持低誤報率的同時縮小布隆篩的尺寸。這項創新透過降低運算成本並提升系統穩定性，從而增強了聯結運算的效率。下圖說明了在我們的分散式運算環境中，傳統與優化的聯結流程。

運用學習型布隆過濾器提升聯結效率

為優化事實表與維度表之間的聯結，我們採用了學習型布隆篩選器（Learned Bloom Filter）的實作方案。我們根據事實表中的鍵建立索引，並在聯結運算前部署該索引以預先篩選維度資料。 

從傳統布隆篩選器到學習型布隆篩選器的演進

雖然傳統布魯姆篩選器效率高，但每個工作節點為達到預期的假陽性率，需額外載入 15-25% 的記憶體。然而，透過運用學習型布魯姆篩選器，我們在維持相同假陽性率的同時，大幅縮減了索引大小。這是因為將布魯姆篩選器轉化為二元分類問題所致：正標籤表示索引中存在該值，負標籤則表示不存在。

導入機器學習模型後，系統會先透過模型進行初步值檢查，再由備用布隆篩網消除假陰性結果。索引大小的縮減，源於模型的壓縮表示形式，以及備用布隆篩網所需鍵值數量減少。這正是其與傳統布隆篩網方法的區別所在。 

作為本研究的一部分，我們建立了兩項指標來評估「學習型布隆篩網」方法：索引的最終序列化物件大小，以及執行聯結查詢時的 CPU 消耗量。 

克服實作挑戰

我們面臨的首要挑戰是處理一個高度偏頗的訓練資料集，其中事實表中的維度表鍵值數量極少。在此過程中，我們觀察到各表間的鍵值重疊率約為三分之一。為解決此問題，我們採用了「三明治式學習型布隆篩選器」（Sandwich Learned Bloom Filter）方法 [2]。此方法整合了初始的傳統布隆篩選器，透過移除事實表中缺失的大部分鍵值來重新平衡資料集分佈，從而有效剔除資料集中的負面樣本。 隨後，僅將初始布魯姆篩選器所包含的鍵值，連同誤判的正例，一併傳送至機器學習模型（常被稱為「學習型預言機」）。此方法為學習型預言機生成了一個分布均衡的訓練資料集，有效克服了偏倚問題。

第二項挑戰聚焦於模型架構與訓練特徵。有別於經典的釣魚網址問題 [1]，我們的聯結鍵（在大多數情況下是使用者/體驗的唯一識別碼）本身並不具資訊性。這促使我們探索維度屬性，作為潛在的模型特徵，以協助預測某個維度實體是否存在於事實表中。 舉例來說，假設有一張事實表，其中包含特定語言體驗的用戶會話資訊。用戶維度的地理位置或語言偏好屬性，將是判斷個別用戶是否存在於事實表中的良好指標。

第三項挑戰——推論延遲——需要既能將假陰性率降至最低，又能提供快速回應的模型。梯度提升樹模型是滿足這些關鍵指標的最佳選擇，我們對其特徵集進行了修剪，以在精準度與速度之間取得平衡。

我們運用已訓練的布隆濾波器所更新的聯結查詢如下所示：

結果

以下是我們在資料湖中使用學習型布隆過濾器進行實驗的結果。我們將其整合至五個生產工作負載中，每個工作負載皆具備不同的資料特性。這些工作負載中運算成本最高的部分，在於事實表與維度表之間的聯結。 事實表的鍵空間約為維度表的 30%。首先，我們將探討在最終序列化物件大小方面，學習型布隆過濾器如何優於傳統布隆過濾器。接著，我們將展示將學習型布隆過濾器整合至工作負載處理管線後所觀察到的效能提升。

學習型布隆篩選器大小比較

如下圖所示，在給定的假陽性率下，相較於傳統布隆濾波器，兩種學習型布隆濾波器的變體可將總物件大小縮小 17% 至 42%。

此外，透過在基於梯度提升樹的模型中使用較小的特徵子集，我們在加速推論的同時，僅損失了極少比例的優化效果。

布隆篩選器應用結果 

在本節中，我們將基於布隆篩選器的聯結與一般聯結的效能，針對多項指標進行比較。 

下表比較了採用與未採用學習型布隆篩選器的工作負載效能。下方的比較採用了總假陽性率為 1% 的學習型布隆篩選器，並確保兩種聯結類型均維持相同的叢集配置。 

首先，我們發現布隆篩選器（Bloom Filter）的實作在 CPU 耗時方面，比傳統的聯結操作快了多達 60%。由於評估布隆篩選器需要額外的運算資源，我們觀察到「學習型布隆篩選器」方法在掃描步驟的 CPU 使用率有所增加。然而，此步驟進行的預篩選減少了需要重新排序的資料量，這有助於降低後續步驟的 CPU 使用率，從而減少總體 CPU 耗時。

其次，相較於傳統聯結，學習型布隆篩網的總資料量減少約 80%，寫入的總洗牌位元組數也減少約 80%。這將帶來更穩定的聯結效能，詳情如下所述。 

在實驗中的其他生產工作負載中，我們也觀察到資源使用量的降低。在為期兩週、涵蓋所有五項工作負載的期間內，學習型布隆篩網方法平均每日節省了 25% 的成本，此數據已包含模型訓練與索引建立的開銷。

由於執行關聯時需洗牌的資料量減少，我們不僅顯著降低了分析管道的營運成本，同時也提升了其穩定性。下圖顯示了在為期兩週的實驗期間，針對我們測試的五項工作負載，常規關聯工作負載與基於學習型布隆篩濾器的工作負載在執行時間（實際執行時間）上的變異性（使用變異係數計算）。 採用學習型布魯姆篩的執行結果更為穩定——執行時間更為一致——這為將其遷移至成本較低、但可靠性較低的臨時運算資源開闢了可能性。 

參考文獻

[1] T. Kraska、A. Beutel、E. H. Chi、J. Dean 及 N. Polyzotis。學習型索引結構的論證。https://arxiv.org/abs/1712.01208，2017。

[2] M. Mitzenmacher. 透過夾層法優化學習型布隆濾波器。 

https://arxiv.org/abs/1803.01474，2018。

¹截至 2023 年 6 月 30 日止之 3 個月期間

²截至 2023 年 6 月 30 日止之 3 個月期間