在 PolarDB 中, 通過輕量級壓縮的實(shí)現(xiàn), 可以實(shí)現(xiàn)減少數(shù)據(jù)大小的同時(shí), 性能有一定程度的提升. 如何實(shí)現(xiàn)的呢?

背景

近幾年互聯(lián)網(wǎng)行業(yè)的降本增效浪潮愈演愈烈, 如數(shù)據(jù)壓縮、分級存儲等技術(shù)成為了數(shù)據(jù)庫產(chǎn)品（在技術(shù)層面上）實(shí)現(xiàn)降本的核心手段。作為一款云原生數(shù)據(jù)庫，PolarDB 會面向大量行業(yè)、場景、需求不同的云用戶，同樣有必要且已經(jīng)支持了這些能力。PolarDB 在全鏈路多個(gè)層級上實(shí)現(xiàn)了并正逐步商業(yè)化數(shù)據(jù)壓縮能力, 如整形、字符串、BLOB 等數(shù)據(jù)格式類型的壓縮，數(shù)據(jù)列字典壓縮、二級索引前綴壓縮，存儲層的數(shù)據(jù)塊軟/硬件壓縮等。

首先要提到的必然是 MySQL 官方原生的兩種壓縮能力：表壓縮和透明頁壓縮。這兩種壓縮能力由于或這或那的各種原因，在實(shí)際線上業(yè)務(wù)中并沒有被廣泛仍可和使用。例如前者在 Buffer pool 中存在兩個(gè)版本數(shù)據(jù)且有較為復(fù)雜的融合邏輯，后者需要文件系統(tǒng)支持 punch hole 只能對帶寬壓縮而沒有優(yōu)化 IOPS，兩者只采用限定的相對開銷較高的通用塊壓縮算法等。它們的實(shí)測表現(xiàn)也導(dǎo)致傳統(tǒng) MySQL 用戶在印象里常覺得壓縮會犧牲不少性能并帶來較多復(fù)雜度。

事實(shí)上，在通用塊壓縮的基礎(chǔ)上，如果可以引入更細(xì)致的輕量級壓縮, 甚至在壓縮后的數(shù)據(jù)上直接進(jìn)行計(jì)算, 那么可以在實(shí)現(xiàn)數(shù)據(jù)壓縮的同時(shí)又保證甚至提升性能。并且，在計(jì)存分離架構(gòu)下，遠(yuǎn)程 I/O 時(shí)延更長,如果可以通過壓縮減少數(shù)據(jù)大小, 從而減少 I/O, 壓縮帶來的收益相比于本地盤就更加明顯。

由 MySQL 向外擴(kuò)展來看，針對:（1）動態(tài)（update-in-place）或靜態(tài)（append-only）數(shù)據(jù)；（2）行存或列存組織組織（數(shù)據(jù)同質(zhì)性不同）；（3）有序鏈或無序堆組織的數(shù)據(jù)（數(shù)據(jù)局部性不同）等不同情況，能適用的壓縮方法也是不同的，并且壓縮能獲得的效果會有很大差異。因此，對于 PolarDB-MySQL 來說，除了官方的兩種原生壓縮能力，通過輕量級壓縮方法實(shí)現(xiàn)頁內(nèi)/行級壓縮（這也是 Oracle、SQL Server、DB2 等企業(yè)級數(shù)據(jù)庫的標(biāo)準(zhǔn)能力），也是重要發(fā)展路徑。

PolarDB 前綴壓縮

本文就主要介紹 PolarDB-MySQL 引擎層的索引前綴壓縮能力（Index Prefix Compression）的技術(shù)實(shí)現(xiàn)和效果。

通過建立索引結(jié)構(gòu)可以提升數(shù)據(jù)檢索的性能，代價(jià)是額外的寫放大和維護(hù)索引結(jié)構(gòu)的存儲空間。OLTP 中為了支持多種訪問路徑，比較常見的情況是在一個(gè)表上建立非常多的索引，這就導(dǎo)致索引在數(shù)據(jù)庫整體存儲空間中占了很大比例。索引存儲占到 50% 以上的實(shí)例并不少見，這些實(shí)例通常在單表會有幾十個(gè)二級索引。

由于索引的 key 部分?jǐn)?shù)據(jù)存在有序性，因此對索引 key 部分進(jìn)行前綴壓縮往往可以取得不錯的壓縮效果。如果用戶的數(shù)據(jù)表中存在較多的索引（如一些做sass的用戶），索引數(shù)據(jù)量相對整體數(shù)據(jù)量的占比不低，此時(shí)前綴壓縮的收益其實(shí)十分可觀。

