??想了解更多關(guān)于開源的內(nèi)容，請訪問：??

??51CTO 開源基礎(chǔ)軟件社區(qū)??

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

【技術(shù)DNA】

【智慧場景】

介紹

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

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

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

LZ4 分析

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

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

從算法上看

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

從結(jié)構(gòu)上看

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

LZ4m 分析

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

其次來說說內(nèi)存中的數(shù)據(jù)。內(nèi)存中的數(shù)據(jù)由虛擬內(nèi)存頁組成，其中包含來自應用程序的堆和棧的數(shù)據(jù)。堆和棧中包含常量、變量、指針和基本類型的數(shù)組，這些數(shù)據(jù)通常是結(jié)構(gòu)化的，并與系統(tǒng)的字邊界對齊。

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

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

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

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

評估

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

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

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

結(jié)論

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

??想了解更多關(guān)于開源的內(nèi)容，請訪問：??

??51CTO 開源基礎(chǔ)軟件社區(qū)??

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