CAWBT: NVM-Based B+Tree Index Structure Using Cache Line Sized Atomic Write

Dokeun LEE; Seongjin LEE; Youjip WON

doi:10.1587/transinf.2019EDP7034

CAWBT: NVM-Based B+Tree Index Structure Using Cache Line Sized Atomic Write

Dokeun LEE, Seongjin LEE, Youjip WON

Full Text Views

0

Cite this

Summary :

Indexing is one of the fields where the non-volatile memory (NVM) has the advantages of byte-addressable characteristics and fast read/write speed. The existing index structures for NVM have been developed based on the fact that the size of cache line and the atomicity guarantee unit of NVM are different and they tried to overcome the weakness of consistency from the difference. To overcome the weakness, an expensive flush operation is required which results in a lower performance than a basic B+tree index. Recent studies have shown that the I/O units of the NVM can be matched with the atomicity guarantee units under limited circumstances. In this paper, we propose a Cache line sized Atomic Write B+tree (CAWBT), which is a minimal B+tree structure that shows higher performance than a basic b+ tree and designed for NVM. CAWBT has almost same performance compared to basic B+tree without consistency guarantee and shows remarkable performance improvement compared to other B+tree indexes for NVM.

Publication: IEICE TRANSACTIONS on Information Vol.E102-D No.12 pp.2441-2450

Publication Date: 2019/12/01

Publicized: 2019/09/12

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2019EDP7034

Type of Manuscript: PAPER

Category: Software System

Authors

Dokeun LEE
  Hanyang University
Seongjin LEE
  Gyeongsang National University
Youjip WON
  KAIST

Keyword

non-volatile memory, key-value store, index structure, B+tree

Cite this

Copy

Dokeun LEE, Seongjin LEE, Youjip WON, "CAWBT: NVM-Based B+Tree Index Structure Using Cache Line Sized Atomic Write" in IEICE TRANSACTIONS on Information, vol. E102-D, no. 12, pp. 2441-2450, December 2019, doi: 10.1587/transinf.2019EDP7034.
Abstract: Indexing is one of the fields where the non-volatile memory (NVM) has the advantages of byte-addressable characteristics and fast read/write speed. The existing index structures for NVM have been developed based on the fact that the size of cache line and the atomicity guarantee unit of NVM are different and they tried to overcome the weakness of consistency from the difference. To overcome the weakness, an expensive flush operation is required which results in a lower performance than a basic B+tree index. Recent studies have shown that the I/O units of the NVM can be matched with the atomicity guarantee units under limited circumstances. In this paper, we propose a Cache line sized Atomic Write B+tree (CAWBT), which is a minimal B+tree structure that shows higher performance than a basic b+ tree and designed for NVM. CAWBT has almost same performance compared to basic B+tree without consistency guarantee and shows remarkable performance improvement compared to other B+tree indexes for NVM.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019EDP7034/_p

Copy

@ARTICLE{e102-d_12_2441,
author={Dokeun LEE, Seongjin LEE, Youjip WON, },
journal={IEICE TRANSACTIONS on Information},
title={CAWBT: NVM-Based B+Tree Index Structure Using Cache Line Sized Atomic Write},
year={2019},
volume={E102-D},
number={12},
pages={2441-2450},
abstract={Indexing is one of the fields where the non-volatile memory (NVM) has the advantages of byte-addressable characteristics and fast read/write speed. The existing index structures for NVM have been developed based on the fact that the size of cache line and the atomicity guarantee unit of NVM are different and they tried to overcome the weakness of consistency from the difference. To overcome the weakness, an expensive flush operation is required which results in a lower performance than a basic B+tree index. Recent studies have shown that the I/O units of the NVM can be matched with the atomicity guarantee units under limited circumstances. In this paper, we propose a Cache line sized Atomic Write B+tree (CAWBT), which is a minimal B+tree structure that shows higher performance than a basic b+ tree and designed for NVM. CAWBT has almost same performance compared to basic B+tree without consistency guarantee and shows remarkable performance improvement compared to other B+tree indexes for NVM.},
keywords={},
doi={10.1587/transinf.2019EDP7034},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - CAWBT: NVM-Based B+Tree Index Structure Using Cache Line Sized Atomic Write
T2 - IEICE TRANSACTIONS on Information
SP - 2441
EP - 2450
AU - Dokeun LEE
AU - Seongjin LEE
AU - Youjip WON
PY - 2019
DO - 10.1587/transinf.2019EDP7034
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2019
AB - Indexing is one of the fields where the non-volatile memory (NVM) has the advantages of byte-addressable characteristics and fast read/write speed. The existing index structures for NVM have been developed based on the fact that the size of cache line and the atomicity guarantee unit of NVM are different and they tried to overcome the weakness of consistency from the difference. To overcome the weakness, an expensive flush operation is required which results in a lower performance than a basic B+tree index. Recent studies have shown that the I/O units of the NVM can be matched with the atomicity guarantee units under limited circumstances. In this paper, we propose a Cache line sized Atomic Write B+tree (CAWBT), which is a minimal B+tree structure that shows higher performance than a basic b+ tree and designed for NVM. CAWBT has almost same performance compared to basic B+tree without consistency guarantee and shows remarkable performance improvement compared to other B+tree indexes for NVM.
ER -