全局序列协议：复制共享状态的健壮抽象 - 《Apaas平台》

论文地址：全局序列协议：复制共享状态的健壮抽象-Burckhardt等人。2015年

这是我们本周到目前为止一直在撰写的ECOOP’15论文。问题领域是支持跨节点（此处是移动设备）复制共享数据并最终保持一致性的常见愿望。在移动环境中，这可以实现断开连接的操作，并减少对电池寿命的需求。作者对论文的贡献作出了自信的断言：

总的来说，我们的工作通过提供一个可理解的高级系统和数据模型，以及一个包含强大而有趣的优化的健壮实现，标志着朝着在设备上自动复制、弱一致的共享数据的可信编程模型迈进了一大步。

全局序列协议是一个通用的协议，在此协议之上可以构建许多最终一致的数据类型。这样就让我想起了Viewstamped复制。这将GSP与以前在复制数据类型上的工作区分开来：

与我们的工作一样，复制数据类型（尤其是crdt）为某些数据类型提供了优化的分布式协议。然而，CRDTs不容易定制和组合，因为一致性协议不像GSP那样与数据模型完全分离，而是专门用于特定的、固定的数据类型。

作者实现了我们昨天看到的云类型模型，但发现它在以下几个方面有所欠缺：

客户机程序员仍然很难对最终一致的程序的行为进行推理
对于某些应用程序，需要在同一程序中混合最终读取和同步更新
实现需要健壮，并处理故障状态等。

核心全局序列协议
要编写正确的程序，我们需要一个简单而精确的存储心理模型……根据我们的经验，理解复制数据所需的关键心理转变是将程序行为理解为一系列更新，而不是状态。为此，我们通过一组更新和查询来描述共享数据，并通过导致共享数据的更新序列来表示状态。

GSP可以处理许多不同的数据模型。与我们昨天看到的QUA类似，数据类型由一组读取操作、一组更新操作和一组读取操作返回的值抽象。此外，还定义了一个读取值（rvalue）函数，该函数接受一个读取操作和一系列更新，并返回将序列中的所有更新应用于数据初始状态所产生的值。（让人想起只追加日志和事件存储）。

例如，我们可以定义一个简单的计数器，如下所示：

Update = { inc }
Read = { rd }
rvalue (rd,s) = s.length

（核心GSP）协议通过定义每个客户机的状态，指定数量有限但不受限制的客户机的行为，以及响应外部刺激而触发的转换。转换分为两类：到客户端程序的接口（从更新和读取操作到达的地方）和到网络的接口（从消息到达的地方）。客户机使用可靠的总顺序广播（RTOB）进行通信，RTOB是一种组通信原语，它保证所有消息以相同的总顺序可靠地传递给所有客户机。RTOB已经在分布式系统的文献中得到了很好的研究，并且经常被用来构建复制的状态机。它可以在各种拓扑结构（如客户机-服务器或对等）上实现，并具有不同程度的容错能力。我们在第6节中描述了一个特殊的实现和重要的优化。

轮是由特定客户端编写的更新：

class Round {
    origin : Client,
    number : N,
    update : Update
}

客户保持三种状态：

客户最近提交的一轮的轮数
一个已知的轮次序列，表示客户端已知的全局更新序列前缀
一个轮次序列，待定，表示客户端已发送但尚未在已知全局更新序列中确认的轮次

当客户端程序发出更新时，我们

（1）将此更新附加到挂起的更新序列中，并且
（2）将更新包装成一个Round对象，该对象包括源和序列号，并广播该Round。

update(u : Update) {
    pending := pending + u;
    RTOB_submit(new Round{origin = this, number = round++, update = u}); 
}

（上面的+表示序列连接）。

通过将rvalue应用于已知全局前缀与客户机自己的挂起更新的连接，可以给出read返回的值（从而给出read-your-writes语义）：

read(r : Read) {
    var composite_log = known + pending;
    return rvalue(r, updates(composite_log))
}

（上面的updates函数给出了来自Round序列的更新序列）。

剩下的就是指定当通过网络接口接收到一个回合时的行为：

onReceive(r : Round) {
    known := known + r;
    if (r.origin = this) {
        assert( r = pending[0]);
        pending := pending[1..];
    }
}

从设计上讲，核心GSP并不完全一致：更新是异步的，并且会延迟生效。不知道这一点的程序员很容易遇到麻烦…

一种解决方法是在需要的地方引入同步，一种更优雅的替代方法是使用更丰富的数据模型，例如为计数器公开“add”操作，而不是“set”操作。

幸运的是，我们可以很容易地在数据模型抽象之上定义更高级别的数据类型。特别是，我们可以实现之前工作提出的完整云类型。云类型允许用户定义和组合前面给出的所有数据类型示例（寄存器、计数器、键值存储）以及支持动态创建和删除存储的表。

核心GSP是：

静态一致，因为当更新停止时，客户端聚合到具有空挂起队列的相同已知前缀。
最终是一致的，因为所有更新最终对所有客户端可见，并且是按照相同的仲裁顺序排序的
因果一致性，因为某个客户端的更新U在发出U时，在初始化客户端可见所有更新之前，不能对其他客户端可见。
事务和同步
事务GSP添加推拉同步操作，并确认同步查询。当一个客户机同时进行了多个打算成为原子的更新时，不能一次发布一个，否则其他客户机将看到部分结果。

为了解决这个问题，GSP使用了transactionbuffer。客户端程序执行的更新将进入此缓冲区。当客户端程序调用push时，缓冲区中的所有更新将在一轮中广播，并且只有在那时…。事务缓冲区中的更新包含在复合日志中，因此可立即用于本地读取。

为了提供读稳定性，GSP使用一个receiveBuffer：

接收到的子弹存储在此缓冲区中。当客户端程序调用pull时，receivebuffer中的所有轮次都会被处理，并且只有在那时才会处理。因此，客户端程序可以依赖于读稳定性——只有在发出pull或执行本地更新时，可见状态才能更改。

如果没有等待确认的本地更新，则confirmed操作返回true，因此可以使用它来确定更新是否已提交到全局已知序列中。

GSP具有足够的表现力，允许客户端程序在需要时恢复强一致性。为此，我们可以编写一个刷新操作，等待提交所有挂起的更新（同时接收任何其他更新）：

flush() {
    push();
    while (!confirmed()) { pull(); }
}

同步更新可以通过调用update（）和flush（）来实现。同步读取是flush（）后跟read（）。

在作者编写的反应式web应用程序中，当事件队列为空时，在事件处理程序之间自动调用以下yield（）操作：

yield() {
    push();
    pull();
}

我们的更新事务不同于传统事务（读提交、可序列化、快照隔离或并行快照隔离），因为它们不检查任何读或写冲突。尤其是，他们从不失败。其优点是它们具有高可用性，即不受网络分区的限制。缺点是不像可序列化的事务（但是像read committed，
快照或并行快照事务），它们不会保留所有数据不变量。

有效实施
上面的模型很容易理解，但不一定有助于高效和健壮的实现。作者给出了一个流实现，并通过改进证明了它忠实地实现了GSP模型。

在本节中，我们将展示所有这些问题都是可以解决的，而无需更改抽象的GSP协议。具体地说，我们描述了GSP的一个健壮的流式服务器客户端实现。它使用套接字（双工流）对通信进行显式建模，并包含到服务器、客户端和网络的模型故障的显式转换。此外，它消除了所有更新序列，而是以简化的形式存储当前服务器状态和增量。重要的是，它在以下意义上是健壮的：

无论失败与否，客户端程序都不需要等待操作完成
连接可能在任何时候、任何一端发生故障
服务器可以崩溃并恢复丢失的软状态，但保留持久状态。持久化状态包括状态快照和每个客户端提交的最后一轮的轮数。没有存储的日志。
客户端可以在无限制的时间内静默崩溃或暂时停止执行，并且始终能够重新连接。
流模型不存储任何更新序列（既不在客户端，也不在服务器上）。相反，它急切地减少这样的序列，并以简化的形式将它们存储为状态对象（如果序列是全局更新序列的前缀）或增量对象（如果序列是全局更新序列的一段）。