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

作者：唐劉 siddontang

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Lock CF: W a = lock

Data CF: W a_10 = value

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

當(dāng) PreWrite 成功之后，就會(huì)進(jìn)入 Commit 階段，會(huì)從 TSO 拿一個(gè) commitTS，譬如 11，然后寫入：

Lock CF: D a

Write CF: W a_11 = 10

當(dāng) Commit 成功之后，對(duì)于一個(gè) key-value 來說，它就會(huì)在 Data CF 和 Write CF 里面都有記錄，在 Data CF 里面會(huì)記錄實(shí)際的數(shù)據(jù)， Write CF 里面則會(huì)記錄對(duì)應(yīng)的 startTS。

當(dāng)我們要讀取數(shù)據(jù)的時(shí)候，也會(huì)先從 TSO 拿到一個(gè) startTS，譬如 12，然后進(jìn)行讀：

Lock CF: R a

Write CF: S a_12 -> a_11 = 10

Data CF: R a_10

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

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

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

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

一個(gè) TiKV 會(huì)有多個(gè) Regions，我們?cè)?Raft RocksDB 里面會(huì)使用 Region 的 ID 作為 key 的前綴，然后再帶上 Raft Log ID 來唯一標(biāo)識(shí)一條 Raft Log。譬如，假設(shè)現(xiàn)在有兩個(gè) 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}

因?yàn)槲覀兪前凑?range 對(duì) key 進(jìn)行的切分，那么在 KV RocksDB 里面，我們直接使用 key 來進(jìn)行保存，類似如下：

a -> N

b -> N

里面存放了兩個(gè) key，a 和 b，但并沒有使用任何前綴進(jìn)行區(qū)分。

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

TiKV 會(huì)將自己所有的 Region 信息匯報(bào)給 PD，這樣 PD 就有了整個(gè)集群的 Region 信息，當(dāng)然就有了一張 Region 的路由表，如下：

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

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

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

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