TiDB 原理與實戰

內容來源：2017年3月4日，PingCAP開發工程師李霞在“七牛架構師實踐日-她時代-大數據與機器學習”進行《HTTPS最佳安全實踐》演講分享。轉載自微信公眾號七牛雲（ID：qiniutek）。
閱讀字數: 2353 用時: 15分鍾

嘉賓演講視頻地址：https://t.cn/R9Zwt0E

1.數據庫的現狀

目前大家熟知的數據庫大致可以分為 RDBMS、NoSQL 和 NewSQL 等。如圖 1 所示。

圖1

如圖 1 所示是一個數據庫解決方案的變遷史，這裏做一些簡單的介紹。以 MySQL 為例剛開始時，它是一個單機模式，但是隨著數據庫的數據量的增加及用戶對性能要求的提高，它的存儲容量和性能都遇到了瓶頸。這些需求催生了新的解決方案，那就是 MySQL 主從模式，進而將讀寫分離，減輕了讀寫係統的負擔。雖然可以是多從，但是主是單點的。接下來就發展到了中間件的解決方案，這個方案優點是能夠在一些限製條件下實現相對擴容，但它是由一種手動的、靜態路由的方式來實現的擴容。那麼對 DBA 在處理擴容操作時的要求就會比較高。之後誕生了 NoSQL 的解決方案，這裏以 HBase 為例：它支持強一致，多版本等，最重要是它在擴容和性能方麵都做的比較好。但是它不支持 SQL 語法，對複雜查詢沒有怎麼支持，還有它的分布式事務不支持跨行。從而引入了 NewSQL 的概念。那麼怎麼理解 NewSQL 呢？NewSQL 可以淺顯地理解為 SQL + NoSQL 的概念，它支持 SQL 語法和分布式事務。

圖 2 是 TiDB 和 TiKV 的架構，具體結構如圖。這邊帶過一下 Coprocessor，它是一個靈活和通用框架擴展，將分布式計算直接放入 TiKV 進行特定處理的功能，這也是我額外介紹它的原因。

圖2

2.TiDB簡介

圖3

TiDB 處理用戶請求的主要流程如圖 2 所示。首先，請求從 Client 端進來後進入語法解析層，然後對語句進行合法性驗證和類型推導，接著做查詢優化——這裏我們分了邏輯優化和物理優化。優化之後會構建一個執行器，最後執行——把數據從 TiKV 取出來進行計算，最後反饋結果。

3.Plan優化

我們主要分兩個層次來做優化。首先是邏輯層優化，它主要是依據關係代數的等價變換規則做優化。接著就是一個物理層優化，它主要根據數據的直方圖分布，表連接順序重排序等技術對查詢進行優化。在邏輯優化的時候，我們會做一些基於規則的優化，然後再進入物理優化，物理優化是基於計算代價的一個優化，需要通過統計信息進行優化，最後執行。

圖4

對於 TP 型的數據庫來說，這兩個優化之後基本上滿足了 TP 的大部分需求。當然我們也不止步於隻支持 TP 型的請求，目前針對一些 AP 型的請求也在優化中。

3.1優化邏輯

目前我們主要做了如下圖的 5 個優化。其中 Prune column 和 Eliminate aggregation 的優化，大家可以看一下圖 5 中優化前後的語句變化。這兩個變化相對簡單就不多解釋了，還有幾個優化會在下麵做具體解釋。

圖5

3.1.1 去關聯化

Decorrelation，也叫子查詢去關聯化，比如有如下語句：

select * from t where t.id in (select id+1 as c2 from s where s.c1 < 10 and s.n = t.n)

那麼我們看一下上麵語句的變化過程。如圖 6 所示，首先看如何將它變成一個圖。SQL 的最外層是 from t ，因此左邊 Plan 有一個 t 的 Data Scan。右邊的子查詢也是同樣的從下往上構建，先是 s 的 Data Scan，然後根據 Where 語句構建出條件為 s.c1 < 10 and s.n = t.n 的 Selection 算子，注意這裏 t.n 是 s 表中不存在的，所以我們需要將它標記為關聯列。再往上它有一個 Select 是 id+1 as c2，這在 TiDB 中對應 Projection 投影算子。中間的 Apply 代表從左邊取一條數據，替換掉右邊 Plan 的關聯列，然後進行 Semi Join ，這裏之所以選擇 Semi Join 是根據 t.id in … 決定的。構建出查詢圖之後進行去關聯化的優化，先是把 s 一側的 Projection 上推，將 c2 替換為 s.id + 1 ，然後把 Selection 往上放到了 Semi Join 的連接條件下。這裏的正確性有一些嚴格的論證過程，因為太複雜了，我就不跟大家解釋了，就簡單介紹一下最後的結果。到了這裏之後，這兩個 Plan 沒有了關聯列，於是可以將 Apply 算子直接改為 Semi Join 。

