论文阅读笔记（MeteorShower）

哎，拖更了，PhxPaxos 系列本来是打算一周一篇的，结果周中偷懒了一会儿，想着干脆拖到周末再写吧，但周四的时候收到邮件说下周二要例会做报告（= =# 为啥每学期都是第一个），于是这周基本就无法更新了，写篇论文阅读笔记做交代吧。这类型的笔记之前也会写，但基本不发，这次试试看吧。内容可能会偏翻译性质，但是水平有限，尽量避免渣翻。理解有误的话很正常，望交流。

原文来自 IPDCS 2017：MeteorShower: Minimizing Request Latency for Majority Quorum-based Data Consistency Algorithms in Multiple Data Centers。

介绍¶

背景¶

目前很多的存储系统都有跨数据中心部署的需求，具体表现就是同一份数据的多个副本会分散在多个数据中心，并且，副本的数量一般都可以根据工作负载的情况来进行调整。这种多副本位于多数据中心的形式可以很好地实现位置相关的访问，为用户提供就近访问，从而降低时延。但是，在为一份数据提供多副本时，由于需要维护数据一致性，会引入额外的代价。

不同的系统出于各自的设计，会向用户提供不同的数据一致性模型，典型的有 Linearizability、Sequential consistency、Causal consistency、FIFO consistency 等等。本文针对的是 Sequential consistency（后续翻译为顺序一致性）。

另外，在顺序一致性模型下实现容错的方法也并不唯一，本文针对的方法是 Majority quorum（后续翻译为多数派）。假设数据 X 的副本数量是 n，对 X 的读请求需要访问 r 个副本，对 X 的写请求需要访问 w 个副本，在这种情况下，满足顺序一致性的最小条件是 r + w > n。

在一般的实现中，会将请求转发给所有的副本，并在收到足够的 ACK 后就返回。但是，这种方法只有在副本间时延较低的情况下才能得到较好的效果。对于跨数据中心的情景，副本之间的时延往往很高，从而导致副本间通信的代价变大，最终使得在这种环境下使用基于多数派的顺序一致性模型会产生很高的请求时延。

0 0 于是就有研究工作可以做了。

问题描述及改进思路¶

基本条件：

跨数据中心：本文的应用环境，在同数据中心下的效果并不明显，甚至较差，这个在后续实验环节会提到。
键值存储：向用户提供键值的访问接口。
就近访问：用户的请求会发送到距离它最近的数据中心，并由该数据中心的存储实例进行代理。

上图是一个示例场景。三个数据中心 DC1、DC2、DC3，数据也是三副本。客户端距离 DC1 较近，所以它的读写请求均交由 DC1 代理。示例中流程如下：

代理发起了一个写请求，附带上该请求的时间戳，即 (x, v2, t1)。写请求会被发送到所有的副本上，此处假设 DC1 中的副本的 ACK 丢失，从而需要等到 DC2 和 DC3 的 ACK 到达才能够成多数派，进而返回（t3）。
代理发起了一个读请求，附带上请求的时间戳，即 (x, t4)。类似地，读请求会被发送到所有的副本上，在收到多数派的 ACK 后，选择其中时间戳最大的那个值作为返回值。

从示例中可以看到，造成读请求时延较高原因在于数据中心之间的 RTT 很高，即图中的 Lreq 和 Lrep。所以，本文的改进想法就是尽量去除掉这种 RTT 带来的时延，而尽可能的进行本地读。而为了在实现本地读的同时仍旧满足多数派的要求，就要求其他的副本周期性的将自身的状态信息发送给代理请求的副本，大致的思想如下图。

图中的 DC3 周期性的将自身的状态信息汇报给 DC1，可以看到，在这种改进下，虽然 DC3 到 DC1 的响应时延（Lrep）依旧存在，但消除了从 DC1 到 DC3 的请求时延（Lreq）。

接下来的工作即如何在这种改进下保证顺序一致性。首先，本文的所有请求和判断都基于时间戳进行，所以要求机器之间的时钟要尽可能同步。另外，从图中可以看到，本文引入了一个参数 θt，该参数定义了对数据 freshness 的要求（更多见下文）。

以图中的示例来描述的话，t4 发起的读请求，只有在 DC3 的状态消息附带的时间戳大于 t4-θt 的情况下，系统才认为该状态消息有效，进而可视作收到了 DC3 的 ACK，带来的效果就是可以直接进行本地读，从而消除了访问 DC3 的时延。

