[[252839]]

挑戰

隨著數據量的快速增長，越來越多的企業迎來業務數據化時代，數據成為了最重要的生產資料和業務升級依據。伴隨著業務對海量數據實時分析的需求越來越多，數據分析技術這兩年也迎來了一些新的挑戰和變革：

• 在線化和高可用，離線和在線的邊界越來越模糊，一切數據皆服務化、一切分析皆在線化。
• 高并發低延時，越來越多的數據系統直接服務終端客戶，對系統的并發和處理延時提出了新的交互性挑戰。
• 混合負載， 一套實時分析系統既要支持數據加工處理，又要支持高并發低延時的交互式查詢。
• 融合分析， 隨著對數據新的使用方式探索，需要解決結構化與非結構化數據融合場景下的數據檢索和分析問題。

阿里巴巴最初通過單節點Oracle進行準實時分析, 后來轉到Oracle RAC，隨著業務的飛速發展, 集中式的Shared Storage架構需要快速轉向分布式，遷移到了Greenplum，但不到一年時間便遇到擴展性和并發的嚴重瓶頸。為了迎接更大數據集、更高并發、更高可用、更實時的數據應用發展趨勢，從2011年開始，在線分析這個技術領域，阿里實時數倉堅定的走上了自研之路。

[[252840]]

分析型數據庫AnalyticDB

AnalyticDB是阿里巴巴自主研發、唯一經過超大規模以及核心業務驗證的PB級實時數據倉庫。自2012年第一次在集團發布上線以來，至今已累計迭代發布近百個版本，支撐起集團內的電商、廣告、菜鳥、文娛、飛豬等眾多在線分析業務。

AnalyticDB于2014年在阿里云開始正式對外輸出，支撐行業既包括傳統的大中型企業和政府機構，也包括眾多的互聯網公司，覆蓋外部十幾個行業。AnalyticDB承接著阿里巴巴廣告營銷、商家數據服務、菜鳥物流、盒馬新零售等眾多核心業務的高并發分析處理， 每年雙十一上述眾多實時分析業務高峰驅動著AnalyticDB不斷的架構演進和技術創新。

經過這2年的演進和創新，AnalyticDB已經成長為兼容MySQL 5.x系列、并在此基礎上增強支持ANSI SQL:2003的OLAP標準(如window function)的通用實時數倉，躋身為實時數倉領域極具行業競爭力的產品。近期，AnalyticDB成功入選了全球權威IT咨詢機構Forrester發布"The Forrester Wave™: CloudData Warehouse,Q4 2018"研究報告的Contenders象限，以及Gartner發布的分析型數據管理平臺報告 (Magic Quadrant forData Management Solutions for Analytics)，開始進入全球分析市場。AnalyticDB旨在幫客戶將整個數據分析和價值化從傳統的離線分析帶到下一代的在線實時分析模式。

整體架構

經過過去2年的架構演進和功能迭代，AnalyticDB當前整體架構如下圖。

AnalyticDB是一個支持多租戶的Cloud Native Realtime Data Warehouse平臺，每個租戶DB的資源隔離，每個DB都有相應獨立的模塊(圖中的Front Node, Compute Node, Buffer Node)，在處理實時寫入和查詢時，這些模塊都是資源(CPU, Memory)使用密集型的服務，需要進行DB間隔離保證服務質量。同時從功能完整性和成本優化層面考慮，又有一系列集群級別服務(圖中綠色部分模塊)。

下面是對每個模塊的具體描述：

DB級別服務組件：

• Front Node：負責JDBC, ODBC協議層接入，認證和鑒權，SQL解析、重寫;分區地址路由和版本管理;同時優化器，執行計劃和MPP計算的調度模塊也在Front Node。
• Compute Node： 包含MPP計算Worker模塊，和存儲模塊(行列混存，元數據，索引)。
• Buffer Node： 負責實時寫入，并根據實時數據大小觸發索引構建和合并。

集群級別服務組件：

• Management Console： 管理控制臺。
• Admin Service：集群管控服務，負責計量計費，實例生命周期管理等商業化功能，同時提供OpenAPI和InnerAPI給Management Console和第三方調用。
• Global Meta Service：全局元數據管理，提供每個DB的元數據管理服務，同時提供分區分配，副本管理，版本管理，分布式DDL等能力。
• Job Service：作業服務，提供異步作業調度能力。異步作業包括索引構建、擴容、無縫升級、刪庫刪表的后臺異步數據清理等。
• Connector Service：數據源連接服務，負責外部各數據源(圖中右側部分)接入到AnalyticDB。目前該服務開發基本完成，即將上線提供云服務。
• Monitoring & Alerting Service：監控告警診斷服務，既提供面向內部人員的運維監控告警診斷平臺，又作為數據源通過Management Console面向用戶側提供數據庫監控服務。
• Resource Management Service：資源管理服務，負責集群級別和DB級別服務的創建、刪除、DNS/SLB掛載/卸載、擴縮容、升降配，無縫升級、服務發現、服務健康檢查與恢復。

數據模型

AnalyticDB中表組(Table Group)分為兩類：事實表組和維度表組。

• 事實表組(Fact Table Group)，表組在AnalyticDB里是一個邏輯概念，用戶可以將業務上關聯性比較多的事實表放在同一個事實表組下，主要是為了方便客戶做眾多數據業務表的管理，同時還可以加速Co-location Join計算。
• 維度表組(Dimension Table Group)，用于存放維度表，目前有且僅有一個，在數據庫建立時會自動創建，維度表特征上是一種數據量較小但是需要和事實表進行潛在關聯的表。

