Meta(Facebook): 基於Alluxio Shadow Cache優化Presto架構決策

語言: CN / TW / HK

在這裡插入圖片描述

01 動機與背景

Facebook Presto是一個以SQL語言作為介面的分散式實時查詢引擎,可以對PB級的資料進行快速的互動式查詢。它支援標準的ANSI SQL.包含查詢、聚合、JOIN以及視窗函式等。

Alluxio將其在資料層的創新作為Presto和各種分析應用程式和用例的關鍵支援技術。它建立了一個虛擬資料層,可以聚合來自任何檔案或物件儲存的資料,提供跨儲存系統的統一名稱空間,並允許應用程式繼續使用原有的行業標準介面來訪問資料,同時能夠為Presto提供記憶體級別的速度和響應時間。

為了提高請求的響應速度,Presto正在探索快取容量與快取命中率對於效能的影響。Presto需要通過Alluxio知道某些關於快取的資訊,從而判斷當一個叢集被快取大小所限制時,擴大快取容量是否能夠幫助叢集提高快取命中率以及請求的響應速度。同時這些資訊也能夠對探索快取演算法潛在的優化策略提供一定的幫助。在此基礎上,為了更好的負載均衡和效率,Presto想要通過這些資訊優化快取擴容的路由演算法。於是如何更好的對Alluxio快取資料進行追蹤管理,就成了presto優化決策的關鍵。

針對上面Presto提出的需求,我們提出兩個關鍵問題:

執行的應用程式需要多大的快取?
快取的命中率提升的極限在哪裡?

我們提出Shadow cache:用於追蹤工作集大小和快取命中率的輕量級Alluxio元件。首先為解決第一個問題,Shadow cache會告知管理者在過去24小時之內快取一共接受到了多少互不重複的bytes,依此可以估計出未來快取的需求量。此外為解決另一個問題,Shadow cache將會告知管理者在快取能夠將過去24h的所有請求全部保留的情況下請求命中快取的數量,也就是說,未命中的都是從未出現過的資料,而這就意味著得到了快取最大命中率。

這個輕量級的Alluxio元件Shadow cache能夠提供相當於無限快取空間下,快取工作集大小以及快取命中率的趨勢。因此,我們定義以下關鍵指標,希望這些指標能夠為我們觀察叢集快取狀態提供幫助:

C1: 在一段時間內的真正的快取佔用空間大小

C2:Shadow cache在一個時間視窗中的工作集

H1:真實快取命中率

H2:Shadow cache的快取命中率

02 挑戰

想要為Alluxio的快取提供上述指標是十分困難的,在實踐嘗試的過程中我們也遇到了方方面面的問題,我們將Shadow cache面臨的挑戰歸類為以下三個方面:

低開銷:作為一個跟蹤快取工作集大小的輕量級元件,留給Shadow cache的記憶體很小,利用有限的記憶體去追蹤“無限”的工作集是相當困難的。另外,由於Shadow cache是在每次應用查詢快取時對本次查詢的資料進行處理,Shadow cache也必須要做到低CPU開銷,否則將會導致使用者的請求被長時間堵塞。

高精準:Shadow cache也必須要有精度上的保證,在Presto中,Shadow cache被用於評估叢集的快取狀況,如果估計的極限快取命中率過小,可能會使Presto錯誤的判斷此作業是快取不友好的;相反的,如果估計的極限快取命中率過大,可能導致Presto認為此時叢集擴大快取能夠極大地提升整體效能。

實時性:Presto以及其他大多數應用在如今都只關心能夠反映當前或未來趨勢的最新項。因此,實時地將過時的項丟棄對於Shadow cache也是相當重要的。否則,很有可能對決策帶來噪音干擾。【滑動視窗】便是記錄最新項的著名技術之一,然而為滑動視窗模型設計資料結構也不是一件簡單的事情。每當視窗滑動時,都需要我們實時地刪去那些剛剛被移出視窗的項。如何找到需要被刪的項以及儘量快的刪去它成為了一個重要的問題。

03 實現方案

既然提到了高精準與低開銷兩個需求,那麼我們首先就想到了在各類分散式資料庫中大放異彩的布隆過濾器,基於布隆過濾器,Shadow cache便完成了對工作集大小和極限命中率的估計。下面我們來對布隆過濾器做一個簡單的介紹:

