[关闭]
@SovietPower 2022-05-18T15:00:06.000000Z 字数 3159 阅读 753

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(可扩展性):倍的计算机或资源,可获得倍的性能或吞吐量。

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 有以下特性:

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

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

GFS

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注