raft理論與實(shí)踐[6]-lab3a-基于raft構(gòu)建分布式容錯(cuò)kv服務(wù)

準(zhǔn)備工作

閱讀raft論文
閱讀raft理論與實(shí)踐[1]-理論篇
閱讀raft理論與實(shí)踐[2]-lab2a
閱讀raft理論與實(shí)踐[3]-lab2a講解
閱讀raft理論與實(shí)踐[4]-lab2b日志復(fù)制
閱讀raft理論與實(shí)踐[5]-lab2c日志復(fù)制
閱讀模擬RPC遠(yuǎn)程過(guò)程調(diào)用

前言

在之前的文章中，我們實(shí)現(xiàn)了raft算法的基本框架
在本實(shí)驗(yàn)中随夸，我們將基于raft算法實(shí)現(xiàn)分布式容錯(cuò)的kv服務(wù)器
客戶端用于交互raft服務(wù)器
kvraft/client.go文件用于書寫我們的客戶端代碼瓶籽，調(diào)用Clerk的Get/Put/Append方法為系統(tǒng)提供強(qiáng)一致性的保證
這里的強(qiáng)一致性指的是愕贡，如果我們一個(gè)一個(gè)的調(diào)用（而不是并發(fā)）Clerk的Get/Put/Append方法，那么我們的系統(tǒng)就好像是只有一個(gè)raft服務(wù)器存在一樣永罚，并且調(diào)用是序列的勘纯，即后面的調(diào)用比前面的調(diào)用后執(zhí)行
對(duì)于并發(fā)調(diào)用吧兔，最終狀態(tài)可能難以預(yù)料论咏，但是必須與這些方法按某種順序序列化后執(zhí)行一次的結(jié)果相同
如果調(diào)用在時(shí)間上重疊优炬，則這些調(diào)用是并發(fā)的。例如厅贪，如果客戶端X調(diào)用Clerk.Put(),同時(shí)客戶端Y調(diào)用Clerk.Append()
同時(shí)蠢护，后面的方法在執(zhí)行之前，必須保證已經(jīng)觀察到前面所有方法執(zhí)行后的狀態(tài)（技術(shù)上叫做線性化（linearizability））
強(qiáng)一致性保證對(duì)應(yīng)用程序很方便养涮，因?yàn)檫@意味著所有客戶端都看到相同的最新?tīng)顟B(tài)
對(duì)于單個(gè)服務(wù)器葵硕，強(qiáng)一致性相對(duì)簡(jiǎn)單。多臺(tái)的副本服務(wù)器卻相對(duì)困難单寂，因?yàn)樗蟹?wù)器必須為并發(fā)請(qǐng)求選擇相同的執(zhí)行順序，并且必須避免使用最新?tīng)顟B(tài)來(lái)回復(fù)客戶端

本服務(wù)實(shí)現(xiàn)的功能

本服務(wù)支持3種基本的操作吐辙，Put(key, value), Append(key, arg), and Get(key)
維護(hù)著一個(gè)簡(jiǎn)單的鍵/值對(duì)數(shù)據(jù)庫(kù)
Put(key, value)將數(shù)據(jù)庫(kù)中特定key的值綁定為value
Append(key, arg)添加宣决，將arg與key對(duì)應(yīng)。如果key的值不存在昏苏，則其行為類似于Put
Get(key) 獲取當(dāng)前key的值
在本實(shí)驗(yàn)中尊沸，我們將實(shí)現(xiàn)服務(wù)具體的功能，而不必?fù)?dān)心Raft log日志會(huì)無(wú)限增長(zhǎng)

實(shí)驗(yàn)思路

對(duì)lab2中的raft服務(wù)器架構(gòu)進(jìn)行封裝贤惯，封裝上一些數(shù)據(jù)庫(kù)洼专、數(shù)據(jù)庫(kù)快照、并會(huì)處理log的具體執(zhí)行邏輯孵构。
對(duì)于數(shù)據(jù)庫(kù)執(zhí)行的Get/Put/Append方法都對(duì)其進(jìn)行序列化并放入到lab2 raft的體系中屁商，這樣就能保證這些方法的一致性

