支付宝转账过程并发交易引起的分布式死锁问题

支付宝转账过程并发交易引起的分布式死锁问题

问题背景
最常见的一种场景: 支付宝账号A向账号B转账500元。 由于支付宝有几亿用户,账户的保存采用了分库分表的方案, 账号A和账号B分别被保存在不同的数据库实例中

一般处理方案
支付宝提供了一套柔性事务处理方案—基于二阶段提交理论的TCC方案,这里不再赘述,有兴趣的同志参考 http://www.kuqin.com/shuoit/20151208/349373.html

对于单笔交易,大致流程用伪代码描述为:

try{//锁资源阶段
lock A; A -= 500; //step 1
lock B; B += 500; //step 2
}
confirm{//分布式事务提交阶段
commit A;
commit B;
}
//若confirm中某一步失败or超时,则做下面的动作
cancel{
rollback A;
rollback B;
}

上述过程中,在单笔交易中,是没问题的

问题引申
对支付宝这种高并发的应用, 很可能出现一种场景,A向B转账的500块的时候,B几乎同时向A转账1000块,比如春节的时候大家频繁发红包。所以这个时候,有这样一个过程:

try{//锁资源阶段
lock B; B -= 1000; //step 3
lock A; A += 1000; //step 4
}
confirm{//分布式事务提交阶段
commit A;
commit B;
}
//若confirm中某一步失败or超时,则做下面的动作
cancel{
rollback A;
rollback B;
}

不难看出, 在两笔交易几乎同时执行的时候, 当交易1执行了step1锁住A账号再去锁B账号的时候,交易2可能正执行step3锁住了B账号然后要请求A账号的资源。 这个时候死锁就出现了。

这里写图片描述

结果就是两笔交易都无法正常往下走,只能等待超时直至对方释放资源。最终的结果可能是这两笔交易都失败, 然后再重新发起交易。 对于支付宝这样的应用来说,这几乎是不能容忍的。

好了,问题摆出来了,how to deal with it?

死锁的预防方案
死锁预防 使引起死锁的必要条件不成立
– 资源排序,按资源序列申请
– 将所有并发事务排序,按标识符或者开始时间
– 有死锁危险的时候,事务退出已经占有的资源, 有两种方法:
等待-死亡: 重启较为年轻的事务, 较为年老的事务等待已经持有资源但是较为年轻的事务
受伤-等待: 年轻的等待年老的, 较年轻的重启,而重启事务并不一定是目前正在申请的事务

死锁检测
–检测死锁时循环等待的圈

并发控制的多版本技术
多版本的概念

保存已经更新数据的旧值
维护一个数据项的多个版本
通过读取数据项的较老版本来维护可串行性, 使得系统可以接受在其他技术中被拒绝的一些读操作
写数据项的时, 写入一个新版本,老版本依然保留

数据项X的多个版本

x1, x2, x3...

系统保存的值

Xi的值
Read_TS(Xi): 读时标,成功读取版本Xi的事务的时标,·最大的一个
Write_TS(Xi): 写时标,写入版本Xi的值的事务时标

多版本规则

事务T发起write_item(X), Xi具有X所有版本中的最高的write_TS(Xi).
若write_TS(Xi)<=TS(T) && read_TS(Xi)>TS(T), 撤销并回滚T
若write_TS(Xi)<=TS(T) && read_TS(Xi)<TS(T),则创建X的新版本, 并且令 write_TS(Xi)=read_TS(Xi)=TS(T)

值 read write version
500 T0 T0 v1
800 T2 T2 v2 //事务T2执行write操作

事务T发起一个read_item(X)操作,并且X的版本Xi具有X所有版本中最高的write_TS(Xi), 同时write_TS(Xi)<=TS(T), 则将其Xi返回给事务T, 并将read_TS(Xi)的值设置为TS(T)和当前read_TS(Xi)中较大的一个

值 read write version
500 T1 T0 v1 //事务T1执行read操作,读取在其之前写入的版本,这里返回值是500
800 T2 T2 v2 //事务T2执行write操作

上一篇:[CF1283E] New Year Parties - 贪心


下一篇:概率图:概率、条件独立性、图概念理解