来自论文Rex: Replication at the Speed of Multi-core

对一系列请求的串行执行已经跟不上多核服务器的脚步了，但又不能直接并行化，因为并行会带来线程调度和锁竞争的不确定性，这就使得状态机复制的前提得不到满足，即要保持确定性。有一点要注意：全序的请求序列并不是保证一致性的必须，也就是说我们完全可以在并行化和一致性之间建立起双赢。本文旨在研究如何在多核机器上实现并行化，同时保证一致性，这样我们就会获得比一般状态机复制更高的吞吐率。那如何去实现这种并行化呢？

对于标准的复制状态机，是通过从一个相同的初始状态开始，以全序的顺序确定性地执行相同的请求集，从而保证一致性。而一旦并行，确定性就难以得到保证，所以这是我们的挑战。所以确定性的并行化就成了一个很热的研究方向，但是目前所采取的手段都是以牺牲性能为代价，还没有从架构上提供硬件支持的方法。Eve是通过mixer来实现了确定性的并行化，mixer会将请求划分成互相没有冲突的组，这样在不同机器上并行去执行这些组就有可能达到确定性和一致性。本文中我们提出Rex，一个execute-agree-follow模型，实现一致性。这个模型中有一个primary机器，一开始它会自由地去并行执行请求，在这个过程中会将不确定性的决定记录在一个偏序的trace中，之后其它的机器运行Paxos来对trace达成一致，最后secondary机器根据这个trace并行执行同样的不确定性选择，这样就跟primary机器保持了同样的一致性状态。进过实验，Rex会获得16倍于标准状态机复制的吞吐率。接下来让我们详细了解Rex。

Rex中有request handler，这个handler会通过标准的同步原语来控制线程对共享数据的访问，进而达到并行执行的目的。因为同步事件的次序是不确定性的唯一来源，所以这些handler会实现确定性。

1. Rex vs. State-Machine Replication

State-Machine Replication， 状态机复制使用consensus-execution模型，即首先会形成一个一致的请求序列（consensus阶段），然后根据这个顺序来执行请求（execution阶段）。这应该是最基本的想法了，要想保证在多个机器上执行同样的请求序列，首先要统一这个序列。但Rex却正好相反，它用的是execute-agree-follow模型，首先让primary去并行执行请求，同时把这些请求之间的细粒度的因果依赖关系记录在一个trace 中（execute阶段），primary会定期地将最新的trace作为value发给下一个consensus instance。之后各个机器会对一系列的trace达成一致（agree阶段）。一旦提交，secondary会根据这些trace来复制在primary上的执行（follow阶段）。也就是说Rex会在达成一之前在primary上去执行。在state-machine replication中，会在请求达成一直后处理请求，处理完后primary会给client一个回复。而在Rex中，在处理完请求后，primary不能去回复client，而是要等到一个包含请求处理的trace，并且这个请求所有的依赖事件都已经提交给一个consensus instance。不过，primary不用去等在secondary上的重新执行完成。接下来详细了解一下Rex的各个阶段。

?Execute阶段

首先在Primary上执行请求，在执行过程中primary上的request handler会记录同步事件集中的因果依赖关系。

Figure 2 是一个例子，两个线程在处理两条不同的请求，锁L被用来控制对共享数据的访问，Lock和Unlock会在两个线程间引起因果依赖关系，如图中的edge，Lock（L）要在Unlock（L）之后。我们之前说的trace中有同步事件，这个同步事件由线程的id和本地时钟来确定，而两个同步事件之间的因果顺序由一条有向边来表示，如在Figure 2中，Unlock（，3）到Lock（，2）是一条因果边。随着primary继续处理到来的请求，trace会一直增加。这里引入一个概念：cut point，即在一个线程中选出一个事件。来自每个线程的cut point会形成一个cut。一个cut包含了线程在这些cut point之前所有的事件，包括线程间的因果顺序。一个cut是一致的，是指在trace中从事件e1到e2的任何因果边，如果e2在cut中，那么e1也在cut中。如，在Figure2中是一致的，而是不一致的，因为对于，（，4）在cut中，而（，3）不在cut中。

?Agree阶段

Rex的replicas用多实例的Paxos协议在一系列的traces上达成一致。trace存的是并行执行请求过程中出现的不确定性的决定，在instance i提交的trace是在instance i+1提交的trace的前缀，实际上这是一个在不断增长的trace。当发生primary change时，在创建更长的trace作为提议给随后的consensus instance之前，新的primary必须首先learn前面consensus instance中提交的，并且重新执行（replay）上一个完成的consensus instance中的trace。

