MIT6.824分布式课程

Lab1—MapReduce

什么是MapReduce

这个方法是处理大数据集的一种简单方法。

前提 : 一般来说, 你会有大量装有含有效数据的文件

Map phase: 读取一小部分文件, 生成你有需要的key/value对, 并且通过key的值来分组(一般用hashmap), 所以叫做map
- 这个Map过程的目的就是归一化, 不管你有多少文件, 你都可以通过Map来变成10个文件, 或者100个文件.(一般来说多少个文件, 到最后就是多少个Reduce任务, 也叫nReduce)
- 这个过程的结果存储在本地, 图中有显示.on local disks
Reduce phase: 读取属于自己的任务的所有文件, 并合并
- 图二中的竖着的框就是它的任务.
- 这个过程是romate读. from local disks

Lab1-Code

总览:
- Work需要通过rpc请求任务, 根据不同回应处理map和reduce两个任务.
- Master负责发送任务, 并且监控任务的完成情况.

我的代码思路: Work和rpc太简单不说了 Master的思路:

数据结构
- 待发送列表
- 已完成列表
- 初始值: len(待发送列表) - 1, 也就是下次给发送的任务的下标
算法
- 发送一个任务后, (初始值 - 1)
- 收到worker完成的消息后, 已完成列表添加完成的任务
- 等到索引值变成-1了, 等几秒, 并且任何worker都无法成功请求到任务, 回复都是busy
  - 目的是等待拿到任务的worker来完成工作
- 几秒后, 检查一下还有哪些任务没有完成
  - 全部完成的话就下一个阶段
  - 还有任务没完成的话
    - 待发送列表通过求差, 变成没完成的任务的列表
    - 已经完成列表清空
- 回到第一步

Lab2—Raft

实现Raft最重要的就是看图

按照Figure2的图来实现Raft的算法!!

一定要熟读,看懂英文, 要不然不可能做得出来. 说一下仅有的两个RPC请求参数和返回值:

AppendEntries RPC
- Agreements
  - term
    - leader’s term
  - leaderId
    - so follower can redirect clients(这个我感觉去掉也可以,看过很多实现, 都没有用到这个)
  - prevLogIndex
    - index of log entry immediately preceding new ones
    - 意思是, leader觉得follower应该添加日志的前一个日志的index
  - prevLogTerm
    - term of prevLogIndex entry
    - 意思是, rf.log[prevLogIndex].term
  - entries[]
    - log entries to store (empty for heartbeat; may send more than one for efficiency)
    - 意思是: leader觉得follower应该添加的日志, 从prevLogIndex+1开始, 你从prevLogIndex如果少了, 那么日志就要加一条, 这样follower遇到正确的,直接就可以添加进去
  - leaderCommit
    - leader’s commitIndex
    - 意思是: leader认为的commitIndex, follower可以根据这个来commit自己的日志
- Results
  - term
    - currentTerm, for leader to update itself
  - success
    - true if follower contained entry matching prevLogIndex and prevLogTerm
    - 意思为: follower是否成功添加了leader要求的日志
RequestVote RPC
- Agreements
  - term
    - candidate’s term
  - candidateId
    - who requesting vote
  - lastLogIndex
    - index of candidate’s last log entry
    - (就是通过这个来判断应该投给谁, 特别重要!!)
  - lastLogTerm
    - term of candidate’s last log entry
    - (就是通过这个来判断应该投给谁, 特别重要!!)
- Results
  - term
    - currentTerm, for candidate to update itself
  - voteGranted
    - true means candidate received vote
    - 意思为: candidate投票给了谁

实现Raft的几个重要的规则

如果收到的term比自己的term大, 那么就转换为follower
如果收到的term比自己的term小, 那么就拒绝, 这是过时的消息
只有这样情况才能投票给候选人:
- 最后一条日志的term相等, 且候选人的Log记录长度大于等于本地Log记录的长度
- 最后一条日志的term不等时, 候选人的term大于本地term
- 我就是因这条没写好, 导致一直过不了figure8的测试, shit!
follower在收到term正确的AppendEntries RPC, 就可以重置选举计时器了
快速回滚也要做:

term不符合的话follower返回, 等于term的第一个位置;
leader也往前找到最后一个, 等于返回的term的位置, 设置nextindex = 位置 + 1

MIT6.824 Lab

MIT6.824分布式课程

Lab1—MapReduce

什么是MapReduce

Lab1-Code

Lab2—Raft

实现Raft最重要的就是看图

实现Raft的几个重要的规则

推荐阅读

Lab3

Lab4