深入解析cassandra 轻量级事务原理-阿里云开发者社区

开发者社区> 陈江@阿里> 正文

深入解析cassandra 轻量级事务原理

简介: how to use cassandra是一个无主架构,多个node可以并行写,但并发场景下对于先读后写的操作,数据会有正确性问题。从cassandra2 开始提供轻量级事务支持,用于cas更新。使用示例: cqlsh> UPDATE cycling.cyclist_name SET firstname = ‘Roxane’ WHERE id = 4647f6d3-7bd2-4085-8d6c-1229351b5498 IF firstname = ‘Roxxane’; 这其实是一个标准的compare and swap 示例。
+关注继续查看

how to use

cassandra是一个无主架构,多个node可以并行写,但并发场景下对于先读后写的操作,数据会有正确性问题。从cassandra2 开始提供轻量级事务支持,用于cas更新。使用示例:

cqlsh> UPDATE cycling.cyclist_name
  SET firstname = ‘Roxane’
  WHERE id = 4647f6d3-7bd2-4085-8d6c-1229351b5498
  IF firstname = ‘Roxxane’;

这其实是一个标准的compare and swap 示例。接下来我们深入看看cassandra是如何实现的,其实我们可以发现,其实它既没有事务,也不轻量级。

理论基础

cassandra轻量级事务是通过basic-paxos协议实现的,提供线性化一致性保证,具体的理论基础可以参考paxos made simple。建议读者先深入理解该论文。
论文讲述得出一个值,主要有两个阶段prepair+accept,大体流程见下图:
image

Cassandra LightWeight Transaction paxos实现在原来的二阶段perpair, propose/accept上增加了commit阶段,论文中对于如何 Learning a Chosen Value的描述,工程化实现不太靠谱,常见的做法如下:

一个提案是否被chosen,acceptor是不知道的,只有proposer知道是否满足多数派,如果满足了,增加commit阶段,在该阶段,把已经chosen的提案提告知learner,learner更新自身状态机。

cassandra 实现

工程实现跟理论还是有些gap的,basic paxos最大的问题是只是用来表决出一个值,但cassandra cas需要持续写入多轮(论文中instance)值,cassandra是在prepare阶段,发现上一轮已经正常commit了,即可开始下一轮,提议新的值。
cassandra使用basic paxos本质上为所有的cas请求申请槽位(slot),保证所有请求线性一致性,不会出现replica A执行了op1->op2,而replica B执行了op2->op1这种不一致的结果。

变量介绍

  • ballot: 提案号,proposer保证线性单调增长,在c*里面使用时间戳表示。
    每个node(acceptor)都有如下三个本地变量:
  • in_progress_ballot: prepair 阶段proposer提案号,acceptor 发现只要比自己本地的大,会promise然后更新该本地变量,简称为promised ballot,代码中使用in_progress_ballot保存
  • proposal_ballot: propose阶段,proposer提案号,如果比acceptor已经promise的ballot(上述in_progress_ballot)大的话,acceptor会accept该提案,并把提案中的value持久化。
  • most_recent_commit_at: proposer提案被多数派acceptor接受后,该value被chosen,proposer向learner发送commit消息,commit消息无论如何都会被接受,持久化到磁盘上,most_recent_commit_at是这个决议commit时间。有时简称为commit ballot

实现流程

image

共四个阶段

  1. Prepare/Promise
  2. 产生一个ballot,向replica 发送prepare请求,replica答应不会接受旧的ballot更新,并且告知最后accept 提案及最近commit提案。
  • 如果最后accept提案比最近commit提案新,说明该accept提案还没有走完整个流程,也许后端节点故障导致的。coordinate重新发起propose+commit请求,跳至步骤3,4,结束上轮未完提案后,可开始本轮自己的新提案
  • 如果最近commit提案都比accept提案新, 说明没有还处于流程中的提案,可直接开始本轮自己的新提案。
  1. Read/Results
  • 从replica读取数据,一致性级别为Quorum或者Local_Quorum
  • 读取完判断是否满足condition条件,将上述cql更新变成mutation, 作为提案的值,进入下面的propose/accept阶段。
  1. Propose/Accept
  • 向所有replica发送propose 提案,proposal_ballot必须比replica本地in_progress_ballot高,高的话,给cordinate回复
  1. ack,并持久化在system.paxos表,否则说明replica本地in_progress_ballot更高,代表其他cordinate发送了更新的prepare提案,给当前cordinate回复reject ack。
  2. Commit/Acknowledge
    如果多数派replica接受了这个提案,我们进入commit,像learner(cassandra中的replica)发起commit请求
  • cordinate向所有replica发送一条commit消息,消息包含ballot&value
  • 因为前面2步的关系,这一定是最高的可见的commit ballot,后续新的paxos阶段promise响应也会回复此新值。
    commit阶段首先相应的表(columnFamily)会apply 这条mutation,然后做清理, 会将proposal_ballot,及proposal value置空,标识本轮paxos正常结束。

