Hermes

2020-07-12

Introduction

当今的共识协议过多的关注于吞吐throughput，而忽视了延迟latency，例如Chain Replication，便是一个典型的利用延迟换吞吐的例子。但是目前延迟已经变成一个越来越重要的指标。

Hermes便是一个兼具吞吐和延迟的共识协议，对于读操作，则可以在任何副本上进行读取；写操作，任一副本都可以启动写入。

读取实现低延迟和高吞吐的关键在于：

  1. 能够在任何副本上提供读取服务

  2. 能在本地完成读取

写入能够实现低延迟和高吞吐的关键在于：

  1. 去中心化：为减少网络跳数并保持整个副本集合之间的负载均衡，任何副本都必须能够发起写操作并驱动它完成(通过与剩余的副本进行通信)，同时避免集中式序列化点。例如：CR就要求在特定节点上启动所有的写操作，因此无法分散写操作

  2. inter-key并发：对不同的key的独立写入应该能够并行进行，以启用内部和多线程并行请求执行。

  3. 快速：快速写入需要最大程度地减少消息往返次数，避免长消息链，以及hunning techniques，否则会增加写入延迟

可靠的共识协议

可靠的共识协议分为两类：1. 基于多数的协议，通常是Paxos的变体；2. 要求活动节点具有稳定成员资格的协议（即：基于成员资格的协议）

基于多数的协议: 要求大多数节点进行响应才能提交写入，因此只要大多数相应，它自然可以容忍失败。但是，基于多数的协议为了高性能付出了一些代价，因为在没有所有副本响应的情况下，无法保证给定的写入已到达所有副本。这使得本地读取成为一件非常有挑战的事情。因此，大多数基于多数的协议都放弃了本地读取。但是可能支持去中心化和inter-key并发写入

基于成员资格的协议：此类协议要求副本组中的所有操作节点都响应写操作。这样做可以确保已提交的写入已到达集合中的所有副本，这自然促进了本地读取，而不妨碍写入性能。

基于成员资格的协议需要通过其他协议（例如Vertical Paxos）选举出一组稳定的成员（使用租期lease）。通常，Vertical Paxos中的节点保存lease、membereship以及epoch_id。对于Hermes中的节点，只有其拥有了有效的lease才是可正常工作的。

当message创建时，其会被sender的epoch_id打上标记，如果receiver本地的epoch_id与message上的epoch_id不同时则会抛弃该message。

membership确定了一组可以正常服务于读和写的节点（只要其有有效的租期leaseo）。当failure发生时，membership将会通过Vertical-Paxos协议进行更新。简单地说，只有在租期到期后才更新成员membership，才能确保没有响应的节点在从membership中删除请求之前停止为它们提供服务(避免出现该节点已经在membership中删除了，却还在响应请求的情况)，而新请求只在已更新membership的剩余活动节点中完成。

CRAQ就是基于成员资格的协议。在CRAQ中，节点是按链组织的，写操作直接写入头部。头部沿链向下传播，直到到达尾部才完成。随后尾部向上游传播确认消息，使所有节点都知道写入的完成情况。CRAQ通过允许从所有节点本地读取来优化改善了CR。但是如果非尾结点正在尝试读服务，它已经看到了从头到尾向下游传播的写消息，但是没有看到ack消息向上传播，则其必须查询尾节点来查看写入是否已经完成。

CRAQ可以结合本地读取和inter-key并发来实现高吞吐量，但是无法满足低延迟要求：虽然读操作是本地的，因此非常快。但是写入操作必须依次遍历多个节点，从而产生了过高的等待时间开销。

Hermes

Hemers是一种可靠的基于成员资格的广播协议，提供高吞吐和低延迟，并且同时提供线性化读取、写入和RMWs(single-key transactions)。Hemers优化了无故障的常见情况，并以当今典型的复制程度(3-7副本)、数据中心内、内存数据存储为目标。

Overview

