本文是针对 UMich EECS491 (这课抄了致敬 MIT CS 6.824) 的 project2 的设计思路和实现的总结, 也可以作为一般的 primary-backup 1-fault-tolerant distributed storage system 的设计参考.

本文不会涉及具体的实现细节, 只会涉及一些 high-level 的设计思路 如果有 JI/GC 同学当了 IA/GSI 希望不要举报我

Lexical Confinement: 串行逻辑链

在分布式系统的高并发请求中并不会完全像我们在单机操作系统中看到的 performance
是最重要的, 在分布式系统中 consistency 才是最重要的, 为了避免各种不同步的分布式
failure 导致的不一致问题以及编码实现的复杂性, 我们可以通过串行化的方式来简化

回忆 Go 语言设计中非常重要的 CSP 模型:

Sharing Memory by Communicating, not Communicating by Sharing Memory

也就是要利用 channel 机制来实现不同线程之间的数据互通, 不过思考一个问题, 如果我们用 mutex 风格的设计来实现这里的一个 primary-backup 实现, 我们很难确保一个事情: liveliness 也就是在阻塞 pb 同步请求中, 我们仍然要保持周期性心跳 tick() 的可用性, 否则整个节点会因为同步卡顿而被踢出服务集群, 那么就很容易形成一个死锁:

  • 操作同步阻塞, 但是此时拥有对当前 resource 的写锁
  • tick 需要获取对当前 resource 的读取锁 (因为潜在的新节点会导致同步传输)
  • 二者之间无法存在 preemption 逻辑

因此会存在死锁的可能, 不过参考单机操作系统我们很难会遇到 “同步阻塞” 的问题, 因此设计操作系统的时候使用 mutex 是没有问题的, 但是在分布式系统中永远要做到 fault-tolerant 远程的阻塞和失败

所以这里就要利用 Lexical Confinement 的设计来辅助我们达到串行的思维逻辑链

Lexical Confinement 思路和实现

Lexical Confinement 是利用一个中心的单线程循环来处理所有的请求, 确保所有资源的读取和修改都是串行的, 从而实现了 mutex 的类似互斥功能, 但是粒度会更加粗糙, mutex 保护的部分我们称为 critical section 一般是一小段代码, 但是这个 lexical 的互斥粒度一般就会比较大一点

首先来看一个 lexical confinement 的写法例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for {
    select {
    case req := <- requestChan:
        // 处理请求
        handleRequest(req)
    case <- tickChan:
        // 处理心跳
        handleTick()
    case <- shutdownChan:
        // 处理关闭
        close (requestChan)
        close (tickChan)
        return
    }
}

在上述代码样本中, 这个 for-select 语法就是最标准的 lexical confinement 的写法, 仔细思考这里的逻辑:

  • select 语句会在多个 就绪 的 channel 中随机选择一个进行处理, 如果没有 channel 就绪就阻塞式等待
  • 单线程循环, 不会同时出现两个 channel 并发地访问, 接收某一个 channel 的信息之后就会被困在整个 case 语句内部而不会跳出到下一段;
  • 两个同 case 条件语句也不会并发执行, 也要等到当前 case 完全指令离开之后才能执行下一个 for 循环然后再执行对应的 case

因此我们可以利用这个写法的特性来实现我们的互斥思路, 不过就像我们上面所说, 这里的互斥粒度比较大, 用代码语言来描述就是
case 级别的 granularity; 因此我们可以结合这里的写法阐述一下 pb service 的一致性实现目的:

  • 根据 线性一致性 (Linearizability) 的设计要求, 集群内所有节点的 operation 顺序必须保持一致, 但是既然 primary 拥有最早的执行顺序, 不妨就让 primary 的内部执行顺序作为全局统一的执行顺序;
  • 在 primary 内部, 前一个指令除非确认 ERR 的情况下可以退出, 其他情况后续指令都必须等待当前的所有指令完成之后才能继续执行下去;
  • 如果在 primary -> backup 同步的时候发生了阻塞, primary 要确保仍然可以执行 tick() 来保持自身活性
  • tick() 期间如果从 view service 得知 view num 更新, primary 就要考虑 push 的同步, 这时候会访问当前的 resource (read-only)
  • push 的实现也应该是一个阻塞式同步, 思路和 operation 一致, 即同步的时候也要确保 tick() 的可用性, 这里还会有一个叠加的可能, 也就是 tick() 内部还有可能会发生更加新的 view num 更新, 这时候就要确保本层的 push 不是一定成功
  • 幂等性 (Idempotency) 的设计, 也就是同一个请求多次执行和执行一次的结果是一样的, 这样就可以避免因为网络问题导致的重复请求的问题, 这个在英文语义上也经常被表述为 At-Most-Once

