Presto 實踐 | Presto 使用一致性雜湊改善動態叢集的快取命中率

語言: CN / TW / HK

目前,越來越多的使用者開始在 Presto 裡面使用 Alluxio,它通過利用 SSD 或記憶體在 Presto workers 快取熱資料集,避免從遠端儲存讀取資料。 Presto 支援基於雜湊的軟親和排程(hash-based soft affinity scheduling),強制在整個叢集中只快取一到兩份相同的資料,通過允許本地快取更多的熱資料來提高快取效率。 但是,當前使用的雜湊演算法在叢集大小發生變化時效果不佳。 本文介紹了一種用於軟親和排程的新雜湊演算法,一致性雜湊(consistent hashing),來解決這個問題。

Soft Affinity Scheduling

Presto 使用一種稱為軟親和排程的排程策略,將一個 split(最小的資料處理單元)排程到同一個 Presto worker(首選節點)。split 和 Presto worker 的對映關係是通過計算 split 路徑的雜湊值然後 mod 叢集的節點數,確保相同的 split 始終被雜湊到同一個 worker 上。第一次處理 split 時,資料將快取在首選工作節點上。當後續查詢處理相同的 split 時,這些請求將再次排程到相同的 worker 節點上。由於資料已經在本地快取,因此不需要遠端讀取。

為了改善負載平衡和處理不穩定的 worker,選擇了兩個首選節點。如果第一個節點繁忙或沒有響應,則使用第二個節點。所以資料可能在兩臺節點上進行快取。

雜湊演算法

軟親和排程依賴於雜湊演算法來計算 split 和 worker 節點之間的對映。之前使用的是以下演算法:

WorkerID1 =Hash(splitID) % workerCount

WorkerID2 =Hash(splitID) % workerCount + 1

這種雜湊策略很簡單,並且在叢集穩定且 worker 節點沒有變化的情況下執行良好。但是,如果某個 worker 暫時不可用或停機,worker 數量可能會發生變化,這時候 split 到 worker 的對映將被完全打亂,從而導致快取命中率顯著下降。如果有問題的 worker 稍後重新上線,這種情況將再次發生。

為了緩解此問題,Presto 在使用雜湊函式計算 worker 分配時使用所有 worker 數而不是活動 worker 數。但是,這隻能緩解 worker 臨時離線引起的重新計算。由於工作量波動,在某些情況下新增/刪除 worker 是有意義的。在這些情況下,是否仍然可以保持合理的快取命中率而不引入大規模的重新雜湊?解決方案是一致的雜湊。

一致性雜湊

一致性雜湊的概念是由 David Karger 在 1997 年引入的,作為在不斷變化的 Web 伺服器群中分配請求的一種方式。該技術廣泛用於負載均衡、分散式雜湊表等。

一致性雜湊是如何工作的

假設雜湊輸出範圍 [0, MAX_VALUE] 被對映到一個圓上(我們將 MAX_VALUE 連線到 0)。為了演示一致性雜湊是如何工作的,假設一個 Presto 叢集包含 3 個 Presto worker 節點,並且有 10 個 split 被重複查詢。

首先,worker 節點被雜湊到雜湊環上(hashing ring)。按照順時針方向,每個 split 都將分配給雜湊環最近的 worker 上。

如果想及時瞭解Spark、Hadoop或者HBase相關的文章,歡迎關注微信公眾號:iteblog_hadoop

在我們上圖的場景下,split 和 worker 的對映關係如下表所示:

刪除一個節點

現在如果 worker2 因為某種原因下線了,按照一致性雜湊演算法,split 0、5、7 會被分配到下一個雜湊值的 worker 上,也就是 worker1:

只有雜湊到離線 worker(在我們的示例中為 worker2)的 split 需要重新雜湊。其他資料不受影響。如果 worker2 稍後上線,Split 0、5 和 7 將再次被 hash 到 worker2,不影響其他 worker 的命中率。

增加一個節點

現在,如果工作負載增加並且需要將另一個 worker4 節點新增到叢集中。Worker4 的雜湊值在雜湊環上如下:

如果想及時瞭解Spark、Hadoop或者HBase相關的文章,歡迎關注微信公眾號:iteblog_hadoop

在這種情況下 split8 將落入 worker4 的範圍內,所有其他 split 的分配不受影響,因此這些 split 的快取命中率不會受到影響。新的分配關係如下:

虛擬節點

從上面可以看出,一致性雜湊可以保證在節點發生變化的情況下,平均只需要重新雜湊 Nsplits / Nnodes個 splits。然而,由於 worker 分佈缺乏隨機性,split 可能不會在所有 worker 節點之間均勻分佈。我們可以引入“虛擬節點”的概念來緩解這個問題。虛擬節點還可以幫助在斷開連線時將節點的負載重新分配到多個節點,從而減少由於叢集不穩定導致的負載波動。

在雜湊環上,每個物理 worker 節點都有多個虛擬節點對映到環上。split 將分配給雜湊環上的下一個(順時針方向)虛擬節點。以下示例顯示了每個物理 worker 節點具有 3 個虛擬節點的可能場景:

如果想及時瞭解Spark、Hadoop或者HBase相關的文章,歡迎關注微信公眾號:iteblog_hadoop

隨著雜湊環上節點數量的增加,雜湊空間更可能被均勻劃分。

在某個物理節點宕機的情況下,該物理節點對應的所有虛擬節點都會被刪除。但現在不再將所有屬於宕機節點的 spilts 重新雜湊到同一個節點,而是將它們分佈在多個虛擬節點上,從而對映到多個物理節點,提供更好的負載平衡。

下面顯示了當 worker3 被移除時,Split2 和 3 被重新雜湊到 worker2,而 Split8 被重新雜湊到 worker1。

如果想及時瞭解Spark、Hadoop或者HBase相關的文章,歡迎關注微信公眾號:iteblog_hadoop

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

一致性雜湊這個功能是社群最近才新增的功能,目前處於實驗階段。為了使用這個功能,首先可以參照這個文件來啟用快取。然後確保我們選擇了 SOFT_AFFINITY 排程,也就是在 catalog/hive.properties 配置檔案裡面加上如下配置:

hive.node-selection-strategy=SOFT_AFFINITY

啟用一致性雜湊需要到 config.properties 配置檔案裡面加上如下配置:

node-scheduler.node-selection-hash-strategy=CONSISTENT_HASHING

總結

如上所示,當引入或移除節點時,一致性雜湊可以最大限度地減少工作負載分配的影響。當叢集的工作節點發生變化時,基於一致性雜湊排程工作負載可以最大限度地減少對現有節點快取命中率的影響。這使得一致性雜湊成為一種更好的策略,可以在 Presto 的叢集大小根據工作負載需求進行擴充套件和縮減的情況下使用。

本文翻譯自:https://www.alluxio.io/blog/using-consistent-hashing-in-presto-to-improve-caching-data-locality-in-dynamic-clusters/