布隆過濾器:滿足開銷小與精度高的要求

布隆過濾器是一個以bit為單位的初始化全0的陣列,它將每個項對映為幾個bits,極大的節省了空間上的開銷,並能夠以極高的效率進行查詢。布隆過濾器能夠判斷項是否存在,若布隆過濾器返回該項不存在,則項一定不存在。反之,則該項不一定存在。在這裡插入圖片描述
布隆過濾器擁有k個hash函式,在插入一個項時,會對此項分別進行k次hash運算,並得到k個位置,將在過濾器中對應位置的bit將被置為1。而需要查詢時,則仍然對項進行k次hash運算,若得到的k個位置上所有bit都為1,那麼判斷此項存在,否則判斷此項不存在。具體過程如上圖所示。

實時更新!布隆過濾器鏈

既然布隆過濾器能夠同時滿足開銷小和精度高的兩種需求,那麼我們能夠直接將布隆過濾器應用於Shadow cache中嗎?

首先我們遇到的問題就是布隆過濾器不支援刪除,我們不關心比較久遠的工作集負載情況,而只關心使用者的應用程式在過去的一段時間中的工作集大小,這就要求Shadow cache必須做到能夠將過時的項刪去,為了做到這一點,Shadow Cache將多個過濾器連線到一起,組成了布隆過濾器鏈。下面我們來看看如何通過布隆過濾器鏈,實時地對工作集負載大小進行更新
在這裡插入圖片描述
查詢:如上圖所示,Shadow cache是由多個布隆過濾器所組成的鏈,如果我們需要跟蹤的是使用者過去24h的工作集大小,那麼可以將24h分為4個時間段,對應每個時間段Shadow cache有一個布隆過濾器,每個布隆過濾器都跟蹤一個時間段。對於一個項的查詢,Shadow cache會將所有布隆過濾器相“或“得到新的布隆過濾器,再對新的布隆過濾器進行此項的查詢,如下圖所示:在這裡插入圖片描述
更新:而為了保證資料的實時性,當時間視窗進行滑動時,我們需要Shadow cache丟棄已經過時的資料。也就是說需要隨著時間t不斷更新布隆過濾器中的數值,將布隆過濾器中已經處於時間視窗外的項刪掉。如下圖所示,由於我們是將多個布隆過濾器組合在了一起,因此,很容易判斷過時的項的位置,它們就處於最末端的布隆過濾器中。於是每當一個新的時間段到來,我們就從鏈中刪去最老的過濾器,並新增一個全空的過濾器來記錄最新資料。在這裡插入圖片描述
工作集大小:布隆過濾器將一個項對映為多個 bits,若將工作集大小直接判斷為bit為1的數量將會帶來不可接受的誤差,因為某一bit可能代表多個項,而某一項也被分散為了多個bits,於是在這裡我們使用了Swamidass & Baldi (2007) 所推匯出的以下公式對工作集大小進行估算,並取得了良好的效果:在這裡插入圖片描述
其中是被插入進過濾器中所有元素的估計值,m是過濾器的長度(大小),k是hash函式的個數,X是所有被置為1的位置的個數。

極限命中率:在提供了工作集大小這一指標後,Shadow cache還需要提供極限命中率這一指標。由於布隆過濾器能夠以極小的記憶體使用量跟蹤巨量的資料,我們可以將布隆過濾器視作一個空間大小為無限的快取,因此,“使用者請求“命中布隆過濾器的數量就相當於命中一個無限大小的快取的數量,我們將此數量記為hit,而“使用者請求”的總數量記為queryNum,於是極限命中率就等於hit/queryNum。

利用Shadow cache判斷Presto叢集快取狀態

在完成布隆過濾器鏈之後,我們就可以輕鬆得知之前定義的指標H1、H2、C1、C2,之後Presto可以通過比較它們之間的大小關係來判斷叢集的快取狀態,如下圖所示:在這裡插入圖片描述
當H2比較低時,表明就算擁有無限的快取空間,也不能使得快取命中率達到理想的數值,因此說明該叢集中執行的應用是快取不友好的。當H2高H1低且C2>C1時,說明叢集的快取空間分配不足,如果擴大快取容量,命中率能夠進一步提高;而當H2高H1高且C2>C1時,證明叢集狀態良好,無需對快取進行縮放。

