MIT 6.5840 和 TinyKV：从分布式系统到分布式数据库存储层

最近把 MIT 6.5840 和 TinyKV 都重新梳理了一遍。它们看起来都在写 KV、Raft、分片和容错，但真正做下来会发现，二者的训练目标很不一样。

MIT 6.5840 更像分布式系统正确性的训练营。它关心的是：在 RPC 丢包、乱序、重试、网络分区、节点重启这些条件下，系统怎样还能给出正确结果。TinyKV 更像分布式数据库存储层的缩小版。它关心的是：数据如何落到本地存储，Raft 如何接入真实的 raftstore，Region 如何分裂和调度，事务如何通过 MVCC 和 Percolator 协议实现。

一句话概括：

MIT 6.5840 训练的是分布式系统底层正确性。
TinyKV 训练的是把这些正确性能力放进数据库存储层。

先用一张图把两条路线摆在一起：

也可以用 Mermaid 把它抽象成两条学习路径：

flowchart LR
    ROOT["两条路线都在训练 KV + Raft，但落点不同"]

    ROOT --> MIT0["MIT 6.5840<br/>系统正确性"]
    MIT0 --> RAFT["Raft / KVRaft<br/>复制状态机"]
    RAFT --> SHARD["ShardKV<br/>分片迁移"]

    ROOT --> TINY0["TinyKV<br/>数据库存储层"]
    TINY0 --> RK["RaftKV / Multi-Raft<br/>Region + raftstore"]
    RK --> TXN["Transactions<br/>MVCC / Percolator"]

    RAFT -. "共识底座" .-> RK
    SHARD -. "分片思想" .-> RK

两个项目分别做什么

MIT 6.5840 的主线是：

MapReduce
  -> 单机 KV Server
  -> Raft
  -> KV over Raft
  -> Sharded KV

它从一个分布式计算框架开始，让你先理解 coordinator 和 worker 的任务分发、失败重试、临时文件和输出文件管理。然后进入 KV 服务，先做单机去重和 RPC，再把 KV 请求接到 Raft 上，最后通过 shardctrler 和 shardkv 实现分片 KV。

TinyKV 的主线是：

Standalone KV
  -> RaftKV
  -> Multi-RaftKV
  -> Transactions

它一开始就站在数据库存储层视角：先实现单机 Raw KV 和 BadgerDB 封装，再实现 Raft 本体和基于 Raft 的 KV 复制，之后引入 Region、Peer、Store、Scheduler，最后在 KV 之上实现 MVCC 和 Percolator 风格事务。

所以二者并不是简单重复。它们有交集，但训练方向不同。

维度	MIT 6.5840	TinyKV
项目气质	分布式系统课程实验	分布式数据库存储层实验
核心问题	不可靠网络下如何保证正确性	如何构建 TiKV 风格的存储节点
存储模型	多数实验用内存 map，snapshot 序列化状态	BadgerDB、Column Family、raftdb/kvdb、MVCC
Raft 接入方式	Raft 模块直接和 service 配合	更接近 etcd-raft/TiKV 的 Tick/Step/Ready/Advance
分片方式	固定数量 shard，shardctrler 管配置	Range Region，每个 Region 是一个 Raft group
事务能力	基本没有完整数据库事务	MVCC、2PC、Percolator、锁清理和回滚

MIT 6.5840 的重点

MIT 6.5840 的重点不是“写一个数据库”，而是理解分布式系统里为什么正确很难。

下面这张图可以先抓住 MIT 6.5840 的主线：前面训练任务分发和 RPC 去重，中间训练单组 Raft 正确性，最后把正确性扩展到多组 ShardKV。

KVRaft 到 ShardKV 的核心变化，可以拆成两条线看。第一条是请求怎么找到负责它的 replica group：

flowchart LR
    C["Client"] --> SC["ShardCtrler<br/>Query 最新配置"]
    SC --> ROUTE["key -> shard<br/>shard -> replica group"]
    ROUTE --> G1["Replica Group 1<br/>Raft 复制<br/>shard 0 / 1 / 2"]
    ROUTE --> G2["Replica Group 2<br/>Raft 复制<br/>shard 3 / 4"]

第二条是配置变化后，旧 owner 和新 owner 怎样交接 shard：

