【MIT6.824】lab3 Fault-tolerant Key/Value Service 实现笔记

2024-04-19 23:04

本文主要是介绍【MIT6.824】lab3 Fault-tolerant Key/Value Service 实现笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

引言

lab3A的实验要求如下:

Your first task is to implement a solution that works when there are no dropped messages, and no failed servers.

You’ll need to add RPC-sending code to the Clerk Put/Append/Get methods in client.go, and implement PutAppend() and Get() RPC handlers in server.go. These handlers should enter an Op in the Raft log using Start(); you should fill in the Op struct definition in server.go so that it describes a Put/Append/Get operation. Each server should execute Op commands as Raft commits them, i.e. as they appear on the applyCh. An RPC handler should notice when Raft commits its Op, and then reply to the RPC.

You have completed this task when you reliably pass the first test in the test suite: “One client”.

Add code to handle failures, and to cope with duplicate Clerk requests, including situations where the Clerk sends a request to a kvserver leader in one term, times out waiting for a reply, and re-sends the request to a new leader in another term. The request should execute just once. These notes include guidance on duplicate detection. Your code should pass the go test -run 3A tests.

lab3B的实验要求如下:

Modify your kvserver so that it detects when the persisted Raft state grows too large, and then hands a snapshot to Raft. When a kvserver server restarts, it should read the snapshot from persister and restore its state from the snapshot.

总体而言,我们需要在lab2所实现的raft系统上构建一个简单的key-value存储系统,这个系统需要支持客户端的Put/Append/Get操作,同时需要支持Raft的持久化和快照功能。本系统的要求是线性一致的,即每个动作都能被当做是在一个唯一的时刻进行原子执行的,具体一致性相关的内容,可查看之前的文章:分布式系统中的线性一致性。
代码可以在https://github.com/slipegg/MIT6.824中得到。所有代码均通过了1千次的测试。

lab3A 实现

lab3A不涉及到Raft的快照功能,主要是要完成整个系统功能的构建。在实验时测试3A时,测试代码将会不断调用客户端的Put/Append/Get操作,然后检查是否所有的操作都被正确执行。

首先通过一个map来存储key-value,如下中的KVMachine所示:

type KVMachine struct {KV map[string]string
}func (kv *KVMachine) Get(key string) (string, Err) {value, ok := kv.KV[key]if !ok {return "", ErrNoKey}return value, OK
}func (kv *KVMachine) Put(key string, value string) Err {kv.KV[key] = valuereturn OK
}func (kv *KVMachine) Append(key string, value string) Err {oldValue, ok := kv.KV[key]if !ok {kv.KV[key] = valuereturn OK}kv.KV[key] = oldValue + valuereturn OK
}func newKVMachine() *KVMachine {return &KVMachine{make(map[string]string)}
}

然后是Client端的实现,首先Client在初始化时会随机生成一个数字当做自己的id,同时它也专门维护每个请求的唯一id。Client的Put/Append/Get操作都是通过RPC调用Server端的Put/Append/Get操作来实现的,如果Server端返回了错误,告诉当前Server不是leader,那么Client就会重新发送请求到下一个Server去,直到找到leader并执行请求成功了为止。Client端的PutAppend/Get操作的实现如下,Get也是类似,就是错误处理稍微不同,不再赘述:

func (ck *Clerk) PutAppend(key string, value string, op string) {DPrintf("{Clinetn-%d} try to %s {'%v': '%v'}\n", ck.clientId, op, key, value)args := PutAppendArgs{Key: key, Value: value, Op: op, ClientId: ck.clientId, RequestId: ck.requestId}for {var reply PutAppendReplyif ck.servers[ck.leaderId].Call("KVServer.PutAppend", &args, &reply) && reply.Err == OK {DPrintf("{Clinetn-%d} %s {'%v': '%v'} success\n", ck.clientId, op, key, value)ck.requestId++break} else {ck.leaderId = (ck.leaderId + 1) % int64(len(ck.servers))time.Sleep(100 * time.Millisecond)}}
}

每个Server端都会维护一个KVMachine,并且也连接到一个专门的raft节点,它的主要作用就是将客户端的请求转化为raft节点的日志,然后等待raft节点将日志提交后接收到raft节点的信息,将日志应用到自己的KVMachine中,然后返回给客户端。

将客户端请求转化为日志传递给raft部分的代码如下,Get请求也是类似的。注意这里对于重复执行过的Put、Append会直接进行返回,因为运行结果只会是OK,所以直接返回OK即可,而Get请求不需要判断是否重复执行,因为Get请求需要获取的实最新的数据,来一次就执行一次即可。