因此，θt 越大，状态消息有效的可能性就越高，从而降低时延的效果就越好，所以我们需要去寻求 θt 的最大值。

不过这种改进必然会对顺序一致性造成影响，比如在状态消息 Report 之后，DC3 和 DC2 之间又成功的进行了 Write，但仍未进行 Report，这将导致 DC1 上的 read 返回一个过期值。这也是 θt 需要合理设置的原因。

主要贡献¶

本文分析了在多数据中心的情况下，如顺序一致性这样的较强一致性模型引起高时延的原因。
本文提出了一个改进的容错算法，在实现本地读的同时保证是顺序一致性，从而降低了多数据中心情况下读请求时延。
本文证明了所提出的算法的正确性。
本文实现了所提出的算法的原型框架 MeteorShower，并使用不同的工作负载对其进行了评估。

算法设计¶

系统模型¶

存储实例之间使用网络互联，消息可丢失或延迟，但不能出错。然而可能是出于篇幅的原因，本文并没有描述所提出算法在消息丢失后该如何处理，所举出的示例基本都是假定消息只延迟不丢失。
由于时钟偏移，机器时间会存在误差，假设控制在 ε 内，可以使用 NTP 协议实现。
顺序一致性：一个合法执行的操作顺序从所有的进程上来观察都是相同的。

算法描述¶

下图为算法描述中所使用到的一系列数据结构。

用 C++ 进行一下定义：

// 用于收集两次状态消息汇报之间的状态更新操作。
using Status = list<pair<key, wts>>;
// 本地的 KV 存储，比如 LevelDB 等。
using LocalStore = ...;
// 维护其他副本汇报的状态，每次状态汇报都有一个 sts 时间戳，并附加每个键在该副本上的最近写入时间戳。
using StatusMap = map<replica, list<tuple<key, wts, sts>>;
// 记录无法立即完成的读请求的键以及时间戳。
using ReadSubscriptionMap = list<pair<key, ts>>;
// 副本列表，记录一个复制组的所有副本地址。
using ReplicaList = list<ReplicaAddress>;

写¶

本文没有对写操作进行改进，依旧是多数派写的常见流程。

接收到用户写请求的存储实例自动成为该请求的代理，为该请求生成相应的时间戳，然后将写请求发送给副本列表中的所有存储实例。当收到构成多数派的 ACK 后，就向用户返回写入成功。
一个存储实例接收到其他存储实例的写请求时，需要比较该写请求的时间戳和所写键的最近时间戳。如果前者大于后者就进行写入；如果前者等于后者，则利用存储实例间的 ID 大小顺序来决定是否写入，如果大于则写入。实质上就是利用时间戳和实例 ID 来构成一个比较关系。

状态更新¶

在问题描述里我们提到本文的改进思路在于利用主动的状态更新消息来去除 Lreq 带来的时延。所以副本之间是需要相应的状态更新算法，由发送和接收两部分组成。

周期性汇报：在一个实例执行写操作的时候，都会记录状态，这些状态会以固定的周期汇报给同一个复制组中的其他副本，每次汇报的内容都是增量信息。
处理其他副本的汇报：利用收到的状态消息更新对应副本的本地状态，然后尝试执行之前那些被挂起的读请求（如果该读请求的键在此次状态消息中有出现）。

读¶

本文对读操作进行了改进，不再去向其他副本发起读请求，而是利用其他副本的状态信息来进行判断，并在不可立即读的情况下把读请求挂起。

接收到用户读请求的存储实例自动成为该请求的代理，为该请求生成相应的时间戳，然后将带时间戳的请求转发给最近的副本（一般来说就是它自己）。
读请求能否立即返回取决于本地维护的其他副本状态。
1. 从所有的副本中找出满足以下条件的副本：拥有要读的 key，并且汇报该 key 的最近状态消息时间戳 sts + θt > ts。如果满足多数派，进入下一步，否则挂起。
2. 检查上一步找到的副本对该 key 的写入时间戳 wts，当该值小于等于本地时间戳时，才能够作为合理副本。如果合理副本数满足多数派，返回本地值，否则挂起。这一步是因为值是存储在本地的，状态消息中不包含值，通过这样的比较能够避免本地值是一个旧值。

