clfB-tree: Cacheline Friendly Persistent B-tree for NVRAM

Citation data:

ACM Transactions on Storage, ISSN: 1553-3077, Vol: 14, Issue: 1, Page: 1-17

Publication Year:
Captures 4
Readers 4
Repository URL:
Kim, Wook-Hee; Seo, Jihye; Kim, Jinwoong; Nam, Beomseok
Association for Computing Machinery (ACM)
Computer Science; Non-volatile memory; data structure; persistent indexing
article description
Emerging byte-addressable non-volatile memory (NVRAM) is expected to replace block device storages as an alternative low-latency persistent storage device. If NVRAM is used as a persistent storage device, a cache line instead of a disk page will be the unit of data transfer, consistency, and durability. In this work, we design and develop clfB-tree—a B-tree structure whose tree node fits in a single cache line. We employ existing write combining store buffer and restricted transactional memory to provide a failure-atomic cache line write operation. Using the failure-atomic cache line write operations, we atomically update a clfB-tree node via a single cache line flush instruction without major changes in hardware. However, there exist many processors that do not provide SW interface for transactional memory. For those processors, our proposed clfB-tree achieves atomicity and consistency via in-place update, which requires maximum four cache line flushes. We evaluate the performance of clfB-tree on an NVRAM emulation board with ARM Cortex A-9 processor and a workstation that has Intel Xeon E7-4809 v3 processor. Our experimental results show clfB-tree outperforms wB-tree and CDDS B-tree by a large margin in terms of both insertion and search performance.