圖6

3.1.2 謂詞下推

select * from t join s on t.id = s.id where t.c < 1 and s.c < 1

這個語句可以表示成圖 7 左邊的圖。優化就是想把條件 t.c < 1 and s.c < 1 下推到兩邊的執行計劃中。這樣的話，我再計算 Join 的時候輸入的數據會比原來小很多，因為條件的存在，t 和 s 掃表的代價也會減小。推到 T 的時候，直接過濾掉了大於等於 1 的數據再進行 Join。如果把 Join 改一下變成 Left Outer Join，右邊是不能下推的。因為大家知道在 Left Outer Join 裏麵，如果左邊找不到可以匹配的行，需要補 NULL 。如果我把右邊的條件下推了，那麼可能會出現很多補 NULL 的行，這些行沒有了過濾條件，會全部返回。但是下推的這個條件實際上是可以把 NULL 過濾掉的，這樣就會出現優化前後數據不一致的情況，造成正確性問題。所以優化的一個重要前提是前後都要等價，就是說結果是相等的。

圖7

3.1.3 聚合下推

select sum(grade.scores) from stu join grade on stu.id = grade.stu_id and stu.name=“xwz”

如圖 8 所示，這個 SQL 是計算某個人的成績總和，stu 是記錄所有學生信息的表，grade 是記錄所有成績的表。這裏如果我們不做任何優化，這個語句的執行流程是先去做一個Join，然後拿 Join 的結果去做聚合。這裏可以做優化是因為 grade 表的 stu_id 顯然是 stu 的外鍵，它可能冗餘了很多 stu_id 的信息，所以我們可以優先做一個預聚合。整個過程就相當於是把 sum 下推了。注意我們這裏本來是沒有 Group By 列的，下推之後一定要將 Join 條件所有和 grade 相關的列作為聚合列，以保證正確性。

圖8

上麵介紹的是邏輯優化，接下來我跟大家介紹一下物理優化

3.2物理優化

同一個邏輯算子可以對應不同的物理算子，物理優化是指基於統計信息和動態規劃算法計算出不同物理計劃的代價，從而選擇最優計劃的優化。這裏主要分享統計信息是怎麼構建的。首先我們采用了等深直方圖，因為如果使用等寬直方圖會有一些數據傾斜的問題造成較大誤差。統計信息的收集算法大概是這樣，因為直方圖本質上是描述頻率分布，所以我們要求統計的數據是有序的。對於普通 Column 來說，它在 TiKV 中是無序的，我們不可能對整個表的每個 Column 進行排序，這樣開銷太大。這裏我們采用了一個采樣算法，對於一個表隨機選取一萬到十萬行，這樣我們就可以用一個很小的代價來構建每個列的直方圖。不過這個方法的副作用也很明顯，就是不管對於多大的表，我們的采樣數據都是很有限的，需要保證數據量足夠小到能進行內存排序，這樣會對直方圖的準確性造成一定影響。而對於索引列來說，它在 TiKV 中的組織本身就是有序的，那麼我們設計了一些算法利用這些索引列的有序性質，可以在不采樣的前提下，建立準確的直方圖。

圖9
具體的做法是，我們先將 Bucket 的個數限製在 128 到 255，然後每個 Bucket 統計的行數，稱為 Bucket Size，不超過 1 個。當我們讀取數據，第一次 Bucket 數量達到 256 的時候，我們會選擇將相鄰的 Bucket 兩兩合並，然後 BucketSize 乘以 2，流程見圖 9。在合並結束後，Bucket 的數量又會回到 128 的合法值，BucketSize 變為 2。這樣如果有 N 條數據，我們可以用 N*logN 的代價去構建等深直方圖。這樣既可以避免采樣帶來的精度損失，又不會為構建直方圖帶來過多的開銷。