?Follow阶段

在follow阶段，secondary根据replicas已经达成一致的trace来执行。设想一下，如果线程t中的事件e必须要等到线程t’中的事件e’的执行，那么Rex会在执行线程t中的事件e之前暂停，并让线程t’中的事件e’执行完后唤醒线程t。这样，在每一个secondary机器上，线程的执行都会遵循一样的因果顺序。但是因为线程交错的不同，有可能会出现刚才例子中的线程等待。再来个例子，primary机器上有两个线程t1和t2，线程t1要在t2之前获得lock，但是在replay，t2首先被调度并先于t1达到了请求锁的点，在这种情况下，t2就要等待t1。实际上我们可以察觉到由因果边所反映的因果依赖决定了follow阶段的并行程度。对于依赖少的，就会获得高的并行性，对于依赖复杂的，就会因为线程等待而增加运行时间。其实能记录线程间的依赖，并能根据这些记录来约束线程的interleaving本身就很了不起，这避免了人工干预，实现了多请求并行处理的确定性，但能否去降低依赖的复杂度，从而提高并行性？比如去掉不必要的因果依赖。还有一个疑问：如果client提出来三个request，但这三个request之间相互独立，是不是直接并行处理就可以？如果是，能否在执行它们之前就知道它们相互独立，这样就省去了在执行过程中去记录它们的因果关系，这样其他机器就跟primary一样直接并行处理，就不必再根据得到的因果关系去处理三个请求。

2. Correctness and Concurrency

Correctness体现在三个方面：（i）一致性：所有的replica机器在一系列trace上达成一致，（ii）确定性：相同trace可以使得replica达到一个相同的状态，（iii）前缀：较早consensus instance中提交的trace是任何之后consensus instance中提交的trace的前缀。在状态机复制（state-machine replication）中，请求都是串行执行的，而在Rex则是并行执行：primary用Rex的同步原语去并行处理请求（为什么请求之间会有因果依赖顺序？），同时记录执行中的因果顺序。之后secondary机器会根据所记录的因果顺序去再一次处理这些请求。其实我们可以看到Rex的一个limitation：在primary执行过程中记录causal order和secondary根据之前记录的order执行都会增加Rex的overhead。然而论文中是这样来回答这个limitation：这个overhead是易控制的，而且在多核机器上带来的很高的并行性会对性能有很大提升。后面我们会详细了解这些理由。

3. Agreeing on Traces

Rex使用Paxos来确保一致性（consensus）和前缀（prefix）。Rex用Paxos来管理一系列的consensus instances，这样replicas就会在trace达成一致。

?Consensus in Rex

Rex使用的多实例Paxos可以检测出replica failures，也能选出一个新的leader（当现在的leader出错时）。其实这就从多核性能问题转向了容错问题，要考虑万一leader出错了，要能选出新的leader，这就要靠Paxos的第一阶段。投票数多的replica成为新的leader。在这个阶段，新的leader必须学习已经提交的proposal，并提出一样的value来确保一致性。在Paxos的第二阶段，leader得到在consensus instance中提交的提议。其实这里并没有详细说明Paxos到底是如何运作的。而Rex本身又在Paxos的基础上提出了两个值得注意的设计决定（design decision）:

首先，Rex在任何时刻至多有一个处于活动的consensus instance。Primary只有在了解到每一个earlier instance有一个提交的提议（proposal）后才提出一个instance。这个设计会在三个方面简化Rex的设计：首先，Rex不必管理多个处于活动的instances；第二，这很容易保证前缀，因为当发生primary change时，新的primary只是简单地学习上一次instance中提交的trace，然后replay这个trace；第三，在新instance中一个提议可以不用包含全部的trace，只需包含比上一次instance中提交的trace多出的信息。

（Primary会把前面instances中还没提交的提议都放在新instance的提议中。）

第二个设计，Rex中的Paxos的leader与primary共存（co-located）。Propose(i, p) 是向instance i 提出提议p。

这里再明确一下， Rex的primary与leader共存，处理客户端请求，定期创建traces作为为了一致性的提议。那些traces自然地满足前缀（prefix）的条件，因为它们是统一执行的cuts。

?Reconfiguration

当一个新的leader出现时，它会变成新的primary，而旧的primary则会变成secondary。

?Checkpointing

Rex通过checkpointing来让一个replica从错误中恢复过来。让primary在执行过程中定期地checkpoint是不好的。

