MIT 6.824 Distributed Systems 课程笔记

Study

schedule：https://pdos.csail.mit.edu/6.824/schedule.html
中文视频：https://www.bilibili.com/video/BV1x7411M7Sf
视频翻译：https://www.zhihu.com/column/c_1273718607160393728

MapReduce论文翻译：https://zhuanlan.zhihu.com/p/122571315
GFS论文翻译：https://www.zhihu.com/column/c_1215668784864190464

分布式系统

https://www.bilibili.com/video/BV1x7411M7Sf P1~P4

分布式系统的目的：
parallelism / performance（并行/性能）
scalability（可扩展性）：$k$倍的计算机或资源，可获得$k$倍的性能或吞吐量。

fault tolerance（容错）
availability（可用性）：当遇到某些故障时，依然能提供可用的服务（故障较多或不可解决时，停止响应）。
recoverability（可恢复性）：故障修复后，系统可再次正确运行；故障发生时，数据不会丢失。
实现方式：
non-volatile memory（NVM，非易失性存储）
replication（保存副本）：问题：keep consistency，保持一致性。
最简单的强一致性方案：一主多从架构，master写入，slave做读取，client写入master后，master同步数据到所有的slave，等所有的slave返回ack后，响应client写入成功。

physical（物理原因）
比如不同地区的计算机一起工作。

security / isolated（安全/隔离）
将工作分解，通过不同计算机/程序完成。

困难：
concurrency（并发）
partial failure（局部错误）
performance（性能）

CAP理论

https://blog.csdn.net/chen77716/article/details/30635543

C（consistency, 一致性）：所有的节点上的数据时刻保持同步。
A（availability, 可用性）：只要收到用户的请求，服务器就必须给出回应，无论请求成功或失败。
P（partition tolerance, 分区容错）：系统应该能持续提供服务，即使系统内部进行了分区，即节点间可能有消息丢失/通信失败。
CAP理论：（强）一致性、可用性和分区容错性无法在分布式系统中被同时满足，最多只能满足其中两个。
适用于基于原子读写的NoSQL场景。

分布式系统的目的是performance，performance需要sharding(分片)，sharding会导致faults，需要tolerance，tolerance需要replication，replication导致inconsistency，实现consistency就会导致low performance。
每一方面都有成本。

对整个网络一段时间产生的数十亿兆字节的数据构建索引，基本相当于对这些数据进行排序。

MapReduce
一个Map或Reduce任务，称作task；所有task，称作job。
一个worker通常执行多个task（运行多个进程）。
Reduce Worker通过RPC处理Map Worker输出的数据，然后发送最终结果。总是在本地运行，所以通信代价不高。

shuffle：将每个Map Worker生成的数据（包含多个不同的key）按照key重新分组（以便能将数据转移到Reduce Worker）。

多线程

https://www.bilibili.com/video/BV1x7411M7Sf P5~P8

事件驱动 event-driven
如epoll？

对数据结构的操作本身绑定一个锁，而不是在代码中
可以但是看情况。不进行共享时会影响效率。当两个带锁数据结构互相调用时，可能会引起死锁。此时应删除锁，即将锁放到该实现的外面。
也存在类似的数据结构，如 sync.Map。
go 的 map 在并发情况下，只有读是线程安全的，同时读写是线程不安全的。
可以在操作前进行加锁，但go提供了效率更高、并发安全的 sync.Map。sync.Map 和 map 不同，并不以语言原生形态提供，而是在 sync 包下的特殊结构。
sync.Map 为了保证并发安全有一些性能损失，因此在非并发情况下，使用 map 会有更好的性能。
sync.Map 有以下特性：

• 无须初始化，直接声明即可。
• sync.Map 不能使用 map 的方式进行取值和设置等操作，而是使用 sync.Map 自身的方法进行调用，Store 表示存储，Load 表示获取，Delete 表示删除。
• 使用 Range 配合一个回调函数进行遍历操作，通过回调函数返回内部遍历出来的值，Range 参数中回调函数的返回值在需要继续迭代遍历时，返回 true，终止迭代遍历时，返回 false。
• sync.Map 没有提供获取元素数量的方法，替代方法是在获取 sync.Map 时遍历自行计算数量。

协作 coordination
程序/线程间需进行交流，可能需要等待对方。
go 提供的工具：channel，sync.Cond，sync.WaitGroup。
这些工具就是管程，即一个封装好了数据和互斥操作的抽象数据类型，可以放心使用。（就是在数据结构本身加了锁）

-race
go run中加入-race可开启冲突检测。
race检测器会在每个用到的内存位置处，分配一点内存（影子内存）来记录该位置近期是否被线程写入或读取。
检测器不能静态分析，只有在执行过程中才可能检测到race。但也不是真的出现问题的race才会被检测到。有的可能没有发生冲突但也可被检测。
应使用race检测运行多组测试数据。

GFS

• 运行在单个数据中心(single data center)（副本之间距离近，不能分布在不同地方）
• 只供内部使用(internal use)，对外提供GFS实现的服务。
• 适用于大文件的顺序读取(big sequential access)，而不是小型数据的随机读取(random access) 。
• 并不保证结果一定完全正确（弱一致性），但搜索系统本身容错率高，这样并没有问题。

master主要包含两张表：
1. 文件名 到 该文件属于哪个/哪些块的映射：file name -> chunk handles。
2. 每个块的信息：它位于哪些块服务器上，它当前的版本，它的primary副本位于哪个块服务器，过期时间：chunk handle -> list of chunkservers, version, primary chunkserver, lease expiration。

primary chunk是块的一个副本，master只用primary chunk进行是否过期的判断。

master将上面的两张表全保存在内存中。为了应对崩溃，硬盘中也会以日志格式保存这些信息。所以读在内存中，写一般在硬盘中。
上面用到的信息中，list of chunkservers存储在内存中，每次重启后重新获取。primary同样，每次重启master在发现没有primary后，重新指定一个合适的。expiration也是。
chunk handles, version, log, checkpoint保存在硬盘中，避免信息丢失。

master重启后，会回滚到最近的checkpoint处（即WAL, Write Ahead Log，预写日志）。

大概再看P10