详细代码请阅读StorageProxy.cas()

LightWeight Transaction 问题

轻量级事务是比较费的,由上面的流程可以看出,正常流程需要4次 RTT,如果发生“活锁”冲突,多个cordinator同时改同一partitionKey,propose 提案会不断被reject,c* 的解决办法是随机睡眠一段时间重试,但带来的问题是线程并发度越高,竞争越激烈,写失败概率越大,分位延时越大。下图99分位写延时能到200ms以上,社区也是不太建议大面积广泛使用cas。
image

摘自:https://www.slideshare.net/DataStax/light-weight-transactions-under-stress-christopher-batey-the-last-pickle-cassandra-summit-2016

但作为数据库,read-before-write是业务系统非常常见的需求,cassandra只能原子写,给我们使用带来很多不便。对于cas性能短板,那么如何改进呢?业界常见的有这么些做法

  • leader模式:如raft,multi-paxos,先选出唯一主,不会有提案的contention,每个写请求都是phase2 accept请求,commit可以异步,这样大大降低了4轮的rpc,可缩减到一跳rpc
  • leaderless模式,改进的paxos,如epaxos,无主跟cassandra相性更兼容,社区后续改进思路就是讲basic-paxos实现改为epaxos,下面我们将花些时间了解一下epaxos

社区改进方向及进展

CASSANDRA-6246, 社区打算使用epaxos做cas优化,将在4.x合入,但该ISSUE已经open了数年,预期进展不会太过乐观,读者了解epaxos原理后,可自行实现改进。
epaxos论文:Egalitarian Paxos

Epaxos介绍

EPaxos用到的几个概念

在描述前,先描述几个概念。

在EPaxos中,每一个command γ都附带attribute,其中包括deps和seq。deps记录了跟γ冲突的command的instance id,γ依赖这些instance id对应的command。deps中维护的依赖关系就是定序用的关系,γ要排在deps中 的command后面。seq是一个序列号,用来在execution阶段打破循环依赖。

接收client请求的副本称之为这个command γ的command leader,记作Lγ。每个副本都会持久化记录到cmds中,通过Q.i这种instance id来索引并读写。

协议分成两个部分,首先是正常处理客户端请求的处理过程,这个过程包括三个阶段:(1) Phase1 Establish ordering constraints (2) Paxos-Accept Phase (3) Commit Phase。其中一个命令可能走Phase1 + Paxos-Accept Phase + Commit Phase,或者Phase 1 + Commit Phase,前者称之为slow path,后者称之为fast path。

需要提前指明的是,优化EPaxos采用的是thrifty模式,fast quorum是 F'=F+⌊(F+1)/2⌋,其中F为系统容忍的少数派,command leader向 F' 个副本发送pre-accept请求,而不是向 2F+1 个副本发送请求等待 F'个回应。

协议详细介绍

image

恢复阶段Explicit Prepare

副本Q怀疑L失效,尝试去恢复L.i这个instance。

  • 递增ballot number:设Q知道的最大proposal id是epoch.b.Q,则使用新的proposal id epoch.(b+1).Q
  • 向所有副本(包括自己)发送Prepare(epoch.(b+1).Q),等待至少多数派的回应。
  • 假设所有回应中最大ballot number的是ballotmax,定义R是所有回应中ballot number等于ballotmax的响应的集合。
  • 如果R没有关于这个instance id的任何信息,那么推出恢复阶段,副本Q对L.i实例尝试去commit no-op。
  • 如果R中包含了至少一条(γ,seqγ,depsγ,committed),则对L.i实例(γ,seqγ,depsγ)执行Commit Phase。
  • 如果R中包含了至少一条(γ,seqγ,depsγ,accept),则对L.i实例(γ,seqγ,depsγ)执行Paxos-Accept Phase。
  • 如果至少(F+1)/2个副本回应了pre-accept,并且它们回应的seqγ,depsγ都与L.i的epoch.0.b那轮PreAccept请求中记录相同,那么就进入TryPreAccept阶段,否则就回到slow path重新来一遍commit。

TryPreAccept阶段