flowchart LR
    CFG["新配置进入<br/>各组 Raft log"] --> STOP["旧 owner 停止服务<br/>待迁移 shard"]
    STOP --> PULL["新 owner 拉取<br/>shard 数据"]
    PULL --> DEDUP["同步 client<br/>去重表"]
    DEDUP --> SERVE["新 owner 服务<br/>该 shard"]
    SERVE --> GC["旧 owner GC<br/>旧 shard"]

1. MapReduce：任务分发和失败恢复

MapReduce 看起来简单，但它已经把后面很多问题提前暴露出来了：

• coordinator 如何记录 map/reduce 任务状态。
• worker 挂掉后任务如何重新分配。
• 中间文件如何命名，才能让 reduce worker 找到正确输入。
• 如何避免半成品污染最终输出。

这一部分最有意思的是，它让人第一次感受到分布式系统里的“完成”不是函数返回那么简单。一个 worker 说自己完成了，coordinator 要相信吗？worker 半路挂了怎么办？任务被执行两次怎么办？这些问题后面在 KV、Raft、ShardKV 里都会以更复杂的形式回来。

2. 单机 KV：RPC 和去重

单机 KV Server 主要实现 Get/Put/Append，但重点不只是 map 读写，而是重复请求处理。

客户端可能因为超时重试，同一个 Append 请求到达服务端两次。如果服务端不做去重，Append("x", "a") 可能会变成追加两次。这里的 client id、request id、last reply 这些机制，是后面 Raft KV 和 ShardKV 的基础。

这部分的价值在于：它让人意识到“至少一次 RPC”不能直接等价于“刚好一次语义”。刚好一次语义通常要靠应用层的去重状态来补。

3. Raft：正确性的核心训练

MIT 6.5840 的 Raft 是非常典型的从零实现：

• 选举和心跳。
• 日志复制和冲突回退。
• 持久化 term、vote、log。
• snapshot 和 InstallSnapshot。
• leader 变更下的安全性。

这里最难的地方不是把论文翻译成代码，而是处理测试里各种并发和故障组合。比如：

• leader 发送了日志但还没提交就宕机。
• 新 leader 覆盖旧 leader 未提交日志。
• follower 日志落后太多，需要 snapshot。
• apply goroutine 和 snapshot 安装之间的边界。
• RPC 回复乱序后，leader 还能不能安全更新 nextIndex 和 matchIndex。

这一部分训练的是分布式系统最底层的直觉：任何你以为“应该马上发生”的事情，都可能延迟、丢失、重复、乱序。

4. KVRaft：把状态机接到 Raft 上

KVRaft 的核心是复制状态机：

客户端请求 -> leader -> Raft log -> 多数派提交 -> apply 到 KV 状态机 -> 返回客户端

这里要处理的重点包括：

• 只有 leader 能接收请求。
• 请求提交后才能真正修改状态机。
• 客户端重复请求不能重复 apply。
• snapshot 要保存 KV 数据和去重表。
• leader 变更时，等待中的请求如何知道自己是否成功。

这部分的意义在于，它把 Raft 从“共识算法”变成“服务的一部分”。Raft 不只是通过测试的模块，它要决定一个真实请求什么时候可以返回。

5. ShardKV：分片迁移和配置一致性

ShardKV 是 MIT 6.5840 里最有工程味的部分。它引入 shardctrler 管理配置，每个 replica group 内部用 Raft 复制自己的 shard 数据。

难点集中在配置切换：

• 一个 shard 在同一时刻只能由一个 group 服务。
• 配置变更也要进入 Raft log，和用户请求排出确定顺序。
• 新 owner 要从旧 owner 拉取 shard 数据。
• 迁移时不仅要迁移 KV 数据，还要迁移 client 去重状态。
• 旧 owner 什么时候可以删除 shard 数据。

我觉得 ShardKV 最有意思的地方是：它把“正确性”从单个 Raft group 推到了多个 group 之间。单组 Raft 已经不够了，你还要考虑配置、迁移、拒绝错误 group 请求、GC 旧 shard 等一整套流程。

TinyKV 的重点

TinyKV 的重点是“更像数据库”。它不只是做一个能通过课程测试的 KV，而是模拟 TiKV 存储层的一些关键结构。

TinyKV 最好先从 raftstore 和 Multi-Raft 的角度看。Raft 在这里不是一个孤立算法模块，而是被接到存储、Region、Peer 和 Scheduler 这些结构里。

TinyKV 写请求的路径可以这样理解：

