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

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

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

【本期看點(diǎn)】

• ??FSST思想內(nèi)核??
• ??FSST的演化??
• ??FSST與LZ4對比??
• ??親手復(fù)現(xiàn)FSST??

【技術(shù)DNA】

【智慧場景】

FSST

快速靜態(tài)符號表(FSST)壓縮，這是一種輕量級的字符串編碼方案。

引言：

• 字符串在現(xiàn)實(shí)世界的數(shù)據(jù)集中很普遍。它們通常占用大量數(shù)據(jù)，處理速度很慢。
• 在許多真實(shí)的數(shù)據(jù)庫中，很大一部分?jǐn)?shù)據(jù)是用字符串表示的。
• 這是因?yàn)樽址?jīng) 常被用作各種數(shù)據(jù)的萬能類型。
• 人工生成的文本(描述或評論字段)。

• 機(jī)器生成的標(biāo)識符(url、電子郵件地址、IP 地址）。

1、字符串處理的現(xiàn)有方案

字符串通常是高度可壓縮的，許多系統(tǒng)依賴字典來壓縮字符串。 但是字典壓縮需要完全重復(fù)字符串來減少大小，因此當(dāng)字符串相似但不相等時(shí)，字典壓縮沒有優(yōu)勢。存儲在數(shù)據(jù)庫中的大多數(shù)字符串每個(gè)字符串通常小于 30 字節(jié)。LZ4 就不適合壓縮小的、單個(gè)的字符串，因?yàn)樗鼈冃枰_(dá)到 KB 數(shù)量級的輸入大小才能獲得良好的壓縮因子。但是，數(shù)據(jù)庫系統(tǒng)通常所需是對單個(gè)字符串隨機(jī)訪問，而LZ4算法是通過對數(shù)據(jù)塊的訪問實(shí)現(xiàn)的，這就無法滿足數(shù)據(jù)庫系統(tǒng)的需求。

2、主要特點(diǎn)

• 隨機(jī)訪問(解壓縮單個(gè)字符串而無需解壓縮一個(gè)更大的塊的能力)。
• 快速解碼(≈1-3 周期/字節(jié)，或 1-3 GB/s 每個(gè)核)。
• 文本字符串?dāng)?shù)據(jù)集的良好壓縮因子(≈2×)。
• 高編碼性能(≈4 個(gè)周期每字節(jié)，或≈1 GB每秒每字節(jié))。

3、關(guān)鍵思想

?是用 1 字節(jié)代碼替換頻繁出現(xiàn)的最多 8 字節(jié)的子字符串，這些元素構(gòu)成一個(gè)不可變符號表。

4、前人的積淀

 數(shù)據(jù)庫系統(tǒng)輕量級壓縮的研究集中在整數(shù)數(shù)據(jù)，但字符串在現(xiàn)實(shí)工作負(fù)載中的普遍存在和性能挑戰(zhàn)需要進(jìn)行更多的研究。 壓縮字符串最常用的方法是使用。

字典重復(fù)數(shù)據(jù)刪除。字典將每個(gè)唯一的字符串映射為整數(shù)代碼，使用整數(shù)壓縮方案對這些代碼進(jìn)行壓縮。在大多數(shù)數(shù)據(jù)庫系統(tǒng)中，字符串本身沒有被壓縮。

• Binnig 等人提出了一個(gè)帶增量前綴壓縮?的保序字符串字典。
  字典被表示為一個(gè)混合的 try /B-tree 數(shù)據(jù)結(jié)構(gòu)，以排序的順序存儲唯一的字符串。 雖然對某些數(shù)據(jù)集(例如 url)有效，但許多其他常見字符串?dāng)?shù)據(jù)集(例如 uuid)沒有長時(shí)間的共享前綴?，這使得該方案無效。全局字典還有如更新昂貴等缺點(diǎn)，這阻礙了它們的廣泛采用。
