6.824

lab1

这是 MIT 6.824 课程中的第一个实验任务，要求你实现一个分布式的 MapReduce 系统。这个实验的目标是让你理解分布式系统中的一些关键概念，如任务分配、容错处理以及进程间通信。

实验概述

你将要实现一个由协调器（Coordinator）和工作者（Worker）组成的 MapReduce 系统：

协调器负责向工作者分配任务，并处理因工作者失败而引起的任务重试。
工作者将从协调器获取任务，执行 Map 或 Reduce 操作，并生成输出文件。

实验步骤

设置实验环境

克隆实验代码库：

git clone git://g.csail.mit.edu/6.824-golabs-2021 6.824
cd 6.824

进入 src/main 目录，编译并运行给定的 mrsequential.go 文件，这是一个单进程的 MapReduce 实现：

cd src/main
go build -race -buildmode=plugin ../mrapps/wc.go
rm mr-out*
go run -race mrsequential.go wc.so pg*.txt

实现分布式 MapReduce 系统
- 你需要在 mr/coordinator.go、mr/worker.go 和 mr/rpc.go 中实现分布式 MapReduce 系统的核心逻辑。
- 工作者应该从协调器获取任务，执行任务，并将结果存储在合适的输出文件中。协调器需要监控工作者的状态，并在工作者失败时重新分配任务。
测试你的实现
- 编译 mrapps/wc.go：
```
go build -race -buildmode=plugin ../mrapps/wc.go
```
- 启动协调器：
```
go run -race mrcoordinator.go pg-*.txt
```
- 在另一个终端中启动一个或多个工作者：
```
go run -race mrworker.go wc.so
```
- 运行测试脚本 test-mr.sh，以验证你的实现是否正确：
```
bash test-mr.sh
```

关键实现细节

协调器：
- 协调器负责追踪 Map 和 Reduce 任务的状态。
- 当一个工作者请求任务时，协调器需要分配一个尚未开始或已超时的任务。
- 协调器还需要检测工作者是否在合理的时间内完成任务，若没有完成，则将任务分配给其他工作者。
工作者：
- 工作者通过 RPC 请求任务。
- 执行任务后，将结果写入中间文件（Map 任务）或输出文件（Reduce 任务）。
- 通过 RPC 向协调器报告任务完成情况。
中间文件和输出文件：
- 中间文件命名格式为 mr-X-Y，其中 X 表示 Map 任务编号，Y 表示 Reduce 任务编号。
- 最终的 Reduce 任务输出文件格式为 mr-out-X，其中 X 表示 Reduce 任务编号。
并发与容错：
- Go 的 sync 包可以帮助你处理并发问题，特别是在协调器中。
- 你需要实现一种机制，确保当工作者失败时，协调器能够重新分配任务。

提示与建议

从简单的任务分配开始，逐步添加错误处理和并发控制。
使用 Go 的 race detector (-race 选项) 来检测并发问题。
使用 json 包来序列化和反序列化中间数据。

提交与检查

在完成实验后，确保所有测试都通过，然后你可以将实验提交给课程系统。

这个实验不仅要求你理解并实现一个分布式系统，还会帮助你掌握如何在分布式环境中处理容错、并发等挑战性问题。祝你实验顺利！如果有任何问题，随时向我提问。

lab2

命令是上层服务lab3/lab4 使用raft时传递的，会在日志中存储

目标

这个实验非常详细，涉及到在多个阶段实现 Raft 共识算法。以下是你可以处理每个部分的简要概述：

第2A部分：领导选举

目标： 实现 Raft 的领导选举和心跳机制。
步骤：
1. 修改 Raft 结构体，添加与选举相关的状态（例如，任期、投票计数）。
2. 实现 RequestVote RPC 处理程序，使候选人可以请求其他节点的投票。
3. 设置定期触发选举的机制，例如在没有接收到领导者心跳信号时触发。
4. 实现 AppendEntries RPC，领导者可以周期性地发送心跳信号，以防止其他节点发起选举。

第2B部分：日志复制

目标： 实现领导者和跟随者之间的日志追加机制，以通过测试。
步骤：
1. 实现 Start 函数，使得新的日志条目可以通过领导者追加到日志中。
2. 编写代码通过 AppendEntries RPC 发送和接收新的日志条目。
3. 确保当某些跟随者的日志与领导者不一致时，领导者能够正确地回滚并同步日志。

第2C部分：持久化

目标： 确保 Raft 在服务器重启后能够恢复之前的状态。
保存的分为raft元数据和快照
步骤：
1. 完成 persist 和 readPersist 函数，实现将 Raft 的状态保存到 Persister 对象中，并在重启时恢复状态。
2. 在每次状态更改时调用 persist 保存持久化状态。
3. readPersist，是在raft启动时读取，
4. 在 AppendEntries 中实现快速回滚以提高同步效率。

第2D部分：日志压缩

目标： 实现日志压缩机制，以便长时间运行的服务可以定期丢弃旧的日志条目。
压缩可以理解为主节点将已提交的旧日志转换为快照，从节点则根据主节点提供的快照来同步数据。
- 主节点会主动进行日志压缩。
- 从节点不会主动进行压缩，但会通过接收主节点的快照来实现类似压缩的效果。主节点执行日志压缩后，如果从节点需要通过快照才能追上主节点的状态，那么主节点会发送当前的快照到从节点，否则会继续通过日志复制的方式保持同步。
步骤：
1. 实现 Snapshot 接口，服务端可以通过它通知 Raft 当前的状态快照。
2. 实现 CondInstallSnapshot，当接收到新的快照时判断是否需要更新。
3. 实现 InstallSnapshot RPC，用于在从节点落后较多时，领导者发送快照以帮助其快速同步状态。
4. 修改 Raft 的日志管理，使得在存储状态快照后，能够丢弃不需要的日志条目。
5. 在实验2D中，测试人员定期调用 Snapshot() ,服务层在每个对等体上调用 Snapshot() （而不仅仅是在领导者上）。
6. 但是，现在可能会有一个follower远远落在后面，以至于leader已经丢弃了它需要赶上的日志条目; leader必须发送一个快照以及从快照开始的日志 7.

快照----主节点日志压缩/从节点落后追赶/崩溃后恢复，持久化----节点56重启时恢复状态

从节点落后追赶：

网络问题
崩溃可能先持久化恢复，又被主节点快照覆盖追赶

