A Log-Structured Merge Tree-aware Message Authentication Scheme for Persistent Key-Value Stores


Igjae Kim, UNIST, KAIST; J. Hyun Kim, Minu Chung, Hyungon Moon, and Sam H. Noh, UNIST


Persistent key-value stores (KVSs) are fundamental building blocks of modern software products. A KVS stores persistent states for the products in the form of objects associated with their keys. Confidential computing (e.g., Intel Software Guard Extensions (SGX)) can help KVS protect data from unwanted leaks or manipulation if the KVS is adapted to use the protected memory efficiently. The characteristics of KVSs accommodating a large volume of data amplify one of the well-known performance bottlenecks of SGX, the limited size of the protected memory. An existing mechanism, Speicher, applied common techniques to overcome this. However, its design decision does not scale because the required protected memory size increases rapidly as the KVS receives additional data, resulting from the design choice to hide the long latency of Merkle tree-based freshness verification. We find that the unique characteristics of the log-structured merge (LSM) tree, a data structure that most popular persistent KVSs have, help reduce the high cost of protected memory consumption. We design TWEEZER on top of this observation by extending RocksDB, one of the most popular open-source persistent KVSs. We compare the performance of TWEEZER with the reproduced version of Speicher. Our evaluation using the standard db_bench reveals that TWEEZER outperforms Speicher by 1.94~6.23x resulting in a reduction of slowdown due to confidential computing from 16~30x to 4~9x.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

This content is available to:

@inproceedings {277820,
author = {Igjae Kim and J. Hyun Kim and Minu Chung and HyunGon Moon and Sam H. Noh},
title = {A {Log-Structured} Merge Tree-aware Message Authentication Scheme for Persistent {Key-Value} Stores},
booktitle = {20th USENIX Conference on File and Storage Technologies (FAST 22)},
year = {2022},
isbn = {978-1-939133-26-7},
address = {Santa Clara, CA},
pages = {363--380},
url = {https://www.usenix.org/conference/fast22/presentation/kim-igjae},
publisher = {USENIX Association},
month = feb,

Presentation Video