副本Q发送TryPreAccept(L.i,γ,depsγ,seqγ)给中未回应过pre-accept response的副本。

  • 副本R收到TryPreAccept(L.i,γ,depsγ,seqγ)之后,如果R现在记录了command δ,同时满足如下三个条件:

    • γ~δ
    • γ∉depsδ
    • δ∉depsγ 或者 δ∈depsγandseqδ≤seqγ
      就回应NACK,并带上冲突command的一些信息(包括δ的instance id、command leader、instance的状态如pre-accepted/accepted/committed),否则就回应ACK。
  • 副本Q在收到TryPreAccept的响应之后,顺序进行如下的条件判断:
  • 如果pre-accepted的副本数目已经大于等于F+1,则Q退出恢复过程,开始对L.i实例γ,depsγ,seqγ 执行Paxos-Accept阶段。
  • 如果某个TryPreAccept NACK中反馈了存在一个已经committed的冲突command,则退出恢复阶段,从头开始slow path来在L.i实例上重新尝试提交γ。
  • 如果某个TryPreAccept NACK中反馈了一个实例δ,其中δ∉depsγ并且Lγ∈γ,则退出恢复阶段,从头开始slow path来在L.i实例上重新尝试提交γ。
  • 如果存在command γ0,Q是先尝试恢复γ0,但因为发现可能需要先恢复跟γ0冲突的γ。在这种情况下,如果发现γ0的command leader是γ的fast quorum中的一个,那么就退出γ的恢复,从头开始slow path来重新提交γ。
  • 如果前面的条件都不满足,Q就推迟defer γ的恢复,先恢复与γ冲突的某个command。

## 优点

  • leaderless,负载更均衡,对于raft,multi-paxos存在leader的bottleneck,epaxos不存在这个问题
    无主模式还有一个非常大的优点,延时更稳定,集中式主模式往往因为主宕机,从需要抢主,重新提供服务,导致延时陡增,像epaxos,每轮消息任何副本都可以当主,挂了一台无所谓,延时稳定,更适合在线服务。
  • 延时优化,无冲突情况下,能优化当前cas实现 4轮rpc至2轮rpc,preAcept+commit,commit还可以异步发送,不同步等ack。
    就算较之于论文basic-paxos(3轮rpc)也是路径较优,当然略逊于raft/multi-paxos,毕竟一轮rpc。
  • 缺点:epaxos比paxos复杂多了,不过好在于作者提供了go实现的原型,见代码库
    https://github.com/efficient/epaxos

    • 延时肯定是比multi-paxos强主模式差的

性能

参考论文第12页,需要指出的是epaxos延时跟multi-paxos对比,作者尽挑对自己有利的说,需要明确指出同机房下epaxos延时比paxos差的,比如在CA地域。

参考

paxos made simple
Egalitarian Paxos
EPaxos协议解读

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
Cassandra源码解析系列启动模块
Cassandra源码解析之初始化
1033 0
《Kafka Stream》调研:一种轻量级流计算模式
流计算,已经有Storm、Spark,Samza,包括最近新起的Flink,Kafka为什么再自己做一套流计算呢?Kafka Stream 与这些框架比有什么优势?Samza、Consumer Group已经包装了Kafka轻量级的消费功能,难道不够吗? 花了一些时间阅读[docs](http
23844 0
蚂蚁金服分布式事务实践解析 | SOFAChannel#12 直播整理
本文根据 SOFAChannel#12 直播分享整理,主题:蚂蚁金服分布式事务实践解析,也就是分布式事务 Seata 在蚂蚁金服内部的实践。
634 0
SAS进阶《深入解析SAS》之SAS数据挖掘的一般流程
SAS进阶《深入解析SAS》之SAS数据挖掘的一般流程 1. 所谓数据挖掘,是指通过对大量的数据进行选择、探索与建模,来揭示包含在数据中以前不为人所知的模式或规律,从而为商业活动或科学研究提供帮助和服务。 2. 数据挖掘重要的两个类别:有监督分析(SupervisedAnalysis),无监督分析(UnsupervisedAnalysis)。 有监督分析属于目标
1072 0
Netflix开源面向稀疏数据优化的轻量级神经网络库Vectorflow
在Netflix公司,我们的机器学习科学家在多个不同的领域处理着各种各样的问题:从根据你的爱好来定制电视和推荐电影,到优化编码算法。我们有一小部分问题涉及到处理极其稀疏的数据;手头问题的总维度数很容易就能达到数千万个特征,即使每次要看的可能只是少数的非零项。
4172 0
单颗GPU计算能力太多、太贵?阿里云发布云上首个轻量级GPU实例
当地时间3月18日,在硅谷举办的2019年NVIDIA GPU技术大会(GTC)上,阿里云发布了国内首个公共云上的轻量级GPU异构计算产品——VGN5i实例,该实例打破了传统直通模式的局限,可以提供比单颗物理GPU更细粒度的服务,从而让客户以更低成本、更高弹性开展业务。
2704 0
+关注
陈江@阿里
从业于BAT等公有云部门,分布式存储领域专家
21
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载