我來組成頭部 – RDBMS和NoSQL的最佳組合TiDB

TiDB 是 PingCAP 公司設計的開源分佈式 HTAP (Hybrid Transactional and Analytical Processing) 數據庫，結合了傳統的 RDBMS 和 NoSQL 的最佳特性。TiDB 兼容 MySQL，支持無限的水平擴展，具備強一致性和高可用性。TiDB 的目標是為 OLTP (Online Transactional Processing) 和 OLAP (Online Analytical Processing) 場景提供一站式的解決方案。

TiDB 具備如下特性：

  • 高度兼容 MySQL 大多數情況下，無需修改代碼即可從 MySQL 輕鬆遷移至 TiDB，分庫分表後的 MySQL 集群亦可通過 TiDB 工具進行實時遷移。
  • 水平彈性擴展 通過簡單地增加新節點即可實現 TiDB 的水平擴展，按需擴展吞吐或存儲，輕鬆應對高並發、海量數據場景。
  • 分佈式事務 TiDB 100% 支持標準的 ACID 事務。
  • 真正金融級高可用 相比於傳統主從 (M-S) 複製方案，基於 Raft 的多數派選舉協議可以提供金融級的 100% 數據強一致性保證，且在不丟失大多數副本的前提下，可以實現故障的自動恢復 (auto-failover)，無需人工介入。
  • 一站式 HTAP 解決方案 TiDB 作為典型的 OLTP 行數據庫，同時兼具強大的 OLAP 性能，配合 TiSpark，可提供一站式 HTAP 解決方案，一份存儲同時處理 OLTP & OLAP，無需傳統繁瑣的 ETL 過程。
  • 雲原生 SQL 數據庫 TiDB 是為雲而設計的數據庫，支持公有雲、私有雲和混合雲，使部署、配置和維護變得十分簡單。

TiDB 的設計目標是 100% 的 OLTP 場景和 80% 的 OLAP 場景，更複雜的 OLAP 分析可以通過PingCAP公司開噶的TiSpark項目來完成。

TiDB 對業務沒有任何侵入性，能優雅的替換傳統的數據庫中間件、數據庫分庫分表等 Sharding 方案。同時它也讓開發運維人員不用關注數據庫 Scale 的細節問題，專註於業務開發，極大的提升研發的生產力。

TiDB 技術內幕 – 存儲篇

數據庫、操作系統和編譯器並稱為三大系統，可以說是整個計算機軟件的基石。其中數據庫更靠近應用層，是很多業務的支撐。這一領域經過了幾十年的發展，不斷的有新的進展。

很多人用過數據庫，但是很少有人實現過一個數據庫，特別是實現一個分佈式數據庫。了解數據庫的實現原理和細節，一方面可以提高個人技術，對構建其他系統有幫助，另一方面也有利於用好數據庫。

研究一門技術最好的方法是研究其中一個開源項目，數據庫也不例外。單機數據庫領域有很多很好的開源項目，其中 MySQL 和 PostgreSQL 是其中知名度最高的兩個，不少同學都看過這兩個項目的代碼。但是分佈式數據庫方面，好的開源項目並不多。TiDB 目前獲得了廣泛的關注，特別是一些技術愛好者，希望能夠參與這個項目。由於分佈式數據庫自身的複雜性，很多人並不能很好的理解整個項目，所以我希望能寫一些文章，自頂向下，由淺入深，講述 TiDB 的一些技術原理，包括用戶可見的技術以及大量隱藏在 SQL 界面後用戶不可見的技術點。

保存數據

數據庫最根本的功能是能把數據存下來，所以我們從這裡開始。

保存數據的方法很多，最簡單的方法是直接在內存中建一個數據結構，保存用戶發來的數據。比如用一個數組，每當收到一條數據就向數組中追加一條記錄。這個方案十分簡單，能滿足最基本，並且性能肯定會很好，但是除此之外卻是漏洞百出，其中最大的問題是數據完全在內存中，一旦停機或者是服務重啟，數據就會永久丟失。

為了解決數據丟失問題，我們可以把數據放在非易失存儲介質（比如硬盤）中。改進的方案是在磁盤上創建一個文件，收到一條數據，就在文件中 Append 一行。OK，我們現在有了一個能持久化存儲數據的方案。但是還不夠好，假設這塊磁盤出現了壞道呢？我們可以做 RAID （Redundant Array of Independent Disks），提供單機冗餘存儲。如果整台機器都掛了呢？比如出現了火災，RAID 也保不住這些數據。我們還可以將存儲改用網絡存儲，或者是通過硬件或者軟件進行存儲複製。到這裡似乎我們已經解決了數據安全問題，可以鬆一口氣了。But，做複製過程中是否能保證副本之間的一致性？也就是在保證數據不丟的前提下，還要保證數據不錯。保證數據不丟不錯只是一項最基本的要求，還有更多令人頭疼的問題等待解決：

  • 能否支持跨數據中心的容災？
  • 寫入速度是否夠快？
  • 數據保存下來後，是否方便讀取？
  • 保存的數據如何修改？如何支持並發的修改？
  • 如何原子地修改多條記錄？