AnalyticDB中表分為事實表(Fact Table)和維度表(Dimension Table)。

事實表創建時至少要指定Hash分區列和相關分區信息，并且指定存放在一個表組中，同時支持List二級分區。

• Hash Partition將數據按照分區列進行hash分區，hash分區被分布到多個Compute Node中。
• List Partition(如果指定List分區列的話)對一個hash分區進行再分區，一般按照時間(如每天一個list分區)。
• 一個Hash Partition的所有List Partition默認存放于同一個Compute Node中。每個Hash Partition配有多個副本(通常為雙副本)，分布在不同的Compute Node中，做到高可用和高并發。

維度表可以和任意表組的任意表進行關聯，并且創建時不需要配置分區信息，但是對單表數據量大小有所限制，并且需要消耗更多的存儲資源，會被存儲在每個屬于該DB的Compute Node中。

下圖描述了從Database到List分區到數據模型：

對于Compute Node 來說，事實表的每個List分區是一個物理存儲單元(如果沒有指定List分區列，可認為該Hash分區只有一個List分區)。一個分區物理存儲單元采用行列混存模式，配合元數據和索引，提供高效查詢。

海量數據

基于上述數據模型，AnalyticDB提供了單庫PB級數據實時分析能力。以下是生產環境的真實數據：

• 阿里巴巴集團某營銷應用單DB表數超過20000張
• 云上某企業客戶單DB數據量近3PB，單日分析查詢次數超過1億
• 阿里巴巴集團內某單個AnalyticDB集群超過2000臺節點規模
• 云上某業務實時寫入壓力高達1000w TPS
• 菜鳥網絡某數據業務極度復雜分析場景，查詢QPS 100+

導入導出

靈活的數據導入導出能力對一個實時數倉來說至關重要，AnalyticDB當前既支持通過阿里云數據傳輸服務DTS、DataWorks數據集成從各種外部數據源導入入庫，同時也在不斷完善自身的數據導入能力。整體導入導出能力如下圖(其中導入部分數據源當前已支持，部分在開發中，即將發布)。

數據導入

首先，由于AnalyticDB兼容MySQL5.x系列，支持通過MySQL JDBC方式把數據insert入庫。為了獲得最佳寫入性能，AnalyticDB提供了Client SDK，實現分區聚合寫的優化，相比通過JDBC單條insert，寫入性能有10倍以上提升。對于應用端業務邏輯需要直接寫入AnalyticDB的場景，推薦使用AnalyticDB Client SDK。

同時，對于快速上傳本地結構化的文本文件，可以使用基于AnalyticDB Client SDK開發的Uploader工具。對于特別大的文件，可以拆分后使用uploader工具進行并行導入。

另外，對于OSS，MaxCompute這樣的外部數據源，AnalyticDB通過分布式的Connector Service數據導入服務并發讀取并寫入到相應DB中。Connector Service還將支持訂閱模式，從Kafka，MQ，RDS等動態數據源把數據導入到相應DB中。AnalyticDB對大數據生態的Logstash，Fluentd，Flume等日志收集端、ETL工具等通過相應插件支持，能夠快速把數據寫入相應DB。

今天在阿里巴巴集團內，每天有數萬張表從MaxCompute導入到AnalyticDB中進行在線分析，其中大量導入任務單表數據大小在TB級、數據量近千億。

數據導出

AnalyticDB目前支持數據導出到OSS和MaxCompute，業務場景主要是把相應查詢結果在外部存儲進行保存歸檔，實現原理類似insert from select操作。insert from select是把查詢結果寫入到內部表，而導出操作則是寫入外部存儲, 通過改進實現機制，可以方便地支持更多的導出數據源。

核心技術

高性能SQL Parser