我們先簡單了解一下 InnoDB 的索引結(jié)構(gòu)，對于主鍵 record，首先是所有主鍵 key 的字段列、再是非 key 數(shù)據(jù)的字段列；而二級索引 record，則先是對應(yīng)二級索引 key 的字段列、再是主鍵 key 的字段列。

值得一提的是，部分商業(yè)數(shù)據(jù)庫在實(shí)現(xiàn) non-unique index 時(shí)，一般會將相同的二級索引對應(yīng)的主鍵索引聚集存放, 這樣二級索引 key 部分的數(shù)據(jù)只需要存一份（Duplicate Key Removal）。而在 InnoDB 中的實(shí)現(xiàn)較為簡單, 每個(gè)二級索引 record 為重復(fù)的二級索引 key 字段加不同主鍵 key，這加劇了 InnoDB 索引數(shù)據(jù)膨脹的問題。

前綴壓縮設(shè)計(jì)原理

前綴壓縮其實(shí)有多種具體實(shí)現(xiàn)，比如同個(gè) Page 的 record 前綴重復(fù)出現(xiàn)部分的直接壓縮，如前綴為 "aaaaa" 直接壓縮為 "a5"；或相對前一記錄重復(fù)部分的壓縮，又或相對具體元素的前綴重復(fù)部分，提取 "aaaaa" 到公共區(qū)域作為前綴。

我們采用的方法是將 record 分為兩個(gè)部分：前綴部分在多個(gè) record 之間共享，因此可以只存儲一份，從而實(shí)現(xiàn)數(shù)據(jù)壓縮；后綴部分由每個(gè) record 單獨(dú)存儲。因此壓縮后的 record 中只存儲了前綴部分的指針 + 后綴部分的數(shù)據(jù)。

對數(shù)據(jù)頁內(nèi)的 record 進(jìn)行前綴壓縮效果：

采用前綴壓縮，可以有效減少 btree 索引的節(jié)點(diǎn)數(shù)量：

壓縮元數(shù)據(jù)的設(shè)計(jì)

對于InnoDB索引這樣有序的數(shù)據(jù)鏈，可以依賴前面的記錄作為前綴壓縮的 prefix base，也可以將 prefix base 額外存儲下來。但由于 InnoDB index 的 update-in-place 導(dǎo)致 record 是動態(tài)的，所以前者為動態(tài) prefix base，而后者一般設(shè)計(jì)為（半）靜態(tài) prefix base。對于前者，在 base record 變遷情況下，由于依賴的壓縮 record 可能膨脹，可能會進(jìn)一步導(dǎo)致原來 optimistic 操作變成 pessimistic 的，引起明顯性能下降，并加劇代碼復(fù)雜性導(dǎo)致風(fēng)險(xiǎn)。因此，PolarDB 這里采用的是半靜態(tài) prefix base 設(shè)計(jì)。

PolarDB 在 page 內(nèi)部新建 symbol table 存放壓縮所需要的元信息，根據(jù)壓縮算法的不同，元信息可以是字典信息、前綴信息等等。

symbol table 放在 page 中，可以實(shí)現(xiàn) page 自解析，避免讀取時(shí)額外的 IO，并且解壓 record 是開銷非常小的純內(nèi)存操作。

symbol table 的物理位置在 system record 之后 user record 之前，也就是 page heap 的起始位置。一旦某個(gè)版本的 symbol table 確定之后，除非發(fā)生完整的 symbol table 更新，其內(nèi)容是不會進(jìn)行修改的，因此我們稱之為半靜態(tài)的。symbol table 內(nèi)部有版本信息、元數(shù)據(jù)信息和元數(shù)據(jù)索引信息等等內(nèi)容，用來實(shí)現(xiàn) record 的快速壓縮和解壓。

數(shù)據(jù)的壓縮

以 insert 為例，當(dāng)經(jīng)過事務(wù)處理、記錄構(gòu)建、索引定位等等操作后，最終會走到 btree 操作的底層函數(shù)中。這里會將獲取的 dtuple_t 轉(zhuǎn)換成 rec_t 選定（樂觀/悲觀）模式后插入數(shù)據(jù)，這時(shí)候應(yīng)該要考慮壓縮邏輯了。我們此時(shí)已經(jīng)拿了所需的 page 鎖，因此可以保證 page 內(nèi)相關(guān)信息的獨(dú)占性，所有需要 page 中壓縮輔助信息內(nèi)容的行壓縮可以在這一步實(shí)現(xiàn)。在這一過程中進(jìn)行壓縮使得 rec_t 中的數(shù)據(jù)為壓縮數(shù)據(jù)，同時(shí)需要在 rec_t 保留相關(guān)的元信息。

對于前綴壓縮，我們采取壓縮的時(shí)機(jī)是 lazy 的，即新插入的 record 在 page 上保持非壓縮狀態(tài)，等到 page 容量觸發(fā)閾值時(shí)，再對 page 整體進(jìn)行壓縮，這樣保證壓縮開銷被均攤到多次 DML 操作上，而不會每次操作都有壓縮開銷。