這些問題每一項都非常難，但是要做一個優秀的數據存儲系統，必須要解決上述的每一個難題。為了解決數據存儲問題，我們開發了 TiKV 這個項目。接下來我向大家介紹一下 TiKV 的一些設計思想和基本概念。

Key-Value

作為保存數據的系統，首先要決定的是數據的存儲模型，也就是數據以什麼樣的形式保存下來。TiKV 的選擇是 Key-Value 模型，並且提供有序遍歷方法。簡單來講，可以將 TiKV 看做一個巨大的 Map，其中 Key 和 Value 都是原始的 Byte 數組，在這個 Map 中，Key 按照 Byte 數組總的原始二進制比特位比較順序排列。大家這裡需要對 TiKV 記住兩點：

  • 這是一個巨大的 Map，也就是存儲的是 Key-Value pair
  • 這個 Map 中的 Key-Value pair 按照 Key 的二進制順序有序，也就是我們可以 Seek 到某一個 Key 的位置，然後不斷的調用 Next 方法以遞增的順序獲取比這個 Key 大的 Key-Value

講了這麼多，有人可能會問了，這裡講的存儲模型和 SQL 中表是什麼關係？在這裡有一件重要的事情要說四遍：

這裡的存儲模型和 SQL 中的 Table 無關！這裡的存儲模型和 SQL 中的 Table 無關！這裡的存儲模型和 SQL 中的 Table 無關！這裡的存儲模型和 SQL 中的 Table 無關！

現在讓我們忘記 SQL 中的任何概念，專註於討論如何實現 TiKV 這樣一個高性能高可靠性的巨大的（分佈式的） Map。

RocksDB

任何持久化的存儲引擎，數據終歸要保存在磁盤上，TiKV 也不例外。但是 TiKV 沒有選擇直接向磁盤上寫數據，而是把數據保存在 RocksDB 中，具體的數據落地由 RocksDB 負責。這個選擇的原因是開發一個單機存儲引擎工作量很大，特別是要做一個高性能的單機引擎，需要做各種細緻的優化，而 RocksDB 是一個非常優秀的開源的單機存儲引擎，可以滿足我們對單機引擎的各種要求，而且還有 Facebook 的團隊在做持續的優化，這樣我們只投入很少的精力，就能享受到一個十分強大且在不斷進步的單機引擎。當然，我們也為 RocksDB 貢獻了一些代碼，希望這個項目能越做越好。這裡可以簡單的認為 RocksDB 是一個單機的 Key-Value Map。

Raft

好了，萬里長征第一步已經邁出去了，我們已經為數據找到一個高效可靠的本地存儲方案。俗話說，萬事開頭難，然後中間難，最後結尾難。接下來我們面臨一件更難的事情：如何保證單機失效的情況下，數據不丟失，不出錯？簡單來說，我們需要想辦法把數據複製到多台機器上，這樣一台機器掛了，我們還有其他的機器上的副本；複雜來說，我們還需要這個複製方案是可靠、高效並且能處理副本失效的情況。聽上去比較難，但是好在我們有 Raft 協議。Raft 是一個一致性算法，它和 Paxos 等價，但是更加易於理解。

Raft 是一個一致性協議，提供幾個重要的功能：

  • Leader 選舉
  • 成員變更
  • 日誌複製

TiKV 利用 Raft 來做數據複製，每個數據變更都會落地為一條 Raft 日誌，通過 Raft 的日誌複製功能，將數據安全可靠地同步到 Group 的多數節點中。

到這裡我們總結一下，通過單機的 RocksDB，我們可以將數據快速地存儲在磁盤上；通過 Raft，我們可以將數據複製到多台機器上，以防單機失效。數據的寫入是通過 Raft 這一層的接口寫入，而不是直接寫 RocksDB。通過實現 Raft，我們擁有了一個分佈式的 KV，現在再也不用擔心某台機器掛掉了。

Region

講到這裡，我們可以提到一個 非常重要的概念：Region。這個概念是理解後續一系列機制的基礎，請仔細閱讀這一節。

前面提到，我們將 TiKV 看做一個巨大的有序的 KV Map，那麼為了實現存儲的水平擴展，我們需要將數據分散在多台機器上。這裡提到的數據分散在多台機器上和 Raft 的數據複製不是一個概念，在這一節我們先忘記 Raft，假設所有的數據都只有一個副本，這樣更容易理解。