AnalyticDB經過數年的發展，語法解析器也經歷了多次更新迭代。曾經使用過業界主流的 Antlr(http://www.antlr.org)，JavaCC(https://javacc.org)等Parser生成器作為SQL 語法解析器，但是兩者在長期、大規模、復雜查詢場景下，Parser的性能、語法兼容、API設計等方面不滿足要求，于是我們引入了自研的SQL Parser組件FastSQL。

領先業界的Parser性能

AnalyticDB主打的場景是高并發、低延時的在線化分析，對SQL Parser性能要求很高，批量實時寫入等場景要求更加苛刻。FastSQL通過多種技術優化提升Parser性能，例如：

• 快速對比：使用64位hash算法加速關鍵字匹配，使用fnv_1a_64 hash算法，在讀取identifier的同時計算好hash值，并利用hash64低碰撞概率的特點，使用64位hash code直接比較，比常規Lexer先讀取identifier，在查找SymbolTable速度更快。
• 高性能的數值Parser：Java自帶的Integer.parseInt()/Float.parseFloat()需要構造字符串再做parse，FastSQL改進后可以直接在原文本上邊讀取邊計算數值。
• 分支預測：在insert values中，出現常量字面值的概率比出現其他的token要高得多，通過分支預測可以減少判斷提升性能。

以TPC-DS99個Query對比來看，FastSQL比Antlr Parser(使用Antlr生成)平均快20倍，比JSQLParser(使用JavaCC生成)平均快30倍，在批量Insert場景、多列查詢場景下，使用FastSQL后速度提升30~50倍。

無縫結合優化器

在結合AnalyticDB的優化器的SQL優化實踐中，FastSQL不斷將SQL Rewrite的優化能力前置化到SQL Parser中實現，通過與優化器的SQL優化能力協商，將盡可能多的表達式級別優化前置化到SQL Parser中，使得優化器能更加專注于基于代價和成本的優化(CBO，Cost-Based Optimization)上，讓優化器能更多的集中在理解計算執行計劃優化上。FastSQL在AST Tree上實現了許多SQL Rewrite的能力，例如：

• 常量折疊：

SELECT * FROM t1 t 
WHERE comm_week  
  BETWEEN CAST(date_format(date_add('day',-day_of_week('20180605'), 
                             date('20180605')),'%Y%m%d') AS bigint) 
        AND CAST(date_format(date_add('day',-day_of_week('20180605') 
                            ,date('20180605')),'%Y%m%d') AS bigint) 
------> 
SELECT * FROM t1 t 
WHERE comm_week BETWEEN20180602AND20180602 

• 函數變換：

SELECT * FROM t1 t 
WHERE DATE_FORMAT(t."pay_time",'%Y%m%d')>='20180529' 
    AND DATE_FORMAT(t."pay_time",'%Y%m%d')<='20180529' 
------> 
SELECT * FROM t1 t 
WHERE t."pay_time">= TIMESTAMP'2018-05-29 00:00:00' 
AND t."pay_time"< TIMESTAMP'2018-05-30 00:00:00' 

• 表達式轉換：

SELECT a, b FROM t1 
WHERE b +1=10; 
------> 
SELECT a, b FROM t1 
WHERE b =9; 

• 函數類型推斷：

-- f3類型是TIMESTAMP類型 
SELECT concat(f3,1) 
FROM nation; 
------> 
SELECT concat(CAST(f3 AS CHAR),'1') 
FROM nation; 

• 常量推斷：

SELECT * FROM t 
WHERE a < b AND b = c AND a =5 
------> 
SELECT * FROM t 
WHERE b >5AND a =5AND b = c 

• 語義去重：

SELECT * FROM t1 
WHERE max_adate >'2017-05-01' 
    AND max_adate !='2017-04-01' 
------> 
SELECT * FROM t1 
WHERE max_adate > DATE '2017-05-01' 

玄武存儲引擎

為保證大吞吐寫入，以及高并發低時延響應，AnalyticDB自研存儲引擎玄武，采用多項創新的技術架構。玄武存儲引擎采用讀/寫實例分離架構，讀節點和寫節點可分別獨立擴展，提供寫入吞吐或者查詢計算能力。在此架構下大吞吐數據寫入不影響查詢分析性能。同時玄武存儲引擎構筑了智能全索引體系，保證絕大部分計算基于索引完成，保證任意組合條件查詢的毫秒級響應。

讀寫分離架構支持大吞吐寫入

傳統數據倉庫并沒有將讀和寫分開處理，即這些數據庫進程/線程處理請求的時候，不管讀寫都會在同一個實例的處理鏈路上進行。因此所有的請求都共享同一份資源(內存資源、鎖資源、IO資源)，并相互影響。在查詢請求和寫入吞吐都很高的時候，會存在嚴重的資源競爭，導致查詢性能和寫入吞吐都下降。

為了解決這個問題，玄武存儲引擎設計了讀寫分離的架構。如下圖所示，玄武存儲引擎有兩類關鍵的節點：Buffer Node和Compute Node。Buffer Node專門負責處理寫請求，Compute Node專門負責查詢請求，Buffer Node和Compute Node完全獨立并互相不影響，因此，讀寫請求會在兩個完全不相同的鏈路中處理。上層的Front Node會把讀寫請求分別路由給Buffer Node和Compute Node。

實時寫入鏈路：

• 業務實時數據通過JDBC/ODBC協議寫入到Front Node。
• Front Node根據實時數據的hash分區列值，路由到相應Buffer Node。
• Buffer Node將該實時數據的內容(類似于WAL)提交到盤古分布式文件系統，同時更新實時數據版本，并返回Front Node，Front Node返回寫入成功響應到客戶端。
• Buffer Node同時會異步地把實時數據內容推送到Compute Node，Compute Node消費該實時數據并構建實時數據輕量級索引。
• 當實時數據積攢到一定量時，Buffer Node觸發后臺Merge Baseline作業，對實時數據構建完全索引并與基線數據合并。

實時查詢鏈路：

• 業務實時查詢請求通過JDBC/ODBC協議發送到Front Node。
• Front Node首先從Buffer Node拿到當前最新的實時數據版本，并把該版本隨執行計劃一起下發到Compute Node。
• Compute Node檢查本地實時數據版本是否滿足實時查詢要求，若滿足，則直接執行并返回數據。若不滿足，需先到Buffer Node把指定版本的實時數據拖到本地，再執行查詢，以保證查詢的實時性(強一致)。

AnalyticDB提供強實時和弱實時兩種模式，強實時模式執行邏輯描述如上。弱實時模式下，Front Node查詢請求則不帶版本下發，返回結果的實時取決于Compute Node對實時數據的處理速度，一般有秒極延遲。所以強實時在保證數據一致性的前提下，當實時數據寫入量比較大時對查詢性能會有一定的影響。

高可靠性

玄武存儲引擎為Buffer Node和Compute Node提供了高可靠機制。用戶可以定義Buffer Node和Compute Node的副本數目(默認為2)，玄武保證同一個數據分區的不同副本一定是存放在不同的物理機器上。Compute Node的組成采用了對等的熱副本服務機制，所有Compute Node節點都可以參與計算。另外，Computed Node的正常運行并不會受到Buffer Node節點異常的影響。如果Buffer Node節點異常導致Compute Node無法正常拉取最新版本的數據，Compute Node會直接從盤古上獲取數據(即便這樣需要忍受更高的延遲)來保證查詢的正常執行。數據在Compute Node上也是備份存儲。如下圖所示，數據是通過分區存放在不同的ComputeNode上，具有相同hash值的分區會存儲在同一個Compute Node上。數據分區的副本會存儲在其他不同的Compute Node上，以提供高可靠性。

高擴展性

玄武的兩個重要特性設計保證了其高可擴展性：1)Compute Node和Buffer Node都是無狀態的，他們可以根據業務負載需求進行任意的增減;2)玄武并不實際存儲數據，而是將數據存到底層的盤古系統中，這樣，當Compute Node和Buffer Node的數量進行改變時，并不需要進行實際的數據遷移工作。

