Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments

Safdar Jamil; Awais Khan; Bernd Burastaller; Youngjae Kim

doi:10.1109/ACSOS-C52956.2021.00022

Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments

Safdar Jamil, Awais Khan, Bernd Burastaller, Youngjae Kim

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

The emergence of manycore machines with Intel DC Persistent Memory (DCPM) aims to provide high performance and scalability with persistence guarantees. Thus, it is required to offer opportunities to port DRAM-based index data structures to DCPM to fully exploit the performance of these machines. Fast Fair (FF) is the state-of-the-art concurrent variant of the B+ -tree for DCPM. However, its adoption on manycore machines suffers from scalability limitations due to lengthy, lock-based synchronization including structure modification operations (SMOs). In this work, we propose F3 -tree, a concurrent, persistent future-based B+-tree that shows superior scalability on DCPMs. F3 -tree design relies on thread-local future objects and a global B+ -tree. We employ an in-memory hash table to mitigate the read overhead for the key searches in thread-local future objects. We implemented the proposed ideas atop F F and performed experiments on Linux (kernel v5.4.0) using both synthetic and real-world workloads. We evaluated F3 -tree with F F and the results show that F3 -tree outperforms F F by 3.4x on average for sequential, random, and mixed workloads.

Original language	English
Title of host publication	Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021
Editors	Esam El-Araby, Vana Kalogeraki, Danilo Pianini, Frederic Lassabe, Barry Porter, Sona Ghahremani, Ingrid Nunes, Mohamed Bakhouya, Sven Tomforde
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	44-49
Number of pages	6
ISBN (Electronic)	9781665443937
DOIs	https://doi.org/10.1109/ACSOS-C52956.2021.00022
State	Published - 2021
Externally published	Yes
Event	2nd IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021 - Virtual, Washington, United States Duration: Sep 27 2021 → Oct 1 2021

Publication series

Name	Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021

Conference

Conference	2nd IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021
Country/Territory	United States
City	Virtual, Washington
Period	09/27/21 → 10/1/21

Funding

This work was supported by the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2014-3-00035, Research on High Performance and Scalable Manycore Operating System).

Keywords

Cloud Computing
Persistent Memory
Scalability

Access to Document

10.1109/ACSOS-C52956.2021.00022

Cite this