在Hermes中，读取操作完全在本地执行。写入操作可以由任何replica启动并快速完成、而不会发生冲突。如下图所示，写入一个key的流程如下：

  1. 启动写操作的副本（称为coordinator）向其余副本（称为followers）广播一个Invalidation(INV)消息，并等待acknowledgements（ACKs）
  2. coordinator收到所有的ACKs
  3. 一旦所有ACKs被收到，那么coordinator向所有的replica发送Validation（VAL）消息来完成写入

write process

现在先简单概述Hermes的显著特征，并在以下小节中做具体讨论。

无效： 当接收到INV消息时，目标key将处于无效状态，这意味着无法读取该key。但是并发写入同一个key不会失败，并且可以通过使用逻辑时间戳来解决。

逻辑时间戳： Hermes中的每个写入都使用单调递增的逻辑时间戳进行标记。该时间戳使用Lamport时钟实现，并在coordinator replica中进行本地计算。时间戳是[v, c(id)] 形式的按字典顺序排列的二元组，其中v是key的版本号，c(id)是协调器的Node ID。其中Key版本号会在每次写的时候自增，而Node ID则在节点启动时进行分配。当两个时间戳进行比较的时候，遵循这样的原则：总是先比较Key版本号，若Key版本号一致，则比较Node ID。为了公平起见，每个server会分配多个不同的Node ID，例如：server A分配的Node ID有：1/4/5, server B分配的Node ID有：2/3/6

高性能无冲突写： Hermes使低延迟写入的基础上、最大化并行写入以达到高性能写入。首先，写入操作是可以由任何一个replica发起，因此减少了网络跳数并确保了load balance。与全局有序独立写入来达到的强一致性相比，Hermes允许inter-key并发。在没有写入失败的情况下，Hermes的写入需要花费一个半折返(INV ACK VAL)，但是暴露的延迟只是一次往返。因为从coordinator replica的角度来看，一旦收到所有ACK，就可以安全地响应客户端，因为在这时候可以保证所有副本都看到该写入，并且将来的读取都不能反悔旧值。从follower的角度来看也只需要一个往返，该往返从接收到一个INV开始，此时每个follower以ACK响应并在收到VAL时完成写操作。

安全可重播写入： 节点或者网络故障可能会使key在某些或者所有节点中处于永久invalid状态。为了避免这种情况，Hermes允许任何invalidated operational replica在不违反线性化的情况下replay写入操作。这依赖于如下两点：

  1. 对于该key的new value会通过inv消息广播至所有的replicas。这保证了每一个invalidated节点都留意到了new value
  2. 逻辑时间戳保证了在所有的replica上全局有序的写入 基于以上两点，一个发现了invalid state key的节点可以开始承担起coordinator的角色，并且开始传播inv消息到其他拥有original timestamp的节点，并保持写入顺序。

上述特性使得Hermes提供了如下特性：

  1. 强一致性：通过在写入开始时将所有的replica设置的key设置为invalid，保证所有的valid的key都持有最新的数据
  2. 高性能：任意replica都可读写，读取操作是本地读
  3. 错误容忍：安全可重播写入。

Hermes协议细节

Hermes协议包括四个稳定的状态Valid、Invalid、Write和Replay，以及一个临时状态Trans

Reads: 一个读请求发往一个replica，如果在该replica server上该key处于Valid状态，那么则返回其local value。否则该请求将会被stall Writes: coordinator只有在该key处于Valid状态的时候才会发起向该key的写入，否则该写入将会被stall。其具体流程：

  • 更新Key Version Number，附加上自己的Node ID作为本次Write请求的时间戳
  • 广播INV消息，将Key设置为Write状态，并本地apply新的值
  • 一旦收到所有节点的ACK，将Key设置为Valid状态
  • 广播VAL消息 Follower：
  • 收到INV消息时，将消息中的时间戳和自己本地的时间戳做对比。当且仅当消息中的时间戳比本地高时将这个Key设置为Invalid状态，并更新Key的时间戳和值，否则就什么都不做
  • 无论时间戳比较的结果是什么，总是返回一个ACK
  • 收到VAL消息时，当且仅当消息中的时间戳与本地一致时将Key更新为Valid状态，否则就直接忽略这个VAL消息。

