Probability-based Address Translation for Flash SSDs

Abstract

Thanks to the advance of NAND scaling technologies, an ultra-scale SSD (e.g., >> 100 TB) is introduced to markets. This rapid increase of SSD capacity, however, comes at the cost of more DRAM which resides in an SSD controller 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 letter proposes a novel probability-based address translation algorithm, called ProbFTL. In contrast to existing translation techniques that maintain exact L2P mapping, ProbFTL employs a probability-based data structure, a bloom filter, for address translation. By leveraging a space-efficient nature of a bloom filter, ProbFTL reduces the amount of DRAM for address translation to 20 percent of the existing techniques. The read latency of ProbFTL is not affected from locality of a workload; ProbFTL guarantees a read amplification factor of 1.1 even under a random read workload. ProbFTL exhibits slightly worse garbage collection efficiency, but its write amplification factor is maintained sufficiently low.