My code of the course mit6.824

Overview

MIT6.824

Lab1

Rules

  1. 最后文件需要输出nReduce个,文件名格式为mr-out-X
  2. 输出到文件的格式在mrsequential.go
  3. 只用写worker.go/coordinator.go/rpc.go这三个文件
  4. worker将中间文件输出到当前文件夹下,之后worker执行reduce任务的时候从中取
  5. 需要实现coordinator.go中的Done()方法,当全部任务被执行完了之后返回true,然后mrcoordinator退出
  6. 当所有的任务的完成的时候,worker也应该停止。简单的方法就是使用rpc的回调,当返回err,也就是故障的时候,这里可以理解为coordinator已经结束了,所以这时候worker可以退出了。

Hints

  1. 一开始可以先实现worker的worker方法来和coordinator进行rpc调用来获取任务,coordinator回应给他文件名作为一个还未开始的map任务。然后worker读取这些文件然后调用map方法,参考mrsequential.go中的方法
  2. map和reduce方法是作为插件使用的,记得启动的时候带上参数wc.so
  3. 没有wc.so插件就build一个,go build -race -buildmode=plugin ../mrapps/wc.go
  4. 中间文件可以命名为mr-X-Y,X表示map任务编号,Y表示reduce任务编号。
  5. 中间文件使用json方法来存来读取
  6. map的worker使用ihash(key)方法来获取reduce编号,靠这个存到对应的中间文件中
  7. coordinator作为一个rpc服务端,需要对共享资源进行并发保护
  8. run的时候使用-race检查一下
  9. 只有所有的map任务被执行完了之后才能进行reduce任务的分配。一种方法是worker周期的请求coordinator来获取任务,没获取到就sleep一会再来请求。另一种方法是每个rpc的handler可以循环等待一下,使用time.Sleep或者sync.Cond
  10. coordinator不能可靠的区别那些故障worker,包括那些执行的太慢的节点。最好就是每次分配了任务之后可以等待10秒,如果10秒都没有完成,就可以认为该worker已故障了。需要重新将该任务分配给别的worker。
  11. 测试故障恢复可以使用mrapps/crash.go插件,会随机在map和reduce中故障
  12. 为了不让已经故障的节点的产生文件对作为真正的中间文件,可以使用论文中提到的临时文件的方法,worker写的使用可以使用临时文件,使用ioutil.TempFile来创建临时文件,然后完成之后使用os.rename来原子性的命名。

Task

结构

任务的id(若为map类型则id为0-files.size-1,若为reduce类型则为分区序号,也就是0-nReduce-1)

  • Id int

    任务的类型

  • TaskType string

    任务需要的文件名(map任务使用,源文件名)

  • Filename string

    任务需要的中间文件名集合(reduce任务使用)

  • Filenames []string

    状态:free/working/finnished

  • Status status

    Reduce任务数(也就是最终输出文件的分区数)

  • NReduce int

方法

//是否已完成
func (s *Task) isFinished() bool
//是否正在处理
func (s *Task) isWorking() bool 
//是否空闲(未被处理)
func (s *Task) isFree() bool
//修改状态为working
func (s *Task) working()
//修改状态为finished
func (s *Task) finished()
//修改状态为free
func (s *Task) free()
//是否是map任务
func (t *Task)isMapTask() bool
//是否是map任务
func (t *Task)isReduceTask() bool

coordinator

结构

存储map任务id->Task

  • mapTasks map[int]*Task *存储reduce任务id->Task
  • reduceTasks map[int]*Task map任务通道
  • mapChan chan *Task reduce任务通道
  • reduceChan chan *Task 当前是否已经处理完所有map任务
  • mapFinished bool 互斥锁
  • mu sync.Mutex 中间文件reduceId->Filenames,format : mr-X-Y (X表示map的id,Y表示reduce的id)
  • interFiles map[int][]string

功能

  1. 传入需要处理的文件名集合,和reduce数目n,n也就是最后出来的n个中间文件。实例化coordinator,创建map和reduce任务然后开启serve,等待worker前来取任务。
  2. 有worker来取任务,判断当前的map通道是否为空,不为空则返回,为空则让它从reduce通道中取;如果此时已经有reduce任务了,则直接返回任务,若没有则直接返回;
  3. 若worker来取的是map任务,则开启一个go routine等10秒后判断刚刚的Task的任务是否已经被完成,若还是working则将状态设为free,并且重新加入chan中。若取的是reduce也同理。
  4. 当worker完成任务时,worker rpc调用finished方法,此时coordinator判断该任务的状态是否是working,是的话则完成该任务,更改状态为finished,作相应处理;map任务则将传来的中间文件名用来加入到中间文件map中;reduce任务则不作额外处理。
  5. Done方法会不断检查当前所有的任务是否已经完成,当所有任务的状态为finished时,返回true。

worker

功能

  1. rpc调用coordinator的GetTask方法,若获取到Task则执行相应的方法,map或者reduce。若返回的Task为空的时候sleep一秒后再循环获取。若rpc调用返回err则worker可以退出了;
  2. 当完成一个任务的时候,将完成的任务的情况rpc调用FinishedTask方法来通知coordinator。调用err的时候直接退出。
  3. 有map和reduce方法,分别进行处理。
