Lock-free Contention Adapting Search Trees
Lock-free Contention Adapting Search Trees
复制标题
DOI：
10.1145/3460874
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
Kjell Winblad;Konstantinos Sagonas;B. Jonsson
中科院分区：
文献类型：
--
作者：
Kjell Winblad;Konstantinos Sagonas;B. Jonsson
同时使用范围查询支持的键值存储对于许多应用程序的可扩展性和性能至关重要。这种现有的无锁数据结构使用固定的同步粒度。在具有范围查询支持的并发键值商店中使用固定的同步粒度是有问题的，因为最佳性能同步粒度取决于难以预测的许多因素按范围查询。我们提出了第一个具有范围查询支持的无锁键值商店，该商店可以动态调整其同步粒度。此数据结构称为无锁的争夺搜索树（LFCA树）。 LFCA树自动对其同步粒度进行局部改编，该粒度基于启发式方法，并考虑到范围查询的性能。我们表明，LFCA树的操作是可线化的，查找操作不含等待，并且其余操作（插入，删除和范围查询）是无锁的。我们的实验评估表明，在许多情况下，LFCA树取得了相关数据结构的两倍以上。此外，由于LFCA树在各种情况下都能比具有固定同步粒度的数据结构更好，因为它们能够适应手头方案。
Concurrent key-value stores with range query support are crucial for the scalability and performance of many applications. Existing lock-free data structures of this kind use a fixed synchronization granularity. Using a fixed synchronization granularity in a concurrent key-value store with range query support is problematic as the best performing synchronization granularity depends on a number of factors that are difficult to predict, such as the level of contention and the number of items that are accessed by range queries. We present the first linearizable lock-free key-value store with range query support that dynamically adapts its synchronization granularity. This data structure is called the lock-free contention adapting search tree (LFCA tree). An LFCA tree automatically performs local adaptations of its synchronization granularity based on heuristics that take contention and the performance of range queries into account. We show that the operations of LFCA trees are linearizable, that the lookup operation is wait-free, and that the remaining operations (insert, remove and range query) are lock-free. Our experimental evaluation shows that LFCA trees achieve more than twice the throughput of related lock-free data structures in many scenarios. Furthermore, LFCA trees are able to perform substantially better than data structures with a fixed synchronization granularity over a wide range of scenarios due to their ability to adapt to the scenario at hand.