实例代码建议

这段“Raft Structure Advice” 提供了关于如何组织 Raft 实例代码的建议，特别是如何处理外部事件和定期任务。以下是主要要点的中文解释：

共享数据与锁：每个 Raft 实例都有一堆状态（如日志、当前索引等），这些状态必须在并发 goroutine 中更新。虽然可以使用消息通道来管理状态更新，但经验表明，使用共享数据和锁更为直接和简单。
时间驱动的活动：Raft 实例有两个基于时间的活动：
- Leader 发送心跳信号。
- 其他节点在超过选举超时时间未收到心跳时发起选举。
建议为每个活动单独创建一个长时间运行的 goroutine，而不是将多个活动合并到一个 goroutine 中。
选举超时管理：选举超时的管理是一个常见的难题。最简单的方案是维护一个变量，记录上次从 Leader 接收到信息的时间。选举超时的 goroutine 定期检查当前时间是否超过了超时时间。最好使用 time.Sleep() 来驱动定期检查，而不是使用 time.Ticker 和 time.Timer，后者使用起来较为复杂。
处理已提交日志条目：应创建一个单独的长时间运行的 goroutine，将已提交的日志条目按顺序发送到 applyCh。这个 goroutine 应该是单独的，因为发送到 applyCh 可能会阻塞；此外，这应该是一个单独的 goroutine，以确保日志条目按顺序发送。更新 commitIndex 的代码需要触发 apply goroutine，最简单的方法是使用条件变量（Go 的 sync.Cond）来处理。
RPC 的处理：每个 RPC 应该在其自己的 goroutine 中发送及处理回复，有两个原因：
- 这样无法访问的节点不会延迟收集多数回复。
- 这样心跳和选举计时器可以始终正常工作。
最好在同一个 goroutine 中处理 RPC 回复，而不是通过通道传递回复信息。
网络延迟与 RPC 乱序：需要注意网络可能会延迟 RPC 和 RPC 回复，并且在发送并发 RPC 时，网络可能会重新排序请求和回复。Leader 在处理 RPC 回复时要格外小心，必须检查在发送 RPC 之后任期是否发生变化，并考虑到来自同一 Follower 的并发 RPC 回复可能会改变 Leader 的状态（例如 nextIndex）。

这些建议有助于在设计和实现 Raft 协议时更好地管理并发和异步操作。

日志压缩

日志压缩对于防止 Raft 日志无限增长至关重要，否则这可能最终会耗尽存储资源并减慢系统的运行速度。日志压缩的核心思想是定期创建应用程序状态的快照，从而允许丢弃已经包含在快照中的旧日志条目。

快照与日志索引的对应关系：在创建快照时，需要确保应用程序的状态与 Raft 日志中的某个已知索引相对应。这意味着应用程序需要向 Raft 通知快照对应的日志索引，或者 Raft 需要延迟应用新的日志条目，直到快照完成。
恢复协议：当服务器崩溃并重新启动时，如果使用了快照，就需要特别注意恢复过程。如果 Raft 状态和快照是分别持久化的，服务器可能会在持久化快照和更新 Raft 状态之间崩溃。这会导致问题，因为根据图 13 的第 7 步，快照所覆盖的日志必须被丢弃。

例如，如果服务器重启时读取了更新后的快照，但日志仍然是旧的，它可能会重新应用一些已经包含在快照中的日志条目。

解决方案是引入一个持久化的状态记录，标记 Raft 持久化日志中第一个条目对应的“真实”索引。这样可以将其与加载的快照的 lastIncludedIndex 进行比较，以确定应丢弃日志开头的哪些元素。

快照会整个替换应用的状态，应用快照需要截取日志到快照包含的最新日志注意：快照是上层应用发给raft的

加速日志回溯优化

加速日志回溯是一种优化，虽然在大多数部署中可能不是必需的，但在某些情况下非常有用。这一优化在原文中描述得较为简略，可能是因为作者认为它对于大多数部署来说并不必要。具体来说，在文本中没有明确说明从客户端发送回来的冲突索引和任期应该如何被领导者用于确定下一个 nextIndex。

我们认为，作者可能希望你遵循的协议是：

prevLogIndex 不存在：如果跟随者的日志中没有 prevLogIndex，那么它应该返回 conflictIndex = len(log)，并且 conflictTerm = None。

即领导者发送到该对等体的上一条日志不存在或者说日志较少，领导者重发该对等体的最新日志的下一条
prevLogIndex 存在但任期不匹配：如果跟随者的日志中存在 prevLogIndex，但任期不匹配，那么它应该返回 conflictTerm = log[prevLogIndex].Term，然后在其日志中搜索第一个任期等于 conflictTerm 的条目的索引。

例如任期大，
领导者处理冲突响应：领导者收到冲突响应后，应该首先在其日志中搜索 conflictTerm。

如果找到具有该任期的条目，它应该将 nextIndex 设置为日志中最后一个该任期条目之后的索引。

如果没有找到具有该任期的条目，则应将 nextIndex 设置为 conflictIndex。

一种简化的解决方案是只使用 conflictIndex（忽略 conflictTerm），这简化了实现，但有时会导致领导者向跟随者发送比严格必要的更多的日志条目，以使它们同步。

锁建议

这段“Raft Locking Advice” 是关于如何在 6.824 课程的 Raft 实验中使用锁的建议，帮助开发者正确处理并发问题，防止数据竞争和死锁。以下是主要规则的中文解释：

规则 1：多线程访问共享数据时使用锁

当多个 goroutine 访问同一个数据时，如果至少有一个 goroutine 会修改该数据，必须使用锁来防止同时访问导致的数据竞争。Go 的竞态检测工具非常适合检测违反此规则的情况。

规则 2：在执行一系列共享数据的修改时使用锁

如果代码执行了一系列对共享数据的修改，而其他 goroutine 如果在修改过程中访问这些数据可能会产生错误，应该在整个修改序列上使用锁。例如：

rf.mu.Lock()
rf.currentTerm += 1
rf.state = Candidate
rf.mu.Unlock()

在这个例子中，必须在整个修改过程中持有锁，以防止其他 goroutine 看到不一致的数据。

规则 3：在一系列读取操作中使用锁

如果代码执行了一系列对共享数据的读取操作（或读写混合），而如果在中途另一个 goroutine 修改了数据会导致错误，应该在整个操作序列上使用锁。例如：

