TL;DR
Wound-wait 与 wait-die 是 DBMS 中处理死锁的两种常见策略,它们的优缺点为:
- Wait-die 会导致更多 rollback,但 rollback 的代价更低:被 rollback 的事务做过的事情比较少。
- Wound-wait 导致的 rollback 较少,但 rollback 的代价更高:被 rollback 的事务做过的事情比较多。
另外 [1] 中提到:
还有一种方法,no wait,就是请求不到锁就回滚,不去做判断。现在的一般看法是,不等比等好,尤其是应用于分布式事务时。
wait-die 与 wound-wait
在基于锁的事务实现中,当事务 Ti需要获得某个 data item 的锁时,发现这把锁当前正在被事务 Tj持有,我们不能直接让 Ti等待这把锁,否则可能造成死锁。
在一个单机 DBMS,或有全局死锁检测的分布式 DBMS 中,可以通过死锁检测来做决定。但如果无法获得全局状态,我们可以使用 wait-die 或 wound-wait 策略来避免产生死锁。
这里我们有三种选择:
- Ti直接 abort。
- Ti等待 Tj执行完,再获取这把锁。
- 强行终止 Tj的执行,从而让 Ti获取到锁。
Wait-die 是比较 Ti与 Tj的 timestamp,如果 Tsi < Tsj(即 Ti更老),则 Ti等待(wait);否则(Ti更新)Ti直接 abort(die)。
Wound-wait 同样是比较 timestamp,但相反,如果 Tsi < Tsj(即 Ti更老),则强行终止 Tj(wound);否则(Ti更新)Ti等待(wait)。
两种策略都只用 timestamp 来做判断,避免依赖各自的读写集,从而获得更好的性能。但需要系统不同节点产生的 timestamp 是可比较的(TimeStatusOracle、TrueTime、HLC 都可以)。
两者的相同点
- 更老的事务总会有机会执行。
- 被 abort 的事务随后会使用相同的timestamp 重启。最终这些事务会成为系统中最老的事务,从而不再被 abort。
两者的区别
- Wait-die 中被 abort 的新事务是试图获取锁的一方
- Wound-wait 中被 abort 的新事务是持有锁,正在运行的一方。
比较两者的代价
关于 abort 代价:
- 更新的事务通常持有更少的锁,且已经读写过的数据更少。
- 更老的事务通常持有更多的锁,且已经读写过的数据更多。
因此更老的事务的 abort 代价更高。
关于 abort 数量:
- 大多数锁被老事务持有。
- 大多数加锁请求由新事务发起(新事务持有的锁更少,因此加锁请求更多)。
- 因此大多数冲突是新事务试图获取老事务持有的锁。
Wait-die 中新事务试图获取老事务持有的锁会导致自身被 abort;而 wound-wait 中类似情况下则是 wait,因此 wait-die 会导致更多的 abort。
但 wound-wait 中被 abort 的事务必须已经持有了一部分锁,它们通常也已经读写过一些数据了(并非刚开始的事务),这些事务的 abort 代价更大;而 wait-die 中大多数被 abort 的事务可能一点读写都没做过,它们的 abort 代价更小。因此 wait-die 每个 abort 的代价会更小一些。
结论就是很难说哪种策略更优(视具体情况讨论)。