KiWi: A Key-Value Map for Scalable Real-Time Analytics

Abstract

Modern big data processing platforms employ huge in-memory key-value (KV) maps. Their applications simultaneously drive high-rate data ingestion and large-scale analytics. These two scenarios expect KV-map implementations that scale well with both real-time updates and large atomic scans triggered by range queries.

We present KiWi, the first atomic KV-map to efficiently support simultaneous large scans and real-time access. The key to achieving this is treating scans as first class citizens,and organizing the data structure around them. KiWi provides wait-free scans, whereas its put operations are lightweight and lock-free. It optimizes memory management jointly with data structure access.We implement KiWi and compare it to state-of-the-art solutions. Compared to other KV-maps providing atomic scans, KiWi performs either long scans or concurrent puts an order of magnitude faster. Its scans are twice as fast as non-atomic ones implemented via iterators in the Java skiplist.

References

1. Apache HBase -- a Distributed Hadoop Database. https://hbase.apache.org/.
2. Java Array Copy. https://docs.oracle.com/javase/7/docs/api/java/lang/System.html, .
3. Java Concurrent Skip List. https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentSkipListMap.html, .
4. http://flurrymobile.tumblr.com/post/144245637325/appmatrix.
5. Flurry analytics. https://developer.yahoo.com/flurry/docs/analytics/.
6. http://flurrymobile.tumblr.com/post/117769261810/the-phablet-revolution.
7. A persistent key-value store for fast storage environments. http://rocksdb.org/, June 2014.
8. A fast and lightweight key/value database library by google. http://code.google.com/p/leveldb, Jan. 2014.
9. M. Arbel, G. Golan-Gueta, E. Hillel, and I. Keidar. Towards automatic lock removal for scalable synchronization. In DISC, pages 170--184, 2015.
10. P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. AddisonWesley, 1987. ISBN 0--201--10715--5.
11. A. Braginsky and E. Petrank. Locality-conscious lock-free linked lists. In ICDCN, pages 107--118, 2011.
12. A. Braginsky and E. Petrank. A lock-free B+tree. In SPAA, pages 58--67, 2012.
13. A. Braginsky, E. Petrank, and N. Cohen. CBPQ: High performance lock-free priority queue. In Euro-Par, 2016.
14. N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. In PPOPP, pages 257--268, 2010.
15. T. Brown and H. Avni. Range queries in non-blocking k-ary search trees. In OPODIS, pages 31--45, 2012.
16. T. Brown and J. Helga. Non-blocking k-ary search trees. In OPODIS, pages 207--221, 2011.
17. 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 Trans. Comput. Syst., 26(2):4:1--4:26, June 2008. ISSN 0734--2071.
18. B. Chatterjee. Lock-free linearizable 1-dimensional range queries. In WTTM, 2016.
19. K. Fraser. Practical lock-freedom. In PhD dissertation, University of Cambridge, 2004.
20. G. Golan-Gueta, E. Bortnikov, E. Hillel, and I. Keidar. Scaling concurrent log-structured data stores. In EuroSys, pages 32:1-- 32:14, 2015.
21. V. Gramoli. More than you ever wanted to know about synchronization: Synchrobench, measuring the impact of the synchronization on concurrent algorithms. In PPoPP, 2015.
22. D. Hendler, N. Shavit, and L. Yerushalmi. A scalable lockfree stack algorithm. In SPAA, pages 206--215, 2004.
23. M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., 2008.
24. M. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463--492, 1990.
25. M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit. A simple optimistic skiplist algorithm. In SIROCCO, pages 124--138, 2007.
26. I. Keidar and D. Perelman. Multi-versioning in transactional memory. In Transactional Memory; Foundations, Algorithms, Tools, and Applications, volume 8913, chapter 7, pages 150--165. 2015.
27. A. Kogan and E. Petrank. A methodology for creating fast wait-free data structures. In PPoPP, pages 141--150, 2012.
28. D. B. Lomet, S. Sengupta, and J. J. Levandoski. The bw-tree: A b-tree for new hardware platforms. In ICDE, pages 302-- 313, 2013.
29. Y. Mao, E. Kohler, and R. T. Morris. Cache craftiness for fast multicore key-value storage. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys '12, pages 183--196, 2012.
30. A. Natarajan and N. Mittal. Fast concurrent lock-free binary search trees. In PPoPP, pages 317--328, 2014.
31. E. Petrank and S. Timnat. Lock-free data-structure iterators. In DISC, pages 224--238, 2013.
32. A. Prokopec, N. G. Bronson, P. Bagwell, and M. Odersky. Concurrent tries with efficient non-blocking snapshots. In PPoPP, pages 151--160, 2012.
33. J. Shute, R. Vingralek, B. Samwel, B. Handy, C. Whipkey, E. Rollins, M. Oancea, K. Littlefield, D. Menestrina, S. Ellner, J. Cieslewicz, I. Rae, T. Stancescu, and H. Apte. F1: A distributed sql database that scales. In VLDB, 2013.
34. B. Sowell, W. Golab, and M. A. Shah. Minuet: A scalable distributed multiversion b-tree. Proc. VLDB Endow., 5(9): 884--895, May 2012.
35. A. Spiegelman, G. Golan-Gueta, and I. Keidar. Transactional data structure libraries. In PLDI, pages 682--696, 2016.
36. J. L. Welch and H. Attiya. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). John Wiley Interscience, 2004.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Concurrent algorithms

  • Theory and algorithms for application domains

    • Database theory

      • Data structures and algorithms for data management