Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1145/3037697.3037721 | ASPLOS |
Field | DocType | Volume |
Black box (phreaking),Linearizability,Data structure,Programming language,Concurrency,Computer data storage,Computer science,Server,Parallel computing,Real-time computing,Concurrent data structure,Replicate | Conference | 51 |
Issue | ISSN | Citations |
2 | 0163-5980 | 7 |
PageRank | References | Authors |
0.44 | 48 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Irina Calciu | 1 | 108 | 6.96 |
Siddhartha Sen | 2 | 312 | 35.46 |
Mahesh Balakrishnan | 3 | 1132 | 57.92 |
Marcos Kawazoe Aguilera | 4 | 2519 | 153.60 |