WarYan's Blog

记录成长历程

发表于 分类于

本文整理自本地 TinyKV 项目文件：tinykv-understanding/labs/tinykv-lab-roadmap.md。
系列顺序：TinyKV Lab 路线图 -> TinyKV Lab1：StandaloneKV -> TinyKV Lab2：RaftKV -> TinyKV Lab3：Multi-RaftKV -> TinyKV Lab3B：Region Split 后的状态收敛问题 -> TinyKV Lab4：Transactions -> TinyKV 测试指南。

资料来源：

说明：TinyKV 官方叫 Project 1/2/3/4，简历里很多人会叫 Lab 1/2/3/4。下面先按 Lab 来写。

总路线

TinyKV 的路线不是一上来就做分布式，而是逐层加能力：

1
2
3
4
Lab1: 单机 KV
  -> Lab2: 单 Raft Group 的高可用 KV
  -> Lab3: 多 Raft Group / Region / 调度
  -> Lab4: MVCC / Percolator 事务

把官方 Project、测试命令、代码范围放到一张表里：

Lab 官方阶段 主要工作 主要测试
Lab1 Project1 StandaloneStorage + Raw KV API make project1
Lab2A Project2 Part A Raft 选主、日志复制、RawNode/Ready make project2aa、project2ab、project2ac、project2a
Lab2B Project2 Part B raftstore 把 KV 请求走 Raft 后再 apply make project2b
Lab2C Project2 Part C log GC、snapshot、落后副本恢复 make project2c
Lab3A Project3 Part A conf change、leader transfer make project3a
Lab3B Project3 Part B ChangePeer、TransferLeader、Region Split make project3b
Lab3C Project3 Part C scheduler heartbeat、balance region make project3c
Lab4A Project4 Part A MVCC 版本、锁、提交记录 make project4a
Lab4B Project4 Part B KvGet、KvPrewrite、KvCommit make project4b
Lab4C Project4 Part C KvScan、rollback、check/resolve lock make project4c
阅读全文 »

发表于 分类于

本文整理自本地 TinyKV 项目文件：tinykv-understanding/labs/lab1-standalonekv.md。
系列顺序：TinyKV Lab 路线图 -> TinyKV Lab1：StandaloneKV -> TinyKV Lab2：RaftKV -> TinyKV Lab3：Multi-RaftKV -> TinyKV Lab3B：Region Split 后的状态收敛问题 -> TinyKV Lab4：Transactions -> TinyKV 测试指南。

官方页面：https://yunpengn.github.io/tinykv/doc/project1-StandaloneKV.html

一句话

Lab1 要做一个单机版 KV 服务。

它还没有 Raft、没有多副本、没有事务。客户端发 RawGet、RawPut、RawDelete、RawScan 请求，服务端直接读写本地的 Badger 数据库。

阅读全文 »

发表于 分类于

本文整理自本地 TinyKV 项目文件：tinykv-understanding/labs/lab2-raftkv.md。
系列顺序：TinyKV Lab 路线图 -> TinyKV Lab1：StandaloneKV -> TinyKV Lab2：RaftKV -> TinyKV Lab3：Multi-RaftKV -> TinyKV Lab3B：Region Split 后的状态收敛问题 -> TinyKV Lab4：Transactions -> TinyKV 测试指南。

官方页面：https://yunpengn.github.io/tinykv/doc/project2-RaftKV.html

一句话

Lab2 要把 Lab1 的单机 KV，升级成基于 Raft 的多副本 KV。

Lab1 是：

1
请求 -> 直接写本地 Badger

Lab2 变成：

1
请求 -> 先写 Raft 日志 -> 多数副本确认 -> 再写 Badger

更完整一点，写请求会走这条路：

1
2
3
4
5
6
7
8
客户端请求
  -> leader
  -> 变成一条 Raft log
  -> 复制到多数副本
  -> commit
  -> apply 到状态机
  -> 写入 Badger
  -> 返回结果

这样做的目的很简单：只要大多数节点还活着，服务就能继续工作，而且多个副本的数据不会乱。

更直观地说，Lab2 解决的是 Lab1 的两个问题：

1
2
3
4
5
问题 1：只有一台机器，挂了就没服务。
解决：复制到多台机器。