rf.mu.Lock()
if args.Term > rf.currentTerm {
   rf.currentTerm = args.Term
}
rf.mu.Unlock()

需要在整个操作序列上持有锁，防止出现竞态条件。

规则 4：避免在持有锁的情况下等待

在持有锁的情况下，不要进行可能会等待的操作，如读取 Go channel、发送 channel、等待计时器、调用 time.Sleep() 或发送 RPC 并等待回复。这样做可能会阻止其他 goroutine 的进展，还可能导致死锁。应在等待之前释放锁。

规则 5：重新获取锁后重新检查假设条件

在释放锁并重新获取锁之后，必须小心之前的假设条件可能已经发生变化。一个典型的错误是，启动 goroutine 后，继续在未加锁的情况下访问共享数据。例如：

rf.mu.Lock()
rf.currentTerm += 1
rf.state = Candidate
for <each peer> {
    go func() {
        rf.mu.Lock()
        args.Term = rf.currentTerm
        rf.mu.Unlock()
        Call("Raft.RequestVote", &args, ...)
    } ()
}
rf.mu.Unlock()

这个代码可能是错误的，因为在创建 goroutine 和读取 rf.currentTerm 之间，时间可能已经过去很长，可能多个任期已经变化。因此，在外部代码持有锁时，需要使用 rf.currentTerm 的副本。

总结

这段建议还包括了一些编写和分析并发代码的方法，尤其是如何识别需要加锁的代码片段。

建议一种较为实用的策略是，从没有锁的代码开始，逐步识别和添加必要的锁，同时在可能的等待操作之前释放锁。

日志工具

go test -race
go test --race -run TestSnapshotInstallCrash2D


#dtest
./dtest -p 10 -n 10 --output ./logs --verbose  --race
./dtest -p 1 -n 100 --output ./logs --verbose  --race TestSnapshotInstallCrash2D

tests: 要运行的测试列表。
--sequential/-s: 顺序运行每组测试。
--workers/-p: 并行任务的数量。
--iter/-n: 运行的迭代次数。
--output/-o: 输出路径。
--verbose/-v: 详细级别。
--archive/-a: 保存所有日志，而不仅仅是失败的日志。
--race/-r/-R: 是否使用竞争条件检查器。
--loop/-l: 是否持续运行。
--growth/-g: 使用 --loop 时，迭代次数的增长比例。
--timing/-t: 是否报告时间（仅在 macOS 上有效）。

#dslog  
#1.文件
python3  ./dslog -c 5  logs/1

#2.
VERBOSE=1 go test -run TestSnapshotInstallCrash2D | ./dslog -c 5 >logs/debug.log -i LEAD,CLNT,TIMR

file: 指定要读取的文件，如果没有提供则从标准输入读取。
colorize: 是否启用彩色输出，默认启用。
n_columns/c: 设置输出的列数，如果未指定则默认单列输出。
ignore/i: 指定要忽略的日志主题。
just: 指定只显示的日志主题。

lab3

每个键/值服务器（kvserver）都与一个Raft节点关联，一个Join等操作是由client客户端发起，在主节点对应的k-v server服务端开始，经过所有节点组成的的raft层达成一致和持久化，最后回到所有k-v server服务端执行

使用请求序列号seqNo 来保证没有重复请求或者超过最新的请求

两类通道

一个是raft的applyMsg通道，由上层创建传给raft
一个是通知Join等操作完成通道，

该实验要求实现一个容错的键/值存储服务，利用之前在Lab 2中实现的Raft库来进行数据复制。具体来说，服务由多个键/值服务器（kvservers）组成，使用Raft协议确保数据的一致性。即使部分服务器出现故障或网络分区，只要大多数服务器仍然可以通信，服务就可以继续处理客户端请求。

主要目标是实现线性化的键/值存储操作。线性化意味着如果客户端按顺序调用Put(key, value)、Append(key, arg)、Get(key)等操作，系统表现得就像只有一个服务器依次处理请求，并且并发操作的结果与某个顺序执行的结果一致。

Part A：不带快照的键/值服务

在这一部分，你需要实现一个基础的键/值存储服务，每个服务器都有一个Raft节点。核心的任务是确保键/值操作通过Raft协议进行复制，所有服务器保持相同的键/值状态。

主要步骤：

客户端与Raft领导者交互：
- 客户端通过Clerk与Raft集群的领导者通信，发送Put、Append、Get等操作。
- 当Clerk无法确定Raft的领导者时，它应自动重试并找到新的领导者。
- Put(key, value)：将某个键的值替换为指定值。
  
  Append(key, arg)：向键的现有值追加一个字符串参数。
  
  Get(key)：获取键对应的值。
操作的Raft日志复制：
- 每个键/值服务器（kvserver）都与一个Raft节点关联。服务器接收来自客户端的请求后，会通过Raft日志复制该操作。
- Raft日志确保所有服务器保持相同的顺序执行客户端操作，最终一致。
线性化执行：
- 线性化是指所有客户端操作的执行结果与这些操作依次在单一副本上执行的结果相同。即使客户端之间的操作是并发的，系统也必须表现得像是按某种顺序执行这些操作。
- 例如，如果客户端A执行了Put("x", "1")，并且完成操作后客户端B执行Get("x")，那么客户端B必须能看到值"1"。
处理失败和重试：
- Clerk在发送RPC请求时，可能会遇到某个Raft领导者失效的情况。在这种情况下，Clerk应重试该操作并发送请求给其他kvservers，直到找到新的领导者。
- 你需要确保每个客户端请求只被执行一次，即使由于重试而多次发送了相同的请求。
防止重复执行：
- 系统需要处理并发请求，确保操作不会被多次执行或乱序执行。
- 你需要设计数据结构来防止同一请求被多次执行，并且每个客户端的操作必须有唯一标识，方便服务器检测重复请求。

实现提示：

Clerk和Server的RPC处理：
- Clerk通过RPC与服务器通信，你需要在kvraft/client.go中为Clerk实现RPC调用逻辑（Put、Append、Get）。
- 服务器端需要在kvraft/server.go中实现RPC处理逻辑，将请求提交给Raft并等待结果返回。
Raft日志与操作提交：
- 服务器会将客户端的操作（Put、Append、Get）封装成一个Op对象，并通过Raft的Start()方法提交到日志中。
- 当Raft成功达成一致时，服务器会通过applyCh通道接收到提交的日志条目，并应用到本地的键/值数据库中。
测试：
- 你需要通过一系列的测试，确保你的系统能正确地处理一个或多个客户端的请求。
- 测试会检查在不同情况下（如网络不可靠、服务器崩溃等），系统是否仍能正确地保持一致性并执行操作。