func (kv *KVServer) PutAppend(args *PutAppendArgs, reply *PutAppendReply) {// Your code here.defer DPrintf("{KVServer-%d} finishes %s {%s: %s}, the reply is %v\n", kv.me, args.Op, args.Key, args.Value, reply)kv.mu.RLock()if kv.isDuplicate(args.ClientId, args.RequestId) {kv.mu.RUnlock()reply.Err = OKreturn}kv.mu.RUnlock()logId, _, isLeader := kv.rf.Start(Op{PutAppendArgs: args})if !isLeader {reply.Err = ErrWrongLeaderreturn}DPrintf("{KVServer-%d} try to %s {%s: %s} with logId: %d\n", kv.me, args.Op, args.Key, args.Value, logId)kv.mu.Lock()ch_putAppend := kv.getNotifyCh_PutAppend(logId)kv.mu.Unlock()select {case result := <-ch_putAppend:reply.Err = result.Errcase <-time.After(MaxWaitTime):reply.Err = ErrTimeout}go func() {kv.mu.Lock()delete(kv.notifyChs_PutAppend, logId)kv.mu.Unlock()}()
}

当raft节点将日志分发给了大部分的节点后,就可以将日志提交,然后提醒Server端将日志应用到自己的KVMachine中。代码如下所示。注意对于Get请求,需要判断这时候节点是不是leader,Term是否还相同,以防止由于applyCh传递时间过长,这时候节点已经不是leader,没有最新的数据了。对于Put、Append操作需要判断是否已经是重复执行过的操作,如果是,直接标记为OK即可,不需要再次执行,同样也需要判断当前还是不是leader,如果是才有权限返回给客户端执行结果。

func (kv *KVServer) applier() {for !kv.killed() {select {case msg := <-kv.applyCh:if msg.CommandValid {kv.mu.Lock()if msg.CommandIndex <= kv.lastApplied {DPrintf("{KVServer-%d} reveives applied log{%v}", kv.me, msg)kv.mu.Unlock()continue}kv.lastApplied = msg.CommandIndexop := msg.Command.(Op)if op.GetArgs != nil {DPrintf("{KVServer-%d} apply get %v.", kv.me, op.GetArgs.Key)value, err := kv.kvMachine.Get(op.GetArgs.Key)reply := GetReply{Err: err, Value: value}if currentTerm, isLeader := kv.rf.GetState(); isLeader && currentTerm == msg.CommandTerm {if ch, ok := kv.notifyChs_Get[msg.CommandIndex]; ok {ch <- reply}}} else if op.PutAppendArgs != nil {var reply PutAppendReplyif kv.isDuplicate(op.PutAppendArgs.ClientId, op.PutAppendArgs.RequestId) {DPrintf("{KVServer-%d} receives duplicated request{%v}\n", kv.me, msg)reply.Err = OK} else {DPrintf("{KVServer-%d} apply %s {%s: %s}.\n", kv.me, op.PutAppendArgs.Op, op.PutAppendArgs.Key, op.PutAppendArgs.Value)if op.PutAppendArgs.Op == "Put" {reply.Err = kv.kvMachine.Put(op.PutAppendArgs.Key, op.PutAppendArgs.Value)} else if op.PutAppendArgs.Op == "Append" {reply.Err = kv.kvMachine.Append(op.PutAppendArgs.Key, op.PutAppendArgs.Value)}kv.lastPutAppendId[op.PutAppendArgs.ClientId] = op.PutAppendArgs.RequestId}if _, isLeader := kv.rf.GetState(); isLeader {if ch, ok := kv.notifyChs_PutAppend[msg.CommandIndex]; ok {ch <- reply}}} else {DPrintf("{KVServer-%d} receives unknown command{%v}", kv.me, msg)}if kv.isNeedSnapshot() {DPrintf("{KVServer-%d} needs snapshot\n", kv.me)kv.snapshot(msg.CommandIndex)}kv.mu.Unlock()} }}
}

lab3B 实现

这里主要需要实现Server的持久化和快照功能,每个Server有一个自己的persister,其结构如下:

type Persister struct {mu        sync.Mutexraftstate []bytesnapshot  []byte
}

其中raftstate部分是raft节点存储自身持久化状态用的,而snapshot节点是用来给Server存储自身状态用的,包括了Server的KVMachine状态以及lastPutAppendId。在Server启动时,会从persister中读取raftstate和snapshot,然后根据raftstate来初始化raft节点,根据snapshot来初始化KVMachine和lastPutAppendId。代码如下所示:

