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

背景

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

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

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

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

PolarDB 前綴壓縮

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

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

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

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

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

前綴壓縮設計原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

前綴壓縮的典型應用

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

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

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

IO Bound 場景

表結構如下

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

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

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

CPU Bound 場景

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

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

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

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

壓縮率

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

測試結果:

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