问题 2：多台机器各写各的，数据会乱。
解决：用 Raft 规定所有机器执行同一串操作。

Raft log 可以先理解成“操作流水账”：

1
2
3
log[1] = Put name Tom
log[2] = Put age 18
log[3] = Delete city

BadgerDB 是执行流水账后的最终结果：

1
2
3
name = Tom
age = 18
city 不存在

所以 Lab2 的关键不是“怎么把 value 写进硬盘”，而是：

1
2
所有副本怎样先同意这条操作排在第几位，
然后再按同样顺序写进各自的硬盘。
阅读全文 »

发表于 分类于

本文整理自本地 TinyKV 项目文件：tinykv-understanding/labs/lab3-multiraftkv.md。
系列顺序：TinyKV Lab 路线图 -> TinyKV Lab1：StandaloneKV -> TinyKV Lab2：RaftKV -> TinyKV Lab3：Multi-RaftKV -> TinyKV Lab3B：Region Split 后的状态收敛问题 -> TinyKV Lab4：Transactions -> TinyKV 测试指南。

官方页面：https://yunpengn.github.io/tinykv/doc/project3-MultiRaftKV.html

一句话

Lab3 要把“一个 Raft 组管理全部 key”，升级成“多个 Raft 组分别管理不同 key 范围”。

Lab2 是：

1
全部 key -> 一个 Region -> 一个 Raft 组

Lab3 变成：

1
2
3
[a, h) -> Region 1 -> Raft 组 1
[h, p) -> Region 2 -> Raft 组 2
[p, z) -> Region 3 -> Raft 组 3

这样数据量大了以后，就可以把不同范围的数据分摊到不同节点上。

从 Lab2 到 Lab3，可以先看这张图：



graph LR
    subgraph Lab2["Lab2：单 Raft 组"]
        AllKeys["全部 key<br/>[空, 空)"] --> OneRegion["Region 1"]
        OneRegion --> OneRaft["一个 Raft 组"]
    end

    subgraph Lab3["Lab3：Multi-Raft"]
        R1["Region 1<br/>[空, h)"] --> G1["Raft 组 1"]
        R2["Region 2<br/>[h, p)"] --> G2["Raft 组 2"]
        R3["Region 3<br/>[p, 空)"] --> G3["Raft 组 3"]
    end

    OneRaft --> R1
    OneRaft --> R2
    OneRaft --> R3

Lab3 的目标不是“把 Raft 换掉”，而是让系统里同时跑很多个 Raft 组。每个 Raft 组只负责一段 key。

阅读全文 »

发表于 分类于

本文整理自本地 TinyKV 项目文件：tinykv-understanding/labs/lab3b-split-heartbeat-difficulty.md。
系列顺序：TinyKV Lab 路线图 -> TinyKV Lab1：StandaloneKV -> TinyKV Lab2：RaftKV -> TinyKV Lab3：Multi-RaftKV -> TinyKV Lab3B：Region Split 后的状态收敛问题 -> TinyKV Lab4：Transactions -> TinyKV 测试指南。

这份记录整理的是我们在 Lab3B 实现 Region Split、ChangePeer、snapshot recovery 相关逻辑时遇到的几个问题。它们表面上出现在不同测试里，但本质都和 raftstore 在 split/conf change 之后的状态收敛有关。

问题目录

编号 问题 根因总结 典型现象 修复位置
1 split 后 scheduler 短暂找不到右半边 region split apply 后只立即上报了 left region，right region 依赖后续异步 heartbeat，导致 scheduler 暂时出现 range gap panic: find no region for "3 00000000" applySplit 中同时上报 left/right
2 被移除的 peer 继续 apply 后续 committed entries RemoveNode 删除自己后 peer 已经 destroy，但同一个 Ready 中剩余 committed entries 仍被继续 apply，可能破坏 raft/apply 状态一致性 unexpected raft log index: lastIndex 0 < appliedIndex ... HandleRaftReady 每次 applyEntry 后检查 d.stopped
3 用 left region 访问 right key 时没有稳定返回 KeyNotInRegion 普通 KV 请求只在 apply 阶段检查 key range，请求已经进入 Raft 后才发现越界，错误返回受 commit/apply 时序影响 TestOneSplit3B 中 expected KeyNotInRegion，但 header error 为 nil preProposeRaftCommand 对普通 KV 请求提前检查 key range
阅读全文 »

