如何提高网站的权重,沈阳市做网站的公司,2018年做网站还能,做二手手机交易网站文章目录 前记Paper6#xff1a;RaftLEC5、6#xff1a;RaftLAB22AtaskHintlockingstructureguide设计与编码 2BtaskHint设计与编码 2CtaskHint question后记 LEC5#xff1a;GO, Threads, and Raftgo threads技巧raft实验易错点debug技巧 前记
趁着研一考完期末有点点空余… 文章目录 前记Paper6RaftLEC5、6RaftLAB22AtaskHintlockingstructureguide设计与编码 2BtaskHint设计与编码 2CtaskHint question后记 LEC5GO, Threads, and Raftgo threads技巧raft实验易错点debug技巧 前记
趁着研一考完期末有点点空余时间把Raft的实验补了记录着看视频、论文和实验过程中的一些想法
Paper6Raft
概述来自NewBing
raft算法是一种用于分布式一致性的共识算法旨在解决分布式系统中的领导者选举和日志复制等问题。它的设计目标是易于理解和实现并且能够提供强一致性保证。raft算法的核心原理包括三个关键组件领导者选举、日志复制和安全性。
领导者选举raft算法将时间划分为一个个的任期term每个任期的开始都是一次选举一个或多个候选者candidate会尝试成为领导者leader。如果一个候选者赢得了大多数节点的投票它就会成为新的领导者并在该任期内管理整个集群。如果没有选出领导者就会开始下一个任期并重新进行选举。raft算法保证在任意时刻最多只有一个领导者。日志复制领导者选出后就开始接收客户端的请求并将请求作为日志条目log entry加入到它的日志中然后并行地向其他节点发送附加日志请求AppendEntries RPC复制日志条目。当这条日志被复制到大多数节点上领导者就将这条日志应用到它的状态机并向客户端返回执行结果。领导者会不断地重试附加日志请求直到所有的节点都存储了所有的日志条目。安全性raft算法增加了一些限制来保证安全性即只有拥有最新的已提交的日志条目的节点才有资格成为领导者而且领导者只能提交当前任期的日志条目旧任期的日志条目要等到提交当前任期的日志条目来间接提交。这样可以避免已提交的日志条目被覆盖的情况。
有一个经验要想在Raft中假设A情况你首先得考虑A情况是否有可能发生。
细节点 Raft Basic Figure 2是非常重要的一个图。follower只接受请求不主动发起请求当client发送请求到follower时会转发给ld处理ld会通过发送AE来抑制其他server发起选举。也就是说ld不出错的话它永远是ld。当ld提交时会通知followerterm会通过包的发送来交换。如果接受者发现有更大的任期那么它会更新自己的任期。如果发现更小term的包那么会拒绝。如果ld或candidate发现自己的任期更小了那么会立刻转变为follower时序client request - ld - 将log entry复制到半数以上服务器并得到回复 - ld commited、apply - 返回响应给client -后面心跳检测AE)时随便告诉其他服务器自己已经commited并apply Leader election 当election timer计时结束还没有ld发请求那么follower会认为ld死了会变成candicate发起选举如果split votes发生了那么term会增加并再次发起选举timer计时器是随机的注意每一个新ld的产生由于它要获得多数server的认可在请求投票时会把最新的term同步给多数的server因此term也是一个“多数共识”的标识。 Log replication 当ld 接收到log entry时它会保证大多数server都接受到这个log entry才会继续自己的下一步操作如返回响应给client如果一个server对接受log entry没有响应ld会无限地尝试如果ld认为LE(log entry是足够安全的了那么这个时候叫作committed注意apply和committed是不一样的在之后ld会通过AE来将已经committed的index告知给各个follower当ld发送AE给follower时如果follower发现日志冲突那么ld会decrements nextIndex直到两者保持一致。注意ld永远不会重写/删除自己的日志。decrements nextIndex不会把follower上的日志删除吗会的但是ld一定有了所有能被commited的日志因此以ld为准。 Safety raft保证被选举出的ld一定会存有所有已经commited的日志这个最难理解了。没有commited的entry又怎么处理呢这样理解要想commited那么日志一定是被复制到“半数以上的服务器”。而新ld一定是“半数以上的服务器”中的一个。因此只要是新ld那么一定有能保证被commited的日志 。。the voter denies its vote if its own log is more up-to-date than that of the candidate。也就是说要被投票的candidate的日志要比半数以上的voter的日志要more up-to-date。什么叫more up-to-date更大term如果term相同则更大index leader的前提是majority因此leader肯定拥有majority的log这就是为什么叫做共识 上面说法有问题更正一下raft保证被选举出的ld一定会存有比大多数server更up-to-date的日志。 leader的前提是majority都同意因此leader肯定拥有majority都同意的更up-to-date的log这就是为什么叫做共识 总结一下大多数server都认为A服务器有比自己more up-tp-date的log**共识**那么A就可以是ld。 ld只允许commited自己任期内的日志为什么 新ld上线时不能够确定旧的entry是否已经被commited如重启后commitedIndex被重置,旧的entry是否已经被大多数server所有。 当能commite自己任期内的log entry时就已经说明前面任期的所有日志一定已经复制到大多数server了。 因此只能通过提交自己任期内的log entry来间接说明之前的日志可以提交。 同时能commited自己任期内的日志说明已经通知到了半数以上服务器这个时候半数以上的服务器的日志中的term是和ld一样是最新的。 图8描述了log即使存储在大多数的server上仍然可能被后面的新ld覆盖(图8的d。 因此不能够直接通过复制的数量来判断之前任期的日志条目是否提交图8的c。 所以才出现下下面的解决方案ld只允许提交自己任期内的log entry。这样保证当 图8的e 的S1的任期4日志被提交时任期为3的自然也算被提交了。 Timing and availabilitybroadcastTime ≪ electionTimeout ≪ MTBF平均故障时间 broadcastTime ≪ electionTimeout 如果不能保证这个那么会频繁出现选举失败electionTimeout ≪ MTBF保证这个是因为让选举平稳进行。这个用脑子想想就知道~为了保证系统平衡运行肯定这种定时器要小于故障时间的。 Cluster membership changes 使用了joint consensus两阶段转变。首先转为joint状态中间态然后再转变为new configuration状态raft的实现中在中间态依然可以正常进行选举和处理client的请求 Log compaction 使用了快照。这个好像在lab3用得到。 Client interaction 初始时client会随机挑选一个server进行连接client发送的请求都会带有一个 唯一的id如果重复请求那么server会通过请求的id直接返回之前已经执行过的请求的响应
文章的假设
应用程序状态是易失的当一个机器死掉后通过心跳确认自己的apply位置并重演一次操作先不考虑日志压缩
问题 如何避免脑裂 majority voting system。这个是整个机制的基石odd servers当出现网络partition时绝不可能有超过一边拥有一半以上的服务器大多数投票机制保证在每一步要投票时保证投票的“大多数”机器中一定有一部分会和上次投票重叠。 如何知道“半数以上” raft算法中每个服务器节点都会保存一些关于集群的信息其中就包括集群的总数目server count。这个信息可以在集群初始化的时候由配置文件或者命令行参数来指定也可以在集群运行的过程中由领导者节点来动态更新。总数目是固定的不会因为机器的故障而减少 要是因网络故障完全将raft的服务器分区成两半怎么办 绝不可能有超过一边拥有一半以上的服务器 Raft集群最大能忍受的故障server数目是多少 假设一共有2f 1台机器那么最多允许f台机器故障。底层原理是因为投票机制是多数机制如果是有n台机器那么就是 2f1nf (n - 1) / 2 有不确定性操作的命令怎么办 为什么需要log entry 为了保证操作顺序暂存操作。因为操作到来不确定是否一被要执行。保存副本当网络故障时可以重发给follower Raft为什么需要要ld比如Paxos就没有ld 加速系统应答让系统更加容易理解 如果因为网络故障分裂成两个partition旧ld在一半但另一半有超过半数的server并且选举出了新ld这个时候如何处理为什么旧ld不会导致错误发生 因为旧ld不会得到多数server的回应因此不会成功执行任何命令 如果一个server的term跑得太快怎么办 快就快。有投票机制的保证没有关系的。 那么这些entry在旧ld执行后返回给client时失败了怎么办新上任的ld还会再执行再给返回client吗 请求是有带id的可以通过id来寻找已经执行的结果。 如果一个ld已经把log复制给大多数server了但是在commited之前挂掉了。那么这个log算是commited吗 还是Figure8©。不算的。只有当前ld将自己任期内的log提交了之前的所有log才算是commited 不能够通过“已经复制日志给大多数server”来判断“是否已经commited” 还是Figure8© 为什么不选有最长日志的作为领导人 最长不代表最up-to-date 。最长不代表能复制给多数server。也就是没有共识。 什么是线性化语义 在Raft协议中“linearizable semantics”线性化语义是一个重要的概念。这意味着对于任何两个操作如果在实际执行中操作A在操作B之前完成那么在系统的状态中操作A就应该在操作B之前 在Raft协议中为了实现线性化语义通常会在服务器端维护一个关于已经执行过的请求的记录。这个记录通常包括每个客户端的最后一个请求的ID以及对应的响应。当收到一个新的请求时服务器首先会检查这个请求的ID是否已经存在于记录中。如果存在说明这个请求是重复的服务器就会直接返回之前的响应而不会再次执行这个请求 总的来说linearizable semantics是Raft协议中保证一致性的重要机制它能够确保所有的操作都能按照一定的顺序执行并且每个操作只执行一次
LEC5、6Raft
随便记记
mapReduce、GFS、VM-FT都单一实体来决定谁是ld最详细对raft的资料https://raft.github.io/教学动画https://thesecretlivesofdata.com/raft/
LAB2
注意点
Raft will continue to operate as long as at least a majority of the servers are alive and can talk to each other. If there is no such majority, Raft will make no progress, but will pick up where it left off as soon as a majority can communicate again.the service expects your implementation to send an ApplyMsg for each newly committed log entry to the applyCh channel argument to Make()Your Raft peers should exchange RPCs using the labrpc Go package (source in src/labrpc).因为测试器会模拟丢包等网络故障
2A
http://nil.csail.mit.edu/6.824/2020/labs/lab-raft.html
task
实现ld选举 及 心跳检测。当旧ld死掉时当follower收不到旧ld的心跳时要有接管机制
Hint
只关注你当前的任务但是应该也要考虑到后面的扩展本实验中the number of Raft peers (usually 3 or 5)Add the Figure 2 state for leader election to the Raft struct in raft.go.Modify Make() to create a background goroutine that will kick off leader election periodically by sending out RequestVote RPCs when it hasn’t heard from another peer for a while. This way a peer will learn who is the leader, if there is already a leader, or become the leader itself. Implement the RequestVote() RPC handler so that servers will vote for one another. 就是要有一个机制心跳超时后要发起选举。The tester requires that the leader send heartbeat RPCs no more than ten times per second.每秒不得多于10次的心跳检测旧ld死掉后要求5秒内就要完成新ld的选举。因为要求选举时间和心跳间隔选得尽可能短The paper’s Section 5.2 mentions election timeouts in the range of 150 to 300 milliseconds. Such a range only makes sense if the leader sends heartbeats considerably more often than once per 150 milliseconds. Because the tester limits you to 10 heartbeats per second, you will have to use an election timeout larger than the paper’s 150 to 300 milliseconds, but not too large, because then you may fail to elect a leader within five seconds. 总的来说这个是说election timer的时间应该设置超过150~300 milSecond。gpt建议300到500。但是不知道原理。。使用looptime.Sleep()来完成周期性任务You may find this guide useful, as well as this advice about locking and structure for concurrency.The tester calls your Raft’s rf.Kill() when it is permanently shutting down an instance. You can check whether Kill() has been called using rf.killed(). You may want to do this in all loops, to avoid having dead Raft instances print confusing messages. 就是test发送信号要永久杀死一个server但是不是通过进程强制杀死。要处理这个信号。周期性任务要通过这个标志判断是否要继续。debug 可以用print语句然后使用 go test -run 2A out. 查看You might find DPrintf in util.go useful to turn printing on and off as you debug different problems. 要通过RPC发送的字段必须大写使用go test -race来保证代码没有race测试时间限制 For all of labs 2, 3, and 4, the grading script will fail your solution if it takes more than 600 seconds for all of the tests (go test), or if any individual test takes more than 120 seconds.
locking
不论读写如果要保证一致性的一定要加锁Code that waits should first release locks. If that’s not convenient, sometimes it’s useful to create a separate goroutine to do the wait.等待的代码要释放锁。但是等待的代码执行完毕后要重新获得锁并判断自己的assumption是否还和当前的环境相同将当时主线程的参数复制到goroutine中。
structure
长时间运行的 activities 应该在不同的线程运行。不同activities 应该也要分割开处理timeout的通用思路存储一个最后时间a睡眠然后在某个时间b判断 b - a timeout在将log送入到applych时必须保证顺序。因此这个操作只能在一个goroutine执行推进 commitIndex 的代码需要触发应用 Goroutine。为了实现这一点建议使用条件变量如 Go 中的 sync.Cond就是signal机制。每个RPC的发送和处理应该在同一个goroutine.
guide figure2是绝对权威的总指导 hearbeat返回时如果返回true是隐式地告诉ld当前follower的日志和ld完全同步。因此即使是hearbeat也要检测里面的term等状态。 什么时候重置election timer 从当前ld接受到AE自己开始一个选举期投票给其他peer的时候。 一个任期内只能投票一次但是由于这个规则的存在If RPC request or response contains term T currentTerm: set currentTerm T, convert to follower。这会改变当前follower的term因此可以再次投票 Check 2 for the AppendEntries RPC handler should be executed even if the leader didn’t send any entries. 也就是说heartbeat应该同正常的AE同等对待。 nextIndex 和matchIndex的不同 nextIndex是极其乐观的初始化为 index1。ld用来指导FO从哪里开始复制日志matchIndex是保守、安全的初始化为-1。用来指示FO已经复制的最高索引。只有在FO对AE请求返回true时这个matchIndex才更新。 对于过期响应的怎么处理应该在args的参数中保留你发送时的term然后在返回响应时比较当前term和当前发送的term是否一样。如果不一样直接丢了。 matchIndex的更新如果在收到响应后已经check过assumption了那么应该将matchIndexprevLogIndexlen(entrites[])而不是直接 matchIndexnextIndex-1 or matchIndex len(log)。因为在发送请求的期间nextIndex可能已经改变了(比如故障重启len(log)更会改变比如有Client请求拼接。 快速恢复的nextIndexhttps://thesquareplanet.com/blog/students-guide-to-raft/#an-aside-on-optimizations 在AE的reply时返回多两个字段conflictIndex和conflitTerm 如果FO没有prevLogIndex的日志那么直接返回 conflictIndexlen(FO自己的所有log), conflictTermNone如果FO有prevLogIndex的日志但是term不匹配设FO的冲突的Term为termA。则返回 conflictTermlog[prevLogIndex].TermtermA。并把 conflictIndex设置为termA的第一个log当LD收到冲突响应时首先查找自己是否有 conflictTermtermA的日志。如果有将nextIndex设置为termaA的最后一个日志的下一个位置。如果没有termA的日志则直接将nextIndexconflictIndex 简单折中实现就是只用conflictIndex不用conflictTerm但这样在某些情况下会多发送些log entry。 conflictIndex的作用 跳过所有FO自己没有的日志跳过一个term的日志这里就是把所有冲突的termA全部跳过 conflitTerm的作用 辅助让 LD 的nextIndex不要把所有的termA日志都跳过 If the leader has no new entries to send to a particular peer, the AppendEntries RPC contains no entries, and is considered a heartbeat. 也就是说同步日志的频率至少和hearbeat一样或者说直接把同步日志这个功能做成heartbeat。如果有需要同步的日志那么直接同步。如果没有需要同步的日志则看成是一个heartBeatentriesnull)。 遇到的问题在hearbeat实现的时候没有按AE的规则来严格设置prevLogIndex和相应的entries[]导致一些bug出现。比如一个hearbeat过来带了最新的leadercommit把FO的rf.commit更新了但hearbeat并没有携带最新的log。 因此在实现的时候直接把同步日志做成心跳检测。逻辑上统一了。并设置条件变量在需要的时候手动触发一次同步日志。也就是设置死循环用和heartBeat一样的频率触发这个条件变量。然后这个条件变量也可以在其他地方手动触发 所以是把 AE看成是hearbeat… 有点奇怪的感觉
设计与编码
有哪些周期性activity
ld的心跳检测FO的election timeout
要加哪些额外的状态
当前ld的id
动作有哪些
ld发送心跳FO变成CA并发起选举请求多数投票 被killed()了那么剩下的已经启动的goRoutine怎么办难道说每一个动作后面都要加killed()判断那也太麻烦了吧。目前看来只要在各个函数头加上killed()判断就行即使剩下的go routine被执行了也不会造成实质性的伤害。 然后每一个动作后加上killed()判断更直观点毕竟killed()也是assumption之一。 注意rf.dead变量虽然是原子的但这种原子性是为了保护这个变量。所以判断killed()的时候最好也当成关键性代码用mutex包裹起来。 小心defer如果放在一个死循环里面会执行不了
2B
task Implement the leader and follower code to append new log entries, so that the go test -run 2B tests pass. Hint
实现Start()函数拼接日志并同步One way to fail to reach agreement in the early Lab 2B tests is to hold repeated elections even though the leader is alive. Look for bugs in election timer management, or not sending out heartbeats immediately after winning an election
设计与编码
当service调用Start()时拼接日志到log[]signal条件变量cond1当ld的 last log index nextIndex时要发送同步日志 syncLogToPeer。成功则更新nextIndex和matchIndex。失败的话减少nextIndex继续尝试signal一下条件变量cond1。然后刚成为LD的时候应该也要启动一下这个。如何确认能commited当 N commitIndex并且N大于大多数的matchIndex并且log[N].term rf.currentTerm那么就能commit到这里。什么时候检查先定期吧简单点。
2C
task
Complete the functions persist() and readPersist()Insert calls to persist() at the points where your implementation changes persistent state
Hint
You will probably need the optimization that backs up nextIndex by more than one entry at a time
question
实现中疑惑的点 同步日志的时候如果用条件变量来实现那么当一个server crash的时候没有时机去触发这个条件变量。后面我还是用了forsleep来实现。有什么好的办法 条件变量的用处似乎不大因为都是周期性任务。而且如果用触发来做有些情况又触发不了。不过实现的时候apply log用了条件变量。这个是一定可以被触发的。 代码中还有比较多的todo偷懒没搞hh那些都是可以优化的点
后记
全部代码写完后重新运行三个test。均通过。
由于1次实验有偶然性再运行10次 go test -run 2也均通过。要多运行几次小概率的bug才会出现 写代码前还是得弄清楚需求这里是看大量lab相关的文档。写代码加调试花了2~3天周日下午到周三早上期间还帮师兄改了论文但看论文和文档远远不止。 写完后看了别人的代码差别还是挺大的hh自己实现得比较乱别人可以这么优雅 而且要遵守建议和论文中的规则自己创造性地“乱写”没有被证明对那么debug之路会很漫长 RPC调用与assumption 日志索引从1开始确实很妙省去了非常多的代码判断。
LEC5GO, Threads, and Raft
在写实验的时候用大粒度锁就行别trick.去想着从cpu层面优化~The Go Memory ModelIf you must read the rest of this document to understand the behavior of your program, you are being too clever. Don’t be clever.如果你的代码中出现了常数要想想为什么可以是常数为什么是这个常数其他常数不行
go threads技巧
waitGroup、闭包能访问到创建该线程的上下文
//1.可以作为投票的一种实现
func main() {var wg sync.WaitGroupfor i : 0; i 5; i {wg.Add(1)go func(x int) {sendRPC(x)wg.Done()}(i) //2.i要传递}wg.Wait()
}func sendRPC(i int) {println(i)
}
周期性任务
func periodic() {for {println(tick)time.Sleep(1 * time.Second)mu.Lock() //如果不加锁无法保证能马上见到其他人作的改变if done {return}mu.Unlock()}
}条件变量 (signal)建议实验中直接用broadcast
func main() {rand.Seed(time.Now().UnixNano())count : 0finished : 0var mu sync.Mutexcond : sync.NewCond(mu)for i : 0; i 10; i {go func() {vote : requestVote()mu.Lock()defer mu.Unlock()if vote {count}finishedcond.Broadcast()}()}mu.Lock() //注意。要先获得lock才能wait。相当于java中synchorized 这个功能放进了Object中了for count 5 finished ! 10 {cond.Wait()}if count 5 {println(received 5 votes!)} else {println(lost)}mu.Unlock()
}func requestVote() bool {time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)return rand.Int() % 2 0
}mu.Lock()
// do something that might affect the condition
cond.Broadcast()
mu.Unlock()----mu.Lock()
while condition false {cond.Wait()
}
// now condition is true, and we have the lock
mu.Unlock()channel无缓冲channel
是一种没有容量的队列。当发送时如果没有接收方发送线程会被阻塞。相反地如果没有人发送接收方也会被阻塞可用于生产者消费者waitGroup效果
func main() {done : make(chan bool)for i : 0; i 5; i {go func(x int) {sendRPC(x)done - true}(i)}//和waitGroup的效果一样for i : 0; i 5; i {-done}
}func sendRPC(i int) {println(i)
}raft实验易错点
不应该在调用RPC时持有锁。1影响效率2容易死锁。可以通过传递assumption消除
debug技巧
cirt /可以打印堆栈