• 另一種壓縮字符串字典的方法是由 Arz 和 Fischer提出
  他們開發(fā)了 LZ78的變體?，允許解壓單個(gè)字符串?。 但是，這種方法的解壓縮非常昂貴，對于平均長度為 19 的字符串，需要超過 1 微秒的時(shí)間。這相當(dāng)于每個(gè)字符大約 100 個(gè) CPU 周期或每秒幾十兆字節(jié)，這對于許多數(shù)據(jù)管理用例來說太慢了。
• PostgreSQL。
  不使用字符串字典，而是實(shí)現(xiàn)了一種叫做 “超大屬性存儲技術(shù)”(TOAST)的方法。大于 2 KB 的進(jìn)行壓縮，較小的值保持不壓縮。
• 字節(jié)對。
  此方案是少數(shù)允許解壓縮單個(gè)短字符串?的壓縮方案之一。它首先對數(shù)據(jù)執(zhí)行一次完整的傳遞，確定哪些字節(jié)值沒有出現(xiàn)在輸入中，并計(jì)算每對字節(jié)出現(xiàn)的頻率。然后用未使用的字節(jié)值替換最常見的字節(jié)對。重復(fù)這個(gè)過程， 直到?jīng)]有更多未使用的字節(jié)。字節(jié)對對未使用字節(jié)的依賴意味，給定一個(gè)現(xiàn)有的壓縮表，不可見的數(shù)據(jù)不能被壓縮。字節(jié)對的遞歸性質(zhì)使解壓縮迭代，速度很慢。
• 遞歸配對。

一種隨機(jī)訪問壓縮格式，它遞歸地構(gòu)造層次符號語法。初始語法由所有單字節(jié)符號組成，通過將源文本中頻率最高的連續(xù)符號對替換為一個(gè)新符號、相對于擴(kuò)展的語法重新計(jì)算所有符號對的頻率，并遞歸地進(jìn)行擴(kuò)展。

主要步驟

• 制靜態(tài)符號表。
  識別經(jīng)常出現(xiàn)的公共子字符串?(稱之為符號)，并將它們替換為短的、固定大小的代碼， 由于效率的原因，符號的長度在 1 到 8 字節(jié)之間，并在字節(jié)(而不是位)邊界上進(jìn)行標(biāo)識。代碼總是 1 字節(jié)長，這意味著最多可以有 256 個(gè)符號，其中一個(gè)碼被保留為轉(zhuǎn)義碼.
• 解壓縮。
  解壓縮是相當(dāng)簡單的。每段代碼都通過數(shù)組查找?轉(zhuǎn)換為其符號，并將符號追加到輸出緩沖區(qū)。為了有效地解壓縮，將每個(gè)符號表示為一個(gè) 8 字節(jié)(64 位)的單詞，并將所有符號存儲在一個(gè)數(shù)組中。此外，還有第二個(gè)數(shù)組，用于存儲每個(gè)單詞的長度。使用這種表示，可以無條件地將 64 位字存儲到輸出緩沖區(qū)中，然后將輸出緩沖區(qū)向前推進(jìn)符號的實(shí)際長度來解壓代碼， 依賴于現(xiàn)代處理器上可用的快速未對齊存儲?，這種實(shí)現(xiàn)需要很少的指令?，而且沒有分支?。它的緩存效率也很高， 因?yàn)榉柋?2048 字節(jié))和長度數(shù)組(256 字節(jié))都可以輕松地 放入一級 CPU 緩存中。
• 幾點(diǎn)解釋。

使用轉(zhuǎn)義字符的優(yōu)勢

PS：（轉(zhuǎn)義碼并不是嚴(yán)格必要的;也可以只使用那些沒有出現(xiàn)在輸入字符串中的字節(jié)作為代碼）。

直接原因：保留代碼 255 作為轉(zhuǎn)義標(biāo)記，表示輸入中的以下字節(jié)需要按原樣復(fù)制，而不需要在符號表中查找。

三個(gè)優(yōu)點(diǎn)：

（1）支持使用現(xiàn)有的符號表壓縮任意(看不見的)文本。

（2）允許在數(shù)據(jù)樣本上執(zhí)行符號表構(gòu)造，從而加速壓縮。

