Solid State Drive Targeted Memory-Efficient Indexing for Universal I/O Patterns and Fragmentation Degrees

Thanks to the advance of device scaling technologies, the capacity of SSDs is rapidly increasing. Such increase, however, comes at the cost of a huge index table requiring large DRAM. To provide reasonable performance with less DRAM, various index structures exploiting locality and regularity of I/O references have been proposed. However, they provide deteriorated performance depending on I/O patterns and storage fragmentation. This paper proposes a novel approximate index structure, called AppL, which combines memory-efficient approximate indices and an LSM-tree that has an append-only and sorted nature. AppL reduces the index size to 6-8-bits per entry, which is considerably smaller than the typical index structures requiring 32-64-bits, and maintains such high memory efficiency irrespective of locality and fragmentation. By alleviating memory pressure, AppL achieves 33.6-72.4% shorter read latency and 28.4%-83.4% higher I/O throughput than state-of-the-art techniques.