摘要：作者唐劉本文會詳細的介紹是如何處理讀寫請求的，通過該文檔，同學們會知道是如何將一個寫請求包含的數據更改存儲到系統，并且能讀出對應的數據的。每個包含兩個實例，一個用于存儲，我們后面稱為，而另一個則是存放用戶實際的數據，我們稱為。

作者：唐劉 siddontang

本文會詳細的介紹 TiKV 是如何處理讀寫請求的，通過該文檔，同學們會知道 TiKV 是如何將一個寫請求包含的數據更改存儲到系統，并且能讀出對應的數據的。

本文分為上下兩篇，在上篇中，我們將介紹一些基礎知識，便于大家去理解后面的流程。

TiKV 使用 Raft 一致性算法來保證數據的安全，默認提供的是三個副本支持，這三個副本形成了一個 Raft Group。

當 Client 需要寫入某個數據的時候，Client 會將操作發送給 Raft Leader，這個在 TiKV 里面我們叫做 Propose，Leader 會將操作編碼成一個 entry，寫入到自己的 Raft Log 里面，這個我們叫做 Append。

Leader 也會通過 Raft 算法將 entry 復制到其他的 Follower 上面，這個我們叫做 Replicate。Follower 收到這個 entry 之后也會同樣進行 Append 操作，順帶告訴 Leader Append 成功。

當 Leader 發現這個 entry 已經被大多數節點 Append，就認為這個 entry 已經是 Committed 的了，然后就可以將 entry 里面的操作解碼出來，執行并且應用到狀態機里面，這個我們叫做 Apply。

在 TiKV 里面，我們提供了 Lease Read，對于 Read 請求，會直接發給 Leader，如果 Leader 確定自己的 lease 沒有過期，那么就會直接提供 Read 服務，這樣就不用走一次 Raft 了。如果 Leader 發現 lease 過期了，就會強制走一次 Raft 進行續租，然后在提供 Read 服務。

因為一個 Raft Group 處理的數據量有限，所以我們會將數據切分成多個 Raft Group，我們叫做 Region。切分的方式是按照 range 進行切分，也就是我們會將數據的 key 按照字節序進行排序，也就是一個無限的 sorted map，然后將其切分成一段一段（連續）的 key range，每個 key range 當成一個 Region。

兩個相鄰的 Region 之間不允許出現空洞，也就是前面一個 Region 的 end key 就是后一個 Region 的 start key。Region 的 range 使用的是前閉后開的模式 ?[start, end)，對于 key start 來說，它就屬于這個 Region，但對于 end 來說，它其實屬于下一個 Region。

TiKV 的 Region 會有最大 size 的限制，當超過這個閾值之后，就會分裂成兩個 Region，譬如 [a, b) -> [a, ab) + [ab, b)，當然，如果 Region 里面沒有數據，或者只有很少的數據，也會跟相鄰的 Region 進行合并，變成一個更大的 Region，譬如 [a, ab) + [ab, b) -> [a, b)

對于同一個 Region 來說，通過 Raft 一致性協議，我們能保證里面的 key 操作的一致性，但如果我們要同時操作多個數據，而這些數據落在不同的 Region 上面，為了保證操作的一致性，我們就需要分布式事務。

譬如我們需要同時將 a = 1，b = 2 修改成功，而 a 和 b 屬于不同的 Region，那么當操作結束之后，一定只能出現 a 和 b 要么都修改成功，要么都沒有修改成功，不能出現 a 修改了，但 b 沒有修改，或者 b 修改了，a 沒有修改這樣的情況。

最通常的分布式事務的做法就是使用 two-phase commit，也就是俗稱的 2PC，但傳統的 2PC 需要有一個協調者，而我們也需要有機制來保證協調者的高可用。這里，TiKV 參考了 Google 的 Percolator，對 2PC 進行了優化，來提供分布式事務支持。

Percolator 的原理是比較復雜的，需要關注幾點：

首先，Percolator 需要一個服務 timestamp oracle (TSO) 來分配全局的 timestamp，這個 timestamp 是按照時間單調遞增的，而且全局唯一。任何事務在開始的時候會先拿一個 start timestamp (startTS)，然后在事務提交的時候會拿一個 commit timestamp (commitTS)。

Percolator 提供三個 column family (CF)，Lock，Data 和 Write，當寫入一個 key-value 的時候，會將這個 key 的 lock 放到 Lock CF 里面，會將實際的 value 放到 Data CF 里面，如果這次寫入 commit 成功，則會將對應的 commit 信息放到入 Write CF 里面。

