摘要

分布式緩存被廣泛應(yīng)用于以十億用戶規(guī)模服務(wù)于社交網(wǎng)絡(luò)和網(wǎng)絡(luò)應(yīng)用。然而，典型的工作負(fù)載偏差會(huì)導(dǎo)致緩存服務(wù)器之間的負(fù)載不平衡。這種負(fù)載不平衡降低了請(qǐng)求吞吐量，并增加了請(qǐng)求延遲，從而降低了緩存的好處。最近的研究從理論上表明，前端一個(gè)小的完美緩存對(duì)分布式緩存的負(fù)載平衡有很大的影響。然而，確定在前端服務(wù)器上實(shí)現(xiàn)近乎完美的緩存的緩存大小和替換策略是一項(xiàng)挑戰(zhàn)，特別是對(duì)于動(dòng)態(tài)變化和不斷變化的工作負(fù)載。這篇文章介紹了Cache on Track（CoT），這是一個(gè)用于云環(huán)境的分散、彈性和預(yù)測(cè)性的緩存框架。CoT是以下問題的答案：在緩存服務(wù)器端實(shí)現(xiàn)負(fù)載平衡所需的前端緩存大小是多少？CoT提出了一個(gè)新的緩存替換策略，專門為服務(wù)于傾斜工作負(fù)載的小型前端緩存量身定制。前端服務(wù)器使用重?fù)舾櫵惴▉磉B續(xù)跟蹤top-k熱鍵。CoT從跟蹤的密鑰中動(dòng)態(tài)緩存最熱的C密鑰。此外，每個(gè)前端服務(wù)器獨(dú)立地監(jiān)視其對(duì)緩存服務(wù)器負(fù)載不平衡的影響，并相應(yīng)地調(diào)整其跟蹤器和緩存大小。我們的實(shí)驗(yàn)表明，CoT的替換策略在不同的傾斜工作負(fù)載下，對(duì)于相同的緩存大小，始終超過LRU、LFU和ARC的命中率。此外，CoT的命中率略高于LRU-2當(dāng)兩個(gè)策略的跟蹤（歷史）大小相同時(shí)。CoT實(shí)現(xiàn)了服務(wù)器大小的負(fù)載平衡，與其他替換策略相比，前端緩存減少了50%到93.75%。最后，我們的實(shí)驗(yàn)表明，CoT的大小調(diào)整算法成功地自動(dòng)配置了跟蹤器和緩存大小，以在工作負(fù)載分布發(fā)生變化的情況下實(shí)現(xiàn)后端負(fù)載平衡。

介紹

社交網(wǎng)絡(luò)、網(wǎng)絡(luò)和移動(dòng)應(yīng)用吸引了數(shù)億用戶[3，7]。這些用戶分享他們的關(guān)系，并在及時(shí)的個(gè)性化體驗(yàn)中交換圖像和視頻[13]。為了實(shí)現(xiàn)這種實(shí)時(shí)體驗(yàn)，底層存儲(chǔ)系統(tǒng)必須提供對(duì)大數(shù)據(jù)的高效、可擴(kuò)展和高可用性訪問。社交網(wǎng)絡(luò)用戶消耗的數(shù)據(jù)比他們產(chǎn)生的數(shù)據(jù)多出幾個(gè)數(shù)量級(jí)[10]。此外，單頁加載需要數(shù)百個(gè)對(duì)象查找，這些對(duì)象查找需要在幾秒鐘內(nèi)完成[13]。因此，傳統(tǒng)的基于磁盤的存儲(chǔ)系統(tǒng)不適合處理這種規(guī)模的請(qǐng)求，因?yàn)榇疟P的高訪問延遲和I/O吞吐量限制[50]。

