在Presto中利用一致性雜湊演算法增強動態叢集的資料快取本地性

語言: CN / TW / HK

本文作者:鍾榮榮 Presto TSC member/Commiter

將Alluxio與Presto結合執行在社群中越來越流行,使用固態硬碟或記憶體來快取熱資料集,能夠實現近Presto worker的資料本地行,從而避免了遠端讀取資料導致的高延遲。Presto支援基於雜湊的軟親和排程(soft affinity scheduling),這樣整個叢集中相同資料只快取一、兩個副本,更多的熱資料能被快取到本地,提高快取效率。現有雜湊演算法在叢集規模發生變化時效果並不理想。針對這一問題,本文介紹了一種可用於軟親和排程的新雜湊演算法——一致性雜湊(consistent hashing)。

軟親和排程

Presto使用一種叫做軟親和排程(soft affinity scheduling)的排程策略,將一個分片(split, 最小的資料處理單位)排程到同一個Presto worker(首選節點)上。分片和Presto worker之間的對映關係是由分片上的雜湊函式計算出來的,確保同一個分片總是被雜湊到同一個worker上。

在第一次處理分片時,資料將被快取在首選worker節點上。當後續的查詢處理同一分片時,這些請求將再次被排程到同一個worker節點上。此時,由於資料已經快取在本地,不需要再遠端讀取資料。

為了提高負載均衡,更好地處理worker節點響應不穩定的問題,會選擇兩個首選節點。如果第一個節點繁忙或沒有響應,則會使用第二個節點。資料可能會被物理快取到兩個worker節點上。

關於軟親和排程的更多資訊,請檢視“通過 Alluxio 資料快取降低Presto延遲”(https://prestodb.io/blog/2020/06/16/alluxio-datacaching#soft-affinity-scheduling

雜湊演算法

軟親和排程依靠雜湊演算法來計算分片和worker節點之間的對映關係。原先使用的是取模函式:

該雜湊策略很簡單,而且在叢集穩定、worker節點沒有變化的情況下效果很好。但是,如果某個worker節點暫時不可用或者掉線,worker節點的數量可能會發生變化,分片到worker節點的對映將全部需要重新分配,導致快取命中率大幅下降。如果出現問題的worker稍後重新上線,則需要再次重新分配。

針對這個問題,Presto在通過取模計算出哪個worker分配給特定分片時,會對worker總數取模,而不是正在執行的worker數量。然而,這隻能緩解worker節點臨時掉線造成的重新分配問題。有時候因為工作負載的波動,增加/刪除worker是合理操作。在這些情況下,是否可能保持合理的快取命中率而無需進行大規模的重新分配?

我們的解決方案是一致性雜湊演算法。

一致性雜湊

一致性雜湊由David Karger在1997年第一次提出,是一種將網路訪問請求分發到一組數量時常發生變化的網路伺服器的分配演算法。該技術被廣泛用於負載均衡、分散式雜湊表等。

一致性雜湊的工作原理

比如,將雜湊輸出範圍[0, MAX_VALUE]對映到一個圓環上(將MAX_VALUE連線到0)。為了說明一致性雜湊的工作原理,我們假設一個Presto叢集由3個Presto worker節點組成,其中有10個分片被反覆查詢。

首先,worker節點被雜湊到雜湊環上。每個分片都被分配給雜湊環上與該分片的雜湊值相鄰的worker(注:這裡“相鄰”定義為從分片雜湊值所在位置,按順時針方向找到的第一個worker節點)。

上述情況下,分片的分配如下:

刪除一個worker

現在,如果worker2由於某種原因下線,那麼根據演算法,分片0、5和7將被排程到對應下一個雜湊值的worker,也就是worker1上。

只有被分配到到已下線worker(在這裡是worker2)的分片需要重新確定分配到哪個worker。其他資料不受影響。如果 worker32 稍後上線,分片 0、5 和 7 將會被重新分配到 worker2,不會影響其他worker的命中率。

增加一個worker

如果工作負載增加,需要在叢集中增加另一個worker節點——worker4, worker4的雜湊值在雜湊環上的位置情況如下圖所示:

在這種情況下,分片8將落入worker4的區間,所有其他分片的分配不受影響,因此這些分片的快取命中率不會受到影響。重新分配的結果如下:

虛擬節點

從上面可以看出,一致性雜湊可以保證在節點變化的情況下,平均只有

的分片需要被重新分配。然而,由於worker分佈缺乏隨機性,分片可能不會均勻地分佈在所有worker節點上。針對這一問題,我們引入了“虛擬節點 ”的概念。虛擬節點能夠在某個節點斷開連線時將它的負載重新分配給多個節點,從而減少因叢集不穩定而造成的負載波動。

將每個物理worker節點對映成多個虛擬節點。這樣虛擬節點便替代原先的物理節點,位於雜湊環上。隨後,每個分片將首先被分配到相鄰(順時針方向最鄰近)的虛擬節點,再路由到虛擬節點對映的物理節點。下圖的示例是一種可能出現的情況,即每個物理worker節點都對應3個虛擬節點。

隨著雜湊環上節點數量的增加,雜湊空間將被分割地更均勻。

在一個物理節點宕機的情況下,與該物理節點相對應的所有虛擬節點都將被重新雜湊。這裡不是所有的分片都被重新分配到同一個節點上,而是會分配到多個虛擬節點,從而對映到多個物理節點上,以達到更好的負載均衡。

如下圖所示,當刪除worker3時,分片2和3將被重新雜湊到worker2,而分片8被重新雜湊到worker1。

如何在Presto中使用一致性雜湊?

這是我們最近貢獻給Presto的一個實驗性功能。如果有意向進行測試或合作,請聯絡我們。

使用該功能前,請先根據指南(https://prestodb.io/docs/current/cache/alluxio.html)或教程(https://docs.alluxio.io/os/user/stable/en/compute/Presto.html)啟用Presto的快取。確保你選擇SOFT_AFFINITY作為排程策略的配置項。在/catalog/hive.properties檔案中,新增hive.node-selection-strategy=SOFT_AFFINITY。

需要通過在config.properties中新增node-scheduler.node-selection-hash-strategy=CONSISTENT_HASHING來啟用一致性雜湊。

結論

如上所述,當增加或刪除節點時,一致性雜湊可以使工作負載重新分配所產生的的影響降到最低。當叢集的worker節點發生變化時,基於一致性雜湊演算法進行工作負載在worker節點間的分配,可以儘量降低對現有節點上快取命中率的影響。因此,在Presto叢集規模按照工作負載的需要擴縮容的場景下,或者部署環境中的硬體裝置不完全受控而導致worker節點可能隨時被重新分配和調整的場景下,一致性雜湊策略都會成為一種更好的選擇。

在Alluxio社群,我們一直在不斷改進Alluxio和各類計算引擎(例如文中的Presto)在功能性和可用性方面的整合。隨著在Presto排程中引入一致性雜湊,Alluxio可以利用Presto的軟親和特性,實現更好的資料本地性和快取效率,最終提高處理效能並降低成本。我們將持續致對整個資料生態圈進行貢獻,不斷改進和優化我們的產品。