為計算而生的存儲

數據存儲格式

傳統關系型數據庫一般采用行存儲(Row-oriented Storage)加B-tree索引，優勢在于其讀取多列或所有列(SELECT *)場景下的性能，典型的例子如MySQL的InnoDB引擎。但是在讀取單列、少數列并且行數很多的場景下，行存儲會存在嚴重的讀放大問題。

數據倉庫系統一般采用列存儲(Column-oriented Storage)，優勢在于其單列或少數列查詢場景下的性能、更高的壓縮率(很多時候一個列的數據具有相似性，并且根據不同列的值類型可以采用不同的壓縮算法)、列聚合計算(SUM, AVG, MAX, etc.)場景下的性能。但是如果用戶想要讀取整行的數據，列存儲會帶來大量的隨機IO，影響系統性能。

為了發揮行存儲和列存儲各自的優勢，同時避免兩者的缺點，AnalyticDB設計并實現了全新的行列混存模式。如下圖所示：

• 對于一張表，每k行數據組成一個Row Group。在每個Row Group中，每列數據連續的存放在單獨的block中，每Row Group在磁盤上連續存放。
• Row Group內列block的數據可按指定列(聚集列)排序存放，好處是在按該列查詢時顯著減少磁盤隨機IO次數。
• 每個列block可開啟壓縮。

行列混存存儲相應的元數據包括：分區元數據，列元數據，列block元數據。其中分區元數據包含該分區總行數，單個block中的列行數等信息;列元數據包括該列值類型、整列的MAX/MIN值、NULL值數目、直方圖信息等，用于加速查詢;列block元數據包含該列在單個Row Group中對應的MAX/MIN/SUM、總條目數(COUNT)等信息，同樣用于加速查詢。

全索引計算

用戶的復雜查詢可能會涉及到各種不同的列，為了保證用戶的復雜查詢能夠得到秒級響應，玄武存儲引擎在行列混合存儲的基礎上，為基線數據(即歷史數據)所有列都構建了索引。玄武會根據列的數據特征和空間消耗情況自動選擇構建倒排索引、位圖索引或區間樹索引等，而用的最多的是倒排索引。

如上圖所示，在倒排索引中，每列的數值對應索引的key，該數值對應的行號對應索引的value，同時所有索引的key都會進行排序。依靠全列索引，交集、并集、差集等數據庫基礎操作可以高性能地完成。如下圖所示，用戶的一個復雜查詢包含著對任意列的條件篩選。玄武會根據每個列的條件，去索引中篩選滿足條件的行號，然后再將每列篩選出的行號，進行交、并、差操作，篩選出最終滿足所有條件的行號。玄武會依據這些行號去訪問實際的數據，并返回給用戶。通常經過篩選后，滿足條件的行數可能只占總行數的萬分之一到十萬分之一。因此，全列索引幫助玄武在執行查詢請求的時候，大大減小需要實際遍歷的行數，進而大幅提升查詢性能，滿足任意復雜查詢秒級響應的需求。

使用全列索引給設計帶來了一個很大挑戰：需要對大量數據構建索引，這會是一個非常耗時的過程。如果像傳統數據庫那樣在數據寫入的路徑上進行索引構建，那么這會嚴重影響寫入的吞吐，而且會嚴重拖慢查詢的性能，影響用戶體驗。為了解決這個挑戰，玄武采用了異步構建索引的方式。當寫入請求到達后，玄武把寫SQL持久化到盤古，然后直接返回，并不進行索引的構建。

當這些未構建索引的數據(稱為實時數據)積累到一定數量時，玄武會開啟多個MapReduce任務，來對這些實時數據進行索引的構建，并將實時數據及其索引，同當前版本的基線數據(歷史數據)及其索引進行多版本歸并,形成新版本的基線數據和索引。這些MapReduce任務通過伏羲進行分布式調度和執行，異步地完成索引的構建。這種異步構建索引的方式，既不影響AnalyticDB的高吞吐寫入，也不影響AnalyticDB的高性能查詢。

異步構建索引的機制還會引入一個新問題：在進行MapReduce構建索引的任務之前，新寫入的實時數據是沒有索引的，如果用戶的查詢會涉及到實時數據，查詢性能有可能會受到影響。玄武采用為實時數據構建排序索引(Sorted Index)的機制來解決這個問題。