接下来几段将会讨论这些设计思路的实现细节

线性一致性 (Linearizability)

如上文所述, 线性一致性的设计要求集群内所有节点的 operation 顺序必须保持一致, 但是既然 primary 拥有最早的执行顺序, 不妨就让 primary 的内部执行顺序作为全局统一的执行顺序;

所以这里思考设计的就是 primary 节点内部的语义和逻辑顺序, 假设我们以有 backup 的情况下请求到来的情形为例:

  1. Client 请求到达, primary 接收请求
  2. priamry 处理请求, 并且将请求同步到 backup
  3. backup 确认同步成功, primary 返回结果给 client

这样我们可以确保: 只要 client 收到成功返回, 就说明整个系统内部实现了同步一致性, 并且完成了改请求; 因此根据要求 primary 就需要保持对当前视角下 backup 进行同步, 这样就确保了 backup 内部执行顺序和 primary 也完全一致

如果 backup 同步期间挂了? 这时候 primary 就在 tick() 中知道这个 backup 无了从而退出同步尝试 或者更换一个同步节点到新的 backup 进行同步

逻辑结论: 只要 primary 返回给 client OK 就说明内部已经实现了资源的统一

pb 同步的活性维护

如果是根据我们传统的 mutex 设计思路, 这里就是一个无限的等待, 如果不执行 tick() 就会被 view service 踢出集群, 但是如果执行 tick() 就会导致当前的同步阻塞, 这就是一个死锁, 如果不加这个锁就会导致 race condition

不过用 lexical confinement 的思路, 如果仍然是使用上文提及过的大 for-select 来进入 tick 执行逻辑, 那么就说明我们的执行流要回到最顶层, 那就有可能会先执行下一个 operation 而不是下一个 tick 请求, 这就和要求的 下一个 operation 只有在当前 operation 执行 OK 或者明确报错 找错 primary 的时候才能开始执行 这个逻辑相违背, 所以我们不能让执行流回到上层的 for-select 循环, 但是我们仍然要执行一个新的 tick(), 所以我们只能在低层级设计一个新的 for-select 循环, 这里 for 确保最终同步成功, select 来确保有 tick() 请求的时候能够执行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for {
  case <- tickChan:
    handleTick()
  default:
    // 同步实现
    ok:= call(Backup, "Operation", OpArgs, &OpReply)
    if ok && OpReply.Err == OK {
    // INFO: 这里注意一个很逆天的机制, 针对 select 的退出机制是 break,
    // 但是我们一般不只想要退出这个 select, 而是想要退出整个 for 循环
    // 所以要用 return
      return 
    }
    time.Sleep(PingInterval)
}

就是这样的实现, 既可以确保有 tick 的请求的时候可以执行 tick, 也可以确保最终同步成功

push 的类似实现与层级式叠加

push 的实现是和 operation 类似的, 也是一个阻塞式的同步, 但是 push 的时候会访问当前的 resource (read-only), 这时候也会有一个叠加的可能, 也就是 tick() 内部还有可能会发生更加新的 view num 更新, 这时候就要确保本层的 push 不是一定成功

所以我们在内部留一个 for-select 接口给 tick() 来调用, 如果 tick() 期间发现 view num 更新, 说明会在 tick() 内部就实现了 Push() 的执行, 也就是 每次离开 Push()/tick() 请求的时候 Primary 一定完成了对 View 的最新同步

不过注意 tick() 本身并不返回或者说其不是阻塞式的, 因此其退出并无所谓, 更重要的是 Push() 请求的退出机制, 或者说是多层 Push 后底层的退出机制

如果在 Push 同步的过程中 backup 挂了怎么办? 考虑在新的 tick 到达之后直接在新的 tick 内更新 view 并且完成 Push, 然后返回到本层 Push 中, 这时候应该发现目标的 viewNum > 本地 viewNum, 从而优雅地终止这个 Push

幂等性 (Idempotency)

幂等性 (Idempotency) 的设计, 也就是同一个请求多次执行和执行一次的结果是一样的, 这样就可以避免因为网络问题导致的重复请求的问题, 这个在英文语义上也经常被表述为 At-Most-Once

