SP-Cache: 基於選擇性熱點數據分割策略，實現分散式內存系統負載均衡
編者按：在Alluxio開源社區，越來越多高校研究人員使用Alluxio作為研究載體。本專欄將介紹一系列基於Alluxio的前沿研究工作。該系列的第一篇博客邀請到了香港科技大學余英豪博士撰寫介紹了他基於Alluxio的研究成果。本文不僅有技術介紹，還會分享他在開源軟體上開展研究的心得與經驗。
本文作者：余英豪
作者簡介：香港科技大學電子與計算機工程系博士研究生，專註於分散式內存系統的性能優化
導師：王威教授，Khaled Ben Letaief教授
特別鳴謝：感謝Alluxio PMC范斌博士以及南京大學顧榮老師的校閱、指正
隨著現代數據中心網路的大幅提速，傳統的HDFS提供的基於硬碟存儲的數據本地性變得越來越不重要 （鏈接1）。而同時對象存儲（Object Store，包括Amazon S3 和 OpenStack Swift等）作為更便宜和更容易水平擴展的數據存儲層系統，在廣泛發展的眾多大數據應用中越來越受到歡迎。由於硬碟的I/O速度仍遠低於內存讀寫，因此在大數據應用和對象存儲之間部署一個以Alluxio為代表的內存文件緩存層來緩存數據，可以有效提升整體的讀寫效率，並彌補網路帶寬受限場景下存儲與計算分離帶來的數據本地性問題。為了進一步提升內存緩存層的整體性能，本文揭示了內存緩存層中由於文件熱度不均導致的負載失衡的嚴重風險，並提出了一種選擇性熱點文件分割的策略來保障系統負載均衡。
常用鏈接
- Alluxio項目官網
- Alluxio Inc網站
- Alluxio在各大廠用例
- 關注Alluxio微信公眾號：Alluxio_China
1、負載均衡
研究表明，數據中心裡不同數據的訪問有顯著的熱度差異。當這些數據被緩存在內存層中時，極容易產生負載失衡的問題：一部分數據被高頻率地訪問，形成局部熱點（hot spot）。熱點機器的網路擁塞往往會成為數據讀寫的瓶頸；而另一部分訪問頻率較低的數據因為佔用緩存資源，導致資源不能更加優化地分配給熱點數據，進而影響內存資源的使用效率。
為了深度觀察負載失衡在生產環境中的嚴重程度，我們分析了Yahoo! 公開的一個生產集群的trace（鏈接2）。在這個涉及上千台機器、跨度數月的數據訪問日誌中，我們統計了涵蓋其中數百萬文件的讀寫頻率及其文件大小。我們有兩個發現，總結如下圖。
- 數據熱度的差異性十分顯著。圖2中的藍色柱子顯示了文件訪問頻次的分布，我們發現只有2%的文件被頻繁的訪問（總次數超過100次），而77%的文件則是冷數據（訪問次數少於10次）。
- 熱點數據往往是大文件。圖2中的黃色柱子顯示了不同熱度區間文件的平均大小。例如，訪問次數超過100次的文件，平均大小是729MB， 將近二十倍於「冷文件」的平均大小。
以上兩點實際情況給系統造成了嚴重的負載失衡風險：存儲熱點文件的機器將被頻繁地訪問，且每次訪問都需要傳輸大量的數據（大文件），造成網路擁塞，使得讀寫速度變慢。因此，負載均衡是影響分散式內存系統性能的關鍵要素。
2、現有策略的問題
現有的用於實現內存系統負載均衡的演算法大致可分為兩類。
- 多副本熱點文件，例如Alluxio 1.x版本中提供的被動複製機制，以及選擇性地主動複製熱數據（selectivereplication, 鏈接3）。通過多份副本分流，實現均衡負載。
- 使用糾刪碼（erasure coding, 鏈接 4）將大文件編碼為若干小數據塊（包括信息塊和校驗塊），並將它們存儲於不同的機器上。對大文件的讀取任務將被分流到這些小數據塊中，實現負載均衡。
然而，我們發現現有的這兩類演算法都不能有效地解決實際問題。一方面，複製熱點文件（往往是大文件）會造成大量的內存冗餘，使內存的整體命中率降低，進而降低讀寫速度；另一方面，若使用糾刪碼，每次文件的讀/寫都需要解碼/編碼操作，拖慢對內存的讀寫速度並增加CPU的負擔（經我們測量，解碼時間可佔總的讀文件時間的30%）。
3、選擇性分割
為了減少內存的冗餘，同時避免編解碼的計算負擔，我們設計了一種選擇性文件分割的演算法來實現負載均衡。
3.1 文件分割
文件分割的基本思路是將大的熱點文件分割成小塊（僅分割，無編碼），然後將這些小塊均勻分散存儲在集群中。圖3顯示的這個示例中，文件A 是一個熱點文件；它被分割為四個小塊，放在四台機器上。這樣做有三個好處。
1. 熱點文件的負載被分流至多台機器，可以均衡負載，同時利用並行I/O可以降低讀延遲；
2. 無需任何編解碼操作；
3. 沒有任何內存冗餘。
但是，文件並不合適被無限地分割成任意粒度的小塊，其中一個重要的原因是straggler（拖後腿者）節點的存在。我們將集群當前狀態下響應慢的機器稱為straggler，它們的產生原因非常複雜且是動態變化的（鏈接5）。文件被分割後，由於每次文件讀取需要並發地讀所有的小塊，總的讀延遲受限於最慢獲取到的小塊。因此，一旦有任何一台存放小塊的機器是straggler，文件讀取就會被拖慢。由於straggler的發生難以提前預知和控制，我們只能儘可能降低分割演算法被straggler影響的概率，即去控制分割小塊的數目。為此，我們提出了選擇性文件分割演算法。
3.2 選擇性文件分割
顧名思義，選擇性文件分割就是優先選擇內存中被頻繁訪問的、大的熱點文件進行分割，而盡量減少對小文件、冷文件的分割。這樣，一方面熱點文件可以被充分分割而達到均衡負載的目的，另一方面straggler的影響被儘可能地降低了。
為了找到每個文件各自的最佳分割數量，我們將整個分散式內存系統簡化為一個fork-join queue模型。在這個模型中，每一個文件讀請求被分叉（fork）為多個子任務，分發至儲存了該文件分割小塊的內存節點，最終所有的子任務的讀取結果被合併（join）為原文件，返回至文件請求源。我們將測量、估計出來的文件大小、被訪問頻率等信息加入模型後，計算出每個文件的最佳分割數量，使得熱點文件的負載可以恰好被充分分散，同時straggler的影響被儘可能限制。
3.3 性能測試
我們在Alluxio中實現了選擇性文件分割的演算法（SP-Cache），並同其他兩種現有演算法，選擇性文件複製（selective replication）和糾刪碼（EC-Cache），進行了性能比較。
- 圖5展示了採用三種不同負載均衡演算法後，一個30節點的Alluxio集群中每個節點的負載。可以看出，選擇性文件分割（SP-Cache）均衡負載的效果最佳，節點之間的負載差別最小。
- 由於選擇性文件分割演算法沒有任何內存冗餘以及編解碼的時間開銷，相比其他負載均衡演算法，可以大幅降低讀延遲。如圖6所示，與複製演算法（以及糾刪碼演算法）相比，選擇性文件分割演算法可以降低平均讀延遲 29 ? 50% (40 ?70%)，降低尾部讀延遲（95 百分位）22 ? 55% (33 ? 60%)。
4、經驗分享
最後，我們分享總結一些在Alluxio上開展科研項目的工程經驗。 得益於Alluxio開源項目成熟的模塊化設計，我們在開發實現我們的演算法的過程中，能夠在原版本Alluxio的框架和結構不變的基礎之上，僅對幾個可插拔的模塊進行集中改動。具體而言，在原版本Alluxio的基礎上，我們主要實現了三個模塊。
- 在Alluxio master中實現一個SP-Master 模塊，負責管理所有與選擇性分割演算法有關的元數據，例如每個文件有幾個分割數，每個分割小塊分別存在哪些Alluxio worker上等；同時，SP-Master會根據過去一段時間的文件訪問熱度，定期計算並更新每個文件的最優分割值；
- 在原來的Alluxio client之外封裝一個SP-Client。來自上層應用的文件讀寫請求會先經過SP-Client。例如，對於讀請求，SP-Client先向SP-Master查詢被訪問文件各個分割小塊所在的worker地址，然後再通過Alluxio client 讀取所有小塊，最後由SP-Client將讀來的數據按照相對順序結合為原來的文件，返回上層應用；
- 由於在很多現實應用中文件的訪問熱度會隨著時間而改變，因此我們實現了一個定期重新分割文件的模塊SP-Repartitioner。在每個分割周期到來時，SP-Repartitioner會首先向SP-Master查詢更新後的文件最優分割值，然後在多個Alluxio worker上並行地對內存中的文件進行重分割。
Alluxio的源代碼結構組織合理並且實現思路清晰，這有助於我們快速鎖定需要修改的模塊，以及我們自己實現的模塊應該如何添加到Alluxio源碼結構中，例如，SP-Master需要在Alluxio master被初始化時即被創建，因此我們把它放在alluxio.master.file這個package中; 而SP-Client是一個獨立的package, 只是在其中調用了部分Alluxio client的介面；另外，關於SP-Master和SP-Client之間的通信，我們可以直接藉助Alluxio原有的thrift框架創建所需要的通信介面。
總地來說，我們的經驗是，在Alluxio平台上開展科研項目，第一步要弄清楚源代碼中每一個模塊的功能是什麼，對Alluxio源代碼本身有全局的了解，然後再根據自己的需求去精讀、修改對應的模塊，這樣可以節省不少看代碼的時間；另外一個建議，研究者最好將自己的改動設計成可插拔的子模塊，這樣可以方便源碼維護並與原版本的Alluxio進行性能對比。
關於本文的更多細節，敬請閱讀我們發表在ACM/IEEE SC 2018會議上的學術論文：
https://dl.acm.org/citation.cfm?id=3291658，或者聯繫本文作者[email protected]。
SP-Cache的源代碼已開源：https://github.com/yhust/SP-Cache。
推薦閱讀：