如下圖所示，玄武在將實時數據以block形式刷到磁盤之前，會根據每一列的實時數據生成對應的排序索引。排序索引實際是一個行號數組，對于升序排序索引來說，行號數組的第一個數值是實時數據最小值對應的行號，第二個數值是實時數據第二小值對應的行號，以此類推。這種情況下，對實時數據的搜索復雜度會從O(N)降低為O(lgN)。排序索引大小通常很小(60KB左右)，因此，排序索引可以緩存在內存中，以加速查詢。

羲和計算引擎

針對低延遲高并發的在線分析場景需求，AnalyticDB自研了羲和大規模分析引擎，其中包括了基于流水線模型的分布式并行計算引擎，以及基于規則 (Rule-Based Optimizer，RBO) 和代價(Cost-Based Optimizer，CBO)的智能查詢優化器。

優化器

優化規則的豐富程度是能否產生最優計劃的一個重要指標。因為只有可選方案足夠多時，才有可能選到最優的執行計劃。AnalyticDB提供了豐富的關系代數轉換規則，用來確保不會遺漏最優計劃。

基礎優化規則：

• 裁剪規則：列裁剪、分區裁剪、子查詢裁剪
• 下推/合并規則：謂詞下推、函數下推、聚合下推、Limit下推
• 去重規則：Project去重、Exchange去重、Sort去重
• 常量折疊/謂詞推導

探測優化規則：

• Joins：BroadcastHashJoin、RedistributedHashJoin、NestLoopIndexJoin
• Aggregate：HashAggregate、SingleAggregate
• JoinReordering
• GroupBy下推、Exchange下推、Sort下推

高級優化規則：CTE

例如下圖中，CTE的優化規則的實現將兩部分相同的執行邏輯合為一個。通過類似于最長公共子序列的算法，對整個執行計劃進行遍歷，并對一些可以忽略的算子進行特殊處理，如Projection，最終達到減少計算的目的。

單純基于規則的優化器往往過于依賴規則的順序，同樣的規則不同的順序會導致生成的計劃完全不同，結合基于代價的優化器則可以通過嘗試各種可能的執行計劃，達到全局最優。

AnalyticDB的代價優化器基于Cascade模型，執行計劃經過Transform模塊進行了等價關系代數變換，對可能的等價執行計劃，估算出按Cost Model量化的計劃代價，并從中最終選擇出代價最小的執行計劃通過Plan Generation模塊輸出，存入Plan Cache(計劃緩存)，以降低下一次相同查詢的優化時間。

在線分析的場景對優化器有很高的要求，AnalyticDB為此開發了三個關鍵特性：存儲感知優化、動態統計信息收集和計劃緩存。

存儲層感知優化

生成分布式執行計劃時，AnalyticDB優化器可以充分利用底層存儲的特性，特別是在Join策略選擇，Join Reorder和謂詞下推方面。

• 底層數據的哈希分布策略將會影響Join策略的選擇。基于規則的優化器，在生成Join的執行計劃時，如果對數據物理分布特性的不感知，會強制增加一個數據重分布的算子來保證其執行語義的正確。 數據重分布帶來的物理開銷非常大，涉及到數據的序列化、反序列化、網絡開銷等等，因此避免多次數據重分布對于分布式計算是非常重要的。除此之外，優化器也會考慮對數據庫索引的使用，進一步減少Join過程中構建哈希的開銷。
• 調整Join順序時，如果大多數Join是在分區列，優化器將避免生成Bushy Tree，而更偏向使用Left Deep Tree，并盡量使用現有索引進行查找。

• 優化器更近一步下推了謂詞和聚合。聚合函數，比如count()，和查詢過濾可以直接基于索引計算。

所有這些組合降低了查詢延遲，同時提高集群利用率，從而使得AnalyticDB能輕松支持高并發。

動態統計信息收集

統計信息是優化器在做基于代價查詢優化所需的基本信息，通常包括有關表、列和索引等的統計信息。傳統數據倉庫僅收集有限的統計信息，例如列上典型的最常值(MFV)。商業數據庫為用戶提供了收集統計信息的工具，但這通常取決于DBA的經驗，依賴DBA來決定收集哪些統計數據，并依賴于服務或工具供應商。

上述方法收集的統計數據通常都是靜態的，它可能需要在一段時間后，或者當數據更改達到一定程度，來重新收集。但是，隨著業務應用程序變得越來越復雜和動態，預定義的統計信息收集可能無法以更有針對性的方式幫助查詢。例如，用戶可以選擇不同的聚合列和列數，其組合可能會有很大差異。但是，在查詢生成之前很難預測這樣的組合。因此，很難在統計收集時決定正確統計方案。但是，此類統計信息可幫助優化器做出正確決定。

我們設計了一個查詢驅動的動態統計信息收集機制來解決此問題。守護程序動態監視傳入的查詢工作負載和特點以提取其查詢模式，并基于查詢模式，分析缺失和有益的統計數據。在此分析和預測之上，異步統計信息收集任務在后臺執行。這項工作旨在減少收集不必要的統計數據，同時使大多數即將到來的查詢受益。對于前面提到的聚合示例，收集多列統計信息通常很昂貴，尤其是當用戶表有大量列的時候。根據我們的動態工作負載分析和預測，可以做到僅收集必要的多列統計信息，同時，優化器能夠利用這些統計數據來估計聚合中不同選項的成本并做出正確的決策。

計劃緩存

