# Lab 4: Map Reduce on Fault-tolerant Distributed Filesystem
### Getting started
Before starting this lab, please back up all of your prior labs' solutions.
```bash
$ cd cse-lab
$ git commit -a -m "upload lab3-sol"
# Then, pull this lab from the repo:
$ git pull
# Next, switch to the lab4 branch:
$ git checkout lab4
# Notice: lab4 is based on lab3.
# Please merge with branch lab3, and solve the conflicts.
$ git merge lab3
# After merging the conflicts, you should be able to compile the new project successfully:
$ chmod -R o+w `pwd`
$ sudo docker run -it --rm --privileged --cap-add=ALL -v `pwd`:/home/stu/cse-lab lqyuan980413/cselab_env:2022lab4
/bin/bash
$ cd cse-lab
$ make clean && make
```
(Reference: MIT 6.824 Distributed Systems)
In this lab, you are asked to build a MapReduce framework on top of your Distributed Filesystem implemented in Lab1-3. **Make sure that you can pass all the tests in lab3 before you get start.**
You will implement a worker process that calls Map and Reduce functions and handles reading and writing files, and a coordinator process that hands out tasks to workers and copes with failed workers.
You can refer to [the MapReduce paper](https://www.usenix.org/legacy/events/osdi04/tech/full_papers/dean/dean.pdf) for more details (Note that this lab uses "coordinator" instead of the paper's "master").
There are four files added for this part: `mr_protocol.h`, `mr_sequential.cc`, `mr_coordinator.cc`, `mr_worker.cc`.
### Task 1
- `mr_sequential.cc` is a sequential mapreduce implementation, running Map and Reduce once at a time within a single process.
- You task is to implement the Mapper and Reducer for Word Count in `mr_sequential.cc`.
### Task 2
- Your task is to implement a distributed MapReduce, consisting of two programs, `mr_coordinator.cc` and `mr_worker.cc`. There will be only one coordinator process, but one or more worker processes executing concurrently.
- The workers should talk to the coordinator via the `RPC`. One way to get started is to think about the RPC protocol in `mr_protocol.h` first.
- Each worker process will ask the coordinator for a task, read the task's input from one or more files, execute the task, and write the task's output to one or more files.
- The coordinator should notice if a worker hasn't completed its task in a reasonable amount of time, and give the same task to a different worker.
- In a real system, the workers would run on a bunch of different machines, but for this lab you'll run them all on a single machine.
- MapReduce relies on the workers sharing a file system. This is why we ask you to implement a global distributed ChFS in the first place.
#### Hints
- The number of Mappers equals to the number of files be to processed. Each mapper only processes one file at one time.
- The number of Reducers equals is a fixed number defined in `mr_protocol.h`.
- The basic loop of one worker is the following: ask one task (Map or Reduce) from the coordinator, do the task and write the intermediate key-value into a file, then submit the task to the coordinator in order to hint a completion.
- The basic loop of the coordinator is the following: assign the Map tasks first; when all Map tasks are done, then assign the Reduce tasks; when all Reduce tasks are done, the `Done()` loop returns true indicating that all tasks are completely finished.
- Workers sometimes need to wait, e.g. reduces can't start until the last map has finished. One possibility is for workers to periodically ask the coordinator for work, sleeping between each request. Another possibility is for the relevant RPC handler in the coordinator to have a loop that waits.
- The coordinator, as an RPC server, should be concurrent; hence please don't forget to lock the shared data.
- The Map part of your workers can use a hash function to distribute the intermediate key-values to different files intended for different Reduce tasks.
- A reasonable naming convention for intermediate files is mr-X-Y, where X is the Map task number, and Y is the reduce task number. The worker's map task code will need a way to store intermediate key/value pairs in files in a way that can be correctly read back during reduce tasks.
- Intermediate files will be operated on your distributed file system implemented in lab 3. If the file system's performance is bad, it *shall not pass the test* !
### Grading
Before grading, we will first check your lab3 implementation using the grade script in lab3.
If lab3's tests fail, you can only get half of the score of lab4.
After you have implement part1 & part2, run the grading script:
```
% ./grade.sh
Passed part A (Word Count)
Passed part B (Word Count with distributed MapReduce)
Lab4 passed
Passed all tests!
Score: 100/100
```
We will test your MapReduce following the evaluation criteria above.
## Handin Procedure
After all above done:
```
% make handin
```
That should produce a file called lab4.tgz in the directory. Change the file name to your student id:
```
% mv lab4.tgz lab4_[your student id].tgz
```
Then upload **lab4_[your student id].tgz** file to [Canvas](https://oc.sjtu.edu.cn/courses/49245/assignments/197178) before the deadline.
You'll receive full credits if your code passes the same tests that we gave you, when we run your code on our machines.
没有合适的资源?快使用搜索试试~ 我知道了~
cse-lab-lab4
共84个文件
h:27个
cc:25个
sh:12个
需积分: 0 0 下载量 132 浏览量
2022-12-10
22:15:25
上传
评论
收藏 710KB ZIP 举报
温馨提示
no
资源推荐
资源详情
资源评论
收起资源包目录
cse-lab-lab4.zip (84个子文件)
cse-lab-lab4
test-lab1-part2-a.pl 3KB
extent_protocol.h 901B
test-lab4-a.sh 636B
mr_coordinator.cc 5KB
inode_manager.h 2KB
chfs_client.h 2KB
GNUmakefile 4KB
extent_smain.cc 764B
lang
algorithm.h 272B
verify.h 240B
extent_sdist_main.cc 1KB
grade.sh 2KB
gettime.cc 4KB
test-lab3-part5-b.sh 400B
mr_sequential.cc 3KB
raft_protocol.h 3KB
inode_manager.cc 11KB
part2_tester.sh 3KB
extent_client.cc 2KB
extent_server_dist.h 975B
test-lab1-part2-d.sh 853B
gettime.h 243B
test-lab1-part2-f.sh 993B
stop.sh 335B
assets
installsnapshot.png 145KB
snapshot1.png 62KB
leader_election.png 70KB
state.png 131KB
appendEntries.png 116KB
part5.png 42KB
test-lab1-part2-e.sh 680B
chfs_state_machine.cc 4KB
extent_server.cc 2KB
raft_test_utils.h 15KB
handle.cc 2KB
raft_protocol.cc 2KB
handle.h 2KB
rpc
thr_pool.h 3KB
pollmgr.cc 7KB
gettime.cc 4KB
fifo.h 2KB
jsl_log.h 694B
gettime.h 243B
connection.cc 10KB
method_thread.h 4KB
marshall.h 6KB
pollmgr.h 2KB
connection.h 2KB
rpctest.cc 11KB
rpc.cc 28KB
rpc.h 16KB
slock.h 334B
jsl_log.cc 109B
thr_pool.cc 1KB
fuse.cc 17KB
mytest_lab3.sh 382B
chfs_state_machine.h 2KB
raft_storage.h 4KB
raft_test.cc 21KB
test-lab4-b.sh 1KB
.gitignore 106B
mr_worker.cc 5KB
extent_client.h 761B
raft_state_machine.h 909B
mr_protocol.h 1KB
start.sh 1KB
test-lab1-part2-c.pl 4KB
chfs_client.cc 14KB
raft.h 28KB
README.md 5KB
extent_server_dist.cc 5KB
raft_test_utils.cc 6KB
test-lab3-part5-a.pl 5KB
test-lab3-part5.sh 2KB
extent_server.h 755B
novels
being_ernest.txt 19KB
dorian_gray.txt 28KB
frankenstein.txt 7KB
mr-wc-correct 38KB
sherlock_holmes.txt 19KB
lcoal-mr-wc-correct 38KB
metamorphosis.txt 37KB
tom_sawyer.txt 7KB
test-lab3-part5-b.cc 4KB
共 84 条
- 1
资源评论
矢泽狸
- 粉丝: 1
- 资源: 14
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Screenshot_20240522_084328_com.tencent.mm.jpg
- 附件计算机专业课选课说明-1.xlsx
- 基于TypeScript的ahousepet-admin-web管理系统设计源码
- 《广东开放大学学习指引》期末考核要求0522.zip
- mkl-2021.1.1-py2.py3-none-macosx-10-15-x86-64.whl
- mkl-2018.0.3-py2.py3-none-manylinux1-x86-64.whl
- halcon实现两幅图像相减
- mkl-2021.3.0-py2.py3-none-manylinux1-x86-64.whl
- IAR9.3主题配置,包含字体颜色等
- 才从简来.apk
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功