（3）它釋放了原本被保留為低頻字節(jié)的符號，從而提高了壓縮因子。

連續(xù)注入單字節(jié)符號

如果由兩個(gè)較短的符號合并創(chuàng)建一個(gè)較長的符號，如果較長的符號再之后的增益排序中處于末尾就會被其他增益較長的字符串取代，這也就意味著原先那兩個(gè)較短的字符串也就隨之消失。

從本質(zhì)上說，如果不考慮單字節(jié)，符號只會變長，如果這樣更好的話，就永遠(yuǎn)不可能回到更短的符號。連續(xù)注入單字節(jié)符號允許重新生長由于這種太貪婪的選擇而丟失的有價(jià)值的長符號。

• FSST良好屬性。

1. 保有字符串屬性：不會因?yàn)榫幋a轉(zhuǎn)化變成其他類型的文本。
2. 壓縮查詢處理。直接通過比較其再表中的符號即可。
3. 字符串匹配。也可以對壓縮的字符串執(zhí)行更復(fù)雜的經(jīng)常發(fā)生的字符串操作(例如，LIKE 模式 匹配)，通過轉(zhuǎn)換為字節(jié)流中識別它們而設(shè)計(jì)的自動機(jī)，將它們重新映射到代碼流中。
4. 符號表很小。符號表的最大大小為 8*255+255 字節(jié)， 但通常只占用幾百字節(jié)，因?yàn)槠骄栭L度通常在 2 左右。因此，使用單獨(dú)的符號表壓縮每個(gè)字符串列的每個(gè)頁面是完全可行的，但也可以采用更粗粒度的粒度(按行組或整個(gè)表)。更細(xì)粒度的符號表構(gòu)造會帶來更好的壓縮因子，因此符號表將更適合于壓縮的數(shù)據(jù)。
5. 并行性。由于沒有(解)壓縮狀態(tài)，F(xiàn)SST(解)壓縮并行化很簡單——只有符號表構(gòu)造算法可能需要序列化。另一方 面，讓每個(gè)批量加載數(shù)據(jù)塊的線程構(gòu)造一個(gè)單獨(dú)的符號表 (應(yīng)該放在每個(gè)塊頭中)也是可以接受的，這樣壓縮也會變得非常并行。
6. 0-terminated 字符串。FSST 可選地生成以 0 結(jié)尾的字符串，因?yàn)樵谝?0 結(jié)尾的字符串中字節(jié)只出現(xiàn)在每個(gè)字符串的末尾，實(shí)際上還有 254 個(gè)代 碼需要壓縮。這稍微降低了壓縮的級別(價(jià)值最低的 255 個(gè)符號必須從符號表中刪除，它的出現(xiàn)將使用轉(zhuǎn)義字節(jié) 進(jìn)行處理)，但這種可選模式允許 FSST 適應(yīng)許多現(xiàn)有的基礎(chǔ)結(jié)構(gòu)。

5、存在問題

• 重復(fù)
  首先計(jì)算長度為 1 到 8 的子字符串在數(shù)據(jù)中出現(xiàn)的頻率，然后根據(jù)?增益順序?選擇前 255 個(gè)符號。這種方法的問題是:選擇的符號可能重疊?，因此計(jì)算的增益會被高估?。例如，在 URL 數(shù)據(jù)集中，8 字節(jié)符號http://w 幾乎每個(gè)字符串都含有，最有希望被選中。但符號 ttp://ww 和 tp://www 看起來同樣有希望，將所有三個(gè)候選者添加到符號表中是對有限代碼數(shù)量的浪費(fèi)，并會對壓縮因子產(chǎn)生負(fù)面影響。
• 貪婪性在編碼期間貪婪地?選擇最長?的符號不一定能最大化壓縮效率 。 參考我們在上文提到的連續(xù)單字節(jié)注入.
• 綜上所述，符號重疊與貪婪編碼相結(jié)合，造成符號之間的依賴問題，這使得難以估計(jì)增益，從而創(chuàng)建良好的符號表。

優(yōu)化方案