從在線應用案件看，大多數客戶都有一個共同的特點，他們經常反復提交類似的查詢。在這種情況下，計劃緩存變得至關重要。為了提高緩存命中率，AnalyticDB不使用原始SQL文本作為搜索鍵來緩存。相反，SQL語句首先通過重寫并參數化來提取模式。例如，查詢 “SELECT * FROM t1 WHERE a = 5 + 5”將轉化為“SELECT * FROM t1 WHERE a =?”。參數化的SQL模版將被作為計劃緩存的關鍵字，如果緩存命中，AnalyticDB將根據新查詢進行參數綁定。由于這個改動，即使使用有限的緩存大小，優化器在生產環境也可以保持高達90%以上的命中率，而之前只能達到40%的命中率。

這種方法仍然有一個問題。假設我們在列a上有索引，“SELECT * FROM t1 WHERE a = 5”的優化計劃可以將索引掃描作為其最佳訪問路徑。但是，如果新查詢是“SELECT * FROM t1 WHERE a = 0”并且直方圖告訴我們數值0在表t1占大多數，那么索引掃描可能不如全表掃描有效。在這種情況下，使用緩存中的計劃并不是一個好的決定。為了避免這類問題，AnalyticDB提供了一個功能Literal Classification，使用列的直方圖對該列的值進行分類，僅當與模式相關聯的常量“5”的數據分布與新查詢中常量“0”的數據分布類似時，才實際使用高速緩存的計劃。否則，仍會對新查詢執行常規優化。

執行引擎

在優化器之下，AnalyticDB在MPP架構基礎上，采用流水線執行的DAG架構，構建了一個適用于低延遲和高吞吐量工作負載的執行器。如下圖所示，當涉及到多個表之間非分區列JOIN時，CN(MPP Worker)會先進行data exchange (shuffling)然后再本地JOIN (SourceTask)，aggregate后發送到上一個stage(MiddleTask)，最后匯總到Output Task。由于絕大多情況都是in-memory計算(除復雜ETL類查詢，盡量無中間Stage 落盤)且各個stage之間都是pipeline方式協作，性能上要比MapReduce方式快一個數量級。

在接下來的幾節中，將介紹其中三種特性，包括混合工作負載管理，CodeGen和矢量化執行。

混合工作負載管理

作為一套完備的實時數倉解決方案，AnalyticDB中既有需要較低響應時間的高并發查詢，也有類似ETL的批處理，兩者爭用相同資源。傳統數倉體系往往在這兩個方面的兼顧性上做的不夠好。

AnalyticDB worker接收coordinator下發的任務, 負責該任務的物理執行計劃的實際執行。這項任務可以來自不同的查詢， worker會將任務中的物理執行計劃按照既定的轉換規則轉換成對應的operator，物理執行計劃中的每一個Stage會被轉換成一個或多個operator。

執行引擎已經可以做到stage/operator級別中斷和Page級別換入換出，同時線程池在所有同時運行的查詢間共享。但是，這之上仍然需要確保高優先級查詢可以獲得更多計算資源。

根據經驗，客戶總是期望他們的短查詢即使當系統負載很重的時候也能快速完成。為了滿足這些要求，基于以上場景，通過時間片的分配比例來體現不同查詢的優先級，AnalyticDB實現了一個簡單版本的類Linux kernel 的調度算法。系統記錄了每一個查詢的總執行耗時，查詢總耗時又是通過每一個Task耗時來進行加權統計的，最終在查詢層面形成了一顆紅黑樹，每次總是挑選最左側節點進行調度，每次取出或者加入(被喚醒以及重新入隊)都會重新更新這棵樹，同樣的，在Task被喚醒加入這顆樹的時候，執行引擎考慮了補償機制，即時間片耗時如果遠遠低于其他Task的耗時，確保其在整個樹里面的位置，同時也避免了因為長時間的阻塞造成的饑餓，類似于CFS 調度算法中的vruntime補償機制。

這個設計雖然有效解決了慢查詢占滿資源，導致其他查詢得不到執行的問題，卻無法保障快查詢的請求延遲。這是由于軟件層面的多線程執行機制，線程個數大于了實際的CPU個數。在實際的應用中，計算線程的個數往往是可用Core的2倍。這也就是說，即使快查詢的算子得到了計算線程資源進行計算，也會在CPU層面與慢查詢的算子形成競爭。所下圖所示，快查詢的算子計算線程被調度到VCore1上，該算子在VCore1上會與慢查詢的計算線程形成競爭。另外在物理Core0上，也會與VCore0上的慢查詢的計算線程形成競爭。

在Kernel sched模塊中，對于不同優先級的線程之間的搶占機制，已經比較完善，且時效性比較高。因而，通過引入kernel層面的控制可以有效解決快查詢低延遲的問題，且無需對算子的實現進行任何的改造。執行引擎讓高優先級的線程來執行快查詢的算子，低優先級的線程來執行慢查詢的算子。由于高優先級線程搶占低優先級線程的機制，快查詢算子自然會搶占慢查詢的算子。此外，由于高優先級線程在Kernel sched模塊調度中，具有較高的優先級，也避免了快慢查詢算子在vcore層面的CPU競爭。

同樣的在實際應用中是很難要求用戶來辨別快慢查詢，因為用戶的業務本身可能就沒有快慢業務之分。另外對于在線查詢，查詢的計算量也是不可預知的。為此，計算引擎在Runtime層面引入了快慢查詢的識別機制，參考Linux kernel中vruntime的方式，對算子的執行時間、調度次數等信息進行統計，當算子的計算量達到給定的慢查詢的閾值后，會把算子從高優先級的線程轉移到低優先級的線程中。這有效提高了在壓力測試下快查詢的響應時間。

