6.824-Class-Schedule-Notes

[0XFF-96]

大纲

• 课程主页: https://pdos.csail.mit.edu/6.824/

[0XFF-96]

上这门课的前提

To do well in 6.824, you should already be familiar with computer systems to the level of 6.033 and 6.004, and you should be good at debugging, implementing, and designing software, perhaps as a result of taking programming-intensive courses such as 6.828 and 6.035.

• [ ] : https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-004-computation-structures-spring-2017/
• [ ] : https://pdos.csail.mit.edu/6.828/2019/ 操作系统
• [x] :

[0XFF-96]

Lecture 1: Introduction

Note: https://pdos.csail.mit.edu/6.824/notes/l01.txt

什么是分布式系统？

为什么需要分布式系统？

为什么需要选择这门课程？

需要完成的四个实验 ？

• Lab 1: MapReduce
• Lab 2: replication for fault-tolerance using Raft
• Lab 3: fault-tolerant key/value store
• Lab 4: sharded key/value store

这门课的不同主题？

This is a course about infrastructure for applications. Storage, Communication, Computation.

• Implementation
• Performance
• Fault tolerance
• consistency

[0XFF-96]

Lec 1

• [x] Introduction [done]
• [x] paper: MapReduce
• [x] lab1, MapReduce

[0XFF-96]

Case Study: Map Reduce

论文阅读笔记📒

1、https://lvsizhe.github.io/course/2020/03/mapreduce.html 2、https://zhuanlan.zhihu.com/p/64854013

论文阅读

MR 模型成功的三个原因？

• easy to use
• easily expressible as MapReduce
• implementations can scale and leverage resources.

Learned thing from this work

• the benefit of restricting the programming model
• network bandwidth is a scarce resource
• redundant execution are beneficial

[0XFF-96]

视频导读：what is a map reduce?

• [ ] : https://www.youtube.com/watch?v=cvhKoniK5Uo 3 星、word count
• [ ] : https://www.youtube.com/watch?v=s8EPQpgpWVE

resource

• udacity 的 big data 课程，https://www.udacity.com/course/intro-to-hadoop-and-mapreduce--ud617

[0XFF-96]

论文：MapReduce: Simplified Data Processing on Large Clusters

a brief note of this paper

Abstract

• programming model and implementation for processing and generating data sets
• partitioning, scheduling, handling failures, inter-machine communication

Users specify a map function that processes a key/value pair to generate a set of intermediate key/value pairs, and a reduce function that merges all intermediate values associated with the same intermediate key

Intro

• 有几个应用场景：request logs, inverted indices
• 特点是 computations -> straightforward. Input is large
• inspired by the map and reduce primitives present in Lisp
• 主要贡献：The major contributions of this work are a simple and powerful interface that enables automatic parallelization and distribution of large-scale computations

Programming Model Example

• word count example
• Distributed Grep
• count of url access frequency
• Reverse web-link graph
• term-vector per Host
• Inverted index
• Distributed Sort

Implementation

requirement:

• Machines
• Commodity networking hardware
• a cluster
• storage
• users submit jobs scheduling system

What happens if a user calls the mapReduce function ?

( 论文提到 7 点） keywords: master, worker, reduce worker, intermediate result

• splits
• master assigns work to worker
• worker reads the contents of the corresponding inputs
• buffered pairs are written to local disk
• reduce worker is notified by master about the locations
• reduce worker iterates over the sorted intermediate data. count unique key
• when tasks have been done, the master wakes up the user program.

master data structures

• 略

Fault Tolerance

• worker failure: all workers are notified are reexecution.
• master failure: a new copy can be started from the last checkpointed
• semantics in the presence of failures, 一样的输入，一定会得到一样的输出 ？

Locality: network bandwidth is a scarce resource

Task Granularity

• practical bounds on how large M and R should be ?