（1)迭代語料庫，使用當(dāng)前的符號表動態(tài)編碼。 這個(gè)階段計(jì)算符號表的整體質(zhì)量(壓縮因子)，但也計(jì)算每個(gè)符號在壓縮表示中的出現(xiàn)頻率，以及每個(gè)連續(xù)符號對。

(2)利用這些計(jì)數(shù)，通過選擇表觀增益最高的符號來構(gòu)建一個(gè)新的符號表。

實(shí)例

語料庫“tumcwitumvldb”上的 4 次迭代。為了使示例易于說明，將最大符號長度限制為 3(而不是 8)，最大符號表大小限制為 5(而不是 255)。在每次迭代之后，在頂部顯示壓縮后的字符串，但為了可讀性，不顯示代碼，而是顯示相應(yīng)的符號?！?”表示轉(zhuǎn)義字節(jié)。

• 這是最初未壓縮的字符串。

• 在第一次迭代中，壓縮字符串的長度臨時(shí)加倍?，因?yàn)榉柋碜畛跏强盏?，每個(gè)符號都必須轉(zhuǎn)義。在圖的底部，我們顯示了符號表，前 5 位符號基于靜態(tài)增益。

迭代 1 后，靜態(tài)增益排名前 5 位的為“um”、“tu”、“wi”，“cw” 和 “mc”。 前兩個(gè)最上面的符號(“um”，“tu”)出現(xiàn)了兩次，因此增益為 4，而后三個(gè)符號(“wi”，“cw”和“mc”)只出現(xiàn)一 次，因此增益為 2。注意，符號“mv”，“vl”，“l(fā)d”，“db”， “m”，“t”，“u”的增益也為 2，也可以被選取。換句話說，當(dāng)選擇頂部符號時(shí)，算法會任意地選取。

• 在第 2、3 和 4 次迭代中，符號表的質(zhì)量穩(wěn)步提高。

• 迭代 4 之后，最初長度為 13 的語料庫被壓縮為 5。

• 圖中還顯示，算法也會出現(xiàn)錯(cuò)誤?，但這些錯(cuò)誤會在下一次迭代中得到修復(fù)。
• 例如，在第 2 次迭代中，符號“tu”看起來相當(dāng)有吸引力，靜態(tài)增益為 4，但由于“tum”也在符號表 中，“tu”最終變得毫無價(jià)值。

• 并在第 3 次迭代中被修正。

技術(shù)優(yōu)化：

AVX512壓縮：

第一步，F(xiàn)SST API 壓縮一批字符串，字符串被復(fù)制到一個(gè)由 512 個(gè)段組成的臨時(shí)緩沖區(qū)中，如果需要將分割長字符串，并添加終止符。

第二步，首先按反向字符串長度對作業(yè)隊(duì)列數(shù)組進(jìn)行基數(shù)排序——速度很快，只需一次傳遞——因此首先處理最長的字符串，這有助于負(fù)載平衡。作業(yè)可能以不連續(xù)的順序完成，因此由于排序而以不連續(xù)的作業(yè)順序開始編碼工作，不會使算法(進(jìn)一步)復(fù)雜化。

第三步，AVX512 的優(yōu)勢不是內(nèi)存訪問，而是在壓縮內(nèi)核中利用的并行計(jì)算。 不只是一次性啟動 SIMD 內(nèi)核來處理 8 個(gè)通道中的 8 個(gè)字符串(或 24 個(gè)通道中的 24 個(gè)字符串，3×展開)，因?yàn)橛行┳址畷绕渌址痰枚?，而有些字符串會?其他字符串壓縮得多。這將意味著在編碼工作結(jié)束時(shí)，許多通道將是空的。因此，緩沖 512 個(gè)作業(yè)，并在需要時(shí)在每次迭代中重新填充車道。退出作業(yè)(作業(yè)控制寄存器中的 通 道 )使 用compress_store 指 令， 并 填 充 expand_load 指令。

FSST 與LZ4對比

• 速度

上表顯示了 LZ4 和 FSST 在每個(gè)數(shù)據(jù)集上分別和平均的三個(gè)指標(biāo)的相對性能。