代碼生成器

Dynamic code generation(CodeGen)普遍出現在業界的各大計算引擎設計實現中。它不僅能夠提供靈活的實現，減少代碼開發量，同樣在性能優化方面也有著較多的應用。但是同時基于ANTLR ASM的AnalyticDB代碼生成器也引入了數十毫秒編譯等待時間，這在實時分析場景中是不可接受的。為了進一步減少這種延遲，分析引擎使用了緩存來重用生成的Java字節碼。但是，它并非能對所有情況都起很好作用。

隨著業務的廣泛使用以及對性能的進一步追求，系統針對具體的情況對CodeGen做了進一步的優化。使用了Loading Cache對已經生成的動態代碼進行緩存，但是SQL表達式中往往會出現常量(例如，substr(col1,1, 3)，col1 like‘demo%’等)，在原始的生成邏輯中會直接生成常量使用。這導致很多相同的方法在遇到不同的常量值時需要生成一整套新的邏輯。這樣在高并發場景下，cache命中率很低，并且導致JDK的meta區增長速度較快，更頻繁地觸發GC，從而導致查詢延遲抖動。

substr(col1,  1, 3) 
=>  cacheKey<CallExpression(substr), inputReferenceExpression(col1),  constantExpression(1), constantExpression(3)>cacheValue bytecode; 

通過對表達式的常量在生成bytecode階段進行rewrite，對出現的每個常量在Class級別生成對應的成員變量來存儲，去掉了Cachekey中的常量影響因素，使得可以在不同常量下使用相同的生成代碼。命中的CodeGen將在plan階段instance級別的進行常量賦值。

substr(col1,  1, 3) 
=>  cacheKey<CallExpression(substr),  inputReferenceExpression(col1)>cacheValue bytecode; 

在測試與線上場景中，經過優化很多高并發的場景不再出現meta區的GC，這顯著增加了緩存命中率，整體運行穩定性以及平均延遲均有一定的提升。

AnalyticDB CodeGen不僅實現了謂詞評估，還支持了算子級別運算。例如，在復雜SQL且數據量較大的場景下，數據會多次shuffle拷貝，在partitioned shuffle進行數據拷貝的時候很容易出現CPU瓶頸。用于連接和聚合操作的數據Shuffle通常會復制從源數據塊到目標數據塊的行，偽代碼如下所示：

foreach row 
   foreach column 
      type.append(blockSrc, position, blockDest); 

從生產環境，大部分SQL每次shuffle的數據量較大，但是列很少。那么首先想到的就是forloop的展開。那么上面的偽代碼就可以轉換成

foreach  row 
   type(1).append(blockSrc(1), position,  blockDest(1)); 
   type(2).append(blockSrc(2), position,  blockDest(2)); 
   type(3).append(blockSrc(3), position,  blockDest(3)); 

上面的優化通過直接編碼是無法完成的，需要根據SQL具體的column情況動態的生成對應的代碼實現。在測試中1000w的數據量級拷貝延時可以提升24%。

矢量化引擎和二進制數據處理

相對于行式計算，AnalyticDB的矢量化計算由于對緩存更加友好，并避免了不必要的數據加載，從而擁有了更高的效率。在這之上，AnalyticDB CodeGen也將運行態因素考慮在內，能夠輕松利用異構硬件的強大功能。例如，在CPU支持AVX-512指令集的集群，AnalyticDB可以生成使用SIMD的字節碼。同時AnalyticDB內部所有計算都是基于二進制數據，而不是Java Object，有效避免了序列化和反序列化開銷。

極致彈性

在多租戶基礎上，AnalyticDB對每個租戶的DB支持在線升降配，擴縮容，操作過程中無需停服，對業務幾乎透明。以下圖為例：

• 用戶開始可以在云上開通包含兩個C4資源的DB進行業務試用和上線(圖中的P1, P2...代表表的數據分區)
• 隨著業務的增長，當兩個C4的存儲或計算資源無法滿足時，用戶可自主對該DB發起升配或擴容操作，升配+擴容可同時進行。該過程會按副本交替進行，保證整個過程中始終有一個副本提供服務。另外，擴容增加節點后，數據會自動在新老節點間進行重分布。
• 對于臨時性的業務增長(如電商大促)，升配擴容操作均可逆，在大促過后，可自主進行降配縮容操作，做到靈活地成本控制。

在線升降配，平滑擴縮容能力，對今年雙十一阿里巴巴集團內和公共云上和電商物流相關的業務庫起到了至關重要的保障作用。

GPU加速

客戶業務痛點

某客戶數據業務的數據量在半年時間內由不到200TB增加到1PB，并且還在快速翻番，截止到發稿時為止已經超過1PB。該業務計算復雜，查詢時間跨度周期長，需按照任意選擇屬性過濾，單個查詢計算涉及到的算子包括20個以上同時交并差、多表join、多值列(類似array)group by等以及上述算子的各種復雜組合。傳統的MapReduce離線分析方案時效性差，極大限制了用戶快速分析、快速鎖定人群并即時投放廣告的訴求，業務發展面臨新的瓶頸。

AnalyticDB加速方案

GPU加速AnalyticDB的做法是在Compute Node中新增GPU Engine對查詢進行加速。GPU Engine主要包括: Plan Rewriter、Task Manager、Code Generator、CUDA Manager、Data Manager和VRAM Manager。

