Split-ordered lists: lock-free extensible hash tables

ABSTRACT

We present the first lock-free implementation of an extensible hash table running on current architectures. It provides concurrent insert, delete, and search operations with an expected O(1) cost. It consists of very simple code, easily implementable using only load, store, and compare-and-swap operations. The new mathematical structure at the core of our algorithm is recursive split-ordering, a way of ordering elements in a linked list so that they can be repeatedly "split" using a single compare-and-swap operation. Empirical tests conducted on a large shared memory multiprocessor show that even in non-multiprogrammed environments, the new algorithm significantly outperforms the most efficient known lock-based algorithm at all concurrency levels, exhibiting up to four times higher throughput at peak load. The incremental nature of our algorithm makes it well suited for real-time applications, as it offers predictable performance without unexpected breaks for resizing.

References

1. CORMEN, T. H., LEISERSON, C. E., RIVEST, R. L., AND STEIN, C. Introduction to Algorithms, Second Edition. MIT Press, Cambridge, Massachusetts, 2001.
2. GAO, H., GROOTE, J., AND HESSELINK, W. Efficient almost wait-free parallel accessible dynamic hashtables, March 2003. Unpublished manuscript.
3. GREENWALD, M. Non-Blocking Synchronization and System Design. PhD thesis, Stanford University Technical Report STAN-CS-TR-99-1624, Palo Alto, CA, 8 1999.
4. GREENWALD, M. Two-handed emulation: How to build non-blocking implementations of complex data-structures using dcas. In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (July 2002), pp. 260--269.
5. HARRIS, T. L. A pragmatic implementation of non-blocking linked-lists. Lecture Notes in Computer Science 2180 (2001), 300--314.
6. HERLIHY, M., LUCHANGCO, V., AND MOIR, M. The repeat offender problem: A mechanism for supporting dynamic-sized, lock-free data structures. In Proceedings of 16th International Symposium on Distributed Computing (DISC 2002) (October 2002), pp. 339--353.
7. HERLIHY, M., LUCHANGCO, V., AND MOIR, M. Sotware transactional memory for dynamic-sized data structures. In Proc. 22th Annual ACM Symposium on Principles of Distributed Computing (July 2003).
8. HERLIHY, M. P., AND WING, J. M. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3 (1990), 463--492.
9. HESSELINK, W., GROOTE, J., MAUW, S., AND VERMEULEN, R. An algorithm for the asynchronous write-all problem based on process collision. Distributed Computing 14, 2 (2001), 75--81.
10. HSU, M., AND YANG, W. Concurrent operations in extendible hashing. In VLDB '86 Twelfth International Conference on Very Large Data Bases, August 25--28, 1986, Kyoto, Japan, Proceedings (1986), W. W. Chu, G. Gardarin, S. Ohsuga, and Y. Kambayashi, Eds., Morgan Kaufmann, pp. 241--247.
11. LEA, D. Hash table util.concurrent.concurrenthashmap in JSR-166, the proposed Java Concurrency Package. http://gee.cs.oswego.edu/dl/.
12. LEA, D. Personal communication, Jan. 2003.
13. LITWIN, W. Linear hashing: A new tool for file and table addressing. In Sixth International Conference on Very Large Data Bases, October 1--3, 1980, Montreal, Quebec, Canada, Proceedings (1980), IEEE Computer Society, pp. 212--223.
14. LUCHANGCO, V., MOIR, M., AND SHAVIT, N. Nonblocking k-compare single swap. In Proc. 15th Annual ACM Symposium on Parallel Algorithms and Architectures (June 2003).
15. MELLOR-CRUMMEY, J. M., AND SCOTT, M. L. Scalable reader-writer synchronization for shared-memory multiprocessors. In Proceedings of the third ACM SIGPLAN symposium on Principles & practice of parallel programming (1991), ACM Press, pp. 106--113.
16. MICHAEL, M. M. High performance dynamic lock-free hash tables and list-based sets. In Proceedings of the fourteenth annual A CM symposium on Parallel algorithms and architectures (2002), ACM Press, pp. 73--82.
17. MICHAEL, M. M. Safe memory reclamation for dynamic lock-free objects using atomic reads and writes. In Proceedings of the twenty-first annual symposium on Principles of distributed computing (2002), ACM Press, pp. 21--30.
18. MICHAEL, M. M., AND SCOTT, M. L. Nonblocking algorithms and preemption-safe locking on multiprogrammed shared --- memory multiprocessors. Journal of Parallel and Distributed Computing 51, 1 (1998), 1--26.
19. MOIR, M. Practical implementations of non-blocking synchronization primitives. In Proceedings of the 15th Annual ACM Symposium on the Principles of Distributed Computing (Aug. 1997).
20. VALOIS, J. D. Lock-free linked lists using compare-and-swap. In Symposium on Principles of Distributed Computing (1995), pp. 214--222.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

    • Parallel programming languages

• Information systems

  • Information storage systems

    • Record storage systems

      • Record storage alternatives

        • Hashed file organization

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types

        • Parallel programming languages

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Concurrency control

          • Multiprocessing / multiprogramming / multitasking

          • Process synchronization