構建直方圖的一個最重要的用途是選擇索引。舉個例子，比如說 select * from t where c1<10 and c2<10 就是會看用哪一個索引代價小，假如說 c1<10，輸出是 10000 個，而 c2<10 輸出是 100 個。使用那個索引直接影響了數據掃描的行數。而利用統計信息就可以很精準的進行估計。

4.MMP的計算框架

首先對大數據的 SQL 計算，基本上用的是 MPP 式的框架，即是分布式又是並行的計算，大概的架構如圖 10 所示。分布式計算的主要優點就是減少計算成本和網絡開銷。比如計算Count(*)，TiDB 會做出對應的物理計劃並將它發送到不同的 TiKV 節點上。然後每個 TiKV 節點會計算他自己的 Count(*) 結果，之後匯總給 TiDB 。TiDB 會將每一個聚合結果全部加起來做一個大和，也就是 sum 操作，得到最終的結果。這樣的話，TiDB 和 TiKV 之間交換的數據量是很少的。因為 TiKV 不需要返回所有的行，每個節點隻要返回一條 count(*) 的計算結果即可。

圖10

簡單介紹對謂詞條件的處理流程。比如圖 11 這個語句查詢年齡大於 20 小於 30 的所有行，首先 TiDB 會檢查 age 是否是索引列。如果是索引列，那麼說明在 TiKV 中 age 列是按照順序排列的。比如 Region 1 存放的是 age 10-20 ，Region 2 存放的是 age 20-30，Region 3 存放的是 age 30-40。那麼 TiDB 可以直接向 Region 2 發送計算請求。如果 age 是無序列，那麼我們就需要向每個 Region 發送計算請求，最後將計算匯總。相對於上麵的算法，這種方式會多很多數據掃描的開銷。而謂詞下推之後，如果語句類似圖 11 的第二個語句，它依然是可以繼續將聚合計算 Count(*) 下推的，過程和之前講的一致。

圖11

我們的 TopN 也是可以下推的，拿圖 11 的第三個 SQL 舉例。如果 age 是無序列，它可以發到每個 Region 計算出每個節點 age 列的前10行，在 TiDB 那邊匯總的數據量是 30 行，再拿 30 行的前 10 行反饋給客戶端，這樣數據量的計算量就很小了。如果 age 是有序的，計算可以更加簡單，直接從按照 Region1 -> Region5 的順序去讀取數據，讀到滿足 10 條時停止即可。

剛剛講到的是分布式計算，我們還有並行優化。比如說我們的 Hash Join 。根據統計信息，我們會判斷 Join 的左右表哪一個是小表，哪一個是大表。然後計算出來把小表放到內存裏，並根據等值條件的 Key 建立哈希表，大表通過多 goroutine 分批取值，匹配哈希表。之後也會支持 Sort Merge Join 等其他 Join 算法，整個就是這樣一個邏輯。

5.Online DDL 實現與優化

之前講到的是 TiDB 和 TiKV 的分布式計算優化過程，之後會講一下我們的 Online DDL 的實現。一般數據庫在進行 DDL 操作時都會鎖表，導致線上對此表的 DML 操作全部進入等待狀態（有些數據支持讀操作，但是也以消耗大量內存為代價），即很多涉及此表的業務都處於阻塞狀態，表越大，影響時間越久。這使得 DBA 在做此類操作前要做足準備，然後挑個天時地利人和的時間段執行。為此，架構師們在設計整個係統的時候都會很慎重的考慮表結構，希望將來不用再修改。但是未來的業務需求往往是不可預估的，所以 DDL 操作無法完全避免。由此可見原先的機製處理 DDL 操作是令許多人都頭疼的事情。接下來會介紹 TiDB 是如何解決此問題的。