對於一個 KV 系統，將數據分散在多台機器上有兩種比較典型的方案：一種是按照 Key 做 Hash，根據 Hash 值選擇對應的存儲節點；另一種是分 Range，某一段連續的 Key 都保存在一個存儲節點上。TiKV 選擇了第二種方式，將整個 Key-Value 空間分成很多段，每一段是一系列連續的 Key，我們將每一段叫做一個 Region，並且我們會盡量保持每個 Region 中保存的數據不超過一定的大小(這個大小可以配置，目前默認是 64mb)。每一個 Region 都可以用 StartKey 到 EndKey 這樣一個左閉右開區間來描述。

注意，這裡的 Region 還是和 SQL 中的表沒什麼關係！ 請各位繼續忘記 SQL，只談 KV。將數據劃分成 Region 後，我們將會做 兩件重要的事情：

  • 以 Region 為單位，將數據分散在集群中所有的節點上，並且盡量保證每個節點上服務的 Region 數量差不多
  • 以 Region 為單位做 Raft 的複製和成員管理

這兩點非常重要，我們一點一點來說。

先看第一點，數據按照 Key 切分成很多 Region，每個 Region 的數據只會保存在一個節點上面。我們的系統會有一個組件來負責將 Region 儘可能均勻的散布在集群中所有的節點上，這樣一方面實現了存儲容量的水平擴展（增加新的結點後，會自動將其他節點上的 Region 調度過來），另一方面也實現了負載均衡（不會出現某個節點有很多數據，其他節點上沒什麼數據的情況）。同時為了保證上層客戶端能夠訪問所需要的數據，我們的系統中也會有一個組件記錄 Region 在節點上面的分佈情況，也就是通過任意一個 Key 就能查詢到這個 Key 在哪個 Region 中，以及這個 Region 目前在哪個節點上。至於是哪個組件負責這兩項工作，會在後續介紹。

對於第二點，TiKV 是以 Region 為單位做數據的複製，也就是一個 Region 的數據會保存多個副本，我們將每一個副本叫做一個 Replica。Replica 之間是通過 Raft 來保持數據的一致（終於提到了 Raft），一個 Region 的多個 Replica 會保存在不同的節點上，構成一個 Raft Group。其中一個 Replica 會作為這個 Group 的 Leader，其他的 Replica 作為 Follower。所有的讀和寫都是通過 Leader 進行，再由 Leader 複製給 Follower。大家理解了 Region 之後，應該可以理解下面這張圖：

我們以 Region 為單位做數據的分散和複製，就有了一個分佈式的具備一定容災能力的 KeyValue 系統，不用再擔心數據存不下，或者是磁盤故障丟失數據的問題。這已經很 Cool，但是還不夠完美，我們需要更多的功能。

MVCC

很多數據庫都會實現多版本控制（MVCC），TiKV 也不例外。設想這樣的場景，兩個 Client 同時去修改一個 Key 的 Value，如果沒有 MVCC，就需要對數據上鎖，在分佈式場景下，可能會帶來性能以及死鎖問題。TiKV 的 MVCC 實現是通過在 Key 後面添加 Version 來實現，簡單來說，沒有 MVCC 之前，可以把 TiKV 看做這樣的：

Key1 -> Value  	Key2 -> Value  	……  	KeyN -> Value

有了 MVCC 之後，TiKV 的 Key 排列是這樣的：

Key1-Version3 -> Value  	Key1-Version2 -> Value  	Key1-Version1 -> Value  	……  	Key2-Version4 -> Value  	Key2-Version3 -> Value  	Key2-Version2 -> Value  	Key2-Version1 -> Value  	……  	KeyN-Version2 -> Value  	KeyN-Version1 -> Value  	……

注意，對於同一個 Key 的多個版本，我們把版本號較大的放在前面，版本號小的放在後面（回憶一下 Key-Value 一節我們介紹過的 Key 是有序的排列），這樣當用戶通過一個 Key + Version 來獲取 Value 的時候，可以將 Key 和 Version 構造出 MVCC 的 Key，也就是 Key-Version。然後可以直接 Seek(Key-Version)，定位到第一個大於等於這個 Key-Version 的位置。

事務

TiKV 的事務採用的是 Percolator 模型，並且做了大量的優化。事務的細節這裡不詳述，大家可以參考論文以及我們的其他文章。這裡只提一點，TiKV 的事務採用樂觀鎖，事務的執行過程中，不會檢測寫寫衝突，只有在提交過程中，才會做衝突檢測，衝突的雙方中比較早完成提交的會寫入成功，另一方會嘗試重新執行整個事務。當業務的寫入衝突不嚴重的情況下，這種模型性能會很好，比如隨機更新表中某一行的數據，並且表很大。但是如果業務的寫入衝突嚴重，性能就會很差，舉一個極端的例子，就是計數器，多個客戶端同時修改少量行，導致衝突嚴重的，造成大量的無效重試。

其他

