The Transactional Conflict Problem
The Transactional Conflict Problem
复制标题
交易冲突问题
DOI：
10.1145/3210377.3210406
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Giorgi Nadiradze
中科院分区：
文献类型：
--
作者：
Dan Alistarh;Syed Kamran Haider;Raphael Kübler;Giorgi Nadiradze
在事务系统中，当两个或多个并发事务在一个数据项上发生冲突时，就会出现事务冲突问题。虽然这种冲突的标准解决方案是立即中止事务之一，但一些实际系统考虑将冲突解决延迟一段短时间的替代方案，这可能允许事务之一提交。在事务冲突问题的挑战是选择这个延迟间隔的最佳长度，以便最小化冲突事务的整体运行时间惩罚。在本文中，我们提出了一个家庭的最优在线算法的事务冲突问题。具体来说，我们考虑这个问题的变种，出现在不同的实现的事务系统，即“请求者赢”和“请求者中止”的实现：在前者中，接收者的一致性请求被中止，而在后者中，它是请求者必须中止。这两种策略都是由真实的系统实现的。我们发现，请求者中止的情况下，可以减少到一个经典的滑雪租赁问题的实例，而请求者获胜的情况下，导致这个经典问题的一个新版本，我们得到最佳的确定性和随机算法。此外，我们证明，在一个简化的对抗模型下，我们的算法是不断的竞争与离线最佳的吞吐量。我们通过硬件事务内存（HTM）的硬件模拟经验验证我们的算法结果，表明我们的算法可以导致经典的并发数据结构的非平凡的性能改进。
The transactional conflict problem arises in transactional systems whenever two or more concurrent transactions clash on a data item. While the standard solution to such conflicts is to immediately abort one of the transactions, some practical systems consider the alternative of delaying conflict resolution for a short interval, which may allow one of the transactions to commit. The challenge in the transactional conflict problem is to choose the optimal length of this delay interval so as to minimize the overall running time penalty for the conflicting transactions. In this paper, we propose a family of optimal online algorithms for the transactional conflict problem. Specifically, we consider variants of this problem which arise in different implementations of transactional systems, namely "requestor wins'' and "requestor aborts'' implementations: in the former, the recipient of a coherence request is aborted, whereas in the latter, it is the requestor which has to abort. Both strategies are implemented by real systems. We show that the requestor aborts case can be reduced to a classic instance of the ski rental problem, while the requestor wins case leads to a new version of this classical problem, for which we derive optimal deterministic and randomized algorithms. Moreover, we prove that, under a simplified adversarial model, our algorithms are constant-competitive with the offline optimum in terms of throughput. We validate our algorithmic results empirically through a hardware simulation of hardware transactional memory (HTM), showing that our algorithms can lead to non-trivial performance improvements for classic concurrent data structures.