Part B：带快照的键/值服务

通过快照机制减少Raft日志的存储空间和重启时的恢复时间。Raft日志不再存储所有历史操作，服务器可以在日志达到一定大小后，通过快照保存当前状态，并丢弃旧的日志。
要确保即使快照存储时系统状态恢复，操作仍然不会重复执行。

在完成Part A后，系统的Raft日志会不断增长，重启时需要重新回放完整的日志来恢复状态，这会变得非常低效。Part B的任务是通过快照（snapshot）机制减少Raft日志的大小，加快系统恢复速度。

主要步骤：

Raft状态的快照：
- 当Raft的日志大小超过指定阈值时，服务器需要生成快照并将其持久化到磁盘。
- 快照可以保存当前的键/值数据库状态，并清除旧的Raft日志条目，减小持久化存储的大小。

快照数据是：
e.Encode(kv.data)
e.Encode(kv.seqNo)

你需要修改kvserver代码，使其在检测到Raft日志超过阈值时生成快照，并通过Raft的Snapshot()方法将快照保存到持久化存储中。
同时，服务器在启动时应从快照中读取已保存的状态。

服务器恢复时读取快照：
- 当服务器重启时，它应首先从快照中恢复键/值数据库的状态，而不是从Raft日志开始重放。
- 跨快照的重复操作检测：
  - 因为在生成快照时可能还有未完成的日志条目，服务器需要确保对这些未完成操作的处理是线性化的，避免重复执行。
Raft日志的截断：
- 当生成快照后，Raft可以安全地丢弃日志中已包含在快照中的条目，从而减少存储开销。
- 你需要修改服务器的逻辑，使其能够在日志大小超过阈值时自动生成快照。

线性化保证如何实现

线性化（Linearizability）是一种强一致性的保证，它要求系统中的所有操作看起来像是按某个全序顺序一次性执行的，并且该顺序符合现实中的时间顺序（即，操作在某个时间点执行后，任何在这之后的操作应该可以观察到该操作的结果）。

要求数据的线性化一致性或强一致性，通常是通过领导者来完成的。

在分布式键/值存储系统中，线性化保证意味着每个客户端的读写操作看起来是按照某个线性顺序执行的，并且这个顺序符合操作实际的发生顺序。换句话说，尽管系统中有多个副本和并发请求，客户端会感受到系统是按某个线性顺序执行的。

实现线性化的关键点

为了实现线性化，Raft协议作为分布式一致性协议在多个副本间达成一致，通过以下几种方式确保线性化：

通过Raft日志复制实现一致性
- 日志复制：Raft协议的核心是通过日志复制来保持多个节点的一致性。Raft中的每个客户端操作（如Put、Append、Get）都被作为日志条目复制到所有节点中，只有在多数节点都同意该日志条目后，操作才被认为是“提交”的。
- 领导者（Leader）选举：在Raft中，只有领导者节点可以处理客户端的写请求。领导者将每个客户端的操作写入自己的日志并尝试将其复制给其他副本节点。线性化得以实现的原因在于，每次只能有一个领导者，并且领导者确保操作在日志中的顺序保持一致。
将操作封装为状态机命令
- 在分布式系统中，每个客户端的操作都会被封装成一个状态机命令，这些命令通过Raft日志复制机制传递给各个服务器的状态机。因为这些命令被按相同顺序复制和执行，所有服务器的状态机都保持一致。
- 线性化执行：当某个操作成功提交到Raft日志后，系统确保所有服务器都会按相同的顺序执行该操作，并且客户端在读取时能够看到所有已提交的操作结果。
处理并发客户端请求
- 多个客户端可能会并发地向集群发送写入和读取请求。在这种情况下，Raft通过以下机制来确保线性化：
  1. 顺序一致性：领导者会按照收到客户端请求的顺序将这些请求作为日志条目加入Raft日志。因为领导者是唯一能够处理写操作的节点，所以它能够决定操作的全局顺序。
  2. 提交机制：只有当日志条目被多数节点（即集群中的大多数副本）确认时，该条目才被认为是“已提交”。客户端只有在操作被提交后，才能收到操作成功的响应。这个提交机制确保所有的客户端看到的都是已提交的操作，未提交的操作对客户端不可见。
处理读取请求
- 线性化的读取：在实现中，读取操作（如Get）通常是从领导者节点获取最新的状态。但为了确保读取操作是线性化的，必须确保领导者在响应读取请求时，已经应用了所有的写入操作。因此，领导者需要等待所有先前的写操作都被提交后，才能返回读取结果。
  - 例如，当领导者接收到Get请求时，它需要检查是否有尚未提交的日志条目。如果有，领导者需要等待这些日志条目提交后，再返回结果，从而保证读取请求的结果反映的是最新的状态。
防止重复操作
- 在分布式系统中，由于网络超时或其他原因，客户端可能会重试同一个操作，导致同一个操作被多次提交。为了确保每个操作只执行一次，系统需要为每个客户端的每个请求分配一个唯一的标识符（如Clerk的ClientId和RequestId）。
- 每个服务器会跟踪它处理过的每个客户端的最新请求，如果它检测到某个请求是重复的，它会直接返回之前的结果，而不会重新执行该操作。
处理领导者失效
- 在Raft中，领导者失效后，其他节点会进行新一轮的领导者选举，选出新的领导者。新的领导者从之前的领导者那里继承日志条目，并继续处理客户端请求。
- 为了确保线性化，在新的领导者选举出来之前，系统会暂停处理客户端请求。因为客户端只能与领导者进行通信，这意味着在领导者失效期间，客户端的写入请求会被阻塞，直到选出新的领导者并确保日志条目的一致性后再处理。

示例

假设有一个分布式键/值存储系统，存在三个节点A、B、C，其中节点A是Raft的领导者。

客户端1请求Put操作：
- 客户端1向节点A发送一个Put("key1", "value1")操作。
- 节点A将该操作记录到它的日志中，并开始将日志条目复制到节点B和C。
- 一旦该日志条目被大多数节点（A和B）确认，节点A会将该操作标记为已提交，并将结果返回给客户端1。
客户端2请求Get操作：
- 在客户端1的Put操作提交后，客户端2发送Get("key1")操作。
- 节点A会检查它的日志，确保所有写入操作都已提交，然后读取键key1的最新值并返回给客户端2。此时，客户端2将会获得"value1"作为返回值。

