Black-box Concurrent Data Structures for NUMA Architectures
Black-box Concurrent Data Structures for NUMA Architectures
复制标题
DOI：
10.1145/3037697.3037721
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
I. Calciu;S. Sen;M. Balakrishnan;M. Aguilera
中科院分区：
文献类型：
--
作者：
I. Calciu;S. Sen;M. Balakrishnan;M. Aguilera
高性能服务器是非一致内存访问(NUMA)计算机。为了充分利用这些机器，程序员需要能够识别NUMA性能构件的高效并发数据结构。我们提出了节点复制(NR)，这是一种获取此类数据结构的黑盒方法。NR采用任意顺序数据结构，并自动将其转换为满足线性化的NUMA感知并发数据结构。使用NR不需要并发数据结构设计方面的专业知识，结果是没有并发错误。NR借鉴了两个学科的思想：共享内存算法和分布式系统。简而言之，NR实现了NUMA感知的共享日志，然后使用该日志跨NUMA节点一致地复制数据结构。NR最适合竞争数据结构，在竞争数据结构中，它的性能比无锁算法高3.1倍，比基于锁的解决方案高30倍。为了展示NR在实际应用中的优势，我们将NR应用到内存存储系统Redis的数据结构中。结果比其他方法高出14倍。NR的成本是为其日志和副本增加内存。
High-performance servers are Non-Uniform Memory Access (NUMA) machines. To fully leverage these machines, programmers need efficient concurrent data structures that are aware of the NUMA performance artifacts. We propose Node Replication (NR), a black-box approach to obtaining such data structures. NR takes an arbitrary sequential data structure and automatically transforms it into a NUMA-aware concurrent data structure satisfying linearizability. Using NR requires no expertise in concurrent data structure design, and the result is free of concurrency bugs. NR draws ideas from two disciplines: shared-memory algorithms and distributed systems. Briefly, NR implements a NUMA-aware shared log, and then uses the log to replicate data structures consistently across NUMA nodes. NR is best suited for contended data structures, where it can outperform lock-free algorithms by 3.1x, and lock-based solutions by 30x. To show the benefits of NR to a real application, we apply NR to the data structures of Redis, an in-memory storage system. The result outperforms other methods by up to 14x. The cost of NR is additional memory for its log and replicas.