- Part I: word count
- 实现Map()和Reduce()函数，Map()返回包含Key/Value的list.List，Reduce()返回每个单词出现次数。
- Part II: Distributing MapReduce jobs & Part III: Handling worker failures
-
Example: test_test.go的TestBasic测试函数
-
setup() -> MakeMapReduce() -> InitMapReduce() -> StartRegistrationServer() -> Run() 注册RPC， 启动Master.
-
test_test.go文件注册worker并且启动Worker，worker等待从master发来的map以及reduce任务。
-
修改MapReduce结构，新增空闲通道idleChannel, 每次选择完成map或者reduce人物的空闲worker。
-
RunMaster()函数的任务就是master通过rpc远程调用，发送map或者reduce给空闲的worker，需要注意的是reduce任务必须在所有map任务执行完成之后才能开始做。
-
-
Part A: The Viewservice
- ViewService: 作为Master服务器（存在单点失败）， 用于检测各个Clerk（即实验中提到的server，这里充当client）的状态并且决定他们的角色（primary/backup）。
- View: 抽象概念，指的是当前场景的状态（谁是primary/backup以及当前的view编号）。
- 系统运行方式：Clerk每隔一个PingInterval向ViewServer发送一个Ping，告知server自己“活着”，同时server根据自己当前的状态，将Clerk标记为primary/backup或者不做任何处理，并且决定是否需要更新View，同时也回复Ping它的Clerk更新（?)之后的View。
- 什么时候需要更新View: 首先需要引入一个机制（Primary Acknowledgement），即Master向Primary回复了当前最新的View(i)，在下一个Ping中，Primary就会携带响应信息证明已经知道了这个View(i)的存在，当Master收到Ping之后，就能够确认Primary已经知道这个View(i)的存在，从而能够决定是否需要根据当前的状态更新View，可以从以下几个方面来考虑是否需要更新View
- Primary挂了。
- Backup挂了。
- 当前View中只有Primary，当一个idle server发来ping时，Master会将这个idle server设为Backup。
- server挂了之后又重启，Master如何得知：When a server re-starts after a crash, it should send one or more Pings with an argument of zero to inform the view service that it crashed
- 修改viewservice/server.go，新增几个状态变量，用于确定Primary/Backup是否Ack过View，以及Ping是否超时。
-
Part B: The primary/backup key/value service
- 可以用go内置类型map来保存"put"/"append"操作，但由于每个操作最多只能操作一下，因此还需要另外一个map来过滤同一个客户端提交的相同的操作；
- tick()函数每隔一定的周期ping一下viewservice，用于获取当前最新的view，如果发现当前的primary就是自己并且又有新的backup加入而且与自己先前知道的backup不同，那么这时候primary就需要和新加入的backup进行同步操作，调用SyncBackup()函数。
- 在PutAppend操作时，如果当前view的backup不为空，则需要将操作进行转发，转发过程中可能遇到网络延迟或者backup宕机，为了确保能够成功转发，需要一定的策略来判断。
-
Part A: Paxos
- 需理解Paxos算法的核心思想，分三个阶段：prepare阶段，server向其他server提交提案（pid, proposal_id）（包括自己），如果获得大多数server的认可，则进入accept阶段，当前server获得之前返回结果的最大值（最大值的定义可以参考文献，如果没有用自己的），提交提案（pid, proposal_id, max_value）之后如果获得大多数server的同意，则进入提案决定阶段，当前server将值发送给其余server。
proposer(v): while not decided: choose n, unique and higher than any n seen so far send prepare(n) to all servers including self if prepare_ok(n, n_a, v_a) from majority: v' = v_a with highest n_a; choose own v otherwise send accept(n, v') to all if accept_ok(n) from majority: send decided(v') to all acceptor's state: n_p (highest prepare seen) n_a, v_a (highest accept seen) acceptor's prepare(n) handler: if n > n_p n_p = n reply prepare_ok(n, n_a, v_a) else reply prepare_reject acceptor's accept(n, v) handler: if n >= n_p n_p = n n_a = n v_a = v reply accept_ok(n) else reply accept_reject- Start()函数用于提交一个序号为seq，价值为v的提案。
- Status()函数用于返回序号为seq的proposal最后返回的status以及被大多数server接受的value。
- Min()返回目前为止提交的proposal的最小序号
- Max()返回目前为止提交的proposal的最大序号
- Done()返回当前server已经接受序号为seq的提案。
-
Part B: Paxos-based Key/Value Server
- 判断at-most-once的思路和lab2差不多，就是用一个map[string]int来判重，通过在GetArgs以及PutAppendArgs结构体中增加一个唯一的Uid来区分。
- 关于同步的问题，每次Get或者PutAppend之前必须先同步所有serve 551A r状态，对于当前接受请求的server，如果当前提交的请求序号小于所能看到的最大的序号，则说明该server没有达到最新的状态，此时需要等待server与别的server进行同步，通过proposalInstance函数获得提交序号为seq的value，然后更新自身server的状态。
- Part A: The Shard Master
- 主要难点在于如何让每个group分到的shard数目均匀（差值不超过1），可以这样做：对于join操作，每次都找shard最多的那个group，然后分一个shard给新加入的group，反复操作直到达到平均水平；对于leave操作，每次找shard最少的那个group（需要注意的是这个group不能是要丢弃的group）,然后将要丢弃的group中的shard重新分配给这个最少shard的group，如此反复直到要丢弃的group中的shard被分完。