即使客户端1和客户端2的操作是并发的，系统依然能保证客户端2在看到客户端1的Put操作的结果后才执行它的Get操作，这就是线性化的体现。

总结

线性化通过以下方式实现：

Raft日志复制确保所有操作按照全局顺序执行。
领导者选举和提交机制确保操作被提交后才对外可见。
并发处理通过Clerk的重试机制和请求唯一标识符确保每个操作只执行一次。
防止未提交操作影响读取请求，领导者需要等待所有日志条目提交后再执行读取。

通过这些机制，系统能在面对网络分区、服务器故障等问题时，依然保证操作是线性化的。

读操作一定是在领导者上完成的吗

读取操作不一定必须由领导者处理，但如果要求数据的线性化一致性或强一致性，通常是通过领导者来完成的。
在某些优化场景下，可以通过跟随者处理读取操作，但需要通过特殊机制（如 Raft 的 ReadIndex 或租约机制）来确保一致性。
如果系统对一致性要求较低（如最终一致性），则读取操作可以通过跟随者来完成，减少领导者的负担并提高系统性能。

1. Raft

在 Raft 一致性算法中，客户端的读取操作不一定需要由领导者执行，但如果希望确保读取到最新、最一致的数据，则通常需要通过领导者来完成。

读取操作的两种方式：

通过领导者处理读取（Leader-based Read）：
- 在 Raft 中，领导者负责处理所有写操作（例如日志复制、状态更新等）。为了确保读取的结果是最新的、符合线性化一致性，最简单的方式是让客户端的读取请求通过领导者。
- 领导者可以保证读取到的状态是最新的，因为它是唯一能够接收并提交新的写操作的节点。
- 这样可以避免读取到未提交的或过时的数据。
通过跟随者处理读取（Follower-based Read）：
- 在某些优化场景下，客户端的读取操作可以直接由跟随者（Follower）节点来处理，以减少领导者的负载并提高系统的读取吞吐量。
- 但这种读取操作可能存在不一致性问题，因为跟随者的数据状态可能落后于领导者的最新状态。
- 为了确保从跟随者读取的数据也是线性化一致的，Raft 引入了所谓的 "lease read" 或 "read index" 机制。具体来说，领导者可以向跟随者提供一个读租约（lease），在租约有效期内，跟随者可以安全地响应客户端的读取请求，因为在此期间内不会有新的领导者被选举，跟随者的数据不会落后于领导者。
- 此外，Raft 还支持使用 ReadIndex 机制来确保从跟随者读取时依然满足线性化一致性。ReadIndex 机制通过领导者告知跟随者当前日志的提交索引，跟随者在处理读取请求时会等待日志到达这个提交索引，以确保读取到的是最新的已提交状态。

领导者读取 vs 跟随者读取的权衡：

领导者读取：更简单，保证强一致性，但领导者负载较大，影响吞吐量。
跟随者读取：可以提升读取性能，减轻领导者压力，但需要复杂的机制来确保读取的一致性。

2. Paxos 和 Multi-Paxos

类似于 Raft，Paxos 和 Multi-Paxos 也采用领导者来处理写操作。

领导者读取：Paxos 协议中，写操作由领导者发起，所有变更需要经过多数派节点（quorum）同意。因此，读取操作如果由领导者处理，通常可以直接返回最新的状态，并保持一致性。
跟随者读取：由于 Paxos 允许节点之间存在滞后，读取操作在跟随者上可能无法保证一致性。为此，Multi-Paxos 可以允许类似 Raft 的 "lease read" 机制，让跟随者也能够处理读取请求，前提是保证其数据不落后于领导者。

3. 在读写分离场景下

某些分布式数据库或系统采用读写分离架构，即写操作通过领导者处理，而读取操作通过跟随者节点处理。为了平衡性能和一致性，系统可能会采用以下几种一致性模型：

最终一致性（Eventual Consistency）：允许从跟随者读取操作，不需要立即得到最新的数据，但系统最终会达到一致性状态。比如在很多分布式存储系统中，为了提高读取的吞吐量，客户端读取操作可以直接从副本节点（Follower）上读取，但不保证读取到的是最新状态。
强一致性（Strong Consistency）：在这种模型下，客户端必须从领导者读取数据，或至少从保证最新状态的节点读取数据。
线性化一致性（Linearizability）：要求读取操作在读取最新的写操作之后执行，通常需要通过领导者来完成。如果允许从跟随者读取，则需要保证跟随者的状态与领导者一致。

4. 领导者读取的必要性

在一些严格的强一致性模型中（如线性化一致性），如果不采用额外的机制（如 read index），从跟随者读取可能会导致读取到过时的数据。因此，很多系统为了保证读取到最新的写入，倾向于让读取请求通过领导者处理。

但这并不意味着读取操作一定必须由领导者完成。通过一些优化手段，可以让跟随者处理部分读取请求，并仍然保持数据一致性。这样可以实现更高的读性能，同时不损害系统的线性化一致性。

跨快照的重复操作检测

在分布式系统中，为了保证线性化一致性和正确性，服务器需要能够处理跨快照的重复操作检测。即使部分操作已经被快照保存，而另一部分操作还存在于日志中，系统仍然需要正确处理这些重复的客户端请求。

背景

在分布式系统中，为了优化存储和提升性能，日志条目会周期性地被快照（snapshot）化，即将当前系统状态保存为一个快照，并删除已经应用到快照的日志条目。这种机制能够减少存储和日志回放的开销。然而，这带来了一个新的挑战：如何确保跨快照的重复请求能够被正确检测和处理。

例如，假设某个客户端发送了一系列请求，其中一些请求已经被应用到系统状态并被保存为快照，另一些请求仍然存在于日志中。如果客户端重新发送了之前的请求，系统需要检测到这些请求已经被处理，而不能重新执行它们。

跨快照的重复操作检测

为了解决跨快照的重复操作检测问题，可以采取以下机制：