然后由于单机操作系统可以保证其内部的操作是原子性的, 也就是有很好的 一致性语义, 所以这里要考虑的只有通信丢失导致的一致性问题和幂等性问题

一般来说最直接解决幂等性问题的思路就是在 server 端添加一个记录 seqNo 的执行 id 来确保不要重复, 同时这个 seqNo 也可以确保是对每一个 client 发出顺序的一致性 (回忆兰伯特时钟的设计逻辑, 这里应该是本地线程先后执行的顺序因果关系)

针对 Push 的设计, 其中的 幂等性也很容易保证, 只要确保某一个 viewNum 没有被多次重复 Push 就可以了, 即将这里的 viewNum 作为 seqNo 来使用

Split-Brain/ Network Partition 问题设计

脑裂问题指的是 primary <-> viewservice 之间通信失败导致 priamry 误以为自己是 primary, 但是实际上 viewservice 已经选举了一个新的 primary, 这时候就会导致两个 primary 的问题, 这时候 client 端如果按照 cache 的 primary 去进行操作就会导致失效

一个最直接的实现思路是 server 自身如果超过 DeadPings 次给 vs 发包失败没有响应就直接自己把自己提出集群拒绝服务, 这个和下一段讲的 lease 思路类似;
很多传统分布式系统会在这里提出 lease 的概念, 也就是给每个 primary 一个周期, 周期内确保有效, 到达周期交界点就要重新向 viewservice 确认身份来保留 lease. 这个方案会存在一个性能问题, 但是让我们先分析这里的 failure 背景:

  • 如果是 primary -> viewservice 的通信丢包, 这时候 viewservice 确实会在 DeadPings 次数后选举一个新的 primary, 但是原 primary 仍然会继续作为 primary
  • 如果是 viewservice -> primary 的通信丢包, 这时候原 primary 仍然会继续作为 primary, 但是 viewservice 会在 DeadPings 次数后保留这个 primary

考虑上述的第二种情况, 这时候如果根据 lease 的做法, primary 无法持续拥有这个 lease, 因此 primary 会失去身份, 但是实际上如果 client 发送请求到这个 primary 其就会拒绝服务告诉 client 请求失败了, 这时候 client 就会重新向 viewservice 获取 primary, viewservice 会返回当前的 primary, 也就是原 primary, 这其实是对性能的浪费

考虑一个更优秀的方法: primary 给 backup 发送请求, 通过 backup 的身份检查 (role== Primary && Source != Client) 来返回一个 ErrWrongServer, 并且可以顺带返回一个 “backup” 的现在的 viewnum 来告知 “primary” 新的 viewNum, 此时如果 primary 发现其心中的 “backup” 的版本更高, 那自己就不用玩了, 这时候再退出就好了

这样就避免了上述第二种情况的 lease 失效问题, 也避免了 client 端的无效请求

优雅的关闭处理

在 Lexical Confinement 的设计往往会留下一个 terminate channel, 用来优雅地关闭这个线程, 这里的设计思路就是在主线程中发送一个关闭信号到这个 channel, 知道 for-select 最终能到达这个 channel 并且处理退出机制

不过我们考虑一种情况:

请求 A 到达之后卡在了 opChan <- A 的入口, 如果我们这里直接暴力退出整个 lexical confinement, 这个请求就不会被处理, client 端调用的 RPC 就会在这里卡住, 所以非常的不优雅;

我们的目的应该是让这里的所有堵塞的请求都能被返回 ErrWrongServer 的错误, 那么我们这里其实可以添加一个退出机制, 首先关闭退出所有的 stale 请求, 然后在所有 channel 都被清空之后就走 default 来关闭剩下的所有 channel

1
2
3
4
5
6
7
8
9
for {
    case <- opChan:
        // 对于阻塞式的请求, 要返回到其 return waiting channel 上
        opReplyChan <- ErrWrongServer
    case <- tickChan:
        // 对于非阻塞式请求, 啥都不用写
    default:
        // close 所有的 channel
}

总结

根据我们上述的设计思路, 我们实现的 PB storage system 具备以下语义:

  • tick() 永远不会阻塞, 并且在任何情况下都可以被执行
  • Operation() 返回的前提是 cluster 同步了该请求
  • Push()/tick() 返回的前提是 cluster 同步了该 view