為了克服這些限制，分布式緩存服務(wù)被廣泛地部署在每個(gè)客戶存儲(chǔ)的頂部，以便高效地為大規(guī)模的用戶請(qǐng)求提供服務(wù)[49]。Memcached[4]和Redis[5]等分布式緩存系統(tǒng)被Amazon Elasti Cache[1]和Azure Redis Cache[2]等云服務(wù)提供商廣泛采用。這些緩存服務(wù)為直接訪問每一個(gè)電阻存儲(chǔ)層的系統(tǒng)提供了顯著的延遲和吞吐量提升。Redis和Memcached使用con-sistent散列[35]在多個(gè)緩存服務(wù)器之間分發(fā)密鑰。盡管一致散列確保了分配給每個(gè)緩存碎片的密鑰數(shù)量的公平分布，但它不考慮分配過程中每個(gè)密鑰的工作負(fù)載?，F(xiàn)實(shí)世界的工作負(fù)載通常是傾斜的，很少有鍵比其他鍵更熱[30]。這種傾斜導(dǎo)致緩存服務(wù)器之間的負(fù)載不平衡。

緩存層中的負(fù)載不平衡可能會(huì)對(duì)整個(gè)應(yīng)用程序性能產(chǎn)生顯著影響。尤其是，它可能導(dǎo)致在接入頻率分布的尾部的操作延遲急劇增加[29]。此外，當(dāng)工作負(fù)載偏差增加時(shí)，平均吞吐量降低，平均延遲增加[15]。當(dāng)在依賴數(shù)據(jù)對(duì)象鏈中執(zhí)行操作時(shí)，實(shí)際工作負(fù)載的平均延遲和尾部延遲的這種增加是放大的[41]。一次Facebook頁面加載會(huì)在多輪數(shù)據(jù)獲取操作中檢索數(shù)百個(gè)對(duì)象[44，13]。最后，解決方案同樣會(huì)過度配置緩存層資源，以處理負(fù)載最重的緩存服務(wù)器所帶來的資源利用率最低的緩存服務(wù)器所帶來的影響。

為了解決負(fù)載不平衡問題，人們提出了多種方法，使用集中負(fù)載監(jiān)控[9，48]、服務(wù)器端負(fù)載監(jiān)控[29]或前端負(fù)載監(jiān)控[24]。Adya等人。[9] 提出將數(shù)據(jù)服務(wù)平面與控制平面分離的切片器?？刂破矫媸且粋€(gè)集中化的系統(tǒng)組件，它收集有關(guān)碎片訪問和服務(wù)器工作負(fù)載的元數(shù)據(jù)。它定期運(yùn)行一個(gè)優(yōu)化算法，該算法決定重新分配、重新分區(qū)或復(fù)制密鑰空間的片段，以實(shí)現(xiàn)更好的后端負(fù)載平衡。Hong等人。[29]使用分布式服務(wù)器端負(fù)載監(jiān)控來解決負(fù)載不平衡問題。每個(gè)后端服務(wù)器都獨(dú)立地跟蹤其熱鍵和取消決定，以便將其熱鍵的工作負(fù)載分配給其他后端服務(wù)器。[9，48]和[29]中的解決方案要求后端更改緩存的密鑰-服務(wù)器映射并將新映射公布到所有的前端服務(wù)器。Fan等人。[24]使用分布式前端負(fù)載監(jiān)控方法。這種方法表明，在前端服務(wù)器中添加一個(gè)小緩存對(duì)解決后端負(fù)載不平衡有很大的影響。在前端服務(wù)器上緩存重量級(jí)用戶可以減少緩存服務(wù)器提供的密鑰之間的偏差，從而實(shí)現(xiàn)更好的后端負(fù)載平衡。Fan等人。理論上通過分析和仿真表明，每個(gè)前端都有一個(gè)小的完美緩存，解決了后端負(fù)載不平衡的問題。然而，完美的緩存實(shí)際上很難實(shí)現(xiàn)。為了動(dòng)態(tài)地改變和發(fā)展工作負(fù)載，確定緩存大小和在前端實(shí)現(xiàn)接近每影響緩存的替換策略是一項(xiàng)挑戰(zhàn)。

