ReLoaDing Performance: A Locality-Based Strategy for Rapid Reads in Encrypted Key-Value Systems

In key-value store systems, data security is often prioritized through compression and encryption of stored key-value pairs, ensuring protection against unauthorized access and breaches. However, these security measures introduce significant performance overheads, particularly during read operations, due to the need for decryption and decompression of data packs. This overhead is exacerbated in log-structured merge-tree (LSM-tree) based systems interfaced with NAND flash memory, where read amplification—caused by accessing entire compressed and encrypted units for a small subset of data—degrades performance. To address this challenge, we propose ReLoaD (Repacking Locality Data), a novel locality-based strategy designed to optimize read performance in encrypted key-value systems without compromising security or compression efficiency. ReLoaD leverages dynamic access pattern analysis to reorganize frequently co-accessed key-value pairs into contiguous storage packs, reducing the frequency of costly decryption and decompression operations. By introducing lightweight in-memory data structures—such as the PackInfo and Remapthl mapping tables—and innovative mechanisms like the locality-aware compactor and reloading repacker, ReLoaD enhances data locality within packs, minimizes I/O overhead, and increases the pack read ratio. Experimental evaluations using real-world workloads from X (formerly known as Twitter) and IBM, executed on the RocksDB platform, demonstrate that ReLoaD achieves up to a 38% improvement in read latency compared to state-of-the-art solutions like TinyEnc, while maintaining minimal impact on write performance. With a memory footprint of less than 3 MB, ReLoaD offers a scalable and practical approach to balancing security and performance, making it well-suited for modern secure storage systems deployed in resource-constrained environments.