A road named NoNameUno

Flash memory technology is now getting to a state that hard disk secondary storage for lots of devices becoming a defacto standard. One of the main reason is speed due to lack of seek time. Yeah there is no rotating disks. Another is reliablity. So as of 2011/2012 we see lot of devices that are using SSD made of Flash memory. Solid state disk (SSD) is becoming very popular every day.

From the systems point of view, one of the interesting feature of SSD is that it can have multiple I/Os concurrently depending on the packaging and FLT(flash translation layer). And this opens up a relatively new ways of building systems. In particular, file systems, host device drivers, and flash firmware designs became very hot as well as very sohphisticated.

Traditionally, Filesystems were designed with HDD ( hard disk drive) in mind, and lot of them are not necessarily well performing file systems for SSD based storage media. Some of the old file systems are supported by providing host device driver and flash firmware that takes care of the underlying mechanics of FLASH somewhat.

So for the systems designer/programmer, understanding the underlying attributes and applying the necessary technological alternatives are very challeging. In a following series of notes I will try to encompass or rather chalkout some of the pros and cons of HDD based storage subsystem. Then will try to introduce the main design alternatives being considered for file systems.

Traditional File Systems (FS) were to give a representation of the sectors of an HDD in a structured and intutive way. Structured meaning, from the users point of view, we only need to understand directories, and files in an hierchachical fashion. And it is intuitive, since we know the office/home cabinet and filing systems. Then to avoid excessive file corruptions, log structured file systems became popular. Log sturctured file systems writes a log about a transaction, before committing the data into the physical storage that backs up the file system. The idea behind this is to ALL or NOTHING paradigm. Loosly speaking a transaction may involve (a) metadata change(s); (b) commiting the data into the backing storage. So to avoid excessive incoherent user data, ALL or NOTHING paradigm became essential.

If the system fails after committing the log, but before committing the actual data, then log file could be used to recover the transaction and commit the data. In that case ALL state for that transaction can be achieved. But if the failure occurs while it is committing the log, it can always go back to NOTHING. So retry the transaction again from the start, if possible.

Now it is only interesting to keep only the last few ( few is relative word here), log file does not need to continuously grow. Hence log file is usually circular in nature, meaning old records are erased.

For SSDs, they are mostly NAND base. And NAND has random access ability, so it is different from HDD in terms of seek time, latency etc. Also flash memory uses out-of-place writes. Meaning that an old valid data can not be over written. It has to be written to an yet fresh write location. So the mapping of virtual to physical sectors changes all the time. As an example, if we write some data to a sector once, we can not use that sector before erasing that block and make the bits to 1 for that sector. When a sector has all the bits set to 1, it is a write-once state, then once data is written, we can not over-write without erasing that sector. So every once in a while, someone or something has to move the good data of a sector to a different place, then erase the sector. Flash uses block erase, where a block consist of one or more sectors. This is one reason that random write could slow down the performance. Not because of the read access becomes slower, but because the underlying systems needs to garbage collect by erasing and compacting valid data into blocks of NAND storage.

These and other attributes opens up lot of alternative approaches to system design and underlying software techniques. For example, lot of data stuctures now have interesting applications for these systems, and Log structured file systems(LSFS) are becoming bit more practical and important.

An LSFS is purely based on log structure, meaning the whole file system is based on LOG. 

Finally I will try to emphasize some of the analytical methods and associated data structures that are suitable for SSD based I/O subsystems.