對于幾乎所有的數(shù)據(jù)集，F(xiàn)SST 在壓縮因子和壓縮速度方面都優(yōu)于 LZ4。平均而言，除了產(chǎn)生更好的壓縮因子 FSST 的壓縮速度也提高了 60%。 對于解壓速度，F(xiàn)SST 在某些數(shù)據(jù)集上更快，而 LZ4 在其他數(shù)據(jù)集上更快——平均速度幾乎相同。

• 隨機(jī)存取

在數(shù)據(jù)庫場景中，通常不存儲大文件，而是使用包含大量相對較短字符串的字符串屬性或字典。用 LZ4 單 獨(dú)壓縮這些字符串會得到非常差的壓縮系數(shù)，普通 LZ4 (LZ4 行)不能合理地處理短字符串—壓縮因子低于 1，這意味著數(shù)據(jù)大小實(shí)際上略有增加。LZ4 還可選地支持使用額外的字典，該字典需要與壓縮數(shù)據(jù)一起提 供。使用 zstd 預(yù)生成一個(gè)適合語料庫的字典(LZ4 字典)， 在一定程度上提高了壓縮因子，但嚴(yán)重影響了壓縮速度。

下圖是測試結(jié)果：

• 分文本數(shù)據(jù)

數(shù)據(jù)庫環(huán)境之外，壓縮社區(qū)經(jīng)常評估 Silesia 語料庫上的壓縮方法，該語料庫由 11 個(gè)文件組成，其中 4 個(gè) 是文本文件(dick- ens, reymont, mr, webster)，1個(gè)是 XML, 6 個(gè)是二進(jìn)制文件。FSST 對文本文件的壓縮大小平均提高了 10%，但對二進(jìn)制文件的壓縮大小平均降低了 25%。 雖然認(rèn)為二進(jìn)制文件與 FSST 無關(guān)，但它在大型 XML 和 JSON 文件上的壓縮比比 LZ4 差 2-2.5 倍，這是相關(guān)的。但是，數(shù)據(jù)庫系統(tǒng)不應(yīng)該將這些組合值存儲為簡單的字符串，而應(yīng)該存儲為允許查詢處理的特殊類型。例如，Snowflake 識別 JSON 列中的結(jié)構(gòu)，并在內(nèi)部將每個(gè)經(jīng)常出現(xiàn)的 JSON 屬性存儲在單獨(dú)的內(nèi)部列中。

FSST的演化

FSST 壓縮算法經(jīng)過多次迭代才達(dá)到當(dāng)前的設(shè)計(jì)。上表 顯示了 7 種變體的??壓縮因子(CF)、符號表構(gòu)建成本(CS)和字 符串編碼速度(SE)??

第一個(gè)設(shè)計(jì)基于后綴數(shù)組，壓縮因子達(dá)到1.97，但符號表的構(gòu)造需要 74.3 cy- cles/字節(jié)，編碼需要 160 cycles/字節(jié)。

目前的 AVX512 版本(圖中的變體 7)在表構(gòu)建方面快了 90 倍，快了40倍 用于編碼比第一個(gè)版本-同時(shí)提供更高的壓縮因子。

最終的版本也比最初的 FSST 版本(變體 4)快得多，這要?dú)w功于損耗完美哈希和 AVX512——盡管不得不犧牲相對于變體 4 大約 6%的空間增益。

盡管需要多次迭代，但符號表的構(gòu)造時(shí)間只占編碼時(shí)間的一小部分。 優(yōu)化構(gòu)造需要將迭代次數(shù)從 10 次減少到 5 次，構(gòu)建一個(gè)示例(每次迭代都會增長)，并縮小計(jì)數(shù)器的內(nèi)存占用。

復(fù)現(xiàn)流程

系統(tǒng)需求

• Linux、Windows、MacOS 均可，此處為 Deepin 20.5 / Linux 環(huán)境。

源碼準(zhǔn)備

