【ELT.ZIP】OpenHarmony啃論文俱樂部——雲端計算資料壓縮方案

語言: CN / TW / HK
時間 2022-05-12 14:04:44
  • 本文出自ELT.ZIP團隊，ELT<=>Elite(精英)，.ZIP為壓縮格式，ELT.ZIP即壓縮精英。
  • 成員：
    • 上海工程技術大學大二在校生
    • 合肥師範學院大二在校生
    • 清華大學大二在校生
    • 成都資訊工程大學大一在校生
    • 黑龍江大學大一在校生
    • 山東大學大三在校生
    • 華南理工大學大一在校生
  • 我們是來自7個地方的同學，我們在OpenHarmony成長計劃啃論文俱樂部裡，與華為、軟通動力、潤和軟體、拓維資訊、深開鴻等公司一起，學習和研究作業系統技術...

@[toc]

【往期回顧】

 ① 2月23日 《老子到此一遊系列》之 老子為什麼是老子 —— ++綜述視角解讀壓縮編碼++  ② 3月11日 《老子到此一遊系列》之 老子帶你看懂這些風景 —— ++多維探祕通用無失真壓縮++  ③ 3月25日 《老子到此一遊系列》之 老子見證的滄海桑田 —— ++輕翻那些永垂不朽的詩篇++  ④ 4月4日 《老子到此一遊系列》之 老子游玩了一條河 —— ++細數生活中的壓縮點滴++  ⑤ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——一文穿透多媒體過往前沿++  ⑥ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——這些小風景你不應該錯過++  ⑦ 4月18日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——淺析稀疏表示醫學影象++  ⑧ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——計算機視覺資料壓縮應用++  ⑨ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——點燃主快取壓縮技術火花++  ⑩ 4月29日 ++【ELT.ZIP】OpenHarmony啃論文俱樂部——即刻征服3D網格壓縮編碼++

【本期看點】

  • Hadoop和Spark框架的效能優化系統
  • 雲端計算重複資料刪除技術降低冗餘度
  • 壓縮框架Ares如何統一不同演算法
  • 線上資料壓縮“搖擺門趨勢”
  • 揭祕新型移動雲端儲存SDM

【技術DNA】

file

【智慧場景】

前言

  • 近年來，相機、衛xing、地震監測等感測裝置產生了大量的流資料，雲端計算技術使這些流資料的儲存、訪問和管理變得更加容易，也降低了成本。其中，雲端儲存系統成為在各種雲伺服器上儲存資料塊的一種有前途的技術，其主要機制之一是資料複製。資料複製的目標是解決雲端儲存的可用性、可靠性、安全性、頻寬和資料訪問的響應時間，從而使資料密集型專案能夠實現更優越的效能。然而，既然複製，就免不了會產生過多的重複副本造成資源浪費。因此，便產生了一種通過移除重複副本來減小云儲存系統中資料佔用的大小，實現資料壓縮、避免資源浪費的重複資料刪除技術。
  • 以一種典型的傳統分類方式來看，可以將此重複資料刪除技術分為delta-based和hash-based兩類。本著相同的目標，前者基於相似性的消除，後者基於加密函式而發揮作用。
  • 而在另一種分類方式中，可以將此重複資料刪除技術分為基於伺服器和基於客戶端兩類。前者中，消除冗餘資料的操作是在伺服器接收到資料後完成的，而後者則在傳送資料之前就先在客戶端檢查資料的重複性。

後文將對以上內容一一解析，不過開始之前，我們還是先了解一些雲端計算的周邊內容。

雲端計算