保存客户端请求的元数据
- 请求唯一标识符（ClientId + RequestId）：每个客户端请求应带有唯一的标识符，通常由客户端ID (ClientId) 和请求ID (RequestId) 组成。系统通过检查这些标识符来判断请求是否已经处理过。
- 请求状态的持久化：服务器需要为每个客户端保存其最近的请求ID以及该请求的处理结果。这可以存储在内存中，但为了处理跨快照的情况，这些信息还需要持久化在快照中，以确保快照后仍能检测到已处理过的请求。
  - 当服务器创建快照时，系统不仅要保存当前的应用状态（如键值对），还需要将每个客户端的最新请求状态一起保存到快照中。
  - 在恢复快照时，系统会重新加载这些客户端的请求状态，确保可以继续检测已处理的请求。
日志与快照结合处理
- 日志与快照的协同：在创建快照时，快照保存了系统的状态，但仍然需要处理日志中尚未快照化的请求。具体来说，服务器在接收请求时首先检查日志中的条目，再检查快照中的状态。
  - 例如，如果某个请求的请求ID在快照之后但在当前日志中不存在，系统应该确保从快照中检查该请求是否已经被处理。
请求处理流程

在处理客户端请求时，系统需要按照以下流程来检测并处理重复操作：
- 步骤1：检查日志：首先检查日志，看看该请求是否已经被记录。如果日志中存在该请求的条目，并且它还没有被提交，那么等待其提交。如果请求已提交，则直接返回之前的结果。
- 步骤2：检查快照：如果在日志中未找到请求，那么检查快照中的客户端请求状态。系统可以通过ClientId 和 RequestId 来确认请求是否已被处理。如果快照中已经保存了该请求的处理结果，则直接返回该结果。
- 步骤3：处理新请求：如果在日志和快照中都未找到该请求，则将该请求作为新的操作进行处理，并将其添加到日志中。之后，在日志提交时更新该请求的处理结果，并在下次创建快照时将其包含在快照中。
快照恢复时的请求处理
- 当服务器从快照恢复时，它不仅需要恢复系统状态，还需要恢复客户端的最新请求状态。这样，当客户端重试之前的请求时，服务器仍能检测到这些请求是否已经被处理。
- 例如，假设系统已经从快照恢复，当某个客户端重新发送已处理的请求时，服务器可以通过恢复的客户端请求状态直接返回之前的结果，而不需要重新执行该操作。

示例

假设有一个分布式键/值存储系统，并且系统已经创建了一个快照。这个快照包括了客户端1的Put("key1", "value1")请求，并删除了该请求的日志条目。

客户端1发送相同的Put请求（重复请求）：
- 当服务器收到客户端1的Put("key1", "value1")请求时，它首先检查当前的日志条目，发现该请求不在日志中。
- 然后，服务器检查从快照恢复的客户端请求状态，发现该请求的RequestId已经被处理过。
- 系统直接返回之前的成功结果给客户端1，而不会重新执行该Put操作。
客户端2发送新请求：
- 客户端2发送了一个新的请求Put("key2", "value2")。服务器首先检查日志，发现该请求不在日志中。
- 服务器随后检查快照中是否存在该请求的状态，发现客户端2的该请求还未处理过。
- 系统将该请求添加到日志中，并在多数节点确认后提交该请求，并返回处理结果给客户端2。

关键要点

请求ID跟踪和持久化：通过唯一的请求ID和客户端ID组合，系统能够准确检测每个请求的执行状态，并避免重复执行。为了处理跨快照的场景，服务器需要在快照中持久化这些请求ID信息。
快照和日志的整合：系统需要结合快照和日志来确保请求的完整处理流程。已经被快照化的请求状态应与日志中的未快照化操作一起被考虑。
恢复机制：在从快照恢复时，除了恢复系统的核心状态外，系统还需要恢复已处理的请求信息，这样在快照恢复后，仍然可以进行重复操作的检测。

通过这种机制，服务器可以在快照优化和日志操作之间平衡，确保跨快照的请求能够得到有效处理并防止重复执行。

lab4

这个实验的目的是构建一个分片的键值存储系统，主要由两个组件组成：副本组和分片控制器。总体目标是管理数据在分片中的分布，确保系统吞吐量随副本组数量增加而扩展，并能够无缝处理重新配置。

第一部分：实现分片控制器

概述：分片控制器负责管理分片到副本组的分配。你需要实现几个RPC处理程序，包括添加副本组（Join）、移除副本组（Leave）、转移分片（Move）以及查询当前配置（Query）。
具体任务：
- 在 shardctrler 目录下的 server.go 和 client.go 中实现分片控制器。
- 分片控制器管理一系列编号的配置，每个配置描述了一组副本组以及分片到副本组的分配。
- Join RPC：将新的副本组加入系统，并重新分配分片，尽可能地均匀分布，并最少移动分片。
- Leave RPC：移除指定的副本组，将这些组的分片重新分配给剩余的组。
- Move RPC：手动指定某个分片应属于哪个副本组，主要用于测试。
- Query RPC：查询指定编号的配置，如果编号是-1或大于现有最大编号，则返回最新配置。
实现细节：
- 初始配置编号为0，应该不包含任何组，所有分片都指向无效的GID（编号为0）。
- 实现时需要注意避免重复的RPC请求，尽量减少分片移动，并且分片的重新分配要保持确定性（即在Go语言中的map遍历顺序不确定，因此要小心处理）。
- 提供一个容错的分片控制器，使用Raft协议保证系统在故障情况下仍能正常工作。

完成这些任务后，确保代码通过 shardctrler 目录下的所有测试。

第二部分：实现分片键值服务器

概述：分片键值服务器负责处理 Get、Put 和 Append 操作，同时支持在多个副本组之间重新配置分片。服务器需要与分片控制器交互，了解分片到副本组的最新分配，并在分片迁移时进行数据传输。
- 实验中的 Raft 副本组不会动态演化成员集。
- 数据和查询模型非常简单。
- 分片的移交过程较慢，并且在移交期间不允许并发的客户端访问。
相比之下，真正的生产级系统通常会处理更复杂的场景，包括更高效的分片管理、动态成员更新、并发处理等功能。
任务：
- 修改 shardkv 目录下的 client.go、common.go 和 server.go，使服务器能够处理配置变化并进行分片迁移。
- 实现分片迁移时，确保并发的客户端请求不会导致不一致的结果。服务器必须在分片所有权变化时立即停止为该分片提供服务，并将数据迁移给新的副本组。
- 实现RPC机制，服务器之间通过RPC传输分片数据。
- 服务器需要周期性地查询分片控制器，获取最新配置。对于不负责的分片，服务器应该返回 ErrWrongGroup 错误。
配置变更处理：
- 服务器在检测到配置变化时，应该立即开始迁移分片。在迁移完成之前，不能为这些分片提供服务。
- 如果一个副本组失去了某个分片，它必须停止为该分片提供服务，并开始将数据迁移到新负责的副本组。
- 使用Raft日志确保所有副本组成员在相同的操作序列中处理重新配置和客户端请求。
测试：
- 完成上述任务后，确保代码通过 shardkv 目录下的所有测试，尤其是并发配置变化、可靠性、分片迁移等方面的测试。

