MIT 6.824-Intro

1. 背景

学习分布式系统相关知识，系统性的补全相关概念知识，为找暑期实习和秋招做准备。

使用的一些学习资料如下：

• 视频：
  • MIT《分布式系统|MIT 6.824 Distributed Systems 2020》中英字幕
• 课程主页：Schedule
• 相关博客：
  • MIT 6.824学习笔记
  • MIT 6.824 2020 视频笔记

2.学习方式

1. 快速阅读下推荐论文。
2. 打算先快速过一遍视频，对概念有个印象，每节课整理笔记。
3. 把优质博客的内容过一过，查缺补漏。
4. 争取将课程实验都完整的做一遍。

3. MapReduce论文笔记

3.1 编程模型

MapReduce 编程模型的原理是：利用一个输入 key/value pair 集合来产生一个输出的 key/value pair 集合。

MapReduce 库的用户用两个函数表达这个计算： Map 和 Reduce：

• 用户自定义的Map 函数接受一个输入的 key/value pair 值，然后产生一个中间 key/value pair 值的集合。MapReduce 库把所有具有相同中间 key 值 I 的中间 value 值集合在一起后传递给 Reduce 函数。

• 用户自定义的Reduce 函数接受一个中间 key 的值 I 和相关的一个 value 值的集合。Reduce 函数合并这些value 值，形成一个较小的 value 值的集合。

类型表示：

• map(k1,v1) -> list(k2,v2)。表示由输入得到中间输出，两者的key和value都在不同的域上，所以分别用k1/k2、v1/v2区分了
• reduce(k2,list(v2)) ->list(v2)。而reduce输出对应的key和value和上面的中间输出结果的域是相同的，也是用k2、v2表示

示例：论文里有好几个示例，这里选取几个：

• 计算 URL 访问频率：
  • Map 函数处理日志中 web 页面请求的记录，然后输出(URL,1)。
  • Reduce 函数把相同URL的value值都累加起来，产生(URL,记录总数) 结果
• 倒排索引：
  • Map 函数分析每个文档输出一个(词,文档号)的列表
  • Reduce 函数的输入是一个给定词的所有(词，文档号)，排序所有的文档号，输出( 词, list(文档号) )。
• 分布式排序：
  • Map 函数从每个记录提取 key，输出(key,record)
  • Reduce 函数不改变任何的值。这个运算依赖分区机制和排序属性。

3.2. 总体执行流程

通过将 Map 调用的输入数据自动分割为 M 个数据片段的集合， Map 调用被分布到多台机器上执行。输入的数据片段能够在不同的机器上并行处理。

使用分区函数将 Map 调用产生的中间 key 值分成 R 个不同分区（例如 hash(key) mod R）， Reduce 调用也被分布到多台机器上执行。分区数量（R）和分区函数由用户来指定。

总体执行流程示意图：

4. 视频笔记

4.1 课程会讨论到的相关概念

这门课是一门关于基础设施建设的课程。
基础设施建设通常包括：

• 存储
• 通信
• 计算

我们在建设分布式系统时，希望隐藏其分布式特性，使其看起来和用起来都像是单机系统，当然这是理想化的，很难实现。

针对这些抽象，我们会有一下几个topics：

• RPC：远程过程调用
• Threads：多线程并发
• Concurrency Control：数据一致性
• Performance：更好的性能
• Scalability：希望系统的性能随着设备拓展是线性的
• Falut Toleran：分布式系统会极大程度增大错误的发生，所以容错机制非常重要。
  • availability：在系统出现故障时仍能提供可用的服务，比如一个副本服务器故障，另一个副本可以提供服务。
  • recoverability：可以在出错后恢复正确的状态。
    1. 使用非易失性存储设备，记录日志等。
    2. replication，存储多个副本。
• Consistency：
  • 假设我们支持俩种操作
    • put(k,v)
    • get(k) -> v
  • 因为在分布式系统中有很多副本，所以会引出一致性问题，因此在系统可能存在很多不同版本的kv对。
    • 强一致性：保证每次get都能拿到最新的数据
      1. 保证数据一致性的开销很大。
    • 弱一致性：不保证每次get都能拿到最新的数据
      1. 当副本之间相隔很远，可以考虑保证弱一致性。为了保证俩个副本的独立性，一般不同的副本会保存在不同的物理位置上。

4.2 MapReduce

MapReduce时Goole提出的一项工作，其背景是对TiB级别的数据进行计算。比如建立网页索引，进行排序等。所以Google希望使用大量的计算机去运行大量的任务。他们希望一个framwork让不同背景的工程师编写程序去将他们的计算任务分散到不同的计算机上进行计算。

示例：word count
Input 1 -> Map a,1 b,1
Input 2 -> Map b,1
Input 3 -> Map a,1 c,1

收集
所有的a，1给一个reduce实例 -> a,2
所有的b，1去一个reduce实例 -> b,2
…

示例：
Map(k,v)
函数输入k是文件名，v是文件内容，功能是把划分成不同的words，对于每个words：emit(word,1)

Reduce(k,v)
emit(len(v))

几乎所有Map操作设计的数据都是在本地的而不需要网络通讯，否则网络通讯开销很大。但是所有的map产生发的结果还是需要集中到一个reduce实例所在的服务器上，通信开销还是很大。