產生背景

  • 雲端儲存數字資料量的不斷增加 ，需要更多的儲存空間，高效的技術 ，處理這些資料。 file

  • 那麼何為雲端計算？是如上圖一般把網線接到雲彩上進行計算嗎？當然不是，這是一種形象的比喻，雲端計算提供了一種新的網際網路技術方式，利用網際網路和中央遠端伺服器管理資源和應用程式。許多終端使用者以最低的成本使用這一創新，並且無需安裝就可以訪問應用程式。

  1. 主要優點：
  • 可容錯
  • 處理速度快
  • 儲存容量大
  • 頻寬寬
  • 允許使用 Internet 訪問遠端資訊和檔案

  1. 存在問題： 雲服務中最重要、最典型的是資訊儲存服務。

  2. 常見的雲端儲存供應商： Dropbox ，谷歌公司的Google Drive、微軟公司的 OneDrive 和亞馬遜公司的 AWS 等。 file

  • 雲端計算和大資料是近六七年來大熱的兩個概念，很多時候，二者都是被繫結在一起談論的。
  • 大資料就是通過蒐集海量的資料對其進行分析和處理，發現隱藏在這些資料背後的潛在聯絡，洞察內在過程，進而使這些資料轉化或推導出具有更多價值的資訊，最終為使用者的決策提供幫助。放到日常工作生活中的典型表現就是“喜歡看什麼，就會推什麼”：當我們刷一些娛樂類或者新聞類的app時，看到感興趣的內容就免不了會駐足多停留一段時間，可能還會直接去搜相關的話題，這時大資料就已經完成了標記、為你的ID打上了相應的標籤。基於內容相關性的頻次或後臺的定位資訊等，標籤也會不盡相同。儘管覺得自己淨如白紙，但在平臺的全閉環下，大資料總是能精確地捕捉並震撼到我們。

當今時代的人們尚無隱私可言。技術是中立的，益害與否取決於被如何使用，地圖導航類app中基於大資料的實時交通流量分析大大方便了出行。鑑於近兩年來不斷髮生的一些事件，隱私防護也得到了有關部門的重視。因此，許多app設定中相繼提供了關閉“個性化”一類的入口，可在一定程度上緩解大資料對個人生活的侵擾。

  • 雲端計算本質上是分散式計算的一種，通過對任務的分發，實現多端平行計算，最終再進行計算結果的合併。它提供了計算資源的虛擬化池，儲存、應用、記憶體、處理能力和服務都是在使用者需要時可以用來請求這些資源的例項。其中，雲服務通常分為平臺即服務（PaaS）、軟體即服務（SaaS）和基礎設施即服務（IaaS）三種模式，三者的主要區別就是提供服務的方式不同，需要使用者根據實際需要進行選擇匹配。此外，基於雲端計算的思路，還衍生出了霧計算、邊緣計算、移動邊緣計算（MEC）和移動雲端計算（MCC）。

2015年迅雷曾推出的“賺錢寶”就是一種基於雲端計算的產品。使用者只需連線家中路由器，就可以將空閒頻寬收集處理，轉變為可供網際網路服務商大規模使用的創新型CDN，最終實現幫助普通使用者將空閒資源變現。

所以我們說雲端計算和大資料之間的聯絡較緊密，雲端計算作為計算資源的底層，支撐著上層大資料的高效處理，資料中心的壯大又為雲端計算的發展提供了保障。

雲端儲存

雲端儲存是一種有用的移動邊緣計算(M E C)裝置，其特點是儲存空間有限。這些資料或日誌資料可以在需要時被儲存和訪問到雲端儲存服務中。為了提高M E C裝置上的雲端儲存服務體驗，可以將多個雲端儲存服務合併成一個統一的雲端儲存在雲端儲存中，在處理大量資料時，無法避免重複。儘管雲端儲存空間巨大，這種複製極大地浪費了網路資源，消耗了大量電能，並使資料管理變得複雜。重複資料刪除可以節省大量空間和成本，備份應用可以減少高達 90-95%的儲存需求，標準檔案系統可以減少高達 68%的儲存需求。 資料重複刪除和資料壓縮是在雲中優化儲存的可用技術中使用的最突出的技術。