而觸發(fā) encode 閾值是在 optimistic 路徑的 page 滿且判斷 reorganize 也無法騰出空間時(shí)觸發(fā)。原本會放鎖進(jìn)入 SMO 流程，我們這里先嘗試 page 級別整體的encode。

不在 SMO 時(shí)做壓縮是因?yàn)槠涑钟?index latch 和多個(gè) page latch，對并發(fā)操作的影響范圍太大，其次 page 內(nèi)部的壓縮不需要依賴其他信息。page 級別的壓縮會嘗試對所有記錄進(jìn)行最優(yōu)化選取前綴壓縮元信息，并判斷對應(yīng)生成的新 symbol table 是否會有足夠收益，有則壓縮數(shù)據(jù)并更新。

我們在 record 的 Info bits 上拓展了一個(gè) bit 來表征此記錄是否是壓縮格式，老版本記錄對應(yīng)標(biāo)志不會被設(shè)置從而完全兼容原有操作路徑。在一個(gè) page 頁內(nèi)可以同時(shí)存在壓縮和非壓縮兩種類型的記錄，根據(jù)對應(yīng)標(biāo)志位判斷處理模式。

數(shù)據(jù)的解壓

首先需要保證在所有 record 使用路徑上，解壓邏輯能夠全面覆蓋，讓用戶拿到原始記錄。其次，InnoDB 內(nèi)部也存在 dtuple_t（內(nèi)存記錄格式）和 rec_t（頁上物理記錄格式）兩種 record 格式類型的轉(zhuǎn)換與比較。當(dāng)數(shù)據(jù)前綴壓縮后可能失去列屬性，因此 rec_get_offsets 等函數(shù)無法對壓縮后的 rec_t 直接解析，需要對應(yīng)的改造相應(yīng)函數(shù)獲取 rec_t 中的物理數(shù)據(jù)偏移。另外，InnoDB 記錄的比較是基于列的，offsets 本質(zhì)是輔助解析 rec_t 至各列的結(jié)構(gòu)，只要保證相應(yīng)信息能將壓縮部分?jǐn)?shù)據(jù)也能解析出來，就可以用壓縮 rec_t、壓縮元信息以及對應(yīng)的 offsets，去和 dtuple_t 轉(zhuǎn)換或比較?？偟膩碚f，對于壓縮的 record，要么先完全解壓構(gòu)建原來的 rec_t 數(shù)據(jù)走原來比較邏輯，要么用改造過的 offsets 或 dtuple_t 以及對應(yīng)的列比較執(zhí)行函數(shù)來做比較（可解釋壓縮計(jì)算）。PolarDB 目前在不同路徑上會根據(jù)環(huán)境條件從兩種方式中選擇之一。

前綴壓縮的典型應(yīng)用

對于如 SaaS/電商場景等一些用戶，其數(shù)據(jù)表中存在較多的索引可以通過前綴壓縮的降低存儲成本。并且我們和客戶了解到很多情況下, 表數(shù)據(jù)中有大量的冗余重復(fù)數(shù)據(jù), 雖然單表中總共有 1 億行, 但是某一行, 比如是品類只有 200 種左右, 這種是最常見的場景.

這種場景在 sysbench-toolkit 里面是 saas_multi_index 場景: https://github.com/baotiao/sysbench-toolkit

從下面的測試數(shù)據(jù)可以看到, 在 Saas/電商等典型場景里面, 前綴壓縮可以在獲得比較高的壓縮率同時(shí)提升整體讀寫性能。

IO Bound 場景

表結(jié)構(gòu)如下

