Skip to main content
Erschienen in: Datenbank-Spektrum 3/2019

27.10.2019 | Schwerpunktbeitrag

Lock-free Data Structures for Data Stream Processing

A Closer Look

verfasst von: Alexander Baumstark, Constantin Pohl

Erschienen in: Datenbank-Spektrum | Ausgabe 3/2019

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Processing data in real-time instead of storing and reading from tables has led to a specialization of DBMS into the so-called data stream processing paradigm. While high throughput and low latency are key requirements to keep up with varying stream behavior and to allow fast reaction to incoming events, there are many possibilities how to achieve them. In combination with modern hardware, like server CPUs with tens of cores, the parallelization of stream queries for multithreading and vectorization is a common schema. High degrees of parallelism, however, need efficient synchronization mechanisms to allow good scaling with threads for shared memory access.In this work, we identify the most time-consuming operations for stream processing exemplarily for our own stream processing engine PipeFabric. In addition, we present different design principles of lock-free data structures which are suited to overcome those bottlenecks. We will finally demonstrate how lock-freedom greatly improves performance for join processing and tuple exchange between operators under different workloads. Nevertheless, the efficient usage of lock-free data structures comes with additional efforts and pitfalls, which we also discuss in this paper.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Weitere Produktempfehlungen anzeigen
Literatur
2.
Zurück zum Zitat Cheng X et al (2017) A study of main-memory hash joins on many-core processor: a case with intel knights landing architecture. In: Proceedings of the 2017 ACM on conference on information and knowledge management CIKM 2017, Singapore, 06.–10.11.2017, pp 657–666 https://doi.org/10.1145/3132847.3132916 CrossRef Cheng X et al (2017) A study of main-memory hash joins on many-core processor: a case with intel knights landing architecture. In: Proceedings of the 2017 ACM on conference on information and knowledge management CIKM 2017, Singapore, 06.–10.11.2017, pp 657–666 https://​doi.​org/​10.​1145/​3132847.​3132916 CrossRef
3.
Zurück zum Zitat Dechev D et al (2010) Understanding and effectively preventing the ABA problem in descriptor-based lock-free designs. In: 13th IEEE international symposium on international symposium on object-oriented real-time distributed computing ISORC 2010, Carmona, Sevilla, 05.–06.05.2010, pp 185–192 https://doi.org/10.1109/ISORC.2010.10 CrossRef Dechev D et al (2010) Understanding and effectively preventing the ABA problem in descriptor-based lock-free designs. In: 13th IEEE international symposium on international symposium on object-oriented real-time distributed computing ISORC 2010, Carmona, Sevilla, 05.–06.05.2010, pp 185–192 https://​doi.​org/​10.​1109/​ISORC.​2010.​10 CrossRef
5.
Zurück zum Zitat Gulisano V et al (2015) Scalejoin: A deterministic, disjoint-parallel and skew-resilient stream join. In: IEEE International Conference on Big Data IEEE Big Data 2015, Santa Clara, 29.10.–01.11.2015. vol 2015, pp 144–153 Gulisano V et al (2015) Scalejoin: A deterministic, disjoint-parallel and skew-resilient stream join. In: IEEE International Conference on Big Data IEEE Big Data 2015, Santa Clara, 29.10.–01.11.2015. vol 2015, pp 144–153
8.
Zurück zum Zitat Hennessy JL, Patterson DA (2006) Computer architecture: a quantitative approach, 4th edn.MATH Hennessy JL, Patterson DA (2006) Computer architecture: a quantitative approach, 4th edn.MATH
10.
Zurück zum Zitat Herlihy M, Shavit N (2008) The art of multiprocessor programming. Morgan Kaufmann, Amsterdam Herlihy M, Shavit N (2008) The art of multiprocessor programming. Morgan Kaufmann, Amsterdam
14.
Zurück zum Zitat Miao H et al (2017) Streambox: modern stream processing on a multicore machine. In: USENIX annual technical conference USENIX ATC 2017, Santa Clara, 12.–14.07.2017, pp 617–629 Miao H et al (2017) Streambox: modern stream processing on a multicore machine. In: USENIX annual technical conference USENIX ATC 2017, Santa Clara, 12.–14.07.2017, pp 617–629
17.
Zurück zum Zitat Michael MM, Scott ML (1996) Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proceedings of the fifteenth annual ACM symposium on principles of distributed computing PODC ’96, Philadelphia, 23.–26.05.1996, pp 267–275 https://doi.org/10.1145/248052.248106 CrossRef Michael MM, Scott ML (1996) Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In: Proceedings of the fifteenth annual ACM symposium on principles of distributed computing PODC ’96, Philadelphia, 23.–26.05.1996, pp 267–275 https://​doi.​org/​10.​1145/​248052.​248106 CrossRef
19.
Zurück zum Zitat Treiber RK (1986) Systems programming: coping with parallelism. IBM, San Jose (Research report) Treiber RK (1986) Systems programming: coping with parallelism. IBM, San Jose (Research report)
23.
Zurück zum Zitat Yu X et al (2014) Staring into the abyss: an evaluation of concurrency control with one thousand cores. Proceedings VLDB Endowment 8(3):209–220CrossRef Yu X et al (2014) Staring into the abyss: an evaluation of concurrency control with one thousand cores. Proceedings VLDB Endowment 8(3):209–220CrossRef
24.
Zurück zum Zitat Zaharia M et al (2012) Discretized streams: an efficient and fault-tolerant model for stream processing on large clusters. In: 4th USENIX workshop on hot topics in cloud computing HotCloud ’12, Boston, 12.–13.06.2012 Zaharia M et al (2012) Discretized streams: an efficient and fault-tolerant model for stream processing on large clusters. In: 4th USENIX workshop on hot topics in cloud computing HotCloud ’12, Boston, 12.–13.06.2012
Metadaten
Titel
Lock-free Data Structures for Data Stream Processing
A Closer Look
verfasst von
Alexander Baumstark
Constantin Pohl
Publikationsdatum
27.10.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
Datenbank-Spektrum / Ausgabe 3/2019
Print ISSN: 1618-2162
Elektronische ISSN: 1610-1995
DOI
https://doi.org/10.1007/s13222-019-00329-4

Weitere Artikel der Ausgabe 3/2019

Datenbank-Spektrum 3/2019 Zur Ausgabe

Editorial

Editorial

Community

News

Dissertationen

Dissertationen