本文是FAST'20 "Strong and Efficient Consistency with Consistency Aware Durability" 的学习笔记。

1. Background

分布式存储系统的研究的一个重要研究方向是consistency model，这个主题已经被人们研究得非常透彻了，但是却很少有人关注durability model，而durability model在很大程度上关系着系统的consistency与performance. 目前已有的两种durability model如下，这两种模型的不同主要体现在写入时系统的行为：

  • synchronous durability

    向系统写入时，只有写入内容在大多数节点上复制且持久化之后，才向client发送ack响应。这样synchronous durability 能够保证很强的一致性，不会出现stale reads等情况，但是同步带来的开销比较大，整个系统的性能会比较差

  • asynchronous durability

    向系统写入时，只需要在写入内容复制到系统中的一个节点之后，即可向client发送ack响应，此后副本在节点之间的同步和持久化都由background threads来完成。因为在写入的过程中不需要进行节点之间的同步，系统的写入性能非常好，但是会经常出现stale reads等情况

而本文提出的consistency-aware durability(CAD) 比较好的解决了上面两种模型的问题，在实现较高一致性的同时，又不会给性能带来太多损失。

2. Design

文章中提到的consistency-aware durability(CAD) 在两个方面对已有的模型做了改进：

  • Performance: shift the points of durability to reads from writes
  • Consistency: cross-client monotonic reads

2.1 Performance

在写入时，CAD的行为与asynchronous model相同，当写入内容复制到集群中的一个节点上(在 leader-based system中，这个节点通常就是leader)之后，就向client 发送ack响应。等到读请求到来时，如果节点发现要读取的内容尚未在集群中实现持久化，那么就会先将这部分内容在集群之间进行同步，实现持久化，完成之后，再向client发送ack响应。

可以看出，CAD的设计保证了写入时的系统的高性能，同时处理读请求时。又能提供比asynchronous durability 更强的一致性。而实际上，上面提到的处理读请求时，同步带来的开销并不大，有下面这两个原因：

  • 通常来说，写入内容之后立即读取新内容的情况出现的并不多，而CAD在后台会进行集群节点之间的同步与持久化，因此等到下次读请求读新写入的内容时，该内容大概率已经被持久化到磁盘上了，不需要再进行额外的同步
  • 如果写入后立即读取这种情况出现了，那么只有第一次请求该内容的读请求会触发同步，带来响应的开销，此后的读请求如果请求相同的内容，因为内容已经被持久化了，所以不会再触发同步

CAD是如何实现上述功能的呢？

该团队在ZooKeeper上实现了CAD，在系统处理读请求时，首先要进行durability check，来检查要读取的内容是否已经持久化到了磁盘上，如果是，那么直接返回响应的内容；如果不是，将请求重定向到leader，然后由leader进行同步，将新写入的内容复制到其他节点中，并进行持久化(flush logs)。

durability check的实现也不是很复杂。follower维护自己的persisted-index，表示最后一次写入磁盘的log的epoch-counter(和raft中的index意义相似)，而leader维护durable-index，表示被大多数节点持久化的log epoch-counter最大值。系统中leader会与follower定期地进行交互，这样leader就可以根据不同follower的persisted-index的值来计算出系统的durable-index的值

2.2 cross-client monotonic reads

乍一看这个概念比较让人费解，可以来看一下原文中是怎样表述的：

Cross-client monotonic reads guarantees that a read from a client will return a state that is at least as up-to-date as the state returned to a previous read from any client, irrespective of failures and across sessions.

大意就是，无论从哪一个client读取指定的内容，都不会读到比上一次更旧的内容。下图是一个比较简单的例子：

假设在同步a2时，S5从局域网中断开，一段时间后恢复，此时a2没有被同步到S5上；而此时如果读请求来到S5，那么client读取的值为旧值a1，这样就出现了不一致的情况。

为了解决上面的这个问题，作者提出了两种机制：

  • Active Set

    Active set至少包含集群中的多数节点，ORCA保证了下面两条原则

    • 当leader要对data item进行持久化时，必须保证data item要持久化到active set中所有的节点上
    • 只有active sets中的节点能够处理读请求

  • Membership using Leases

    此处membership指的是节点是否在active set之中。当节点宕机或者节点从集群网络中断开时，该节点就应该从active sets中剔除。ORCA中实现了两种“被剔除”的机制：

    • 节点认为自己已经被剔除

    • leader将节点从active sets中剔除

      需要注意的是，这两个是不一样的概念。两种情况分别对应不同的变量：mark-out timeout(\(mt\))和removal timeout(\(rt\))。\(mt\)时间后，如果follower仍然无法与leader正常通信，那么节点就会认为自己已经被剔除active sets；\(rt\)时间后，如果leader仍然无法与该follower进行通信，那么leader就会将该节点剔除active sets。通常来说，\(rt\)的值要大于\(mt\)，来防止出现non-monotonic的情况，具体细节可以参考论文4.4.2节，此处不再赘述。

可以看出，active set比较好地解决了上述问题。

3. Evaluation

可以看出，实现了CAD的ZooKeeper系统在性能上与week-zookeeper相差无几；

作者团队还实现了一套测试框架，用来模拟集群中机器的崩溃与重启，来测试cross-client reads的一致性：

可以看出，ORCA确实是实现了monotonic cross-cliet reads.

4. 后记

之前在读论文的时候，上来就是看paper，但读起来的话不是一般的吃力。我的英文水平自认为还可以，但是学术性的文章读起来还是有一些困难，而且即使是精读Abstract和Introduction部分，在不熟悉相应领域的情况下，也很难对整篇文章有一个整体的把握和理解。

在找这篇文章的时候，我发现USENIX主页上有对应的Presentation。在Youtube上看完后，就已经对文章有了一个整体的理解，读文章的速度也快多了。我想这是一个相当不错的读论文的办法，之后我也会重复同样的方法。