具體實現

Shadow cache的布隆過濾器實現是基於Guava庫的,並且支援根據使用者自定義的空間開銷,視窗大小等引數選擇過濾器的具體配置。目前Shadow cache支援統計的工作集單位包括pages和bytes,分別代表工作集包含多少頁以及工作集包含多少具體bytes。而對於命中率的計算,Shadow cache 可以以byte為單位記為一次命中,同樣的也可以用一個物件為單位來記為一次命中。

配置項如下圖示:
在這裡插入圖片描述

評估測試

我們對Shadow cache進行了實驗評估,發現僅需125MB的空間,Shadow cache就能追蹤27TB的工作集,並且錯誤率僅有3%。並且錯誤率還可以通過HyperLogLog演算法進一步減少,但如果使用HyperLogLog就將不支援極限命中率的估計。

04 Presto 路由優化

在利用Shadow cache得知叢集的具體狀態後,如果叢集狀態不良,Presto需要一些手段來及時的調整叢集,以此提高叢集的響應速度。我們接下來先介紹目前presto的路由演算法,然後給出幾種在加入Shadow cache之後可選的路由優化方案。

Presto路由

Presto將不同的表儲存在不同的叢集中,以表名在各個叢集之間分享快取。因此,當一個對於某表請求到來時,該請求總會被髮往相同的叢集。如果不這樣做的話叢集的快取就容易被各種雜亂不一的表充滿,不能發揮快取的效果。下面我們通過一張圖來說明路由邏輯:
在這裡插入圖片描述
如上圖所示,table 1到table4有著不同的表名,因此被分配到不同的叢集中 。當請求table1中的資料時,路由邏輯將會把此請求發往cluster1,而請求table3中的資料時,路由邏輯將把請求發往cluster3。

路由優化方案

判斷一個叢集是否正常的一個簡單方案就是看一個指向某個叢集的請求的響應時間,若該叢集遲遲沒有迴應或迴應的時間過長,我們就認為該叢集出現了問題。在有了Shadow cache之後,就像上文所提到的,結合H1、H2、C1、C2,我們可以快速判斷一個叢集是否是因為快取有壓力而出現的效能下降。

對於這樣一個表現不佳的叢集,Presto提出以下三種路由優化方案:

方案一:當主要叢集正忙時,我們有一個指定的也擁有該快取的第二叢集會被啟用來為請求進行服務。但這種方法會在每個叢集中佔用額外的快取空間。

方案二:兩個叢集都被視為主叢集對請求進行服務,並且在這兩個叢集中進行負載均衡,然而這種方案將會使得快取磁碟空間佔用倍增。

方案三:基於請求的模式來交換各叢集中的表,進而讓CPU佔用的分佈更加均勻。同樣的,這種方案也有問題:會使得快取分佈不均勻從而需要額外的快取空間。

05 總結

對使用者快取中的工作集大小進行追蹤估算是一項重要而又富有挑戰性的工作,為此我們基於布隆過濾器設計了一個輕量化的Alluxio元件Shadow cache。由於我們只關心使用者工作集大小的最新情況,因此需要使用時間視窗模型來淘汰過時項,為此Shaodow cache將時間視窗拆分為4段,每段用不同的布隆過濾器進行跟蹤,每次淘汰時只需刪除最早建立的布隆過濾器,再建立一個新的布隆過濾器追蹤最新資料。最後,需要提供工作集大小時,我們用到了Swamidass & Baldi (2007) 提出的基數估計公式。

總體來看,Shadow cache為Presto提供了四種方便的指標:H1、H2、C1、C2,其中H1、C1分別代表真實快取命中率和容量,而H2、C2則代表著快取的極限命中率以及一段時間內使用者的工作集大小。基於以上的四種指標,Presto能夠輕鬆的判斷快取容量與應用效能之間的關係 ,並進一步探索路由演算法的優化策略。

想要獲取更多有趣有料的【活動資訊】【技術文章】【大咖觀點】,請關注[Alluxio智庫]