Distributed

在这部分中我们要在lab4的基础上更近一步，lab4是只有一组raft服务，lab5就是Multiraft(multi-group)，进一步加入了分片的机制，主要用于解决在大规模分布式系统中高可用、强一致性、可扩展性等问题。 单 Raft Group 的局限性： Raft 是一种用于实现分布式系统一致性的共识算法，通常以一个“Raft Group”（即一组节点共同维护一个日志副本）为单位工作。但在实际应用中，如果整个系统只用一个 Raft Group，有以下缺点： 写性能瓶颈： 所有的写请求必须由 Leader 单节点处理并定序，无法利用集群多节点的并发能力，吞吐量受限于单机资源。 扩展性受限： 增加节点仅能提升容灾能力，无法线性提升写性能，且集群总存储容量被限制在单机磁盘大小。 故障恢复慢与热点问题： 巨大的状态机导致快照生成和日志回放缓慢，故障恢复时间长；且单一 Group 难以进行细粒度的负载均衡，易形成读写热点。 分片 + 多 Raft Group： Multiraft 将整个数据集划分为多个分片（shard），每个分片由一个独立的 Raft Group 负责管理。 每个 Raft Group 只负责一部分数据，互不影响； 写/读请求可以并行处理，提高系统吞吐； 系统可以通过增加分片数量来横向扩展； 故障隔离：某个 Group 出现问题（如网络分区、节点宕机），不会影响其他 Group。 shardctrler 针对5A的实验，主要就是设计一个shardctrler，它的作用是维护集群的配置信息（Configuration），即负责管理“分片（Shard）”到“复制组（Replica Group / GID）”的映射关系，并在集群拓扑变化时自动进行分片的负载均衡（Rebalancing）。 具体来说，它需要通过 Raft 保证高可用和强一致性，并支持以下 4 个核心操作（RPC）： Join (加入新组)： 当新的复制组（Replica Group）加入集群时，Ctrler 需要将部分分片从现有组迁移给新组，以实现负载均衡。 Leave (移出旧组)： 当某个复制组想要离开集群时，Ctrler 需要将其持有的分片重新分配给剩余的组，确保数据不丢失且分布均匀。 Move (手动迁移)： 允许管理员强制将某个特定的分片（Shard）分配给特定的组（GID），主要用于调试或处理热点。 Query (查询配置)： 允许 ShardKV 节点或 Client 查询最新的或历史版本的配置（Config），以便知道读写请求该发往哪里。 它本身一个group，所以基本的接收命令然后提交等操作和之前完全一样，主要就是这四个操作和rebalance，注意rebalance要最少移动原则。 ...

这个部分就是在基于lab3的raft的基础上构建一个容错的、可复制的键值存储服务。其架构图在lab中也已经给出了，根据这个来做就可以了。 Client Client端的实现非常直观，和lab2的实现完全一样。本质上是一个屏蔽了网络故障和Leader切换的RPC重试循环。为了保证系统的线性一致性，每个客户端维护唯一的ClientID和单调递增的CommandID作为请求的唯一标识，每次发新的请求前要先把CommandID + 1，在收到明确的成功响应前，即便多次重试也保持CommandID不变，从而配合Server端进行去重。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 func (ck *Clerk) PutAppend(key string, value string, op string) { // You will have to modify this function. ck.CommandId += 1 args := PutAppendArgs{Key: key, Value: value, ClientId: ck.ClientId, CommandId: ck.CommandId} for { reply := PutAppendReply{} if !ck.servers[ck.LeaderId].Call("KVServer."+op, &args, &reply) || reply.Err != OK { ck.LeaderId = (ck.LeaderId + 1) % len(ck.servers) time.Sleep(retryInterval) continue } break } } Server KVServer 端的设计核心在于“共识层”与“状态机”的解耦协同。 也就是采用了**“异步提交 + 同步等待”**的模式：RPC Handler 收到请求后，调用 Raft 的 Start() 接口将命令写入日志，获得该日志的 index。由于 Raft 的共识过程是异步的，Handler 此时会创建一个通知通道（我在这里用的是waitCh），并以 index 为 Key 注册到等待列表中，随即阻塞等待。 ...

3B感觉要难不少，也需要仔细阅读 手册 所需字段 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 type Raft struct { mu sync.Mutex // Lock to protect shared access to this peer's state peers []*labrpc.ClientEnd // RPC end points of all peers persister *Persister // Object to hold this peer's persisted state me int // this peer's index into peers[] dead int32 // set by Kill() state State // rf当前的状态 heartbeatTimer *time.Timer // 心跳timer electionTimeout *time.Timer // 超时选举 timer currentTerm int //当前的任期 votedFor int // 投票给了哪个节点 logs []LogEntry // 日志 nextIndex []int // 要传给节点的下一个index matchIndex []int // 节点已经匹配的index commitIndex int // 已经提交的index lastApplied int // 已经返回给客户端的index applyCond *sync.Cond applyCh chan ApplyMsg } Append Entry Leader 需要向所有的 Follower 发送日志，我在这里的就是将心跳和发送日志采用了同一个函数，每一次心跳都会调用requestAppendEntries()这个函数，但只有发现peer的日志落后时才会附带日志。为了避免单个网络差的 Follower 阻塞整个集群的日志提交进度， Leader 会为每一个 Peer 启动一个独立的后台协程。一旦发现 Follower 落后（nextIndex <= lastLogIndex），就立即构造 AppendEntries RPC 发送日志。如果不落后，则是一个空的心跳。对于有日志发送的rpc，直到Follower完全跟上Leader日志才会退出。 ...

Key/Value Server实验的实现

Key/Value Server实验的实现

lab1 MapReduce的实现