6.824 2020 Lecture 2: Infrastructure: RPC and threads

# 6.824实验的基础设施：RPC和线程

Go中的线程和RPC，以及Go Tour中的一些练习

## 为什么使用Go作为lab的编程语言

* Go对线程的良好支持
* 方便使用的RPC
* 具有垃圾回收机制
* 相对简单
* 本教程的Go编程规范和细则参考[https://golang.org/doc/effective_go.html](https://golang.org/doc/effective_go.html)

## 线程

常用的结构化工具，但是使用起来会有各种各样的trick。在Go中，被称作goroutines。线程的存在，使得一个程序可以并发的处理多项任务。线程共享内存空间，线程不共享的有程序计数器、线程栈、寄存器。

在分布式系统中，我们需要线程的并行语义：
1. I/O并发。多个客户端发送请求并等待响应，服务端处理多个客户端请求。当在等待读取客户端X的数据时，可以利用等待的时间去处理客户端Y的请求。
2. 多核性能。代码可以并行地在多个cpu核里运行。
3. 便捷

## 线程有无替代品

事件驱动，就是线程的替代品。即，在一个线程中，活动状态交织，其实就是状态机。维护一个数据结构，保存每个活动的状态，比如，每个客户端请求。

开启一个事件循环，监听每个活动的输入（比如，服务端的响应到达），然后切换该活动到下一状态。

事件驱动，也可以实现I/O并发，并且避免线程切换的开销，但是浪费了多核编程环境。

## 多线程编程的难点

* 数据共享
    * 比如，如果两个线程同时执行`n = n + 1`，或者，一个线程增加n时，另外一个线程读取n。这时候需要利用锁机制（Go里面有sync.Mutex），或者，避免共享可变对象数据。
* 线程之间的条件竞争
    * 比如一个线程在生产数据，另外一个消耗数据。那么消费者怎么等待数据，生产者怎么唤醒消费者。Go中使用Go channel、sync.Cond、WaitGroup等数据结构解决该问题。
* 死锁
    * RPC或者Go channels中可能产生死锁
    
## [Web Crawler](https://pdos.csail.mit.edu/6.824/notes/crawler.go)

爬虫需要注意的两个问题：
1. I/O并发
    多个线程，同时爬取多个网址
2. 每个URL只处理一次，避免重复处理
    维护一个数据结构记录已经处理过的url，并且知道爬取程序的终止条件

crawler.go有两种解决方式。单线程和多线程。

### Serial crawler

深度优先遍历，使用名为"fetched"的map记录避免重复，每次只访问一个网址，如果把go放在Serial函数前面，会发生什么？

### ConcurrentMutex crawler

创建线程，每个线程访问一个网址。`go func`创建一个go例程并运行，`func`会以异步的方式运行。线程共享`fetched map`。

为了避免fetched访问的数据竞险，需要使用Mutex的Lock()和Unlock()。试想，两个不同的web网页包含了同一个url，两个线程同时访问这两个网页，并解析得到这url时，会通过fetched变量判断是否已经访问过。线程T1读取`fetched[url]`，T2读取`fetched[url]`。此时，T1和T2都会看到该url没有被访问过（即，already == false）。使用Mutex，可以保证同一个时刻，只有一个线程可以访问fetched变量，即，同一时刻，只有一个线程可以看到`already == false`。

爬虫如何终止？使用sync.WaitGroup。`Add()`添加要运行的thread，Done()标记当前thread执行完成。`Wait()`会阻塞到所有被`Add`的线程都执行完成。

### ConcurrentChannel crawler

Go中有一个数据结构，channel，类似于FIFO。channel允许一个线程将数据发送给另外一个线程，`ch <- x`，发射端会阻塞到某些go例程接收数据，`y := <- ch`或者`for y:= range ch`。接收端会阻塞到某些go例程发射数据。使用channel时，务必注意死锁，因为发射端会阻塞，直到接收端接收数据。

master()函数创建一个worker例程获取每个网页。worker()发送url的切片引用给channel。多个worker使用一个channel发送。master()从channel中读取url切片，然后继续创建worker。

这该版本的实现中，`fetched map`无需使用互斥器，因为`fetched map`未被多个线程使用。

爬虫如何终止？使用变量n记录worker的数量，每个worker只会向channel压入一个item。

为什么使用相同的channel，不会发生数据竞险？worker向url切片中写入数据，master读取切片，不需要锁吗？不需要，因为，
* worker仅在发送数据前写切片
* master仅在接收数据后读切片

使用共享数据、锁以及channel的时机？具体问题具体分析，取决于编程者如何考虑程序状态。对于6.824的实验来说，笔者推荐`共享数据`+锁来控制状态，等待/通知可以使用sync.Cond、channels、time.Sleep()来完成。

## RPC

分布式设置中的关键一环。为了更简单的客户端/服务端通信，隐藏网络协议的具体细节，将要传输的数据序列化。

RPC消息传输图,
Client        Server
request  --> 
        <-- response

软件架构，
  client app        handler fns
   stub fns         dispatcher
   RPC lib           RPC lib
     net  ------------ net
     
### Go例子[kv.go](https://pdos.csail.mit.edu/6.824/notes/kv.go)

实现一个简单kv存储服务，`Put(key, value), Get(key) -> value`，使用go的RPC库。

* common: 为每一个server handler, 声明Args和Reply结构
* client
    * connect()中的Dail创建一个TCP链接，get()和put()都是client stubs
    * Call()调用RPC库，用户选定server端的函数名、参数、响应存放位置，然后发送请求，反序列化响应。通常，你会有一个reply.Err标识服务级别的失败
* server
    * 服务端会定义一个对象，对象中的函数即RPC handlers
    * Server将该对象注册到RPC库中
    * RPC库
        * 读取每个请求
        * 为该请求创建新的go例程
        * 反序列化请求，查找给定对象并调用该对象的指定函数
        * 序列化响应并写入到TCP链接
    * server的Get和Put() handlers
        * 需要上锁
        
### 一些小细节

* Binding: client如何知道server地址。对于Go的RPC，client需要name/port参数，这两个参数通常来自name server或者configuration server
* Marshalling: 序列化数据。Go的RPC库可以传输strings、arrays、objects、maps、pointer(实际传递所指向的数据)，无法传输channel和function

### 故障处理

可能发生的故障有，lost packet（丢包）、网络故障（broken network）、服务响应超时（slow server）、服务崩溃（crashed server）

故障发生时，client看到的现象可能有：
* server无响应
* client无法得知，request是否发送成功
    * 可能server未接收到request
    * server成功执行函数调用，发送响应前server恰好崩溃
    * server成功执行函数调用，发送响应前网络故障
    
最简单的故障处理方案--“best effort”：（即，重试）
* Call()等待一会响应
* 如果没有响应到达，重发请求
* 重复几次，若扔无响应，则放弃重试并抛出错误

更好的RPC行为--"at most once":
* 理想情况下，server可以检测重复请求，返回之前请求的响应，而不是重复调用函数
* 那如何检测重复请求？client在请求时可以带上一个unique id(XID)，如果client重发，则XID不变
```
server:
    if seen[xid]:
        r = old[xid]
    else 
        r = handler()
        old[xid] = r
        seen[xid] = true
```

Go的RPC是`at-most-once`的简单实现，但略有区别：
1. 打开TCP链接
2. 向TCP请求中写入链接
3. Go RPC从来不重发请求，所以server不会看到重复的请求
4. Go RPC代码在无法得到响应时会抛出错误
    * 可能TCP超时
    * 可能server未看到请求
    * 可能server处理请求，但是在响应返回前，server崩溃或者网络故障
    
另外Lab 3会提到`exactly once`，即无限制的重试，重复检测以及容错服务

逆风起笔