Lock-free Linearizable 1-Dimensional Range Queries

ABSTRACT

Efficient concurrent data structures that support range queries are highly sought-after in a number of application areas. For example, the contemporary big-data processing platforms employ them as in-memory index structures for fast and scalable real-time updates and analytics, where analytics utilizes the range queries.

In this paper, we present a generic algorithm to perform linearizable range queries in lock-free ordered 1-dimensional data structures. The algorithm requires single-word atomic compare-and-swap (CAS) primitives. Our method generalizes the lock-free data structure snapshot of Petrank et al. [25]. Fundamentally, we utilize a partial snapshot object derived from the snapshot object of Jayanti [20].

We experimentally evaluate the proposed algorithm in a lock-free linked-list, skip-list and binary search tree (BST). The experiments demonstrate that our algorithm is scalable even in the presence of high percentage of concurrent modify operations and outperforms an existing range search algorithm in lock-free k-ary trees in several scenarios.

References

1. Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots of shared memory. Journal of the ACM (JACM), 40(4):873--890, 1993.
2. Y. Afek, G. Stupp, and D. Touitou. Long-lived adaptive collect with applications. In 40th FOCS, pages 262--272, 1999.
3. H. Attiya, R. Guerraoui, and E. Ruppert. Partial snapshot objects. In 20th SPAA, pages 336--343, 2008.
4. H. Avni, N. Shavit, and A. Suissa. Leaplist: lessons learned in designing tm-supported range queries. In 32nd PODC, pages 299--308. ACM, 2013.
5. D. Basin, E. Bortnikov, A. Braginsky, G. Golan Gueta, E. Hillel, I. Keidar, and M. Sulamy. Brief announcement: A key-value map for massive real-time analytics. In 35th PODC, pages 487--489, 2016.
6. T. Brown and H. Avni. Range queries in non-blocking k-ary search trees. In 16th OPODIS, pages 31--45. Springer, 2012.
7. F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. E. Gruber. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS), 26(2):4, 2008.
8. B. Chatterjee. Lock-free 1-dimensional range queries. Technical Report 2015:06, ISNN 1652-926X, Chalmers University of Technology, 2015.
9. B. Chatterjee, N. Nguyen, and P. Tsigas. Efficient lock-free binary search trees. In 33rd PODC, pages 322--331, 2014.
10. B. Chatterjee, I. Walulya, and P. Tsigas. Concurrent linearizable nearest neighbour search in lockfree-kd-tree. Technical report, Chalmers University of Technology, 2015.
11. F. Ellen, P. Fatourou, J. Helga, and E. Rupert. The amortized complexity of non-blocking binary search trees. In 33rd PODC, pages 332--341, 2014.
12. F. Ellen, P. Fatourou, E. Ruppert, and F. van Breugel. Non-blocking binary search trees. In 29th PODC, pages 131--140, 2010.
13. M. Fomitchev and E. Ruppert. Lock-free linked lists and skip lists. In 23rd PODC, pages 50--59, 2004.
14. T. L. Harris. A pragmatic implementation of non-blocking linked-lists. In 15th DISC, pages 300--314, 2001.
15. A. HBase. A distributed database for large datasets. The Apache Software Foundation, Los Angeles, CA. URL http://hbase.apache.org, 4(4.2).
16. M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124--149, 1991.
17. M. P. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463--492, 1990.
18. S. V. Howley and J. Jones. A non-blocking internal binary search tree. In 24th SPAA, pages 161--171, 2012.
19. D. Imbs and M. Raynal. Help when needed, but no more: efficient read/write partial snapshot. Journal of Parallel and Distributed Computing, 72(1):1--12, 2012.
20. P. Jayanti. An optimal multi-writer snapshot algorithm. In 37th STOC, pages 723--732, 2005.
21. D. Lea. ConcurrentSkipListMap. In java.util.concurrent.
22. M. M. Michael and M. L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In 15th PODC, pages 267--275, 1996.
23. A. Natarajan and N. Mittal. Fast concurrent lock-free binary search trees. In 19th PPoPP, pages 317--328, 2014.
24. N. Nguyen, P. Tsigas, and H. Sundell. Parmarksplit: A parallel mark-split garbage collector based on a lock-free skip-list. In International Conference on Principles of Distributed Systems, pages 372--387. Springer, 2014.
25. E. Petrank and S. Timnat. Lock-free data-structure iterators. In Distributed Computing, pages 224--238. Springer, 2013.
26. A. Prokopec, N. G. Bronson, P. Bagwell, and M. Odersky. Concurrent tries with efficient non-blocking snapshots. In Acm Sigplan Notices, volume 47, pages 151--160. ACM, 2012.
27. K. F. Sagonas and K. Winblad. Efficient support for range queries and range updates using contention adapting search trees. In Languages and Compilers for Parallel Computing - 28th International Workshop, LCPC 2015, Raleigh, NC, USA, September 9-11, 2015, Revised Selected Papers, pages 37--53, 2015.
28. H. Samet. Foundations of multidimensional and metric data structures. Morgan Kaufmann, 2006.
29. H. Sundell and P. Tsigas. Fast and lock-free concurrent priority queues for multi-thread systems. J. Parallel Distrib. Comput., 65(5):609--627, 2005.
30. H. Sundell and P. Tsigas. Lock-free and practical doubly linked list-based deques using single-word compare-and-swap. In 9th OPODIS, pages 240--255. Springer, 2005.

• Computing methodologies

  • Concurrent computing methodologies