[[430923]]

前言

最近分析型數(shù)據(jù)庫在資本市場和技術(shù)社區(qū)都非常的火熱，各種創(chuàng)業(yè)公司的創(chuàng)新型產(chǎn)品如雨后春筍般出現(xiàn)。這一方面是因為當前階段企業(yè)日益依賴從數(shù)據(jù)中尋找增長潛力帶來需求的增長，另一方面云原生技術(shù)的發(fā)展帶來現(xiàn)有技術(shù)體系的進化和變革，諸如Snowflakes這類產(chǎn)品的成功證明，使用云原生技術(shù)再造分析型數(shù)據(jù)庫技術(shù)體系是必要的且存在很大的市場機會。

PolarDB MySQL是因云而生的一個數(shù)據(jù)庫系統(tǒng), 除了云上OLTP場景，大量客戶也對PolarDB提出了實時數(shù)據(jù)分析的性能需求。對此PolarDB技術(shù)團隊提出了In-Memory Column Index(IMCI）的技術(shù)方案，在復雜分析查詢場景獲得的數(shù)百倍的加速效果。

本文闡述了IMCI背后技術(shù)路線的思考和具體方案的取舍。PolarDB MySQL 列存分析功能即將在阿里云上線，敬請期待。

一  MySQL生態(tài)HTAP數(shù)據(jù)庫解決方案

MySQL是一款主要面向OLTP型場景設(shè)計的開源數(shù)據(jù)庫，開源社區(qū)的研發(fā)方向側(cè)重于加強其事務(wù)處理的能力，如提升單核性能/多核擴展性/增強集群能力以提升可用性等。在處理大數(shù)據(jù)量下復雜查詢所需要的能力方面，如優(yōu)化器處理子查詢的能力，高性能算子HashJoin, SQL并行執(zhí)行等，社區(qū)一直將其放在比較低優(yōu)先級上，因此MySQL的數(shù)據(jù)分析能力提升進展緩慢。

隨著MySQL發(fā)展為世界上最為流行的開源數(shù)據(jù)庫系統(tǒng)，用戶在其中存儲了大量的數(shù)據(jù)，并且運行著關(guān)鍵的業(yè)務(wù)邏輯，對這些數(shù)據(jù)進行實時分析成為一個日益增長的需求。當單機MySQL不能滿足需求時，用戶尋求一個更好的解決方案。

1  MySQL + 專用AP數(shù)據(jù)庫的搭積木方案

專用分析型數(shù)據(jù)庫產(chǎn)品選項眾多，一個可選方案是使用兩套系統(tǒng)來分別滿足的OLTP和OLAP型需求，在兩套系統(tǒng)中間通過數(shù)據(jù)同步工具等進行數(shù)據(jù)的實時同步。更進一步，用戶甚至可以增加一層proxy，自動將TP型負載路由到MySQL上，而將分析型負載路由到OLAP數(shù)據(jù)庫上，對應(yīng)用層屏蔽底層數(shù)據(jù)庫的部署拓撲。

這樣的架構(gòu)有其靈活之處，例如對于TP數(shù)據(jù)庫和AP數(shù)據(jù)庫都可以各自選擇最好的方案，而且實現(xiàn)了TP/AP負載的完全隔離。但是其缺點也是顯而易見的。首先，在技術(shù)上需要維護兩套不同技術(shù)體系的數(shù)據(jù)庫系統(tǒng)，其次由于兩套系統(tǒng)處理機制的差異，維護上下游的數(shù)據(jù)實時一致性也非常具有挑戰(zhàn)。而且由于同步延遲的存在，下游AP系統(tǒng)存儲的經(jīng)常是過時的數(shù)據(jù)，導致無法滿足實時分析的需求。

2  基于多副本的Divergent Design方法

隨著互聯(lián)網(wǎng)而興起的新興數(shù)據(jù)庫產(chǎn)品很多都兼容了MySQL協(xié)議，因此成為替代MySQL的一個可選項。而這些分布式數(shù)據(jù)庫產(chǎn)品大部分采用了分布式Share Nothing的方案，其一個核心特點是使用分布式一致性協(xié)議來保障單個partition多副本之間的數(shù)據(jù)一致性。由于一份數(shù)據(jù)在多個副本之間上完全獨立，因此在不同副本上使用不同格式進行存儲，來服務(wù)不同的查詢負載是一個易于實施的方案。典型的如TiDB，其從TiDB4.0開始，在一個Raft Group中的其中一個副本上，使用列式存儲(TiFlash)來響應(yīng)AP型負載, 并通過TiDB的智能路由功能來自動選取數(shù)據(jù)來源。這樣實現(xiàn)了一套數(shù)據(jù)庫系統(tǒng)同時服務(wù)OLTP型負載和OLAP型負載。

該方法在諸多Research及Industry領(lǐng)域的工作中都被借鑒并使用，并日益成為分布式數(shù)據(jù)領(lǐng)域一體化HTAP的事實標準方案。但是應(yīng)用這個方案的前提是用戶需要遷移到對應(yīng)的NewSQL數(shù)據(jù)庫系統(tǒng)，而這往往帶來各種兼容性適配問題。

3  一體化的行列混合存儲方案

比多副本Divergent Design方法更進一步的，是在同一個數(shù)據(jù)庫實例中采用行列混合存儲的方案，同時響應(yīng)TP型和AP型負載。這是傳統(tǒng)商用數(shù)據(jù)庫Oracle/SQL Server/DB2等不約而同采用的方案。

• Oracle公司在在2013年發(fā)表的Oracle 12C上，發(fā)布了Database In-Memory套件，其最核心的功能即為In-Memory Column Store，通過提供行列混合存儲/高級查詢優(yōu)化(物化表達式，JoinGroup)等技術(shù)提升OLAP性能。

• 微軟在SQL Server 2016 SP1上，開始提供Column Store Indexs功能，用戶可以根據(jù)負載特征，靈活的使用純行存表，純列存表，行列混合表，列存表+行存索引等多種模式。

• IBM在2013年發(fā)布的10.5版本(Kepler)中，增加了DB2 BLU Acceleration組件，通過列式數(shù)據(jù)存儲配合內(nèi)存計算以及DataSkipping技術(shù)，大幅提升分析場景的性能。

三家領(lǐng)先的商用數(shù)據(jù)庫廠商，均同時采用了行列混合存儲結(jié)合內(nèi)存計算的技術(shù)路線，這是有其底層技術(shù)邏輯的：列式存儲由于有更好的IO效率(壓縮,DataSkipping,列裁剪)以及CPU計算效率(Cache Friendly), 因此要達到最極致的分析性能必須使用列式存儲，而列式存儲中索引稀疏導致的索引精準度問題決定它不可能成為TP場景的存儲格式，如此行列混合存儲成為一個必選方案。但在行列混合存儲架構(gòu)中，行存索引和列存索引在處理隨機更新時存在性能鴻溝, 必須借助DRAM的低讀寫延時來彌補列式存儲更新效率低的問題。因此在低延時在線事務(wù)處理和高性能實時數(shù)據(jù)分析兩大前提下，行列混合存儲結(jié)合內(nèi)存計算是唯一方案。

對比上述三種方法，從組合搭積木的方法到Divergent Design方法再到一體化的行列混合存儲，其集成度越來越高，用戶的使用體驗也越來越好。但是其對內(nèi)核工程實現(xiàn)上的挑戰(zhàn)也一個比一個大?；A(chǔ)軟件的作用就是把復雜留給自己把簡單留給用戶，因此一體化的方法是符合技術(shù)發(fā)展趨勢的。

二  PolarDB MySQL AP能力的演進

PolarDB MySQL能力棧與開源MySQL類似，長于TP但AP能力較弱。由于PolarDB提供了最大單實例100TB的存儲能力，同時其事務(wù)處理能力遠超用戶自建MySQL。因此PolarDB用戶傾向于在單實例上存儲更多的數(shù)據(jù)，同時會在這些數(shù)據(jù)上運行一些復雜聚合查詢。借助于PolarDB一寫多讀的架構(gòu)，用戶可以增加只讀的RO節(jié)點以運行復雜只讀查詢，從而避免分析型查詢對TP負載的干擾。

1  MySQL的架構(gòu)在AP場景的缺陷

MySQL的實現(xiàn)架構(gòu)在執(zhí)行復雜查詢時性能差有多個方面的原因，對比專用的OLAP系統(tǒng)，其性能瓶頸體現(xiàn)多個方面：

1. MySQL的SQL執(zhí)行引擎基于流式迭代器模型(Volcano Iterator)實現(xiàn), 這個架構(gòu)在工程實現(xiàn)上依賴大量深層次的函數(shù)嵌套及虛函數(shù)調(diào)用，在處理海量數(shù)據(jù)時，這種架構(gòu)會影響現(xiàn)代CPU流水線的pipline效率，導致CPU Cache效率低下。同時Iterator執(zhí)行模型也無法充分發(fā)揮現(xiàn)代CPU提供的SIMD指令來做執(zhí)行加速。

2. 執(zhí)行引擎只能串行執(zhí)行，無法發(fā)揮現(xiàn)代多核CPU的并行話能力。官方從MySQL 8.0開始，在一些count(*)等基本查詢上增加并行執(zhí)行的能力，但是復雜SQL的并行執(zhí)行能力構(gòu)建依然任重道遠。

3. MySQL最常用的存儲引擎都是按行存儲，在按列進行海量數(shù)據(jù)分析時，按行從磁盤讀取數(shù)據(jù)存在非常大的IO帶寬浪費。其次行式存儲格式在處理大量數(shù)據(jù)時大量拷貝不必要的列數(shù)據(jù)，對內(nèi)存讀寫效率也存在沖擊。

2  PolarDB 并行查詢突破CPU瓶頸

PolarDB團隊開發(fā)的并行查詢框架（Parallel Query), 可以在當查詢數(shù)據(jù)量到達一定閾值時，自動啟動并行執(zhí)行，在存儲層將數(shù)據(jù)分片到不同的線程上，多個線程并行計算，將結(jié)果流水線匯總到總線程，最后總線程做些簡單歸并返回給用戶，提高查詢效率。

