课程概要
主要讨论Golang中的多线程和RPC，以及实验相关的内容。
正文
为什么是Golang？
- 对多线程的良好支持，那个线程拥有自己的执行栈
- RPC特别方便
- 类型安全
- 自动垃圾回收（不用担心内存释放问题）
- 多线程+GC非常更吸引人
- 简单
- 教程 Effective Go
多线程
I/O并发（做多件事情）、并行（CPU）。
多线程是一个结构化工具，但是有一些坑
Go叫多线程为goroutines；
Thread = 执行线程
多线程允许一个程序在执行时去做很多事情。
每个线程都是串行执行，就像是非线程程序
线程可以共享内存
每个线程都有自己的线程状态：程序计数器、寄存器、栈
线程和进程是包含的关系，一个进程可以产生很多线程
为什么选择多线程？
在分布式系统中，需要并发执行。而多线程是实现并发已经廉价的方式
I/O并发：多个客户端同时发送请求到多台server，并且等待响应。服务器处理多个客户端请求，每个请求可能会阻塞。譬如客户端X读取磁盘数据的同时接到处理客户端Y的请求。
多核性能：并行的在多个CPU执行代码
方便：通过后台运行worker，进行每秒查询某个值是否有效
是否有线程的替代方案？
yes：在单线程中写非串行逻辑。这种方式也被称为事件驱动。譬如JavaScript。
做法：使用一个状态表保存所有活动的状态，假设是每个客户端的请求
事件循环：在收到服务器的响应时，传入新的输入值，检查状态表中的每个活动的状态。执行每个活动的下一步。并且更新状态。依次循环完成整个状态表。
利用事件驱动来达到I/O 并发的目的：这个相比较多线程要更大节约成本。但它不能利用多核，写起代码来也比较痛苦
线程的挑战
共享数据
例如：有两个线程，同时做一个n=n+1的逻辑？有一个线程正在读取，而另外有一个线程在做自增操作？类似数据库事务中遇到的数据共享问题。
上面两个问题都遇到了“竞争”问题，这个会成为一个程序的Bug。在电商领域会有超卖的风险。如何解决？
- 使用锁（Go中使用sync.Mutex）
- 避免使用共享可变数据（immutable and mutable）
线程间协调
例如：一个线程生产数据，另一个线程消费数据。生产与消费者
- 消费者如何等待（不能总是占着CPU）
- 生产者如何唤醒消费者？
如何解决？
- 使用Go channel通讯
- sync.Cond
- WaitGroup
死锁
周期性的锁检查或者是通讯（RPC或Go channels）
案例学习：Web爬虫
什么是Web爬虫？
- 获取一个或多个站点的所有的web网页。例如：用来构建索引
- 网页和链接构成是一个图结构
- 指向某些页面的多个链接
- 图具有环性特征
爬虫的挑战
如何利用I/O并发
爬虫的很多瓶颈都是因为网络带宽的限制。在同一时刻抓取多个URL来提高并发（每秒抓取数量）=> 利用多线程来提高并发
避免重复抓取
多次抓取是网络的浪费，这里需要记录访问状态
要知道何时停止
不能没有边界，遇到什么情况就需要停止继续爬取
以爬取Golang.org 为例子
代码：https://pdos.csail.mit.edu/6.824/notes/crawler.go
解决方案1: 串行爬取
通过递归调用执行按序爬取，定义的fetched map会记录哪些地址已经爬取。函数中所传递的参数为引用。
缺点：同一时刻，一次只能爬取一个页面。不过可以试试执行go Serial() 来改善性能。
解决方案2: 并发互斥爬取（concurrentMutex）
-
为每个爬取的页面创建一个线程
并发爬取、提高爬取速度。 “go func”可以创建一个goroutine 并且运行该函数（可以是匿名函数）
-
线程之间是共享变量 feteched map
通过互斥锁的方式来控制，同时只能一个线程访问该变量
-
为什么需要互斥？（Lock()、Unlock()）
- 不同的页面可能包含相同的URL
- 两个线程同时读取该URL。譬如T1 获取fetched[url]、线程T2也获取feteched[url]，此时因为该URL还没有爬取完，already还是false状态。那么会导致两个线程都在爬取。这里就需要借助锁来处理。锁会保证读取和更新这两个操作是具有原子性。
- 在Go语言内部，map是一个复杂的数据结构（tree or 扩展的hash）。并发更新/更新会导致内部的不可变性。并发的update/read可能会导致read失败
思考：假设注释掉Lock() / Unlock()会发生什么？
- go run crawler.go为什么可以正常工作？
- 即使刚刚打印的结果都是正确的
- 即使刚刚打印的结果都是正确的，不过可以执行go run -race crawler.go 列出变量竞争的日志
ConcurrentMutex何时认为执行已经完成？
sync.WaitGroup
Wait()等待所有的Add()操作，但遇见调用Done()时表示已经运行完成。譬如：可以用来处理等待所有的子进程处理完成。
该爬虫程序会创建多少个线程？等于URL数量
ConcurrentChannel 爬虫
- go channel：channel是一个对象，ch := make(chan int)。通道可以让一个线程发送一个对象给另外一个线程。发送的线程使用ch <- x 把j发送给其他Goroutine接收者。接收者通过y := <- ch 把结果存储到y对象中。for y := range ch等待通道消息。
- 通道的通信是同步的
- 通道可以被多个线程发送或者是接收消息
- 通道对于操作系统非常廉价
- 发送方在接收者接到消息之前会一直阻塞，直到此条消息被消费（同步，小心死锁）
ConcurrentChannel master()
master()会创建worker进行页面爬取，worker()把页面的URL格式化为slice，并且发送结果到channel中。master作为接收者监听来自其他worker发送过来的消息。feteched不需要锁，因为不存在数据共享访问。
问题： master中的wait应该写在哪儿？等待的时候是否会占用CPU时间？
master是如何知道已经完成爬取？使用计数的方式n，每个worker只发送一次消息到channel
为什么多个线程使用同一个通道不会造成竞争？（因为通道的发送和接收是同步的）
当worker向URLs slice中写入数据时，是否存在竞争？master读取时，为什么不需要锁？
- worker只会在发送前写入
- master只会在接收消息后读取
- 并不存在同时使用URLs对象的情况
何时应该使用共享变量和锁？对比通道有什么好处？
其实所有的问题都有两种解决方案，依赖你如何去思考。
- 状态– 共享和锁
- 通信– 通道
对于6.824的实验，推荐如果是状态就使用共享变量+锁的方式，如果是等待和消息就使用sync.Cond或channel或time.Sleep()
远程调用（RPC）
远程调用是分布式系统的关键，所有的实验都有涉及
RPC的目的是为了解决客户端程序和服务端易于编程的数据通信，隐藏网络协议、把数据转换成统一的格式，譬如strings, arrays, maps, &c转换为wire格式
RPC消息图
软件结构
案例学习：kv.go
代码：https://pdos.csail.mit.edu/6.824/notes/kv.go
介绍：这是一个简单的模拟KV存储服务器，仅支持Put(key,value), Get(key)->value
代码中使用了Go的 RPC库net/rpc
代码分为三部分：
- common
声明一些参数以及server响应的数据结构
-
client
connect() 创建一个tcp连接，并连接到server
get()和put()是客户端的操作，函数内部的Call()调用RPC库。主要包含动作、操作、值以及错误处理
-
server
声明供RPC调用的方法、完成对象注册到RPC库。库包含：连接读取、为每个连接创建goroutine、解码请求、查找存储结果、调用对象方法、编码响应结果、回写结果给客户端；Get()和Put()都必须使用锁，因为多线程会存在同时操作数据。
一些其他的细节：
- Binding：客户端如何连接需要通信的服务端？对于Go rpc。使用主机名加端口号的形式。在大型系统中，会存在各种命名和配置服务器
- Marshalling：编码，发送时的数据格式。Go中支持传入字符串、数组、对象、map、指针等，不支持channel和函数。可以通过指针来复制需要访问的数据
RPC的问题：调用失败怎么办？
例如：丢包、网络中断、服务器慢、服务器崩溃
对于连接的客户端来说，故障会表现出什么样子？
- 客户端得不到服务端响应
- 客户端不知道服务端是否已经收到了请求，这里有几种情况。请求未收到、请求已经收到正在处理，但在返回结果时崩溃了、服务端发送了结果，但是网络出现故障
简单的故障处理方式：best effort
- Call()时等待一段时间的响应
- 重发请求
- 当等待一段时间后，发现还是没有响应就放弃并返回错误。
Q：开发的应用程序如何做到处理逻辑更简单，又有效？
假设一个场景，客户端执行Put(“k”,10);Put(“k”,20);两者都成功执行成功。再执行Get(“k”)时会得到什么结果？中间会有一些问题：超时、重发、先发送的后到。
Q：这种Best effort的形式是否就够了？
只读操作、保持幂等性。譬如，数据库在进行inserted前可以进行检查记录是否存在（唯一键）
优秀的RPC服务：只做一次
解决方式：RPC服务器能识别什么是重复的请求，如果是重复的请求，则返回前面生成的结果。
问题：如何识别出重复的请求？
客户端在请求时，针对每个请求，可以生成一个唯一请求ID（request id）。当进行重发时，该ID不变。逻辑伪代码如下：
该方案的复杂点：（lab3）
假设有两个客户端生成了相同的xid怎么办？更多的随机数？使用客户端ID（譬如IP）？
服务端最终需要丢弃掉旧的RPC请求，那何时丢弃才是安全的？
思路：
- 每个客户端有一个唯一ID、每个客户端 会生成一个RPC序列号、每个客户端都包含”seen all replies <= X”（像是TCP序列号和ack）。
- 第二种方案，在同一时刻，只允许一个RPC连接。seq+1的消息被允许。小于seq的消息就丢弃
当遇到冲突的请求时，前一个请求还在处理中。如何解决冲突？为每个执行的RPC都定一个flag标示。最终来决定是等待还是丢弃。
at-most-once的策略，当遇到服务器崩溃或者重启如何处理？如果重复记录的信息是存储在内存中，当服务器重启时，之前的记录就会丢失。这里可以：
- 从副本从获取
- 每次写结果前，先落盘
GO RPC就是at-more-once的策略模式，只执行一次。
- 打开TCP连接
- 发送请求到TCP
- 永不进行重发（服务器就看不到重复调用了）
- 如果没有得到响应，就返回错误.（TCP超时、服务端未收到请求、服务端处理了但是网络故障）
扩展：恰好一次的策略（exactly once）
无限制的重试，重复检测以及容错服务（Raft）
参考文献