Managing Flash Memory
Dynamic Random Access Memory (DRAM): stores each bit of data in separate capacitor within integrated circuit, volatile.
Flash Translation Layer (FTL)
Want to write file systems to take advantage of flash layer. Currently FAT style file system.
Direct mapped approach for FTLs: * Virtual block i is stored on page i of flash disk * Reads are simple * To write: * Read erase unit containing page i * Erase entire unit * Rewrite erased unit with modified page * Whats wrong? Some information is accessed more frequency than others, too slow.
Need to allow virtual block to occupy different pages in flash memory over time. We don't want to erase for every write operation. Just write to clean parts of memory. To do this, keep a block map (kind of like a page table) of virtual blocks to physical pages. * Read: lookup physical location on block map. * Write: * Find empty page * Write virtual block to page * Update block map with new location * Mark previous page as free
* Issues: * Managing the block map * Managing free space
Approach 1: keep block map in memory, rebuild on startup. * Don't store block map on flash device * Each page on flash contains additional header: * Virtual block number * Allocated bit (free = 1) * Written bit (written = 0) * Obsolete bit (no longer in use = 0) * A-W-O bits track page lifecycle * Just erased: 1-1-1 * About to write data: 0-1-1 // It's been allocated, no longer free * Block written: 0-0-1 // written * Block deleted: 0-0-0 // set obsolete since this has been written elsewhere * Why need 0-1-1 state?
FTL will cache part of the block map, store the rest of it in flash device, results in another level of indirection -- block map map.
## Garbage Collection * As long as we have empty page sitting on the device, Approach 1 is fine. * Wait as long as possible to garbage collect * Find erase units with many free pages * Copy live pages to a clean erase unit (update block map) * Erase and reuse old erase unit * Need to keep always at least one clean erase unity for garbage collection. * Write amplification: high utilization results in higher write cost. * If flash device is 90% utilized, must garbage collect 10 old erase units in order to get space for 1 erase unit. --Why? * Lower utilization makes writes cheaper, wastes space.
Ideal Sitation: separate hot and cold data * Have some erase units contain data that is never modified--always full, never garbage collected. * Hot data -- just wait till all of it has been overwritten then reuse it.
## Wear-leveing * Want all erased units to be erased at about the same rate * Basically use garbage collection to move data between hot and cold pages. Isolate cold data for better performance, but move cold data around to get more even wear.
### Incorporating flash memory into file system We have a lot of duplication--file system has block map already. We wish we could manage flash directly, so to combine block map with file indexes. Information lack * FTL doesn't know when OS has freed a block. Only finds out when overwritten. * FTL may rewrite dead blocks during garbage collection. * Trim command: OS can tell FTL at block X has been freed.
## Long Term Goals Design file systems for flash memory. We want direct access to erase units.
References:
http://codecapsule.com/2014/02/12/coding-for-ssds-part-3-pages-blocks-and-the-flash-translation-layer/ http://flashdba.com/2014/09/17/understanding-flash-the-flash-translation-layer/