??想了解更多關于開源的內容，請訪問：??

??51CTO 開源基礎軟件社區??

??https://ost.51cto.com??

【技術DNA】

【智慧場景】

介紹

隨著互聯網突飛猛進地發展，我們已經進入了“大數據時代”。對于大部分像抖音、淘寶等應用來說，其龐大的數據量、數據的復雜程度等都無疑會帶來很多問題；就拿淘寶來說，打開淘寶APP，一大堆的信息就會推送給你，像是文字、圖片、直播的視頻等等都會在數據方面帶來巨大的開銷。如果能夠試圖壓縮這些 “數據密集型（data-intensive）” 應用所帶來的數據，那么對于手機、電腦等等消費設備來說，人們將會從價格高昂的高端設備轉而選擇更便宜的配備小內存的型號。

要想讓“數據密集型”應用所產生的數據“瘦下來”可不是一件容易的事，因為 “壓縮自古兩難全”，想要壓縮比高，又不在性能（壓縮速度）上減少，很難有這種兩全其美的事。但對于一個應用來說，用戶體驗不能太差，這直接關系到內存中的數據壓縮，因為內存訪問的性能將會嚴重影響整個系統的性能，為此 Wilson 等人提出了 WKdm 算法，該算法利用了從內存數據中觀察的規律，從而展現出了非常出色的壓縮速度，但是它較差的壓縮比成為了它邁向成功的“絆腳石”。因此，作者將本文中提出的算法與其做對照。

文中，作者提出了一種新的壓縮算法，LZ4m；和 Wilson 提出的 WKdm 算法一樣，通過內存數據中經常觀察到的特征來加快 LZ4 算法輸入流的掃描；其次，針對 LZ4 算法，作者修改了其編碼方案，使其壓縮后的數據能夠以更簡潔的形式表示，結果表明，LZ4m 在壓縮和解壓縮的速度上分別比 LZ4 算法提高了 2.1x 和 1.8x，壓縮比的 marginal loss 小于 3%。

LZ4 分析

很多低壓縮延遲的壓縮算法都是基于 Lempel-Ziv 算法的，但是其仍有缺點，因為其最長匹配以及部分較長的匹配很難再帶來時間和空間開銷的減少，從而招致很高的時間和空間開銷。因此，在實踐中，大家通常會改變策略來快速識別足夠長的子字符串。

LZ4 則是在 Lempel-Ziv 算法的基礎上發展起來的最成功的壓縮算法之一，下面為對 LZ4 的匹配過程進行解釋：

從算法上看

• LZ4 主要在其滑動窗口與哈希表部分，滑動窗口每次掃描 4 字節的輸入流，并檢查窗口中的字符串是否在之前出現過。
• 為了輔助匹配，LZ4 維護了一個哈希表，并將 4 字節的字符串從輸入流開始的地方映射。
• 如果哈希表中包含當前滑動窗口中的字符串，那么將從當前掃描位置繼續匹配字符串，前后兩個具有相同前綴的子串能夠匹配出一個最長子串，對應哈希表條目更新到當前起始掃描位置。
• 滑動窗口繼續移動，不斷更新哈希表中沒有的子串的條目，直到滑動窗口達到結尾。

從結構上看

• 輸入流被編碼成了一個編碼單元，一個編碼單元（Encoding unit） 由首部（Token） 和主體（Body） 兩個部分組成。
• 每個編碼單元 都以 1 字節的首部開始，首部的前四位用來表示主體（Body） 的字面量長度 的大小，首部的后四位用來表示匹配長度 的大小。
• 如果字符串超過15字節，也就是首部的字面量長度的 4 位全為 1 時（1111），首部的字面量長度將減去 15 并放在首部后面的主體上。
• 主體（Body） 由字面量數據與匹配描述組成，其中匹配描述由向后的匹配偏移量與匹配長度 組成。
• 主體中偏移量由 2 字節編碼，因此 LZ4 可以回溯到 64 KB（2^16/1024）來查找匹配。
• 緊跟在某個匹配（Match）之后的其他匹配（Match）以類似的方式編碼，只是標記中的文字長度字段被設置為0000，并且主體（Body）省略了字面量（Literal）部分。

LZ4m 分析

由于 LZ4 是一種通用壓縮算法，沒有針對某個特定方面做了特別的優化，它的壓縮比以及解壓縮速度沒有針對某一領域完全釋放。因此，這里將利用內存中數據的特性來對 LZ4 進行修改。

其次來說說內存中的數據。內存中的數據由虛擬內存頁組成，其中包含來自應用程序的堆和棧的數據。堆和棧中包含常量、變量、指針和基本類型的數組，這些數據通常是結構化的，并與系統的字邊界對齊。

