MIT 6.824分布式课程讲稿翻译 - Lec 2

Posted on | In

原文地址: 6.824 2017 Lecture 2: Infrastructure: RPC and threads

最经常被问到的问题: 为什么用Go?

6.824过去使用的是C++, 但学生们总会把时间用在调试Bug而不是分布式系统上(例如释放了还在使用中的对象内存).

而Go能让你集中关注于分布式系统的问题:

  • 很好地支持并发
  • 很好地支持RPC
  • 垃圾回收(不会遇到释放内存的问题)
  • 类型安全(type safe)

同时我们也喜欢Go编程, 因为:

  • 简单易学
  • 我们重新设计实验时, 还是一门很潮的语言

至于教程, 建议看Effective Go

线程(Threads)

线程是一种很有用的结构化工具
Go把它们称为goroutines, 一般地都叫做线程
线程有很多使用技巧(tricky)

为什么用线程

  • 允许并发执行, 在分布式系统中是很常见的
  • I/O并发(I/O concurrency): 从其他服务器等待回复时, 先处理下一个请求
  • 多核(Multicore): 多个线程在多个核上并行执行

线程 = “执行线程”

线程能让一个程序(逻辑上)同时做多件事
这些线程共享内存
每个线程包含某些线程相关(per-thread)的状态: 程序计数器(program counter), 寄存器, 栈

一个程序中有多少线程

应用程序有多少用处, 就有多少线程.
Go鼓励使用者创建多个线程:

  • 通常线程要比核数多
  • Go执行器会在可用的核上调度这些线程

Go线程是有开销的, 但你可以当做没有.
创建一个线程比调用一个函数开销大.

线程带来的问题

  • 共享数据(sharing data)
    一个线程读取另一个线程正在修改的数据?
    这样会导致竞争条件(race condition)
    -> 不要共享数据, 或同步共享的数据(如使用Mutex)
  • 线程间协作(coordination between threads)
    例如等待所有Map线程完成
    可能导致死锁(一般来说比数据竞争更容易发现)
    -> 使用Go的channel或WaitGroup
  • 并发粒度(granularity of concurrency)
    粗粒度 -> 简单, 但并发/并行效率低
    细粒度 -> 高并发, 但带来更多的竞争和死锁

爬虫练习: 两个难点

  • 安排I/O并发
    获取一个URL的同时, 处理其他URL
  • 每个URL只获取一次
    以便减少浪费的带宽
    对(被爬取的)远程服务器更友好
    => 需要使用某些工具来实时记录已经爬过得URL
  • [在不同的核上处理不同的URL]

解决方案(见crawler.go)

  • 减少深度 — 使用一个fetched的map数据结构(来记录已爬取URL)
  • 串行执行的方案:
    • 将fetched map传入递归调用
    • IO没有重叠(overlap), 因此fetcher处理时间长
    • 不使用多核
  • 使用go routine和共享的fetched map的方案
    • 每个URL创建一个线程
      如果我们不传u进去会发生什么(数据竞争)
    • 为什么要用锁? (即便把它们去掉也是可以正常工作的!)
      • 如果没有锁会出现什么错误?
        检查和标记URL操作就不是原子性的了
        因此有可能会重复爬取同一个URL.
        例如, T1检查了fetched[url], 同时T2也检查了fetched[url]
        两者都发现这个url没有爬取过
        因此两者都会开始爬取, 这样就出错了
      • 这种情况称为一个竞争条件(race condition)
        这个Bug只在某些线程交叉的时候出现
        很难发现, 也难以解释
      • go可以自动检测竞争(go run -race crawler.go)
      • 注意检查和标记URL的操作必须是原子性的
    • 处理一个页面时, 怎么确定我们处理完成?
      WaitGroup
  • 使用channel的方案
    • Channel: 同步多线程的常用手段
      可以看做是一个bounded-buffer的消息体(bounded-buffer of messages)
      多个线程可以对channel接收或发送值
    • 发送和接收操作在下面两种情况阻塞:
      • channel满了(channel is full)
      • channel是空的(channel is empty)
    • 通过一个Master线程来分配各个url
      fetched map不会出现竞争, 因为它不是共享的!

怎样才是最好的解决方案?

- 所有并发的方案都远比串行方案难
- 有些Go设计者认为不应该使用共享内存
    也就是说一律只使用channel
- 我们的实验中用到了许多并发特性:
    - 共享内存用锁
        如多个服务线程共享一个map
    - 线程间同步用channel
        如生产者/消费者风格的并发
- 使用Go的race detector:
    https://golang.org/doc/articles/race_detector.html
    go test -race mypkg

远程方法调用(Remote Procedure Call, RPC)

  • 分布式系统中的关键部分, 所有实验都用到了RPC
  • 使用目的:
    • 易于编程的网络通信
    • 隐藏了很多客户端/服务端的通信细节
    • 客户端调用类似通常的函数调用
    • 服务端处理类似通常的函数
  • RPC的使用非常广泛!

