System|分布式|Aegean Replication

Aegean是微服务下的备份方案，目的是在微服务架构下保持Replication的高效性。

Aegean: Replication beyond the client-server model SOSP 2019

传统的Replication通常基于RSM状态机，然而现在的状态早已不是单机化的，微服务的嵌套调用使得C/S架构下的Primary/Backup和Paxos等传统协议不再高效。

In a world of large-scale systems and microservices, it becomes imperative to rethink our replication protocols to allow for interactions between multiple components. This paper puts forth a number of techniques that allow interacting services to be replicated both safely and efficiently in this brave new world.

问题陈述

这些问题都处在middle service中，问题出在嵌套的请求只能由一个服务发出，而不能由整个集群发出(share backend的情况下）。

举个例子，如果middle service的每次修改都需要使得backend的counter++，那么整个集群只能发出一次有效的++，由某个具体的服务发出。

响应丢失

Primary-backup

仅由Primary对backend发出嵌套请求，在Primary崩溃后，Backup并不知道这个请求的状态

Paxos-like

假如某个服务器发出了嵌套请求后崩溃，即使由其他服务器恢复了状态，但是response依然无法返回到那个崩溃的服务器上，导致请求失败。

Speculative execution

Zyzzyva在达到一致之前就先执行请求，如果无法达到一致就回退，这个和CPU的speculation差不多。问题在于这个rollback过程即使可以在本机运行，却无法撤回嵌套请求。

总结

Replicated client - 备份之中的每个服务都可能发出请求，并且视为整体发出的请求

Durability of nested responses - 嵌套请求的响应应该被足够的middle service接收

Speculative execution - 不能进行预测执行

Replication

Server shim

解决Replicated client问题，如果所有备份服务器都能发出嵌套请求，那么后端必须能够避免重复执行，而结果又能由所有备份访问。这个shim层加在backend service上，相当于对backend的输入输出进行filter。

• Receiving request - 会收集请求而不立即发出，直到数目达到r+1(不一定是半数，看失败模型)再传给backend replica(例如primary),并且忽视剩下的请求。
• Sending response - 会收集响应并且返回给对应的middle replica，并且维持最后一次响应的cache进行retry

Durability of nested responses(注意这里的durable指的是响应没有丢失)

当middle service接收到请求时，它会向其他replica发出ack，仅当收到包括自己在内的u+1个ack才会commit(u指的是允许失败的上限)

但实际上，这里实现时做了优化，直接在server shim完成，而不需要进行上面这个阶段

思路如下: 当之前的响应没有durable时，不会响应嵌套请求

• middle对本次请求的所有嵌套请求都增加额外参数，是之前所有嵌套响应的递归hash
• backend仅当收集到max (u,r) + 1个一致请求时才会响应这个请求

非常有趣的设计，r+1是为了确保收到的请求满足上面的要求，u+1则是确保请求已经durable了。通过在请求中额外加入参数，同时保证了响应收到>u+1并且请求发出>r+1

Taming speculation

Spec-tame is based on the insight that nested requests are a type of output commit to an external observer. It is therefore possible to employ speculation within the service, as long as the speculation is resolved before the output commit happens. Essentially, spec-tame applies the idea of “Rethink the sync” to interacting replicated services.

作者这里用了Eve这个预测执行的协议举例(a protocol for replicating multithreaded service), 基于execute-verify架构。

核心思想: using it internally, but resolving it before performing output commit

意思是我可以先在本地预测并且执行相应的修改，但是当我需要嵌套请求(output commit，对backend产生影响，无法回滚)时必须验证预测是否正确。

• 首先由于上面的机制，多个replicas同时发出请求。(Replicated client)
• execute - 一组并行批处理的请求称为一个parallelBatch，他们并不会直接进行嵌套请求，而是同时执行到发送嵌套请求前(barrier）。
• verify - 然后将状态以及即将执行的嵌套请求做merkle tree校验，和其他备份进行比较。

• 如果校验结果相同，说明预测成功，可以继续执行嵌套请求。标记为稳定状态。
• 否则说明预测失败，备份没有达成同步，回滚到上个稳定状态。

作者也强调了，嵌套请求其实也是可以回滚的，但是这样要求backend支持事务，侵入性过大。所以作者认为这个过程应该放在middle service，避免预测失败的嵌套请求。

Sequential Execution

然而，在多服务的情况下，请求顺序执行就很难了。

顺序执行的情况下，在执行嵌套请求的时候，middle service必须等待。

这里有趣的在于把请求进行了流水线化，响应回来之后并不是立即执行后半截，而是等待所有流水线中的响应(深度)。此外，嵌套请求还赋予了sequence，方便backend顺序执行。

需要注意的是，这里的响应处理并不是严格按照FIFO的，因为对于其他备份来说，有可能r3的响应先于r1到，因此采用RR来解决响应顺序问题。

这个实现基于假设，所有的嵌套请求在确定性的时机执行。

用户可以自行使用锁来保证linearizability。

此外，在达到Barrier时，parallelBatch会进入idle，此时可以切换到其他parallelBatch。这样流水线也能并行。

实现

Implicit agreement就是上面提到的max(u,r)+1，确实很秀

Optimize是特殊情况下的，不关注状态只关注输出。

避免死锁指的是idle时如果拿不到锁，并不是阻塞住，而是yield pipeline

这个问题其实很经典，OS中就有一种名叫优先级反转的问题，意思是明明优先执行的线程，却在等待低优先级的线程放锁。问题就出在锁调度和线程调度的不协调上。

这里的思路也是一样的，RR要求流水线轮流执行，但是如果之前的请求拿了锁，那么锁调度(应该由前面的线程执行)和RR调度(应该由后面的线程执行)不协调。

在OS中，解决方法一般是线程调度向锁调度让步，例如

• 优先级继承协议PIP(高优先级被阻塞时，继承给锁持有者优先级)
• 不可打断临界区协议NCP(线程调度向锁调度让步，不可打断)
• 即时优先级置顶协议IPCP(拿锁时，锁持有者直接拥有所有竞争者中最高优先级)
• 原生优先级置顶协议OPCP(高优先级被阻塞时，继承给锁持有者所有竞争者中最高优先级)

在这里，也是一样，RR调度向锁调度让步，使得下一次调度的线程会是拿锁的线程，从而解除死锁。不过这样说起来，感觉效率就不怎么高了，毕竟每次调度都要yield一轮。

总结

Problem: 从CS到微服务，没有适合嵌套调用的Replication模型

Related work: 会出现响应丢失，预测无法撤回的情况

Observation: Shim+ Taming speculation+ Pipeline

Solution: Shim维持多请求多响应，同步确保预测正确，Pipeline保证性能

Evaluation: 性能UPUP，正确性有保证

Comments:

shim的设计和pipeline都很精妙，尤其是shim进行了二合一，后面避免死锁让我想起了刚上过的OS课。

微服务集群因为崩溃而导致响应丢失，这个问题感觉确实很有必要，毕竟不管有没有状态都有可能发生。

针对备份的问题，这里实际上针对的是share everything的有状态服务器中间层((共用backend)，个人想了想其他分布式系统怎样解决的:

有状态服务器中间层可以采用share nothing，比如primary有属于自己的backend，每个backup也有属于自己的backend，这样就可以不考虑丢失问题了，每个服务器都能向backend发送请求，响应丢失也就丢失了，反正整个backend也丢失了。

个人想了一下，感觉spanner就是我说的这种，Paxos集群各自拥有自己的数据存在Colossus里面，而Colossus里面又对于数据进行备份。