As adoption of non-uniform memory access (NUMA) architectures has grown, efficient concurrent data structures have become essential to take advantage of all the cores available in NUMA machines. VMware has been actively involved in researching techniques to automatically produce concurrent thread-safe data structures from their sequential, non-thread safe implementations. The results, presented at the ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), won one of the two Best Paper Awards.
The recipe for the success of this endeavor came from integrating techniques from distributed systems and shared-memory algorithms to form a new approach, Node Replication (NR). The secret ingredient is replicating the sequential data structures across the NUMA nodes. The key is to minimize the amount of data shared between nodes, which is achieved using an in-memory log that provides synchronization between replicas. Mix in the Flat Combining technique, which coordinates operations within a node efficiently and decreases contention on the log through batching. The goal of NR is to work well under contention, an area where other methods have fallen short. Building concurrent data structures for NUMA is laborious and error-prone, even for an expert programmer. NR produces concurrent data structures that are linearizable and free from concurrency bugs from black-box sequential data structures with no special skills needed. This is similar to the way a box of pasta is easier to make than homemade pasta.
A “taste” test was performed on Redis’ data structures to compare NR to five other approaches. The results showed that under high contention, NR outperformed all others except tailored-made NUMA-aware data structures. Just as good recipes put on extra pounds, NR needs additional memory for the log and replicas, so this approach is best suited for small- to medium-sized structures.
For the background of concurrent data structure approaches, NR algorithm details, and more importantly, the evaluation results, see “Black-box Concurrent Data Structures for NUMA Architectures“, Irina Calciu (VMware Research); Siddhartha Sen (Microsoft Research); Mahesh Balakrishnan (Yale University); Marcos K. Aguilera (VMware Research). To learn more about what projects VMware Researchers are working on click here.
Comments