HuRan's BlogMIT6.824 分布式系统-笔记
MIT6.824 分布式系统-笔记
本文结合mit6.824视频课程和这位同学的笔记
Introduce 导入
对于分布式系统的基础设施有以下的抽象：
- Storage，存储，一个很直接并常用的抽象；如何构建多副本、容错、高性能分布式存储系统。
- Communication，通信，如何可靠的通信。
- Computation，现代的大规模计算，如 MapReduce
最终理想是提供能够屏蔽分布式细节的、类似于单机的通用接口，同时能兼具容错和性能。
- RPC：像在本机调用一样跨节点通信
- Concurrency，Threads：并发载体
- Concurrency，Lock：并发控制。
Performance 性能
scalability，伸缩性
- 可以线性的集结计算机资源：使用两倍的机器获取两倍的吞吐。
- 意味着遇到瓶颈你只需要花少量的钱买机器，而不用付很多的工资找程序员重构。
- 但这个特点很难实现。可伸缩性是我们追求的目标，但这样的伸缩性通常有瓶颈
Fault Tolerance 容错
单机虽好，作为上千台机器组成的集群来说，故障却是常态。比如说：
- 主机宕机
- 网络抖动
- 交换机故障
特性
- Availability 可用性：出现故障也仍然运行，并且通知你；一个副本失败，其他副本继续运行。
- Recoverbility 可恢复性，无干预 、不影响正确性的可恢复
对应手段
- NV storage：持久化（非易失性）
- Replication：多副本
Consistency 一致性
分布式系统产生不一致的因素
- 缓存
- 多副本
- 一个服务器有两个副本，都有数据，但是version不同。在同步时一台宕机了，导致数据不一致。
不同程度的一致性：
-
强一致性：每个客户端每次都能读到（自己 or 他人）之前所写数据。在多副本系统实现强一致性代价十分高昂，需要进行大量的通信。简单说两种方法：
- 每次更改同时写到所有副本
- 每次读取都去读所有副本，使用具有最新时间戳的数据。
-
弱一致性，为了性能，工业级系统通常选择弱一致性。
强一致性（Strict Consistency） 系统中的某个数据被成功更新后，后续任何对该数据的读取操作都将得到更新后的值；
也称为：原子一致性（Atomic Consistency）线性一致性（Linearizable Consistency）
两个要求：
任何一次读都能读到某个数据的最近一次写的数据。 系统中的所有进程，看到的操作顺序，都和全局时钟下的顺序一致。 简言之，在任意时刻，所有节点中的数据是一样的。
例如，对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。
总结：
一个集群需要对外部提供强一致性，所以只要集群内部某一台服务器的数据发生了改变，那么就需要等待集群内其他服务器的数据同步完成后，才能正常的对外提供服务。 保证了强一致性，务必会损耗可用性。
顺序一致性（Sequential Consistency） 两个要求：
任何一次读都能读到某个数据的最近一次写的数据。 系统的所有进程的顺序一致，而且是合理的。即不需要和全局时钟下的顺序一致，错的话一起错，对的话一起对。 弱一致性 系统中的某个数据被更新后，后续对该数据的读取操作可能得到更新后的值，也可能是更改前的值。
但即使过了“不一致时间窗口”这段时间后，后续对该数据的读取也不一定是最新之；
所以说，可以理解为数据更新后，如果能容忍后续的访问只能访问到部分或者全部访问不到，则是弱一致性。
最终一致性 是弱一致性的特殊形式，存储系统保证在没有新的更新的条件下，最终所有的访问都是最后更新的值。
不保证在任意时刻任意节点上的同一份数据都是相同的，但是随着时间的迁移，不同节点上的同一份数据总是在向趋同的方向变化。
简单说，就是在一段时间后，节点间的数据会最终达到一致状态。
弱一致性与最终一致性区别 弱一致性即使过了不一致时间窗口，后续的读取也不一定能保证一致，而最终一致过了不一致窗口后，后续的读取一定一致，才能说清楚弱一致和最终一致的区别
CAP理论：
一个分布式系统最多只能同时满足
- 一致性（Consistency）
- 可用性（Availability）
- 分区容错性（Partition tolerance）
这三项中的两项
MapReduce
背景
Google （2003 年左右）面对巨量（数十 T）的索引数据和全网结构的数据，需要找到最重要的网页。可以简化为一个排序问题，但如此数量级的排序，单机不是一个可选项。而又不是所有工程师都有手撸分布式系统的能力，因此产生了做一个分布式框架的需求，以对应用程序员屏蔽分布式环境细节：
- 如何将工作高效分配到上千台机器上。
- 如何控制数据流动。
- 如何进行容错。
存储配合
为了更好的并行读写，需要一个网络文件系统来配合输入和输出，这就是 GFS（谷歌文件系统）。
GFS 可以简单理解为，一个将大文件拆为一个个小的 64M 的块分散到不同机器上网络文件系统。
网络开销
为了尽量绕开当时的主要瓶颈（网络传输），Google 做了一系列优化，包括 GFS 和 MR 跑在一个集群上，以减少读取和写入数据的网络传输。具体做法是让 Map 任务（Map Task）去找数据（Block）—— 将 Task 调度到其输入所在的机器上。但对于 Reduce 任务，无论如何都会存在大量网络开销：GFS 对数据都进行了冗余备份，意味着每个结果都要写多次。
不过，时下的数据中心可以通过很多手段使得网络传输的速度大大提高，比如使用多个根路由器进行分摊流量，意味着在设计时可以有更多灵活性，不用太为网络传输而优化。
RPC
线程（Threads）
线程为什么这么重要？因为他是我们控制并发的主要手段，而并发是构成分布式系统的基础。在 Go 中，你可以将 goroutine 认为是线程，以下这两者混用。 每个线程可以有自己的内存栈、寄存器，但是他们可以共享一个地址空间。
GO使用原因
IO concurrency（IO 并发）: 一个历史说法，以前单核时，IO 是主要瓶颈，为了充分利用 CPU，一个线程在进行 IO 时，可以让出 CPU，让另一个线程进行计算、读取或发送网络消息等。在这里可以理解为：你可以通过多个线程并行的发送多个网络请求（比如 RPC、HTTP 等），然后分别等待其回复。
Parallelism（并行）：充分利用多核 CPU。
关于并发（concurrency）和并行（parallelism）的区别和联系，可以看这篇文章。记住两个关键词即可：逻辑并发设计 vs 物理并行执行。
Convenience（方便）：比如可以在后台启动一个线程，定时执行某件事、周期性的检测什么东西（比如心跳）。
Q&A：
- 不使用线程还能如何处理并发？基于事件驱动的异步编程。但是多线程模型更容易理解一些，毕竟每个线程内执行顺序和你的代码顺序是大体一致的。
- 进程和线程的区别？进程是操作系统提供的一种包含有独立地址空间的一种抽象，一个 Go 程序启动时作为一个进程，可以启动很多线程（不过我记得 Goroutine 是用户态的执行流）。
并发导致的问题
数据共享问题
共享内存易出错。一个经典的问题是，多个线程并行执行语句：n = n + 1 时，由于该操作不是原子操作，在不加锁时，很容易出现 n 为非期望值。
我们称这种情况为竞态 （race）：即两个以上的线程同时试图改变某个共享变量。
解决的方法是加锁，但如何科学的加锁以兼顾性能并避免死锁又是一门学问。
Q&A：
- Go 是否知道锁和资源（一些共享的变量）间的映射？Go 并不知道，它仅仅就是等待锁、获取锁、释放锁。需要程序员在脑中、逻辑上来自己维护。
- Go 会锁上一个 Object 的所有变量还是部分？和上个问题一样，Go 不知道任何锁与变量之间的关系。Lock 本身的源语很简单，goroutine0 调用 mu.Lock 时，没有其他 goroutine 持有锁，则 goroutine0 获取锁；如果其他 goroutine 持有锁，则一直等待直到其释放锁；当然，在某些语言，如 Java 里，会将对象或者实例等与锁绑定，以指明锁的作用域。
- Lock 应该是某个对象的私有变量？如果可以的话，最好这样做。但如果由跨对象的加锁需求，就需要拿出来了，但要注意避免死锁。
协调（Coordination）
与不同线程之间交流，确认数据是否已经生成直接消费/未生成需要等待。
- channels：go 中比较推荐的方式，分阻塞和带缓冲。
- sync.Cond：条件信号机制。
- waitGroup：阻塞知道一组 goroutine 执行完毕，后面还会提到。
死锁（DeadLock）
产生条件：多个锁，循环依赖，占有并等待。
- T1等待T2，T2也在等待T1.T1有A需要B，T2有B需要A。
- 解决方法：
- 顺序加锁：所有线程按照先A后B加锁
- 死锁判定：判定为死锁后，全部资源解锁。一个个唤起
如果你的程序不干活了，但是又没死，那你就需要看看是否死锁了。