Hexo

6.824 lab2B思考

Posted on Edited on In
Symbols count in article: 4.2k Reading time ≈ 4 mins.

Raft2B

本文进行有关lab2B的实现思路的梳理

实现目标

image-20250724131832492

lab2B中需要实现的目标相对简洁，但是相对来说麻烦许多。课程描述的任务十分简洁，就是使得当前的代码支持追加日志的RPC操作。但是这个需要费的心力比起2A来说复杂许多…

  • 完善Raft上一个服务器上的状态

​ 为了能够支持日志，我们需要引入一些额外的状态，具体的在Figure2中有描述

  • 进一步完善选举机制

​ 2A中实现的选举机制只是建立在基本的投票共识上，由于没有引入日志属性，所以其中的选举缺乏了一些机制，例如论文5.4中要求 的由日志来保证的选举安全性

  • 实现基本的日志收发机制

​ 日志本身的推送是本次lab中的核心，其需要多个环节的实现以及联调，其中涉及了收集数据，分发数据，上报状态等多个环节需要 处理

  • 进一步优化代码结构

    在此次lab中，我们特别需要注意的一件事，就是一个lab的实现会是后续的lab的基础，后续的lab可能还会涉及到本lab代码的修改，不能使得代码过于难以维护

关于选举部分的处理都需要基于现有的本机上的Log状态，所以，本次我们优先来分析关于基础的AppendEntries需要注意什么

AppendEntries

关于日志推送该操作，个人认为其基本只存在几个简单的状态，如下图

image-20250724133314947

简述一下流程

  • 一个Leader服务器始终处于Acceptor(监听)状态，外部通过**Start()**接口传入其所需要本cluster执行的command
  • Leader收到command之后，需要将本次请求持久化到本地，然后触发AppendEntries，将本次请求广播到本cluster中其他server
  • 当且仅当超过半数cluster中的server都ACK了本次操作时，本个command会被标记为commited
  • 在一个command被标记为commited之后，Leader需要向上层上报本次操作

问题

上述流程描述的很清晰，但是，对应的其中存在很多的实现细节需要注意，本次个人写本文本质上也是为了理清思路

Acceptor

  • 监听到Command到来时需要进行什么动作

​ 一次Command到来时，由于其本身只是一段临时的指令，我们需要将其持久化到本地中。基于论文中的思路，一个Log基本需要具有term和command的属性，因此我们需要一次来进行一些基础的封装等。同时，论文中提到后续可能需要实现snapshot，如果需要，snapshot本身还需要日志的一些属性配合，需要注意一个server中的log[] (Figure2)的实现

  • 需要怎么进行由Acceptor向Deliver的状态转移

​ 成功持久化数据之后，我们需要广播该Log，将其持久化到cluster中的其他服务器中，我们需要考虑该操作的时机以及实现的程度，在论文中，其中说明需要使用AppendEntries这个RPC进行对应的操作。实际设计中，存在一个权衡，就是是否需要与心跳共用该RPC，还是说需要抽离出来独立。这个需要考虑实现该RPC的时机

  • 需要怎么确保一个Log已经被大多数Server给ACK

​ 这个的实现思路很自然，即通过一个总的调度goroutinue来管理该类操作，但是该goroutinue会相对麻烦。就比如，如果在上一条Log还没有被commited时又存在Log被推送进行需要怎么处理等等

  • 需要怎么确保一个commited的操作能够被上层感知

​ 该操作在tip中有提到，而且实际的lab代码中，已存一个chan作为上报的通道。同时，在对应的guide等文件中，提到，推荐使用一个cond来进行本类上报操作的管理

上诉问题肯定并非全部，不过当前已经足够麻烦，先来实现并解决上诉问题，若存在其他问题再来补充

实现思路

对于当前Lab的实现，个人目前存在了一个三板斧。

  • 实现基础的RPC收发操作，即实现论文中的逻辑处理
  • 封装调用逻辑，客户端调用此类RPC需要与应用端进行联调
  • 整合主程序逻辑，将调用逻辑整合到现有的系统中

基础成员

为了能够实现日志的成功复制以及持久化，服务器进程中势必需要储存一些信息来进行标识，其在Figure2中存在详细的介绍

  • commitIndex 标识当前服务器上的已经提交的日志的索引
  • lastApplied 标识当前服务器中已经提交到本地状态机上的最新日志的索引
  • nextIndex[] 标识当前服务器所知的其他服务器上的下一个未被确认的日志的索引
  • matchIndex[] 标识当前服务器已知的其他服务器上的已经确认复制成功的日志的索引
  • log[] 储存当前服务器中留存的日志的信息

分析一下当前的几个成员会在日志复制中扮演的作用

  • 服务器接收到command请求

