[1][lecture] Introduction to distributed system

6.824 2018 Lecture 1: Introduction

summary

什么是分布式系统？（多机器，核心组件是多机器，比如map reduce系统）

为什么学习分布式？（组织物理隔离的不同机器/实现物理隔离/失败恢复/横向扩展）

分布式复杂度？（并发/网络引入的失败，超时，网络中断，硬件故障）

why本课程？（有趣且有难度/现实中实际应用很多/活跃的研究领域/实际开发分布式系统）

内容（lecture/paper/lab）

目标（深刻理解分布式的重要技术/获取分布式系统经验）

labs（MR/replication for ft with raft/ft kv/shared kv）

Big Topics

1. 实现（rpc，threads，并发模型）
2. 性能（scale out、负载均衡，计算存储网络瓶颈）
3. 错误容忍（可用性/可恢复性 通过replication）
4. 一致性（设计可用性和一致性的权衡，扩展性和一致性的权衡）

paper MR

什么是MR？(>1000台机器并发计算1000TB数据，比如社交网络Web数据，设计目标是非分布式专家也可以很容易上手使用，容易处理数据分割并且自动并发在多机环境下，获得横向扩展性，屏蔽底层分布式细节给客户)

首先输入（N份输入）分割成M个文件（存储在GFS中），map函数(M个map task)从GFS中读取K-V pairs，map处理结束后得到中间文件（存放在本机存储），reduce函数（R个reduce task）从map本机得到中间文件，reduce处理结束后存储在gfs中得到最终文件，map(k1,v1)->list(k2,v2) reduce(k2,list(v2))->list(k2,v3)

More details：
  master: gives tasks to workers; remembers where intermediate output is
  M Map tasks, R Reduce tasks
  input stored in GFS, 3 copies of each Map input file
  all computers run both GFS and MR workers
  many more input tasks than workers
  master gives a Map task to each worker
    hands out new tasks as old ones finish
  Map worker hashes intermediate keys into R partitions, on local disk
  no Reduce calls until all Maps are finished
  master tells Reducers to fetch intermediate data partitions from Map workers
  Reduce workers write final output to GFS (one file per Reduce task)
  
Example: word count
  input is thousands of text files
  Map(k, v)
    split v into words
    for each word w
      emit(w, "1")
  Reduce(k, v)
    emit(len(v))

论文写作2003年网络带宽是瓶颈，因此做了较多在网络上的优化？

• map task会优先找计算节点本地存了gfs三副本数据的作为执行task节点
• map计算后写本地，而不是gfs

如何处理负载均衡问题？

• N >> M,R
• 最后的任务会开启多个计算防止长尾计算延长计算时间

如何处理错误容忍？

1. 某个MR task失败，可以直接由master重新计算失败的task（MR要求MR任务为纯函数计算，无状态，该设计保障了简单性，但也失去了一些普适性）
2. map fails，master re-map，reduce读取会失败也会re-reduce，读取成功继续计算即可
3. reduce worker失效，依赖gfs提供的原子重命名技术，保障一致性
4. master 发放同一个map task多次，master在执行reduce发放时只会指定其中一个map
5. master 发放同一个reduce task多次，依赖gfs原子重命名
6. 某个work节点非常慢，master会启动备份计算
7. 某个work节点计算错误，mr假设 fail-stop硬件模型，无法处理这种错误
8. master失效，checkpint重启，job失败客户端重启

不适用于MR的场景？

1. 数据量太小
2. 大量数据的小部分更新
3. map recude无状态，不能根据情况来随意读取
4. page-rank，过多的shuffle，低效率

适用于MR场景？

1. 全量建立web检索索引
2. 分析点击量，推荐广告系统
3. 对所有数据跑同样的操作，如去除某种状态的doc
4. 重建倒排索引/分析点击量/过滤点击模式

Conclusion
  MapReduce single-handedly made big cluster computation popular.
  - Not the most efficient or flexible.
  + Scales well.
  + Easy to program -- failures and data movement are hidden.
  These were good trade-offs in practice.