到這裡，我們已經了解了 TiKV 的基本概念和一些細節，理解了這個分佈式帶事務的 KV 引擎的分層結構以及如何實現多副本容錯。下一節會介紹如何在 KV 的存儲模型之上，構建 SQL 層。

TiDB 技術內幕 – 計算篇

關係模型到 Key-Value 模型的映射

在這我們將關係模型簡單理解為 Table 和 SQL 語句，那麼問題變為如何在 KV 結構上保存 Table 以及如何在 KV 結構上運行 SQL 語句。假設我們有這樣一個表的定義：

CREATE TABLE User {  	ID int,  	Name varchar(20),  Role varchar(20),  	Age int,  PRIMARY KEY (ID),  Key idxAge (age)  };

SQL 和 KV 結構之間存在巨大的區別，那麼如何能夠方便高效地進行映射，就成為一個很重要的問題。一個好的映射方案必須有利於對數據操作的需求。那麼我們先看一下對數據的操作有哪些需求，分別有哪些特點。

對於一個 Table 來說，需要存儲的數據包括三部分：

  • 表的元信息
  • Table 中的 Row
  • 索引數據

表的元信息我們暫時不討論，會有專門的章節來介紹。對於 Row，可以選擇行存或者列存，這兩種各有優缺點。TiDB 面向的首要目標是 OLTP 業務，這類業務需要支持快速地讀取、保存、修改、刪除一行數據，所以採用行存是比較合適的。

對於 Index，TiDB 不止需要支持 Primary Index，還需要支持 Secondary Index。Index 的作用的輔助查詢，提升查詢性能，以及保證某些 Constraint。查詢的時候有兩種模式，一種是點查，比如通過 Primary Key 或者 Unique Key 的等值條件進行查詢，如 select name from user where id=1; ，這種需要通過索引快速定位到某一行數據；另一種是 Range 查詢，如 select name from user where age > 30 and age < 35;，這個時候需要通過idxAge索引查詢 age 在 30 和 35 之間的那些數據。Index 還分為 Unique Index 和 非 Unique Index，這兩種都需要支持。

分析完需要存儲的數據的特點，我們再看看對這些數據的操作需求，主要考慮 Insert/Update/Delete/Select 這四種語句。

對於 Insert 語句，需要將 Row 寫入 KV，並且建立好索引數據。

對於 Update 語句，需要將 Row 更新的同時，更新索引數據（如果有必要）。

對於 Delete 語句，需要在刪除 Row 的同時，將索引也刪除。

上面三個語句處理起來都很簡單。對於 Select 語句，情況會複雜一些。首先我們需要能夠簡單快速地讀取一行數據，所以每個 Row 需要有一個 ID （顯示或隱式的 ID）。其次可能會讀取連續多行數據，比如 Select * from user;。最後還有通過索引讀取數據的需求，對索引的使用可能是點查或者是範圍查詢。

大致的需求已經分析完了，現在讓我們看看手裡有什麼可以用的：一個全局有序的分佈式 Key-Value 引擎。全局有序這一點重要，可以幫助我們解決不少問題。比如對於快速獲取一行數據，假設我們能夠構造出某一個或者某幾個 Key，定位到這一行，我們就能利用 TiKV 提供的 Seek 方法快速定位到這一行數據所在位置。再比如對於掃描全表的需求，如果能夠映射為一個 Key 的 Range，從 StartKey 掃描到 EndKey，那麼就可以簡單的通過這種方式獲得全表數據。操作 Index 數據也是類似的思路。接下來讓我們看看 TiDB 是如何做的。

TiDB 對每個表分配一個 TableID，每一個索引都會分配一個 IndexID，每一行分配一個 RowID（如果表有整數型的 Primary Key，那麼會用 Primary Key 的值當做 RowID），其中 TableID 在整個集群內唯一，IndexID/RowID 在表內唯一，這些 ID 都是 int64 類型。

每行數據按照如下規則進行編碼成 Key-Value pair：

Key: tablePrefix{tableID}_recordPrefixSep{rowID}  Value: [col1, col2, col3, col4]

其中 Key 的 tablePrefix/recordPrefixSep 都是特定的字符串常量，用於在 KV 空間內區分其他數據。

對於 Index 數據，會按照如下規則編碼成 Key-Value pair：

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue  Value: rowID

Index 數據還需要考慮 Unique Index 和非 Unique Index 兩種情況，對於 Unique Index，可以按照上述編碼規則。但是對於非 Unique Index，通過這種編碼並不能構造出唯一的 Key，因為同一個 Index 的 tablePrefix{tableID}_indexPrefixSep{indexID} 都一樣，可能有多行數據的 ColumnsValue 是一樣的，所以對於非 Unique Index 的編碼做了一點調整：

Key: tablePrefix{tableID}_indexPrefixSep{indexID}_indexedColumnsValue_rowID  Value: null