Key 在 Data CF 和 Write CF 里面存放的時候，會把對應的時間戳給加到 Key 的后面。在 Data CF 里面，添加的是 startTS，而在 Write CF 里面，則是 commitCF。

假設我們需要寫入 a = 1，首先從 TSO 上面拿到一個 startTS，譬如 10，然后我們進入 Percolator 的 PreWrite 階段，在 Lock 和 Data CF 上面寫入數據，如下：

Lock CF: W a = lock

Data CF: W a_10 = value

后面我們會用 W 表示 Write，R 表示 Read， D 表示 Delete，S 表示 Seek。

當 PreWrite 成功之后，就會進入 Commit 階段，會從 TSO 拿一個 commitTS，譬如 11，然后寫入：

Lock CF: D a

Write CF: W a_11 = 10

當 Commit 成功之后，對于一個 key-value 來說，它就會在 Data CF 和 Write CF 里面都有記錄，在 Data CF 里面會記錄實際的數據， Write CF 里面則會記錄對應的 startTS。

當我們要讀取數據的時候，也會先從 TSO 拿到一個 startTS，譬如 12，然后進行讀：

Lock CF: R a

Write CF: S a_12 -> a_11 = 10

Data CF: R a_10

在 Read 流程里面，首先我們看 Lock CF 里面是否有 lock，如果有，那么讀取就失敗了。如果沒有，我們就會在 Write CF 里面 seek 最新的一個提交版本，這里我們會找到 11，然后拿到對應的 startTS，這里就是 10，然后將 key 和 startTS 組合在 Data CF 里面讀取對應的數據。

上面只是簡單的介紹了下 Percolator 的讀寫流程，實際會比這個復雜的多。

TiKV 會將數據存儲到 RocksDB，RocksDB 是一個 key-value 存儲系統，所以對于 TiKV 來說，任何的數據都最終會轉換成一個或者多個 key-value 存放到 RocksDB 里面。

每個 TiKV 包含兩個 RocksDB 實例，一個用于存儲 Raft Log，我們后面稱為 Raft RocksDB，而另一個則是存放用戶實際的數據，我們稱為 KV RocksDB。

一個 TiKV 會有多個 Regions，我們在 Raft RocksDB 里面會使用 Region 的 ID 作為 key 的前綴，然后再帶上 Raft Log ID 來唯一標識一條 Raft Log。譬如，假設現在有兩個 Region，ID 分別為 1，2，那么 Raft Log 在 RocksDB 里面類似如下存放：

1_1 -> Log {a = 1}

1_2 -> Log {a = 2}

…

1_N -> Log {a = N}

2_1 -> Log {b = 2}

2_2 -> Log {b = 3}

…

2_N -> Log {b = N}

因為我們是按照 range 對 key 進行的切分，那么在 KV RocksDB 里面，我們直接使用 key 來進行保存，類似如下：

a -> N

b -> N

里面存放了兩個 key，a 和 b，但并沒有使用任何前綴進行區分。

RocksDB 支持 Column Family，所以能直接跟 Percolator 里面的 CF 對應，在 TiKV 里面，我們在 RocksDB 使用 Default CF 直接對應 Percolator 的 Data CF，另外使用了相同名字的 Lock 和 Write。

TiKV 會將自己所有的 Region 信息匯報給 PD，這樣 PD 就有了整個集群的 Region 信息，當然就有了一張 Region 的路由表，如下：

當 Client 需要操作某一個 key 的數據的時候，它首先會向 PD 問一下這個 key 屬于哪一個 Region，譬如對于 key a 來說，PD 知道它屬于 Region 1，就會給 Client 返回 Region 1 的相關信息，包括有多少個副本，現在 Leader 是哪一個副本，這個 Leader 副本在哪一個 TiKV 上面。

Client 會將相關的 Region 信息緩存到本地，加速后續的操作，但有可能 Region 的 Raft Leader 變更，或者 Region 出現了分裂，合并，Client 會知道緩存失效，然后重新去 PD 獲取最新的信息。

PD 同時也提供全局的授時服務，在 Percolator 事務模型里面，我們知道事務開始以及提交都需要有一個時間戳，這個就是 PD 統一分配的。

基礎知識就介紹到這里，下篇我們將詳細的介紹 TiKV 的讀寫流程～ 敬請期待！