前言
隨著雲時代全面到來，企業數據需求不斷變化，從傳統的 Big Data 逐漸向 Fast Data 演進，主要表現在如下 4 個方面（部分數據參考 Gartner、IDC）：
- 數據規模爆炸性增長，到 2020 年全球數據預計會到 40ZB，而到 2025 年還會繼續增長 4 倍以上。
- 企業上雲速度明顯加快，預計到 2025 年企業 50% 的數據都是雲存儲，而企業 75% 的數據庫都運行在雲上。
- 數據的實時化需求強烈，預計 2025 年全球數據處理中會有 30% 是實時數據處理。
- 數據智能化趨勢明顯，隨著 AI 和 5G 技術的發展，非結構化數據快速增長，到 2025 年預計 80% 的數據都是非結構化數據。
在數據爆炸性增長、企業全面上雲的大背景下，海量數據的存儲、處理的性能及性價比是雲原生數倉面向未來最核心的關鍵技術指標之一，TPC 官方推出的 TPC-DS 基準測試是對一個數據倉庫從數據導入、查詢性能（單併發、多併發）、查詢複雜度（覆蓋星型模型/雪花模型、複雜 Window function 支持）、可用性（數據一致、壞盤容錯處理等）全方面的嚴格考核，並需要進行全面嚴苛的審計，是目前全球衡量一個數據倉庫成熟度、競爭力的核心基準測試。
AnalyticDB 作為雲時代的雲原生數據倉庫，參與 TPC-DS 基準測試是我們提升自研產品產品化能力、核心技術突破驗證的重要過程，也是我們技術走向全球領先的必經之路，這個過程中的核心技術突破正在幫我們的客戶提升性能進一步提升實時化進程、大幅降低成本，一起進入數據庫與大數據一體化、業務在線化的新時代。
TPC-DS 榜單
一 AnalyticDB 介紹
AnalyticDB（簡稱 ADB，原 ADS） 是阿里巴巴自主研發、唯一經過超大規模以及核心業務驗證的 PB 級實時數據倉庫，自 2012 年第一次在集團發佈上線以來，至今已累計迭代發佈近百個版本，支撐起集團內的電商、廣告、物流、文娛、旅遊、風控等眾多在線分析業務。AnalyticDB 於 2014 年在阿里雲開始正式對外輸出，支撐行業既包括傳統的大中型企業和政府機構，也包括眾多的互聯網公司，覆蓋外部十幾個行業。
AnalyticDB MySQL 3.0 （簡稱 ADB 3.0）是在過去 8 年沉澱的基礎上，基於數據庫大數據一體化的理念及趨勢以及工程上深度打磨出的雲原生數倉升級版本。在本次 TPC-DS 基準測試中，AnalyticDB MySQL 3.0 充分展現了出色的雲原生技術優勢，對比友商有近 10 倍的巨大優勢！
二 TPC-DS 性能基準介紹
TPC (Transaction Processing Performance Council) 是事務性能管理委員會的簡稱，是最知名的非盈利的數據管理系統評測基準標準化組織，它制定商務應用基準程序（Benchmark）的標準規範、性能和價格度量，並管理測試結果的發佈，而 TPC Benchmark 測試結果是衡量一個數據管理系統性能及性價比的最核心指標之一。
TPC-DS 基準測試模擬了一個典型的零售行業數據倉庫的評測決策支持系統（Decision Support），是數據庫界最具挑戰的一個測試基準，是 TPC-H 的升級版，它採用星型、雪花等多維數據模式，測試集包含對大數據集的統計、報表生成、聯機查詢、數據挖掘等複雜應用，與真實場景非常接近。
TPC-DS 的難點和挑戰主要有：
- 數據集規模大，例如事實表 store_sales，單表超過 280 億行。
- 面向真實零售決策場景，SQL 非常複雜：覆蓋 SQL 99 和 2003 的核心部分以及 OLAP 標準；既包含報表類 ad-hoc 低延時查詢，又包含海量數據挖掘高吞吐分析查詢。
- 測試項多且維度廣：既要高性能、高可靠、高可用、高性價比，又要 ETL 和數據更新的 ACID 能力。
TPC-DS 測試流程及數據模型：
三 AnalyticDB MySQL 3.0 技術架構
AnalyticDB MySQL 3.0 採用雲原生架構，計算存儲分離、冷熱數據分離，支持高吞吐實時寫入和數據強一致，兼顧高併發查詢和大吞吐批處理的混合負載。
第一層是接入層，由 Mulit-Master 可線性擴展的協調節點構成，主要負責協議層接入、SQL 解析和優化、實時寫入 Sharding、數據調度和查詢調度。
第二層是計算引擎，具備分佈式 MPP + DAG 融合執行能力，結合智能優化器，可支持高併發和複雜 SQL 混合負載，同時藉助於雲原生基礎設施，計算節點實現了彈性調度，可根據業務需求做到分鐘級甚至秒級擴展，達到了資源的有效利用。
第三層是存儲引擎，基於 Raft 協議實現的分佈式實時強一致高可用存儲引擎，通過數據分片和 Multi-Raft 實現並行，利用分層存儲實現冷熱分離降低成本，通過行列存儲和智能索引達到極致性能。
四 AnalyticDB 存儲技術
1 分佈式強一致存儲
AnalyticDB MySQL 3.0 存儲完全自主研發，基於 Raft 協議構建了一套分佈式強一致高可靠的輕量級存儲架構，可實現高吞吐實時寫入，適合極致分析性能場景。AnalyticDB MySQL 3.0 存儲相比開源 HBase、Kudu 等在 SQL 分析性能上有較大優勢，並且在實時寫入強一致可見、支持 ACID 方面也是開源 ElasticSearch、ClickHouse 等所不具備的能力。
AnalyticDB 存儲整體架構如下：
AnalyticDB MySQL 3.0 是基於數據庫的並行數據模型，存儲建模親和 MPP 計算模型，內部實現為多層並行的架構：
第一級是集群實例級並行，用戶實例被劃分為多個存儲節點組（Worker Group），每個 Worker Group 由 N（通常是 3，也可以是其他基數）個 Worker 構成。Worker 相當於用戶數據節點容器，分組的目標是保證系統大規模擴展時不會出現通信膨脹、也方便系統並行升級和運維。
第二級是 DB 並行，用戶數據庫被切分為 N 個物理分庫（ Shard，也叫數據分片），每個 Shard 是獨立的 Raft Group 以保證數據強一致，多個 Shard 就形成了 multi-raft 的並行。Shard 是可以是 Hash 或者 Range 分區，通常 Hash 分區可以做數據對齊以避免數據大表 JOIN 的數據 Shuffle；Shard 可以在需要的時候在不同 Worker Group 之間均衡或者遷移，Shard 本身也會支持動態分裂和合並。
第三是表內並行，對於數倉場景的歷史數據存儲通常有數據分區的概念，例如 TPC-DS 中 store sales 就可以根據時間週期分區，數據分區除方便數據生命週期管理外還可以支持查詢分區裁剪和 DFP，有助於大幅縮小數據計算範圍。
在 TPC-DS 基準測試中，通過分佈式並行存儲架構以及感知存儲分佈的查詢優化和執行引擎緊密配合，整體性能優異。
2 高性能批量導入
數據導入速度是雲數倉的基礎能力，在 TPC-DS 中對導入有著極致的性能要求，我們的第一個優化思路是輕量級 build（把實時數據轉換為全量分區數據稱之為 build），AnalyticDB MySQL 3.0 實現了輕量化的全內存單副本 local build，相比之前版本的類 MR 作業的全量 build 大幅減少了讀寫 DFS 和落盤開銷，並且可以充分通過本地化向量指令有效利用 CPU 提升性能。
第二個思路是 IO 和網絡優化，在導入鏈路上，我們採用 DirectIO、Binary 化、全流式、異步化、零拷貝等技術大幅提升導入性能。
第三個思路是減少數據量，通過 Raft 2+1 技術（2 份數據 + 1 份日誌）在保證數據高可靠的前提下將數據量減少 1/3, 再通過高性能 lz4 壓縮算法將數據進一步壓縮，整體下來數據的讀寫 IO 和網絡傳輸開銷都得到大幅優化。
最終，在 TPC-DS 18 個節點上可以實現超過 5000 萬/秒的導入性能。
3 高吞吐實時更新 DML
AnalyticDB MySQL 3.0 基於 Raft 實現了高吞吐實時數據更新能力，寫入鏈路通過全異步化、零拷貝、高效編碼壓縮等實現了出色的性能，在 TPC-DS DML 測試中，AnalyticDB 十幾個節點可以做到千萬級 TPS 實時寫入更新，並且能夠保證線性一致性（寫入後立即可查）。在實際生產中，用戶寫入性能完全可擴展，可以輕鬆實現億級 TPS 的實時寫入更新。
在 TPC-DS 中，需要驗證數據倉庫的數據修改和 ACID 能力，AnalyticDB MySQL 3.0 支持 ETL 事務，具備 ACID 能力（可以完整跑 TPC-C 事務功能測試），在 TPC-DS 的 DML 測試中，存儲引擎 MVCC 能力發揮了巨大的作用：存儲引擎通過切分為實時數據（Delta）和分區數據（Main）+ 異步的數據轉換（Build）實現了類 LSM 寫優化架構。AnalyticDB 實現了 Block-level MVCC + 快照隔離，可以保證 ETL 和數據更新過程中數據的隔離性（可見性）、在壞盤出錯時可以保證數據更新原子性。
4 行列混存和智能索引
AnalyticDB MySQL 3.0 通過自研的行列混存格式，能夠兼顧高篩選率和大吞吐掃描兩種場景，相比開源 ORCFile 的純列存格式在明細點查上更有優勢，而相比 Parquet，AnalyticDB MySQL 存儲格式具有更出色的隨機讀性能，同時對比業界行存表 + 列存表兩份數據冗餘的模式成本更低。在 AnalyticDB MySQL 中，每個 Table 都有一個行列存儲格式文件，數據被切分成不同的 RowGroup，在 RowGroup 內由列的 Block 構成，Block 內對定長、非定長（Toast）數據的進行有效的編碼和壓縮，並且支持高效的隨機讀和順序讀。
在 TPC-DS 測試中，通過配置合理的存儲 Block 大小（4KB 對齊）、數據塊預取、源頭算子向量讀等大幅優化了存儲掃描性能；同時，存儲上精確的統計信息(min/max/sum/cnt 等)一方面可以加速數據過濾（Smart Scan），另一方面還能夠為查詢優化器提供豐富的 Statistics 以幫助制定出最優的執行計劃。
AnalyticDB MySQL 的特色之一是自研智能索引框架，支持五種索引類型：字符串類的 Invert 索引、bitmap 索引、數值類的 KDTree 索引、JSON 索引和向量索引；不同類型的索引可以實現列級索引多種條件（交、並、差）任意組合；相比較傳統數據的優勢是，無需建組合索引（不會引起空間膨脹）、且支持 OR/NOT 等更多條件的索引下推。為了降低用戶使用門檻，AnalyticDB 在建表時可以開啟一鍵自動全列索引，查詢時通過 Index CBO 智能動態篩選索引下推，確定下推的索引鏈會通過謂詞計算層進行流式漸進多路歸併輸出。
五 AnalyticDB 查詢技術
AnalyticDB MySQL 3.0 的查詢引擎，由自研的查詢優化器和查詢執行器兩個模塊組成。它是 AnalyticDB MySQL 提供高併發、高吞吐數倉分析能力的重要一環。感知數據特徵，深度結合存儲引擎的架構，同時支持 Reporting、Ad-hoc、ETL 數倉分析場景，是其相較於單一計算引擎的核心優勢。
作為一款分佈式雲原生實時數倉產品，AnalyticDB MySQL 的優化器不僅僅要面臨傳統優化器所涉及的挑戰，例如複雜 Join Reorder 的 NP-hard 問題，代價估算的不確定性問題，還面臨在分佈式環境下分佈式並行計劃的新問題。CBO 做為 AnalyticDB MySQL 3.0 版本最新成果，在 TPC-DS 戰役中首次開啟使用，對於整體計劃的調優，起到了非常重要的作用。
ADB 查詢執行引擎，以統一的內存池化和查詢的混合負載管理能力為基礎，使用動態代碼生成技術，創新性的混合執行模型，利用 SIMD 指令集的向量化算法，以及自適應的面向行、列混合存儲的查詢執行等技術，是 AnalyticDB MySQL 持續的在 TPC-DS 查詢性能上領先的關鍵因素。
1 CBO 查詢優化框架
基於代價的優化器本質上是一個複雜的搜索問題，想要解決好這個問題，需要從四個方面入手：
搜索框架
從數據庫的發展歷程來看，基於 Cascades 的搜索框架已經成為了業界標準，包括商業數據庫 SQL Server 以及開源數據庫 GP/ORCA 都採用 Cascades 實現。AnalyticDB MySQL 優化器 CBO 也是基於 Cascades 論文實現的。搜索框架面臨的一個核心問題是搜索空間會急速膨脹，但是搜索時間需要維持毫秒級響應，因此需要有高效的數據結構存儲搜索空間、高效的優化規則生成搜索空間、高效的搜索算法遍歷搜索空間，高效的剪枝策略裁剪搜索空間。
分佈式並行計劃
相對於傳統的單機版數據庫來說，分佈式 MPP 數據庫給優化器帶來了新的挑戰。在分佈式 MPP 數據庫中，數據的分佈屬性變得十分的重要，它會直接影響到數據的正確性。為了滿足不同算子對數據分佈的要求，數據重分佈不可避免，然而數據的重分佈即數據 shuffle 的代價非常昂貴，因此，在保證數據正確性的前提下，儘可能的減少數據 shuffle。作為分佈式 MPP 數據庫優化器來說，需要把數據的 Partitioning 屬性，以及 Sorting、Grouping 屬性，也納入到搜索空間來綜合考慮，基於代價選擇最優的分佈式並行執行計劃。
代價估算
代價估算是優化器能否尋找到最優計劃的關鍵因素。代價估算涉及到統計信息的推導和代價模型。統計信息的推導依賴於：原始表的統計信息、中間算子的推導算法、對數據的各種假設（均勻性假設、獨立性假設、包括性假設、包含性假設）以及在一些極端情況下的猜測。因此統計信息的推導存在大量的不確定性，也正是因為這些不確定性，極大的加劇了優化器尋找最優解的難度。本質上來說，只有打破對數據屬性的假設，才有可能使得統計信息的估算做到知其然知其所以然，然而打破這些假設，也要付出更多的代價。
統計信息收集
收集必要的統計信息是 CBO 工作的前提，統計信息需要做到：基本信息能夠自動化收集，自動化更新，高級統計信息可以手動收集，為 CBO 提供可靠的、多緯度的統計信息。在實際的情況下，可能存在統計信息丟失或者沒有及時收集，在這種情況下，為了避免生成災難性的計劃，可以在運行時動態採樣來獲取必要的統計信息。
2 混合查詢執行框架
傳統的火山執行模型不能滿足分析場景高吞吐的性能需求已經成為業界的共識。隨著各個系統的不斷髮展，目前業界計算引擎有 2 種演化後的執行框架實現：
- Just-in-time (JIT) compilation
- Vectorization
JIT編譯方式以數據為中心，一條數據經過上一個算子處理後，還在 CPU 緩存中便直接進行下一個算子的計算，對 CPU 緩存友好，適合計算密集型任務。Vectorization 中每個算子處理一批數據後，將一批結果再交給下一個算子計算。適合內存密集型任務以及向量計算，用中間結果物化的開銷換取算子的計算高內聚。
JIT 編譯方式和 Vectorization 各有所長，如上圖所示，紅色表示 JIT 編譯方式，綠色表示 Vectorization 方式。目前 AnalyticDB MySQL 是唯一的同時支持這兩種查詢模式的自研分析引擎。混合執行框架，在 Vectorization 執行模式的基礎上，自適應的把多個計算密集特徵的算子融合成一個驅動執行。實現了一個查詢執行引擎同時具備 Compilation 和 Vectorization 的優點。
3 統一內存管理
在內存方面，高效的內存管理是計算優化的基石。面向類型的內存模型，特指針對不同的數據類型使用不同的基礎類型存儲。這導致不同的類型無法存儲在連續的內存地址中，僅能通過按列的方式進行存儲，減少多個內存對象帶來的額外代價。另外一方面，不同內存類型間的內存無法複用，這會造成額外的內存管理代價。
ADB 的查詢執行引擎，通過統一內存管理來解決上面的幾個問題：
- 內存 binary 化：統一內存類型，不同類型均使用相同的數據類型（byte）來存儲，同時這也是查詢執行面向行存，緩存友好算法優化的基石。
- 規範化的內存管理規格：統一內存規格，降低內存碎片帶來的額外代價，並且降低複用內存的難度。
- 分層的內存管理：統一內存管理，根據計算特點對應內存的生命週期，針對內存使用特點，實現 MemoryCache， MemoryPool，並且支持內存洩漏檢測，實現面向常駐服務的主動內存管理。
4 DFP 和 CTE 技術
在數據倉庫中，事實表和維度表 Join 是典型場景，他們之間的數據量的差異可以達到千萬倍級別，這個時候，Join 的計算成本更多的在於數據的掃描成本，因此我們會採用 DynamicFilterPushDown 的方式，來極大的減少左表的數據量。另外數據倉庫中會出現大量的 WITH 語句以及隱式的共享語句，這些都可以通過 Common Table Expression 的共享來避免重複計算。
DFP（DynamicFilterPushDown）對於篩選率高的 Join （命中率低）、Probe 端的數據從存儲中被讀上來之後，大部分數據會被丟棄掉。因此如果評估出來 build 的數據維持在一個比較小範圍的閾值，那麼我們就可以把 build 端結果值，作為左表的過濾條件，也就是 Dynamic Filter，直接下推存儲，減少掃描量。對於優化器來說，最主要的工作就是要合理評估 build 端命中 Join 條件的 NDV 值。
不同的 Join Order 直接影響可做 Dynamic Filter 的範圍和粒度，能夠進行該優化的 Join 其 Cost 與真正的 Hash Join 有巨大的差異反過來也影響了 Join Order。基於 ADB 完善且擴展性較好的 CBO 框架，我們做到了從全局考慮，基於 Cost 選擇最優的 Dynamic Filter 方案。
在執行層面，我們通過如下三個關鍵點實行有高效的 DFP：
- 高效動態謂詞構建，通過進程內 in-place 構建動態謂詞，降低動態文詞構建代價。
- 多層過濾執行優化，結合 bloomfilter，分區裁剪，感知存儲索引等方式，加速過濾效果。
- 異構數據源的下推，統一數據源接口層抽象實現，擴展異構數據源的支持。
CTE（Common table expression），TPC-DS 30%+ 的 sql 中包含 with as 用法， 通過 with as 子查詢，在主查詢中多次引用，每一次引用帶來了額外的重複計算，導致資源浪費。基礎的 CTE 優化，通過複用 with 子句的結果給多個引用方，來減少重複計算的代價。但是對於部分場景，與主查詢的關係推導可以進一步減少 with 子查詢中的計算量，這時直接 share 完整 with 子句會導致額外的性能回退。那麼通過 inline 後的最優計劃，進行 common sub tree 的識別，進一步減少重複計算量，達到無 bad case 的效果。執行器實現中，我們引入了死鎖檢測，通過分析 common sub tree 的多個 consumer 之間的依賴關係，解決死鎖問題。
六 總結和展望
AnalyticDB 經過數據庫領域最頂級會議 VLDB 論文（AnalyticDB: Realtime OLAP Database System at Alibaba Cloud）的理論驗證（中國極其少有的大規模商用系統介紹論文，類似有 Google F1 [VLDB'2013]、AWS Aurora [SIGMOD'2017] 等）、TPC-DS 全球領先的工程驗證（TPC-DS 全球性價比、性能雙雙領先）、覆蓋核心部委以及大型泛互聯網客戶的客戶驗證、阿里集團多年的超大規模驗證形成了多方面優勢，基於雲計算的高效資源效率、數據庫與大數據一體化發展趨勢，正式完成重大品牌升級，由“分析型數據庫”升級為“雲原生數據倉庫”。
未來已來，大數據與數據庫一體化 + 雲原生將會重新定義雲計算時代的數據倉庫，TPC-DS 破世界紀錄只是起點，AnalyticDB 將會持續投入致力於成為企業數字化轉型升級、數據價值在線化的基礎設施！
AnalyticDB 2019 大盤點：點擊這裡