獲取源代碼

假設(shè)讀者已經(jīng)閱讀了準(zhǔn)備工作中的一系列文章
在此基礎(chǔ)上我們?cè)黾恿吮緦?shí)驗(yàn)的基本框架kvraft文件以及l(fā)inearizability文件
讀者需要在kvraft文件夾中，實(shí)驗(yàn)本實(shí)驗(yàn)的具體功能
獲取實(shí)驗(yàn)代碼如下

客戶端

Clerk結(jié)構(gòu)體存儲(chǔ)了所有raft服務(wù)器的客戶端servers []*labrpc.ClientEnd颈墅，因此我們可以通過(guò)Clerk結(jié)構(gòu)體與所有raft服務(wù)器通信
我們需要為Clerk結(jié)構(gòu)體實(shí)現(xiàn)Put(key, value), Append(key, arg), Get(key)方法
Clerk結(jié)構(gòu)體是我們連接raft服務(wù)器的橋梁
注意Clerk必須將方法發(fā)送到當(dāng)前的leader節(jié)點(diǎn)中蜡镶，由于其可能并不會(huì)知道哪一個(gè)節(jié)點(diǎn)為leader雾袱，因此需要重試。但是記住保存上一個(gè)leader的id會(huì)加快這一過(guò)程官还，因?yàn)閘eader在穩(wěn)定的系統(tǒng)里面是不會(huì)變的芹橡。
客戶端必須要等到此操作不僅為commit，而且已經(jīng)被完全應(yīng)用后望伦，才能夠返回林说，這才能夠保證下次get操作能夠得到最新的
需要注意的是，如果raft服務(wù)器出現(xiàn)了分區(qū)屯伞，可能會(huì)陷入一直等待腿箩，直到分區(qū)消失

補(bǔ)充Clerk

leader記錄最后一個(gè)leader的序號(hào)
seq 記錄rpc的序號(hào)
id記錄客戶端的唯一id

補(bǔ)充Get方法

Get方法會(huì)遍歷訪問(wèn)每一個(gè)raft服務(wù)，直到找到leader
調(diào)用時(shí)會(huì)陷入堵塞愕掏，等待rpc方法返回
設(shè)置有超時(shí)時(shí)間度秘，一旦超時(shí)，會(huì)重新發(fā)送
為了保證Get方法到的數(shù)據(jù)是準(zhǔn)確最新的饵撑，也必須要將其加入到raft算法中
客戶端必須要等到此操作不僅為commit剑梳，而且已經(jīng)被完全應(yīng)用后，才能夠返回滑潘，這才能夠保證下次get操作能夠得到最新的垢乙。

    ck.leader %= cnt
    done := make(chan bool, 1)
    go func() {
        ok := ck.servers[ck.leader].Call("KVServer.Get", args, reply)
        done <- ok
    }()
    select {
    case <-time.After(200 * time.Millisecond): // rpc timeout: 200ms
        ck.leader++
        continue
    case ok := <-done:
        if ok && !reply.WrongLeader {
            ck.seq++
            if reply.Err == OK {
                return reply.Value
            }
            return ""
        }
        ck.leader++
    }
}

return ""

}</pre>

補(bǔ)充Append和Put方法

調(diào)用同一個(gè)PutAppend方法，但是最后一個(gè)參數(shù)用于標(biāo)識(shí)具體的操作

