深入解析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 示例。接下来我们深入看看cassandra是如何实现的,其实我们可以发现,其实它既没有事务,也不轻量级。

理论基础

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

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

实现流程

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

共四个阶段

  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。
深入解析cassandra 轻量级事务原理

摘自: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'个回应。

协议详细介绍

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

恢复阶段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 nodetool常用命令介绍


下一篇:为什么选择Cassandra