并行查詢的加入使得PolarDB突破了單核執(zhí)行性能的限制，利用多核CPU的并行處理能力，在PolarDB上部分SQL查詢耗時成指數(shù)級下降。

3  Why We Need Column-Store

并行執(zhí)行框架突破了CPU擴展能力的限制，帶來了顯著的性能提升。然而受限于行式存儲及行式執(zhí)行器的效率限制，單核執(zhí)行性能存在天花板，其峰值性能依然與專用的OLAP系統(tǒng)存在差距。要更進一步的提升PolarDB MySQL的分析性能，我們需要引入列式存儲：

1. 在分析場景經(jīng)常需要訪問某個列的大量記錄，而列存按列拆分存儲的方式會避免讀取不需要的列。其次列存由于把相同屬性的列連續(xù)保存，其壓縮效率也遠超行存，通常可以達到10倍以上。最后列存中大塊存儲的結(jié)構(gòu)，結(jié)合MIN/MAX等粗糙索引信息可以實現(xiàn)大范圍的數(shù)據(jù)過濾。所有這些行為都極大的提升了IO的效率。在現(xiàn)今存儲計算分離的架構(gòu)下，減少通過網(wǎng)絡(luò)讀取的數(shù)據(jù)量可以對查詢處理的響應(yīng)時間帶來立竿見影的提升。