Owner
TheR1sing3un
TheR1sing3un
An easy-to-use Map Reduce Go parallel-computing framework inspired by 2021 6.824 lab1. It supports multiple workers on a single machine right now.

MapReduce This is an easy-to-use Map Reduce Go framework inspired by 2021 6.824 lab1. Feature Multiple workers on single machine right now. Easy to pa

Bo-Wei Chen 193 Jun 9, 2022
mit 6.824 lab

lab-6.824 0. How to run? go版本: 1.13+ 在高于1.11的版本中报unexpected directory layout, 但是用较低版本goLand无法调试... unexpected dir layout 原因是不支持相对路径包引入, 遇到时在import 删掉.

JinyuChata 1 Dec 9, 2021
learn mit 6.824 lab

MIT6.824 lab1 MapReduce timeout: command not found -> brew install coreutils panic data race -> 加锁 内层变量会屏蔽外部同名变量 test1 word-count 测试基本功能 test2 indexer

GoodbyeYesterDay 0 Jan 5, 2022
labs & notes on 6.824

Lab 1: MapReduce MapReduce论文 概念 MapReduce is a programming model and an associated implementation for processing and generating large data sets. Users

Vurtne 1 Mar 6, 2022
MIT 6.824: Distributed Systems (Spring 2020)

MIT6.824 MIT 6.824: Distributed Systems (Spring 2020) Lab 1 Lab 2 Lab 2A Lab 2B Lab 2C Lab 2D Lab 3 Lab 3A Lab 3B Lab 4 Lab 4A Lab 4B Lab 4 Challenge

Ray Eldath 52 Jun 26, 2022
Auto Judger for BUAA-SE-OOP Course (2021 Spring)

patpat Auto Judger for BUAA-SE-OOP Course (2021 Spring) 1. 评测机使用方法 1.1. 一些准备工作 1.1.1. 下载评测机 见 GitHub 中的 Releases,下载对应版本即可。目前提供 Windows, Linux, MacOS(I

null 28 Feb 27, 2022
The High Code Framework (low-code for devs)

hof - the high code framework The hof tool tries to remove redundent development activities by using high level designs, code generation, and diff3 wh

_Hofstadter 232 Jun 21, 2022
🎄 My code for the Advent of Code of year 2021 in Go.

Advent of Code 2021 This repository contains all code that I wrote for the Advent of Code 2021. This year I chose to try and learn Go. Enjoy! Built wi

Nick van Ravenzwaaij 0 Dec 9, 2021
Morse Code Library in Go

morse Morse Code Library in Go Download and Use go get -u -v github.com/alwindoss/morse or dep ensure -add github.com/alwindoss/morse Sample Usage pac

Alwin Doss 76 Jun 14, 2022
Automatically generate Go test boilerplate from your source code.

gotests gotests makes writing Go tests easy. It's a Golang commandline tool that generates table driven tests based on its target source files' functi

Charles Weill 4k Jul 1, 2022
XSD (XML Schema Definition) parser and Go/C/Java/Rust/TypeScript code generator

xgen Introduction xgen is a library written in pure Go providing a set of functions that allow you to parse XSD (XML schema definition) files. This li

null 166 Jul 1, 2022
Get user-like access to VirtualBox VMs from Go code.

#Vboxgo Get user-like access to VirtualBox VMs from Go code. This library wraps some define-tainted VirtualBox SDK functions, making it possible to ge

Vladislav Supalov 27 Oct 25, 2021
WeCTF 2020+ Source Code & Organizer's Writeup

WeCTF 2020+ Thank you all for participating! This README contains our writeup sketches. You can also share your writeup on CTFtime. Event Link: https:

WeCTF Organizers 23 Jun 29, 2022
Visualize how a projects source code is distributed among its files and folders

Source Code Visualizer Visualize the code distribution in a project. Applications Applications include: Visualizing code distribution for more educate

Guy Levin 79 Jun 13, 2022
Jennifer is a code generator for Go

Jennifer Jennifer is a code generator for Go. package main import ( "fmt" . "github.com/dave/jennifer/jen" ) func main() { f := NewFile("m

Dave Brophy 2.5k Jun 29, 2022
Universal code search (self-hosted)

Sourcegraph OSS edition is a fast, open-source, fully-featured code search and navigation engine. Enterprise editions are available. Features Fast glo

Sourcegraph 6.4k Jun 28, 2022
Yet another Go REPL that works nicely. Featured with line editing, code completion, and more.

gore Yet another Go REPL that works nicely. Featured with line editing, code completion, and more. (Screencast taken with cho45/KeyCast) Usage gore Af

Hironao OTSUBO 4.5k Jun 26, 2022
Nodebook - Multi-Lang Web REPL + CLI Code runner

nodebook Nodebook - Multi-Language REPL with Web UI + CLI code runner Useful to practice algorithms and datastructures for coding interviews. What is

Jérôme Schneider 1.6k Jul 5, 2022
Experimental code execution microservice based on Docker containers.

ranna ランナー - Experimental code runner microservice based on Docker containers. ⚠ PLEASE READ BEFORE USE First of all, this project is currently work i

ranna 20 Jun 28, 2022