发表于 分类于

本文整理自本地 TinyKV 项目文件：tinykv-understanding/labs/lab4-transactions.md。
系列顺序：TinyKV Lab 路线图 -> TinyKV Lab1：StandaloneKV -> TinyKV Lab2：RaftKV -> TinyKV Lab3：Multi-RaftKV -> TinyKV Lab3B：Region Split 后的状态收敛问题 -> TinyKV Lab4：Transactions -> TinyKV 测试指南。

官方页面：https://github.com/talent-plan/tinykv/blob/course/doc/project4-Transaction.md

先建立直觉

Lab4 不要一上来就背 MVCC、Percolator、2PC。先把它想成一个多人共用的小仓库。

Lab1 到 Lab3 已经让这个仓库越来越靠谱：



graph LR
    L1["Lab1<br/>单机仓库<br/>能查、存、删、扫"] --> L2["Lab2<br/>多副本仓库<br/>写入先经过 Raft"]
    L2 --> L3["Lab3<br/>很多片仓库<br/>按 Region 分摊 key 空间"]
    L3 --> L4["Lab4<br/>事务仓库<br/>多人同时改也要有规矩"]

Lab1-3 解决的是：

1
2
3
数据怎么存
数据怎么复制
数据怎么拆分到多个 Region

Lab4 解决的是：

1
2
多个客户端同时读写时，怎么保证读到一个稳定视图。
一次事务改多个 key 时，怎么保证要么都成功，要么都不成功。

换成更生活化的话：

1
2
3
4
5
6
7
Lab1-3 像是在建设仓库本身。
Lab4 像是给仓库加账本、临时占用牌、正式入账记录。

有人正在改某件货，先挂一把锁。
货物有历史版本，读的人按自己进门时的时间看账。
改完以后写一条正式记录，别人才看得到。
改到一半失败，就把临时东西撤掉，并留一条“这次作废”的记录。

这就是 Lab4 的直觉。



graph TB
    Raw["Lab1-3 的 Raw KV 视角<br/>一个 key 只有一个当前值"] --> Problem["多客户端并发读写<br/>会遇到读旧值、写冲突、半路失败"]
    Problem --> Txn["Lab4 的事务视角<br/>一个 key 有多个版本<br/>还有锁、提交记录、回滚记录"]
阅读全文 »

发表于 分类于

本文整理自本地 TinyKV 项目文件：tinykv-understanding/labs/testing-guide.md。
系列顺序：TinyKV Lab 路线图 -> TinyKV Lab1：StandaloneKV -> TinyKV Lab2：RaftKV -> TinyKV Lab3：Multi-RaftKV -> TinyKV Lab3B：Region Split 后的状态收敛问题 -> TinyKV Lab4：Transactions -> TinyKV 测试指南。

官方 Makefile：https://github.com/talent-plan/tinykv/blob/course/Makefile

这份文档只回答一个问题：每个 Lab 应该怎么跑测试，测试大概在查什么。

最常用命令

在 TinyKV 源码根目录运行：

1
2
3
4
make project1
make project2
make project3
make project4

如果只想跑某个小阶段：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
make project2aa
make project2ab
make project2ac
make project2a
make project2b
make project2c

make project3a
make project3b
make project3c

make project4a
make project4b
make project4c
阅读全文 »

发表于 分类于

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

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

一句话概括：

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

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

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
阅读全文 »

发表于 分类于

第 3 章 数据链路层

使用点对点信道的数据链路层

数据链路和帧

  • 数据链路层使用的信道主要有以下两种类型：

    • 点对点信道。这种信道使用一对一的点对点通信方式。
    • 广播信道。这种信道使用一对多的广播通信方式，因此过程比较复杂。广播信道上连接的主机很多，因此必须使用专用的共享信道协议来协调这些主机的数据发

  • 链路(link)是一条无源的点到点的物理线路段，中间没有任何其他的交换结点。

  • 数据链路(data link) 除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路。

  • 数据链路层传送的是帧

    阅读全文 »
0%