论文阅读:在Paxos/Raft的从节点实现线性一致性读取(sl

2019-12-06  本文已影响0人  招财二师兄

(本文属于原创内容,未经作者许可,不得转载)

背景

在2019年的USENIX顶级会议中,发布了一篇论文:Linearizable Quorum Reads in Paxos,提出一个名为Paxos Quorum Read(PQR,下文称Paxos多数派读)的协议,可以让Raft,Paxos这种分布式系统,在从节点提供线性一致性读。

基于Paxos多数派读,可以让整个分布式系统增加12%的吞吐量以及减少30%的延时,减少Leader的压力。

我们一齐来看看吧。

linearizable reads,线性一致性读

我们先来简单介绍一下linearizable reads。在分布式系统中,线性一致性读为现阶段可实现的最强一致性读,简单定义为:只要写入成功,后续的所有读操作,都会读到最新的数据。

所以linearizable reads不允许出现脏读(stale read),幻读,不可重复读。

业界分布式系统,对读取优化的方案

这章节简单介绍业界分布式系统的读方案,如果你对此很熟悉了,可以直接跳到下一章,直接看论文的思路

本文说的分布式系统,主要是指基于复制状态机(Replicated State Machine)的系统,如基于Zab的ZooKeeper,Raft的ETCD,PacificA的Pegasus,Paxos的PaxosStore等等。

Leader读

这个不需要展开了,在Leader Based的分布式系统,在Leader读取肯定能提供线性一致性,缺点就是Leader压力大,其它Followers资源利用率不高

单个从节点读

如ZooKeeper,可以直接在从节点读,但明确提出不提供线性一致性读。(sync方式不展开讨论)

读修复

典型的就是Cassandra,在读的时候,需要在majority replicas进行读修复,Cassandra是基于Timestamp版本修复的。

LSN

LSN为Logical Sequence Number,逻辑序列。基于LSN的思想是,在写的时候,Leader会返回此次操作的LSN,然后,后续的读就可以带上此LSN进行读,这样,从节点就可以保证返回这个LSN后commit的数据。

其它

有基于timestamp的小强DB(CockroachDB),由于在不同的Server中,timestamp可能不一样,会带来一些问题,小强DB也不提供线性一致性(或者没那么严格的线性一致性)

Paxos Quorum Reads

我们接下来介绍论文的思想:Paxos Quorum Reads,Paxos多数派读。它其实是个2PC的协议,其核心实现思路分为两步:

  1. 多数派读(Quorum-read Phase):客户端会往除了Leader的多数派节点读取数据,每个节点返回两个数据,一个是last accepted value,另外一个是max slot(即Paxos中的instance)。值得注意的是,这个max slot是不管空洞的,即如果一个从节点accept了1,3,5,7,那么就返回7。
  2. Rinse Phase:不知道怎么翻译好,其实就是类似于Long Polling,它主要是需要客户端等待第一阶段中的max slot被从节点commit。流程是,客户端随便选一个从节点,发送Rinse Phase的Request,当从节点对应的slot commit完,并且中间的空洞也commit完,才进行Response。

论文中的图片如下:

1.1 process_mark.jpg

我也做了另一个图讲解,如下图所示:

1.2 detail_mark.jpg

假设分布式系统有5个节点,在多数派读阶段,我们假设client请求的从节点是2,3,4,那么Client将得到max slot是5,在Rinse Phase阶段,client可以去请求任意一个从节点,对应的从节点需要在slot5被commit之后(注意1-4也需要commit),才返回。

其核心思想是,在请求的那一个时间点,我得到了一个value以及max slot5,那么,只要保证max slot5被commit了,我这个value就一定是最新的,而且是已达到多数派commit的,提供了线性一致性读。

Paxos Quorum Reads的优化

从本质上,Paxos多数派读是一个2PC的协议,即最少需要2RTT才能完成。论文中也提出了一些优化的建议,在我看来还是比较容易想到,比较容易理解的。

1. 从节点的max slot与commit slot一致

即读的时候,没有写入请求正在进行。从max slot与某个从节点的commit slot一致,保证了此从节点的返回值,肯定是最新的。所以可以省去Rinse Phase。

2. 类似于KV类型的服务优化

我们明白,max slot与value不是必然存在联系的,如果我们能区分max slot,commit slot以及value的关系,就可以用一次RTT完成操作。

比如KV的系统,如果把存储结构加上slot:

1.3 kv structs_mark.jpg

比如,还是上面的例子,一个client求请Key为KA的Value,而KA是slot 1写入的,则只要Client知道max commit已经超过slot 1,就可以直接返回,则不需要进行Rinse Phase。

这也适用于其它类型的系统,只要能把value与slot关联起来,比如micro-shards,sql之类的(sql要看设计)。

3. Flexible Quorum Optimization

暂时还没有理解,回头再补上。

总结

USENIX的这篇论文:Linearizable Quorum Reads in Paxos,提供了一个Paxos Quorum Read,Paxos多数派读的思路,让分布式系统可以在从节点读的同时,提供了线性一致性读。在此基础上,在设计系统时,就可以trade off Paxos主节点与从节点之间的balance。

它从本质上看是一个2PC的协议,但有优化途径可以减少至1PC。

可以关注我的微信公众号:招财二师兄,下次文章发送时会直接推送给你

上一篇下一篇

猜你喜欢

热点阅读