重複資料刪除技術

  • 隨機複製作為一種流行的複製方案，已廣泛用於雲端儲存系統，如Hadoop分散式檔案系統（HDFS）、RAMCloud、Google檔案系統（GFS）和微軟Azure等，使用隨機複製從不同機房隨機選擇的三臺伺服器中複製資料，從而防止單個叢集中的資料丟失。然而，三方隨機複製不能很好地應對機器故障，若三個節點的隨機組合同時出現錯誤，就會造成資料丟失。
  • 為了解決以上問題，便提出了Copyset複製和分層複製兩種方案。但又出現了新的問題：它們都沒有試圖降低由於複製而造成的儲存成本和頻寬成本。儘管後續又提出了更多相關的複製方案，但仍然存在著同樣的問題。
  • 於是，有學者設計了一種叫做流行感知的多故障彈性和經濟有效的複製方案（PMCR）的方案。它比之前的複製方案都有優勢，且同時具有以下特點：
  1. 可以處理相關或不相關的機器故障
  2. 壓縮那些很少使用的冷門資料的副本
  3. 降低了儲存和頻寬成本
  4. 不會顯著影響資料永續性、資料可用性和資料請求的延遲

SC、DC壓縮

  • 由於PMCR方案的操作是一整套流程，我們在此只關注其中壓縮資料降低冗餘度的部分。
  • SC全稱Similarity Compression，是依據資料相似性壓縮的一種方法；DC全稱Delta Compression，意即增量壓縮。PMCR使用SC壓縮讀密集型資料，使用DC壓縮寫密集型資料。SC刪除檔案或檔案中相似的塊，檔案請求使用者在接收到壓縮檔案後，可再恢復已刪除的資料塊；DC儲存檔案的副本和與此檔案相似的其他檔案的不同部分，以上將會被傳輸給檔案請求使用者。而當檔案更新時，只需將更新後的部分同步到副本節點即可。

相似性壓縮（SC）：

  • 進行SC時，相似的塊被分組在一起，一定數量相似的小塊形成一個大塊。然後，刪除重複的塊或接近重複的塊到一個塊。在PMCR中，當壓縮讀密集型資料時，對於每一組相似的塊，只需儲存第一個塊即可，剩下的冗餘塊可刪除；對於不同資料物件之間的冗餘塊，也可消除，方式大體分為檔案內壓縮和檔案間壓縮： file file

增量壓縮（DC）：

  • 如圖，B塊和B'塊都是相似的塊，它們之間的差異用橙色標記出，此時，便可用DC儲存橙色區域。當塊B或塊B'被更新時，只需將更新的部分而非整個塊傳送到複製伺服器即可，然後，副本伺服器再更新相應的部分。要將資料傳送給使用者，只需傳輸儲存的不同部分和B塊的完整部分。 file

DSHA演算法

  • 現有系統使用（任何型別的）加密雜湊演算法(如 MD5 或 Secure 雜湊演算法)，生成雜湊值，重複資料刪除這些演算法產生固定長度的 128 位或 160 位分別作為輸出以識別複製的存在。同時用一個額外的記憶體空間儲存雜湊值。
  • 本文提出了一種高效的分散式儲存雜湊演算法(Distributed Storage Hash Algorithm, DSHA)，以減少用於識別和丟棄冗餘資料的雜湊值所佔用的記憶體空間。

結論：實驗分析表明，該策略降低了雜湊值的記憶體利用率，提高了資料讀寫效能。

SDM技術

  • SDM是一種針對移動裝置的智慧重複資料刪除系統，提高了雲端儲存作為移動裝置上的儲存解決方案的可行性。SDM旨在利用多核技術 在現代移動處理器上的架構。為了減少重複資料刪除過程的時間，針對每種檔案型別的最佳重複資料刪除方法，而不依賴於針對每種檔案型別的任何配置。由於其設計，學習系統不存在雜湊不相容性。