从这个过程也可以看出来 θt 是一个可以衡量 freshness 的参数，该值越小，对状态消息的实时性要求越高，虽然这会导致挂起的可能性增加。

算法证明¶

引理 1¶

Lemma 1. For each execution δ and every process p, p’s read operations reflect all the values successfully applied by its previous write operations, all updates occur in the same order at each process, and this order preserves the order of write operations on a per-process basis.

先不考虑状态消息的更新，如果采用多数派读写，是满足引理的。因为任意一个通过读算法得到的多数派，必然和写算法时的多数派有交集，从而交集中至少有一个副本值为最新的写入值。另外，写请求是附加了时间戳的，这使得并发写入之间也是有序的。

本文的算法中的写操作依旧保持着原始的状态，所以不需要考虑。而读操作因为状态消息的原因，不再主动从其他副本 fetch 值，所以仅从本地来看，肯定是能保证读操作得到在它之前所应用的所有写操作的值的。

但是如果执行是从全局来看的话，如果不加任何限制条件的话，读操作不一定能够得到最近在其他实例上应用的写操作的值。

以上图作为示例，示例在完成了一个写操作后的 Δd 时刻发起读操作，Δd 接近于 0，同时假设 θt1 >= θt3 >= θt2。

我们先对图中的示例做点修改来看看一个无法满足全局要求的情况。假设由于网络原因，写操作在 DC2 上的应用时刻 t4 比读操作 t6 滞后，并且同样因为网络原因，DC2 还没有收到来自 DC1 和 DC3 的新状态消息，这导致了在 DC2 上，key 的值仍处于上一个状态。显然，此时 DC2 如果将值返回的话，就不符合引理的要求了，因为该值没有反应出 t6 之前的写入操作的应用结果。

所以，我们要对读进行一些限制，而限制的思路就是我们依旧需要构成读多数派，不过这个多数派是通过本地以及状态消息构成的，只有满足限制条件的状态消息所属的副本能够加入多数派。此条件即为 sts + θt > ts。可以看到，如果合理的设置 θt，我们上面的那个假设情况，DC1 和 DC3 会由于状态消息不够新，无法被加入多数派，从而发生在 DC2 上的读请求会被挂起延后。

让我们回到原示例，看看该如何选择 θt。其实很明显，在 t6 - θt 所表示的时刻，全局要能够构成写入的多数派，这样就能够保证读得到的多数派一定包含最新的写入值。在本示例中即 θt = θt3。

我们之前也曾提到过，θt 的取值很大程度的影响了读的性能，越大则越好。依旧借用此示例，来寻找 θt3 的一个上界，显然，它和 DC1 和 DC3 之间的时延相关，假设最小时延为 D，则 D 即为 θt3 的上限。因此，在实际应用中，θt 的选取和它所关联链路的最小时延有关。顺便提一句，θt 的下界是 0，即（几乎）每次读操作都会被挂起，等到有更新的状态消息到来后才能够执行读操作。

引理 2¶

Lemma 2. For each execution δ and every process p, p’s read operations cannot reflect the updates applied by its following write operations.

这个我觉得不太难理解，所有的读都发生在本地，读操作返回的值显然还没应用该读操作后续的写操作。

证明¶

略。作者直接引用了另外一篇经典论文：Sequential consistency versus linearizability，然后说我们接着它配合引理进行证明 = =#。我不是研究分布式一致性的，所以也没看过这篇论文，加之时间比较紧，此处就略过了。。

关键参数¶

θt¶

引理的证明中通过示例描述了 θt 的取值过程，但未推广，并且 θt 的取值实际还取决于写入的模式，所以此处需要进行额外的讨论。

多数派的写入至少有 WRITE_ALL 和 WRITE_QUORUM 两种。如果是 WRITE_QUORUM，那 θt 的上界值就是所有最小时延的中位数。如果是 WRITE_ALL，那么 θt 的上界值就是最小时延中的最大值。

同步时钟¶

之前的证明中都假设时钟没有偏差，但实际中是存在误差的，比如我们前面曾经提到的 ε，所以在确定了 θt 之后，仍需要减掉这部分误差，所以最后需要满足 θt >= ε。

一般来说，数据中心间的时钟误差都在个位毫秒，而时延在百位毫秒，所以本算法要求的 θt >= ε 是可以满足的。

MeteorShower 设计¶

消息¶

WriteNotification¶

