This post has been republished via RSS; it originally appeared at: Channel 9.
The design of fast, scalable, and correct concurrent systems remains a notoriously difficult task. Particularly problematic is the design of fast and scalable concurrent search data structures, which lie at the core of many modern systems.
In this talk, I will present generic solutions to address this problem. I will first present a set of patterns that when applied, result in concurrent search data structures that scale across different platforms, workloads, and metrics (universally). These patterns can be used to improve existing algorithms, as well as to design new concurrent data structure algorithms from scratch - thus greatly simplifying this process.
I will then discuss the impact that progress guarantees have on such data structures, and show that blocking algorithms, which are significantly easier to design and reason about than their non-blocking counterparts, are in fact sufficient in a large variety of common scenarios. Finally, I will discuss how these data structures can be designed such that they retain their performance and scalability when using non-volatile RAM, an upcoming technology.
To conclude, I shall briefly discuss some additional work that concerns both concurrent and larger scale distributed systems, and sketch potential avenues for future research.