2. 列式存儲同樣能提高CPU在處理數(shù)據(jù)時的執(zhí)行效率，首先列存的緊湊排列方式可提升CPU訪問內(nèi)存效率，減少L1/L2 Cache miss導致的執(zhí)行停頓。其次在列式存儲上可以使用應(yīng)用SIMD技術(shù)進一步提升單核吞吐能力，而這是現(xiàn)代高性能分析執(zhí)行引擎的通用技術(shù)路線（Oracle/SQL Server/ClickHouse).

三  PolarDB In-Memory Column Index

PolarDB In-Memory Column Index功能為PolarDB帶來列式存儲以及內(nèi)存計算能力，讓用戶可以在一套PolarDB數(shù)據(jù)庫上同時運行TP和AP型混合負載，在保證現(xiàn)有PolarDB優(yōu)異的OLTP性能的同時，大幅提升PolarDB在大數(shù)據(jù)量上運行復雜查詢的性能。

In-Memory Column Index使用行列混合存儲技術(shù)，同時結(jié)合了PolarDB基于共享存儲一寫多讀的架構(gòu)特征，其包含如下幾個關(guān)鍵的技術(shù)創(chuàng)新點：

1. 在PolarDB的存儲引擎（InnoDB)上新增對列式索引（Columnar Index）的支持，用戶可以選擇通過DDL將一張表的全部列或者部分列創(chuàng)建為列索引，列索引采用列壓縮存儲，其存儲空間消耗會遠小于行存格式。默認列索引會全部常駐內(nèi)存以實現(xiàn)最大化分析性能，但是當內(nèi)存不夠時也支持將其持久化到共享存儲上。

2. 在PolarDB的SQL執(zhí)行器層，我們重寫了一套面向列存的執(zhí)行器引擎框架(Column-oriented), 該執(zhí)行器框架充分利用列式存儲的優(yōu)勢，如以4096行的一個Batch為單位訪問存儲層的數(shù)據(jù)，使用SIMD指令提升CPU單核心處理數(shù)據(jù)的吞吐，所有關(guān)鍵算子均支持并行執(zhí)行。在列式存儲上，新的執(zhí)行器對比MySQL原有的行存執(zhí)行器性有幾個數(shù)量級的性能提升。

3. 支持行列混合執(zhí)行的優(yōu)化器框架，該優(yōu)化器框架會根據(jù)下發(fā)的SQL是否能在列索引上執(zhí)行覆蓋查詢，并且其所依賴的的函數(shù)及算子能被列式執(zhí)行器所支持來決定是否啟動列式執(zhí)行。優(yōu)化器會同時對行存執(zhí)行計劃和列存執(zhí)行計劃做代價估算，并選中代價交代的執(zhí)行計劃。

4. 用戶可以使用PolarDB集群中的一個RO節(jié)點作為分析型節(jié)點，在該RO節(jié)點上配置生成列存索引，復雜查詢運行在列存索引上并使用所有可用CPU的計算能力，在獲得最大執(zhí)行性能的同時不影響該集群上的TP型負載的可用內(nèi)存和CPU資源。

幾個關(guān)鍵關(guān)鍵技術(shù)結(jié)合使得PolarDB成為了一個真正的HTAP數(shù)據(jù)庫系統(tǒng)，其在大數(shù)據(jù)量上運行復雜查詢的性能可以與Oracle/SQL Server等業(yè)界最頂尖的商用數(shù)據(jù)庫系統(tǒng)處在同一水平。

四  In-Memory Column Index的技術(shù)架構(gòu)

1  行列混合的優(yōu)化器

PolarDB原生有一套面向行存的優(yōu)化器組件，在引擎層增加對列存功能支持之后，此部分需要進行功能增強，優(yōu)化器需要能夠判斷一個查詢應(yīng)該被調(diào)度到行存執(zhí)行還是列存執(zhí)行。我們通過一套白名單機制和執(zhí)行代價計算框架來完成此項任務(wù)。系統(tǒng)保證對支持的SQL進行性加速，同時兼容運行不支持的SQL.

如何實現(xiàn)100%的MySQL兼容性