func (kv *KVServer) reloadBySnapshot(snapshot []byte) {if snapshot == nil || len(snapshot) < 1 {return}var kvMachine KVMachinevar lastPutAppendId map[int64]int64r := bytes.NewBuffer(snapshot)d := labgob.NewDecoder(r)if d.Decode(&kvMachine) != nil ||d.Decode(&lastPutAppendId) != nil {DPrintf("{KVServer-%d} reloadBySnapshot failed\n", kv.me)}DPrintf("{KVServer-%d} reloadBySnapshot succeeded\n", kv.me)kv.lastPutAppendId = lastPutAppendIdkv.kvMachine = kvMachine
}

当Server在apply节点时,按照要求,如果raft的日志信息过大,就触发快照功能,将Server的状态保存到snapshot中,同时让raft节点生成快照。如下所示:

func (kv *KVServer) snapshot(lastAppliedLogId int) {w := new(bytes.Buffer)e := labgob.NewEncoder(w)if mr, lr := e.Encode(kv.kvMachine), e.Encode(kv.lastPutAppendId); mr != nil ||lr != nil {DPrintf("{KVServer-%d} snapshot failed. kvMachine length: %v, result: {%v}, lastPutAppendId: {%v}, result: {%v},",kv.me, len(kv.kvMachine.KV), mr, kv.lastPutAppendId, lr)return}data := w.Bytes()kv.rf.Snapshot(lastAppliedLogId, data)DPrintf("{KVServer-%d} snapshot succeeded\n", kv.me)
}

由于快照的引入,Server也可能需要apply快照,即对上述的applier函数再多加一个msg类型的判断,如下所示:

else if msg.SnapshotValid {kv.mu.Lock()kv.reloadBySnapshot(msg.Snapshot)kv.lastApplied = msg.CommandIndexkv.mu.Unlock()}

相关问题

为什么Get操作不能直接读leader的本地数据?

在Raft系统中,当面临网络分区情况时,原本的leader如果位于一个小分区,那么他就不知道其实大分区中已经有了一个新leader了,这样如果client还是连接的原本的leader,并且是直接读取该leader的本地数据,那么就会面临读取到过时数据的问题,导致系统线性不一致。

所以解决这个问题的关键在于确定节点真的是leader,这里采取的是一个简单的方法,即将这个Get操作作为一个log日志放入raft系统中,直到raft系统将这个log日志提交后,才返回。实际上还有优化的空间,一个方法是在raft接受到了一个Get操作后,立刻执行心跳,如果接收到了过半的节点的心跳回复,那么就证明了这个节点是真的leader,这样就可以直接返回数据了,这就避免了将Get操作放入raft系统中的开销。还有一种方法是叫做Lease Read,它的吞吐更大,详情可参考深入浅出etcd/raft —— 0x06 只读请求优化。

applier中是否有机会出现重复执行的put、append操作?

有机会出现。例如当客户端发送后,Server将其提交给了Raft,但是Raft没有在规定时间内返回,那么就会返回超时,然后客户端再去循环提交一轮,再一次提交给这个节点的时候,节点此时可能还是没有收到Raft的返回,所以会再次提交给Raft,这样就会出现重复提交的情况。而在applier中就会只执行第一次提交的操作,后续的提交都会被忽略。

只用lastPutAppendId记录最后一次的Put、Append操作的id是否可行?

可行。因为系统中Put、Append操作的结果只会是ok,所以不需要记录每次的Put、Append操作的id,同时由于raft系统中一旦apply了就是永久apply了,并且前面的操作也都apply了,不存在回退的情况,所以如果当前操作的id小于最新一次Put、Append操作的id,那么就说明是重复执行了,直接返回ok即可。

运行结果

代码通过了1k次的测试,如下图所示。

请添加图片描述

参考资料

  • 深入浅出etcd/raft —— 0x06 只读请求优化

这篇关于【MIT6.824】lab3 Fault-tolerant Key/Value Service 实现笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/918676

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy:PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注,收藏不迷路💖 Kubernetes的PodSecurityPolicy(PSP)是一个关键的安全特性,它在Pod创建之前实施安全策略,确保P

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

工厂ERP管理系统实现源码(JAVA)

工厂进销存管理系统是一个集采购管理、仓库管理、生产管理和销售管理于一体的综合解决方案。该系统旨在帮助企业优化流程、提高效率、降低成本,并实时掌握各环节的运营状况。 在采购管理方面,系统能够处理采购订单、供应商管理和采购入库等流程,确保采购过程的透明和高效。仓库管理方面,实现库存的精准管理,包括入库、出库、盘点等操作,确保库存数据的准确性和实时性。 生产管理模块则涵盖了生产计划制定、物料需求计划、