OpenHarmony啃論文俱樂部—快速隨機訪問字符串壓縮
【本期看點】
- ?
?FSST思想內核?? - ?
?FSST的演化?? - ?
?FSST與LZ4對比?? - ?
?親手復現FSST??
【技術DNA】
【智慧場景】
********** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ******************** | ***************** |
場景 | 自動駕駛 / AR | 語音信號 | 流視頻 | GPU 渲染 | 科學、云計算 | 內存縮減 | 科學應用 | 醫學圖像 | 數據庫服務器 | 人工智能圖像 | 文本傳輸 | GAN媒體壓縮 | 圖像壓縮 | 文件同步 | 數據庫系統 |
技術 | 點云壓縮 | ?稀疏快速傅里葉變換? | 有損視頻壓縮 | 網格壓縮 | 動態選擇壓縮算法框架 | 無損壓縮 | 分層數據壓縮 | 醫學圖像壓縮 | 無損通用壓縮 | 人工智能圖像壓縮 | 短字符串壓縮 | GAN 壓縮的在線多粒度蒸餾 | 圖像壓縮 | 文件傳輸壓縮 | 快速隨機訪問字符串壓縮 |
開源項目 | ??SFFT?? | ??Ares?? | ??LZ4?? | ??DICOM?? | ??Brotli?? | ??RAISR?? | ??AIMCS?? | ??OMGD?? | ??rsync?? | ??FSST?? |
FSST
快速靜態符號表(FSST)壓縮，這是一種輕量級的字符串編碼方案。
引言：
- 字符串在現實世界的數據集中很普遍。它們通常占用大量數據，處理速度很慢。
- 在許多真實的數據庫中，很大一部分數據是用字符串表示的。
- 這是因為字符串經 常被用作各種數據的萬能類型。
- 人工生成的文本(描述或評論字段)。
- 機器生成的標識符(url、電子郵件地址、IP 地址）。
1、字符串處理的現有方案
字符串通常是高度可壓縮的，許多系統依賴字典來壓縮字符串。 但是字典壓縮需要完全重復字符串來減少大小，因此當字符串相似但不相等時，字典壓縮沒有優勢。存儲在數據庫中的大多數字符串每個字符串通常小于 30 字節。LZ4 就不適合壓縮小的、單個的字符串，因為它們需要達到 KB 數量級的輸入大小才能獲得良好的壓縮因子。但是，數據庫系統通常所需是對單個字符串隨機訪問，而LZ4算法是通過對數據塊的訪問實現的，這就無法滿足數據庫系統的需求。
2、主要特點
- 隨機訪問(解壓縮單個字符串而無需解壓縮一個更大的塊的能力)。
- 快速解碼(≈1-3 周期/字節，或 1-3 GB/s 每個核)。
- 文本字符串數據集的良好壓縮因子(≈2×)。
- 高編碼性能(≈4 個周期每字節，或≈1 GB每秒每字節)。
3、關鍵思想
?是用 1 字節代碼替換頻繁出現的最多 8 字節的子字符串，這些元素構成一個不可變符號表。
4、前人的積淀
數據庫系統輕量級壓縮的研究集中在整數數據，但字符串在現實工作負載中的普遍存在和性能挑戰需要進行更多的研究。 壓縮字符串最常用的方法是使用。
字典重復數據刪除。字典將每個唯一的字符串映射為整數代碼，使用整數壓縮方案對這些代碼進行壓縮。在大多數數據庫系統中，字符串本身沒有被壓縮。
- Binnig 等人提出了一個帶增量前綴壓縮?的保序字符串字典。
字典被表示為一個混合的 try /B-tree 數據結構，以排序的順序存儲唯一的字符串。 雖然對某些數據集(例如 url)有效，但許多其他常見字符串數據集(例如 uuid)沒有長時間的共享前綴?，這使得該方案無效。全局字典還有如更新昂貴等缺點，這阻礙了它們的廣泛采用。 - 另一種壓縮字符串字典的方法是由 Arz 和 Fischer提出
他們開發了 LZ78的變體?，允許解壓單個字符串?。 但是，這種方法的解壓縮非常昂貴，對于平均長度為 19 的字符串，需要超過 1 微秒的時間。這相當于每個字符大約 100 個 CPU 周期或每秒幾十兆字節，這對于許多數據管理用例來說太慢了。 - PostgreSQL。
不使用字符串字典，而是實現了一種叫做 “超大屬性存儲技術”(TOAST)的方法。大于 2 KB 的進行壓縮，較小的值保持不壓縮。 - 字節對。
此方案是少數允許解壓縮單個短字符串?的壓縮方案之一。它首先對數據執行一次完整的傳遞，確定哪些字節值沒有出現在輸入中，并計算每對字節出現的頻率。然后用未使用的字節值替換最常見的字節對。重復這個過程， 直到沒有更多未使用的字節。字節對對未使用字節的依賴意味，給定一個現有的壓縮表，不可見的數據不能被壓縮。字節對的遞歸性質使解壓縮迭代，速度很慢。 - 遞歸配對。
一種隨機訪問壓縮格式，它遞歸地構造層次符號語法。初始語法由所有單字節符號組成，通過將源文本中頻率最高的連續符號對替換為一個新符號、相對于擴展的語法重新計算所有符號對的頻率，并遞歸地進行擴展。
主要步驟
- 制靜態符號表。
識別經常出現的公共子字符串?(稱之為符號)，并將它們替換為短的、固定大小的代碼， 由于效率的原因，符號的長度在 1 到 8 字節之間，并在字節(而不是位)邊界上進行標識。代碼總是 1 字節長，這意味著最多可以有 256 個符號，其中一個碼被保留為轉義碼. - 解壓縮。
解壓縮是相當簡單的。每段代碼都通過數組查找?轉換為其符號，并將符號追加到輸出緩沖區。為了有效地解壓縮，將每個符號表示為一個 8 字節(64 位)的單詞，并將所有符號存儲在一個數組中。此外，還有第二個數組，用于存儲每個單詞的長度。使用這種表示，可以無條件地將 64 位字存儲到輸出緩沖區中，然后將輸出緩沖區向前推進符號的實際長度來解壓代碼， 依賴于現代處理器上可用的快速未對齊存儲?，這種實現需要很少的指令?，而且沒有分支?。它的緩存效率也很高， 因為符號表(2048 字節)和長度數組(256 字節)都可以輕松地 放入一級 CPU 緩存中。 - 幾點解釋。
使用轉義字符的優勢
PS：（轉義碼并不是嚴格必要的;也可以只使用那些沒有出現在輸入字符串中的字節作為代碼）。
直接原因：保留代碼 255 作為轉義標記，表示輸入中的以下字節需要按原樣復制，而不需要在符號表中查找。
三個優點：
（1）支持使用現有的符號表壓縮任意(看不見的)文本。
（2）允許在數據樣本上執行符號表構造，從而加速壓縮。
（3）它釋放了原本被保留為低頻字節的符號，從而提高了壓縮因子。
連續注入單字節符號
如果由兩個較短的符號合并創建一個較長的符號，如果較長的符號再之后的增益排序中處于末尾就會被其他增益較長的字符串取代，這也就意味著原先那兩個較短的字符串也就隨之消失。
從本質上說，如果不考慮單字節，符號只會變長，如果這樣更好的話，就永遠不可能回到更短的符號。連續注入單字節符號允許重新生長由于這種太貪婪的選擇而丟失的有價值的長符號。
- FSST良好屬性。
- 保有字符串屬性：不會因為編碼轉化變成其他類型的文本。
- 壓縮查詢處理。直接通過比較其再表中的符號即可。
- 字符串匹配。也可以對壓縮的字符串執行更復雜的經常發生的字符串操作(例如，LIKE 模式 匹配)，通過轉換為字節流中識別它們而設計的自動機，將它們重新映射到代碼流中。
- 符號表很小。符號表的最大大小為 8*255+255 字節， 但通常只占用幾百字節，因為平均符號長度通常在 2 左右。因此，使用單獨的符號表壓縮每個字符串列的每個頁面是完全可行的，但也可以采用更粗粒度的粒度(按行組或整個表)。更細粒度的符號表構造會帶來更好的壓縮因子，因此符號表將更適合于壓縮的數據。
- 并行性。由于沒有(解)壓縮狀態，FSST(解)壓縮并行化很簡單——只有符號表構造算法可能需要序列化。另一方 面，讓每個批量加載數據塊的線程構造一個單獨的符號表 (應該放在每個塊頭中)也是可以接受的，這樣壓縮也會變得非常并行。
- 0-terminated 字符串。FSST 可選地生成以 0 結尾的字符串，因為在以 0 結尾的字符串中字節只出現在每個字符串的末尾，實際上還有 254 個代 碼需要壓縮。這稍微降低了壓縮的級別(價值最低的 255 個符號必須從符號表中刪除，它的出現將使用轉義字節 進行處理)，但這種可選模式允許 FSST 適應許多現有的基礎結構。
5、存在問題
- 重復
首先計算長度為 1 到 8 的子字符串在數據中出現的頻率，然后根據?增益順序?選擇前 255 個符號。這種方法的問題是:選擇的符號可能重疊?，因此計算的增益會被高估?。例如，在 URL 數據集中，8 字節符號http://w 幾乎每個字符串都含有，最有希望被選中。但符號 ttp://ww 和 tp://www 看起來同樣有希望，將所有三個候選者添加到符號表中是對有限代碼數量的浪費，并會對壓縮因子產生負面影響。 - 貪婪性在編碼期間貪婪地?選擇最長?的符號不一定能最大化壓縮效率 。 參考我們在上文提到的連續單字節注入.
- 綜上所述，符號重疊與貪婪編碼相結合，造成符號之間的依賴問題，這使得難以估計增益，從而創建良好的符號表。
優化方案
（1)迭代語料庫，使用當前的符號表動態編碼。 這個階段計算符號表的整體質量(壓縮因子)，但也計算每個符號在壓縮表示中的出現頻率，以及每個連續符號對。
(2)利用這些計數，通過選擇表觀增益最高的符號來構建一個新的符號表。
實例
語料庫“tumcwitumvldb”上的 4 次迭代。為了使示例易于說明，將最大符號長度限制為 3(而不是 8)，最大符號表大小限制為 5(而不是 255)。在每次迭代之后，在頂部顯示壓縮后的字符串，但為了可讀性，不顯示代碼，而是顯示相應的符號。“$”表示轉義字節。
- 這是最初未壓縮的字符串。
- 在第一次迭代中，壓縮字符串的長度臨時加倍?，因為符號表最初是空的?，每個符號都必須轉義。在圖的底部，我們顯示了符號表，前 5 位符號基于靜態增益。
迭代 1 后，靜態增益排名前 5 位的為“um”、“tu”、“wi”，“cw” 和 “mc”。 前兩個最上面的符號(“um”，“tu”)出現了兩次，因此增益為 4，而后三個符號(“wi”，“cw”和“mc”)只出現一 次，因此增益為 2。注意，符號“mv”，“vl”，“ld”，“db”， “m”，“t”，“u”的增益也為 2，也可以被選取。換句話說，當選擇頂部符號時，算法會任意地選取。
- 在第 2、3 和 4 次迭代中，符號表的質量穩步提高。
- 迭代 4 之后，最初長度為 13 的語料庫被壓縮為 5。
- 圖中還顯示，算法也會出現錯誤?，但這些錯誤會在下一次迭代中得到修復。
- 例如，在第 2 次迭代中，符號“tu”看起來相當有吸引力，靜態增益為 4，但由于“tum”也在符號表 中，“tu”最終變得毫無價值。
- 并在第 3 次迭代中被修正。
技術優化：
AVX512壓縮：
第一步，FSST API 壓縮一批字符串，字符串被復制到一個由 512 個段組成的臨時緩沖區中，如果需要將分割長字符串，并添加終止符。
第二步，首先按反向字符串長度對作業隊列數組進行基數排序——速度很快，只需一次傳遞——因此首先處理最長的字符串，這有助于負載平衡。作業可能以不連續的順序完成，因此由于排序而以不連續的作業順序開始編碼工作，不會使算法(進一步)復雜化。
第三步，AVX512 的優勢不是內存訪問，而是在壓縮內核中利用的并行計算。 不只是一次性啟動 SIMD 內核來處理 8 個通道中的 8 個字符串(或 24 個通道中的 24 個字符串，3×展開)，因為有些字符串會比其他字符串短得多，而有些字符串會比 其他字符串壓縮得多。這將意味著在編碼工作結束時，許多通道將是空的。因此，緩沖 512 個作業，并在需要時在每次迭代中重新填充車道。退出作業(作業控制寄存器中的 通 道 )使 用compress_store 指 令， 并 填 充 expand_load 指令。
FSST 與LZ4對比
- 速度
上表顯示了 LZ4 和 FSST 在每個數據集上分別和平均的三個指標的相對性能。
對于幾乎所有的數據集，FSST 在壓縮因子和壓縮速度方面都優于 LZ4。平均而言，除了產生更好的壓縮因子 FSST 的壓縮速度也提高了 60%。 對于解壓速度，FSST 在某些數據集上更快，而 LZ4 在其他數據集上更快——平均速度幾乎相同。
- 隨機存取
在數據庫場景中，通常不存儲大文件，而是使用包含大量相對較短字符串的字符串屬性或字典。用 LZ4 單 獨壓縮這些字符串會得到非常差的壓縮系數，普通 LZ4 (LZ4 行)不能合理地處理短字符串—壓縮因子低于 1，這意味著數據大小實際上略有增加。LZ4 還可選地支持使用額外的字典，該字典需要與壓縮數據一起提 供。使用 zstd 預生成一個適合語料庫的字典(LZ4 字典)， 在一定程度上提高了壓縮因子，但嚴重影響了壓縮速度。
下圖是測試結果：
- 分文本數據
數據庫環境之外，壓縮社區經常評估 Silesia 語料庫上的壓縮方法，該語料庫由 11 個文件組成，其中 4 個 是文本文件(dick- ens, reymont, mr, webster)，1個是 XML, 6 個是二進制文件。FSST 對文本文件的壓縮大小平均提高了 10%，但對二進制文件的壓縮大小平均降低了 25%。 雖然認為二進制文件與 FSST 無關，但它在大型 XML 和 JSON 文件上的壓縮比比 LZ4 差 2-2.5 倍，這是相關的。但是，數據庫系統不應該將這些組合值存儲為簡單的字符串，而應該存儲為允許查詢處理的特殊類型。例如，Snowflake 識別 JSON 列中的結構，并在內部將每個經常出現的 JSON 屬性存儲在單獨的內部列中。
FSST的演化
FSST 壓縮算法經過多次迭代才達到當前的設計。上表 顯示了 7 種變體的??壓縮因子(CF)、符號表構建成本(CS)和字 符串編碼速度(SE)??
第一個設計基于后綴數組，壓縮因子達到1.97，但符號表的構造需要 74.3 cy- cles/字節，編碼需要 160 cycles/字節。
目前的 AVX512 版本(圖中的變體 7)在表構建方面快了 90 倍，快了40倍 用于編碼比第一個版本-同時提供更高的壓縮因子。
最終的版本也比最初的 FSST 版本(變體 4)快得多，這要歸功于損耗完美哈希和 AVX512——盡管不得不犧牲相對于變體 4 大約 6%的空間增益。
盡管需要多次迭代，但符號表的構造時間只占編碼時間的一小部分。 優化構造需要將迭代次數從 10 次減少到 5 次，構建一個示例(每次迭代都會增長)，并縮小計數器的內存占用。
復現流程
系統需求
- Linux、Windows、MacOS 均可，此處為 Deepin 20.5 / Linux 環境。
源碼準備
- 首先，來到 FSST 的開源倉庫??https://github.com/cwida/fsst，在已配置??? Git 環境的情況下可以按照如圖所指位置復制 https 或 ssh 地址將源碼克隆至本地；若未配置 Git，可參考 github 或 gitee 的相關指示進行配置操作。不過，Git 在此處并非必要條件，也可手動 “Download ZIP” 得到壓縮包后進行解壓。
如上所述，針對 Git 環境，在終端中鍵入以下命令：
git clone???https://github.com/cwida/fsst.git??? # 若已配置SSH公鑰，可采用下圖形式。
cd fsst/：
環境搭建
- CMake 安裝。
- FSST 使用 C++ 語言實現，因此依賴 CMake 工具進行編譯構建，Debian 系下可方便地使用 apt 實現工具安裝初始化，鍵入并執行以下命令：
sudo apt update
sudo apt install cmake
可以看到 cmake 在之前已經安裝過了，并且版本是 3.18.4 ：
- Zstd 與 LZ4 庫的安裝。
- FSST 需要調用 zstd 與 lz4 的相關 API 以在壓縮過程中生成對應字典，因此還需要準備相應的動態庫：
sudo apt install zstd* lz4* libzstd* liblz4* # 同 cmake 的安裝
完成后，可以在 /usr/lib/x86_64-linux-gnu/ 下看到相關文件已生成：
此外，還需要建立到 /usr/lib/ 的軟鏈接，避免后續鏈接時出現找不到缺省目錄的問題：
# 注意，下方諸如 '1.4.8' '1.8.3' 一類的版本號需要根據實際狀況進行相應地替換
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
編譯構建
- 環境部署基本完成，下面開始編譯。
cd -
cmake ./
make -j8 && make binary
- 100% 完成后，說明編譯已成功，查看所在目錄，可以看到 fsst 的二進制程序已生成：
- 為了方便后續操作，建議將其加入環境變量：
vim ~/.bashrc
export PATH=/home/yanxu/ELT.ZIP/fsst:$PATH # 在尾行添加
:wq # 保存退出
已經可以正常使用，輸入 fsst 即可查看說明：
評估測試
自動化測試
- 倉庫中提供了足量的數據集用來對算法進行評估，并且也有自動化腳本幫助一鍵跑完全程，下面就來試一試吧：
cd paper/
chmod +x *.sh
results 目錄中已存放有作者測試過的結果，但我們同樣可以在自己機器上再進行一遍測試，執行如下命令：
make experiments
花費時間會較長，耐心等待即可，這里舉出作者的其中一項示例：
最左側的一列是各式各樣的字符集，另外三個框框分別表示壓縮比、壓縮速度、解壓速度，其中，左側是 LZ4、右側是 FSST。不難看出，壓縮比方面，FSST 僅在 urls 上較 LZ4 弱了一點；壓縮速度方面，LZ4 僅在 hex 上取得了微弱的優勢；而解壓速度方面，則是二者互有勝負，可以視作忽略不計。
手動測試
- 那么除此之外，還可以手動進行對更多算法的對比。