我們通過一套白名單機制來實現(xiàn)兼容性目標。使用白名單機制是基于如下幾點考量。第一點考慮到系統(tǒng)可用資源（主要是內(nèi)存）的限制，一般不會在所有的表的所有上都創(chuàng)建列索引，當一個查詢語句需要使用到列不在列存中存在時，其不能在列存上執(zhí)行。第二點，基于性能的的考量，我們完全重寫了一套面向列存的SQL執(zhí)行引擎，包括其中所有的物理執(zhí)行算子和表達式計算，其所覆蓋的場景相對MySQL原生行存能夠支持的范圍有欠缺。當下發(fā)的SQL中包含一些IMCI執(zhí)行引擎不能支持的算子片段或者列類型時，需要能能夠識別攔截并切換回行存執(zhí)行。

查詢計劃轉(zhuǎn)換

Plan轉(zhuǎn)換的目的是將MySQL的原生邏輯執(zhí)行計劃表示方式AST轉(zhuǎn)換為IMCI的Logical Plan。在生成IMCI的Logical Plan之后，會經(jīng)過一輪Optimize過程，生成Physical Plan。Plan轉(zhuǎn)換的方法簡單直接，只需要遍歷這個執(zhí)行計劃樹，將 mysql 優(yōu)化后的 AST 轉(zhuǎn)換成IMCI 以 relation operator 位節(jié)點的樹狀結(jié)構(gòu)即可，是一個比較直接的翻譯過程。不過在這個過程中，也會做一部分額外的事情，如進行類型的隱式轉(zhuǎn)換，以兼容MySQL靈活的類型系統(tǒng)。

兼顧行列混合執(zhí)行的優(yōu)化器

有行存和列存兩套執(zhí)行引擎的存在，優(yōu)化器在選擇執(zhí)行計劃時有了更多的選擇，其可以對比行存執(zhí)行計劃的Cost和列存執(zhí)行計劃的Cost，并使用代價最低的那個執(zhí)行計劃.

在PolarDB中除了有原生MySQL的行存串行執(zhí)行，還有能夠發(fā)揮多核計算能力的基于行存的Paralle Query功能。因此實際優(yōu)化器會在1)行存串行執(zhí)行，2）行存Paralle Query 3)IMCI 三個選項之中選擇。在目前的迭代階段，優(yōu)化器按如下的流程操作：

• 1.執(zhí)行SQL的Parse過程并生成LogicalPlan，然后調(diào)用MySQL原生優(yōu)化器按照執(zhí)行一定優(yōu)化操作，如join order調(diào)整等。同時該階段獲得的邏輯執(zhí)行計劃會轉(zhuǎn)給IMCI的執(zhí)行計劃編譯模塊,嘗試生成一個列存的執(zhí)行計劃(此處可能會被白名單攔截并fallback回行存）。

• 2.PolarDB的Optimizer會根據(jù)行存的Plan,計算得出一個面向行存的執(zhí)行Cost。如果此Cost超過一定閾值，則會嘗試下推到IMCI執(zhí)行器使用IMCI_Plan進行執(zhí)行。

• 3.如果IMCI無法執(zhí)行此SQL，則PolarDB會嘗試編譯出一個Parallel Query的執(zhí)行計劃并執(zhí)行。如果無法生成PQ的執(zhí)行計劃，則說明IMCI和PQ均無法支持此SQL，fallback回行存執(zhí)行。

上述策略是基于這樣一個判斷，從執(zhí)行性能對比，行存串行執(zhí)行 < 行存并行執(zhí)行 < IMCI。從SQL兼容性上看，IMCI < 行存并行執(zhí)行 < 行存串行執(zhí)行。但是實際情況會更復雜，例如某些情況下，基于行存有序索引覆蓋的并行Index Join會比基于列存的Sort Merge join有更低的Cost. 目前的策略下可能就選擇了IMCI 列存執(zhí)行。

2  面向列式存儲的執(zhí)行引擎

IMCI執(zhí)行引擎是一套面向列存優(yōu)化,并完全獨立于現(xiàn)有MySQL行式執(zhí)行器的一個實現(xiàn)，重寫執(zhí)行器的目的是為了消除現(xiàn)有行存執(zhí)行引擎在執(zhí)行分析型SQL時效率低兩個關(guān)鍵瓶頸點：按行訪問導致的虛函數(shù)訪問開銷以及無法并行執(zhí)行。

支持BATCH并行的算子

IMCI執(zhí)行器引擎使用經(jīng)典的火山模型，但是借助了列存存儲以及向量執(zhí)行來提升執(zhí)行性能。

火山模型里，SQL生成的語法樹所對應(yīng)的關(guān)系代數(shù)中，每一種操作會抽象為一個 Operator，執(zhí)行引擎會將整個 SQL 構(gòu)建成一個 Operator 樹，查詢樹自頂向下的調(diào)用Next()接口，數(shù)據(jù)則自底向上的被拉取處理。該方法的優(yōu)點是其計算模型簡單直接，通過把不同物理算子抽象成一個個迭代器。每一個算子只關(guān)心自己內(nèi)部的邏輯即可，讓各個算子之間的耦合性降低，從而比較容易寫出一個邏輯正確的執(zhí)行引擎。

• 在IMCI的執(zhí)行引擎中，每個Operator也使用迭代器函數(shù)來訪問數(shù)據(jù)，但不同的是每次調(diào)用迭代器會返回一批的數(shù)據(jù)，而不是一行，可以認為這是一個支持batch處理的火山模型。

• 串行執(zhí)行受制于單核計算效率，訪存延時，IO延遲等限制，執(zhí)行能力有限。而IMCI執(zhí)行器在幾個關(guān)鍵物理算子（Scan/Join/Agg等)上均支持并行執(zhí)行。除物理算子需要支持并行外，IMCI的優(yōu)化器需要支持生成并行執(zhí)行計劃，優(yōu)化器在確定一個表的訪問方式時，會根據(jù)需要訪問的數(shù)據(jù)量來決定是否啟用并行執(zhí)行，如果確定啟用并行執(zhí)行，則會參考一系列狀態(tài)數(shù)據(jù)決定并行度：包括當前系統(tǒng)可用的CPU/Memory/IO資源, 目前已經(jīng)調(diào)度和在排隊的任務(wù)信息, 統(tǒng)計信息, query 的復雜程度, 用戶可配置的參數(shù)等。根據(jù)這些數(shù)據(jù)計算出一個推薦的DOP值給算子, 而一個算子內(nèi)部會使用相同的DOP。同時DOP也支持用戶使用Hint的方式進行設(shè)定。

