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

作者：唐劉 siddontang

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

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

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

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

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

當 Leader 發(fā)現(xiàn)這個 entry 已經(jīng)被大多數(shù)節(jié)點 Append，就認為這個 entry 已經(jīng)是 Committed 的了，然后就可以將 entry 里面的操作解碼出來，執(zhí)行并且應(yīng)用到狀態(tài)機里面，這個我們叫做 Apply。

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

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

兩個相鄰的 Region 之間不允許出現(xiàn)空洞，也就是前面一個 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 里面沒有數(shù)據(jù)，或者只有很少的數(shù)據(jù)，也會跟相鄰的 Region 進行合并，變成一個更大的 Region，譬如 [a, ab) + [ab, b) -> [a, b)

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

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

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

Percolator 的原理是比較復(fù)雜的，需要關(guān)注幾點：

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

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

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

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

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 里面會記錄實際的數(shù)據(jù)， Write CF 里面則會記錄對應(yīng)的 startTS。

當我們要讀取數(shù)據(jù)的時候，也會先從 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，然后拿到對應(yīng)的 startTS，這里就是 10，然后將 key 和 startTS 組合在 Data CF 里面讀取對應(yīng)的數(shù)據(jù)。

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

TiKV 會將數(shù)據(jù)存儲到 RocksDB，RocksDB 是一個 key-value 存儲系統(tǒng)，所以對于 TiKV 來說，任何的數(shù)據(jù)都最終會轉(zhuǎn)換成一個或者多個 key-value 存放到 RocksDB 里面。

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

一個 TiKV 會有多個 Regions，我們在 Raft RocksDB 里面會使用 Region 的 ID 作為 key 的前綴，然后再帶上 Raft Log ID 來唯一標識一條 Raft Log。譬如，假設(shè)現(xiàn)在有兩個 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，但并沒有使用任何前綴進行區(qū)分。

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

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

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

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

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

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