## 4 Asymmetric Programming: A Reliability Enhancement Scheme for Metadata
### Metadata Identification  
Metadata such as file system metadata are normally stored in predefined locations with fixed logical addresses. This characteristic helps us identify the metadata and enhances the reliability of flash. Among the metadata, the file system metadata contributes to the major amount of read and write accesses. File systems normally format the disk and write logical formatting information needed by the file system  
Figure 4: System architecture of Asymmetric Programming.  
onto the disk. File system metadata, such as file allocation table and the root folder, must be stored in a fixed location so that the files needed to start the system can be correctly located.  
In modern file systems, such as NTFS, every sector on an NTFS volume that is allocated belongs to some file. The file system metadata is also part of a file. Figure 5 illustrates the layout of an NTFS volume when formatting has finished. The first file on an NTFS volume is the Master File Table (MFT), which contains a set of files maintaining the metadata used to implement the file system structure. In NTFS, the location of MFT is fixed. The NTFS file system reserves the first 16 records in the MFT for the information about these metadata files. The NTFS file system uses about 1 MB for the metadata files and the first 16 records in the MFT.  
Besides the file system metadata, the metadata for wear-leveling are used to maintain the block erase counts and to select a victim block for garbage collection in NAND flash memory. Current wear-leveling algorithms normally use heuristics such as priority queue to find the victim block that has the minimum erase counts or has the lowest block utilization. The implementation of these wear-leveling algorithms needs to maintain metadata at the per block level.  
NAND flash memory storage also needs to maintain the address mapping table to track the mapping between logical addresses and physical addresses. When writing data into NAND flash memory, the address mapping table will be updated in the RAM and synchronized to NAND flash memory periodically. The tree-like data structure (e.g., B+ tree) has been widely adopted in the FTL schemes to manage the address mapping table. For the tree data structure, the more random writes are, the more indexing nodes have to be updated in the in-memory data structure (e.g., on-flash index in UBIFS). Since the on-chip RAM only has very limited capacity, the metadata stored in RAM has to be frequently flushed from volatile cache to NAND flash memory, which could cause frequent metadata synchronization.  
To fully utilize the limited RAM space and improve the write performance, many FTL schemes adopt the demand-based strategy. In demand-based FTL schemes, several physical blocks (called translation blocks) are used to hold the address mapping information that could not be stored in RAM. When running out of translation blocks, the valid pages in translation blocks have to be merged. The victim block that contains all invalid data will be erased. If multiple valid pages are distributed to different translation blocks, this case will trigger many consecutive garbage collection operations. Therefore, the more random the writes are, the more merge operations are triggered. Then the amount of metadata for address mappings is determined by the specific FTL design.  
From the above analysis, we found that the logical requests (_i.e._, logical page numbers) for metadata will be different from those for normal data. They are handled by either file systems or the dedicated FTL schemes. The logical locations that store the metadata have the natural isolations from those of the normal data. File systems or FTL schemes could further manipulate the logical to physical mappings  
Figure 5: The layout of the NTFS volume.  
and issue the read or write requests to different physical locations. Therefore, we can utilize this feature and provide extra protections for metadata stored in NAND flash memory. This can significantly enhance the reliability of NAND flash memory storage systems.