這樣能夠對索引中的每行數據構造出唯一的 Key。注意上述編碼規則中的 Key 裏面的各種 xxPrefix 都是字符串常量，作用都是區分命名空間，以免不同類型的數據之間相互衝突，定義如下：

var(  	tablePrefix     = []byte{'t'}  	recordPrefixSep = []byte("_r")  	indexPrefixSep  = []byte("_i")  )

另外請大家注意，上述方案中，無論是 Row 還是 Index 的 Key 編碼方案，一個 Table 內部所有的 Row 都有相同的前綴，一個 Index 的數據也都有相同的前綴。這樣具體相同的前綴的數據，在 TiKV 的 Key 空間內，是排列在一起。同時只要我們小心地設計後綴部分的編碼方案，保證編碼前和編碼後的比較關係不變，那麼就可以將 Row 或者 Index 數據有序地保存在 TiKV 中。這種保證編碼前和編碼後的比較關係不變 的方案我們稱為 Memcomparable，對於任何類型的值，兩個對象編碼前的原始類型比較結果，和編碼成 byte 數組後（注意，TiKV 中的 Key 和 Value 都是原始的 byte 數組）的比較結果保持一致。具體的編碼方案參見 TiDB 的 codec 包。採用這種編碼後，一個表的所有 Row 數據就會按照 RowID 的順序排列在 TiKV 的 Key 空間中，某一個 Index 的數據也會按照 Index 的 ColumnValue 順序排列在 Key 空間內。

現在我們結合開始提到的需求以及 TiDB 的映射方案來看一下，這個方案是否能滿足需求。首先我們通過這個映射方案，將 Row 和 Index 數據都轉換為 Key-Value 數據，且每一行、每一條索引數據都是有唯一的 Key。其次，這種映射方案對於點查、範圍查詢都很友好，我們可以很容易地構造出某行、某條索引所對應的 Key，或者是某一塊相鄰的行、相鄰的索引值所對應的 Key 範圍。最後，在保證表中的一些 Constraint 的時候，可以通過構造並檢查某個 Key 是否存在來判斷是否能夠滿足相應的 Constraint。

至此我們已經聊完了如何將 Table 映射到 KV 上面，這裡再舉個簡單的例子，便於大家理解，還是以上面的表結構為例。假設表中有 3 行數據：

1, "TiDB", "SQL Layer", 10  2, "TiKV", "KV Engine", 20  3, "PD", "Manager", 30

那麼首先每行數據都會映射為一個 Key-Value pair，注意這個表有一個 Int 類型的 Primary Key，所以 RowID 的值即為這個 Primary Key 的值。假設這個表的 Table ID 為 10，其 Row 的數據為：

t10_r1 --> ["TiDB", "SQL Layer", 10]  t10_r2 --> ["TiKV", "KV Engine", 20]  t10_r3 --> ["PD", "Manager", 30]

除了 Primary Key 之外，這個表還有一個 Index，假設這個 Index 的 ID 為 1，則其數據為：

t10_i1_10_1 --> null  t10_i1_20_2 --> null  t10_i1_30_3 --> null

大家可以結合上面的編碼規則來理解這個例子，希望大家能理解我們為什麼選擇了這個映射方案，這樣做的目的是什麼。

元信息管理

上節介紹了表中的數據和索引是如何映射為 KV，本節介紹一下元信息的存儲。Database/Table 都有元信息，也就是其定義以及各項屬性，這些信息也需要持久化，我們也將這些信息存儲在 TiKV 中。每個 Database/Table 都被分配了一個唯一的 ID，這個 ID 作為唯一標識，並且在編碼為 Key-Value 時，這個 ID 都會編碼到 Key 中，再加上 m_ 前綴。這樣可以構造出一個 Key，Value 中存儲的是序列化後的元信息。除此之外，還有一個專門的 Key-Value 存儲當前 Schema 信息的版本。TiDB 使用 Google F1 的 Online Schema 變更算法，有一個後台線程在不斷的檢查 TiKV 上面存儲的 Schema 版本是否發生變化，並且保證在一定時間內一定能夠獲取版本的變化（如果確實發生了變化）。

SQL on KV 架構

TiDB 的整體架構如下圖所示

TiKV Cluster 主要作用是作為 KV 引擎存儲數據，上篇文章已經介紹過了細節，這裡不再敷述。本篇文章主要介紹 SQL 層，也就是 TiDB Servers 這一層，這一層的節點都是無狀態的節點，本身並不存儲數據，節點之間完全對等。TiDB Server 這一層最重要的工作是處理用戶請求，執行 SQL 運算邏輯，接下來我們做一些簡單的介紹。

SQL 運算

