Efficient FTL-Aware Data Categorization and Identification Scheme for Flash Memory

Hot data identification in flash memory is of great interest because it significantly affects the garbage collection and wear-leveling performance. Presently, certain hot and cold data classification schemes based on Bloom filters (BFs) have been proposed. Although BFs are efficient in most cases, there is a significant trade-off between false positive rates, which are the result of hash value collisions and memory utilization. In this paper, we suggest a better data categorization mechanism that is based on a hashing technique called Fingerprinting by Random Polynomials with the aim of reducing false positive rates and achieving lower memory consumption compared to the BF-based schemes. We also introduce a new methodology for classifying write requests by linking the definition of hot and cold write requests to the flash memory software layer, the flash translation layer (FTL) characteristics. Our approach improves space utilization by representing each logical block number (lbn) by one counter in the hash table, and achieves an extremely low error rate by choosing the degree of the hash function based on the address space of the flash memory. In addition, we achieved lower false identification rates. We demonstrate the performance using mathematical analysis and trace-driven simulation.