向量化執(zhí)行解決了單核執(zhí)行效率的問題，而并行執(zhí)行突破了單核的計算瓶頸。二者結(jié)合使得IMCI執(zhí)行速度相比傳統(tǒng)MySQL行式執(zhí)行有了數(shù)量級的速度提升。

SIMD向量化計算加速

AP型場景，SQL中經(jīng)常會包含很多涉及到一個或者多個值/運算符/函數(shù)組成的計算過程，這都是屬于表達式計算的范疇。表達式的求值是一個計算密集型的任務(wù)，因此表達式的計算效率是影響整體性能的一個關(guān)鍵的因素。

傳統(tǒng)MySQL的表達式計算體系以一行為一個單位的逐行運算，一般稱其為迭代器模型實現(xiàn)。由于迭代器對整張表進行了抽象，整個表達式實現(xiàn)為一個樹形結(jié)構(gòu)，其實現(xiàn)代碼易于理解，整個處理的過程非常清晰。

但這種抽象會同時帶來性能上的損耗，因為在迭代器進行迭代的過程中，每一行數(shù)據(jù)的獲取都會引發(fā)多層的函數(shù)調(diào)用，同時逐行地獲取數(shù)據(jù)會帶來過多的 I/O，對緩存也不友好。MySQL采用樹形迭代器模型，是受到存儲引擎訪問方法的限制，這導致其很難對復雜的邏輯計算進行優(yōu)化。

在列存格式下，由于每一列的數(shù)據(jù)都單獨順序存儲，涉及到某一個特定列上的表達式計算過程都可以批量進行。對每一個計算表達式，其輸入和輸出都以Batch為單位，在Batch的處理模式下，計算過程可以使用SIMD指令進行加速。新表達式系統(tǒng)有兩項關(guān)鍵優(yōu)化：

• 充分利用列式存儲的優(yōu)勢，使用分批處理的模型代替迭代器模型，我們使用SIMD指令重寫了大部分常用數(shù)據(jù)類型的表達式內(nèi)核實現(xiàn)，例如所有數(shù)字類型(int, decimal, double)的基本數(shù)學運算(+, -, *, /, abs)，全部都有對應(yīng)的SIMD指令實現(xiàn)。在AVX512指令集的加持下, 單核運算性能獲得會數(shù)倍的提升。

• 采用了與Postgres類似表達式實現(xiàn)方法：在SQL編譯及優(yōu)化階段，IMCI的表達式以一個樹形結(jié)構(gòu)來存儲(與現(xiàn)有行式迭代器模型的表現(xiàn)方法類似)，但是在執(zhí)行之前會對該表達式樹進行一個后序遍歷，將其轉(zhuǎn)換為一維數(shù)組來存儲，在后續(xù)計算時只需要遍歷該一維數(shù)組結(jié)構(gòu)即可以完成運算。由于消除了樹形迭代器模型中的遞歸過程，計算效率更高。同時該方法對計算過程提供簡潔的抽象，將數(shù)據(jù)和計算過程分離，天然適合并行計算。

3  支持行列混合存儲的存儲引擎

事務(wù)型應(yīng)用和分析型應(yīng)用對存儲引擎有著截然不同的要求，前者要求索引可以精確定位到每一行并支持高效的增刪改，而后者則需要支持高效批量掃描處理，這兩個場景對存儲引擎的設(shè)計要求完全不同，有時甚至是矛盾的。

