Uniformity improving page allocation for flash memory file systems

Flash memory is a storage medium that is becoming more and more popular. Though not yet fully embraced in traditional computing systems, Flash memory is prevalent in embedded systems, materialized as commodity appliances such as the digital camera and the MP3 player that we enjoy in our everyday lives. This paper considers an issue in file systems that use Flash memory as a storage medium and makes the following two contributions. First, we identify the cost of block cleaning as the key performance bottleneck for Flash memory analogous to the seek time in disk storage. We derive and define three performance parameters, namely, utilization, invalidity, and uniformity, from characteristics of Flash memory and present a formula for block cleaning cost based on these parameters. We show that, of these parameters, uniformity most strongly influences the cost of cleaning and that uniformity is a file system controllable parameter. This leads us to our second contribution, designing the modification-aware (MODA) page allocation scheme and analyzing how enhanced uniformity affects the block cleaning cost with various workloads. Real implementation experiments conducted on an embedded system show that the MODA scheme typically improves 20 to 30% in cleaning time compared to the traditional sequential allocation scheme that is used in YAFFS.