An Efficient Lock-Free Logarithmic Search Data Structure Based on Multi-dimensional List
An Efficient Lock-Free Logarithmic Search Data Structure Based on Multi-dimensional List
复制标题
一种基于多维列表的高效无锁对数搜索数据结构
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
D. Dechev
中科院分区：
文献类型：
--
作者：
Deli Zhang;D. Dechev
对数搜索数据结构，如搜索树和跳转列表，是许多应用程序的基本构建块。虽然自平衡二叉搜索树是最普遍的顺序搜索数据结构之一，但由于所需的结构变更，可能会使其他并发操作停止，因此设计非阻塞再平衡算法具有挑战性。Skiplists在一个有序列表中概率性地创建多个级别的快捷方式，为平衡搜索树提供了实用的替代方案。使用skiplists消除了重新平衡的需要，并确保摊销的对数顺序搜索时间，但并发性是有限的写为主的工作负载，因为多个远程节点之间的链接必须更新。在本文中，我们提出了一个线性化的无锁字典设计的多维列表（MDList）的基础上。MDList中的节点按维度排列其子节点，并按坐标前缀对其进行排序。搜索操作首先生成从标量键到高维向量空间的一对一映射，然后使用向量作为坐标来唯一地定位目标位置。我们的算法保证最坏情况下的搜索时间为O（log N），其中N是密钥空间的大小。此外，数据结构的排序属性在突变期间容易保持，而无需重新平衡或随机化。在我们使用微基准测试的实验评估中，当密钥宇宙很大时，我们的字典比最先进的方法性能高出100%，在所有场景中平均为30%。
Logarithmic search data structures, such as search trees and skiplists, are fundamental building blocks of many applications. Although the self-balancing binary search trees are among the most ubiquitous sequential search data structures, designing non-blocking rebalancing algorithms is challenging due to the required structural alternation, which may stall other concurrent operations. Skiplists, which probabilistically create multiple levels of shortcuts in an ordered list, provide practical alternatives to balanced search trees. The use of skiplists eliminates the need of rebalancing and ensures amortized logarithmic sequential search time, but concurrency is limited under write-dominated workload because the linkage between multiple distant nodes must be updated. In this paper, we present a linearizable lock-free dictionary design based on a multi-dimensional list (MDList). A node in an MDList arranges its child nodes by their dimensionality and order them by coordinate prefixes. The search operation works by first generating a one-to-one mapping from the scalar keys to a high-dimensional vectors space, then uniquely locating the target position by using the vector as coordinates. Our algorithm guarantees worst-case search time of O(log N) where N is the size of key space. Moreover, the ordering property of the data structure is readily maintained during mutations without rebalancing nor randomization. In our experimental evaluation using a micro-benchmark, our dictionary outperforms the state of the art approaches by as much as 100% when the key universe is large and an average of 30% across all scenarios.