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

語言: CN / TW / HK
  • 本文出自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-basedhash-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)RAMCloudGoogle文件系統(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和snappyCT、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