Jamil, S., Khan, A., Burastaller, B., & Kim, Y. (2021). Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments. In E. El-Araby, V. Kalogeraki, D. Pianini, F. Lassabe, B. Porter, S. Ghahremani, I. Nunes, M. Bakhouya, & S. Tomforde (Eds.), Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021 (pp. 44-49). (Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ACSOS-C52956.2021.00022

Jamil, Safdar ; Khan, Awais ; Burastaller, Bernd et al. / Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments. Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021. editor / Esam El-Araby ; Vana Kalogeraki ; Danilo Pianini ; Frederic Lassabe ; Barry Porter ; Sona Ghahremani ; Ingrid Nunes ; Mohamed Bakhouya ; Sven Tomforde. Institute of Electrical and Electronics Engineers Inc., 2021. pp. 44-49 (Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021).

@inproceedings{c1d58eaccda94f8a85ec77ccc9ca71bd,

title = "Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments",

abstract = "The emergence of manycore machines with Intel DC Persistent Memory (DCPM) aims to provide high performance and scalability with persistence guarantees. Thus, it is required to offer opportunities to port DRAM-based index data structures to DCPM to fully exploit the performance of these machines. Fast Fair (FF) is the state-of-the-art concurrent variant of the B+ -tree for DCPM. However, its adoption on manycore machines suffers from scalability limitations due to lengthy, lock-based synchronization including structure modification operations (SMOs). In this work, we propose F3 -tree, a concurrent, persistent future-based B+-tree that shows superior scalability on DCPMs. F3 -tree design relies on thread-local future objects and a global B+ -tree. We employ an in-memory hash table to mitigate the read overhead for the key searches in thread-local future objects. We implemented the proposed ideas atop F F and performed experiments on Linux (kernel v5.4.0) using both synthetic and real-world workloads. We evaluated F3 -tree with F F and the results show that F3 -tree outperforms F F by 3.4x on average for sequential, random, and mixed workloads.",

keywords = "Cloud Computing, Persistent Memory, Scalability",

author = "Safdar Jamil and Awais Khan and Bernd Burastaller and Youngjae Kim",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 2nd IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021 ; Conference date: 27-09-2021 Through 01-10-2021",

year = "2021",

doi = "10.1109/ACSOS-C52956.2021.00022",

language = "English",

series = "Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "44--49",

editor = "Esam El-Araby and Vana Kalogeraki and Danilo Pianini and Frederic Lassabe and Barry Porter and Sona Ghahremani and Ingrid Nunes and Mohamed Bakhouya and Sven Tomforde",

booktitle = "Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021",

}

Jamil, S, Khan, A, Burastaller, B & Kim, Y 2021, Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments. in E El-Araby, V Kalogeraki, D Pianini, F Lassabe, B Porter, S Ghahremani, I Nunes, M Bakhouya & S Tomforde (eds), Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021. Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021, Institute of Electrical and Electronics Engineers Inc., pp. 44-49, 2nd IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021, Virtual, Washington, United States, 09/27/21. https://doi.org/10.1109/ACSOS-C52956.2021.00022

Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments. / Jamil, Safdar; Khan, Awais; Burastaller, Bernd et al.
Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021. ed. / Esam El-Araby; Vana Kalogeraki; Danilo Pianini; Frederic Lassabe; Barry Porter; Sona Ghahremani; Ingrid Nunes; Mohamed Bakhouya; Sven Tomforde. Institute of Electrical and Electronics Engineers Inc., 2021. p. 44-49 (Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments

AU - Jamil, Safdar

AU - Khan, Awais

AU - Burastaller, Bernd

AU - Kim, Youngjae

PY - 2021

Y1 - 2021

N2 - The emergence of manycore machines with Intel DC Persistent Memory (DCPM) aims to provide high performance and scalability with persistence guarantees. Thus, it is required to offer opportunities to port DRAM-based index data structures to DCPM to fully exploit the performance of these machines. Fast Fair (FF) is the state-of-the-art concurrent variant of the B+ -tree for DCPM. However, its adoption on manycore machines suffers from scalability limitations due to lengthy, lock-based synchronization including structure modification operations (SMOs). In this work, we propose F3 -tree, a concurrent, persistent future-based B+-tree that shows superior scalability on DCPMs. F3 -tree design relies on thread-local future objects and a global B+ -tree. We employ an in-memory hash table to mitigate the read overhead for the key searches in thread-local future objects. We implemented the proposed ideas atop F F and performed experiments on Linux (kernel v5.4.0) using both synthetic and real-world workloads. We evaluated F3 -tree with F F and the results show that F3 -tree outperforms F F by 3.4x on average for sequential, random, and mixed workloads.

AB - The emergence of manycore machines with Intel DC Persistent Memory (DCPM) aims to provide high performance and scalability with persistence guarantees. Thus, it is required to offer opportunities to port DRAM-based index data structures to DCPM to fully exploit the performance of these machines. Fast Fair (FF) is the state-of-the-art concurrent variant of the B+ -tree for DCPM. However, its adoption on manycore machines suffers from scalability limitations due to lengthy, lock-based synchronization including structure modification operations (SMOs). In this work, we propose F3 -tree, a concurrent, persistent future-based B+-tree that shows superior scalability on DCPMs. F3 -tree design relies on thread-local future objects and a global B+ -tree. We employ an in-memory hash table to mitigate the read overhead for the key searches in thread-local future objects. We implemented the proposed ideas atop F F and performed experiments on Linux (kernel v5.4.0) using both synthetic and real-world workloads. We evaluated F3 -tree with F F and the results show that F3 -tree outperforms F F by 3.4x on average for sequential, random, and mixed workloads.

KW - Cloud Computing

KW - Persistent Memory

KW - Scalability

UR - http://www.scopus.com/inward/record.url?scp=85123442091&partnerID=8YFLogxK

U2 - 10.1109/ACSOS-C52956.2021.00022

DO - 10.1109/ACSOS-C52956.2021.00022

M3 - Conference contribution

AN - SCOPUS:85123442091

T3 - Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021

SP - 44

EP - 49

BT - Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021

A2 - El-Araby, Esam

A2 - Kalogeraki, Vana

A2 - Pianini, Danilo

A2 - Lassabe, Frederic

A2 - Porter, Barry

A2 - Ghahremani, Sona

A2 - Nunes, Ingrid

A2 - Bakhouya, Mohamed

A2 - Tomforde, Sven

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2nd IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021

Y2 - 27 September 2021 through 1 October 2021

ER -

Jamil S, Khan A, Burastaller B, Kim Y. Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments. In El-Araby E, Kalogeraki V, Pianini D, Lassabe F, Porter B, Ghahremani S, Nunes I, Bakhouya M, Tomforde S, editors, Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021. Institute of Electrical and Electronics Engineers Inc. 2021. p. 44-49. (Proceedings - 2021 IEEE International Conference on Autonomic Computing and Self-Organizing Systems Companion, ACSOS-C 2021). doi: 10.1109/ACSOS-C52956.2021.00022

Towards Scalable Manycore-Aware Persistent B+- Trees for Efficient Indexing in Cloud Environments

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this