R&D: Probability-Based Address Translation for Flash SSDs

IEEE Computer Architecture Letters, Preprints has published an article written by Junsu Im, Hanbyeol Kim, Yumin Won, Jiho Oh, Minjae Kim, and Sungjin Lee, ICE, Daegu Gyeongbuk Gwahak Gisul Won Daehakwon, 236423 Daegu, Dalseong-gun, Korea.

Abstract: “Thanks to the advance of NAND scaling technologies, an ultra-scale SSD (e.g., > 100TB) is introduced to markets these days. This rapid increase of SSD capacity, however, comes at the cost of more DRAM for logical-to-physical (L2P) address translation. Many have proposed various address translation algorithms to reduce DRAM, but they fail to provide short read latency, in particular when a workload has weak locality. This paper proposes a novel probability-based address translation algorithm, called BloomFTL. In contrast to existing translation techniques that maintain exact L2P mapping, BloomFTL employs a probability-based data structure, a bloom filter, for address translation. By leveraging a space-efficient nature of a bloom filter, BloomFTL reduces the amount of DRAM for address translation to 20% of the existing techniques. The read latency of BloomFTL is not affected from locality of a workload; BloomFTL guarantees a read amplification factor of 1.1 even under a random read workload. BloomFTL exhibits slightly worse garbage collection efficiency, but its write amplification factor is maintained sufficiently low.“