在這篇文章中，我們提出了Cache-on-Track（CoT），它是一種分散的、彈性的、預(yù)測(cè)性強(qiáng)的前端服務(wù)器緩存。CoT pro提出了一個(gè)新的緩存替換策略，專門針對(duì)服務(wù)于傾斜工作負(fù)載的小型前端緩存。CoT使用一個(gè)小的前端緩存來解決后端負(fù)載不平衡的問題，如[24]中介紹的。然而，CoT并不認(rèn)為前端有完美的緩存。CoT使用節(jié)省空間的算法[43]來跟蹤top-k重?fù)羰?。跟蹤信息允許CoT從top-k跟蹤的近似鍵中緩存出準(zhǔn)確的top-C最熱鍵，以防止長(zhǎng)尾的冷鍵和噪聲鍵替換緩存中的熱鍵。CoT是分散的，因?yàn)槊總€(gè)前端獨(dú)立地根據(jù)在這個(gè)特定前端服務(wù)的密鑰訪問分配來確定其熱鍵集。這種低成本的CoT解決了后端負(fù)載不平衡的問題，沒有引入單一的故障點(diǎn)或瓶頸，這些通常都是集中解決方案帶來的。此外，這使得CoT可以擴(kuò)展到數(shù)千個(gè)前端服務(wù)器，這是社交網(wǎng)絡(luò)和現(xiàn)代web應(yīng)用程序的共同要求。CoT是彈性的，因?yàn)槊總€(gè)前端使用其本地負(fù)載信息來監(jiān)視其對(duì)后端負(fù)載不平衡的貢獻(xiàn)。每個(gè)前端彈性地調(diào)整其跟蹤器和緩存大小，以減少由這個(gè)前端引起的負(fù)載不平衡。在工作負(fù)載發(fā)生變化的情況下，CoT除了動(dòng)態(tài)調(diào)整跟蹤器和緩存大小之外，還動(dòng)態(tài)調(diào)整前端跟蹤器與緩存的比率，以消除任何后端負(fù)載不平衡。

在傳統(tǒng)的架構(gòu)中，內(nèi)存大小是靜態(tài)的，緩存算法努力實(shí)現(xiàn)所有可用資源的最佳利用。然而，在云環(huán)境中，理論上存在有限的內(nèi)存和處理資源，而云站姿遷移是一種常態(tài)，云最終用戶的目標(biāo)是實(shí)現(xiàn)其slo，同時(shí)減少所需的云資源，從而降低其貨幣部署成本。CoT的主要目標(biāo)是在每個(gè)前端減少必要的前端緩存大小，以消除服務(wù)器端負(fù)載不平衡。減少前端緩存大小對(duì)于以下方面至關(guān)重要：1）它降低了部署前端緩存的金錢成本。為此，我們引用大衛(wèi)•洛米特（David Lomet）最近的著作[40，39，38]中的話，他指出成本/性能通常比純粹的性能更重要：“這里的論點(diǎn)不是沒有足夠的主內(nèi)存來保存數(shù)據(jù)，而是有一種成本更低的數(shù)據(jù)管理方法?！薄?/p>

2） 在數(shù)據(jù)更新的情況下，當(dāng)需要數(shù)據(jù)一致性時(shí)，增加前端緩存大小會(huì)顯著增加數(shù)據(jù)一致性管理技術(shù)的成本。請(qǐng)注意，社交網(wǎng)絡(luò)和現(xiàn)代web應(yīng)用程序運(yùn)行在成千上萬的前端服務(wù)器上。增加前端緩存大小不僅會(huì)使部署更大緩存的成本乘以前端服務(wù)器的數(shù)量，但也增加了一致性管理管道中的一些成本，包括a）跟蹤不同前端服務(wù)器中的密鑰體現(xiàn)的成本，b）將更新傳播到前端服務(wù)器的網(wǎng)絡(luò)和處理成本。3） 由于工作負(fù)載是傾斜的，我們的經(jīng)驗(yàn)清楚地表明，添加更多前端緩存線的相對(duì)成本（以每個(gè)緩存線的平均緩存命中率和后端負(fù)載不平衡減少來衡量）隨著前端緩存大小的增加而急劇減少。

CoT的調(diào)整大小算法根據(jù)動(dòng)態(tài)工作負(fù)載的變化動(dòng)態(tài)地增加或減少前端分配的內(nèi)存。CoT的動(dòng)態(tài)調(diào)整大小算法在不同的云設(shè)置中很有價(jià)值

