论文阅读:在Paxos/Raft的从节点实现线性一致性读取(slave强一致性读),Linearizable Quorum Reads in Paxos

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

背景

在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。

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

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,496评论 6 501
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,407评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,632评论 0 353
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,180评论 1 292
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,198评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,165评论 1 299
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,052评论 3 418
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,910评论 0 274
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,324评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,542评论 2 332
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,711评论 1 348
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,424评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,017评论 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,668评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,823评论 1 269
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,722评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,611评论 2 353

推荐阅读更多精彩内容

  • 一、分布式系统的挑战 CAP理论的核心思想是任何基于网络的数据共享系统最多只能满足数据一致性(Consistenc...
    常晓csc阅读 349评论 0 1
  • Ceph Monitor作为Ceph服务中的元信息管理角色,肩负着提供高可用的集群配置的维护及提供责任。Ceph选...
    CatKang阅读 3,460评论 0 2
  • 本文由厦门大学计算机系教师林子雨翻译,翻译质量很高,本人只对极少数翻译得不太恰当的地方进行了修改。 【摘要】:Sp...
    Jeffbond阅读 3,931评论 1 42
  • Spanner is Google’s highly available global SQL database ...
    nafoahnaw阅读 837评论 0 1
  • 夜 ——是夜无眠,随风杂想,由此而做此诗。 太白醉了 夜 给了他想象的手杖 从此 就有了嫦娥 千年的期待 东坡醒了...
    故人依旧1993阅读 47评论 0 0