理解了 SQL 到 KV 的映射方案之後，我們可以理解關係數據是如何保存的，接下來我們要理解如何使用這些數據來滿足用戶的查詢需求，也就是一個查詢語句是如何操作底層存儲的數據。能想到的最簡單的方案就是通過上一節所述的映射方案，將 SQL 查詢映射為對 KV 的查詢，再通過 KV 接口獲取對應的數據，最後執行各種計算。比如 Select count(*) from user where name="TiDB"; 這樣一個語句，我們需要讀取表中所有的數據，然後檢查 Name 字段是否是 TiDB，如果是的話，則返回這一行。這樣一個操作流程轉換為 KV 操作流程：

  • 構造出 Key Range：一個表中所有的 RowID 都在 [0, MaxInt64) 這個範圍內，那麼我們用 0 和 MaxInt64 根據 Row 的 Key 編碼規則，就能構造出一個 [StartKey, EndKey) 的左閉右開區間
  • 掃描 Key Range：根據上面構造出的 Key Range，讀取 TiKV 中的數據
  • 過濾數據：對於讀到的每一行數據，計算 name="TiDB" 這個表達式，如果為真，則向上返回這一行，否則丟棄這一行數據
  • 計算 Count：對符合要求的每一行，累計到 Count 值上面 這個方案肯定是可以 Work 的，但是並不能 Work 的很好，原因是顯而易見的：
    • 在掃描數據的時候，每一行都要通過 KV 操作同 TiKV 中讀取出來，至少有一次 RPC 開銷，如果需要掃描的數據很多，那麼這個開銷會非常大
    • 並不是所有的行都有用，如果不滿足條件，其實可以不讀取出來
    • 符合要求的行的值並沒有什麼意義，實際上這裡只需要有幾行數據這個信息就行

分佈式 SQL 運算

如何避免上述缺陷也是顯而易見的，首先我們需要將計算盡量靠近存儲節點，以避免大量的 RPC 調用。其次，我們需要將 Filter 也下推到存儲節點進行計算，這樣只需要返回有效的行，避免無意義的網絡傳輸。最後，我們可以將聚合函數、GroupBy 也下推到存儲節點，進行預聚合，每個節點只需要返回一個 Count 值即可，再由 tidb-server 將 Count 值 Sum 起來。這裡有一個數據逐層返回的示意圖：

SQL 層架構

上面幾節簡要介紹了 SQL 層的一些功能，希望大家對 SQL 語句的處理有一個基本的了解。實際上 TiDB 的 SQL 層要複雜的多，模塊以及層次非常多，下面這個圖列出了重要的模塊以及調用關係：

用戶的 SQL 請求會直接或者通過 Load Balancer 發送到 tidb-server，tidb-server 會解析 MySQL Protocol Packet，獲取請求內容，然後做語法解析、查詢計劃制定和優化、執行查詢計劃獲取和處理數據。數據全部存儲在 TiKV 集群中，所以在這個過程中 tidb-server 需要和 tikv-server 交互，獲取數據。最後 tidb-server 需要將查詢結果返回給用戶。

小結

到這裡，我們已經從 SQL 的角度了解了數據是如何存儲，如何用於計算。SQL 層更詳細的介紹會在今後的文章中給出，比如優化器的工作原理，分佈式執行框架的細節。下一篇文章我們將會介紹一些關於 PD 的信息，這部分會比較有意思，裏面的很多東西是在使用 TiDB 過程中看不到，但是對整體集群又非常重要。主要會涉及到集群的管理和調度。

TiDB 技術內幕 – 調度篇

為什麼要進行調度

先回憶一下TiDB 技術內幕 – 存儲篇提到的一些信息，TiKV 集群是 TiDB 數據庫的分佈式 KV 存儲引擎，數據以 Region 為單位進行複製和管理，每個 Region 會有多個 Replica（副本），這些 Replica 會分佈在不同的 TiKV 節點上，其中 Leader 負責讀/寫，Follower 負責同步 Leader 發來的 raft log。了解了這些信息後，請思考下面這些問題：

  • 如何保證同一個 Region 的多個 Replica 分佈在不同的節點上？更進一步，如果在一台機器上啟動多個 TiKV 實例，會有什麼問題？
  • TiKV 集群進行跨機房部署用於容災的時候，如何保證一個機房掉線，不會丟失 Raft Group 的多個 Replica？
  • 添加一個節點進入 TiKV 集群之後，如何將集群中其他節點上的數據搬過來?
  • 當一個節點掉線時，會出現什麼問題？整個集群需要做什麼事情？如果節點只是短暫掉線（重啟服務），那麼如何處理？如果節點是長時間掉線（磁盤故障，數據全部丟失），需要如何處理？
  • 假設集群需要每個 Raft Group 有 N 個副本，那麼對於單個 Raft Group 來說，Replica 數量可能會不夠多（例如節點掉線，失去副本），也可能會過於多（例如掉線的節點又回復正常，自動加入集群）。那麼如何調節 Replica 個數？
  • 讀/寫都是通過 Leader 進行，如果 Leader 只集中在少量節點上，會對集群有什麼影響？
  • 並不是所有的 Region 都被頻繁的訪問，可能訪問熱點只在少數幾個 Region，這個時候我們需要做什麼？
  • 集群在做負載均衡的時候，往往需要搬遷數據，這種數據的遷移會不會佔用大量的網絡帶寬、磁盤 IO 以及 CPU？進而影響在線服務？