sequenceDiagram
    participant C as Client
    participant S as RaftStorage
    participant P as Peer/raftstore
    participant R as Raft RawNode
    participant PS as PeerStorage
    participant DB as BadgerDB

    C->>S: RawPut / RawDelete
    S->>P: RaftCmdRequest
    P->>R: Propose(entry)
    R-->>P: Ready(entries, messages, committed)
    P->>PS: SaveReadyState
    PS->>DB: 持久化 HardState 和 log
    P->>DB: apply committed entry
    P-->>S: callback
    S-->>C: response

Multi-Raft 里的 Store、Region、Peer 关系，可以再压成一张图：

flowchart TB
    subgraph S1["Store 1"]
        P11["R1 Peer"]
        P21["R2 Peer"]
    end
    subgraph S2["Store 2"]
        P12["R1 Peer"]
        P32["R3 Peer"]
    end
    subgraph S3["Store 3"]
        P23["R2 Peer"]
        P33["R3 Peer"]
    end

    P11 --- R1["Region 1<br/>[a, h)<br/>Raft group"]
    P12 --- R1
    P21 --- R2["Region 2<br/>[h, p)<br/>Raft group"]
    P23 --- R2
    P32 --- R3["Region 3<br/>[p, z)<br/>Raft group"]
    P33 --- R3

    Scheduler["Scheduler/PD 思想<br/>收集 heartbeat<br/>生成 balance operator"] -.-> S1
    Scheduler -.-> S2
    Scheduler -.-> S3

1. StandaloneKV：存储抽象和 BadgerDB

TinyKV 的 Lab1 是单机 KV，但它和 MIT 的单机 KV 不太一样。

MIT 的单机 KV 更偏内存服务和 RPC 去重；TinyKV 的单机 KV 更偏存储引擎封装。它要实现 Storage 接口，把 RawGet/RawPut/RawDelete/RawScan 映射到底层 BadgerDB。

这里有几个重要概念：

• Storage.Reader 返回一个一致性读视图。
• Write 接收一批 Modify，统一写到底层引擎。
• Badger 本身没有 Column Family，TinyKV 用 key prefix 模拟 CF。
• 后面的事务层会真正用到 default/write/lock 三个 CF。

这一部分看起来不难，但它把 TinyKV 的数据库味道铺好了：上层不直接操作 map，而是通过存储抽象操作一个本地持久化引擎。

2. RaftKV：更工程化的 Raft 接入方式

TinyKV 的 Raft 本体和 MIT 重叠度很高，都有选举、日志复制、持久化和 snapshot。但 TinyKV 更特别的地方在于它的接口风格：

Tick / Step -> Ready -> 持久化/发消息/apply -> Advance

Raft 模块本身不直接发网络包，也不直接写磁盘。它只告诉上层：

• 哪些消息要发。
• 哪些日志和 HardState 要持久化。
• 哪些 entry 已经 committed，可以 apply。

真正复杂的是 raftstore：

• RaftStorage 把 KV 请求包装成 RaftCmdRequest。
• proposeRaftCommand 把请求 propose 进 Raft。
• HandleRaftReady 处理 Ready。
• PeerStorage.SaveReadyState 保存 HardState 和日志。
• applyEntry 把 committed entry 应用到 Badger。
• callback 把结果返回给客户端。

这一套比 MIT 的 KVRaft 更接近真实系统。面试时如果讲 TinyKV，不能只说“我实现了 Raft”，还要讲清楚 Ready 的处理顺序为什么重要：

先持久化，再发消息，再 apply，最后 Advance。

顺序错了，崩溃恢复后就可能出现已经对外暴露、但本地没有持久化的状态。

3. Log GC 和 Snapshot：长期运行问题

MIT 和 TinyKV 都有 snapshot，但 TinyKV 的处理更贴近存储系统。

TinyKV 里 Raft log 不能无限增长，所以会通过 CompactLog 这种 admin command 推进 TruncatedState，再由 raftlog-gc worker 异步删除旧日志。

当 follower 落后太多，leader 本地已经 compact 掉它需要的日志，就不能继续普通 AppendEntries，只能发送 snapshot。snapshot 在 TinyKV 里不只是 Raft 层元信息，还涉及：

• region worker 生成 snapshot。
• snapshot 文件传输。
• follower 应用 snapshot。
• 清理旧 Region 状态。
• 更新 RaftLocalState、RaftApplyState、RegionLocalState。

