Virtual Consensus in Delos

0x00 基本内容

这篇Paper值发表在OSDI 20上面的一篇关于Consensus的paper。Delos可以看作是一种Shared Log的实现，其特点之一是总体上将系统分为Virtual Log和Loglets两个部分，也可以对应到Control Plane和Data Plane两个Plane。其基本架构如下图，对于Virtual Log和Loglets，两个部分提供的都是一般的Shared Log的接口，基本接口示意如下的代码，Loglet的核心是append的操作，读取为每次读取下一个entry，删除使用prefixTrim。这些接口和Corfu种使用的很类似，队医VirtualLog，在其之上还加入了一个Control Plane功能的接口。

class ILoglet {
    logpos_t append(Entry payload); pair<logpos_t,bool> checkTail(); 
    Entry readNext(logpos_t min, logpos_t max);
    logpos_t prefixTrim(logpos_t trimpos); void seal();
}
class IVirtualLog : public ILoglet {
    bool reconfigExtend(LogCfg newcfg); 
    bool reconfigTruncate();
    bool reconfigModify(LogCfg newcfg);
}

在两层的抽象设计之上，只有VirtualLog必须要考虑fault-tolerant，Loglets则不是必须的。VirtualLog在一个Loglets的集合之上构建出一个Shared Log的抽象，给客户端提供一个强一致的(i.e., linearizable), failure-atomic, 以及高可用的shared，append-only virtual address space。这虚拟的地址空间有多个Loglet组成，VirtualLog来维护Loglets到VirutalLog的映射关系，一个Loglet在一个shared log为一个segment，不同的segment根据在虚拟地址空间中的位置组成一个chian。在IVirtualLog中相对易ILoglet添加的接口中，reconfigExtend用于改变active segment，这样append操作切换到另外的一个Loglet，reconfigModify用于seal一个segment，reconfigTruncate移除chain上的first sealed segment。如果trim了第一个seal的loglet的时候，prefixTrim可以引起reconfigTruncate调用。VirutalLog相关的一些东西：

对于VirutalLog，其主要有两个组件，一个client-side layer给用户提供shared log的接口，而一个MetaStore保存元数据信息。Client可以发起一个reconfiguration请求，complete一个reconfiguration可以有另外一个client完成。可以有另外一个client完成的设计是为了处理发起的client故障。Reconfiguration的操作需要先sealing原来的chain，并添加一个新版本的chain。Seal操作先通过sealing最后一个Loglet来完成。完成之后还没的append操作会被拒绝。Seal操作在Loglet上是幂等的，一个clieng重试seal操作or多个client并发seal一个chain都是可以的。一个seal操作完成之后，client可以通过checkTail接口获取目前的tail。之后，client向MetaStore请求写入一个新版本的chain，如果之前的版本为Ci，这里就只会接受Ci+1版本的chain写入。这里必须保证多个client并发操作的时候，只有一个client能够操作成功。最好就是从MetaStore获取最新的chain信息，在一些情况下这个操作是可以省略的。Seal操作过程中，一个可能出现的情况是一个client在seal一个chain之后却没有添加新的chain。这种情况下，一个client遇到之后在等待一个超时时间之后，会对reconfiguration发起一个rolls forward操作。即自己来完成后面的操作。
Seal操作还有一些cases需要处理。比如一个新new chain重新映射一些没有写入的unwritten virtual address到另外一个Loglet的时候，这种情况下old chain得去sealed。另外的一些情况是不需要seal操作。这些情况出现在reconfiguration操作没有改变在虚拟地址空间的位置的时候，一般出现在一个sealed的Loglet所在的server故障了，或者是copy、 remap一个sealed segment到另外的一个Loglet的时候。这种情况下不需要seal old chain的操作。另外的truncation操作也不需要seal old chain的操作。

Loglet方面，这里对其的要求要少一些，对于append请求没有高可用的要求。对于seal请求，Loglet要求其highly available，以支持后面的append操作都能知道前面的seal操作。VirtualLog依赖于Loglet的这个seal的能力。另外checkTail的操作返回目前的tail信息，(tailpos,sealbit)。为了降低对Loglet的要求，这里不需要这个tail检查是原子的。也就是为tailpos和获取sealbit信息直接可以有其它的操作。checkTail操作实际上是checkTail和checkSeal两个调用组合到一起。这样带来另外一个效果是，即使返回结果里面的sealbit是true，获取的tailpos后面也可能是变化了的。另外这里对Loglet在position上面的连续性也是没有要求的，也就是可以存在空洞。

0x01 Delos

Delos在Facebook中是作为类似于Google的Chubby、开源的ZooKeeper一样的角色。其基本架构如下图所示，不同的结点之间通过VirtualLog来进行状态的复制，而本地会使用一个RocksDB来维护本地的一个数据副本。MetaStore复制保存全局的元数据信息，Loglet层面支持多种类似的实现，

