TiKV 源碼解析系列 - Lease Read

01-28

本系列文章主要面向 TiKV 社區開發者，重點介紹 TiKV 的系統架構，源碼結構，流程解析。目的是使得開發者閱讀之後，能對 TiKV 項目有一個初步了解，更好的參與進入 TiKV 的開發中。本文是本系列文章的第五章節。作者：唐劉

Raft log read

TiKV 是一個要保證線性一致性的分散式 KV 系統，所謂線性一致性，一個簡單的例子就是在 t1 的時間我們寫入了一個值，那麼在 t1 之後，我們的讀一定能讀到這個值，不可能讀到 t1 之前的值。

因為 Raft 本來就是一個為了實現分散式環境下麵線性一致性的演算法，所以我們可以通過 Raft 非常方便的實現線性 read，也就是將任何的讀請求走一次 Raft log，等這個 log 提交之後，在 apply 的時候從狀態機裡面讀取值，我們就一定能夠保證這個讀取到的值是滿足線性要求的。

當然，大家知道，因為每次 read 都需要走 Raft 流程，所以性能是非常的低效的，所以大家通常都不會使用。

我們知道，在 Raft 裡面，節點有三個狀態，leader，candidate 和 follower，任何 Raft 的寫入操作都必須經過 leader，只有 leader 將對應的 raft log 複製到 majority 的節點上面，我們才會認為這一次寫入是成功的。所以我們可以認為，如果當前 leader 能確定一定是 leader，那麼我們就可以直接在這個 leader 上面讀取數據，因為對於 leader 來說，如果確認一個 log 已經提交到了大多數節點，在 t1 的時候 apply 寫入到狀態機，那麼在 t1 之後後面的 read 就一定能讀取到這個新寫入的數據。

那麼如何確認 leader 在處理這次 read 的時候一定是 leader 呢？在 Raft 論文裡面，提到了兩種方法。

ReadIndex Read

第一種就是 ReadIndex，當 leader 要處理一個讀請求的時候：

將當前自己的 commit index 記錄到一個 local 變數 ReadIndex 裡面。
向其他節點發起一次 heartbeat，如果大多數節點返回了對應的 heartbeat response，那麼 leader 就能夠確定現在自己仍然是 leader。
Leader 等待自己的狀態機執行，直到 apply index 超過了 ReadIndex，這樣就能夠安全的提供 linearizable read 了。
Leader 執行 read 請求，將結果返回給 client。

可以看到，不同於最開始的通過 Raft log 的 read，ReadIndex read 使用了 heartbeat 的方式來讓 leader 確認自己是 leader，省去了 Raft log 那一套流程。雖然仍然會有網路開銷，但 heartbeat 本來就很小，所以性能還是非常好的。

但這裡，需要注意，實現 ReadIndex 的時候有一個 corner case，在 etcd 和 TiKV 最初實現的時候，我們都沒有注意到。也就是 leader 剛通過選舉成為 leader 的時候，這時候的 commit index 並不能夠保證是當前整個系統最新的 commit index，所以 Raft 要求當 leader 選舉成功之後，首先提交一個 no-op 的 entry，保證 leader 的 commit index 成為最新的。

所以，如果在 no-op 的 entry 還沒提交成功之前，leader 是不能夠處理 ReadIndex 的。但之前 etcd 和 TiKV 的實現都沒有注意到這個情況，也就是有 bug。解決的方法也很簡單，因為 leader 在選舉成功之後，term 一定會增加，在處理 ReadIndex 的時候，如果當前最新的 commit log 的 term 還沒到新的 term，就會一直等待跟新的 term 一致，也就是 no-op entry 提交之後，才可以對外處理 ReadIndex。

使用 ReadIndex，我們也可以非常方便的提供 follower read 的功能，follower 收到 read 請求之後，直接給 leader 發送一個獲取 ReadIndex 的命令，leader 仍然走一遍之前的流程，然後將 ReadIndex 返回給 follower，follower 等到當前的狀態機的 apply index 超過 ReadIndex 之後，就可以 read 然後將結果返回給 client 了。

Lease Read

雖然 ReadIndex 比原來的 Raft log read 快了很多，但畢竟還是有 Heartbeat 的開銷，所以我們可以考慮做更進一步的優化。

在 Raft 論文裡面，提到了一種通過 clock + heartbeat 的 lease read 優化方法。也就是 leader 發送 heartbeat 的時候，會首先記錄一個時間點 start，當系統大部分節點都回復了 heartbeat response，那麼我們就可以認為 leader 的 lease 有效期可以到 start + election timeout / clock drift bound 這個時間點。

為什麼能夠這麼認為呢？主要是在於 Raft 的選舉機制，因為 follower 會在至少 election timeout 的時間之後，才會重新發生選舉，所以下一個 leader 選出來的時間一定可以保證大於 start + election timeout / clock drift bound。

雖然採用 lease 的做法很高效，但仍然會面臨風險問題，也就是我們有了一個預設的前提，各個伺服器的 CPU clock 的時間是準的，即使有誤差，也會在一個非常小的 bound 範圍裡面，如果各個伺服器之間 clock 走的頻率不一樣，有些太快，有些太慢，這套 lease 機制就可能出問題。

TiKV 使用了 lease read 機制，主要是我們覺得在大多數情況下面 CPU 時鐘都是正確的，當然這裡會有隱患，所以我們也仍然提供了 ReadIndex 的方案。

TiKV 的 lease read 實現在原理上面跟 Raft 論文上面的一樣，但實現細節上面有些差別，我們並沒有通過 heartbeat 來更新 lease，而是通過寫操作。對於任何的寫入操作，都會走一次 Raft log，所以我們在 propose 這次 write 請求的時候，記錄下當前的時間戳 start，然後等到對應的請求 apply 之後，我們就可以續約 leader 的 lease。當然實際實現還有很多細節需要考慮的，譬如：

我們使用的 monotonic raw clock，而不是 monotonic clock，因為 monotonic clock 雖然不會出現 time jump back 的情況，但它的速率仍然會受到 NTP 等的影響。
我們默認的 election timeout 是 10s，而我們會用 9s 的一個固定 max time 值來續約 lease，這樣一個是為了處理 clock drift bound 的問題，而另一個則是為了保證在滾動升級 TiKV 的時候，如果用戶調整了 election timeout，lease read 仍然是正確的。因為有了 max lease time，用戶的 election timeout 只能設置的比這個值大，也就是 election timeout 只能調大，這樣的好處在於滾動升級的時候即使出現了 leader 腦裂，我們也一定能夠保證下一個 leader 選舉出來的時候，老的 leader lease 已經過期了。

當然，使用 Raft log 來更新 lease 還有一個問題，就是如果用戶長時間沒有寫入操作，這時候來的讀取操作因為早就已經沒有 lease 了，所以只能強制走一次上面的 ReadIndex 機制來 read，但上面已經說了，這套機制性能也是有保證的。至於為什麼我們不在 heartbeat 那邊更新 lease，原因就是我們 TiKV 的 Raft 代碼想跟 etcd 保持一致，但 etcd 沒這個需求，所以我們就做到了外面。

小結

在 TiKV 裡面，從最開始的 Raft log read，到後面的 Lease Read，我們一步一步的在保證線性一致性的情況下面改進著性能。後面，我們會引入更多的一致性測試 case 來驗證整個系統的安全性，當然，也會持續的提升性能。

源碼地址：https://github.com/pingcap/tikv