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

背景

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

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

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

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

PolarDB 前綴壓縮

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

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

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

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

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

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

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

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

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

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

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

對(duì)于InnoDB索引這樣有序的數(shù)據(jù)鏈，可以依賴前面的記錄作為前綴壓縮的 prefix base，也可以將 prefix base 額外存儲(chǔ)下來(lái)。但由于 InnoDB index 的 update-in-place 導(dǎo)致 record 是動(dòng)態(tài)的，所以前者為動(dòng)態(tài) prefix base，而后者一般設(shè)計(jì)為（半）靜態(tài) prefix base。對(duì)于前者，在 base record 變遷情況下，由于依賴的壓縮 record 可能膨脹，可能會(huì)進(jìn)一步導(dǎo)致原來(lái) 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 是開(kāi)銷非常小的純內(nèi)存操作。

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

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

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

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

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

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

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

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

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

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

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

這種場(chǎng)景在 sysbench-toolkit 里面是 saas_multi_index 場(chǎng)景: https://github.com/baotiao/sysbench-toolkit

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

IO Bound 場(chǎng)景

表結(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 場(chǎng)景隨機(jī)讀，采用隨機(jī) point read，128線程，4G Buffer Pool，二級(jí)索引大小 20G，壓縮后 3.5G。測(cè)得壓縮后 QPS 是 49w，非壓縮是 26w，壓縮是非壓縮的 1.88 倍。

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

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

CPU Bound 場(chǎng)景

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

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

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

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

壓縮率

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

測(cè)試結(jié)果:

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