实质上是对写操作的消息进行了封装，以便适应到不同的存储系统中。

WriteNotification = {key, update, wts, vn}

key：键
update：更新值
wts：写请求的时间戳
vn：本记录的版本号

状态消息（Status message）¶

状态消息是本文算法的核心，副本周期性地通过状态消息将自身（由于写请求导致的）键状态变化发送给其他副本，从而能够实现本地读的算法。

StatusMessage = {status,sts,seq,redundant}

status：本周期内的状态变化，(key, wts) 的列表。
sts：本状态消息的生成时间戳。
seq：状态消息的序列号，让接收者可以对状态消息进行排序。
redundant：冗余。显然，状态消息可能丢失，此参数将在当前状态消息上附带之前的 l 条状态内容，即最多容忍连续 l 条状态消息丢失。

实现¶

Status Message Dispatcher：负责周期性发送状态消息。
Message Receiver：负责接收消息并将它们分发到其他模块。
Status Map：维护其他的副本发来的状态消息，用于判断能否立即进行本地读。
Read Subscription Map：被挂起的读请求，在收到状态消息和写请求时可能会重新取出执行。
Write Worker：负责处理写请求。
Read Worker：负责处理读请求。

性能评估¶

实验设置¶

Google Cloud Platform (GCP)，3 数据中心，每个数据中心 3 实例。
基于 Cassandra 改造，比较对象为 Cassandra。
选取 θt 的上下界进行评估，MeteorShower1 表示下界（0），MeteorShower2 表示上界。
NTP：时钟误差 ε = 2ms。
利用 Yahoo! Cloud Serving Benchmark (YCSB) 生成工作负载。
状态消息的发送周期为 10 ms。

参数可调环境¶

在单个 GCP 的数据中心中模拟多数据中心以便利用 GCP 提供的参数控制功能来调整存储实例之间的时延。

上图为不同时延（RTT）情况下，各种算法配置以及读写模式下的读写时延。

在读方面，很明显，在低时延（0）的情况下，Cassandra 表示更好，因为它无论是 READ_ALL 还是 READ_QUORUM 都只需要简单的一次 RTT 即可；而配置了 M1 的算法，因为 θt 下界为 0，所以需要等待一次状态消息的到来（最差是 10 ms 加上半个 RTT）后才能返回，所以带来了时延；相较之下，M2 有接近于 Cassandra 的性能。

因为 Cassandra 是简单的 RTT，所以基本上时延就随着配置的时延变化而变化。而在时延增加后，本文提出的算法在 M1 和 M2 配置下都体现出了一些优势，一般来说，M1 最差只要等待 10 ms 和半个 RTT，所以表现比 Cassandra 要好；而 M2 在有些情况下是可以直接返回的，所以表现更佳。

而在写方面，比较了 WRITE_ONE 和 WRITE_QUORUM 两种模式，因为本文并没有改进写，基本没有区别。

汇总后大概是：

Cassandra：RTT
M1：10 + RTT / 2
M2：10

真实环境¶

真实的部署三个数据中心，其他情况不变。数据中心的时延情况如下图所示。

显然，因为数据中心间的时延不同，在各自数据中心中的实例中配置的 θt 上界也将有所区别：

Asia：75 - 2
Europe：50 - 2
U.S.：50 - 2

上图是对在三个数据中心中进行读请求的聚合结果：

Cassandra：因为是 3 副本，QUORUM 模式下时延取决于最近的数据中心（100 左右），而 ALL 模式下取决于最远的数据中心（250 左右）。
M1：类似 Cassandra，但只要半个 RTT。
M2：因为 θt 的存在，效果很明显。

上图按使用的方法进行了聚合：

Cassandra：还是 QUORUM 取决于最近，ALL 取决于最远。US (100, 150)、ER (100, 255)、ASIA (150, 255)。
M1：和 Cassandra 类似，但只要一半。
M2：因为 θt 的存在，效果很明显。但是注意 Asia 的效果要好于 Europe，因为它拥有更大的 θt。

上图按数据中心进行了聚合：结果还是因为类似的原因。

总结¶

论文主要的思路就在于引入周期性的状态消息，去除了读请求时的请求延时（Lreq），但为了仍旧保证顺序一致性，必须增加 θt 来进行限制。

哎，完全理解论文讲给别人听和理解论文要点就好这两种情况的难度差的好多，毕竟后者不用扣细节（捂脸）。