和Get方法相似语卤，遍歷訪問(wèn)每一個(gè)raft服務(wù)追逮，直到找到leader
調(diào)用時(shí)會(huì)陷入堵塞，等待rpc方法返回
設(shè)置有超時(shí)時(shí)間粹舵，一旦超時(shí)钮孵，會(huì)重新發(fā)送
客戶端必須要等到此操作不僅為commit，而且已經(jīng)被完全應(yīng)用后眼滤，才能夠返回巴席，這才能夠保證下次get操作能夠得到最新的。

    ck.leader %= cnt
    done := make(chan bool, 1)
    go func() {
        ok := ck.servers[ck.leader].Call("KVServer.PutAppend", args, reply)
        done <- ok
    }()
    select {
    case <-time.After(200 * time.Millisecond): // rpc timeout: 200ms
        ck.leader++
        continue
    case ok := <-done:
        if ok && !reply.WrongLeader && reply.Err == OK {
            ck.seq++
            return
        }
        ck.leader++
    }
}

}</pre>

Server

kvraft/server.go文件用于書寫我們的客戶端代碼
KVServer結(jié)構(gòu)是對(duì)于之前書寫的raft架構(gòu)的封裝
applyCh chan raft.ApplyMsg 用于狀態(tài)虛擬機(jī)應(yīng)用coommit log诅需，執(zhí)行操作
db map[string]string 是模擬的一個(gè)數(shù)據(jù)庫(kù)
notifyChs map[int]chan struct{} commandID => notify chan 狀態(tài)虛擬機(jī)應(yīng)用此command后漾唉，會(huì)通知此通道
duplicate map[int64]*LatestReply 檢測(cè)重復(fù)請(qǐng)求

完成PutAppend、Get方法

下面以PutAppend為例堰塌，Get方法類似
檢測(cè)當(dāng)前是否leader狀態(tài)
檢測(cè)是否重復(fù)請(qǐng)求
將此command通過(guò)rf.Start(cmd) 放入raft中
select等待直到ch被激活赵刑，即command index被此kv服務(wù)器應(yīng)用
ch被激活后,需要再次檢測(cè)當(dāng)前節(jié)點(diǎn)是否為leader
- 如果不是,說(shuō)明leader更換,立即返回錯(cuò)誤，這時(shí)由于如果不再是leader场刑，那么雖然此kv服務(wù)器應(yīng)用了此command index般此，但不一定是相同的command
- 這個(gè)時(shí)候會(huì)堵塞直到序號(hào)為commandIndex的命令被應(yīng)用，但是，如果leader更換恤煞，此commandIndex的命令不一定就是我們的當(dāng)前的命令
- 但是完全有可能新的leader已經(jīng)應(yīng)用了此狀態(tài)屎勘，我們這時(shí)候雖然仍然返回錯(cuò)誤，希望客戶端重試居扒，這是由于操作是冪等的并且重復(fù)操作無(wú)影響概漱。
- 優(yōu)化方案是為command指定一個(gè)唯一的標(biāo)識(shí)，這樣就能夠明確此特定操作是否被應(yīng)用

DPrintf("[%d]: leader %d receive rpc: PutAppend(%q => (%q,%q), (%d-%d).\n", kv.me, kv.me,
    args.Op, args.Key, args.Value, args.ClientID, args.SeqNo)

kv.mu.Lock()
// duplicate put/append request
if dup, ok := kv.duplicate[args.ClientID]; ok {
    // filter duplicate
    if args.SeqNo <= dup.Seq {
        kv.mu.Unlock()
        reply.WrongLeader = false
        reply.Err = OK
        return
    }
}

// new request
cmd := Op{Key: args.Key, Value: args.Value, Op: args.Op, ClientID: args.ClientID, SeqNo: args.SeqNo}
index, term, _ := kv.rf.Start(cmd)
ch := make(chan struct{})
kv.notifyChs[index] = ch
kv.mu.Unlock()

reply.WrongLeader = false
reply.Err = OK

// wait for Raft to complete agreement
select {
case <-ch:
    // lose leadership
    curTerm, isLeader := kv.rf.GetState()
    if !isLeader || term != curTerm {
        reply.WrongLeader = true
        reply.Err = ""
        return
    }
case <-kv.shutdownCh:
    return
}

}</pre>

完成對(duì)于log的應(yīng)用操作

