介紹

Raft是當(dāng)前廣泛使用的共識(shí)算法。流行的系統(tǒng)，如Kafka、Cockroach DB、MongoDB、Neo4j、Splunk等，都使用Raft來(lái)實(shí)現(xiàn)共識(shí)。系統(tǒng)要么是最終一致性的，要么是強(qiáng)一致性的。線性一致性是一致性模型中最強(qiáng)大的，但實(shí)現(xiàn)它可能很耗時(shí)。鍵值數(shù)據(jù)庫(kù)出現(xiàn)在市場(chǎng)上，以避免SQL數(shù)據(jù)庫(kù)的復(fù)雜性并提供橫向擴(kuò)展性。這些數(shù)據(jù)庫(kù)主要提供兩種操作：get(key)和put(key, value)。

在我對(duì)Raft相關(guān)論文的探索中，我找到了一篇有趣的文章，標(biāo)題為‘Rethink the Linearizability Constraints of Raft for Distributed Key-Value Stores’。本文詳細(xì)介紹了在類似鍵值數(shù)據(jù)庫(kù)中減少讀寫(xiě)線性操作延遲以提高吞吐量的技術(shù)。本文提供了對(duì)這篇論文的簡(jiǎn)要概述。

Raft如何處理寫(xiě)請(qǐng)求？

Raft處理寫(xiě)請(qǐng)求涉及三個(gè)關(guān)鍵操作：追加（Append）、提交（Commit）和應(yīng)用（Apply），因此引入了一系列用于讀寫(xiě)請(qǐng)求處理的索引，以確保線性一致性。這些索引包括日志索引、提交索引和應(yīng)用索引。

圖片來(lái)源：Paper 9458806

1.追加

當(dāng)客戶端向領(lǐng)導(dǎo)者發(fā)送寫(xiě)請(qǐng)求時(shí)，請(qǐng)求中的日志將被分配一個(gè)唯一遞增的索引號(hào)。領(lǐng)導(dǎo)者將日志附加到本地日志存儲(chǔ)，并向跟隨者發(fā)送用于復(fù)制的附加條目請(qǐng)求。領(lǐng)導(dǎo)者收到來(lái)自大多數(shù)跟隨者的附加條目請(qǐng)求的響應(yīng)后，將日志設(shè)置為已提交，即新寫(xiě)入的數(shù)據(jù)在系統(tǒng)中是安全的。

2.提交

當(dāng)領(lǐng)導(dǎo)者收到附加條目請(qǐng)求的大多數(shù)跟隨者的響應(yīng)時(shí)，日志被設(shè)置為已提交，即新寫(xiě)入的數(shù)據(jù)在系統(tǒng)中是安全的。

3.應(yīng)用

領(lǐng)導(dǎo)者開(kāi)始將已提交的日志應(yīng)用到其本地狀態(tài)機(jī)，并并行通知跟隨者執(zhí)行相同的操作。每個(gè)節(jié)點(diǎn)在應(yīng)用操作成功后將更新其應(yīng)用索引。只有在領(lǐng)導(dǎo)者將日志應(yīng)用到狀態(tài)機(jī)之后，領(lǐng)導(dǎo)者才能向客戶端返回響應(yīng)。

寫(xiě)請(qǐng)求序列

Raft如何處理讀請(qǐng)求？

為了實(shí)現(xiàn)線性一致性，所有讀請(qǐng)求都由領(lǐng)導(dǎo)者自身處理。Raft還為此引入了讀索引。當(dāng)領(lǐng)導(dǎo)者收到讀請(qǐng)求時(shí)，請(qǐng)求的讀索引設(shè)置為當(dāng)前提交索引。只有當(dāng)領(lǐng)導(dǎo)者的應(yīng)用索引不小于讀索引時(shí)，領(lǐng)導(dǎo)者才能執(zhí)行讀請(qǐng)求并將結(jié)果返回給客戶端。在這種情況下，我們可以確保客戶端不會(huì)獲取到陳舊的數(shù)據(jù)。

對(duì)這些操作的評(píng)估

文章討論了所有這些操作的時(shí)間消耗評(píng)估，如復(fù)制、提交和應(yīng)用。根據(jù)評(píng)估，應(yīng)用操作是最耗時(shí)的。對(duì)于帶有高速網(wǎng)絡(luò)的系統(tǒng)，網(wǎng)絡(luò)開(kāi)銷較低。日志的結(jié)構(gòu)簡(jiǎn)單，日志附加通常是一個(gè)具有較高速度的順序I/O操作。因此，更新復(fù)雜的狀態(tài)機(jī)最可能成為性能瓶頸。

下圖顯示了值大小從1KB到1MB時(shí)，應(yīng)用操作和所有其他操作的時(shí)間消耗百分比。它顯示應(yīng)用實(shí)際上是慢的，占寫(xiě)請(qǐng)求總時(shí)間的近40%。

如何改進(jìn)這個(gè)？

與其他類型的數(shù)據(jù)庫(kù)相比，鍵值存儲(chǔ)是一個(gè)簡(jiǎn)單的數(shù)據(jù)庫(kù)。寫(xiě)操作只是將鍵和值插入或更新到數(shù)據(jù)庫(kù)，而讀操作只是為給定的鍵讀取相應(yīng)的值。文章證明，去除請(qǐng)求處理中的應(yīng)用階段可能會(huì)減少延遲。應(yīng)用操作可以異步執(zhí)行。讀和寫(xiě)操作不需要等待應(yīng)用完成。為此，文章引入了兩種新方法：

• 提交返回（用于寫(xiě)操作）
• 立即讀（用于讀操作）

1.提交返回

這個(gè)想法是一旦請(qǐng)求中的日志被提交，直接向客戶端返回成功響應(yīng)，而不必等待將日志應(yīng)用到狀態(tài)機(jī)。因此，這個(gè)方法被稱為提交返回。提交返回不會(huì)破壞KV存儲(chǔ)的正確性和線性一致性。

提交返回

2.立即讀

在Raft中，讀操作在查詢狀態(tài)機(jī)之前等待應(yīng)用索引追上讀索引。當(dāng)實(shí)施提交返回時(shí)，應(yīng)用索引和讀索引之間的差距會(huì)比傳統(tǒng)Raft方法中的差距更大。因此，提交返回可以提升寫(xiě)處理但可能降低讀處理。然而，如果

我們能夠消除由于應(yīng)用索引和讀索引之間的差距而引起的等待時(shí)間，讀性能將得到顯著改善。

由于鍵值對(duì)的讀操作簡(jiǎn)單，我們可以直接根據(jù)位于讀索引和應(yīng)用索引之間的日志數(shù)據(jù)副本執(zhí)行讀請(qǐng)求，而不必查詢狀態(tài)機(jī)。如果日志中存在鍵的值，則立即返回，否則查詢狀態(tài)機(jī)并返回結(jié)果。通過(guò)這種方式，讀性能將大大提高。

例子：立即讀

采用這種方法，平均寫(xiě)入延遲將減少36.4% ～ 39.9%，平均讀取延遲將減少5.8% ～ 16.2%，與Raft相比。有關(guān)詳細(xì)信息，請(qǐng)參閱實(shí)際論文，文章中提供了論文鏈接。