通過作者的觀察，發現掃描匹配單詞粒度中的數據可以在不顯著損失壓縮機會的情況下加速數據壓縮。此外，由于 4 字節對其的緣故，更大的粒度可以用更少的位來表示長度和偏移量，子字符串可以用更簡潔的形式編碼。

根據以上信息，作者提出了 LZ4m 算法，即用 LZ4 表示內存中的數據。下圖中則是 LZ4 與 LZ4m 的區別的對比，乍一看可能看不出有什么區別，滑動窗口、哈希表，兩者該有的都有；但是細看就會發現，LZ4m 的首部比 LZ4 多了偏移量（Offset），其它部分（包括首部的字面量長度，首部的匹配長度以及 主體的字面量的偏移量）也對內存大小方面做了改動。

由于 4 字節對齊，來獲取結構中元素的偏移量，長度為 4 字節的倍數，兩個最不重要的位總會是00（就像0,4,8,12 用 二進制表示為 0000、0100、1000、1100，后面兩位總是0，我們便可以將其刪掉來節省空間），這樣 首部（Token） 的 字面量長度（Literal length）、匹配長度（Match length） 以及 主體（Body） 的 匹配偏移量（Match offset） 都可以縮短 2 位。

此外，由于 LZ4m 是以 4 字節粒度壓縮 4KB 的頁面，所以偏移量最多需要 10 位，因此將偏移量的 2 個最高有效位放在首部（Token） 中，將剩下的 8 位放在主體中。

評估

• 將 LZ4 和 LZO1x 評估為通用算法的代表，將 WKdm 評估為專業算法。論文收集了通過交換從主內存中清除的數據來收集內存數據。
• 壓縮比是頁面的平均值，壓縮比越小意味著相同數據的壓縮大小越小。WKdm的壓縮比最大，其次是LZ4m，LZ4，最后是LZO1x，速度歸一化為 LZ4m。與通用算法（即 LZ4 和 LZO1x）相比，LZ4m 顯示出可比較的壓縮比，僅降低了 3%。
• LZ4m 在速度上優于這些算法高達 2.1× 和 1.8× 分別用于壓縮和解壓縮。LZ4m 在壓縮比和解壓速度上高于 WKdm 許多，但代價是壓縮速度下降了 21%。綜上，LZ4m 在壓縮比損失的情況下，大幅提高了 LZ4 的壓縮/解壓速度。

• 下圖顯示了頁面壓縮率的累積分布。LZ4m 的壓縮比曲線僅次與于 LZO 和 LZ4 算法一些，沒有很大差距。而 WKdm 顯示出明顯的壓縮比曲線，遠遠落后于其他算法。并且 6.8% 的頁面根本無法使用 WKdm 進行壓縮，而使用其他頁面的比例不到 1%。這表明 WKdm 的壓縮加速可以通過其較差的壓縮比來抵消
• 進一步比較 4 字節粒度的匹配偏移量和匹配長度的含義為目的，將從跟蹤匹配長度入手，如圖原始 LZ4 和 LZ4m 結果中計算匹配子串的長度，與累積匹配計數進行比較。放大了 LZ4 和 LZ4m 匹配長度在 0 到 32 之間的原始結果，增加的粒度只減少了總長度匹配的出現 2.5%，這意味著 4 字節粒度方案對找到匹配的機會影響很小，在匹配長度上的劣勢也是微不足道的。

• 時間和壓縮比之間的關系，通過測量每個頁面的壓縮時間并平均具有相同壓縮比的頁面的時間可以獲得算法的壓縮速度。壓縮良好的壓縮頁面的時間在算法中是相似的。比起 LZ4 和 LZO1x，LZ4m 顯示出了出色的壓縮速度 。因為 LZ4m 的掃描過程，如果沒有找到前綴匹配，掃描窗口會提前 4 個字節，從而在難以壓縮的頁面上提高四倍的掃描速度。
• 算法的解壓縮速度與平均解壓速度除以壓縮比，速度的獲得方式與平均壓縮速度相同。 LZ4m 在幾乎整個壓縮比范圍內的解壓縮速度都優于其他算法。

結論

• LZ4 是目前綜合來看效率最高的壓縮算法，更加側重壓縮解壓速度，壓縮比并不是第一。
• 利用內存數據的固有特性優化了一種流行的通用壓縮算法，根據數據，LZ4m 能極大地提高了壓縮/解壓縮速度，而壓縮比沒有實質性損失。
• LZ4m 針對小塊大小進行了優化。最大偏移量為 270（在 LZ4 中為 65535）。
• LZ4m 背后開發人員計劃將這種新的壓縮算法用于現實世界的內存壓縮系統。但從2017年后找不到更多的代碼。

??想了解更多關于開源的內容，請訪問：??

??51CTO 開源基礎軟件社區??

??https://ost.51cto.com??。