1） 所有前端服務(wù)器部署在同一個(gè)數(shù)據(jù)中心，并獲得相同的動(dòng)態(tài)演進(jìn)工作負(fù)載分布；2）所有前端服務(wù)器部署在同一個(gè)數(shù)據(jù)中心，但獲得不同的動(dòng)態(tài)演進(jìn)工作負(fù)載分布，
最終3）前端服務(wù)器部署在不同的邊緣數(shù)據(jù)中心，并獲得不同的動(dòng)態(tài)變化的工作負(fù)載分布。特別是，CoT旨在從每個(gè)單獨(dú)的前端服務(wù)器的角度捕捉本地趨勢(shì)。在社交網(wǎng)絡(luò)應(yīng)用程序中，服務(wù)于不同地理區(qū)域的前端服務(wù)器可能會(huì)經(jīng)歷不同的密鑰訪問分布和不同的本地趨勢(shì)（例如，邁阿密與紐約）。類似地，在大型數(shù)據(jù)處理管道中，幾個(gè)應(yīng)用程序部署在共享緩存層的頂部。每個(gè)應(yīng)用程序可能對(duì)不同的數(shù)據(jù)分區(qū)感興趣，因此體驗(yàn)不同的密鑰訪問分布和本地趨勢(shì)。CoT在前端服務(wù)器上運(yùn)行的是細(xì)粒度密鑰級(jí)別，而Slicer[9]這樣的解決方案在緩存服務(wù)器上運(yùn)行的是較粗的細(xì)粒度切片或碎片。服務(wù)器端解決方案是對(duì)CoT的補(bǔ)充。雖然捕獲本地趨勢(shì)可以減輕緩存服務(wù)器之間的負(fù)載并減少負(fù)載不平衡，但其他因素可能會(huì)導(dǎo)致負(fù)載不平衡，因此使用服務(wù)器端負(fù)載平衡（例如切片器）可能仍然是有益的。

我們?cè)诒疚闹械呢暙I(xiàn)總結(jié)如下。

•緩存在軌（CoT）是一種分散的、有彈性的，

以及預(yù)測(cè)性的前端緩存框架

減少后端負(fù)載不平衡并改進(jìn)

整體表現(xiàn)。

•

CoT動(dòng)態(tài)地最小化所需的前端緩存大小，以實(shí)現(xiàn)后端負(fù)載平衡。與其他替代政策相比，CoT的內(nèi)置彈性是一個(gè)關(guān)鍵的新優(yōu)勢(shì)。

•

廣泛的實(shí)驗(yàn)研究，將CoT的替代政策與傳統(tǒng)的以及最先進(jìn)的替代政策，即LFU、LRU、ARC和LRU-2進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，與其他替換策略相比，CoT在不同工作負(fù)載下實(shí)現(xiàn)了服務(wù)器大小的負(fù)載平衡，前端緩存減少了50%到93.75%。

•實(shí)驗(yàn)研究表明

成功地自動(dòng)配置跟蹤程序和緩存

大小以實(shí)現(xiàn)后端負(fù)載平衡。

•在我們的實(shí)驗(yàn)中，我們發(fā)現(xiàn)

YCSB的[19]加密工作負(fù)載發(fā)生器-

阿托爾。這個(gè)生成器生成的工作負(fù)載

明顯沒有承諾的那么偏斜

壓縮分布。

論文的其余部分安排如下。第二節(jié)介紹了系統(tǒng)和數(shù)據(jù)模型。在第3節(jié)中，我們通過介紹在前端使用LRU、LFU、ARC和LRU-k緩存的主要優(yōu)點(diǎn)和局限性來激勵(lì)CoT。我們?cè)诘谒墓?jié)介紹了嬰兒床的細(xì)節(jié)。第五節(jié)對(duì)膠輥的性能和運(yùn)行費(fèi)用進(jìn)行了評(píng)估，第六節(jié)對(duì)相關(guān)工作進(jìn)行了討論，第七節(jié)對(duì)論文進(jìn)行了總結(jié)。

論文PDF版下載：https://arxiv.org/pdf/2006.08067