IEEE TSC'22：邊緣環境下基于糾刪碼的數據存儲
邊緣計算是一種延伸云計算的新型分布式計算范式，能夠將存儲和計算能力下沉至網絡邊緣，從而為數據的高效實時處理提供有力支撐。邊緣存儲系統與傳統云存儲系統的差異主要表現在以下三個方面：1）邊緣存儲資源有限且昂貴；2）用戶對數據的訪問具有地理范圍約束；3）數據的訪問請求具有低延遲約束。傳統存儲系統中的數據放置策略主要采用多副本的方案，即將數據以多副本的形式存儲于各個節點。這種方法無法適應邊緣存儲系統的特點。同時，當數據規模較大時，該方案會造成邊緣存儲資源的巨大浪費。為此，我們首次提出將糾刪碼技術引入邊緣環境，以實現在保證低數據檢索延遲的同時降低數據存儲量。然而，糾刪碼技術的引入也給邊緣存儲系統帶來了新的挑戰。區別于云存儲系統，邊緣節點之間的互聯結構往往不是任意可達的，并且邊緣網絡中的數據傳輸相比于云數據中心網絡具有較高的通信開銷，邊緣存儲系統中編碼數據的放置策略需要重新設計。針對上述問題，本文提出了兩種拓撲感知的編碼數據放置優化算法，一種是基于整數線性規劃的最優方法EC-EDP-O，一種是基于投票策略的近似算法EC-EDP-V。我們在真實數據集上進行了大量實驗，實驗結果表明我們提出的方法平均可以節省68.58%的存儲空間，在大規模場景下空間節省可達81.16%。
該研究成果“Cost-Effective Data Placement in Edge Storage Systems with Erasure Code “已被 IEEE Transactions on Services Computing (TSC) 期刊錄用。TSC為計算機學會推薦國際學術期刊軟件工程領域CCF B類期刊，影響因子為6.582。
- 論文鏈接：https://doi.org/10.1109/TSC.2022.3152849
背景與動機
近年來邊緣計算在快速發展，它將計算和存儲資源下放至距離數據源頭更近的網絡邊緣，從而具有低延遲、高安全和本地自治的數據處理優勢。為了給用戶提供低延遲的服務，服務提供商們傾向于將熱門數據存儲在距離用戶更近的邊緣服務器。與此同時，移動和物聯網設備所產生的數據也傾向于存儲在本地邊緣服務器來保證實時的處理與共享。
傳統的基于多副本的數據放置策略旨在追求數據訪問延遲最小化。然而這些策略往往忽略了邊緣節點因多副本帶來的巨大存儲資源浪費。受限于邊緣服務器的物理大小，邊緣存儲資源是極度受限的。隨著數據存儲需求的日益增多，存儲資源的限制給邊緣存儲系統的性能限定了上界。因此，為了提高邊緣存儲資源利用率，本文創新性地引入了糾刪碼技術。糾刪碼技術將原始數據進行切分并以數據塊的形式在不同的節點進行存儲，以大幅降低數據存儲量。與此同時，糾刪碼技術可以通過不同的編碼和恢復機制來實現數據存儲的高可靠性。然而，邊緣存儲系統與傳統云存儲系統的根本性區別給糾刪碼技術的引入帶來了新的挑戰。首先，云存儲系統中節點通過高速的數據中心網絡進行連接，并且節點之間是任意可達的，因此糾刪碼中的編碼數據塊可以在云節點中任意放置。然而在邊緣存儲系統中，邊緣節點的覆蓋范圍是有限的，用戶往往只能通過無線網絡從覆蓋他的邊緣節點上獲取數據，這使得編碼數據在邊緣節點上的放置策略需要被重新設計。其次，邊緣環境下用戶對于數據的檢索延遲往往具有較高要求，且數據在邊緣網絡中的多跳傳輸具有較高的通信開銷，這使得據放置策略在實現低存儲資源占用的同時還需要保證較低的數據檢索延遲。
圖1 不同數據放置策略的存儲成本比較
在基于糾刪碼的邊緣數據存儲系統中，不同的數據放置策略和編碼方案會給系統帶來不同的存儲開銷，以圖1為例， v 1 至 v 10代表該存儲系統中的10個邊緣節點，假設這里用戶對數據的訪問延遲約束為2跳以內，如果以多副本策略進行數據放置（圖1（a）），要使10個邊緣節點所服務的任何用戶都能在2跳以內訪問到該數據，那么必須分別在 v 4 和 v 9 （或者 v 5 和 v 8 ）上存儲該數據，即所需要的存儲成本為1*2=2。方案（b）-（d）表示了不同的糾刪碼編碼方案。以圖1（b）為例，如果編碼數據塊為原數據塊大小的一半(EC(2,1))，即當用戶需要訪問該數據時，必須同時在2跳內檢索到兩塊編碼數據塊。為使得每個節點都可以滿足用戶的數據請求服務，必須在 v 4 、 v 5 和 v 8這三個邊緣節點上存儲數據塊，所帶來的存儲成本為0.5*3=1.5。同理，方案（c）和方案（d）的存儲成本為別分1.33和2。給定一個邊緣存儲系統，通常會存在大量可行的EC-EDP（erasure code-based edge data placement）解決方案。結合不同的數據編碼和放置策略，這些解決方案會產生不同的存儲成本。同時，在真實的EC-EDP場景中，邊緣服務器的數量可能很大，網絡拓撲可能也更復雜。在這種情況下實現個以最小存儲成本為邊緣存儲系統中的所有用戶提供低延遲數據訪問服務的方案是極具挑戰性的。
設計與實現
基于上述分析，我們研究了基于糾刪碼的邊緣數據放置問題。首先對該問題進行數學建模與抽象，構建了一個以最小化存儲成本為目標，以邊緣服務器覆蓋范圍、編碼數據可靠性和數據檢索延遲為約束的整數線性規劃模型。首先，我們從經典的NP難問題——最小支配集（MDS）問題著手，通過規約理論證明了EC-EDP問題是一個NP難問題。然后，我們給出了一種最優方法，即采用整數規劃求解器CPLEX設計的最優算法ED-EDP-O；針對EC-EDP-O方法在大規模邊緣場景下的計算開銷大的問題，我們進一步設計了一種可應用于大規模場景快速求解的ED-EDP-V近似算法，ED-EDP-V算法的設計靈感來源于機器學習中的投票理論，其核心思路是以每一個邊緣節點能檢索出完整數據所需要的數據塊個數作為該節點的投票權重，在每輪迭代中邊緣節點分別為周圍的節點進行投票，并選擇出能夠產生最大存儲收益的邊緣節點作為數據塊的下一個存儲節點，每輪迭代進行后不斷地更新邊緣節點的投票權重，反復進行上述過程以實現問題的最終求解。最后，為了驗證EC-EDP-V近似算法與最優解之間的差距，我們從理論上分析了其計算復雜度為，并且證明了其具有的近似比。
圖2 小規模實驗下不同方法的存儲成本
圖3 小規模實驗下不同方法的時間開銷
我們在真實數據集上對提出的兩種方法分別進行了小規模和大規模實驗。小規模的實驗的存儲成本和時間開銷分別如圖2和圖3所示。EC-EDP-O的存儲成本最小。同時，EC-EDP-O的高計算開銷也證明了這是一個NP難問題。大規模實驗結果如圖4和圖5所示。在具有250個邊緣節點的場景下求解該問題只需要40ms的計算開銷，證明了EC-EDP-V方法的有效性和高效率。綜上所述，我們提出的兩種邊緣數據放置方法能夠在保證低時間開銷的同時，有效降低數據存儲量。
圖4 大規模實驗下不同方法的存儲成本
圖5 大規模實驗下不同方法的時間開銷
