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

实现流程

共四个阶段

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。

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

协议详细介绍

恢复阶段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协议解读