SQL查詢從Front Node發送到Compute Node，經過解析和邏輯計劃生成以后，Task Manager先根據計算的數據量以及查詢特征選擇由CPU Engine還是GPU Engine來處理，然后根據邏輯計劃生成適合GPU執行的物理計劃。

GPU Engine收到物理計劃后先對執行計劃進行重寫。如果計劃符合融合特征，其中多個算子會被融合成單個復合算子，從而大量減少算子間臨時數據的Buffer傳輸。

Rewriting之后物理計劃進入Code Generator，該模塊主功能是將物理計劃編譯成PTX代碼。Code Generator第一步借助LLVM JIT先將物理計劃編譯成LLVM IR，IR經過優化以后通過LLVMNVPTX Target轉換成PTX代碼。CUDA運行時庫會根據指定的GPU架構型號將PTX轉換成本地可執行代碼，并啟動其中的GPU kernel。Code Generator可以支持不同的Nvidia GPU。

CUDA Manager通過jCUDA調用CUDA API，用于管理和配置GPU設備、GPU kernel的啟動接口封裝。該模塊作為Java和GPU之間的橋梁，使得JVM可以很方便地調用GPU資源。

Data Manager主要負責數據加載，將數據從磁盤或文件系統緩存加載到指定堆外內存，從堆外內存加載到顯存。CPU Engine的執行模型是數據庫經典的火山模型，即表數據需逐行被拉取再計算。這種模型明顯會極大閑置GPU上萬行的高吞吐能力。目前Data Manager能夠批量加載列式數據塊，每次加載的數據塊大小為256M，然后通過PCIe總線傳至顯存。

VRAM Manager用于管理各GPU的顯存。顯存是GPU中最稀缺的資源，需要合理管理和高效復用，有別于現在市面上其他GPU數據庫系統使用GPU的方式，即每個SQL任務獨占所有的GPU及其計算和顯存資源。為了提升顯存的利用率、提升并發能力，結合AnalyticDB多分區、多線程的特點，我們設計基于Slab的VRAM Manager統一管理所有顯存申請：Compute Node啟動時，VRAM Manager先申請所需空間并切分成固定大小的Slab，這樣可以避免運行時申請帶來的時間開銷，也降低通過顯卡驅動頻繁分配顯存的DoS風險。

在需要顯存時，VRAM Manager會從空閑的Slab中查找空閑區域劃分顯存，用完后返還Slab并做Buddy合并以減少顯存空洞。性能測試顯示分配時間平均為1ms，對于整體運行時間而言可忽略不計，明顯快于DDR內存分配的700ms耗時，也利于提高系統整體并發度。在GPU和CPU數據交互時，自維護的JVM堆外內存會作為JVM內部數據對象(如ByteBuffer)和顯存數據的同步緩沖區，也一定程度減少了Full GC的工作量。

GPU Engine采用即時代碼生成技術主要有如下優點：

• 相對傳統火山模型，減少計劃執行中的函數調用等，尤其是分支判斷，GPU中分支跳轉會降低執行性能
• 靈活支持各種復雜表達式,例如projection和having中的復雜表達式。例如HAVING SUM(double_field_foo) > 1這種表達式的GPU代碼是即時生成的
• 靈活支持各種數據類型和UDF查詢時追加
• 利于算子融合，如group-by聚合、join再加聚合的融合，即可減少中間結果(特別是Join的連接結果)的拷貝和顯存的占用

根據邏輯執行計劃動態生成GPU執行碼的整個過程如下所示：

GPU 加速實際效果

該客戶數據業務使用了GPU實時加速后，將計算復雜、響應時間要求高、并發需求高的查詢從離線分析系統切換至AnalyticDB進行在線分析運行穩定，MapReduce離線分析的平均響應時間為5到10分鐘，高峰時可能需要30分鐘以上。無縫升級到GPU加速版AnalyticDB之后，所有查詢完全實時處理并保證秒級返回，其中80%的查詢的響應時間在2秒以內(如下圖)，而節點規模降至原CPU集群的三分之一左右。 業務目前可以隨時嘗試各種圈人標簽組合快速對人群畫像，即時鎖定廣告投放目標。據客戶方反饋，此加速技術已經幫助其在競爭中構建起高壁壘，使該業務成為同類業務的核心能力，預計明年用戶量有望翻番近一個數量級。

總結

簡單對本文做個總結，AnalyticDB做到讓數據價值在線化的核心技術可歸納為：

• 高性能SQL Parser：自研Parser組件FastSQL，極致的解析性能，無縫集合優化器
• 玄武存儲引擎：數據更新實時可見，行列混存，粗糙集過濾，聚簇列，索引優化
• 羲和計算引擎：MPP+DAG融合計算，CBO優化，向量化執行，GPU加速
• 極致彈性：業務透明的在線升降配，擴縮容，靈活控制成本。
• GPU加速：利用GPU硬件加速OLAP分析，大幅度降低查詢延時。

分析型數據AnalyticDB， 作為阿里巴巴自研的下一代PB級實時數據倉庫, 承載著整個集團內和云上客戶的數據價值實時化分析的使命。 AnalyticDB為數據價值在線化而生，作為實時云數據倉庫平臺，接下來會在體驗和周邊生態建設上繼續加快建設，希望能將最領先的下一代實時分析技術能力普惠給所有企業，幫助企業轉型加速數據價值探索和在線化。

【本文為51CTO專欄作者“阿里巴巴官方技術”原創稿件，轉載請聯系原作者】 

戳這里，看該作者更多好文