TiDB 的解決方案根據 Google F1 的異步 schema 變更算法實現，並做了一些簡單優化。此方案分為兩個部分，一是租約。schema 信息在每台服務的內存中會存儲一份，另外還會持久化到 TiKV。為了保證整個集群中的同一時刻最多隻有前後兩個 schema 版本，約定了一個租約時間，所有服務器在租約到期後都需加載 schema 信息。如果節點無法重新完成續租，它將會自動終止服務並等待被集群管理設施重啟。目前的實現不會終止服務，但是超時的操作會失敗，具體實現這裏不作展開。另一個是中間狀態。假設從無到有的話，當中部分服務在無的狀態，部分服務在有的狀態，那用戶到不同的服務上，能對此數據進行的操作是不同的。那麼我們就拆解成多個中間狀態，比如有 Delete Only、Write Only。拆分狀態時，希望在同一時間裏的兩種狀態不管是哪個狀態，對數據的一致性還有完整性都沒有影響，這就是論文的主要思想，具體論證可以閱讀論文。這裏簡單舉個例子，在某表中新添加一列，一開始是從 None 狀態轉換到 Delete Only 狀態。那麼這個集群中的服務在同一時刻，有一些處於 None 狀態，另一些處於 Delete Only 狀態，處於前者的不能訪問到此列，處於後者的隻能對此列的數據進行刪除，但是此時此列裏麵還沒有數據。那麼從用戶角度看，將請求發到這個集群中同時存在的這兩個狀態的不同服務器，可以認為其操作結果相同。之後的狀態變更情況類似就不多解釋了，有興趣的人可以去看論文或者我們在 Github 上分享的從零開始寫分布式數據庫。

5.1Online DDL實現

圖12

5.1.1 一般的 DDL 請求

目前的方案是是串行執行，雖然並行處理也可以做，但是相對複雜，且收益沒有那麼明顯，等將來我們再做對應的優化。

Online DDL 的主要執行流程如圖 12 。這裏詳細介紹圖中的兩個流程：

1.獲取執行 DDL 語句的權利。
每台 Server 都有一個 Worker，這個 Worker 用於處理 DDL 語句，但是 Worker 隻有成為了 Owner 角色才能真正的執行這個 DDL，這樣才能保證串行化執行。如圖 12 可以看到 Owner 信息存在 TiKV，它有兩個字段，唯一的標識和最近更新此信息的時間戳（LastUpdateTS）。那麼 Server 具體的競選是分兩種情況：

a.Owner 的 id 與此 Server id 一致，那麼用當前時間更新 Owner 的 LastUpdateTS。

b.Owner 的 id 與此 Server id 不一致，且當前的時間與 Owner 的 LastUpdateTS 的差大於 4 * lease，認為原來獲取到 Owner 角色的 Server 出讓了此角色，此 Server 可競選 Owner。

針對多個 Server 競選 Owner 時，通過下層的分布式事務確保隻有一台 Server 能競選成功。

2. 更新最新的 schema 信息。
每個 Server 定期（0.5*lease）加載 schema。在 Server 上的每個事務在提交時會檢查 schema version 是否超時，如果超時此事務不會提交。

5.1.2 特殊的 DDL 請求

包括 Drop Table、Drop Database 和 Truncate Table，這些操作是將 job 放於後台異步處理的。假如說有個 drop table 的請求，且 table 中有上億行的數據，那麼這個操作需要處理很久，而且這個操作以後，此 table 裏麵的數據其實都不再使用。所以我們對這類 DDL 操作做了特殊處理，將此操作換成兩部分：

1.跟原先邏輯一樣，進行狀態轉換。到清理數據那步，隻清理元數據（沒有元數據，訪問不到此 table，且 table id 保證全局唯一，所以不會有數據不一致問題），並將此元信息存儲到 background job 中，最後返回版本變更完成。

2.後台的 Worker 從 background queue 中拿到 job 後會真正地進行數據刪除。

5.2Online DDL優化

圖13

因為 DDL 一般操作都是串行化的，有一些操作涉及的數據量比較大。不管是上千萬條還是上億條，做一個操作就要等幾個小時，或者以天計算。雖然是 Online DDL，但是有一些對數據一致性要求很高的客戶，在一開始接入 TiDB 時，為了能保證安全性，可能還是會選擇等，所以我們做了一些優化。

5.2.1 Add index 優化

