TiDB 源碼初探

02-01

作者: @申礫

本文檔面向 TiDB 社區開發者，主要介紹 TiDB 的系統架構、代碼結構以及執行流程。目的是使得開發者閱讀文檔後，可以對 TiDB 項目有一個整體的了解，更好的參與進來。首先會介紹一下大體的結構以及 Golang 包的結構，然後會介紹內部的執行流程，最後會對優化器、執行器這兩個最重要的組件做一些說明。

系統架構

TiDB Server 在整個系統中位於 Load Balancer(或者是 Application) 與底層的存儲引擎之間，主要部分分為三層：

MySQL Protocol 層

接收 MySQL Client 的請求，解析 MySQL Protocol 的包並轉換為 TiDB Session 中的各種命令；處理完成後，將結果結果為 MySQL Protocol 格式，返回給 Client。

SQL 層

解析並執行 SQL 語句，制定查詢計劃並優化，生成執行器並通過 KV 層讀取或寫入數據，最後返回結果給 MySQL Protocol層。這一層是重點，後面會詳細介紹。

KV 層

提供帶事務的（分散式/單機）存儲，在 KV 層和 SQL 層之間，有一層抽象，使得 SQL 層能夠忽略下面不同的 KV 存儲的差異，看到統一的介面。

代碼結構概述

這裡首先會把所有的 package 列出來，然後介紹其主要功能。這一章會比較散，信息量比較大，可以結合下一章節一起理解。

tidb

這個包可以認為是 MySQL Protocol Layer 和 SQL Layer 之間的介面，主要的文件有三個：

session.go: 每一個 session 對象對應一個 MySQL Client 的 connection，MySQL Protocol 層負責管理 connection 與 Session 之間的綁定關係，並且各種 MySQL 查詢/命令都是調用 Session 的介面來執行。

tidb.go: 一些函數，供 session.go 調用

bootstrap.go: 當 TiDB Server 啟動後，如果發現系統未經初始化，會執行初始化流程，詳細信息會在下面的章節中介紹。

docs

一些簡略的文檔，更詳細的文檔參見中文文檔以及英文文檔。

executor

TiDB 執行器，SQL 語句最終會轉化為一系列執行器（物理運算元）的組合。這個包對外暴露的最主要的介面是 Executor:

type Executor interface {nt// 返回下一行數據（如果返回為空，則表明沒有更多數據）nNext() (*Row, error) n// 關閉當前執行器，做一些清理工作ntClose() errornt// 改執行器返回結果的 Schema，包括每個 Field 的詳細信息ntSchema() expression.Scheman}n

各種執行器都會實現這個介面，TiDB 的執行引擎採用 Volcano 模型，執行器之間通過上述三個介面交互，每一個執行器只需要通過 Next 介面從其他執行器獲取數據以及通過 Schema 介面獲取數據的元信息。

plan

這裡是整個 SQL 層的核心，SQL 語句解析成 AST 之後，在這個包中制定出查詢計劃，並對查詢計划進行優化，包括邏輯優化和物理優化。

這個包中還包括下面幾個功能：

validator.go：對 AST 進行合法性驗證

preprocess.go：目前只有 name resolve 這一項

resolver.go：名稱解析，將 SQL 語句中的標識符（database/table/column/alias）解析並綁定到對應的 column 或者是 Field 上。

typeinferer.go：推導結果類型。對於 SQL 語句，不需要執行即可推導出結果的類型。

logical_plan_builder.go: 制定出優化的邏輯查詢計劃

physical_plan_builder.go: 根據邏輯查詢計劃制定出物理查詢計劃

privilege

許可權控制相關介面，具體實現在 privilege/privileges 包中

sessionctx

存放 session 中的狀態信息，比如 session variable 信息，這些信息可以在 session 中獲取，放在單獨的包中主要是理清依賴關係，避免循環依賴問題。

table

table介面，對資料庫中的表做了一層抽象，提供很多對錶的操作（如獲取表的 column 信息、讀取一行數據等），具體實現在 table/tables 中。另外這裡還有對於 Column 以及 Index 的抽象。

tidb-server

tidb-server 程序的 main.go，主要是啟動為 server 的代碼。

server

tMySQL Procotol 層的實現，主要工作是解析協議、傳遞命令/Query。

ast

的定義一個 visitor 然後調用樹中節點的的 Accept 方法，對樹進行遍歷。SQL 語句會解析為一顆抽象語法樹（AST），樹中的節點定義都在這個包下。每個節點都實現了 visitor 介面，可以很簡單

ddl

非同步 Schema 變更相關代碼，類似 Google F1 的論文實現。演算法詳解。

domain

domain 可以認為是一個存儲空間，可以在其中創建資料庫、創建表，不同的 domain 之間，可以存在相同名稱的資料庫，有點像 Name Space。domain 上會綁定 information schema 信息。

expression

表達式的定義，最重要的介面是 :

type Expression interface {n.....n}n

目前實現這個介面的表達式包括：

Scalar Function：標量函數表達式

Aggregate Function：聚合函數表達式

Column：列表達式

Const：常量表達式

evaluator

表達式求值相關邏輯，所有的表達式求值方法都在這裡。

infoschema

InformationSchema 的實現，提供 db/table/column 相關信息。

KV 相關的介面定義和部分實現，包括 Retriever / Mutator / Transaction / Snapshot / Storage / Iterator 等。對下層的多種KV存儲做了一個統一的抽象。

model

TiDB 支持的 ddl / dml 相關的數據結構，包括 DBInfo / TableInfo / ColumnInfo / IndexInfo 等

parser

語法解析模塊，主要包括詞法解析 (lexer.go) 和語法解析 (parser.y)，這個包對外的主要介面是 Parse()，用於將 SQL 文本解析成 AST。

store

底層 KV 存儲的實現，如果要接入新的存儲引擎，可以將其進行包裝，代碼放在這個包下面，目前接入兩個引擎：分散式引擎（tikv）和單機引擎（localstore/{goleveldb/boltdb}）。這裡的新引擎需要實現 kv 包中定義的介面。

關於kv和store，可以參考 TiDB 存儲引擎接入指南

terror

定義了 TiDB 的 error 體系。

context

context介面，session 是 context 介面的一個實現，這裡抽象出介面來，主要是避免循環依賴。session 各種各種狀態信息都通過這個介面存取。

inspectkv

TiDB SQL Data 和 KV 輔助 check 包，以後會用於外部對於 TiDB KV 的訪問，將被重新定義和擴展

meta

TiDB 的 meta 數據相關常量定義以及常用函數定義。meta/autoid 定義了一個用於生成全局唯一session內自增 ID 的API，meta 信息依賴於這個工具。

mysql

MySQL 相關的常量定義。

structure

在 key-value上做了一層封裝，支持更豐富的支持 Transaction 的 KV 類型，包括 string / list / hash 等。主要在非同步 Schema 變更中使用。

util

一些工具類，這裡有一個包比較重要，就是 types 包，裡面有很多和類型的定義以及對各種類型對象的操作。

distsql

分散式 SQL 執行介面，如果下層的存儲引擎支持分散式執行器，可以通過這個介面發送請求，後面會詳細介紹這個模塊。

Protocol 層

協議層是和應用交互的介面，目前 TiDB 只支持 MySQL 協議，相關的代碼都在 server 包中。這一層的主要功能是管理客戶端 connection，解析 MySQL 命令並返回執行結果。這一層是按照 MySQL 協議實現，具體的協議可以參考：14 MySQL Client/Server Protocol

單個 connection 處理命令的入口方法是 clientConn 類的 dispatch 方法，這裡會解析協議並調用不同的處理函數。

SQL 層

經過上面章節，讀者已經了解了 TiDB 整體框架以及各個包的細節，本章開始講解核心章節，對 TiDB 的 SQL 層如何 work 做一個簡要的介紹。這裡忽略具體的 KV 層，只關注 SQL 層。希望通過本章，讀者可以了解一條 SQL 語句是如何從一段文本變成執行結果集。整個流程中的詳細過程會在接下來的幾個章節中說明。

大體上講，一條 SQL 語句需要經過，語法解析-->合法性驗證-->制定查詢計劃-->優化查詢計劃-->根據計劃生成查詢器-->執行並返回結果等一系列流程。TiDB 的執行流程以這個為基礎，流程圖如下：

整個流程的入口在 tidb 包的 session.go 中，TiDB-Server 調用 Session.Execute() 介面，輸入為文本格式的 SQL 語句，實現在 session.Execute()。

首先會調用 Compile() 對 SQL 語句進行語法解析（tidb.Parse()），解析後會得到一個 stmt 的列表，這裡每條語句都是一個 AST（抽象語法樹），每一個語法單元都是數的一個 Node，結構定義都在 ast 包中。

得到 AST 之後，調用 executor 包中的 Compiler，輸入 AST，得到執行器（Compiler.Compile()）。在這個過程中，會完成合法性驗證、制定計劃以及優化查詢計劃。

進入 Compiler.Compile() 函數，首先會調用 plan.Validate() 對語句進行合法性驗證（見 plan/validator.go），然後進入 Preprocess 流程，目前這個階段，Preprocess 只做了名稱解析工作，及將 SQL 語句中的提到的 column 名或者 alias name 綁定到對應的 field上。比如」select c from t;」這個語句，會將 c 這個名字綁定到 t 這個表的對應列上（具體的實現見 plan/resolver.go）。之後就進入 optimizer.Optimize()。

Optimize() 方法中，首先對 AST 中各個node的結果進行推導，如

select 1, xx, c from t;

對於 select fields，第一個 field是 1，其類型為 Longlong，第二個 field 是 xx , 其類型為 VarString，第三個field是 c, 其類型為表 t 中 column c 的類型。注意這裡除了類別之外還有 charset 等信息，都要進行推導，具體實現見 plan/typeinferer.go。完成類型推導後，進行邏輯優化（planBuilderbuild()），主要工作是根據代數運算，對 AST 進行等價變換，化簡 AST。比如

select c from t where c > 1+1*2;

可以等價變換為

select c from t where c > 3;

邏輯優化完成後，進行物理優化，生成查詢計劃樹，並利用索引、根據一些 rule 以及 cost 模型，對樹進行變換，減少查詢過程的代價，入口在 plan/optimizer.go 中的 doOptimize()方法。

t生成查詢計劃後，會轉換為執行器，通過 Exec 介面執行得到 RecordSet對象，對其調用 Next() 方法獲取查詢結果。

優化器

優化器是資料庫的核心，決定了每條語句如何執行。如果說資料庫是一支軍隊，那麼優化器就是這支軍隊的主將、軍師，需要運籌帷幄，決勝於千里之外。俗話說一將無能累死三軍，同樣的一條語句，選擇不同的查詢計劃，最終的運行時間可能會相差很大。對優化器的研究一直是學術界比較活躍的領域，優化是永無止境，可以說在這塊投入多大的精力都不為過。

從優化方法上，大致可以分為三類：

Rule based optimizer：通過啟發式規則對 plan 進行優化
Cost based optimizer：通過計算查詢代價對 plan 進行優化
History based optimizer：通過歷史查詢信息對 plan 進行優化

基於規則的優化器比較容易實現，只要選取一些常用的規則，就可以對大多數常用的查詢有較好的效果。但是其缺陷也比較明顯：無法根據數據的真實情況，選擇最優的方案。比如對於查詢語句「select * from t where c1 = 10 and c2 > 100」在選擇索引時，如果只根據規則，那麼一定是選擇 c1 上面的索引進行查詢，但是如果 t 中 c1 所有的值都是 10，那麼這個查詢計劃就很差。這個時候如果有表中數據分布的信息，對選擇好的查詢計劃很有幫助。

基於代價的優化器複雜一些，其核心問題有兩個，一個是如何獲取數據的真實分布信息，另一個是如何根據這些信息，估算出某一個查詢計劃所需的代價。

基於歷史信息的查詢優化器用的比較少，一般 OLTP 資料庫中不會涉及。

TiDB 的優化器相關代碼在 plan 包中，這個包的主要工作是將 AST 轉換為查詢計劃樹，樹中的節點是各種邏輯運算元或者是物理運算元，對查詢計劃化的各種優化都是通過調用樹根節點的各種方法，遞歸地對所有節點進行優化，並且會不斷的對樹中的節點進行轉換和裁剪。

最重要的幾個介面在 plan.go 中，包括：

Plan：所有查詢計劃的介面t

LogicalPlan：邏輯查詢計劃，所有的邏輯運算元都需要實現這個介面

PhysicalPlan：物理查詢計劃，所有的物理運算元都需要實現這個介面

邏輯優化的入口是 planbuilder.build()，輸入是 AST，輸出是邏輯查詢計劃樹。然後在這棵樹上進行邏輯查詢優化：

調用 LogicalPlan 的 PredicatePushDown 介面，將謂詞儘可能下推
調用 LogicalPlan 的 PruneColumns 介面，將不需要的列裁減掉
調用 aggPushDownSolver.aggPushDown，將聚合運算元下推到 Join 之前

拿到邏輯優化後的查詢計劃樹之後，會進行物理優化，代碼的入口是對邏輯查詢計劃樹的根節點調用 convert2PhysicalPlan(&requiredProperty{})，其中 requiredProperty 是對下層返回結果順序、行數的要求。

邏輯查詢計劃樹從根節點開始，不斷的遞歸調用，將每個節點從邏輯運算元轉成物理運算元，並且根據每個節點的查詢代價找到一條比較好的查詢路徑。

執行器

雖然優化器是最核心的組件，但是缺少優秀的執行器，依舊無法構成一個優秀的資料庫。同樣以軍隊為例，執行器就是軍隊中衝鋒陷陣的士兵。再厲害的將軍，如果沒有一群能征善戰的士兵，同樣無法打勝仗。

相比 MySQL，TiDB 的執行器有兩個有點，第一是整個計算框架是一個 MPP 的框架，計算會在多台 TiKV 以及 TiDB 節點上進行，儘可能提高效率和速度；第二是單個運算元會儘可能並行，比如 Join/Union 等運算元，會啟動多個線程同時計算，整個數據計算流程構成一個 pipeline，儘可能縮短每個運算元的等待時間。所以 TiDB 在處理大量數據時，比 MySQL 表現好。

執行器最重要的介面在 executor.go 中:

// Executor executes a query.ntype Executor interface {ntNext() (*Row, error)ntClose() errorntSchema() expression.Scheman}n

通過優化器得到的物理查詢計劃樹會轉換為一個執行器樹，樹中的每個節點都會實現這個介面，執行器之間通過 Next 介面傳遞數據。比如 select c1 from t where c2 > 10; 最終生成的執行器是 Projection->Filter->TableScan 這三個執行器，最上層的 Projection 會不斷的調用下層執器的 Next 介面，最終調到底層的 TableScan，從表中獲取數據。

分散式執行器

TiDB 作為分散式資料庫，內置一個分散式的計算框架，Query 在執行的時候，會盡量分散式+並行。這個框架的入口在 distsql 包中，最重要的是下面兩個介面：

DistSQL 提供的對外最重要的一個介面是 Select()。第一個參數 kv.Client，只要 KV 引擎滿足帶事務、滿足 KV 介面，並且滿足這個 Client 的一些介面，就可以接入 TiDB。目前有一些其他的廠商和 TiDB 合作開發，在其他的 KV 上 run TiDB，並且支持分散式的 SQL。第二個參數是 SelectRequest 。這個東西是由上層執行器構造出來的，它把計算上的邏輯，比如說一些表達式要不要排序、要不要做聚合，所有的信息都放在 req 裡邊，是一個 Protobuf 結構，然後發給 Select 介面，最終會發送到進行計算的 TiKV region server 上。

分散式執行器在 TiDB 端的主要工作是做任務的分發和結果的收集。Select 介面返回一個數據結構，叫 SelectResult ，這個結構可以認為是一個迭代器，因為下層是有很多 region server，每個節點返回的結果是一個 PartialResult。在這些部分結果之上封裝了一個 SelectResult ，就是一個 PartialResult 的迭代器。通過這個的 next 方法可以拿到下一個 PartialResult 。

SelectResult 的內部實現可以認為是個 pipeline。TiDB 會並發地向各個 region server 發請求，並且按照預定的順序返回結果給上層，這裡的順序是由下層結果返回順序以及 Select 介面的 KeepOrder 參數共同決定。

這部分相關的代碼可以參看 distsql 包以及 store/tikv/coprocessor.go。