实验提交

在提交之前，请确保所有测试都通过，包括 Raft 实现的测试 (raft 目录)、键值存储系统的测试 (kvraft 目录)、分片控制器的测试 (shardctrler 目录) 以及分片键值服务器的测试 (shardkv 目录)。

这个实验的核心挑战在于如何处理多个副本组之间的分片迁移和重新配置，同时保证系统的一致性和容错性。

分片控制器

在分片控制器 (Shard Controller) 的设计中，Config 用于定义分片和副本组之间的映射关系。每个配置 (Config) 包含了配置编号、分片到副本组的映射、以及每个副本组和它们的服务器列表。

这里的目标是实现一个分片控制器，支持添加、移除副本组，以及在副本组之间移动分片。以下是实现思路的主要步骤：

主要组件

Config 结构体：
- Num: 配置编号，用来唯一标识每个配置。
- Shards: 表示每个分片对应的副本组ID (gid)。
- Groups: 一个映射，记录副本组ID (gid) 和服务器列表之间的映射。
RPC 接口：
- Join: 添加一组新的副本组，并重新分配分片。
- Leave: 删除一组副本组，并将它们持有的分片重新分配给其他副本组。
- Move: 手动将一个分片分配给指定的副本组，用于测试。
- Query: 获取指定配置编号的配置，如果 num == -1，返回最新的配置。

设计思路

1. Join RPC

传入一个映射：gid -> servers[]，其中 gid 是副本组ID，servers[] 是该组的服务器列表。
新的副本组加入后，分片控制器需要重新平衡分片的分配，确保尽可能均匀地将分片分配到所有副本组。

func (sc *ShardCtrler) Join(args *JoinArgs, reply *JoinReply) {
    sc.mu.Lock()
    defer sc.mu.Unlock()

    // 创建一个新配置
    newConfig := sc.latestConfig()
    newConfig.Num += 1

    // 将新的副本组添加到配置中
    for gid, servers := range args.Servers {
        newConfig.Groups[gid] = servers
    }

    // 重新分配分片
    sc.rebalanceShards(&newConfig)

    // 保存配置
    sc.configs = append(sc.configs, newConfig)
}

2. Leave RPC

接受一个 gids[] 列表，删除这些副本组，并将它们的分片重新分配给其他副本组。

func (sc *ShardCtrler) Leave(args *LeaveArgs, reply *LeaveReply) {
    sc.mu.Lock()
    defer sc.mu.Unlock()

    newConfig := sc.latestConfig()
    newConfig.Num += 1

    // 删除指定的副本组
    for _, gid := range args.GIDs {
        delete(newConfig.Groups, gid)
    }

    // 重新分配它们持有的分片
    sc.rebalanceShards(&newConfig)

    sc.configs = append(sc.configs, newConfig)
}

3. Move RPC

将某个分片手动分配给指定的副本组。

func (sc *ShardCtrler) Move(args *MoveArgs, reply *MoveReply) {
    sc.mu.Lock()
    defer sc.mu.Unlock()

    newConfig := sc.latestConfig()
    newConfig.Num += 1

    // 手动移动分片
    newConfig.Shards[args.Shard] = args.GID

    sc.configs = append(sc.configs, newConfig)
}

4. Query RPC

返回指定编号的配置。如果 num == -1，返回最新配置。

func (sc *ShardCtrler) Query(args *QueryArgs, reply *QueryReply) {
    sc.mu.Lock()
    defer sc.mu.Unlock()

    if args.Num == -1 || args.Num >= len(sc.configs) {
        reply.Config = sc.configs[len(sc.configs)-1]
    } else {
        reply.Config = sc.configs[args.Num]
    }
}

5. 重新分配分片 (`rebalanceShards`)

当副本组发生变化时，需要重新平衡分片。目标是尽量均匀分配分片。

func (sc *ShardCtrler) rebalanceShards(config *Config) {
    // 获取所有现有的 gid
    gids := make([]int, 0)
    for gid := range config.Groups {
        gids = append(gids, gid)
    }

    // 重新均匀分配分片
    for i := 0; i < NShards; i++ {
        config.Shards[i] = gids[i % len(gids)]
    }
}

锁机制与Raft的一致性

由于这是一个分布式系统，多个分片控制器实例之间通过 Raft 保证一致性。因此，所有对配置的修改（如 Join、Leave、Move）都需要通过 Raft 的日志同步机制。确保每个实例处理相同的请求顺序，从而保持一致性。

测试与验证

确保每个 RPC 函数的实现能够处理以下情况：

正常的副本组加入和移除。
手动移动分片的场景。
在多副本组、多个客户端并发操作的情况下，确保分片分配的一致性。

你可以通过实现这些方法，并运行测试集来验证分片控制器的功能是否符合预期。

分片键值服务器

实现一个分片键值服务器（Shard Key-Value Store）的核心任务是通过分片机制将键值对存储在多个副本组上，以支持分布式环境下的高可用性和负载均衡。主要思路是将键映射到不同的分片，并将每个分片分配给不同的副本组来管理存储和操作请求。

实现思路

1. 系统结构

客户端（Clients）：发送 Get、Put、Append 等请求，系统会根据键决定分片，并将请求发送到管理该分片的副本组。
分片控制器（Shard Controller）：负责管理副本组和分片之间的映射。控制器接收 Join、Leave、Move、Query 等指令，动态调整分片与副本组的关系。
副本组（Replica Groups）：副本组是实际存储和管理键值对的服务器集群。每个副本组负责管理若干分片，并通过一致性协议（如 Raft）保证副本组内数据一致性。
Raft 协议：副本组内部的多个节点通过 Raft 协议进行选主并保持一致性，以确保高可用性和容错能力。

2. 数据分片机制