<-kv.applyCh 是當(dāng)log成為commit狀態(tài)時(shí)喜喂，狀態(tài)機(jī)對(duì)于log的應(yīng)用操作
本系列構(gòu)建的為kv-raft服務(wù)瓤摧，根據(jù)不同的服務(wù)其應(yīng)用操作的方式不同
下面的操作是簡(jiǎn)單的操作內(nèi)存map數(shù)據(jù)庫(kù)
同時(shí)，將最后一個(gè)操作記錄下來(lái)玉吁，避免同一個(gè)log應(yīng)用了兩次照弥。

<pre style="font-family: Consolas, "Liberation Mono", Menlo, Courier, monospace; -webkit-font-smoothing: antialiased; margin: 0px; padding: 0.88889em; max-width: 100%; font-size: 0.9em; word-break: break-all; white-space: pre-line; font-style: normal; font-variant: normal; font-weight: normal; font-stretch: normal; line-height: 1.45; color: rgb(86, 116, 130); word-wrap: normal; background: rgb(246, 246, 246); overflow: auto; letter-spacing: normal; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">func (kv *KVServer) applyDaemon() {
for {
select {
case msg, ok := <-kv.applyCh:
if ok {
// have client's request? must filter duplicate command
if msg.Command != nil {
cmd := msg.Command.(Op)
kv.mu.Lock()
if dup, ok := kv.duplicate[cmd.ClientID]; !ok || dup.Seq < cmd.SeqNo {
switch cmd.Op {
case "Get":
kv.duplicate[cmd.ClientID] = &LatestReply{Seq: cmd.SeqNo,
Reply: GetReply{Value: kv.db[cmd.Key],}}
case "Put":
kv.db[cmd.Key] = cmd.Value
kv.duplicate[cmd.ClientID] = &LatestReply{Seq: cmd.SeqNo,}
case "Append":
kv.db[cmd.Key] += cmd.Value
kv.duplicate[cmd.ClientID] = &LatestReply{Seq: cmd.SeqNo,}
default:
DPrintf("[%d]: server %d receive invalid cmd: %v\n", kv.me, kv.me, cmd)
panic("invalid command operation")
}
if ok {
DPrintf("[%d]: server %d apply index: %d, cmd: %v (client: %d, dup seq: %d < %d)\n",
kv.me, kv.me, msg.CommandIndex, cmd, cmd.ClientID, dup.Seq, cmd.SeqNo)
}
}
// notify channel
if notifyCh, ok := kv.notifyChs[msg.CommandIndex]; ok && notifyCh != nil {
close(notifyCh)
delete(kv.notifyChs, msg.CommandIndex)
}
kv.mu.Unlock()
}
}
}
}
}</pre>

測(cè)試

注意，如果上面的測(cè)試出現(xiàn)錯(cuò)誤也不一定是程序本身的問(wèn)題进副，可能是單個(gè)進(jìn)程運(yùn)行多個(gè)測(cè)試程序帶來(lái)的影響
同時(shí)这揣，我們可以運(yùn)行多次避免偶然的影響
因此，如果出現(xiàn)了這種情況影斑，我們可以為單個(gè)測(cè)試程序獨(dú)立的運(yùn)行n次给赞，保證正確性，下面是每10個(gè)測(cè)試程序獨(dú)立運(yùn)行矫户，運(yùn)行n次的腳本

sleep 40

if grep -nr "FAIL.*raft.*" res; then
    echo "fail"
fi

done</pre>

總結(jié)

在本實(shí)驗(yàn)中片迅，我們封裝了lab2a raft框架實(shí)現(xiàn)了容錯(cuò)的kv服務(wù)
如果出現(xiàn)了問(wèn)題，需要仔細(xì)查看log皆辽，思考問(wèn)題出現(xiàn)的原因
下一個(gè)實(shí)驗(yàn)中柑蛇，我們將實(shí)現(xiàn)日志的壓縮

參考資料