在VritualLog的层面，按照上面的架构设计，主要是client library和MetaStore两个部分，其中Delos的MetaStore使用一个机遇Paxos的embedded MetaStore。这里的实现使用了一个很朴素的Paxos的实现，Paper中的描述是基本按照Paxos的Paper来实现，是一种canonical single-slot Paxos。这里朴素的Paxos对于MetaStore来说就已经足够了，不用Multi-Paxos or 其它的Paxos变体来实现统一的功能。
Loglet可以支持Native的实现，or ZK、LogDevice的实现等。对于其中NativeLoglet的实现，可以支持converged or disaggregated的形式。在converged的模式下面，每个Delos Server会运行一个NativeLoglet client 和一个 NativeLoglet server (or LogServer)，另外还会有一个sequencer组件。在多数的LogServers存活的情况下，seal和checkTail操作可用。对于append操作，需要sequencer目前的状态正常。每个LogServer使用一个本地的on-disk log，另外会使用一个seal bit来保存seal信息。Entry在log中保存是严格按照顺序保存的，但是其中可以存在空洞。也就是说一台LogServer上，并不一定包含了所有的entry。

另外，实现中实现locally committed表示在某台的LogServer上面，一个command已经写入并持久化到磁盘上面了。Local tail表示local log最后的没有数据写入的位置。一个command变成globally committed需要在一个多数的LogServer上面被locally committed之外，还要求在其之前的command被globally committed。所以这里多globally committed也是有顺序要求的。从NativeLoglet的角度来看，它是不会存在空洞的。Global tail则指的是全局的第一个globally uncommitted log的位置。另外关于tail，每个组件知道的可能有些不同，

  Each component (i.e., LogServers, clients, and the sequencer) maintains a knownTail variable: the global tail it currently knows about, which can trail the actual global tail. Components piggyback knownTail on the messages they exchange, updating their local value if they see a higher one.

在NativeLoglet的实现中，基本的操作：

append，append操作Delos会先向sequencer发送一个请求。这个sequencer给每个请求赋予一个position，然后在转发这个请求到所有的LogServer。发送请求出现之后，如果收到了超过半数的LogServer的成功恢复，可以根据这些信息来更新globally committed 等的信息，并回复client。Sequencer接受到回复中，可能是其中的异常信息。如果收到了超过半数结点的sealed的回复，直接向client返回错误信息。其它的错误的情况下，sequenceer可以选择重试操作。这里的一个特点是重试的操作是幂等的，因为同样的command写入同样的position多次得到同样的结果。
对于一个LogServer来说，其可以local commits一个command，要满足两个条件之一：1. 这个postion前面的command都已经local committed or 2. 前面的command已经globally committed了。
seal，seal可以有任意一个client发起。一个seal命令被成功执行之后，超过半数的LogSevrer对应的sealbit被设置。后面的append请求会被直接拒绝。这里的一个特点值，LogServers执行完这个seal命令之后，不同的LogServers之前的tail不一定相同。
checkTail，checkTail操作返回current global tail。client发送的这个请求会发送到所有的的LogServers，在超过半数的结点回复的时候，根据下面的状态机来进行处理。对于不同的返回情况：如果返回的情况是all-sealed，则这里会尝试repair哪些没有复制到超过少数结点的commands。这里将最大的tail记为X-max，repair到这个位置之后在向client返回这个X-max，
```
Note that repair is safe: the single sequencer ensures that there can never be different entries for the same position on different LogServers. This repair activity can result in the ‘zombie’ appends, where appends on a sealed Loglet are not acknowledged but can complete later due to repairs.
```
如果返回的是some-sealed的情况，这种情况下会再发出seal请求，然后再执行checkTail操作；如果是none-sealed的情况，这里选择X-max，然后等待knownTail达到这个position。如果在这个等待的过程中发现有结点sealed的情况，需要转移到前面两个cases的处理逻辑。

另外的还有一个操作就是readNext。一般类似的系统中，空洞的处理都是比较目的的。比如一个可能是处理的一个问题就是那些已经被复制到没有超过半数结点的command，重试的过程中又超时了这些操作。对于那些已经复制到半数已经结点都是在一个LogServer可能是空洞的情况，前面通过checkTail操作的repaire逻辑处理了。没有复制到半数以上的情况，根据paper中的描述，应该是在重试超过还没有复制到半数以上的情况，应该就是切换一个Loglet来实现，seal之前的部分，从而让这部分的数据被舍弃。Delos的readNext可以基于checkTail的信息，去读取一个已经存在的log，这种情况是比较简单的。从前面的描述可以看得出来，NativeLoglet不是高可用的，比如sequencer故障的时候，append操作就会变的不可用。但是seal操作确实高可用的，简单地通过设置一个quorum的seal bits来实现。另外为了提高性能，Delos使用了StripedLoglet，通过类似RAID的方式将写入打散到多台服务器上面。

0x02 评估

这里的具体信息可以参看[1].

参考

Virtual Consensus in Delos, OSDI ‘20.