分片数目：通常，系统会有一个固定的分片数，比如 NShards = 10。每个分片存储一部分键值数据。
哈希映射：为了确定某个键属于哪个分片，通常使用哈希函数（如 hash(key) % NShards）将键映射到分片。
分片分配：分片控制器负责将分片分配给副本组。副本组负责处理所有属于该分片的键值对请求。

3. 请求处理流程

客户端请求：客户端发起 Get、Put 或 Append 请求。
确定分片：根据请求中的键，使用哈希函数确定该键属于哪个分片。
查找副本组：通过分片控制器查询当前配置，找到负责该分片的副本组。
发送请求：将请求发送到负责该分片的副本组，主节点处理请求并通过 Raft 保证一致性。

4. 分片控制器

分片控制器与之前讨论的一样，主要负责处理分片与副本组之间的映射。它维护一个配置列表，每个配置都记录当前分片和副本组的关系。

分片控制器的核心功能包括：

Join：新副本组加入系统，分片控制器会重新分配分片。
Leave：副本组离开系统，分片控制器将其管理的分片重新分配给其他副本组。
Move：将某个分片从一个副本组移动到另一个副本组。
Query：返回指定版本的配置，或返回最新配置。

5. 副本组

每个副本组内部使用 Raft 协议来保证副本之间的数据一致性。副本组需要处理以下操作：

Get(key)：根据键找到对应的分片，然后在该分片内查找值。
Put(key, value)：根据键找到对应的分片，将键值对存入分片，并在副本组内复制数据。
Append(key, value)：在原有值的基础上附加新值。

副本组的核心逻辑是通过 Raft 保证每个写请求在所有副本上都执行相同的操作。

6. 重新分片（Shard Rebalancing）

当副本组的加入或离开导致分片重新分配时，数据需要在副本组之间迁移。步骤如下：

分片控制器更新配置：当 Join 或 Leave 操作发生时，分片控制器会生成新的配置，调整分片与副本组的映射。
数据迁移：副本组需要将旧的分片数据迁移到新的副本组。通常是将分片的数据从旧的副本组复制到新的副本组，保证在迁移过程中不丢失数据。
切换配置：迁移完成后，所有副本组切换到新的配置，继续处理新的请求。

7. 容错与高可用性

为了保证系统在某些副本组宕机时依然可用，系统会将每个分片的数据复制到多个副本（如 3 个副本）。通过 Raft 协议，可以在副本组内的节点之间选出一个主节点处理请求。当主节点宕机时，剩下的副本可以通过选举产生新的主节点，继续处理请求。

具体实现结构

1. 分片控制器（Shard Controller）

type ShardCtrler struct {
    mu      sync.Mutex
    configs []Config
}

func (sc *ShardCtrler) Join(args *JoinArgs, reply *JoinReply) {
    // 处理副本组的加入逻辑
}

func (sc *ShardCtrler) Leave(args *LeaveArgs, reply *LeaveReply) {
    // 处理副本组的离开逻辑
}

func (sc *ShardCtrler) Move(args *MoveArgs, reply *MoveReply) {
    // 处理分片移动逻辑
}

func (sc *ShardCtrler) Query(args *QueryArgs, reply *QueryReply) {
    // 返回指定编号的配置
}

2. 副本组（Replica Group）

每个副本组内部实现键值对存储逻辑，并通过 Raft 协议保证一致性。

type KVServer struct {
    mu       sync.Mutex
    me       int
    rf       *raft.Raft
    applyCh  chan raft.ApplyMsg
    kvStore  map[string]string
}

func (kv *KVServer) Get(args *GetArgs, reply *GetReply) {
    // 处理 Get 请求
}

func (kv *KVServer) PutAppend(args *PutAppendArgs, reply *PutAppendReply) {
    // 处理 Put 和 Append 请求
}

3. Raft 协议

Raft 协议用于保证每个副本组内的节点之间的数据一致性。每个写操作都会在 Raft 中作为日志进行复制，确保所有副本都执行相同的操作。

总结

分片键值服务器的关键在于如何将键值数据合理分片，并通过分片控制器动态管理分片与副本组之间的映射。通过分片和副本机制，可以实现系统的高可用性和负载均衡。而 Raft 协议在副本组内部确保数据一致性，保证在分布式环境中的可靠性。

6.824

lab1:

lab2:

lab3:

Name		Name	Last commit message	Last commit date
Latest commit History 25 Commits
src		src
.check-build		.check-build
.gitignore		.gitignore
Makefile		Makefile
README.md		README.md

lanyoumeng/6.824

Folders and files

Latest commit

History

Repository files navigation

6.824

lab1

实验概述

实验步骤

关键实现细节

提示与建议

提交与检查

lab2

目标

第2A部分：领导选举

第2B部分：日志复制

第2C部分：持久化

第2D部分：日志压缩

实例代码建议

日志压缩

加速日志回溯优化

锁建议

规则 1：多线程访问共享数据时使用锁

规则 2：在执行一系列共享数据的修改时使用锁

规则 3：在一系列读取操作中使用锁

规则 4：避免在持有锁的情况下等待

规则 5：重新获取锁后重新检查假设条件

总结

日志工具

lab3

Part A：不带快照的键/值服务

主要步骤：

实现提示：

Part B：带快照的键/值服务

主要步骤：

线性化保证如何实现

实现线性化的关键点

示例

总结

读操作一定是在领导者上完成的吗

1. **Raft **

2. **Paxos 和 Multi-Paxos **

3. 在读写分离场景下

4. 领导者读取的必要性

跨快照的重复操作检测

示例

关键要点

lab4

第一部分：实现分片控制器

第二部分：实现分片键值服务器

实验提交

分片控制器

主要组件

设计思路

1. Join RPC

2. Leave RPC

3. Move RPC

4. Query RPC

5. 重新分配分片 (rebalanceShards)

锁机制与Raft的一致性

测试与验证

分片键值服务器

实现思路

1. 系统结构

2. 数据分片机制

3. 请求处理流程

4. 分片控制器

5. 副本组

6. 重新分片（Shard Rebalancing）

7. 容错与高可用性

具体实现结构

1. 分片控制器（Shard Controller）

2. 副本组（Replica Group）

3. Raft 协议

总结

6.824

About

Resources

Stars

Watchers

1. Raft

2. Paxos 和 Multi-Paxos

5. 重新分配分片 (`rebalanceShards`)

Packages