移動裝置和雲端儲存服務的固有限制：

  1. 移動裝置的效能限制 移動裝置的處理功率和電源受到限制。
  2. 有限的儲存容量 由於其外形因素，也很難在移動裝置中安裝高容量的儲存空間。雲端儲存供應商提供的免費儲存容量 往往很小，升級需支付額外費用。
  3. 網路頻寬 網路頻寬對於訪問雲端儲存至關重要。遺憾的是，網路頻寬通常被限制在免費儲存上，雲端儲存服務的頻寬是在活動使用者的數量之間劃分的，會導致更長的訪問時間，在大多數在某些情況下，這將導致雲端儲存服務的效能低於客戶的網路效能。
  4. 價格昂貴的無線網路收費
  5. 有限網路覆蓋範圍 網路覆蓋對移動使用者來說可能是一個問題。當用戶超出網路覆蓋範圍時，所有的網路活動都將是已停止，這意味著沒有云儲存服務。

系統架構

  • 我們建議使用智慧重複資料刪除技術進行移動雲端儲存(SDM)。SDM在檔案級和塊級使用多級重複資料刪除方法，這些方法由學習系統整合（學習系統選擇最佳的重複資料消除 方法來實現最佳的資料減少和能量消耗。此外，我們還使用雜湊表和一個bloom過濾器來進行本地搜尋並新增並行化來提高應用程式的效能。整個系統如圖所示。整個過程是可逆的，因為重複資料刪除是一個無失真壓縮的操作。 file

  • 檔案級重複資料刪除 在檔案級別上，重複資料刪除可以通過比較整個檔案來進行操作。由於它只將一個雜湊值與另一個檔案雜湊值進行比較，因此該程序比其他方法更快。但是，當檔案的一部分發生更改時，整個雜湊值也會發生更改。這就降低了檔案級重複資料刪除的效能。

  • 塊級重複資料刪除 當在塊級別執行重複資料刪除時，處理的檔案被分割為多個塊。每個塊的處理與檔案級重複資料刪除中的檔案相同。塊的大小可以是固定大小的或可變大小的。 file 塊級變化不會影響其他塊的雜湊值，但是，在一個塊部分位元組變化上就會改變多個塊的雜湊值。可變大小的塊或內容定義的分塊通過使用固定的分塊偏移量來分割一個檔案來解決這個問題。固定的分塊偏移量可以通過使用Rabin滾動雜湊找到。Rabin滾動雜湊使用多項式和一個滑動視窗來進行雜湊。為了找到分塊偏移量，我們滑動和雜湊視窗，直到雜湊匹配一個預定義的值。

應用場景

  1. 客戶端API 該方案提供了客戶端與儲存伺服器之間良好的介面。通過選擇合適的儲存節點， 可以降低 CPU 負載。
System.out.println();
jLabel3.setText(digits+outputString1);
Class.forname("com.mysql.jdbc.Driver");
con = DriverManager.getConnection("jdbc:mysql://localhost:3306/javamysql", "root", "root");
String HashValue = digits + outputString1;
String status = null;
int result, tab = 0;

效能測試資料：

  • 安卓的一個原型實現上的實現：
  1. 僅限檔案級重複資料刪除的系統(FDS)
  2. 僅限塊級重複資料刪除的系統(BDS)
  3. 針對移動裝置或SDM的智慧重複資料刪除
  4. 預配置的重複資料刪除系統(PCDS) file
  5. 旋轉重複資料刪除系統(RADS) RADS的工作原理是使用重複資料消除比率來確定每種檔案型別應該使用哪種重複資料消除方法。如果沒有達到該檔案型別 的目標重複資料刪除比率，則系統將選擇另一種重複資料刪除方法。對於每種檔案型別，重複資料刪除比率通過將重複資料刪除檔案大小除以檔案大小來計算。 file

測試結果： 演示不同的重複資料刪除系統在處理未知檔案型別時的效能： file 總的來說，SDM比其他系統表現得更好，特別是在未知的檔案型別上，因為我們的系統不需要對不同的檔案型別進行任 何特定的配置。對於大多數情況下檔案和塊級之間的重複資料刪除吞吐量，以及接近塊級重複資料刪除精度的重複資料刪 除精度，與其他系統相比，我們的系統可以使雲端儲存作為移動裝置的儲存解決方案更加可行。

