1. Introduction
本文提出了一个新的复制协议Aegean，它的思路超越了传统CS架构，使得复制协议能保证正确（保持较好的一致性），且不极大的降低性能。
它的贡献点有：
- 问题描述：描述已有复制协议的缺陷，并指出新的复制协议的挑战
- 保证正确性：引入新技术server-shim、response-durability和spec-tame，并共同构建一个single correct machine (SCM) 的抽象
- 提升性能：引入新技术request pipelining，在多步操作/嵌套操作下不需要串行操作，降低了等待时间
2. 已有协议的缺陷和挑战
本文引入一个服务场景，服务是有状态的。它是一个多步嵌套操作，如下所示： \(client \rightarrow middle(replicated) \rightarrow backend\)
本文未实现环拓扑，因为没解决死锁问题
2.1. 已有协议的缺陷
a) 主从复制
主节点向从节点发送副本数据，等到从节点响应后，再响应客户端。
在多步嵌套场景下会有问题：
-
若$middle$主节点在确认从节点以复制之前，发送请求给$backend$，则有可能导致$middle$和$backend$不一致
$middle$向$backend$请求后挂掉的情况
-
若$middle$主节点在确认从节点以复制之后，发送请求给$backend$，或者发送$backend$请求后，等待所有副本的$backend$响应再返回给客户端，这样系统性能会非常差
这里指，$middle$返回响应给客户端时，需要保证副本的一致（即需要复制完成）
b) 类Paxos协议
类Paxos协议是基于quorum的，不过在多步嵌套场景下也有问题：
- 由于采用主动复制，从节点若不做特殊处理，$backend$会收到相同的请求，需要去重
- 去重也不足，当$middle$响应客户端后节点挂掉，其它副本需要返回与挂掉节点相同的状态，不易实现
- 在$backend$使用reply cache保存返回给客户端的响应，但不能应用于所有场景
- 对于BFT协议，还会引入安全性的问题
- 若保证正确性，Paxos也可以串行执行，性能同样不好
c) 投机式执行
这里有几个协议：
- Zyzzyva: 从节点未达成共识前，发送请求给$backend$，顺序还是保证的
- Eve: 顺序也会投机式的更改，且在多线程环境下，非确定性的请求也会投机式执行
投机式执行是能提高性能的，但是留下了很大的正确性隐患，需要有一定的场景前提。且投机失败需要有回滚机制。
d) 总结
根据上面3类设计，可以总结出下面几点：
-
复制的客户端（重复问题）：上面的服务架构中，复制的服务也可以作为客户端（即复制的客户端）请求下游服务，它们多个的相同请求应该视作一个请求
-
嵌套响应的持久性（一致性问题）：嵌套响应是$backend$对$middle$的响应，需要保证足够的从副本复制完毕后，才能向下游发送请求，或者保证收到足够的嵌套响应再返回给客户端
-
投机执行（性能问题）：嵌套请求不应该投机执行，因为它带来非常大的风险，尽管它性能好
2.2. 另外的设计
可以将服务设计成无状态的，然后用一个集中且容错的存储后端维护状态，服务间用可靠的消息队列传输数据。
这样，各个服务状态不需要各个服务自行复制，避免了2.1.的所有问题。
不过有一定的缺点：
- 服务状态必须编码解码
- 改变服务状态必须要和后端存储通信
3. 系统模型
本文中的系统模型和技术是通用的，可用于同步与异步系统，且适用于任何故障（包括拜占庭）。
模型涉及到的有：
-
存储后端：包括复制的和非复制的存储后端
-
故障模型：本文采用混合的故障模型UpRight
- liveness：系统在最高$u$故障下，一直可用
- safety：系统在最高$r$个commission failure（进程做了不该做的事情，不符合协议）和任意数量的omission failure（进程没有做该做的事情，符合协议）下，客户端接受的响应是正确的
- 故障节点不能破坏密码学原语
-
正确性：从SCM得到的不可区分性，即复制的服务输出与对应未复制的服务，两者输出一致。它不需要依赖第2节中协议的线性化。
若未复制服务是串行执行，那么复制的服务需要保证线性化
4. 保证正确性
这里介绍3个技术：server-shim、response-durability和spec-tame
4.1. Server Shim
它从传统复制系统的客户端shim层得到启发。它主要解决2.1.d)提出的第1个问题。
Server-shim单独在每个副本上运行，不需要协调。
它本质上是一个过滤器，主要做下面的事情：
- 接受请求：它会认证每个请求，以确认发送方
- 若无法确认，则转发请求到副本进行处理
- 若能确认，从复制客户端接受quorum个匹配请求，然后转发请求到副本，并忽略重复请求
- 返回响应：当$backend$返回响应时，它也需要
- 广播响应到所有的副本
- 每个复制客户端的每个线程有对应的缓冲，存储线程对应的最新响应，用于重传
4.2. Response Durability
当收到嵌套响应式，它会转发给ACK消息给所有的副本，当确认有$u+1$个副本收到ACK后，才能保证这个响应被持久化了，接着才能进行响应返回的操作。
不过它带来了很高的延迟，后文会说明如何利用$backend$服务来减少这个延迟。
4.3. Taming Speculation (Spec-Tame)
这里涉及2.1.d)的第3个问题。文中认为回滚投机状态，以及实现对应的隔离性是不可行的。
这里引入spec-tame，允许复制的服务能投机地执行请求，仍为未修改的后端服务提供SCM抽象。
这里的spec-tame遵循这个原则：
- 服务内部进行投机处理
- 当对外输出前，只要保证投机状态被处理即可
5. 解决串行执行的灾难——流水线
串行化执行会带来很大的空闲时间，性能会很差。本文采用了流水线方法来提高性能和资源利用率。
串行：
流水线：
5.1. 请求流水线化
串行能保证一致，但它是充分条件。而必要条件是请求的执行调度是确定的。
因此这里采用流水线的思路：
- 服务是可以一直接受$k$请求，并像下游发送嵌套请求，不必要等待嵌套响应返回后再接受下一个请求
- $k$是这个流水线的深度
- 若流水线满，后面的请求需要等待
- 一旦流水线有空余，后面的请求就可以执行
- 对于请求重试场景，若第一个嵌套响应在第二个请求之后，第二个请求会推迟执行
- 请求的顺序调度基于可确定的round-robin调度，使顺序与请求的到来无关
- 嵌套请求的顺序由序列号指定，它会在请求触发的时候获得
它肯定能带来性能上的提升，因为它提高了系统资源的利用率。
此外，本文提及流水线化尝试实现的是“不可区分性”，而非“线性化”，所以它尝试将“线性化”解耦，应用程序可自行选择一致性级别。当然“线性化”也是可以实现的。
5.2. 并行流水线
单流水线还可以再优化，让流水线并行化，从而可以并行执行请求，并使用了spec-tame。
6. 实现
代码基于UpRight和Eve，使用Java实现。其中做了3个方面的技术：
- 隐式共识：利用后端服务代表中间服务隐式执行协议
- 优化Eve：在CFT设置中检查差异时，忽略副本状态，仅比较副本输出
- 避免流水线的死锁：使用同步操作让线程使用流水线
6.1. 隐式共识
利用后端服务代表中间服务隐式执行协议：
- 后端将拒绝执行嵌套请求，直到它确保所有先前的嵌套响应都已被接受且持久化
- 利用后端服务，执行Eve协议的验证操作（使用请求和响应的稍带）
6.2. 优化Eve协议
在CFT设置中检查差异时，忽略副本状态，仅比较副本输出。
若状态不同，但输出一样，spec-tame是不会回滚的；若状态不同，且输出也不同，则通过选择其它副本进行状态转移来修复差异。
但若在拜占庭副本下，还是得保证状态一致。
6.3. 避免死锁
流水线下：当请求需要发送嵌套的请求时，会产生下一个请求的执行。
而RR下的请求调度，在还存在没执行完且手握共享资源的请求下，会引入可能的死锁问题。
例：$r1$拥有$x$的锁，然后发送了嵌套请求，产生$r_2$的执行。而$r_{2}$要获取锁$x$。这就有死锁：
- $r_{2}$要获取锁，等待$r_{1}$解锁$x$
- $r_1$需要等待$r_2$的执行，但手握锁$x$
这里实现了一个中间层来控制线程同步：线程会先通知流水线产生空位/打破栅栏。
这样，即使锁被获取，其它请求也不会等待锁的释放，本请求将执行的控制交给下一个请求。
7. 总结
感觉本文还是很抽象的，很难读懂（上面估计有很多问题）。不过提出的问题——有状态服务链式调用的复制，还是很需要解决的。
其贡献点，个人认为在于：
- 描述已有复制协议在链式调用上的缺陷
- 引入新技术server-shim（过滤层去重）、response-durability（持久化+复制一致）和spec-tame（投机处理以提升性能，但返回结果时，要处理投机的状态）
- 使用流水线来提高整体性能