• 首先，來到 FSST 的開源倉庫??https://github.com/cwida/fsst，在已配置??? Git 環(huán)境的情況下可以按照如圖所指位置復(fù)制 https 或 ssh 地址將源碼克隆至本地；若未配置 Git，可參考 github 或 gitee 的相關(guān)指示進(jìn)行配置操作。不過，Git 在此處并非必要條件，也可手動 “Download ZIP” 得到壓縮包后進(jìn)行解壓。
• 

如上所述，針對 Git 環(huán)境，在終端中鍵入以下命令：

git clone???https://github.com/cwida/fsst.git??? # 若已配置SSH公鑰，可采用下圖形式。

cd fsst/：

環(huán)境搭建

1. CMake 安裝。

• FSST 使用 C++ 語言實(shí)現(xiàn)，因此依賴 CMake 工具進(jìn)行編譯構(gòu)建，Debian 系下可方便地使用 apt 實(shí)現(xiàn)工具安裝初始化，鍵入并執(zhí)行以下命令：

sudo apt update
sudo apt install cmake

可以看到 cmake 在之前已經(jīng)安裝過了，并且版本是 3.18.4 ：

2. Zstd 與 LZ4 庫的安裝。

• FSST 需要調(diào)用 zstd 與 lz4 的相關(guān) API 以在壓縮過程中生成對應(yīng)字典，因此還需要準(zhǔn)備相應(yīng)的動態(tài)庫：

sudo apt install zstd* lz4* libzstd* liblz4*   # 同 cmake 的安裝

完成后，可以在 /usr/lib/x86_64-linux-gnu/ 下看到相關(guān)文件已生成：

此外，還需要建立到 /usr/lib/ 的軟鏈接，避免后續(xù)鏈接時(shí)出現(xiàn)找不到缺省目錄的問題：

# 注意，下方諸如 '1.4.8' '1.8.3' 一類的版本號需要根據(jù)實(shí)際狀況進(jìn)行相應(yīng)地替換
cd /usr***/lib/x86_64-linux-gnu/
echo '../libzstd.so ../libzstd.so.1 ../libzstd.so.1.4.8' | sudo xargs -n 1 ln -s libzstd.so.1.4.8
echo '../liblz4.so ../liblz4.so.1 ../liblz4.so.1.8.3' | sudo xargs -n 1 ln -s liblz4.so.1.8.3

編譯構(gòu)建

• 環(huán)境部署基本完成，下面開始編譯。

cd -
cmake ./
make -j8 && make binary

• 100% 完成后，說明編譯已成功，查看所在目錄，可以看到 fsst 的二進(jìn)制程序已生成：

• 為了方便后續(xù)操作，建議將其加入環(huán)境變量：

vim ~/.bashrc
export PATH=/home/yanxu/ELT.ZIP/fsst:$PATH    # 在尾行添加
:wq    # 保存退出

已經(jīng)可以正常使用，輸入 fsst 即可查看說明：

評估測試

自動化測試

• 倉庫中提供了足量的數(shù)據(jù)集用來對算法進(jìn)行評估，并且也有自動化腳本幫助一鍵跑完全程，下面就來試一試吧：

cd paper/
chmod +x *.sh

results 目錄中已存放有作者測試過的結(jié)果，但我們同樣可以在自己機(jī)器上再進(jìn)行一遍測試，執(zhí)行如下命令：

make experiments

花費(fèi)時(shí)間會較長，耐心等待即可，這里舉出作者的其中一項(xiàng)示例：

最左側(cè)的一列是各式各樣的字符集，另外三個(gè)框框分別表示壓縮比、壓縮速度、解壓速度，其中，左側(cè)是 LZ4、右側(cè)是 FSST。不難看出，壓縮比方面，F(xiàn)SST 僅在 urls 上較 LZ4 弱了一點(diǎn)；壓縮速度方面，LZ4 僅在 hex 上取得了微弱的優(yōu)勢；而解壓速度方面，則是二者互有勝負(fù)，可以視作忽略不計(jì)。

手動測試

• 那么除此之外，還可以手動進(jìn)行對更多算法的對比。

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

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

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