​ 封装当前command请求为一个有状态的log，依照论文中的说法，一个合法的Log需要存在一个Term标识(Each log entry stores a state machine command along with the term number when the entry was received by the leader),以及一个index信息(Each log entry also has an integer index identifying its position in the log.)。在封装完成之后，Leader需要将其持久化到本地中

  • 服务器发起日志复制请求

    当Leader收到一个新的请求后，其需要将该请求分发到各个Follower中，此阶段涉及到对应的Follower上的信息，依照论文中的说法，我们需要将此前未被改服务器ACK的数据也一并发送出去，因此，该阶段涉及到**nextIndex[]和matchIndex[]**的信息使用(This also commits all preceding entries in the leader’s log, including entries created by previous leaders.)

  • 服务器完成日志复制

    在当前Leader完成将当前日志复制到cluster集群中的大多数服务器中，此时该Log的状态成功转变为了commited的状态,此个状态会涉及到一些新的状态转移，比如，对应的本地的commitIndex等，同时，依照论文所说，Leader本身需要在此时去上报Log已经处理成功。

When the entry has been safely replicated (as described below), the leader applies the entry to its state machine and returns the result of that execution to the client.

RPC参数定义

image-20250725145424880

在本次RPC中，我们只考虑使用为推送日志的情况，并不考虑心跳用途下的RPC参数场景。

  • 日志匹配

​ 本次RPC使用一个偏移索引以及外部约束的定义来判断当前是否存在匹配为止，规则简单如下: 如果一个Follower的Log[]中对应于 prevLogIndex下的Log的Index与prevLogTerm相同，那么视为匹配，否则视为不匹配，具体原因参照论文5.3节定义

  • 数据携带

​ 本次RPC中会一次性携带所有的Leader认为的冲突的日志数据，如果匹配成功，需要将该些日志数据进行拷贝，否则，需要重新匹配

RPC服务器端实现

在论文中，对于AppendEntries的逻辑处理行为进行了一些约束，此处来基于最简单的实现进行一些分析

  • 日志匹配

​ 如上文所说，该RPC的参数中的prevLogIndex和prevLogTerm字段是处理是否匹配的核心，判断逻辑也很简单，上面已经简单讲 过，这里不再赘诉。但是关于不匹配的场景，我们还是需要进行一些探讨。按照论文中所说，当一个日志不匹配时，其需要Leader 在下次发送请求时去继续往前移动一个日志尝试匹配。这种算法是简单但是不一定高效的。在论文中，其中提到了这种匹配算法的优 化，就是在服务器处理端去索引到一个匹配项，然后讲该匹配项的信息返回，减少RPC次数以及对应的网络I/O。但是，请注意，实 际的实现并没有那么简单，这里提供一个可能的思路，以Term为粒度进行匹配的回退

  • 日志复制

​ 日志复制本身逻辑并不复杂，总结出来就是一个操作，找到本机上对应的匹配项，将该匹配项的后续数据全部截断，然后append上 由RPC所传输过来的数据即可

RPC客户端实现

在实际的实现中，该RPC的客户端的实现可以说是这个环节中最麻烦的一个，其涉及的状态很多，需要小心管理

  • 参数构建

    客户端RPC中最基本，同时也最为核心的即为参数的构建。对于本次实现，其中最麻烦的就是关于precLogTerm和prevLogIndex的处理。但是，实际上，由于这俩个只是关于一个Log的属性，所以本质上，我们需要在意的是我们需要如何去找到适配一个Server的Log。

    • Log地位

      本次所需要寻找的Log是当前系统中已知的关于特定的server的最后的匹配日志项。即，若索引x上为双方匹配的最大的索引(索引从1开始就算)，那么x即为我们本次需要找的日志，但x-1索引所对应的日志信息则是实际上我们需要使用的信息。

    • Log定位

      已知，nextIndex[]储存的信息为当前Leader已知的匹配项的索引，故，不难推出，关于上述Log的寻找，需要使用该信息进行定位，具体的，由于nextIndex[peer]储存的是peer上的最新匹配的索引，索引nextIndex[peer]-1自然也就是对应的匹配索引的前一位。但是，在逻辑上，这是对于对端服务器的建模，我们无法取得对端服务器上的信息。此时就需要一个匹配的定义来辅助实现，由于匹配，所以Leader和对应的Follower上的Log信息一致，我们可以直接在当前Leader上去查找对应的信息拿来使用即可

      注意，在实际实现中，一些个人的实现可能会遇到一些与定义存在冲突以及存在一些边界的情况，请依照论文为准

  • 确认提交

    论文中说明，当一条Log被推送到大多数的服务器上后，该日志可以被视为commited，当一个日志成为commited之后，Leader需要将该状态上报给Client。但是实际上，这个实现起来相当复杂，下面只给出几个实现中可能会遇到的问题

    • 如何去确认一个Log已经被commited，特别是在部分Server会失联的情况下(注意:使用一个全局计数器是很困难的)
    • 如何去高效的提交一个Log(tips: lab instruction中有说明)
    • 如何保证提交的并发安全
-------------本文结束 感谢阅读-------------