6.824lab1解题

发表于 | 分类于

6.824-2020 Lab1: MapReduce count word

1
2
3
4
5
6
7
8
  input is (already) split into M files
  Input1 -> Map -> a,1 b,1
  Input2 -> Map ->     b,1
  Input3 -> Map -> a,1     c,1
                    |   |   |
                    |   |   -> Reduce -> c,1
                    |   -----> Reduce -> b,2
                    ---------> Reduce -> a,2

由于课程限制，这里只描述实现思路，不放具体代码

work

1
2
3
4
5
6
7
8
9
10
while true:
    get task from master.GetTask
    if task is map:
        Y = ihash(key) % nReduce
        generate mr-X-Y
        call master.DoneTask
    else task is reduce:
        generate mr-out-Y
        call master.DoneTask
    else exit

思路

  1. GetTask，可能有多个work获取同一个task（比如第一个任务已经超时了）， 所以要控制最后生成的文件名，先temp一个文件，在通过os.Rename原子操作改文件名
  2. 注意mr-X-Y中的key要排序

master

  1. GetTask: 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     while mapTasks not finished:
     try get mapTask
     if success:
         return mapTask
     else
         wait
 while reduceTasks not finished:
     try get reduceTask
     if success:
         return reduceTask
     else
         wait
 return finished
  2. DoneTask: 
    1
    2
    3
    4
    5
     if mapTask:
     mapTask set finished
 else
     reduceTask set finished
 notify all wait
  3. Done: 
    1
    2
     notify all wait
 return if reduceTasks finished
  4. 思路
    1. 怎样判断一个任务是否结束：用一个变量存储，任务成功后，做+1，由于多work的存在，要加锁
    2. 怎么获取任务：用数组，每个元素代表对于任务的状态，如果为0，则代表任务未分配， 如果为-1，则代表任务已完成，否则该状态应该为获取任务时的时间戳，这样也可以判断是否是超时的任务，这种方法需要锁保护（或者通过cas操作）