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的緩存命中率

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

低開銷：作為一個跟蹤緩存工作集大小的輕量級組件，留給Shadow cache的內存很小，利用有限的內存去追蹤“無限”的工作集是相當困難的。另外，由於Shadow cache是在每次應用查詢緩存時對本次查詢的數據進行處理，Shadow cache也必須要做到低CPU開銷，否則將會導致用户的請求被長時間堵塞。

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

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

既然提到了高精準與低開銷兩個需求，那麼我們首先就想到了在各類分佈式數據庫中大放異彩的布隆過濾器，基於布隆過濾器，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。

在完成布隆過濾器鏈之後，我們就可以輕鬆得知之前定義的指標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就將不支持極限命中率的估計。

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

Presto將不同的表存儲在不同的集羣中，以表名在各個集羣之間分享緩存。因此，當一個對於某表請求到來時，該請求總會被髮往相同的集羣。如果不這樣做的話集羣的緩存就容易被各種雜亂不一的表充滿，不能發揮緩存的效果。下面我們通過一張圖來説明路由邏輯：

如上圖所示，table 1到table4有着不同的表名，因此被分配到不同的集羣中 。當請求table1中的數據時，路由邏輯將會把此請求發往cluster1，而請求table3中的數據時，路由邏輯將把請求發往cluster3。

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

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

方案一：當主要集羣正忙時，我們有一個指定的也擁有該緩存的第二集羣會被啓用來為請求進行服務。但這種方法會在每個集羣中佔用額外的緩存空間。

方案二：兩個集羣都被視為主集羣對請求進行服務，並且在這兩個集羣中進行負載均衡，然而這種方案將會使得緩存磁盤空間佔用倍增。

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

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

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