research-article

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

Authors:

Edward Bortnikov,

Anastasia Braginsky,

Guy Golan-Gueta,

Moshe SulamyAuthors Info & Claims

ACM SIGPLAN Notices, Volume 52, Issue 8

Pages 357 - 369

https://doi.org/10.1145/3155284.3018761

Published: 26 January 2017 Publication History

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.

Digital Library

[10]

P. A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in Database Systems. AddisonWesley, 1987. ISBN 0--201--10715--5.

Digital Library

[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.

Digital Library

[13]

A. Braginsky, E. Petrank, and N. Cohen. CBPQ: High performance lock-free priority queue. In Euro-Par, 2016.

Digital Library

[14]

N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun. A practical concurrent binary search tree. In PPOPP, pages 257--268, 2010.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[24]

M. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463--492, 1990.

Digital Library

[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.

Digital Library

[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.

Digital Library

[30]

A. Natarajan and N. Mittal. Fast concurrent lock-free binary search trees. In PPoPP, pages 317--328, 2014.

Digital Library

[31]

E. Petrank and S. Timnat. Lock-free data-structure iterators. In DISC, pages 224--238, 2013.

Digital Library

[32]

A. Prokopec, N. G. Bronson, P. Bagwell, and M. Odersky. Concurrent tries with efficient non-blocking snapshots. In PPoPP, pages 151--160, 2012.

Digital Library

[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.

Digital Library

[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.

Digital Library

[35]

A. Spiegelman, G. Golan-Gueta, and I. Keidar. Transactional data structure libraries. In PLDI, pages 682--696, 2016.

Digital Library

[36]

J. L. Welch and H. Attiya. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). John Wiley Interscience, 2004.

Cited By

Bhardwaj GChatterjee BJain APeri S(2023)Wait-Free Updates and Range Search Using UruvStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_33(435-450)Online publication date: 30-Sep-2023
https://doi.org/10.1007/978-3-031-44274-2_33
Jordan HSubotić PZhao DScholz B(2020)Specializing parallel data structures for DatalogConcurrency and Computation: Practice and Experience10.1002/cpe.564334:2Online publication date: 7-Jan-2020
https://doi.org/10.1002/cpe.5643
Jordan HSubotić PZhao DScholz B(2019)BrieProceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3303084.3309490(31-40)Online publication date: 17-Feb-2019
https://dl.acm.org/doi/10.1145/3303084.3309490
Show More Cited By

Index Terms

KiWi: A Key-Value Map for Scalable Real-Time Analytics
1. Theory of computation
  1. Design and analysis of algorithms
    1. Concurrent algorithms
  2. Theory and algorithms for application domains
    1. Database theory
      1. Data structures and algorithms for data management

Recommendations

KiWi: A Key-value Map for Scalable Real-time Analytics
Special Issue on PPoPP 2017 (Part 2) and Regular Papers

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 ...
KiWi: A Key-Value Map for Scalable Real-Time Analytics
PPoPP '17: Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

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-...
Flying KIWI: Design of Approximate Query Processing Engine for Interactive Data Analytics at Scale
BigDAS '15: Proceedings of the 2015 International Conference on Big Data Applications and Services

This paper introduces the design of hybrid SQL-on-Hadoop system, which supports dual-mode (interactive and deep) analytics. We present an architecture of approximate query processing engine using horizontal and vertical sampling of the original database ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 52, Issue 8

PPoPP '17

August 2017

442 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/3155284

Editor:
Matthew Fluet

Issue’s Table of Contents

PPoPP '17: Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
January 2017
476 pages
ISBN:9781450344937
DOI:10.1145/3018743
General Chair:
Vivek Sarkar
Rice University, USA
,
Program Chair:
Lawrence Rauchwerger
Texas A&M University, USA

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 January 2017

Published in SIGPLAN Volume 52, Issue 8

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
447
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)4

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhardwaj GChatterjee BJain APeri S(2023)Wait-Free Updates and Range Search Using UruvStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_33(435-450)Online publication date: 30-Sep-2023
https://doi.org/10.1007/978-3-031-44274-2_33
Jordan HSubotić PZhao DScholz B(2020)Specializing parallel data structures for DatalogConcurrency and Computation: Practice and Experience10.1002/cpe.564334:2Online publication date: 7-Jan-2020
https://doi.org/10.1002/cpe.5643
Jordan HSubotić PZhao DScholz B(2019)BrieProceedings of the 10th International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3303084.3309490(31-40)Online publication date: 17-Feb-2019
https://dl.acm.org/doi/10.1145/3303084.3309490
Kobus TKokoci?ski MWojciechowski PDhulipala LSun Y(2024)Jiffy: A Lock-free Skip List with Batch Updates and Snapshots (Abstract)Proceedings of the 2024 ACM Workshop on Highlights of Parallel Computing10.1145/3670684.3673410(5-7)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3670684.3673410
Dhulipala LBlelloch GGu YSun YJhala RDillig I(2022)PaC-trees: supporting parallel and compressed purely-functional collectionsProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523733(108-121)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523733
Blelloch GFerizovic DSun Y(2022)Joinable Parallel Balanced Binary TreesACM Transactions on Parallel Computing10.1145/35127699:2(1-41)Online publication date: 11-Apr-2022
https://dl.acm.org/doi/10.1145/3512769
Kobus TKokociński MWojciechowski PLee JAgrawal KSpear M(2022)JiffyProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508437(400-415)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508437
Nelson-Slivon JHassan APalmieri RLee JAgrawal KSpear M(2022)Bundling linked data structures for linearizable range queriesProceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/3503221.3508412(368-384)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1145/3503221.3508412
Jiang XCai MYe B(2022)Improving Write Performance for LSM-tree-based Key-Value Stores with NV-Cache2022 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/SocialCom/SustainCom)10.1109/ISPA-BDCloud-SocialCom-SustainCom57177.2022.00057(394-401)Online publication date: Dec-2022
https://doi.org/10.1109/ISPA-BDCloud-SocialCom-SustainCom57177.2022.00057
Raisamo RSalminen KRantala JFarooq AZiat M(2022)Interpersonal Haptic CommunicationInternational Journal of Human-Computer Studies10.1016/j.ijhcs.2022.102881166:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.ijhcs.2022.102881
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents