支付宝转账过程并发交易引起的分布式死锁问题
问题背景
最常见的一种场景： 支付宝账号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操作