理想情况下RPC让网络通信就像fn调用一样:

Client:
    z = fn(x, y)

Server:
    fn(x, y) {
        compute
        return z
    }

RPC目的就是为了达到这种程度的透明.

Go示例: kv.go

RPC消息图示

  Client             Server
    request--->
       <---response

软件架构

  client app         handlers
    stubs           dispatcher
   RPC lib           RPC lib
     net  ------------ net

一些细节

  • 调用由服务器的哪个函数处理?
    Go语言中可以在Call()的参数中制定
  • 序列化: 将数据格式化为数据包
    数组, 指针, 对象等等都能很巧妙地处理
    可以看到Go的RPC库非常强大!
    但有些类型还是不能传: 例如channel, 函数
  • 绑定: 客户端怎么知道和谁通信?
    可以是客户端提供了服务器端的主机名
    可能是某个命名服务(name service)将服务器名映射到某个主机

RPC可能会出现哪些问题?

例如: 丢包, 网络中断, 服务器慢, 服务器宕机

服务器的错误对于客户端的RPC库来说是怎么样的?

  • 客户端收不到服务端的回复
  • 客户端不知道服务器有没有收到请求
    因为可能是服务端或网络在发送回复前发生了错误

最简化模型: “at least once”

  1. RPC库等一段时间内的回复
  2. 如果没有回复, 那就重发请求
  3. 重复若干次这个操作
  4. 如果依然没有回复, 就向应用返回错误
  • Q: “at least once”适用于所有应用吗?
    不, “at least once”存在一个明显的问题: 如客户端发送”从银行账户减$10”
  • Q: 这样的话客户端程序会出什么问题?
    Put(“k”, 10) — 写一个Key值的RPC请求
    Put(“k”, 20) — 然后客户端又对同一个Key写了一次
    第二个RPC先到服务端, 第一个后到, 导致写入了旧值
  • Q: 那”at least once”还能用吗?
    可以: 如果重复操作没问题的话, 例如只读操作
    可以: 如果应用自己可以处理重复写的问题, 在实验1中就需要这样

更好的RPC模型: “at most once”

思路: 服务端RPC代码自动检测重复的请求, 对于重复的请求直接返回上一次的结果, 而不是重新执行

  • Q: 怎么检测重复请求?
    客户端需要在请求中包含一个唯一的ID(XID), 重复发送请求时使用同一个XID
    服务器端:
      if seen[xid]:
    r = old[xid]
  else
    r = handler()
    old[xid] = r
    seen[xid] = true

“at most once”的难点

这些难点会在实验3及后续实验会出现

  • 如何保证XID是唯一的?
    • 大随机整数?
    • 使用唯一客户端ID(IP地址?)+序列号?
  • 服务器必须忽略旧的RPC请求
    如何能够安全地忽略?
    • 一种思路:
      • 唯一客户端ID
      • 客户端唯一的RPC序列号
      • 客户端在每个RPC请求中包含”已经收到了序列号<=X的回复”
      • 很类似于TCP的序列号和ack包
    • 每次只允许客户端有一个未完成的RPC:
      收到序号seq+1的请求时, 服务器就忽略所有<=seq的请求
    • 客户端能够只保持5分钟的重试时间:
      服务端可以忽略已经超过5分钟的请求
  • 当一个请求还没处理完时, 如何处理重复请求?
    服务器端此时还不知道如何回复, 也不想执行两次
    思路:
    • 在每个RPC回复中加一个”pending”标志
    • 继续等待或忽略
  • 如果一台”at most once”服务器宕机并重启了怎么办?
    如果内存中的信息丢失了, 服务器重启后会忘记重复的请求并接受处理这些请求.
    • 可能需要把这些重复请求的数据写入磁盘?
    • 可能备机也需要备份这些重复数据?
  • “exactly once”怎么样?
    等于”at most once” + 无限次重试 + 容错服务

Go RPC使用的是”at-most-once”

  1. 打开TCP连接
  2. 将请求写入TCP连接
  3. TCP可能会重传, 但服务端的TCP会过滤重复包
  4. Go RPC代码不会重试(不会创建第二个TCP连接)
  5. 如果没有接收到回复, Go RPC代码会向应用返回错误
  • 可能是由于(TCP)超时
  • 可能是服务端没有收到请求
  • 可能是服务端处理了请求, 但在回复包传达之前服务器/网络出错

Go RPC的”at-most-once”对于实验1不够用, 因为它只发送一次单独的RPC请求
而在MapReduce模型中, 如果Worker不回应, Master会重新发送给其他Worker. 但原来的Worker可能没有出错, 而是仍然在处理这个请求.
Go RPC不能检测出这种重复的情况, 这在实验1中没问题, 可以在应用层处理.
实验3中会显式地检测重复请求.