摘要
分散式快取被廣泛應用於以十億使用者規模服務於社交網路和網路應用。然而，典型的工作負載偏差會導致快取伺服器之間的負載不平衡。這種負載不平衡降低了請求吞吐量，並增加了請求延遲，從而降低了快取的好處。最近的研究從理論上表明，前端一個小的完美快取對分散式快取的負載平衡有很大的影響。然而，確定在前端伺服器上實現近乎完美的快取的快取大小和替換策略是一項挑戰，特別是對於動態變化和不斷變化的工作負載。這篇文章介紹了Cache on Track（CoT），這是一個用於雲環境的分散、彈性和預測性的快取框架。CoT是以下問題的答案：在快取伺服器端實現負載平衡所需的前端快取大小是多少？CoT提出了一個新的快取替換策略，專門為服務於傾斜工作負載的小型前端快取量身定製。前端伺服器使用重擊跟蹤演算法來連續跟蹤top-k熱鍵。CoT從跟蹤的金鑰中動態快取最熱的C金鑰。此外，每個前端伺服器獨立地監視其對快取伺服器負載不平衡的影響，並相應地調整其跟蹤器和快取大小。我們的實驗表明，CoT的替換策略在不同的傾斜工作負載下，對於相同的快取大小，始終超過LRU、LFU和ARC的命中率。此外，CoT的命中率略高於LRU-2當兩個策略的跟蹤（歷史）大小相同時。CoT實現了伺服器大小的負載平衡，與其他替換策略相比，前端快取減少了50%到93.75%。最後，我們的實驗表明，CoT的大小調整演算法成功地自動配置了跟蹤器和快取大小，以在工作負載分佈發生變化的情況下實現後端負載平衡。
介紹
社交網路、網路和移動應用吸引了數億使用者[3，7]。這些使用者分享他們的關係，並在及時的個性化體驗中交換影象和影片[13]。為了實現這種實時體驗，底層儲存系統必須提供對大資料的高效、可擴充套件和高可用性訪問。社交網路使用者消耗的資料比他們產生的資料多出幾個數量級[10]。此外，單頁載入需要數百個物件查詢，這些物件查詢需要在幾秒鐘內完成[13]。因此，傳統的基於磁碟的儲存系統不適合處理這種規模的請求，因為磁碟的高訪問延遲和I/O吞吐量限制[50]。
為了克服這些限制，分散式快取服務被廣泛地部署在每個客戶儲存的頂部，以便高效地為大規模的使用者請求提供服務[49]。Memcached[4]和Redis[5]等分散式快取系統被Amazon Elasti Cache[1]和Azure Redis Cache[2]等雲服務提供商廣泛採用。這些快取服務為直接訪問每一個電阻儲存層的系統提供了顯著的延遲和吞吐量提升。Redis和Memcached使用con-sistent雜湊[35]在多個快取伺服器之間分發金鑰。儘管一致雜湊確保了分配給每個快取碎片的金鑰數量的公平分佈，但它不考慮分配過程中每個金鑰的工作負載。現實世界的工作負載通常是傾斜的，很少有鍵比其他鍵更熱[30]。這種傾斜導致快取伺服器之間的負載不平衡。
快取層中的負載不平衡可能會對整個應用程式效能產生顯著影響。尤其是，它可能導致在接入頻率分佈的尾部的操作延遲急劇增加[29]。此外，當工作負載偏差增加時，平均吞吐量降低，平均延遲增加[15]。當在依賴資料物件鏈中執行操作時，實際工作負載的平均延遲和尾部延遲的這種增加是放大的[41]。一次Facebook頁面載入會在多輪資料獲取操作中檢索數百個物件[44，13]。最後，解決方案同樣會過度配置快取層資源，以處理負載最重的快取伺服器所帶來的資源利用率最低的快取伺服器所帶來的影響。
為了解決負載不平衡問題，人們提出了多種方法，使用集中負載監控[9，48]、伺服器端負載監控[29]或前端負載監控[24]。Adya等人。[9] 提出將資料服務平面與控制平面分離的切片器。控制平面是一個集中化的系統元件，它收集有關碎片訪問和伺服器工作負載的元資料。它定期執行一個最佳化演算法，該演算法決定重新分配、重新分割槽或複製金鑰空間的片段，以實現更好的後端負載平衡。Hong等人。[29]使用分散式伺服器端負載監控來解決負載不平衡問題。每個後端伺服器都獨立地跟蹤其熱鍵和取消決定，以便將其熱鍵的工作負載分配給其他後端伺服器。[9，48]和[29]中的解決方案要求後端更改快取的金鑰-伺服器對映並將新對映公佈到所有的前端伺服器。Fan等人。[24]使用分散式前端負載監控方法。這種方法表明，在前端伺服器中新增一個小快取對解決後端負載不平衡有很大的影響。在前端伺服器上快取重量級使用者可以減少快取伺服器提供的金鑰之間的偏差，從而實現更好的後端負載平衡。Fan等人。理論上透過分析和模擬表明，每個前端都有一個小的完美快取，解決了後端負載不平衡的問題。然而，完美的快取實際上很難實現。為了動態地改變和發展工作負載，確定快取大小和在前端實現接近每影響快取的替換策略是一項挑戰。
在這篇文章中，我們提出了Cache-on-Track（CoT），它是一種分散的、彈性的、預測性強的前端伺服器快取。CoT pro提出了一個新的快取替換策略，專門針對服務於傾斜工作負載的小型前端快取。CoT使用一個小的前端快取來解決後端負載不平衡的問題，如[24]中介紹的。然而，CoT並不認為前端有完美的快取。CoT使用節省空間的演算法[43]來跟蹤top-k重擊手。跟蹤資訊允許CoT從top-k跟蹤的近似鍵中快取出準確的top-C最熱鍵，以防止長尾的冷鍵和噪聲鍵替換快取中的熱鍵。CoT是分散的，因為每個前端獨立地根據在這個特定前端服務的金鑰訪問分配來確定其熱鍵集。這種低成本的CoT解決了後端負載不平衡的問題，沒有引入單一的故障點或瓶頸，這些通常都是集中解決方案帶來的。此外，這使得CoT可以擴充套件到數千個前端伺服器，這是社交網路和現代web應用程式的共同要求。CoT是彈性的，因為每個前端使用其本地負載資訊來監視其對後端負載不平衡的貢獻。每個前端彈性地調整其跟蹤器和快取大小，以減少由這個前端引起的負載不平衡。在工作負載發生變化的情況下，CoT除了動態調整跟蹤器和快取大小之外，還動態調整前端跟蹤器與快取的比率，以消除任何後端負載不平衡。
在傳統的架構中，記憶體大小是靜態的，快取演算法努力實現所有可用資源的最佳利用。然而，在雲環境中，理論上存在有限的記憶體和處理資源，而云站姿遷移是一種常態，雲終端使用者的目標是實現其slo，同時減少所需的雲資源，從而降低其貨幣部署成本。CoT的主要目標是在每個前端減少必要的前端快取大小，以消除伺服器端負載不平衡。減少前端快取大小對於以下方面至關重要：1）它降低了部署前端快取的金錢成本。為此，我們引用大衛•洛米特（David Lomet）最近的著作[40，39，38]中的話，他指出成本/效能通常比純粹的效能更重要：“這裡的論點不是沒有足夠的主記憶體來儲存資料，而是有一種成本更低的資料管理方法。”。
2） 在資料更新的情況下，當需要資料一致性時，增加前端快取大小會顯著增加資料一致性管理技術的成本。請注意，社交網路和現代web應用程式執行在成千上萬的前端伺服器上。增加前端快取大小不僅會使部署更大快取的成本乘以前端伺服器的數量，但也增加了一致性管理管道中的一些成本，包括a）跟蹤不同前端伺服器中的金鑰體現的成本，b）將更新傳播到前端伺服器的網路和處理成本。3） 由於工作負載是傾斜的，我們的經驗清楚地表明，新增更多前端快取線的相對成本（以每個快取線的平均快取命中率和後端負載不平衡減少來衡量）隨著前端快取大小的增加而急劇減少。
CoT的調整大小演算法根據動態工作負載的變化動態地增加或減少前端分配的記憶體。CoT的動態調整大小演算法在不同的雲設定中很有價值
1） 所有前端伺服器部署在同一個資料中心，並獲得相同的動態演進工作負載分佈；2）所有前端伺服器部署在同一個資料中心，但獲得不同的動態演進工作負載分佈，
最終3）前端伺服器部署在不同的邊緣資料中心，並獲得不同的動態變化的工作負載分佈。特別是，CoT旨在從每個單獨的前端伺服器的角度捕捉本地趨勢。在社交網路應用程式中，服務於不同地理區域的前端伺服器可能會經歷不同的金鑰訪問分佈和不同的本地趨勢（例如，邁阿密與紐約）。類似地，在大型資料處理管道中，幾個應用程式部署在共享快取層的頂部。每個應用程式可能對不同的資料分割槽感興趣，因此體驗不同的金鑰訪問分佈和本地趨勢。CoT在前端伺服器上執行的是細粒度金鑰級別，而Slicer[9]這樣的解決方案在快取伺服器上執行的是較粗的細粒度切片或碎片。伺服器端解決方案是對CoT的補充。雖然捕獲本地趨勢可以減輕快取伺服器之間的負載並減少負載不平衡，但其他因素可能會導致負載不平衡，因此使用伺服器端負載平衡（例如切片器）可能仍然是有益的。
我們在本文中的貢獻總結如下。
•快取在軌（CoT）是一種分散的、有彈性的，
以及預測性的前端快取框架
減少後端負載不平衡並改進
整體表現。
•
CoT動態地最小化所需的前端快取大小，以實現後端負載平衡。與其他替代政策相比，CoT的內建彈性是一個關鍵的新優勢。
•
廣泛的實驗研究，將CoT的替代政策與傳統的以及最先進的替代政策，即LFU、LRU、ARC和LRU-2進行比較。實驗結果表明，與其他替換策略相比，CoT在不同工作負載下實現了伺服器大小的負載平衡，前端快取減少了50%到93.75%。
•實驗研究表明
成功地自動配置跟蹤程式和快取
大小以實現後端負載平衡。
•在我們的實驗中，我們發現
YCSB的[19]加密工作負載發生器-
阿托爾。這個生成器生成的工作負載
明顯沒有承諾的那麼偏斜
壓縮分佈。
論文的其餘部分安排如下。第二節介紹了系統和資料模型。在第3節中，我們透過介紹在前端使用LRU、LFU、ARC和LRU-k快取的主要優點和侷限性來激勵CoT。我們在第四節介紹了嬰兒床的細節。第五節對膠輥的效能和執行費用進行了評估，第六節對相關工作進行了討論，第七節對論文進行了總結。