原先 add index 最後填充數據就是通過批量處理。這樣做是為了防止此操作的事務與其他在操作此 index 的事務發生衝突，導致整個 add index backfill 的操作重試從而進行分批處理。但是這個批量不是並發處理，隻是為了減少衝突域做的。優化前串行邏輯是先掃一批 key，掃完之後對這批 key 的值進行修改。優化分兩部分，一是減少對 TiKV 的訪問，二是對一些操作進行並發處理。接下來主要介紹下第二部分的優化，此處的並發處理比一般的略微複雜，即真正的並發是在掃完一批 key 後對其進行的解析及真正修改 key 的值的處理。雖然每個 key 區間的長度可控, 但是這個區間的具體值由於一些刪除操作不可預計, 所以需要串行地獲取一批 key。這個優化用 go 處理還是特別方便易懂。通過一個小集群進行一定數量的對比測試後，請求執行時間大約是優化前的 ⅓ （具體需考慮表中數據行數，這些測試中表行數最少也是上萬行）。其中並發個數是通過優化效果和衝突域兩個參考值權衡下調整的。

5.2.2 Add Column 優化

這個優化效果會更加顯著，因為事實上我們最後沒有存那個數據。那麼整個操作就不關心表的數據行數，整個操作隻需要進行 5 個狀態的變更即可。從圖 13 上看出來，此操作前後做了兩個優化：

1.新加列的 Default Value 是一個空值，那麼就不需要實際的去填充。之後對此列的讀取時，從 TiKV 返回的列值為空時，查看此列的元信息，如果它是 NULL 約束則可直接返回空值。

2.新加列的 Default Value 的值非空的情況下，也不用將 Default Value 存儲到 TiKV，這優化是最近做的。隻用將此默認值存到一個字段（Original Default Value）中，在之後做讀取操作時，如果發現 TiKV 返回一個空值，且這個字段中的值非空，那麼將此字段中的值填充給它，然後返回。

除了這兩個優化外，我們還針對性地做了一些其他優化，這邊就不多介紹了。

我們目前比較常用的 DDL 語句基本上都支持了，具體與 MySQL 的兼容情況可以看我們在 github 上的文檔。至於那些還不支持的，我們會根據用戶實際需求進行處理。因為目前開發人員比較有限，所以很歡迎大家給我們提一些 PR，非常感謝。

6.TiKV簡介

圖14
如圖 14，TiKV 對於 TiDB 是做了很多非常重要的支持。開始分享時介紹的分布式數據解決方案中，很多不支持的特性（如圖 14 所示），TiDB 已經支持。圖中所示的特性基本上是通過 TiKV 層實現。比如我們分布式事務是通過 2PC 實現，MVCC 的具體原理在之前的一次分享中已經介紹過了，這裏我就不贅述了。底層引擎用了 RocksDB，集群自動伸縮是通過 PD 和 Raft 協議實現，其中的 PD 用於 TiKV 的集群管理。

感想

簡單介紹一下平常程序員不太看重，但我們團隊還是很重視的幾個方麵。首先是代碼風格方麵。貴司有很多社區經驗很豐富的且代碼能力很強的同事，他們就對代碼簡明性要求很高。這不隻是我原來認為的代碼的簡潔，還包括代碼命名的規範和風格統一。在同事的代碼風格出現分歧的時候，一般借鑒 go 源碼或者一些 GitHub 上麵知名項目的代碼風格作為參照。其中代碼命名方麵在我幾個處女座同事的挑（指）剔（點）下進步很大。

接著就是注釋，大家都說代碼簡潔了就不需要注釋了，但是對一些特殊的複雜功能，注釋還是必須的。這不僅有助於其他人理解你的代碼，而且也讓自己之後閱讀此代碼時能更快速理解。如果 review 這段代碼的同事（對這功能有一定了解）有疑問，說明你的代碼已經略微複雜，那麼能簡化就簡化代碼，不能則加注釋。特別是做開源社區，這方麵要求就更高了。

然後就是測試，特別是數據庫這種對準確性的要求非常高的服務，測試是很重要的。我們目前就已經通過了 800 多萬測試，其中包括一些 MySQL Drivers 的測試，一些常用的 ORM 和一些常用服務的測試。目前還在引入一些其他的測試類型和測試場景的支持。此外就是提高單元測試的覆蓋率，我們的要求是單元測試覆蓋率達到 85% 以上。

以上是我今天分享的內容，感謝聆聽！

相關推薦
MongoDB應用從設計到實現 | 深度解讀
 知數堂聯合創始人葉金榮：MySQL 5.7新時代
近期活動
活動 | 區塊鏈技術如何改變我們的生活
 活動 | 一起出發，吹響Container+的號角

最後更新：2017-08-16 11:32:29

TiDB 原理與實戰

1.數據庫的現狀

2.TiDB簡介

3.Plan優化