Write Replays: 当发现一个key处于Invalid状态一段时间时，则会触发write replay操作。该节点则开始充当coordinator角色，并将该key设置为Replay状态，并开始Write流程。

Hermes优化

  • 取消不必要的validations。当coordinator收到所有的ack时，发现了对于同一个key、拥有更高的timestamp的同时写入，则不在广播VAL，以节省带宽
  • 增强公平性。由于逻辑时钟是由key版本和node id组成，如果一个server分配一个node id，很容易造成不公平。采用了为一个server分配多个node id的方法
  • 减少block时间。在failure-free的情况下，在写一个key时，followers必须block读一个往返的时间。我们可以通过将实现改为follower向所有的server广播ACK，代替只是向coordinator发送ACK。这样当一个follower收到所有follower的ack时，便可以设置该key为validate

Network Faults, Reconfiguration and Recovery

网络连接问题：如果coordinator发送完INV之后经过一段时间没有完成写入，则重新发送INV消息。如果是follower收到INV消息之后很久没有收到VAL消息，则follower充当coordinator，开始对该key进行重新写入。

网络分区：如果发生了网络分区，那么只有拥有多数replica server的分区才可以服务于读写，其他少部分的replica server将无法提供服务。这使得可用性从允许n-1个节点故障降低到了允许n/2个节点故障。

成员变更：成员变更使用了一个叫m-update的东西，一个m-update包括：

  • 一个新的lease
  • 一批新的live nodes
  • 一个递增的epoch ID

一个接受了m-update的replica就可以当成coordinator了，这里需要注意：

  • 如果read处于Valid的key，仍然是按照之前的方式处理
  • 如果write或者read处于Invalid的key，则需要等m-update里面的live nodes接收到m-update。这是因为只有所有的replica可正常工作时，写入才能正常进行。
  • 如果一个follower还没接受到m-update，则会丢弃后续的消息，因为这些消息的epoch ID会比follower当前的epoch ID要大。这将会导致INV消息的重新发送，一直到所有的followers接收到了最新的memership并可以正常工作了。

Recovery:对于新增一个node，随着所有的replica被告知该新node加入进来，membership被可靠的更新。这时新加入进来的node被作为shadow replica并且作为一个follower参与到写入流程，但是不会直接服务于客户端。它从其他的replica读取，获取最新的数据。当读取完毕之后，该shadow replica则是最新的并且切换到了正常工作状态（此时可以正常接收客户端的请求）

Example

  • Node 1开始write A = 1，同样，node 3开始write A = 3。
  • Node 2收到Node 1的INV消息，回复了ACK，并且将Key A变成了Invalid状态
  • Node 3给Node 1也回复了ACK，但Node 3并没有改变A或者它的状态，因为A的LT是比Node 1发过来的INV要大的。
  • Node 2收到了Node 3的INV，因为这个INV的LT比之前的要大，所以Node 2更新了本地A的LT和value
  • Node 1收到了Node 3的INV，同理也更新了本地A的状态
  • Node 2开始一次read，因为A的状态是invalid，所以read会stalled，然后收到VAL的消息，就可以读取了，这时候读到的值是3
  • Node 1收到了所有的ACKs，但仍然将A变成了Invalid状态，因为之前收到从Node 3发来的带有更大LT的INV消息，但还没收到Node 3发来的VAL消息
  • 如果Node 3挂掉了，Node 1还没收到VAL消息
    1. Lease过期，Node 3仍然是failed，membership更新
    2. 从Node 1读取A，会发现处于Invalid状态，Node 1对A进行replay操作
    3. Node 2收到消息不用处理，因为有同样的LT
    4. Node 1收到Node 2的ACK，完成replay，并且广播VAL