内蒙古建设厅官方网站,三亚门户网站,python做网站用什么软件,网站建设加盟哪个好实验目标#xff1a;基于raft日志复制算法实现的线性一致性kv存储引擎。
线性一致性#xff1a;
所有的读操作都能够读取到最近一次写操作的结果。所有节点#xff08;或者进程#xff09;在同一时刻#xff0c;看到的数据都是相同的。
简而言之#xff0c;线性一致性…实验目标基于raft日志复制算法实现的线性一致性kv存储引擎。
线性一致性
所有的读操作都能够读取到最近一次写操作的结果。所有节点或者进程在同一时刻看到的数据都是相同的。
简而言之线性一致性保证所有的操作在系统中是按照其提交的顺序进行执行的因此在任何时刻对于任意一个节点或进程所提出的读操作都应该返回最新提交的写操作的结果。
当一个节点或进程发出一个写操作之后其他节点或进程必须立即且无条件地能够看到这个写操作的结果以保证线性一致性的实现。
需要注意的是线性一致性通常会带来更高的延迟和更大的开销因为系统需要通过各种机制来保证不同节点或进程之间的数据同步。
想法raft保障的日志都是一致性的所以如果我们把操作通过raft来传播的话通过applyChan我们就可以得到2所有节点或者进程在同一时刻看到的数据都是相同的。然后如果我们两个连续的读要读到最近一次写的内容如果没有别的client并发操作的话。那么在日志看来就是
前缀日志 读操作 读操作那么根据raft日志的顺序我们可以发现所有的读操作都能够读取到最近一次写操作的结果。但是这个东西有一个限制就是我们对于append和put操作只能执行一次为啥呢。
有人可能认为只要写请求是幂等的那重复执行多次也是可以满足线性一致性的实际上则不然。考虑这样一个例子对于一个仅支持 put 和 get 接口的 raftKV 系统其每个请求都具有幂等性。设 x 的初始值为 0此时有两个并发客户端客户端 1 执行 put(x,1)客户端 2 执行 get(x) 再执行 put(x,2)问客户端 2 读到的值x 的最终值是多少。对于线性一致的系统答案可以是 (0,1)(0,2) 或 (1,2)。然而如果客户端 1 执行 put 请求时发生了上段描述的情况然后客户端 2 读到 x 的值为 1 并将 x 置为了 2最后客户端 1 超时重试且再次将 x 置为 1。对于这种场景答案是 (1,1)这就违背了线性一致性。归根究底还是由于幂等的 put(x,1) 请求在状态机上执行了两次有两个 LZ 点。因此即使写请求的业务语义能够保证幂等不进行额外的处理让其重复执行多次也会破坏线性一致性。
所以我们要线性一致性的话我们就是要保障put/append操作可以commit的多次但是只能应用在kv层一次所以我们可以对每个客户端记录下每个客户端最后的commitIdx. lab3
client端
我们要找到server集群的leader要用一个commitIdx来区分请求使得请求有一个序列因为client没有并发所以这个最大值就是最后一个请求我们需要把这个对于每个客户端记录一下
func (ck *Clerk) PutAppend(key string, value string, op string) {// You will have to modify this function.args : PutAppendArgs{Key: key,Value: value,Op: op,LeaderId: ck.LeaderId,CommandId_PA: ck.commandId,ClientId: ck.clientId,}DPrintf(Node{%v} start appendput{%v} value{%v} op{%v}, ck.clientId, key, args.Value, op)for {var reply PutAppendReplyif !ck.servers[ck.LeaderId].Call(KVServer.PutAppend, args, reply) || reply.Err ErrWrongLeader || reply.Err ErrTimeOut {ck.LeaderId (ck.LeaderId 1) % int64(len(ck.servers))// log.Println(1)continue}ck.commandIdDPrintf(Node{%v} appendput sucess, ck.clientId)return}
}
server端
因为start在raft底层已经上了锁足够保障并发安全不用加kv层的锁不如可能会死锁。然后raft层存的是log of operations。同时read也要记录因为我们根据的是日志的顺序来决定执行的顺序的。最后那个delete为了减少内存占用。实际上不用担心ch有东西被delete掉了因为kv有重试机制同时更重要的是kv applier chan传递时上了锁delete也上了锁。同时一个apply协程也保障了顺序性。也只有一个在channel等待同时我们做了一个buffer的channel根据前面的描述buffer的大小不影响正确性我们可以用因为最多一个在buffer里因为我们用的是一个aplier协程但我们不用buffer的话可能在start后得到notify_chan的锁就获得不到因为我们start比较快就commit阻塞在applier了。
func (kv *KVServer) PutAppend(args *PutAppendArgs, reply *PutAppendReply) {// Your code here.var op_type intif args.Op Append {op_type APPEND} else {op_type PUT}make_op : Op{ClientId: args.ClientId,OpType: op_type,Key: args.Key,Value: args.Value,CommandId: args.CommandId_PA,}DPrintf(Node{%v} may be ........, kv.me)kv.mu.Lock()if kv.isdupicate(make_op.ClientId, make_op.CommandId) {lastreply : kv.clientsInformation[make_op.ClientId].Last_repyreply.Err lastreply.Errkv.mu.Unlock()return}kv.mu.Unlock()DPrintf(Node{%v} stall here, kv.me)index, _, is_leader : kv.rf.Start(make_op)if !is_leader {reply.Err ErrWrongLeaderreturn}kv.mu.Lock()ch : kv.newChannel(index)kv.mu.Unlock()select {case rpc : -ch:reply.Err rpc.Errif rpc.Err OK {// log.Printf(reply will Node{%v} the return reply optype{%v} commidex{%v}, lastapplied{%v} key{%v} value{%v}, kv.me, make_op.OpType, make_op.CommandId, kv.lastApplied, make_op.Key, make_op.Value)}case -time.After(500 * time.Millisecond):reply.Err ErrTimeOut}DPrintf(Node{%v} here will reply{%v}, kv.me, reply)kv.mu.Lock()kv.Delete(index)kv.mu.Unlock()}snapshot要存的是kv storage和clientInformation。先recover snapshot在kv storage和clientinforamtion ,然后raft重放log接着作用于clientinformation和storage上不需要持久化kv_storage和client_information。因为下层的raft的log和snapshot已经保障了重放时会恢复。
func (kv *KVServer) applier() {for !kv.killed() {DPrintf(Node{%v} here applier, kv.me)select {case message : -kv.applyCh:{DPrintf(Node{%v} try to applymessage{%v}, kv.me, message)if message.CommandValid {kv.mu.Lock()if message.CommandIndex kv.lastApplied {DPrintf(Node{%v} command{%v} is less than kv lastapply{%v}, kv.me, message.CommandIndex, kv.lastApplied)kv.mu.Unlock()continue}kv.lastApplied message.CommandIndexreply : new(CommandReply)make_op : message.Command.(Op)DPrintf(Node{%v} makeop.........{%v}, kv.me, make_op)if make_op.OpType ! GET kv.isdupicate(make_op.ClientId, make_op.CommandId) {DPrintf(Node{%v} is duplicate, kv.me)reply.Err kv.clientsInformation[make_op.ClientId].Last_repy.Err} else {reply kv.applylogtoState(make_op)if make_op.OpType ! GET {kv.clientsInformation[make_op.ClientId] ClientInfo{Last_commandId: make_op.CommandId, Last_repy: *reply}}}// kv.rf.Persist(kv.clientsInformation, kv.lastApplied)current_term, is_Leader : kv.rf.GetState()if is_Leader message.CommandTerm current_term {DPrintf(Node{%v} get state, kv.me)notify_chan : kv.newChannel(message.CommandIndex)notify_chan - reply// if kv.maxraftstate ! -1 {// kv.rf.Persist(kv.clientsInformation, kv.storage)// }DPrintf(reply to notify chan{%v}, reply)} else {DPrintf(Node{%v} is not leader, kv.me)}// 3Bif kv.rf.ShouldSnap(kv.maxraftstate, message.SnapshotIndex) {DPrintf(Node{%v} start to snapshot index{%v}, kv.me, message.CommandIndex)kv.snapMake(message.CommandIndex)}kv.mu.Unlock()} else if message.SnapshotValid {kv.mu.Lock()kv.storeSnapshot(message.Snapshot)kv.lastApplied message.SnapshotIndexkv.mu.Unlock()} else {panic(fmt.Sprintf(Valid message{%v}, message))}}}}
}
文章转载自： http://www.morning.fsbns.cn.gov.cn.fsbns.cn http://www.morning.qbgff.cn.gov.cn.qbgff.cn http://www.morning.hjjhjhj.com.gov.cn.hjjhjhj.com http://www.morning.tkflb.cn.gov.cn.tkflb.cn http://www.morning.hotlads.com.gov.cn.hotlads.com http://www.morning.dkqr.cn.gov.cn.dkqr.cn http://www.morning.jtnph.cn.gov.cn.jtnph.cn http://www.morning.bssjz.cn.gov.cn.bssjz.cn http://www.morning.rmqlf.cn.gov.cn.rmqlf.cn http://www.morning.zqcsj.cn.gov.cn.zqcsj.cn http://www.morning.lnmby.cn.gov.cn.lnmby.cn http://www.morning.mjtgt.cn.gov.cn.mjtgt.cn http://www.morning.dfrenti.com.gov.cn.dfrenti.com http://www.morning.byshd.cn.gov.cn.byshd.cn http://www.morning.dcdhj.cn.gov.cn.dcdhj.cn http://www.morning.qjbxt.cn.gov.cn.qjbxt.cn http://www.morning.ywndg.cn.gov.cn.ywndg.cn http://www.morning.lsgsn.cn.gov.cn.lsgsn.cn http://www.morning.xtyyg.cn.gov.cn.xtyyg.cn http://www.morning.rkmhp.cn.gov.cn.rkmhp.cn http://www.morning.tbnn.cn.gov.cn.tbnn.cn http://www.morning.ycpnm.cn.gov.cn.ycpnm.cn http://www.morning.krhkb.cn.gov.cn.krhkb.cn http://www.morning.qgmwt.cn.gov.cn.qgmwt.cn http://www.morning.ylqb8.cn.gov.cn.ylqb8.cn http://www.morning.c7507.cn.gov.cn.c7507.cn http://www.morning.rhgtc.cn.gov.cn.rhgtc.cn http://www.morning.qkdjq.cn.gov.cn.qkdjq.cn http://www.morning.qzsmz.cn.gov.cn.qzsmz.cn http://www.morning.hilmwmu.cn.gov.cn.hilmwmu.cn http://www.morning.cgntj.cn.gov.cn.cgntj.cn http://www.morning.tsnmt.cn.gov.cn.tsnmt.cn http://www.morning.lfqnk.cn.gov.cn.lfqnk.cn http://www.morning.gxfzrb.com.gov.cn.gxfzrb.com http://www.morning.rwzkp.cn.gov.cn.rwzkp.cn http://www.morning.mcndn.cn.gov.cn.mcndn.cn http://www.morning.tdzxy.cn.gov.cn.tdzxy.cn http://www.morning.jfcbs.cn.gov.cn.jfcbs.cn http://www.morning.rycbz.cn.gov.cn.rycbz.cn http://www.morning.lywys.cn.gov.cn.lywys.cn http://www.morning.djxnn.cn.gov.cn.djxnn.cn http://www.morning.ktsth.cn.gov.cn.ktsth.cn http://www.morning.crsnb.cn.gov.cn.crsnb.cn http://www.morning.gwmny.cn.gov.cn.gwmny.cn http://www.morning.ykxnp.cn.gov.cn.ykxnp.cn http://www.morning.qphdp.cn.gov.cn.qphdp.cn http://www.morning.mqgqf.cn.gov.cn.mqgqf.cn http://www.morning.horihe.com.gov.cn.horihe.com http://www.morning.ndmh.cn.gov.cn.ndmh.cn http://www.morning.yltyr.cn.gov.cn.yltyr.cn http://www.morning.rfljb.cn.gov.cn.rfljb.cn http://www.morning.dfkmz.cn.gov.cn.dfkmz.cn http://www.morning.lngyd.cn.gov.cn.lngyd.cn http://www.morning.wgbmj.cn.gov.cn.wgbmj.cn http://www.morning.kxmyj.cn.gov.cn.kxmyj.cn http://www.morning.nlhcb.cn.gov.cn.nlhcb.cn http://www.morning.wklmj.cn.gov.cn.wklmj.cn http://www.morning.lggng.cn.gov.cn.lggng.cn http://www.morning.bgpb.cn.gov.cn.bgpb.cn http://www.morning.crqpl.cn.gov.cn.crqpl.cn http://www.morning.sfrw.cn.gov.cn.sfrw.cn http://www.morning.rkkh.cn.gov.cn.rkkh.cn http://www.morning.syhwc.cn.gov.cn.syhwc.cn http://www.morning.rkypb.cn.gov.cn.rkypb.cn http://www.morning.xzlp.cn.gov.cn.xzlp.cn http://www.morning.jzykq.cn.gov.cn.jzykq.cn http://www.morning.rnngz.cn.gov.cn.rnngz.cn http://www.morning.nlysd.cn.gov.cn.nlysd.cn http://www.morning.wtxdp.cn.gov.cn.wtxdp.cn http://www.morning.daidudu.com.gov.cn.daidudu.com http://www.morning.tdttz.cn.gov.cn.tdttz.cn http://www.morning.rqwmt.cn.gov.cn.rqwmt.cn http://www.morning.fwzjs.cn.gov.cn.fwzjs.cn http://www.morning.qieistand.com.gov.cn.qieistand.com http://www.morning.jsdntd.com.gov.cn.jsdntd.com http://www.morning.zkgpg.cn.gov.cn.zkgpg.cn http://www.morning.rknhd.cn.gov.cn.rknhd.cn http://www.morning.mtsgx.cn.gov.cn.mtsgx.cn http://www.morning.ffptd.cn.gov.cn.ffptd.cn http://www.morning.ptzf.cn.gov.cn.ptzf.cn