4. Execute and Follow

Rex利用record进行replay，从而实现determinism的属性。在replay时也要有并行性。

?Wrapping Synchronization Primitives

如何保证各台机器上多线程同步操作具有相同的顺序，这是很关键的问题。Rex在通用的同步原语上加了wrapper。我们所说的记录因果依赖，实际上就是集成在这些wrapper中。

?Tradeoff between record overhead and replay parallelism

只有Lock和Unlock，记录中的因果关系式同一个lock上所有事件的全序。

在Figure 4 的右图中，在replay过程中，t3和t2不相互等待。右图要比左图记录更多的因果边，并且更多的共享资源信息。也就是说为了获得较高的并行性，Rex就要增加record的overhead，它们之间的tradeoff问题是Rex要把握的关键。

?Remove unnecessary causal edges

通过去除不必要的因果边（causal edges）可以减小trace的大小，并且也可以减少因为要检查因果边是否满足（satisfied）而带来的replay cost。所谓的不必要的因果边指的是这条边可以通过其他的边间接得到，例如Figure 4中的因果边X可以由A和t2内部的1->2边来代替，同理Y也是如此。这样之前我们所说的record的overhead就会减少，同时还保证了较高的并行性。

5. Discussion

Rex使用的是execute-agree-follow模型，Eve使用的是execute-verify模型，State-Machine Replication使用的是consensus-execution模型。Rex和Eve是应用在多核服务器上的两种不同的方法，尤其体现在在replicas间实现一致性的前提和性能机制。

?Consistency

Eve在verify阶段通过比较application states来检测出是否有divergence，从而保证consistency。Eve的这种做法很好：（i）verification可以很好得保证consistency，能检测出各种divergence， 如Byzantine faults和 concurrency bugs；（ii）replicas可以独立执行。然而在Rex中，replicas不再独立执行，因为他们要做出相同的non-deterministic决定才能保证consistency。再来比较二者的correctness，Eve的correctness取决于正确mark机器的states，而Rex的correctness取决于完全捕获到所有non-determinism的来源。Eve是事后检测，而Rex是提前检测。那究竟二者谁更胜一筹？

当然本文还是更倾向于Rex，理由是Rex中可以很容易发现locks和non-deterministic functions，因为之前我们提到Rex使用了自己的synchronization primitives，这样用Rex的同步原语来替换原程序中的接口，便很容易捕获到所有的locks和non-deterministic functions，这种替换是否类似LD_PRELOAD的机制？尽管如此，数据竞争还是很难去发现。但论文却说越来越多的人意识到数据竞争的危险，并在用数据竞争做同步时开始采取防范措施。

Eve中的状态标记本质上是将程序状态划分成两部分，没有做标记的状态称作context。

这里文章点出了Eve的execute-verify的一个limitation：We have found that handling on-disk state is tricky in the execute-verify model.意思是处理记录在磁盘的状态比较棘手。

Rex继承了Eve中verification的优点，如Result checking，用primary上的返回值来检查secondary上的结果。为了检测数据竞争，可以再trace中记录更多的状态和返回值，但是这回明显增加overhead，但是Rex通过resource-version checking的手段可以有效的找到数据竞争的根源。

?Performance

Eve和Rex都是为多核处理所做的努力，为了实现并行处理，Eve采用了mixer，mixer会将请求分成没有冲突的batches，这些batches就可以并行执行。但是对于Eve来说，如果要增加并行性，需要大的batches，但同时等待大的batches又会带来更长的latency，也就是说Eve会在latency和throughput之间有个tradeoff。

Rex不会去了解请求之间的冲突，文章说Rex将faithfulness作为重要的设计目标，因为faithfulness对性能有重要影响。

正常情况下，Eve的overhead主要是由运行mixer，追踪state改变和检测divergence引起的。而Rex的overhead则是由捕获不确定性decisions（它们包含同步原语）和在secondary机器上follow这些decisions引起的。到底谁的overhead更多呢？而且当检测出divergence时，Eve要roll back去串行重新执行，不过Eve认为这种divergence不是经常发生的。其实对于Eve来说，最重要的是mixer的使用，如果mixer不好，对性能会有很大影响。mixer要捕捉到当处理两个请求什么时候会出现conflicts，这时误报和漏报都会降低性能，所以降低mixer的误报率和漏报率是关键。而对于Rex，rollback只发生在primary出错和被替换，对Rex来说rollback就要比Eve的简单不少（是这样吗？）。

Rex: Replication at the Speed of Multi-core