这里有一个容易混淆的点：

Raft snapshot 是复制状态机恢复手段。
Snapshot Isolation 是事务隔离级别。
它们完全不是一回事。

4. Multi-Raft：Region、Peer、Store

TinyKV 的 Lab3 是它和 MIT 差别最大的部分之一。

MIT 的 ShardKV 是固定数量 shard，由 shardctrler 维护配置。TinyKV 则更像 TiKV：整个 key 空间被切成连续的 Range Region，每个 Region 背后是一组 Peer 组成的 Raft group。

三个词要分清：

概念	含义
Store	一个 TinyKV 存储进程，类似一台存储节点
Region	一段连续 key range
Peer	某个 Region 在某个 Store 上的一份副本

所以横着看：

同一个 Region 的多个 Peer -> 一个 Raft group

竖着看：

同一个 Store 上有很多不同 Region 的 Peer

Multi-Raft 的意义是扩展性。单个 Raft group 所有写请求都要排成一条日志，吞吐受限。拆成多个 Region 后，不同 key range 可以由不同 Raft group 并行处理。

Lab3 里有几个非常面试友好的点：

• ChangePeer 如何增加或删除副本。
• TransferLeader 如何转移 leader。
• Region Split 如何把一个 Region 切成两个。
• RegionEpoch.conf_ver 和 RegionEpoch.version 分别什么时候增加。
• KeyNotInRegion 和 EpochNotMatch 什么时候返回。
• 新 Peer 如何通过 snapshot 追数据。

这些问题都很像真实数据库存储系统会遇到的东西。

5. Scheduler：PD 思想的缩小版

TinyKV 的 Scheduler 类似 TiKV 里的 PD 思想。它通过 Region heartbeat 观察整个集群，然后决定是否要搬 Region、加 Peer、删 Peer、转移 leader。

这里最有意思的是职责分离：

TinyKV store 负责执行具体命令。
Scheduler 负责站在全局视角做决策。

Scheduler 不能盲目信任 heartbeat。因为网络分区后，旧 Region 信息可能还会被上报。它要通过 RegionEpoch 判断哪个信息更新。

balance-region scheduler 的逻辑也很有工程味：从负载较高的 store 选 region，迁移到负载较低的 store，并且要判断这个迁移是否真的值得做。

6. Transaction：MVCC 和 Percolator

TinyKV 最区别于 MIT 6.5840 的地方，是 Lab4 事务。

MIT 6.5840 的 KV 基本是 Get/Put/Append 语义，没有完整数据库事务。TinyKV 则实现了 MVCC 和 Percolator 风格的 2PC。

事务这部分如果只看文字会很绕，关键是把 lock/default/write 三个 CF 和 Prewrite/Commit 两阶段流程对应起来：

正常事务路径和异常锁清理路径，可以拆成两个 Mermaid 流程：

flowchart TB
    BEGIN["事务开始<br/>拿到 start_ts"] --> READ["KvGet/KvScan<br/>按 start_ts 读快照"]
    READ --> PRE["KvPrewrite<br/>检查 write conflict 和 lock conflict"]
    PRE --> LOCK["lock CF<br/>写事务锁"]
    PRE --> DEFAULT["default CF<br/>写临时 value"]
    LOCK --> COMMIT["KvCommit<br/>拿到 commit_ts"]
    DEFAULT --> COMMIT
    COMMIT --> WRITE["write CF<br/>写提交记录"]
    COMMIT --> UNLOCK["删除 lock"]
    WRITE --> VISIBLE["版本正式可见"]
    UNLOCK --> VISIBLE

flowchart TB
    CONFLICT["遇到别的事务遗留 lock"] --> CHECK["KvCheckTxnStatus<br/>检查 primary lock"]
    CHECK -->|primary 已提交| RESOLVE_COMMIT["KvResolveLock<br/>提交 secondary locks"]
    CHECK -->|primary 超时/不存在| ROLLBACK["KvBatchRollback<br/>删除临时 value<br/>写 rollback 记录"]
    RESOLVE_COMMIT --> CLEAN["状态收敛<br/>清理锁"]
    ROLLBACK --> CLEAN

核心概念包括：

• start_ts：事务开始时间，决定能看到哪些版本。
• commit_ts：事务提交时间，决定写入什么时候可见。
• default CF：存真实 value。
• write CF：存提交记录。
• lock CF：存事务锁。

