System Software for Flash Memory: A Survey
---
paper_title: A flash-memory based file system

paper_content:

A flash memory device driver that supports a conventional UNIX file system transparently was designed. To avoid the limitations due to flash memory's restricted number of write cycles and its inability to be overwritten, this driver writes data to the flash memory system sequentially as a Log-structured File System (LFS) does and uses a cleaner to collect valid data blocks and reclaim invalid ones by erasing the corresponding flash memory regions. Measurements showed that the overhead of the cleaner has little effect on the performance of the prototype when utilization is low but that the effect becomes critical as the utilization gets higher, reducing the random write throughput from 222 Kbytes/s at 30% utilization to 40 Kbytes/s at 90% utilization. The performance of the prototype in the Andrew Benchmark test is roughly equivalent to that of the 4.4BSD Pageable Memory based File System (MFS).
---
paper_title: eNVy: a non-volatile, main memory storage system

paper_content:

This paper describes the architecture of eNVy, a large non-volatile main memory storage system built primarily with Flash memory. eNVy presents its storage space as a linear, memory mapped array rather than as an emulated disk in order to provide an efficient and easy to use software interface. Flash memories provide persistent storage with solid-state memory access times at a lower cost than other solid-state technologies. However, they have a number of drawbacks. Flash chips are write-once, bulk-erase devices whose contents cannot be updated in-place. They also suffer from slow program times and a limit on the number of program/erase cycles. eNVy uses a copy-on-write scheme, page remapping, a small amount of battery backed SRAM, and high bandwidth parallel data transfers to provide low latency, in-place update semantics. A cleaning algorithm optimized for large Flash arrays is used to reclaim space. The algorithm is designed to evenly wear the array, thereby extending its lifetime. Software simulations of a 2 gigabyte eNVy system show that it can support I/O rates corresponding to approximately 30,000 transactions per second on the TPC-A database benchmark. Despite the added work done to overcome the deficiencies associated with Flash memories, average latencies to the storage system are as low as 180ns for reads and 200ns for writes. The estimated lifetime of this type of storage system is in the 10 year range when exposed to a workload of 10,000 transactions per second.
---
paper_title: Algorithms and data structures for flash memories

paper_content:

Flash memory is a type of electrically-erasable programmable read-only memory (EEPROM). Because flash memories are nonvolatile and relatively dense, they are now used to store files and other persistent objects in handheld computers, mobile phones, digital cameras, portable music players, and many other computer systems in which magnetic disks are inappropriate. Flash, like earlier EEPROM devices, suffers from two limitations. First, bits can only be cleared by erasing a large block of memory. Second, each block can only sustain a limited number of erasures, after which it can no longer reliably store data. Due to these limitations, sophisticated data structures and algorithms are required to effectively use flash memories. These algorithms and data structures support efficient not-in-place updates of data, reduce the number of erasures, and level the wear of the blocks in the device. This survey presents these algorithms and data structures, many of which have only been described in patents until now.
---

Title: System Software for Flash Memory: A Survey

Section 1: Introduction
Description 1: Introduce the significance of flash memory and the necessity of specialized system software like FTL due to its inherent characteristics.

Section 2: Problem Definition
Description 2: Define the problem in managing flash memory, focusing on the logical to physical address mapping and the constraints of read, write, and erase operations.

Section 3: FTL Functionalities
Description 3: Describe the essential functions of an FTL algorithm including address mapping, power-off recovery, and wear-leveling.

Section 4: A Taxonomy for FTL Algorithms
Description 4: Suggest a classification system for FTL algorithms based on different features such as addressing mapping, mapping information management, and SRAM table size.

Section 5: Addressing Mapping
Description 5: Provide detailed descriptions of different address mapping techniques including sector mapping, block mapping, and hybrid mapping along with their pros and cons.

Section 6: Managing Address Mapping Information
Description 6: Explain methods for storing address mapping information in flash memory, discussing both map block methods and per block methods.

Section 7: RAM Table
Description 7: Highlight the importance of RAM size in designing FTL algorithms and the various types of information stored in RAM.

Section 8: Performance Results
Description 8: Present and discuss the performance results of different FTL algorithms based on their implementation and testing under various workloads.

Section 9: Conclusion
Description 9: Summarize the survey findings, including the classifications, performance comparisons, and future research directions for FTL algorithms.