因此設(shè)計一個一體化的存儲引擎能同時服務(wù)OLTP型和OLAP型負載非常具有挑戰(zhàn)性。目前市場上HTAP存儲引擎做的比較好的只有幾家有幾十年研發(fā)積累的大廠，如Oracle (In-Memory Column Store）/Sql Server(In Memory Column index）/DB2（BLU)等。如TiDB等只能通過將多副本集群中的一個副本調(diào)整為列存來支持HTAP需求。

一體化的HTAP存儲引擎一般使用行列混合的存儲方案，即引擎中同時存在行存和列存，行存服務(wù)于TP，列存服務(wù)于AP。相比于部署獨立一套OLTP數(shù)據(jù)庫 加一套OLAP數(shù)據(jù)庫來滿足業(yè)務(wù)需求，單一HTAP引擎具有如下的優(yōu)勢：

• 行存數(shù)據(jù)和列存數(shù)據(jù)具有實時一致性，能滿足很多苛刻的業(yè)務(wù)需求，所有數(shù)據(jù)寫入即可見于分析型查詢。

• 更低的成本，用戶可以非常方便的指定哪些列甚至一張表哪個范圍的存儲為列存格式用于分析。全量數(shù)據(jù)繼續(xù)以行存存儲。

• 管理運維方便，用戶無需關(guān)注數(shù)據(jù)在兩套系統(tǒng)之間同步及數(shù)據(jù)一致性問題。

PolarDB 采用了和Oracle/Sql Server等商用數(shù)據(jù)庫類似的行列混合存儲技術(shù)，我們稱之為In-Memory Column Index：

• 建表時可以指定部分表或者列為列存格式，或者對已有的表可以使用Alter table語句為其增加列存屬性，分析型查詢會自動使用列存格式來進行查詢加速。

• 列存數(shù)據(jù)默認壓縮格式存儲在磁盤上，并可以使用In-Memory Columbia Store Area來做緩存加速并加速查詢，傳統(tǒng)的行格式依然保存在BufferPool中供OLTP性負載使用。

• 所有事務(wù)的增刪改操作都會實時反應(yīng)到列存存儲上，保證事務(wù)級別的數(shù)據(jù)一致性。

實現(xiàn)一個行列混合的存儲引擎技術(shù)上非常困難，但是在InnoDB這樣一個成熟的面向OLTP負載優(yōu)化的存儲引擎中增加列存支持，又面臨不同的情況：

• 滿足OLTP業(yè)務(wù)的需求是第一優(yōu)先的，因此增加列存支持不能對TP性能太大影響。這要求我們維護列存必須足夠輕量，必要時需要犧牲AP性能保TP性能。

• 列存的設(shè)計無需考慮事務(wù)并發(fā)對數(shù)據(jù)的修改, 數(shù)據(jù)的unique check等問題，這些問題在行存系統(tǒng)中已經(jīng)被解決，而這些問題對ClickHouse等單獨的列存引擎是非常難以處理的。

• 由于有一個久經(jīng)考驗的行存系統(tǒng)的存在，列存系統(tǒng)出現(xiàn)任何問題，都可以切換回行存系統(tǒng)響應(yīng)查詢請求。

上述條件可謂有利有弊，這也影響了對PolarDB整個行列混合存儲的方案設(shè)計。

表現(xiàn)為Index的列存

在MySQL插件式的存儲引擎框架的架構(gòu)下，增加列存支持最簡單方案是實現(xiàn)一個單獨的存儲引擎，如Inforbright以及MarinaDB的ColumnStore都采用了這種方案。而PolarDB采用了將列存實現(xiàn)為InnoDB的二級索引的方案，主要基于如下幾點考量：

• InnoDB原生是支持多索引的，Insert/Update/Delete操作都會以行粒度apply到Primary Index和所有的Secondary Index上，并且保證事務(wù)。將列存實現(xiàn)為一個二級索引可以復用這套事務(wù)處理框架。

• 在數(shù)據(jù)編碼格式上，實現(xiàn)為二級索引的列存可以和其他行存索引使用完全一樣的內(nèi)格式，直接內(nèi)存拷貝即可，不需要考慮charset和collation等信息，這對上層執(zhí)行器也是完全透明的。

• 二級索引操作非常靈活，可以在建表時即指定索引所包含的列，也可以后續(xù)通過DDL語句對一個二級索引中包含的列進行增加或者刪除操作。例如用戶可以將需要分析的int/float/Double列加入列索引，而對于一般只需要點查但是又占用大量空間的text/blob字段，則可以保留在行存中。

• 崩潰恢復過程可以復用InnoDB的Redo事務(wù)日志模塊, 與現(xiàn)有實現(xiàn)無縫兼容。同時也方便支持PolarDB的物理復制過程，支持在獨立RO節(jié)點或者Standby節(jié)點上生成列存索引提供分析服務(wù)。

• 同時二級索引與主表有一樣的生命周期，方便管理。

如上圖所示，在PolarDB中所有Primary Index和Seconary Index都實現(xiàn)為一個B+Tree。而列索引在定義上是一個Index，但其實是一個虛擬的索引，用于捕獲對該索引覆蓋列的增刪改操作。

對于上面的表其主表(Primary Index）包含（C1,C2,C3,C4,C5) 5列數(shù)據(jù), Seconary Index索引包含(C2,C1) 兩列數(shù)據(jù), 在普通二級索引中，C2與C1編碼成一行保存在B+tree中。而其中的列存索引包含(C2,C3,C4)三列數(shù)據(jù). 在實際物理存儲時，會對三列進行拆分獨立存儲，每一列都會按寫入順序轉(zhuǎn)成列存格式。

列存實現(xiàn)為二級索引的另一個好處是執(zhí)行器的工程實現(xiàn)非常簡單，在MySQL中已經(jīng)存在覆蓋索引的概念，即一個查詢所需要的列都在一個二級索引中存儲，則可以直接利用這個二級索引中的數(shù)據(jù)滿足查詢需求，使用二級索引相對于使用Primary Index可以極大減少讀取的數(shù)據(jù)量進而提升查詢性能。當一個查詢所需要的列都被列索引覆蓋時，借助列存的加速作用，可以數(shù)十倍甚至數(shù)百倍的提升查詢性能。

列存數(shù)據(jù)組織

對ColumnIndex中每一列，其存儲都使用了無序且追加寫的格式，結(jié)合標記刪除及后臺異步compaction實現(xiàn)空間回收。其具體實現(xiàn)上有如下幾個關(guān)鍵點：

• 列索引中記錄按RowGroup進行組織，每個RowGroup中不同的列會各自打包形成DataPack。

• 每個RowGroup都采用追加寫，分屬每個列的DataPack也是采用追加寫模式。對于一個列索引，只有個Active RowGroup負責接受新的寫入。當該RowGroup寫滿之后即凍結(jié)，其包含的所有Datapack會轉(zhuǎn)為壓縮格保存到磁盤上，同時記錄每個數(shù)據(jù)塊的統(tǒng)計信息便于過濾。

• 列存RowGroup中每新寫入一行都會分配一個RowID用作定位，屬于一行的所有列都可以用該RowID計算定位，同時系統(tǒng)維護PK到RowID的映射索引，以支持后續(xù)的刪除和修改操作。

• 更新操作采用標記刪除的方式來支持，對于更新操作，首先根據(jù)RowID計算出其原始位置并設(shè)置刪除標記，然后在ActiveRowGroup中寫入新的數(shù)據(jù)版本。

• 當一個RowGroup中的無效記錄超過一定閾值，則會觸發(fā)后臺異步compaction操作，其作用一方面是回收空間，另一方面可以讓有效數(shù)據(jù)存儲更加緊湊，提升分析型查詢單的效率。 

  

采用這種數(shù)據(jù)組織方式一方面滿足了分析型查詢按列進行批量掃描過濾的要求。另一方面對于TP型事務(wù)操作影響非常小，寫入操作只需要按列追加寫到內(nèi)存即可，刪除操作只需要設(shè)置一個刪除標記位。而更新操作則是一個標記刪除附加一個追加寫。列存可以做到支持事務(wù)級別的更新同時，做到幾乎不影響OLTP的性能。

全量及增量行轉(zhuǎn)列

行轉(zhuǎn)列操作在兩種情況下會發(fā)生，第一種情況是使用DDL語句對部分列創(chuàng)建列索引(一般是業(yè)務(wù)對一個已有的表有新增分析型需求)，此時需要掃描全表數(shù)據(jù)以創(chuàng)建列索引。另一種情況是在事務(wù)操作過程中對于涉及到的列實時行專列。

對于全表行轉(zhuǎn)列的情形，我們使用并行掃描的方式對InnoDB的Primary Key進行掃描，并依次將所有涉及到的列轉(zhuǎn)換為列存形式，這一操作的速度非常快，其基本只受限于服務(wù)器可用的IO吞吐速度和可用CPU資源。該操作是一個online-DDL過程，不會阻塞在線業(yè)務(wù)的運行。

在一個表上建立列索引之后，所有的更新事務(wù)將會同步更新行存和列存數(shù)據(jù)，以保證二者的事務(wù)一致性。下圖演示了在IMCI功能關(guān)閉和開啟之間的差異性。在未開啟IMCI功能時，事務(wù)對所有行的更新都會先加鎖，然后再對數(shù)據(jù)頁進行修改，在事務(wù)提交之前會對所有加鎖的記錄一次性方所。在開啟IMCI功能之后，事務(wù)系統(tǒng)會創(chuàng)建一個列存更新緩存，在所有數(shù)據(jù)頁被修改的同時，會記錄所涉及到的列存的修改操作，在事務(wù)提交結(jié)束前，該更新緩存會應(yīng)用到列存系統(tǒng)。

在此實現(xiàn)下，列存存儲提供了與行存一樣的事務(wù)隔離級別。對于每個寫操作, RowGroup中的每一行都會記錄修改該行的事務(wù)編號，而對于每個標記刪除操作也會記錄該設(shè)置動作的事務(wù)編號。借助寫入事務(wù)號和刪除事務(wù)號，AP型查詢可以用非常輕量級的方式獲得一個全局一致性的快照。

列索引粗糙索引

由前述列的存儲格式可以看出, IMCI中所有的Datapack都采用無序且追加寫的方式, 因此無法像InnoDB的普通有序索引那樣的可以精準的過濾掉不符合要求的數(shù)據(jù)。在IMCI中，我們借助統(tǒng)計信息來進行數(shù)據(jù)塊過濾，以此來達到降低數(shù)據(jù)訪問單價的目的。

• 在每個Active Datapack終結(jié)寫入的時候，會預先進行計算，并生成Datapack所包含數(shù)據(jù)的最小值/最大值/數(shù)值的總和/空值的個數(shù)/記錄總條數(shù)等信息。所有這些信息會維護在DataPacks Meta元信息區(qū)域并常駐內(nèi)存。由于凍結(jié)的Datapack中還會存在數(shù)據(jù)的刪除操作，因此統(tǒng)計信息的更新維護會放到后臺完成。

• 對于查詢請求，會根據(jù)查詢條件將Datapacks分為相關(guān)、不相關(guān)、可能相關(guān)三大類，從而減少實際的數(shù)據(jù)塊訪問。而對于一些聚合查詢操作，如count/sum等，可以通過預先計算好的統(tǒng)計值進行簡單的運算得出，這些數(shù)據(jù)塊甚至都不需要進行解壓。

采用基于統(tǒng)計信息的粗糙索引方案對于一些需要精準定位部分數(shù)據(jù)的查詢并不是很友好。但是在一個行列混合存儲引擎中，列索引只需要輔助加速那些會涉及到大量數(shù)據(jù)掃描的查詢，在這個場景下使用列會具有顯著的優(yōu)勢。而對于那些只會訪問到少量數(shù)據(jù)的SQL，優(yōu)化器通常會基于代價模型計算得出基于行存會得到一個成本更低的方案。

行列混合存儲下的TP和AP資源隔離

PolarDB行列混合存儲可以支持在一個實例中同時支持AP型查詢和TP型查詢。但很多業(yè)務(wù)有很高的OLTP型負載，而突發(fā)性的OLAP性負載可能干擾到TP型業(yè)務(wù)的響應(yīng)時延。因此支持負載隔離在HTAP數(shù)據(jù)庫中是一個必須支持的功能。借助PolarDB一寫多讀的架構(gòu)，我們可以非常方便對AP型負載和TP型負載進行隔離。在PolarDB的技術(shù)架構(gòu)下，我們有如下幾個部署方式

• 第一種方式，RW上開啟行列混合存儲，此種模式部署可以支持輕量級的AP查詢，在主要為TP負載，且AP型請求比較少時可以采用?；蛘呤褂肞olarDB進行報表查詢，但是數(shù)據(jù)來自批量數(shù)據(jù)導入的場景。

• 第二種方式，RW支持OLTP型負載，并啟動一個AP型RO開啟行列混合存儲以支持查詢，此種部署模式下CPU資源可以實現(xiàn)100%隔離，同時該AP型RO節(jié)點上的內(nèi)存可以100%分配給列存存儲和執(zhí)行器。但是由于使用的相同的共享存儲，因此在IO上會相互產(chǎn)生一定影響，對于這個問題我們在未來會支持將列存數(shù)據(jù)寫入到外部存儲如OSS等，實現(xiàn)IO的資源隔離，同時提升AP型RO上的IO吞吐速率。

• 第三種方式，RW/RO支持OLTP型負載，在單獨的Standby節(jié)點開啟行列混合存儲以支持AP型查詢，由于standby是使用獨立的共享存儲集群，這種方案在第二種方案支持CPU和內(nèi)存資源隔離的基礎(chǔ)上，還可以實現(xiàn)IO資源的隔離。

除了上述部署架構(gòu)上不同可以支持的資源局隔離之外。在PolarDB內(nèi)部對于一些需要使用并行執(zhí)行的大查詢支持動態(tài)并行度調(diào)整(Auto DOP)，這個機制會綜合考慮當前系統(tǒng)的負載以及可用的CPU和內(nèi)存資源，對單個查詢所用的資源進行限制，以避免單個查詢消耗的資源太多，影響其他請求的處理。

五  PolarDB IMCI的OLAP性能

為了驗證IMCI技術(shù)的效果， 我們對PolarDB MySQL IMCI的進行了TPC-H場景的測試。同時在相同的場景下將其與原生MySQL的行存執(zhí)行引擎以及當前OLAP引擎單機性能最強的ClickHouse進行了對比。測試參數(shù)簡要介紹如下:

• 數(shù)據(jù)量TPC-H 100GB, 22條Query

• CPU Intel(R) Xeon(R) CPU E5-2682 2 socket

• 內(nèi)存 512G, 啟動后數(shù)據(jù)都灌進內(nèi)存。

1  PolarDB IMCI VS MySQL串行

在TPC-H場景下，所有22條Query ，IMCI處理延時相對比原生MySQL都有數(shù)十倍到數(shù)百倍不等的加速效果。其中Q6的的效果將近400倍。體現(xiàn)出了IMCI的巨大優(yōu)勢。

2  PolarDB IMCI VS ClickHouse

而在對比當前社區(qū)最火熱的分析型數(shù)據(jù)庫ClickHouse時, IMCI在TPC-H場景下的性能也與其基本在同一水平。部分SQL的處理延時各有優(yōu)劣。用戶完全可以使用IMCI替代ClickHouse使用，同時其數(shù)據(jù)管理也更加方便。

FutureWork

IMCI是PolarDB邁向數(shù)據(jù)分析市場的第一步，它迭代腳步不會停止，接下里我們會在如下幾個方向進一步研究和探索，給客戶帶來更好的使用體驗：

• 自動化的索引推薦系統(tǒng)，目前列存的創(chuàng)建和刪除需要用戶手動指定，這增加了DBA的工作量，目前我們正在研究引入自動化推薦技術(shù)，根據(jù)用戶的SQL請求特征，自動創(chuàng)建列存索引，降低維護負擔。

• 單獨的列存表以及OSS存儲，目前IMCI只是一個索引，對純分析型場景，去除行存可以更進一步的降低存儲大小，而IMCI執(zhí)行器支持讀寫OSS對象存儲能將存儲成本降到最低。

• 行列混合執(zhí)行，即一個SQl的執(zhí)行計劃部分片段在行存執(zhí)行，部分片段在列存執(zhí)行。以獲得最大化的執(zhí)行加速效果。