一条事务写入大概是：

KvPrewrite:
  检查写冲突和锁冲突
  写 lock
  写 default value

KvCommit:
  检查 lock 是否属于当前事务
  写 write 记录
  删除 lock

异常处理也很关键：

• KvCheckTxnStatus 检查 primary lock 是否超时或已提交。
• KvBatchRollback 删除临时 value、清锁、写 rollback 记录。
• KvResolveLock 根据 primary 状态批量提交或回滚 secondary locks。
• KvScan 不能像 RawScan 一样直接扫当前值，而要按 start_ts 找每个 key 的可见版本。

这一部分非常数据库。它让 TinyKV 从“一个复制 KV”变成“一个有事务语义的分布式存储层”。

二者重难点对比

主题	MIT 6.5840 的难点	TinyKV 的难点
Raft	从零实现协议，并通过极端不可靠测试	把 Raft 接入 raftstore，处理 Ready、持久化、callback
Snapshot	KV 状态和去重表的序列化恢复	Raft 元信息、Region 数据、snapshot 文件和状态清理
分片	配置变更和 shard 迁移的一致顺序	Region split、ChangePeer、RegionEpoch、Scheduler
存储	主要是内存状态和快照	Badger、CF、raftdb/kvdb、MVCC 编码
事务	基本没有完整事务	Percolator、MVCC、lock/write/default、rollback
测试压力	RPC 乱序、丢包、重复、重启、分区	多模块协作：Raft、raftstore、scheduler、transaction

我自己的理解是：

MIT 6.5840 难在“所有并发和故障组合下都不能错”。
TinyKV 难在“模块更多，更像真实数据库，边界和状态更多”。

面试里怎么讲

如果面试官问：“MIT 6.5840 和 TinyKV 有什么区别？”

可以这样回答：

MIT 6.5840 更偏分布式系统正确性，我在里面实现了 MapReduce、Raft、KVRaft 和 ShardKV，重点是处理不可靠网络、重复请求、leader 切换、snapshot、shard 迁移这些问题。TinyKV 更偏分布式数据库存储层，它也有 Raft，但更强调 Raft 如何接入真实存储系统，比如 Badger、raftstore、Region、Scheduler、MVCC 和 Percolator。二者的关系是，MIT 6.5840 给了我分布式正确性底座，TinyKV 让我把这个底座放进数据库存储系统里。

如果继续追问：“两个项目分别最有意思的地方是什么？”

可以这样回答：

MIT 6.5840 最有意思的是 ShardKV。因为它不只是单个 Raft group 的正确性，还要处理多个 group 之间的配置切换、shard 数据迁移和去重状态迁移。TinyKV 最有意思的是 Multi-Raft 和事务。Multi-Raft 让我看到 TiKV 这种系统如何用 Region 把 key 空间拆开，事务部分则让我理解 MVCC、lock/default/write 三个 CF，以及 Percolator 如何用 2PC 在 KV 层实现事务。

如果问：“这两个项目有没有重复？”

可以这样回答：

有重叠，主要是 Raft 和 KV over Raft。但重复部分的侧重点不一样。MIT 6.5840 是从零实现 Raft 并验证正确性，TinyKV 是把 Raft 模块接入 raftstore，处理持久化、Region、snapshot 和上层 KV 请求。前者像打地基，后者像把地基用在数据库存储层。

总结

MIT 6.5840 和 TinyKV 都很值得做，但收获不一样。

MIT 6.5840 让我理解：

• RPC 不可靠时怎么设计系统。
• Raft 为什么能保证复制状态机一致。
• snapshot、去重、shard 迁移这些细节为什么容易出错。
• 分布式系统里的正确性必须靠状态机顺序和持久化边界来保证。

TinyKV 让我理解：

• 一个 KV 存储系统如何从单机走向分布式。
• Raft 如何以 Ready 的形式嵌入真实存储系统。
• Region、Peer、Store、Scheduler 如何组成 Multi-Raft 架构。
• MVCC 和 Percolator 如何在 KV 层实现事务。

最后可以这样记：

MIT 6.5840 是分布式系统的骨架。
TinyKV 是分布式数据库存储层的血肉。

前者让我知道系统为什么不能错，后者让我知道一个更接近真实数据库的系统到底由哪些模块拼起来。