這些問題單獨拿出可能都能找到簡單的解決方案，但是混雜在一起，就不太好解決。有的問題貌似只需要考慮單個 Raft Group 內部的情況，比如根據副本數量是否足夠多來決定是否需要添加副本。但是實際上這個副本添加在哪裡，是需要考慮全局的信息。整個系統也是在動態變化，Region 分裂、節點加入、節點失效、訪問熱點變化等情況會不斷發生，整個調度系統也需要在動態中不斷向最優狀態前進，如果沒有一個掌握全局信息，可以對全局進行調度，並且可以配置的組件，就很難滿足這些需求。因此我們需要一個中心節點，來對系統的整體狀況進行把控和調整，所以有了 PD 這個模塊。

調度的需求

上面羅列了一大堆問題，我們先進行分類和整理。總體來看，問題有兩大類：

作為一個分佈式高可用存儲系統，必須滿足的需求，包括四種：

  • 副本數量不能多也不能少
  • 副本需要分佈在不同的機器上
  • 新加節點後，可以將其他節點上的副本遷移過來
  • 節點下線後，需要將該節點的數據遷移走

作為一個良好的分佈式系統，需要優化的地方，包括：

  • 維持整個集群的 Leader 分佈均勻
  • 維持每個節點的儲存容量均勻
  • 維持訪問熱點分佈均勻
  • 控制 Balance 的速度，避免影響在線服務
  • 管理節點狀態，包括手動上線/下線節點，以及自動下線失效節點

滿足第一類需求後，整個系統將具備多副本容錯、動態擴容/縮容、容忍節點掉線以及自動錯誤恢復的功能。滿足第二類需求後，可以使得整體系統的負載更加均勻、且可以方便的管理。

為了滿足這些需求，首先我們需要收集足夠的信息，比如每個節點的狀態、每個 Raft Group 的信息、業務訪問操作的統計等；其次需要設置一些策略，PD 根據這些信息以及調度的策略，制定出盡量滿足前面所述需求的調度計劃；最後需要一些基本的操作，來完成調度計劃。

調度的基本操作

我們先來介紹最簡單的一點，也就是調度的基本操作，也就是為了滿足調度的策略，我們有哪些功能可以用。這是整個調度的基礎，了解了手裡有什麼樣的鎚子，才知道用什麼樣的姿勢去砸釘子。

上述調度需求看似複雜，但是整理下來最終落地的無非是下面三件事：

  • 增加一個 Replica
  • 刪除一個 Replica
  • 將 Leader 角色在一個 Raft Group 的不同 Replica 之間 transfer

剛好 Raft 協議能夠滿足這三種需求，通過 AddReplica、RemoveReplica、TransferLeader 這三個命令，可以支撐上述三種基本操作。

信息收集

調度依賴於整個集群信息的收集，簡單來說，我們需要知道每個 TiKV 節點的狀態以及每個 Region 的狀態。TiKV 集群會向 PD 彙報兩類消息：

每個 TiKV 節點會定期向 PD 彙報節點的整體信息

TiKV 節點（Store）與 PD 之間存在心跳包，一方面 PD 通過心跳包檢測每個 Store 是否存活，以及是否有新加入的 Store；另一方面，心跳包中也會攜帶這個 Store 的狀態信息，主要包括：

  • 總磁盤容量
  • 可用磁盤容量
  • 承載的 Region 數量
  • 數據寫入速度
  • 發送/接受的 Snapshot 數量（Replica 之間可能會通過 Snapshot 同步數據）
  • 是否過載
  • 標籤信息（標籤是具備層級關係的一系列 Tag）

每個 Raft Group 的 Leader 會定期向 PD 彙報信息

每個 Raft Group 的 Leader 和 PD 之間存在心跳包，用於彙報這個 Region 的狀態，主要包括下面幾點信息：

  • Leader 的位置
  • Followers 的位置
  • 掉線 Replica 的個數
  • 數據寫入/讀取的速度

PD 不斷的通過這兩類心跳消息收集整個集群的信息，再以這些信息作為決策的依據。除此之外，PD 還可以通過管理接口接受額外的信息，用來做更準確的決策。比如當某個 Store 的心跳包中斷的時候，PD 並不能判斷這個節點是臨時失效還是永久失效，只能經過一段時間的等待（默認是 30 分鐘），如果一直沒有心跳包，就認為是 Store 已經下線，再決定需要將這個 Store 上面的 Region 都調度走。但是有的時候，是運維人員主動將某台機器下線，這個時候，可以通過 PD 的管理接口通知 PD 該 Store 不可用，PD 就可以馬上判斷需要將這個 Store 上面的 Region 都調度走。