項(xiàng)目鏈接
[lab3實(shí)驗(yàn)介紹]http://nil.csail.mit.edu/6.824/2020/labs/lab-kvraft.html)
閱讀raft論文
閱讀raft理論與實(shí)踐[1]-理論篇
閱讀raft理論與實(shí)踐[2]-lab2a
閱讀raft理論與實(shí)踐[3]-lab2a講解
閱讀raft理論與實(shí)踐[4]-lab2b日志復(fù)制
閱讀raft理論與實(shí)踐[5]-lab2c日志復(fù)制
閱讀模擬RPC遠(yuǎn)程過(guò)程調(diào)用

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市驱闷，隨后出現(xiàn)的幾起案子耻台，更是在濱河造成了極大的恐慌，老刑警劉巖空另，帶你破解...
沈念sama閱讀 207,113評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件盆耽，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡痹换，警方通過(guò)查閱死者的電腦和手機(jī)征字，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,644評(píng)論 2贊 381
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門都弹，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)娇豫，“玉大人，你說(shuō)我怎么就攤上這事畅厢》肓。” “怎么了？”我有些...
開(kāi)封第一講書人閱讀 153,340評(píng)論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)浦楣。經(jīng)常有香客問(wèn)我袖肥，道長(zhǎng)，這世上最難降的妖魔是什么振劳？我笑而不...
開(kāi)封第一講書人閱讀 55,449評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任椎组，我火速辦了婚禮，結(jié)果婚禮上历恐，老公的妹妹穿的比我還像新娘寸癌。我一直安慰自己，他們只是感情好弱贼，可當(dāng)我...
茶點(diǎn)故事閱讀 64,445評(píng)論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布蒸苇。她就那樣靜靜地躺著，像睡著了一般吮旅。火紅的嫁衣襯著肌膚如雪溪烤。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書人閱讀 49,166評(píng)論 1贊 284
城市分裂傳說(shuō)
那天庇勃，我揣著相機(jī)與錄音檬嘀，去河邊找鬼。笑死匪凉，一個(gè)胖子當(dāng)著我的面吹牛枪眉，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播再层，決...
沈念sama閱讀 38,442評(píng)論 3贊 401
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼贸铜，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了聂受？” 一聲冷哼從身側(cè)響起蒿秦，我...
開(kāi)封第一講書人閱讀 37,105評(píng)論 0贊 261
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎蛋济，沒(méi)想到半個(gè)月后棍鳖，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,601評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡碗旅，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,066評(píng)論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年渡处，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片祟辟。...
茶點(diǎn)故事閱讀 38,161評(píng)論 1贊 334
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡医瘫，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出旧困，到底是詐尸還是另有隱情醇份，我是刑警寧澤稼锅，帶...
沈念sama閱讀 33,792評(píng)論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站僚纷，受9級(jí)特大地震影響矩距，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜怖竭，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,351評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一锥债、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧痊臭，春花似錦赞弥、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 30,352評(píng)論 0贊 19
一樁弒父案绽左，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至艇潭，卻和暖如春拼窥，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背蹋凝。一陣腳步聲響...
開(kāi)封第一講書人閱讀 31,584評(píng)論 1贊 261
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工鲁纠，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人鳍寂。一個(gè)月前我還...
沈念sama閱讀 45,618評(píng)論 2贊 355
代替公主和親
正文我出身青樓改含，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親迄汛。傳聞我的和親對(duì)象是個(gè)殘疾皇子捍壤，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,916評(píng)論 2贊 344

raft理論與實(shí)踐[6]-lab3a-基于raft構(gòu)建分布式容錯(cuò)kv服務(wù)

準(zhǔn)備工作

前言

本服務(wù)實(shí)現(xiàn)的功能

實(shí)驗(yàn)思路

獲取源代碼

客戶端

補(bǔ)充Clerk

補(bǔ)充Get方法

補(bǔ)充Append和Put方法

Server

完成PutAppend、Get方法

完成對(duì)于log的應(yīng)用操作

測(cè)試

總結(jié)

參考資料

推薦閱讀更多精彩內(nèi)容