Ares資料壓縮框架

介紹

  • 現代應用中的資料爆炸現象給儲存系統帶來了巨大的壓力，因此開發者使用資料壓縮技術來解決這個問題。但是，在考慮輸入資料型別和格式時，每個壓縮庫都表現出不同的優勢和劣勢。所以有相關學者提出了Ares，一個智慧、自適應和靈活的模組化壓縮框架，可以根據工作負載的型別為給定的輸入資料動態選擇壓縮庫，併為使用者提供適當的基礎設施來微調所選的庫。Ares是一個模組化框架，它統一了多個壓縮庫，同時允許使用者新增更多壓縮庫。同時，Ares也是一個統一的壓縮引擎，它抽象了每個工作負載使用不同壓縮庫的複雜性。
  • 在科學和雲端計算領域的實際運用中，Ares的執行速度相比其他解決方案快了 2-6 倍，而且附加資料分析的成本較低。與完全沒有壓縮的基線相比，速度快了 10 倍。

面臨的問題

  • 我們知道，無失真壓縮演算法分為兩類：通用演算法和專用演算法。像Bzip、Zlib、7z這些就是屬於通用壓縮庫，事實上，它們的效能的確很好，但不足是不會利用資料表示之間的細微差別。所以又有了一些更專門的演算法，比如Snappy、SPDP、LZO等，這一類演算法通過最小化資料佔用空間來提高應用程式的整體效能，因而有著廣泛的前景。
  • 儘管有以上這些特定領域的壓縮庫的良好發展，但是仍然面臨幾個比較現實的問題：
  1. 資料依賴： 由於每個庫對某種資料型別的專一化，致使對於其他情況來說，它通常不夠一般化。即使選擇了庫，大多數應用程式由於使用很多不同型別的資料，因此僅使用一個庫也不會產生最佳效能。
  2. 庫的選擇： 不同的庫有著不同的優點和缺點，通常為一個用例選擇合適的庫是困難的。即使在同一個應用程式中，其不同部分也會有著不同的壓縮需求。比如檔案的儲存需要高的壓縮比，而程序間的資料共享需要高的壓/解壓縮速度。
  3. API和可用性： 每個壓縮庫都有自己的一組引數和API，通常很難過渡到或採用新的庫，沒有哪種壓縮演算法可為所有型別的資料、檔案格式或應用程式需求提供最佳效能。我們希望可以有一個智慧的框架，能夠無縫統一多個庫，並根據特定場景動態選擇“最佳”壓縮演算法。

基準測試

  • 既然要統一不同演算法，那首先就要確切地掌握它們的實際表現。因此，學者對廣泛選擇的壓縮庫通過全面的基準測試進行了效能評估： file file file

  • 從資料型別、資料格式和工作負載優先順序三個維度進行了測試，篇幅有限，細節分析部分這裡不再具體展開。簡單總結為：通過觀察各個庫之間的效能變化，可以發現每個工作負載都可以從智慧的動態壓縮框架中受益。

Ares的體系架構

file

  • Ares架構的核心是即插即用，框架是一箇中間件庫，它封裝了多個壓縮庫，從使用者側抽象出它們的複雜性。應用程式可以使用Ares作為工具（CLI）或作為一個庫（API）。在這兩種情況下，Ares內部的資料流是相同的。首先，Ares分析輸入資料，以識別所涉及的資料型別和格式。其輸入可以是一個檔案、一個目錄或一個以前壓縮過的檔案（file.ares）。然後，將分析結果傳遞給主引擎，由主引擎決定哪個壓縮庫最適合給定的情況。根據決策，Ares利用一個庫池，其中包括預編譯的壓縮庫（目前的原型中已存在11個），再執行壓/解壓縮操作。最後，Ares用其元資料修飾壓縮資料，並輸出.ares檔案到磁碟。

