分布式系统笔记一
lecture 1 简介lecture 2 -- RPC(远程过程调用） and Threadslecture 3 --- GFS
分布式系统笔记一lecture 1 简介
分布式系统的简介
parallelism 性能
ioslate 隔离
分布式系统的复杂在于机器多之后，在不同的网络环境下会出现意向不到 的故障。除此之外，机器本身也会出现故障。
分布式挑战：并发 分区错误 性能
同一个代码在多台计算机上运行 引发安全问题
性能和容错
并发编程 时序问题
设计分布式系统的根本原因是想获得更好的性能performance
四次实验:
Lab 1–MapReduce
Lab 2–Raft算法 为了实现容错
Lab 3–K/Ｖserver 可以完成复制和容错
Lab 4–分片式KV服务 把KV服务器分发到一系列独立的集群中，通过切分KV存储系统。通过这些独立的副本集群进行加速，并行的对集群进行多个复制
重点内容
基础设施 （存储 通信和计算问题
存储是最重点的是存储部分，关于人们如何构建和使用存储系统，以及如何去构建一种可复制容错的、高性能的分布式存储实例
通信是建立分布式系统的工具
对于存储和计算，学习目标是需要研究一些抽象方法，比如如何简化这些分布式存储和计算基础设施的接口设计，以此构建应用。最重要的是我们希望通过构建这种抽象的接口，将这些分布式特性隐藏在整个系统中而不被用户感知（极高的运算性能和容错的分布式系统。
话题一：实现 RPC 多线程 并发控制
话题二：性能，通过伸缩机器能达到性能的提升
分布式系统的目标：当遇到负载问题时，只需要通过加机器就可以解决，而不是通过程序员重新设计开发一套新的；
在系统中，伸缩随着n系数的增加，会面临一些困难：
1、内部负载不均衡
2、长尾问题(执行时间 执行效率问题），相同的任务在不同的机器上面执行的效率不一样
3、有些不能并行执行的代码：初始化、交叉执行
4、共享资源的瓶颈：网络
分布式也不是一劳永逸的，有些性能其实也没那么容易解决：
1、个别用户的响应时间过长（长尾）
2、多个用户希望同更新同一数据
需要认识到的一个问题是：故障出现的时间永远不确定，故障是一个很常见的问题。
对于分布式软件，我们期望：
1、可用性 尽管出现了部分故障也能继续提供服务
2、可恢复性 故障处理后，不需要额外的处理就能继续工作
服务器副本
如果某台服务器出现问故障，可以让副本继续提供服务。容错不只是单单的多台服务器即可，应该要保证在不同的区域。例如，机房虽然有多台服务器，但是这不是一个分布式系统。
远程调用RPC
对于本课程，线程提供了一种结构化的并发操作方式
可用性 可恢复性 非易失性存储 复制
一致性 强一致性需要更昂贵的通信
通用的基础结构需要定义明确的行为。客户端先进行put(k,v)操作更新数据，然后通过Get(k)读取数据。此时应该保证所有的get(k)结果都是v
让所有的行为一致很难，因为在分布式系统中，你的数据是存在于副本（容错）的，并且存在于cashe,disk中；
比如：
1、副本很难保证一致性，如果要保证一致性，需要牺牲吞吐性
2、客户端可能在多过程更新的过程中出现失败
3、服务器可能在执行请求后发送响应之前时奔溃
4、网络分区可能会导致以为服务下线了，其实还在工作，俗称“脑裂”
一致性和性能是相对称的。强一致性需要额外的通信。譬如get()需要检查最新的put()操作（分布式不是单点）。
现在大多数分布式系统采用弱一致性来保证任务处理速度。譬如，get()时，不需要检查或等待put()
一致性和性能是目前分布式系统中讨论较多的地方。
MapReduce 是一种编程模型，用于大规模数据集的并行运算。
MapReduce可以说是开启了分布式系统在工业界的普遍应用。
MapReduce的诞生是为了解决希望在短时间内分析和处理几TB级别的数据。譬如：构建索引、排序、分析爬虫回来文档的Web结构
Map 映射 Reduce 归约
MapReduce 框架给每个key安排了一个Reduce调用
当前软件的实现是指定一个Map函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce函数，用来保证所有映射的键值对中的每一个共享相同的键组。
Map只关注函数的输入和输出
emit 发出 函数性函数 吞吐量
MapReduce 任务执行抽象图：
1、MR调用输入文件的map()任务，产生新的数据集合(k2,v2) —中间数据
2、MR根据提供的K2对数据v2进行规整
3、把key和value传递给reduce处理
4、最终根据一系列的(k2,v2)集合生成最终结果
例如可以用这个模型来完成单词计数的任务：
输入-切割文件-生成map任务-提取(shuffle)-reduce计算-生成结果
MapReduce的伸缩性能很好，N台worker可以带来N倍的速度
Map和Reduce的运行是并行的，不需要交叉执行
在分布式系统设计中，影响性能的不是CPU、硬盘、内存，而是网络。
Map()任务需要从GFS中读取输入文件，Reduce需要从Map读取产生的结果。发送reduce的结果文件到GFS。读和输出在排序任务时，所需带宽都比较大。值得注意的是，我们的MP机器大部分都是共享一台交换机的。而交换机本身是有限制的。
一些其他的细节：
所有的任务处理进度都存储在一台master上。并且此台机器需要负责任务分派
Map操作产生的文件立即写本地文件
Map需要把按hash生成的多个文件合并为一个发给reduce
当所有的map任务完成后，再由master分配执行reduce任务。并且每个reduce是单独写GFS的。
MR如何最大化的减少对网络的使用
所有的worker都运行有GFS和MR worker
Master会尝试在存储输入文件的GFS上执行MR任务
因此，输入是从本地磁盘（通过GFS）读取的，而不是通过网络读取的。
中间数据仅通过网络传输一次
Map直接写本地磁盘，Reduce直接从Map的worker读取文件，而不是通过GFS
中间文件会根据hash分为多个
R比键的数量少
大型网络的传输效率更高
MR是如何获取良好的负载均衡的
如果N-1台服务器需要等待最后一台完成任务，是一种巨大的浪费。
某些任务花费的时间会比其他的任务执行时间要长
解决方案：把任务切分的比worker多
master在发送新任务时，先发送给哪些之前先执行任务的机器。同一时间，执行速度快的worker要比执行速度慢的woker执行的任务要多
根交换机
MapReduce如何处理容错？
如果某个worker在执行MR任务时崩溃了。（面向应用开发程序员我们应该隐藏这个细节）
MR是否需要必须从开头执行整个任务？为什么不需要？
MR只需要运行失败的map和reduce任务。
假设map任务执行了两次，一个reduce任务执行看到了第一次执行map任务的结果，另外一个reduce任务看到的是第二个。那么这种情况需要重新执行整个过程。除此之外，可以把map和reduce设计成为一个纯确定性函数。参数决定结果
没有状态，没有文件I/O，没有交叉、没有额外的通讯。假设此时你需要容忍非纯确定的函数怎么办？
当某个worker失败时，解决方式要不是通过全部重新执行。或者是回到某个系统的快照（你可能需要增加这部分的逻辑）
worker故障恢复细节
Map woker故障
master注意到worker不再响应。
master因为保存了所有该worker执行的任务编号，把任务发给其他worker执行。之前的中间文件丢失了，需要重建
如果Reduce读取了从之前崩溃的worker的中间数据，则可以丢弃重新运行.
Reduce worker故障
已经执行完成的任务可以保留，因为文件存储在GFS，存在副本
Master重启未完成的任务在其他worker执行
其他问题思考：
如果master给两个worker发送了相同的Map任务怎么办？master认为其中一个，此时master只会告诉reduce worker只存在一个
如果master给两个 reduce work发送了相同的任务怎么办？他们会尝试写相同的文件到GFS。GFS是rename是原子性的，可以保证只会存在一个输出结果文件
如果有一台worker执行任务非常慢，怎么办？master应在其他机器执行发送到该机器的其他任务。
如果因为计算机硬件导致计算结果错误怎么办？
如果master挂了怎么办？
总结
MapReduce让分布式处理变得流行。
它不是最有效和最灵活的系统。
扩展性非常好。
面向应用开发程序员友好，把数据转移和故障隐藏了起来。
里面包含了很多trade-off实践。
lecture 2 – RPC(远程过程调用） and Threads
为什么是Golang
Go语言：Go是类型安全和内存安全的语言，垃圾回收机制可以尽可能的帮我们消灭大量的bug
go对多线程良好的支持，每个线程拥有自己的执行栈
线程 锁 线程间同步
IO并发
使用多线程的原因？
多线程是一个结构化工具；多线程允许一个程序在执行时去做很多事情；
线程可以共享内存，每个线程都有自己的线程状态：线程计数器、寄存器、栈
1、使用多线程可以让我们同时发起多个网络调用，所有的线程都会等待回复
2、使用多线程的另一个重要原因是多核并行，多线程可以并发执行；
并行化：通过运行多个线程，一个线程调用一个内核，因此可以充分使用计算机内的多个内核，使用更多的CPU核时钟，提高运行速率和效率。
（多核性能：并行的在多个CPU执行代码）
3、易用性
IO并发：多个客户端同时发送请求到多台server，并且等待响应。服务器处理多个客户端请求，每个请求可能会阻塞。譬如客户端X读取磁盘数据的同时接到处理客户端Y的请求。
线程的替代方案
如果不想使用多线程，可以使用**异步编程（事件驱动编程）**的风格来实现，在单线程中写非串行逻辑；例如Javascript
事件驱动编程的一般形式：包括一个线程一个循环，这个循环等待输入。
大多数windows程序都是用这种风格实现的，等待的是敲击键盘的输入
事件循环：
在收到服务器的响应时，传入新的输入值，检查状态表中的每个活动的状态。执行每个活动的下一步。并且更新状态。依次循环完成整个状态表。
利用事件驱动来达到I/O 并发的目的：这个相比较多线程要更大节约成本。但它不能利用多核，写起代码来也比较痛苦
多进程和多线程的区别
对大多数Linux程序，一个进程就是一个单独运行的的程序，只有一个地址空间，一块可供进程使用的内存。
一个进程里面可以包含多个线程
在多线程中，当上下文切换时，是所有的线程都在切换嘛
假设只有一个单核机器（同一个时刻只能做一件事），当你打算在你的机器上运行多进程，操作系统会把CPU时间片反复分配给这几个进程的程序，当硬件时钟到期时，操作系统会判断是时候把CPU从当前的运行的进程剥夺，然后把CPU分配给另一个进程，这个事件是在进程级别上做的。
我们使用的线程最终是由操作系统提供的线程， 当操作系统进行上下文切换时，就是不同的线程之间产生切换时，操作系统是知道这些的，此时操作系统会基于一些调度算法选择一个不同的线程来进行
线程模型：
线程面临的挑战
挑战一 共享数据
问题:有两个线程，同时做一个n=n+1的逻辑？有一个线程正在读取，而另外有一个线程在做自增操作？这样就产生了竞争问题。
解决方案：加锁
多线程之间是可以共享内存的
共享内存：线程共享地址空间
如果某个线程在内存中创建了一个对象，在其他线程中也能使用它，当其中一个线程正处理一个客户端的请求的时候，首先会检查缓存中的数据，因为这个缓存每个线程都能读，当线程里有新的数据时，线程可能会向缓存中写入数据进行更新。
关于多线程需要记住的一点是：
无论何时你在多线程中读写共享数据，在同一时刻，可能总会有其他的线程也正在查看它。
多个线程同一时刻运行同一段代码的行为叫竞争race,比如一个线程正在启动这些代码，而另一个线程正在结束这段代码
解决这个问题的方法很简单:锁mutex，只有在持有锁的时候，这个共享数据才可以被使用，任何人想要使用这个锁都需要等待。
lock和unlock之间的代码就是要运行的代码
因此我们需要解决的第一个是同时访问数据的加锁策略，另一个方案是你可以让你的代码不再共享数据。
挑战二 线程间如何协调
问题L:
一个线程生产数据，另一个线程消费数据 ，那么问题是：
消费者如何等待（不能总是占着CPU）
生产者如何唤醒消费者？
解决方案：实现channel通讯
挑战三 死锁
线程致命的问题是死锁deadlock，死锁是个一般性问题。
死锁：当你运行到线程中的某个位置，一个线程T1正在等待另外一个线程T2生产的数据，然而T2也在等待着T1做一些事情。或者T1拥有锁A，T2拥有锁B，T1要申请锁B，T2要申请锁A,此时他们各自持有一把锁，又要申请第二把锁，这样他们就都处于申请第二把锁的位置，它们都无法继续进行下去，此时你的机器停了下来什么也不做，但是也没崩溃，这样就会产生死锁了。
什么是Web爬虫？
获取一个或多个站点的所有的web网页。例如：用来构建索引
网页和链接构成是一个图结构
指向某些页面的多个链接
图具有环性特征
网络爬虫 Crawler：给你一个url让它运行，然后在web页面里，包含有许多链接指向了其它页面，所以web爬虫要做的就是把这些链接指向的页面提取出来，抓取这些页面后，再检查所有这些页面里的url，然后继续抓取这些url指向的页面。直到web中所有的页面都被抓取完就会停止。
对于爬虫应该注意的一点就是：对于已经抓取过的页面，对于任何正在抓取的页面，不应该再有第二次抓取，避免重复抓取。而且要有边界，知道什么情况下需要停止继续爬取。否则你的爬虫永远不会结束，陷入循环。
(url:统一资源定位系统（uniform resource locator;URL）是因特网的万维网服务程序上用于指定信息位置的表示方法。)
为什么需要互斥？（Lock()、Unlock()）
1、不同的页面可能包含相同的URL
2、两个线程同时读取该URL。譬如T1 获取fetched[url]、线程T2也获取feteched[url]，此时因为该URL还没有爬取完，already还是false状态。那么会导致两个线程都在爬取。这里就需要借助锁来处理。锁会保证读取和更新这两个操作是具有原子性。
3、在Go语言内部，map是一个复杂的数据结构（tree or 扩展的hash）。并发更新/更新会导致内部的不可变性。并发的update/read可能会导致read失败
何时应该使用共享变量和锁？对比通道有什么好处？
其实所有的问题都有两种解决方案：
状态- 共享内存和互斥锁
通信-通道
waitGroup
在go中实现并发控制的函数
WaitGroup 对象内部有一个计数器，最初从0开始，它有三个方法：Add(), Done(), Wait() 用来控制计数器的数量。Add(n) 把计数器设置为n ，Done() 每次把计数器-1 ，wait() 会阻塞代码的运行，直到计数器地值减为0。
在多线程并发控制时，如果不加锁会发生什么？
运行无锁的代码不会出现race,运行一段事时间后总会出错的
（幸运的是，go语言提供了内置的race探测器）
远程调用RPC
远程调用是分布式的关键
RPC的目的是为了解决客户端程序和服务端易于编程的数据通信，隐藏网络协议、把数据转换程统一的格式
RPC消息图：
软件结构：
lecture 3 — GFS
分布式存储是分布式系统的关键
构建分布式存储的难点：
高性能：跨服务器的数据文件分片获取
多服务器：标志着更多的故障
容错：多副本
复制：潜在的不一致
一致性：导致性能降低
GFS(The Google File System 谷歌文件系统）
GFS是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。它运行于廉价的普通硬件上，并提供容错功能。它可以给大量的用户提供总体性能较高的服务。(它只处理大文件的顺序访问，而不是随机访问）
一个值得关注的问题是如何构建大型存储 Big Storage
构建分布式系统，大多都是关于如何设计存储系统，或是设计其他类型的系统。我们还会关注如何为一个大型分布式存储系统设计一个优秀的接口，以及如何设计分布式存储系统的内部结构。
（本课程经常讨论的话题：并行性能、容错、复制和一致性）
首先讨论一下大型分布式存储系统的空间。
（性能需求）人们建立大型分布式存储系统的出发点往往是为了获得巨大的综合性能，如何利用数百台机器的资源来完成大量的工作。
（分片-将数据进行分割，分配到大量机器上，从而能够并行的从多台服务器读取数据.
把数据分配到大量服务器上，总有那么几台机器会宕机，因此总会有错误产生。这样的错误不可能依靠人工发现，因此得有一个自动化的容错（fault-tolerant)系统.
实现容错最有用的一个方法就是使用复制。想要有容错能力，就要有复制replication,对数据进行复制保留其两三份副本，当有一份数据出错时，使用其副本即可，这样可以提高容错能力。此时一不小心，就会造成副本的不一致，就会引发不一致问题。这时再想保持一致性，你就需要做大量的额外工作，因此性能会降低。这样和我们的初衷是相违背的。
**并行，容错，复制和一致性是我们在构建高性能的分布式系统的过程中会面对的问题。**因此，这就需要我们在性能目标和实现良好的一致性上做出权衡。
（单个服务器的容错能力很差）
一个糟糕的复制系统的设计：
C1和C2同时向S1、S2发起请求，由于没有规定两台服务器处理两个客户端请求的顺序相同，会造成读取结果不一致。
引入一个场景：
假设有几个场景c1和c2是并发写。在写完成后，发起C3和C4读取。那么会得到什么结果？
答案：可能是1或者是2，但是两个读都应该是相同的值返回（强一致性模型），但是单机无法做到好的容错。
在现实分布式系统中肯定存在副本。
GFS架构
分布式 分片sharding 容错
分工明确：master负责读写分发，chunkmaster负责具体数据
chunk servers 块服务器:每个块都有三份副本，所有的文件都可以迁移到其他chunk 服务器。支持并行读/写（MapReduce）
master 主服务器 ：
其中一个表存储的是从filename到chunk ID的数组的映射，另一张表记录的是从chunk handle 到list if chunkservers 的映射
(master-slave 主从设备）
这种管理方式要求所有的master在磁盘上都有一个log,任何时候有数据变更，就会在磁盘上的日志追加一个条目，并定期创建checkpoint。（使用日志而不是数据库的原因是追加日志是十分高效的，数据库基于B-tree和hash会比较繁琐，操作复杂降低效率）
客户端如何读取一个文件？
1、发送一个请求
2、master根据offset查询chunk server（无缓存时）
3、Master响应最新的chunkserver table给客户端
4、客户端缓存chunk handle 和chunkserver服务器列表
5、客户端发送请求
6、chunkserver从磁盘读取文件并响应给客户端（客户端接收的是buffer，library会合并为真正文件）
读取数据的方式：
step 1 表示应用程序想读取某个特定的文件的某个特定的偏移上的数据，在某个特定的范围内，比如1000-2000字节范围内的数据，所以它只要发送一个文件名和要读取的字节范围给master，然后master从文件表里查询这个文件名，找到包含这个字节范围的chunk
写入数据的方式（应用程序对于写的接口）：
有一些函数调用和一些可调用的库可以请求GFS
记录追加（接口）：客户端会发起lib库调用，这有个文件名，我想把这个buffer里的字节数据追加到文件里
客户端发送”我想追加的数据“的请求到master,请求内容是”我要给这个名字的文件追加数据“，请告诉我这个文件最后一个chunk在哪里。
写的情况分为有无primary（最初的，初级的：
第一步是要找到那个最新的（发生在master ,client请求master,告诉master我要追加此文件，请告诉我与那些块服务器对话）
然后up-to-date(一个副本的chunk版本等于master服务器知道的最新的版本号）
master告诉client谁是primary谁是secondary（client会通过缓存提高效率）
客户端追加一条记录的方式：
GFS如何保证一致性？
GFS只 保证一次原子写入，数据已经在一个副本落盘。在经过一定时间后，所有的副本数据会一致。
假设出现网络分区，导致脑裂(split brain，存在两个primary)。出现这种情况，GFS引入60秒的租约时间，出现primary不能连通，就必须等待超时（剩余的时间client可以通过cache的primary信息计算）。
当Primary响应客户端已经成功append 记录，随后客户端立即进行读取，看到的应是最新的文件。
（注意：不是所有的客户端都能看到最新的文件，GFS是弱一致性。需要等待时间同步到其他节点，通过“就近”复制.）
GFS如何容错？
对GFS的总结：
GFS是MapReDuce的基础设施
优点：
1、集群式文件系统演变为基础设施
2、存储与管理的分离标志（name管理在master 文件存储在chunkserver)
3、并行吞吐
4、大文件分块存储减少开销
5、主chunk顺序写设计
6、利用租期来解决脑裂问题
缺点：
单master的限制：内存和CPU
对小文件存储不够友好
master的故障转移不友好
弱一致性
