License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.35
URN: urn:nbn:de:0030-drops-191612
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19161/
Go to the corresponding LIPIcs Volume Portal

Aksenov, Vitaly ; Anoprenko, Michael ; Fedorov, Alexander ; Spear, Michael

Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures

pdf-format:
LIPIcs-DISC-2023-35.pdf (0.6 MB)

Abstract

Batching is a technique that stores multiple keys/values in each node of a data structure. In sequential search data structures, batching reduces latency by reducing the number of cache misses and shortening the chain of pointers to dereference. Applying batching to concurrent data structures is challenging, because it is difficult to maintain the search property and keep contention low in the presence of batching.
In this paper, we present a general methodology for leveraging batching in concurrent search data structures, called BatchBoost. BatchBoost builds a search data structure from distinct "data" and "index" layers. The data layer’s purpose is to store a batch of key/value pairs in each of its nodes. The index layer uses an unmodified concurrent search data structure to route operations to a position in the data layer that is "close" to where the corresponding key should exist. The requirements on the index and data layers are low: with minimal effort, we were able to compose three highly scalable concurrent search data structures based on three original data structures as the index layers with a batched version of the Lazy List as the data layer. The resulting BatchBoost data structures provide significant performance improvements over their original counterparts.

BibTeX - Entry

@InProceedings{aksenov_et_al:LIPIcs.DISC.2023.35,
  author =	{Aksenov, Vitaly and Anoprenko, Michael and Fedorov, Alexander and Spear, Michael},
  title =	{{Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{35:1--35:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19161},
  URN =		{urn:nbn:de:0030-drops-191612},
  doi =		{10.4230/LIPIcs.DISC.2023.35},
  annote =	{Keywords: Concurrency, Synchronization, Locality}
}

Keywords: Concurrency, Synchronization, Locality
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI