MIT 6.5840 Raft Implementation(2B, Log Replication)

mit,raft,implementation,2b,log,replication · 浏览次数 : 61

小编点评

**Raft结构体内容** ``` commitIndex: 表示提交日志下标的最高值 lastApplied: 表示已经应用到状态机中的日志下标的最大值 nextIndex: 每个成员下一组指令的下标的最小值 matchIndex: 和领导人达成一致的下标的最大值 ``` **实现细节** **Start()函数** * 增加 `logChange` 和 `lastLogIndex` 属性。 * 开一个 `go` 程来发送信息:`go rf.launchAppendEntries(peerId)`。 * 检查回复信息: * 如果回复成功,则增加 `nextIndex` 和 `matchIndex`。 * 如果回复失败,则减少 `nextIndex[peerId]`。 **appendEntries()函数** * 在 `applyCh` 内实现 RPC 的功能。 * 在轮询中,检查 `nextIndex` 和 `matchIndex` 的值,并根据结果,添加日志条目。 **其他** * `lastLogTerm` 用于记录最后一次日志变更的时间。 * `matchIndex` 用于选择要提交的指令的索引。 * `applyCh` 是一个通道,用于管理对各个成员的命令发送。 * `Rules For All Servers` 是指在任何服务器都必须满足的服务器一致性协议要求。

正文

Raft实现思路+细节(2B)

任务分解

2B中最主要的任务就是进行日志的复制。Raft是一个强领导人的系统,这意味着所有的日志添加都是由领导人发起的,与之相类似的,还有很多其他的结论(它们都是比较显然的),读者可以自行证明。

我们可以这样地分解复制日志的过程

  1. 我们首先需要完善Raft结构体的内容。

     

    我们对新加入的内容进行解释:

    • commitIndex:这代表了每一个Raft中最高的已经提交的日志下标,它表示对于这个下标以内的所有日志,我们都已经和领导达成共识。可以想象,它的更新是在收到RPC的时候完成的,因为如果领导人提交了某一条指令,且某个追随者有这条指令,那么就可以认为是达成共识的了,后续可以进行应用等操作。

    • lastApplied:这是一个紧跟commitIndex的成员,他指代的是每一个Raft中已经应用到状态机中的日志下标的最大值。我们会对每个Raft有一个轮询(至少我是这么实现的),如果lastApplied<commitIndex,那么就把这个区间内的所有指令应用到复制状态机上。

    • nextIndex(对于领导人):这代表的是对于每个成员,下一组要发的指令的下标的最小值,可以想象它代表着领导人和每个成员在哪些日志上达成了一致,它的更新应该是在AppenEntriesRPC中实现的。

    • matchIndex(对于领导人):这代表的是,对于每个成员,和领导人达成一致的下标的最大值(当然,你可以期待一般matchIndex=nextIndex-1)。我们通过它来决定要提交到哪一条指令(也即大部分人matchIndex的下界)。

  2. 经过上层服务器的多次尝试,我们终于在领导人这里加了一条日志:我们需要完成Start()函数,它的参数为一条指令(一个空的interface),返回的是这条指令在领导人这边的日志编号,领导人的任期,和这个人是否是领导人。同时,在Start函数中我们也要显式地向每一个追随者发一条心跳(其实就是AppendEntriesRpc).

  3. 类似于MakeElection函数,我们需要完成launchAppendEnries()这一函数,并处理回复信息。

  4. 我们需要完成AppendEntries()函数,在里面完成RPCHandler的功能。

  5. 我们需要完成上文中提到的轮询,对每一个Raft开一个Go程来检查要不要提交某一些指令,如果是的话,那就加到applyCh内(这个applyCh也需要自己完成)。

实现细节

  1. Start中,我们需要:

    • 增加log

    • 改变lastLogIndex, lastLogTerm

    • 开Go程来发送信息:go rf.launchAppendEntries(peerId)

  2. 我们首先需要发送AppendEntriesArgs,然后需要考虑AppendEntriesReply,具体来说:

    • 需要遵循Rules For All Servers,如果自己的任期变大,不需要处理;如果Reply的任期更高,变成追随者......(建议参考raft-extended)

    • 如果回复显示成功,那么把nextIndex, matchIndex都增加,并考察commitIndex是否也可以增加(看看是不是有一半的matchIndex)都超过了某一个值

    • 如果回复显示失败,我们就把nextIndex[peerId]减少一,来向下匹配。(在后文中我们会看到对于这一点的明显优化)

  3. 这是2B中的核心内容,我们在这里考察论文中的图示:

     

  4. 这个比较简单,只要知道“信道”是啥基本就可以了。

注意事项

  • 在上面这张图中,Reply false的意思是直接返回

  • 这里第三条的conflicts with的实现需要细细思考。如果接收者的日志中的每一条都是正确的,那么不需要截断(我到2C才发现这个)

  • 对于Rules For All Server而言,如果变成Follower,不需要返回。这一点上的处理是和2A一致的。

关于评测

 

 

与MIT 6.5840 Raft Implementation(2B, Log Replication)相似的内容:

MIT 6.5840 Raft Implementation(2B, Log Replication)

Raft实现思路+细节(2B) 任务分解 2B中最主要的任务就是进行日志的复制。Raft是一个强领导人的系统,这意味着所有的日志添加都是由领导人发起的,与之相类似的,还有很多其他的结论(它们都是比较显然的),读者可以自行证明。 我们可以这样地分解复制日志的过程 我们首先需要完善Raft结构体的内容。

MIT 6.5840 Raft Implementation(2A, Leader Election)

2022-2023-3 PPCA Raft项目的记录(1)

Raft-2023的一些笔记(SJTU-ACM-PPCA & MIT 6.5840)

大概是处于边读边翻译的状态。可以有挺多理解不符合实际情况,接下来读/写的过程中会尽量修正

wpfui:一个开源免费具有现代化设计趋势的WPF控件库

wpfui介绍 wpfui是一款开源免费(MIT协议)具有现代化设计趋势的WPF界面库。wpfui为wpf的界面开发提供了流畅的体验,提供了一个简单的方法,让使用WPF编写的应用程序跟上现代设计趋势。截止写这篇文章,该项目获得了6.7k starts。 最近我也在使用wpfui,整体使用下来感觉非常

[转帖]开源软件项目中BSD、MIT许可证合规问题探析

https://www.allbrightlaw.com/CN/10475/3be2369275d19e9e.aspx [摘要]本文将探析BSD开源许可证(Berkeley Software Distribution License)和MIT开源许可证这两类“元老级”的宽松型开源许可协议(Permi

WatchDog:一款.NET开源的实时应用监控系统

项目介绍 WatchDog是一个开源(MIT License)、免费、针对ASP.Net Core Web应用程序和API的实时应用监控系统。开发者可以实时记录和查看他们的应用程序中的消息、事件、HTTP请求和响应,以及运行时捕获的异常。 项目工作原理 它利用SignalR进行实时监控,并使用Lit

5款.NET开源、免费、功能强大的图表库

LiveCharts2 LiveCharts2是一个.NET开源(MIT License)、简单、灵活、交互式且功能强大的.NET图表、地图和仪表,现在几乎可以在任何地方运行如:Maui、Uno Platform、Blazor-wasm、WPF、WinForms、Xamarin、Avalonia、W

一款开源、免费、现代化风格的WPF UI控件库 - ModernWpf

前言 今天大姚给大家分享一款开源(MIT License)、免费、现代化风格的WPF UI控件库:ModernWpf。 项目介绍 ModernWpf是一个开源项目,它为 WPF 提供了一组现代化的控件和主题,使开发人员能够创建具有现代外观的桌面应用程序。 项目特点 可以轻松自定义的浅色和深色主题。

一款.NET开源、功能强大、跨平台的绘图库 - OxyPlot

前言 今天大姚给大家分享一款.NET开源(MIT License)、免费、跨平台、功能强大的绘图库,支持多平台使用(包括:WPF、UWP、WinForm、Silverlight、Xamarin.iOS、Xamarin.Android、Xamarin.Forms 和 Xamarin.Mac等):Oxy

一款.NET开源、免费、实用的多功能原神工具箱(改善桌面端玩家的游戏体验)

前言 今天大姚给大家分享一款.NET开源(MIT License)、免费、实用的多功能原神工具箱,旨在改善桌面端玩家的游戏体验:胡桃工具箱。 工具箱介绍 胡桃工具箱是一款.NET开源(MIT License)、免费、实用的多功能原神工具箱,专为现代化 Windows 平台设计,旨在改善桌面端玩家的游