EMT: Elegantly Measured Tanner for Key-Value Store on SSD

• Published in: IEEE transactions on computer-aided design of integrated circuits and systems 2022-01, Vol.41 (1), p.91-103
• Main Authors: Chang, Tai, Hsieh, Jen-Wei, Chang, Tai-Chieh, Lai, Liang-Wei
• Format: Article
• Language: English
• Subjects: Amplification; Data base management systems; Data storage; Flash memory (computers); Fragmentation; Key-value store; Memory management; Metadata; NAND flash; Performance evaluation; Protocols; Relational data bases; Relational databases; Resource management; Solid state devices; solid state drive (SSD); Solid state drives
• ISSN: 0278-0070; 1937-4151
• DOI: 10.1109/TCAD.2021.3055489

With the emergence of big data era, NoSQL key-value database is considered as a promising candidate for replacing relational database management system (RDBMS). As cost per GB of flash memory is getting closer to HDD, high performance solid state drive (SSD) is regarded as the best substitute of HDD. However, there are still some issues that need to be taken into consideration. et al. have reported that applying key-value store to SSD with conventional FTL would incur internal fragmentation and further cause the degradation of device lifespan. Although they proposed KVFTL to deal with the above issues, their work gave rise to the read amplification problem. In this article, we investigate the root cause of the read amplification problem and propose elegantly measured tanner FTL (EMT-FTL) to mitigate internal fragmentation and read amplification with acceptable memory overhead. Different from KVFTL that slices a variable-sized value into multiple partitions (up to 20) of different sizes and manages them as a linked chain, EMT-FTL slices a value into 16 KiB full partitions with its remaining bytes treated as a fragment partition and appended to the fragment buffer. For a 64 GiB SSD with 16 KiB pages, the overall memory usage of EMT-FTL is only 8.81% of KVFTL. The experiments showed that EMT-FTL achieved almost the optimal space utilization as KVFTL did under most of traces and averagely improved the get performance by 78.57% (compared with KVFTL) under the traces with request sizes ranging from 1 byte to 16 KiB.