作者：玄弟
早期資料庫受限于硬體水準，IO、記憶體和CPU資源都非常昂貴，比如計算層的資料一多，記憶體容易爆掉；且隻做單核計算，更談不上用分布式去解決計算加速問題。可見在當時背景下執行器能夠做的加速優化微乎其微。但今時不同往日，由于硬體水準的高速發展，分布式技術的日益成熟，執行器在大資料量的加速優化也越來越被重視，而我們的PolarDB-X執行器也就是在這個背景下不斷疊代成長起來的。
目前PolarDB-X執行器在混合負載場景下，能確定TP和AP工作負載不互相影響，在能保證TP負載低延遲的前提下，AP依然可以保持一個不錯的吞吐。在PolarDB-X企業版主執行個體32核128 GB下，在開啟智能讀寫分離模式并存在隻讀執行個體情況下，TPC-C流量将會被路由至主執行個體，而TPC-H流量将會被路由至隻讀執行個體。OLTP負載與OLAP負載能夠分别在主執行個體和隻讀執行個體上做到實體資源隔離，同時隻讀執行個體可以提供MPP能力，能夠充分利用計算資源。
備注：
- 開始通過100并發的純TPC-C流量，吞吐可以達到23萬tpmC;
- 關閉智能讀寫分離，加入TPC-H流量混跑。TPC-C吞吐下降明顯，TPC-H總耗時為840s;
- 開啟智能讀寫分離，TPC-C吞吐恢複到23萬tpmC，TPC-H總耗時也可以恢複到最初的274s。
發展曆程
PolarDB-X資料庫曆經10年的發展，而其執行器起起伏伏也沉底了10年。其最早可以追溯到執行器經典架構：Volcano 模型的計算架構。我們可以先回顧下傳統資料庫在執行器領域過去幾十年的發展，同時也介紹下我們對技術選型的思考。
執行器模型：Pull vs. Push
早期的執行器多半都采樣經典的Volcano 模型[1]，如下圖所示。執行計劃中的每個算子都需要實作next函數，上遊算子每一次調用，内部都會調用其輸入的next函數, 遞歸調用，再層層計算傳回結果。目前MySql/SQLServer/DB2/Oracle等早期資料庫基本都采用這種計算模型。
Volcano模型簡單靈活，且這種設計不用占用過多的記憶體。在當時記憶體是非常昂貴的，火山模型将更多的記憶體資源用于IO的緩存設計而沒有優化CPU的執行效率，這在當時的硬體基礎上是很自然的權衡。但是現在CPU的硬體環境與大資料場景下，性能表現卻差強人意。究其原因。主要有如下幾點：
- 每次 next 都是一次虛函數調用過程是被動拉資料，編譯器無法對虛函數進行inline優化，同時也帶來分支預測的開銷，且很容易預測失敗，導緻CPU流水線執行混亂。
- Volcano Style的代碼對資料的局部性并不友好，往往造成cache miss。我們知道CPU cache是存儲着連續資料空間，每次可以對連續資料進行集中處理，将受益最大。而Volcano模型每次調用隻處理一行。
鑒于火山模型每次處理一行一行資料，而next調用代價又比較高。是以批量處理模型在業界被提出，在算子間傳遞資料不再是一條一條記錄，而是一批資料，算子每次執行的時候都會在内部攢一批資料，資料大小盡可能和CPU cache對齊，不僅大大提高了cache命中率，而且有效地減少了函數調用次數。
除此之外，業界也提出了Push計算模型，如上圖所示。可以直覺看到push執行模式相對于pull模型來說有效減少了指令的跳轉，優化了CPU執行效率。通常做法就是用visitor方式周遊在優化器提供的執行計劃，建構出push執行的實體計劃。Push模式的算子實作大大提高了算子複雜度，比如merge join在原先pull模型中可以直接在算子内部控制兩端輸入的資料流。
編譯執行 vs. 向量化執行
當我們提到編譯執行的時候到底是在講什麼呢？通常我們是先編寫代碼，再編譯，最後運作。而對于這裡提到的編譯執行，更多的是運作時期的代碼生成生成技術。在執行過程中生成編譯生成執行代碼，避免過多的虛函數調用和解析執行，因為在執行之初我們是知道關系代數的schema資訊。在具備Schema資訊的情況下，事先生成好的代碼，可以有效減少很多執行分支預測開銷。這裡直接參考自Impala論文[2]給出來的代碼比對。
如上圖右邊的代碼非常緊湊，有效消除了字段個數，字段大小，字段類型，對于資料量特别多的處理場景，可以大大減少CPU開銷，提高性能，但實際仍有一個問題，如何生成右邊的代碼？業界常用的代碼生成架構有ASM/LLVM IR等。但是每個表達式和算子都需要單獨編譯，如何減少編譯開銷？在這個基礎上發展出來了Pipeline Compilation技術，就是将多個operator融合在一起編譯，減少開銷；此外還有Operator Cache技術，将事後編譯好的代碼cache起來，類似的查詢語句可以直接複用編譯好的代碼，進一步減少編譯開銷時間[3]。
另一種加速思路是向量化執行，簡單來說就是通過 batch 的方式均攤開銷：假設每次通過 operator tree[4]生成一行結果的開銷是C的話，經典模型的計算架構總開銷就是C*N，其中N為參與計算的總行數，如果把計算引擎每次生成一行資料的模型改為每次生成一批資料的話，因為每次調用的開銷是相對恒定的，是以計算架構的總開銷就可以減小到C*N/M，其中M是每批資料的行數，這樣每一行的開銷就減小為原來的1/M，當 M 比較大時，計算架構的開銷就不會成為系統瓶頸了。
這樣說很多人會誤解，這個是不是就是之前提到的批量處理模型呢？看似差不多，實際上要做到向量化執行，需要對算子和表達式做大量的改造，基于SIMD向量化指令操作的思想去重構整個表達式計算。向量化執行可以減少分支預測的開銷，充分發揮SIMD指令并行計算的優勢；還可以和列式存儲有效結合在一起，減少資料額外轉換的overhead。我們所知道ClickHouse就是采樣了向量化（vectorized query execution）機制。
并行：SMP vs. MPP
随着多處理器結構硬體的出現，執行器開始往SMP架構發展，既單機并行計算，充分利用多核能力加速計算。在這樣的系統中，所有的CPU共享全部資源，如總線，記憶體和I/O系統等，作業系統或管理資料庫的副本隻有一個，這種系統有一個最大的特點就是共享所有資源。但是單機并行執行器的擴充能力非常有限，在計算過程中也隻能充分使用一台 SMP 伺服器的資源，随着要處理的資料越來越多，這種有限擴充的劣勢越來越明顯。
但是 SMP 架構隻能利用單個機器的計算能力（scale up），不能擴充到多台機器（scale out）。MPP 就是将計算分布到多個節點的叢集中，叢集中的記憶體、CPU等資源理論上可以無限擴充，使得資源不再輕易成為計算的瓶頸。但分式并行計算在充分發揮叢集各台機器的CPU等能力的同時，會帶來新的問題。排程上如何做到均衡排程，避免更多的網絡傳輸，避免單個節點成為計算瓶頸？分布式計算過程中如何確定資源利用最大化？可見建構一個分布式并行計算比之前的系統複雜的多，要考慮的因素也非常多。
HTAP: Single System vs. Separate Systems
HTAP最早的概念是Gartner在2014年的一份報告中使用混合事務分析處理(Hybrid Transactional and Analytical Processing，HTAP)一詞描述新型的應用程式架構，以打破OLTP和OLAP之間的隔閡，既可以應用于事務型資料庫場景，亦可以應用于分析型資料庫場景。實作實時業務決策。這種架構具有顯而易見的優勢：不但避免了繁瑣且昂貴的ETL操作，而且可以更快地對最新資料進行分析。
在近期的頂會論文中也不乏出現HTAP架構的身影，推薦一篇SIGMOD的論文《Hybrid Transactional/Analytical Processing: A Survey》，高度總結和歸納了下HTAP架構的技術方案。實作HTAP技術主要兩個分類：
Single System（一套系統解決 TP/AP）
- Decoupled Storage，比如SAP HANA、Hyper(行式記憶體+列式擴充)、SQLServer(列存索引)、MemSQL(行式記憶體+刷盤時轉列存)等；
- Unified Storage，主要為SQL-on-Hadoop類，比如Impala with Kudu(SQL-On-hadoop類型，支援變更)
Separate Systems（兩套系統分别應對 TP/AP）
- Decoupled Storage，比如Lambda架構、以及傳統的線上+數倉組合， 技術上使用ETL進行資料同步；
- Unified Storage，比如基于Hbase建構TP寫入一份資料，AP側是Spark SQL-base使用同一份資料。
PolarDB-X 執行器架構
PolarDB-X 是由阿裡巴巴自主研發的雲原生分布式資料庫，是一款基于雲架構理念，并同時支援線上事務處理與線上分析處理 (Hybrid Transactional and Analytical Processing, HTAP）的融合型分布式資料庫産品，是以在PolarDB-X優化器、執行器上針對HTAP混合負載都有對應的設計展現。
HTAP架構
PolarDB-X主要面向以OLTP事務型為主的分布式資料庫，同時支援OLAP的線上分析的混合負載能力，我們期望以Single System的形态，基于Decoupled Storage存儲結構支援HTAP形态。
PolarDB-X HTAP執行器，主要有幾個特征：
- PolarDB-X 提供一個HTAP的endpoint(可以了解為一個vip)，業務所有的TP和AP流量隻需要通過這個endpoint通路即可；
- PolarDB-X 提供RW(讀寫)、RO(隻讀)節點的概念，基于Decoupled Compute/Storage的思路提供HTAP混合負載的能力；
- PolarDB-X 提供面向HTAP的優化器、分布式排程能力，可在Decoupled模式下将TP和AP請求做分離，利用實體隔離滿足OLTP的穩定性，另外結合分布式事務多副本強一緻的能力，實作OLAP的資料一緻性。可參考文檔： PolarDB-X 強一緻分布式事務原理 、 PolarDB-X 面向 HTAP 的 CBO 優化器
具體HTAP的工作原理和流程：
總結一下優勢：
- 強隔離、強一緻的混合負載，OLTP請求不會因為日志複制而産生延遲
- 引入分布式并行計算，OLAP查詢可滿足線性擴充能力
MPP 并行執行器
PolarDB-X在混合執行器設計上，借助于
，可以實作TP和AP的識别和路由，可以在一個執行個體裡同時運作OLTP和OLAP業務，保證AP的查詢不影響TP流量的穩定性。同時在OLAP能力上，引入Push模型、Chunk執行、向量化、MPP并行計算等特性，可以滿足TPC-H/TPC-DS等複雜查詢的訴求，後續會專門開一篇文章介紹下PolarDB-X的MPP并行計算的代碼設計和理念。
以 TPC-H Q9為例：
關鍵特性對比
| 對比項 | 子項 | PolarDB-X | MySQL with Analytics Engine | TiDB | Cockroach | Presto | Spark |
| OLTP | 強一緻事務 | 分布式 | 單機 | / | |||
| 基于索引的點查 | 支援 | ||||||
| 基于索引的Join關聯 | |||||||
| 各種DML | |||||||
| OLAP | 執行模型 | Push+Batch | Volcano+Batch | Pull+Batch | |||
| 執行方式 | vectorized | vectorized (表達式有codegen) | whole stage codegen (企業版有vectorized) | ||||
| 并行計算 | MPP | SMP(MPP需外挂Spark) | SMP | ||||
| HTAP | 資源隔離 | 存儲和計算 | 存儲 | ||||
| 資料一緻性 | 強一緻 | 弱一緻(異步複制） |
- MySQL with Analytics Engine，是MySQL在20年12月2号在其官網推出分析引擎，極大增強MySQL自身的分析能力。
- OLTP場景會比較注重基于索引的優化，比如基于Index的point select 以及Index Nested Loop Join，在OLAP場景下會比較注重并行能力和執行效率的優化，比如SMP/MPP、vectorized/codegen等，最後針對HTAP場景，更多會注重資源隔離、資料一緻性、查詢入口是一個還是多個等。
我們還在路上
軟體技術的發展總是和硬體技術的發展緊密結合在一起的，迎合硬體技術的發展而改變軟體技術棧的相應政策能夠使得設計的系統獲得更大的受益。這些年PolarDB-X執行器經過多次版本的疊代，早已不再是單機版本的記憶體執行器了，我們既是一款和分布式事務相耦合的執行器，也可以是一款可以處理海量的資料處理，具備了落盤和MPP的計算能力的執行器。這一切都得益于我們從一開始就把自己定位成了一款HTAP引擎：
- 是一款可以同時滿足事務處理和工作負載分析的業務需求的執行器
- 是一款分布式并行執行器，具備計算水準擴充的能力
- 高度統一的執行器代碼，真正做到了TP和AP執行器一體化
- 支援大規模并行處理和複雜查詢優化
- 基于工作負載做資源管理，支援計算資源互相彈縮
但我們知道這些還遠遠不夠，技術永無止境。現在的我們仍會時刻關注業界最新的技術動态，我們會探索一切可能的東西，充分融入到我們PolarDB-X的系統裡頭去，不斷加強我們HTAP資料庫的能力，這個過程我們也期待你的加入!
參考文檔
- Graefe G..Volcano-an extensible and parallel query evaluation system[J].Knowledge & Data Engineering, IEEE Transactions on,1994,6
- S. Wanderman-Milne and N. Li, “Runtime Code Generation in Cloudera Impala,” IEEE Data Eng. Bull., vol. 37, no. 1, pp. 31–37, 2014
- 向量化與編譯執行淺析
- A. Kemper, P. Boncz, T. Kersten, V. Leis, A. Pavlo, and T. Neumann, “Everything you always wanted to know about compiled and vectorized queries but were afraid to ask,” Proc. VLDB Endow., vol. 11, no. 13, pp. 2209–2222, 2018.