??想了解更多關(guān)于開源的內(nèi)容，請(qǐng)?jiān)L問(wèn)：??

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

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

【技術(shù)DNA】

【智慧場(chǎng)景】

介紹

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

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

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

LZ4 分析

很多低壓縮延遲的壓縮算法都是基于 Lempel-Ziv 算法的，但是其仍有缺點(diǎn)，因?yàn)槠渥铋L(zhǎng)匹配以及部分較長(zhǎng)的匹配很難再帶來(lái)時(shí)間和空間開銷的減少，從而招致很高的時(shí)間和空間開銷。因此，在實(shí)踐中，大家通常會(huì)改變策略來(lái)快速識(shí)別足夠長(zhǎng)的子字符串。

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

從算法上看

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

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

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

LZ4m 分析

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

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

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

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

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

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

評(píng)估

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

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

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

結(jié)論

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

??想了解更多關(guān)于開源的內(nèi)容，請(qǐng)?jiān)L問(wèn)：??

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

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