調度的策略

PD 收集了這些信息後，還需要一些策略來制定具體的調度計劃。

一個 Region 的 Replica 數量正確

當 PD 通過某個 Region Leader 的心跳包發現這個 Region 的 Replica 數量不滿足要求時，需要通過 Add/Remove Replica 操作調整 Replica 數量。出現這種情況的可能原因是：

  • 某個節點掉線，上面的數據全部丟失，導致一些 Region 的 Replica 數量不足
  • 某個掉線節點又恢復服務，自動接入集群，這樣之前已經補足了 Replica 的 Region 的 Replica 數量多過，需要刪除某個 Replica
  • 管理員調整了副本策略，修改了 max-replicas 的配置

一個 Raft Group 中的多個 Replica 不在同一個位置

注意第二點，『一個 Raft Group 中的多個 Replica 不在同一個位置』，這裡用的是『同一個位置』而不是『同一個節點』。在一般情況下，PD 只會保證多個 Replica 不落在一個節點上，以避免單個節點失效導致多個 Replica 丟失。在實際部署中，還可能出現下面這些需求：

  • 多個節點部署在同一台物理機器上
  • TiKV 節點分佈在多個機架上，希望單個機架掉電時，也能保證系統可用性
  • TiKV 節點分佈在多個 IDC 中，希望單個機房掉電時，也能保證系統可用

這些需求本質上都是某一個節點具備共同的位置屬性，構成一個最小的容錯單元，我們希望這個單元內部不會存在一個 Region 的多個 Replica。這個時候，可以給節點配置 lables 並且通過在 PD 上配置 location-labels 來指明哪些 lable 是位置標識，需要在 Replica 分配的時候盡量保證不會有一個 Region 的多個 Replica 所在結點有相同的位置標識。

副本在 Store 之間的分佈均勻分配

前面說過，每個副本中存儲的數據容量上限是固定的，所以我們維持每個節點上面，副本數量的均衡，會使得總體的負載更均衡。

Leader 數量在 Store 之間均勻分配

Raft 協議要讀取和寫入都通過 Leader 進行，所以計算的負載主要在 Leader 上面，PD 會儘可能將 Leader 在節點間分散開。

訪問熱點數量在 Store 之間均勻分配

每個 Store 以及 Region Leader 在上報信息時攜帶了當前訪問負載的信息，比如 Key 的讀取/寫入速度。PD 會檢測出訪問熱點，且將其在節點之間分散開。

各個 Store 的存儲空間佔用大致相等

每個 Store 啟動的時候都會指定一個 Capacity 參數，表明這個 Store 的存儲空間上限，PD 在做調度的時候，會考慮節點的存儲空間剩餘量。

控制調度速度，避免影響在線服務

調度操作需要耗費 CPU、內存、磁盤 IO 以及網絡帶寬，我們需要避免對線上服務造成太大影響。PD 會對當前正在進行的操作數量進行控制，默認的速度控制是比較保守的，如果希望加快調度(比如已經停服務升級，增加新節點，希望儘快調度)，那麼可以通過 pd-ctl 手動加快調度速度。

支持手動下線節點

當通過 pd-ctl 手動下線節點後，PD 會在一定的速率控制下，將節點上的數據調度走。當調度完成後，就會將這個節點置為下線狀態。

調度的實現

了解了上面這些信息後，接下來我們看一下整個調度的流程。

PD 不斷的通過 Store 或者 Leader 的心跳包收集信息，獲得整個集群的詳細數據，並且根據這些信息以及調度策略生成調度操作序列，每次收到 Region Leader 發來的心跳包時，PD 都會檢查是否有對這個 Region 待進行的操作，通過心跳包的回復消息，將需要進行的操作返回給 Region Leader，並在後面的心跳包中監測執行結果。注意這裡的操作只是給 Region Leader 的建議，並不保證一定能得到執行，具體是否會執行以及什麼時候執行，由 Region Leader 自己根據當前自身狀態來定。

總結

本篇文章講的東西，大家可能平時很少會在其他文章中看到，每一個設計都有背後的考量，希望大家能了解到一個分佈式存儲系統在做調度的時候，需要考慮哪些東西，如何將策略、實現進行解耦，更靈活的支持策略的擴展。

至此希望大家能夠對整個 TiDB 的基本概念和實現原理有了解。

本篇文章來自與pingCAP的工程師在pingCAP社區的分享。

更多關於TiDB的使用可以參考：https://pingcap.com/docs-cn/stable/faq/tidb-lightning/

VirMach 便宜 VPS

QNews

QNews