CREATE TABLE `prefix_off_saas_log_10w%d` (
  `id` bigint(20) NOT NULL AUTO_INCREMENT,
  `saas_type` varchar(64) DEFAULT NULL,
  `saas_currency_code` varchar(3) DEFAULT NULL,
  `saas_amount` bigint(20) DEFAULT '0',
  `saas_direction` varchar(2) DEFAULT 'NA',
  `saas_status` varchar(64) DEFAULT NULL,
  `ewallet_ref` varchar(64) DEFAULT NULL,
  `merchant_ref` varchar(64) DEFAULT NULL,
  `third_party_ref` varchar(64) DEFAULT NULL,
  `created_date_time` datetime DEFAULT NULL,
  `updated_date_time` datetime DEFAULT NULL,
  `version` int(11) DEFAULT NULL,
  `saas_date_time` datetime DEFAULT NULL,
  `original_saas_ref` varchar(64) DEFAULT NULL,
  `source_of_fund` varchar(64) DEFAULT NULL,
  `external_saas_type` varchar(64) DEFAULT NULL,
  `user_id` varchar(64) DEFAULT NULL,
  `merchant_id` varchar(64) DEFAULT NULL,
  `merchant_id_ext` varchar(64) DEFAULT NULL,
  `mfg_no` varchar(64) DEFAULT NULL,
  `rfid_tag_no` varchar(64) DEFAULT NULL,
  `admin_fee` bigint(20) DEFAULT NULL,
  `ppu_type` varchar(64) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `saas_log_idx01` (`user_id`) USING BTREE,
  KEY `saas_log_idx02` (`saas_type`) USING BTREE,
  KEY `saas_log_idx03` (`saas_status`) USING BTREE,
  KEY `saas_log_idx04` (`merchant_ref`) USING BTREE,
  KEY `saas_log_idx05` (`third_party_ref`) USING BTREE,
  KEY `saas_log_idx08` (`mfg_no`) USING BTREE,
  KEY `saas_log_idx09` (`rfid_tag_no`) USING BTREE,
  KEY `saas_log_idx10` (`merchant_id`)
  ) ENGINE=InnoDB AUTO_INCREMENT=0 DEFAULT CHARSET=utf8

IO Bound 場景隨機(jī)讀，采用隨機(jī) point read，128線程，4G Buffer Pool，二級索引大小 20G，壓縮后 3.5G。測得壓縮后 QPS 是 49w，非壓縮是 26w，壓縮是非壓縮的 1.88 倍。

可以看到再開啟了壓縮之后, 性能并沒有下降, 而是有一定程度的提升, 原因如下:

壓縮可以減少btree葉子節(jié)點(diǎn)的數(shù)量，在 IO bound 場景增加了 buffer pool 對葉子節(jié)點(diǎn)的覆蓋率，覆蓋更多的 page 意味著隨機(jī)讀場景更少的 page 換入換出，對 bp 的 hash table 和 lru list 訪問頻率更小，hash 鎖和 lru list 鎖競爭更少，此外，對文件系統(tǒng)的 IO 次數(shù)更少，用戶線程直接命中 BP 即可返回。

CPU Bound 場景

CPU Bound 場景隨機(jī)寫（index鎖沖突），256 線程，100G Buffer Pool 足夠大，單表，一個(gè)二級索引，為了效果更加明顯，將二級索引的行長設(shè)置為 500，insert 場景，測得壓縮 10w QPS，非壓縮 8w QPS，壓縮是非壓縮的 1.25 倍。

page 中 record 密度更大，減少了 page 分裂頻率，緩解了分裂對 index SX 鎖的爭搶，而且減少了正在分裂節(jié)點(diǎn)的父節(jié)點(diǎn)拿的 X 鎖數(shù)量，緩解了對其葉子節(jié)點(diǎn)的插入。此外，為了減少開啟壓縮后 SMO 時(shí)拿 index 鎖時(shí)間，壓縮路徑不覆蓋 SMO 過程。

CPU Bound場景隨機(jī)讀，壓縮和非壓縮性能差不多。

在 bp 足夠大時(shí)進(jìn)行隨機(jī)讀取，那么壓縮并不會帶來性能提升，但訪問壓縮 record 會帶來一定解壓開銷，但解壓開銷很?。▋?nèi)存的隨機(jī)訪問），因此讀取性能差不多。

壓縮率

還有一個(gè)比較關(guān)心的問題就是壓縮效率，目前每個(gè) page 有 symbol table，記錄了公共前綴，且一個(gè) record 壓縮到最后是有一部分元數(shù)據(jù)的。所以并不是 record 越大，壓縮率就一定會更好的。假設(shè)公共前綴部分基本占據(jù)了整個(gè) record，那么經(jīng)過演算得到壓縮率隨 record size 的變化曲線是拋物線，由于默認(rèn) row 格式時(shí) dynamic，其index key長度限制是 3072Bytes，相當(dāng)于 1024 個(gè) utf8 字符，這個(gè)值小于壓縮率取到極值的點(diǎn)。

測試結(jié)果:

測試二級索引大小對壓縮率的影響，探討壓縮的極限壓縮率。單線程順序insert 400w～800w條數(shù)據(jù)，datasize不超過128的插入800w行，datasize大于128的插入400w行。采用最大的重復(fù)率，即每個(gè)page里面只有幾種rec。data size是二級索引字段的大小，單位是utf8字符，data size為32相當(dāng)于96Bytes，其未壓縮的索引大小是壓縮的2.92倍。注意，不同灌數(shù)據(jù)方式會導(dǎo)致不同的壓縮率，這里測的是單線程隨機(jī)插入，壓縮效率優(yōu)于多線程并發(fā)插入，因?yàn)椴l(fā)插入可能導(dǎo)致不必要的page分裂。