要點評估

1. 開銷和資源利用率

file

  • 如上圖，我們可以觀察到，每個被測試的庫都展現了不同的開銷。例如，lz4、quicklz和snappy在CT、I/O和DT上都實現了類似的時間，但系統利用率不同（如snappy是CPU密集型、記憶體佔用低）。相比之下，bsc提供了最高8.6x的CR，但也是最慢的庫，它的CPU和記憶體佔用率高達90%以上。bzip2的記憶體佔用較低，但在CR為6.2x時仍保持較高的CPU佔用率。另一方面，Ares通過分析輸入資料來平衡CT、DT和CR，而這個額外的開銷只佔總時間的10%。Ares用了74秒進行資料型別和格式的檢測，即便有這些額外的開銷，Ares執行所有操作的速度仍然比所有庫的速度快，並取得了最佳的總體時間。
  • 具體來說，Ares比bsc快6.5倍，比bzip2快4.6倍，比lz4、quicklz快5-40%，而且在達到58%的CPU和64%的記憶體佔用率情況下仍然非常快。

2. 壓/解壓智慧度

file file

  • 從結果可以看出，使用CR為1.75倍的lz4可以更快地壓縮二進位制資料。對於較複雜的壓縮，bsc實現了大於5倍的CR，但CT和DT明顯減慢。

3. 壓/解壓適應度

file

4. 壓/解壓靈活度

  • Ares的優勢在於它能夠根據輸入的資料型別和格式進行壓縮。此外，Ares提供了在給定工作負載的情況下對某些壓縮特性進行優先順序排序的基礎設施。Ares的目標是通過C/C++和Java繫結支援科學和雲工作負載。此外，Ares抽象了它的引擎中包含的每個壓縮庫的細節，這使得它更易於使用，並且在需要時可以靈活地擴充套件到更多的壓縮庫。下面用了四個不同的科學應用（VPIC和HACC）和雲工作負載（單詞計數和整數排序）測試了Ares的效能，研究了三種類型的工作負載：讀密集型、寫密集型和混合讀寫型。 file

總結

  • 與傳統的壓縮庫相比，Ares可以提高效能。具體來說，在科學和雲端計算領域的實際應用中，Ares的執行速度比同類解決方案快了2-6倍，併為使用者提供了一個靈活的基礎設施，可根據手頭的任務確定壓縮特點。

參考文獻

[1] Shakarami A, Ghobaei-Arani M, Shahidinejad A, et al. Data replication schemes in cloud computing: a survey[J]. Cluster Computing, 2021, 24(3): 2545-2579. [2] Widodo R N S, Lim H, Atiquzzaman M. SDM: Smart deduplication for mobile cloud storage[J]. Future Generation Computer Systems, 2017, 70: 64-73. [3] Rani, I.S., Venkateswarlu, B.: A systematic review of different data compression technique of cloud big sensing data. In: International conference on computer networks and inventive communication technologies (pp. 222–228). Springer, Cham (2019) [4] Hema, S., Kangaiammal, A. (2019) Distributed storage hash algorithm (DSHA) for file-based deduplication in cloud computing. In: International conference on computer networks and inventive communication technologies (pp. 572–581). Springer, Cham (2019) [5] Liu J, Shen H, Narman H S. Popularity-aware multi-failure resilient and cost-effective replication for high data durability in cloud storage[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 30(10): 2355-2369. [6] Devarajan H, Kougkas A, Sun X H. An intelligent, adaptive, and flexible data compression framework[C]//2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID). IEEE, 2019: 82-91. [7] Widodo R N S, Lim H, Atiquzzaman M. SDM: Smart deduplication for mobile cloud storage[J]. Future Generation Computer Systems, 2017, 70: 64-73. [8] Top 10 benefits of cloud computing - Information Age

「」
「」