seadt：金融级分布式事务解决方案（三）—— SAGA设计与实现

点击关注公众号👆，探索更多Shopee技术实践

摘要

seadt 是 Shopee Financial Products 团队使用 Golang，针对真实的业务场景提供的分布式事务解决方案。

上一篇文章TCC应用与实现介绍了seadt TCC的应用和具体实现，在seadt TCC的基础上，本章继续介绍seadt-SAGA的设计与实现。

seadt在TCC设计之初已经考虑好SAGA的扩展，SAGA事务设计在底层框架、状态机等均与TCC保持一致，仅在调用流程中有SAGA独特之处。

1. SAGA介绍

SAGA概念来源于一篇数据库论文Sagas。SAGA事务是由多个短时事务组成的长时事务。在分布式事务场景下，我们可以把SAGA分布式事务看作是由多个本地事务组成的事务，每个本地事务都有一个与之对应的补偿事务。SAGA事务执行流程如下：

图片1 SAGA事务

1.1 SAGA-应用场景

分布式事务处理有多种模型，大家熟知的有TCC、SAGA、AT等。前两篇文件已经介绍了seadt中TCC的设计与实现，那么TCC与SAGA除了接口不同外，还有下面差异：

TCC主要适用于短事务，例如支付转账业务，支付场景的特点是一致性要求高（业务上的隔离性）、短流程、并发高。

SAGA则更适用于长事务，例如现金贷业务，现金贷的申贷流程涉及额度扣减，优惠券使用，购买保险，进行放款等多个环节。任意一个环节失败，都需要对前面执行过的环节进行冲正处理。可以看到现金贷业务申贷场景的特点就是流程多，流程长，还需要调用其他的服务（购买保险，进行放款），且需要保证数据最终一致。

这个场景下SAGA事务就是一个比较合适的解决方案，可以将申贷流程的多个环节组合成一个SAGA事务，由SAGA处理每个环节的正向和反向流程，通过使用SAGA来保证数据的最终一致性。业务只需要提供正向和反向接口，不需要关心何时调用接口，降低业务代码复杂度。实际上SAGA较低的接入成本，对数据最终一致性的保证，已经让SAGA成为目前业界比较认可的长事务解决方案。

1.2 SAGA-实现模式

SAGA事务的实现有两种模式，编排模式和协同模式。下面用贷款申请场景举例说明两个模式的区别：贷款申请流程中，需要进行额度扣减和优惠券使用，并且两个操作组成一个SAGA事务。

1.2.1 编排模式

编排模式是指，业务将SAGA事务状态机以DSL的方式提交到TC中进行维护，由TC编排管理整个流程的流转，由TC进行事务的正向推进，反向回滚和异常处理。SAGA编排模式贷款申请流程如下：

例如上述例子中，编排模式处理过程：

1. 业务启动SAGA
2. TM向TC发起请求，启动SAGA事务
3. TC根据该事务DSL，调用Quota，执行分支事务A额度扣减
4. 步骤3失败，则TC根据事务DSL进行反向补偿，调用Quota，执行分支事务A的回滚事务，恢复额度，SAGA事务结束
5. 步骤3成功，则TC根据事务DSL进行正向推进，调用Promotion，执行分支事务B进行使用优惠券
6. 步骤5失败，则TC根据事务DSL进行反向补偿，调用Promotion，执行分支事务B的回滚事务，退回优惠券，然后执行步骤4
7. 步骤5成功，SAGA事务结束

下面为编排模式使用的伪代码：

import seadtfunc BizFunc() {    sagaTxId := "BizTrans"    seadt.StartSAGATx(ctx, seadt_name, req_id)}

// DSL伪代码{    "seadt_name":"BizTrans",    "tx_seq":[        {            "sub_tx_id": "UseQuota",            "commit_method": "/Module_Name/UseQuota",            "callback_method": "/Module_Name/UnUseQuota",            "pre_step":"Start",            "next_step":"UseCoupon"        },        {            "sub_tx_id": "UseCoupon",            "commit_method": "/Module_Name/UseCoupon",            "callback_method": "/Module_Name/UnUseCoupon",            "pre_step":"UseQuota",            "next_step":"End"        }    ]}

编排模式的优点：

• 可视化：可以用可视化工具来定义流程和生成流程的DSL，标准化，可读性高
• 中心化管理/统一管理：可以提供管理面板，对事务进行统一管理，例如批量查询事务状态，批量重试事务等功能
• 流程灵活编排：可以根据业务需求，灵活进行SAGA事务的“向前重试”或“向后补偿”
• 接口原子化：参与者提供原子化接口，实现简单

编排模式的缺点：

• 易用性差：业务接入前，需要先了解状态机原理，了解对应的DSL，学习成本比较高
• 接入成本高：如果是现有业务要接入，业务需要将原有的业务代码转换为DSL，对业务入侵性高
• 实现难度大：实现状态机引擎的研发成本比较高
• 成本高：实现的人力投入大

术语说明： DSL：领域特定语言(domain-specific language)，是仅为某个适用的领域而设计的语言，HTML就是一种用于建立网页的DSL

1.2.2 协同模式

协同模式是指，将SAGA事务编排的功能以本地SDK的方式集成在事务发起者TM中。SAGA各个分支事务的流转关系在事务发起者TM的业务代码中进行编排，SAGA事务的正向推进在事务发起者侧完成，SAGA事务的反向回滚在事务协调者TC侧推动完成，业务无需关注事务的反向回滚。SAGA协同模式流程如下：

图片3 协同模式

例如上述例子中，协同模式处理过程：

1. 事务发起者开启SAGA事务
2. 事务发起者调用Quota，执行分支事务A额度扣减
3. 步骤2失败，抛出异常，TM上报事务结果到TC，TC进行事务反向回滚，调用Quota，执行分支事务A的回滚事务，恢复额度，SAGA事务结束
4. 步骤2成功，事务发起者调用Promotion，执行分支事务B使用优惠券
5. 步骤4失败，抛出异常，TM上报事务结果到TC，TC进行事务反向回滚，调用Quota和Promotion，恢复额度和退回优惠券，SAGA事务结束
6. 步骤4成功，SAGA事务结束

下面为协同模式使用的伪代码：

func BizTrans(ctx context.Context, userId, loanId, couponId，Principal string) {  saga.WithGlobalTransaction(ctx, func(ctx context.Context) {         // 使用额度     biz.RefAccount().UseQuota(ctx, userId, loanId, Principal)     // 使用优惠券     biz.RefPromotion().UseCoupon(ctx, userId, couponId)
     // local db op     dao.ClFileAuthDAO().Insert(ctx, record)
      }, &seadt_model.Option{         TimeOutSecond:   10,         TransactionName: "loan_apply",  })

协同模式的优点： 易接入：业务作为事务发起者，在代码中直接编排事务流程实现难度低：协同模式需要拦截事务参与者的请求，进行分支事务管理。这部分的功能seadt TCC已经实现，可以直接复用研发成本低：在TCC基础上开发，10人/天以内

协同模式的缺点：

• 无法统一管理：框架无法提供基于业务状态的业务流程管理能力，没法集中查看事务编排
• 业务耦合：协同模式需要在业务代码中直接编排事务流程，如果要修改事务流程，就必须修改业务代码
• 不支持向前重试：无法通过事务框架自动完成向前重试，需要业务自行进行向前重试动作
• 较难实现有序回滚：TC无法精确感知分支事务的顺序

实现：全局-TC / SDK-TC

• SAGA协同模式两种不同的实现。
• SDK-TC：TC与TM、RM以SDK的形式提供给业务引用。
• 全局-TC：TC作为单独服务部署。

推动事务反向回滚的协调者可以是本地SDK，也可以是全局TC。

可以看到全局TC模式的优点是比较明显的，缺点则是使用全局TC会带来的单点风险，因此使用全局TC模式的前提就是全局TC服务是高性能和高可用的。seadt TC这部分的高可用设计会在后续文章进行详细介绍。

1.3 选型

在1.2节介绍SAGA的编排模式和协同模式时，我们也对两种模式做了简单总结。

那为什么seadt-SAGA选择优先支持协同模式？

seadt的初衷之一是以小步快跑的方式为我们的业务团队提供分布式事务解决方案。基于这个初衷，我们的选型思路主要考虑两个方面：业务接入成本和研发成本。

考虑业务接入成本是好理解的。那为什么还要考虑研发成本呢？

因为随着业务发展，目前团队在一些业务场景已经产生了SAGA事务的需求，我们希望在可控时间内为团队提供稳定可靠的SAGA事务功能。

基于上述对比，seadt最终选择了先实现协同模式，采用全局TC方式。

2. seadt-SAGA实现

2.1 接口设计

目前seadt-SAGA的接口设计如下

图片4 seadt-SAGA接口设计

2.2 交互流程

我们仍然以上面的业务场景来介绍接入seadt-SAGA后各个系统之间的交互流程

图片5 seadt-SAGA交互流程

• 发起者 TM 向 TC 注册全局事务
• 发起者进行额度扣减和使用优惠券
• 参与者 RM 注册分支事务
• 参与者执行额度扣减或使用优惠券的本地事务
• 发起者 RM 执行本地业务处理
• 发起者 TM 提交全局事务
• 如果全局事务为Confirm，TC 记录全局事务完成，全局事务结束；
• 如果全局事务为Cancel，TC执行Cancel，调用参与者 RM 执行Unuse方法，进行额度增加/优惠券退回操作

2.3 业务接入

事务发起者接入，同本文1.2.2接入一致。接下来是业务参与者的接入：

图片6 参与者接入示例

seadt-SAGA的接口设计和seadt-TCC基本相同，seadt-SDK 为参与者提供一套 SAGA 的二个接口，但是只替参与者提供反向的Compensate API 接口 pb，并不提供正向的Forward 接口；正向的Forward接口需要业务参与者自行提供 pb 伪代码如下：

// saga_manager.govar quotaUseProxySagaRef *saga.SagaResourceServiceProxy
func init() {  quotaUseProxySagaRef = saga.RegisterSagaResourceService(new(QuotaUseSagaImpl))}
func GetQuotaUseSagaRef() *saga.SagaResourceServiceProxy {  return quotaUseProxySagaRef}

// saga_resource_impl.gotype QuotaUseSagaImpl struct {}
func (t *QuotaUseSagaImpl) Forward(ctx context.Context, payload interface{}) (bool, error) {  biz.UseQuota(ctx, payload)   return true,nil}
func (t *QuotaUseSagaImpl) Compensate(ctx context.Context, payload interface{}) bool {  biz.UnUseQuota(ctx, payload)  return true}

// service.gofunc UseQuota(ctx context.Context, req *api.UseQuotaReq, resp *api.UseQuotaResp) error {  db.WithTransaction(ctx, func(ctx context.Context) {     resp, err := seadt.GetQuotaUseSagaRef().Forward(ctx, req)     if err != nil {        panic(err)     }  })  return nil}

2.4 状态机

与TCC相同，SAGA分布式事务中也有两个核心的状态机，主事务状态机、分支事务状态机。

图片7 全局事务状态机

图片8 分支事务状态机

SAGA的主事务状态机和TCC这样的两阶段提交事务不一样，SAGA事务的事务发起者一旦提交全局事务状态为Commit，即表示全局事务结束，全局事务的状态会直接从Commit流转为Committed完成。

SAGA的分支事务状态机和TCC的区别就更大了，SAGA分支事务只有三种状态: Prepared，Confirmed，Canceled，并且Confirmed状态是可以流转到Canceled状态。

TM 与 RM 状态矩阵（行代表主事务，列代表分支事务）：

RM 与 RM 状态矩阵：

从上面两个状态矩阵可以得知，SAGA事务确实是只保证数据最终一致性，不保证数据的隔离性，即使主事务已经是Rollbacking状态，分支事务也可以是Confirmed或者Canceled，这些状态都是用户可见的，SAGA只保证这些分支事务最终是Canceled。

1. 当主事务是Rollbacking时，分支事务可以是任何状态
2. 分支事务相互独立，分支事务之间的状态也是任意的，没有约束

SAGA事务作为主流的长事务解决方案，适用的场景非常多，适合大多数业务系统。

我们考虑团队自身情况，选择自研SAGA的协同模式-全局TC方式，最终会朝着编排模式发展。

读者朋友如果有SAGA需求，可以根据本文介绍的SAGA几种模式，选择适合自身业务的模式。seadt团队会继续分享自研过程中遇到的实际问题与对应解决方案。

附录：重点剖析-事务回滚

SAGA事务要求，当分支事务是有序执行时，分支事务的回滚也必须是有序执行的，回滚执行的顺序和正向操作是相反。对应的，当某些分支事务之间是并行执行的，那么这些分支事务的回滚也可以是并行执行的。

Backward crash recovery for parallel sagas is similar to that for sequential sagas. Within each process of the parallel saga, transactions are compensated for (or undone) in reverse order just as with sequential sagas. In addition all compensations in a child process must occur before any compensations for transactions in the parent that were executed before the child was created (forked). (Note that only transaction execution order within a process and fork and join information constrain the order of compensation. If T1 and T2 have executed in parallel processes and T2 has read data written by T1, compensating for T1 does not force us to compensate for T2 first.) —— 引自:  Hector Garcaa-Molrna, Kenneth Salem. “SAGAS ”

SAGA事务回滚实现的难点在于：

• 如何判断事务之间是有序的，还是并行的？
• 如果是有序的，事务之间的顺序是什么？

为了解决上述的两个问题，我们需要引入一个概念Happened-before：

In computer science, the happened-before relation (denoted: ->) is a relation between the result of two events, such that if one event should happen before another event, the result must reflect that, even if those events are in reality executed out of order (usually to optimize program flow). This involves ordering events based on the potential causal relationship of pairs of events in a concurrent system, especially asynchronous distributed systems. It was formulated by Leslie Lamport.

The happened-before relation is formally defined as the least strict partial order on events such that:

• If events a and b occur on the same process, a -> b if the occurrence of event a preceded the occurrence of event b.
• If event a is the sending of a message and event b is the reception of the message sent in event a, a -> b.
• If two events happen in different isolated processes (that do not exchange messages directly or indirectly via third-party processes), then the two processes are said to be concurrent, that is neither a -> b nor b -> a is true.

—— 引自:  “Happened-before wiki ”

从Happened-before关系定义可以知道，我们可以通过构建事务之间的Happened-before关系感知到事务之间是并行的，还是有序的；若有序，顺序是什么。

同时我们也知道了Happened-before关系是一种严格偏序关系，然后严格偏序与有向无环图有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。

因此实现SAGA事务回滚，就是构建一个满足Happened-before关系的事务集，或者生成一个事务的有向无环图，两个方案本质是一个方案的两种实现

1. 编排模式-回滚

编排模式下，事务回滚是易于实现的。因为TC可以通过解析业务提交的DSL，获得SAGA事务的状态机，进而获得一个满足Happened-before关系的事务集，基于这个事务集就可以实现事务回滚

2. 协同模式-回滚

协同模式下，事务回滚的实现会比编排模式困难。因为协同模式下，SAGA事务的正向推进在事务发起者侧完成，SAGA事务的反向回滚在事务协调者侧推动完成。作为反向回滚的推动者TC无法直接感知事务的Happened-before关系，需要通过其他方式感知事务的Happened-before关系

对此，我们有两种获得事务之间Happened-before关系的方案：向量时钟、事务序列号。

方案一：向量时钟

标准的向量时钟算法是可以准确刻画事件顺序的，即可以根据向量时钟，得到事务的严格偏序集，感知事务之间的Happened-before关系，向量时钟算法如下：

对每个节点，定义一个向量VC ，向量的长度是 n ， n 是节点数目。

1. 初始化各个节点 P i 的向量， 全部抹零：V C i = [ 0 , … , 0 ] 
2. 节点 P i 每发生一个事件时， 其向量的第 i 个元素自增：V C i [ i ] + = 1
3. 当节点 P i 发消息给节点 P j 时，需要在消息上附带自己的向量 V C i 
4. 当节点 P j 接收到消息时，对齐对方的时钟，并在自己的时钟上自增：对 [ 0 , n ) 上的任意一个整数 k 执行 V C j [ k ] = M a x ( V C j [ k ] , V C i [ k ] ) ， 接着，对应第2点：V C j [ j ] + = 1

下面我们来看看，如何使用向量时钟算法得到事务的严格偏序集：

先假设事务有1个TM(Trans)，两个RM（Quota和Promotion）

1. 定义Trans为P0，Quota为P1，Promotion为P2
2. TM和所有RM都初始化一个向量VCi = [0,0,0]
3. Trans创建事务，视为一个事件A，Trans的向量更新为[1,0,0]
4. Trans调用Quota，Quota创建分支事务，视为一个事件B，Quota的向量更新为[2,1,0]
5. Trans成功调用Quota后，接着调用Promotion，Promotion创建分支事务，视为事件C，Promotion的向量更新为[4.2,1]

通过向量时钟算法，是可以得到事务的严格偏序集，然后通过将关键事件发生时的向量时钟上报TC，TC侧就可以通过比较事件A，B，C的向量值得到事件之间的Happened-before关系：事件A[1,0,0] < 事件B[2,1,0] < 事件C[4.2,1]  =>  A -> B -> C，进而实现事务回滚。

但标准向量时钟算法有个缺点，只考虑了固定数量的节点，没有考虑节点的动态添加和销毁，而分支事务是动态创建的，因此要使用向量时钟算法获得事务的Happened-before关系，需要对算法进行一些改变。

在初始化各个节点Pi的向量时，为每个节点分配一个全局唯一标识，采用HashMap的方式记录各个节点的时钟值，通过比较相同Key的Value大小得到向量之间的大小关系。

图片11 改良版向量时钟算法示例

这样就可以通过向量时钟获得事务之间的Happened-before关系。

方案二：事务序列号通过分配给每个分支事务一个可比较的事务序列号，来判断分支事务间的顺序，以此保证SAGA事务的有序反向回滚。在下文我们称事务序列号的集合为事务序列，一个SAGA事务对应一个事务序列。

seadt使用的全局TC模式，可以准确的为全局事务里每个分支事务分配一个序号。序列号是TC在注册分支事务时，为分支事务分配的全局事务内唯一的序列号，事务序列号满足以下两个性质：

1. 序列号严格递增
2. 若分支事务A的序列号Seq-a < 分支事务B的序列号Seq-b，分支事务A和B不一定有因果关系；若分支事务A和B有因果关系（A先于B发生），则一定有分支事务A的序列号Seq-a < 分支事务B的序列号Seq-b

上述的事务序列号方案，借助中心节点(全局TC)，构建了事务的全序集合(事务序列)来描述事务顺序，基于构建的事务全序集合可以串行执行事务的反向回滚，可以保证后发生的事务一定比先发生的事务先完成回滚操作，从而实现SAGA事务的有序回滚。

因为事务序列号方案构建的是全序关系（类似于逻辑时钟算法的效果），而Happened-before是严格偏序关系，因此全序关系是无法体现两个事务间的并行关系，如果两个事件并不相关，那么这个全序集合给出的大小关系则没有意义，无法通过比较事务序列号来决定什么事务之间是并行的，也就无法并行回滚这些分支事务，因此只能串行回滚所有分支事务。

对比两个方案，向量时钟方案可以构建出标准的Happened-before关系，可以准确的对事务进行有序回滚和并行回滚。但缺点是向量时钟方案需要每个节点维护一个事务时钟变量，并且在节点交互的过程中不断传播更新这个时钟变量，会带来一定的存储成本和传输成本。同时向量时钟方案也需要对seadt现有接口交互逻辑和seadt-sdk的底层实现都进行较大的改动。

事务序列号方案的优点是实现比较简单，对现有seadt的接口交互逻辑改动较小，seadt-sdk无感知，只需要进行seadt-tc的改造。虽然只能进行有序串行回滚，不能实现并行回滚，但我们考虑到反向回滚流程是业务无感知的异步流程，我们认为目前没必要为了提升异步流程的效率，提高代码的复杂度。事务序列号方案的缺点是可以接受的。

综上所述，我们最后选择了事务序列号方案。

参考文章：

1. saga论文：https://github.com/mltds/sagas-report
2. 偏序关系：https://zh.wikipedia.org/wiki/%E5%81%8F%E5%BA%8F%E5%85%B3%E7%B3%BB
3. 全序关系：https://zh.wikipedia.org/wiki/%E5%85%A8%E5%BA%8F%E5%85%B3%E7%B3%BB
4. Happened-before：https://en.wikipedia.org/wiki/Happened-before
5. 逻辑时钟与向量时钟：https://writings.sh/post/logical-clocks