Flash file systems primer
Background & basics
What is a Flash File System?
A Flash File System stores data on flash memory, rather than a hard drive. Flash is used because it’s faster, much more tolerant of physical stress and takes less power. A flash filesystem is used to manage the data and get the best out of flash memory.
As two examples, a flash memory chip needs to be erased in blocks before it is rewritten and a flash file system will manage that; flash memory has a limited number of writes per block so many flash file systems incorporate a wear levelling mechanism to ensure the writes are spread out.
A flash file system is most useful as a part of an embedded system,. As a developer, you can read from and write directly to your Flash memory on an embedded system, but unless your use is extremely limited, you'll probably find that you come up against problems that Flash file systems have already solved.
What are NAND flash & NOR flash?
These are the two fundamental flash architectures and have very different characteristics in performance, reliability, erase cycles, life span, and price. They also differ fundamentally from hard disk drives, and so need specialised handling.
|
NAND flash
|
NOR flash
|
Storage density
|
Higher
|
Lower
|
Read performance
|
Fast
|
Fast (may be slowed by serial access)
|
Write performance
|
Faster
|
Slower (may be slowed further by serial access)
|
Erase performance
|
Faster (low ms typically)
|
Slower (possibly seconds)
|
Storage reliability
|
Lower (without management)
|
Better
|
Life span
|
Higher
|
Lower
|
Price
|
Lower
|
Higher
|
Yaffs is both an embedded NAND flash file system and an embedded NOR Flash file system. It can handle SLC, TLC and MLC NAND. It also works on MLC and SLC NOR. And it can work with parallel or serial access including Serial Peripheral Bus (SPI).
What special functions does a file system for flash include?
As well as the normal file system functions, a flash file system embedded in hardware should help the device to start and stop quickly and deal well with losing power with no warning, without corrupting the data; and, manage the foibles of flash memory, protecting the stored data with extreme reliability. (Read our paper Considerations in Choosing a Flash File System.)
To these ends, an embedded flash file system must employ extra steps to achieve these such as using log structuring, rather than traditional file structuring plus a flash translation layer; manage power loss and recovery; include flash memory wear levelling; deal with the unreliability of flash from read and write disturbs, by using error correction (ECC), bad block remapping, over provision and flash block refreshing; ensure it’s ready to write fast by using garbage collection and flash block erase to prepare; and manage writing while avoiding write amplification.
What is a log-structured file system?
Log structuring means that data is written to the file system as a sequence of changes to the file system. This has the advantage that there is less overhead, and so it's faster than a non-log-structured system. More important though is that it is more robust against power failure. It also means that a file may be fragmented. For hard drives, fragmentation can mean much slower access due to the time required to mechanically move the read heads around the disk, but flash memory has no moving parts so there is no overhead for flash.
Yaffs is log structured a flash file system architecture which is faster and more robust than the alternatives.
What is a Flash Translation Layer (FTL) ?
It is sometimes desirable to use regular block file systems (such as FAT) with flash memory. In such cases, a Flash Translation Layer presents flash memory or a flash file system as if it's an ordinary hard drive.
An FTL is an incomplete storage solution it still requires a file system. This makes two layers where data can be damaged and lost: in the FTL and in the flash memory file system.
True file systems for flash memory, such as Yaffs, do not use FTLs. They deal directly with the idiosyncrasies of flash, providing a faster and more reliable solution.
What is power loss recovery?
When power to any storage device is suddenly lost, the device can end up in an unknown state and may have damaged areas. Most file systems have to work hard to ensure that they are in a consistent state after power loss. Embedded file systems for flash may make allowances for unscheduled power loss with a recovery process.
Yaffs is built with fault tolerance as a guiding principle and so is designed so power loss is considered a normal event.
What is wear levelling?
Flash chips wear out. Each time a part of the flash memory is erased and written, it is slightly damaged. Embedded flash file systems note the danger, and sometimes try to spread the damage rather than having it concentrated in one region, so prolonging the life of the memory and the life of the device.
Yaffs is designed so that extra wear leveling is unnecessary. Instead, it’s automatically wear levelling because of the log structure.
What is flash read disturb? What is flash write disturb?
NAND flash may experience degradation or loss of data owing to reads of pages in the same block or data changes in neighbouring blocks of the NAND device. This is particularly true for MLC NAND.
Yaffs uses block refreshing to deal with such problems.
What is flash error correction/flash ECC?
There are ways in which flash memory can be corrupted – for instance F-N tunnelling problems and leaky oxide layers. See our detailed discussion of flash memory problems.
But every bit counts, and especially if it's part of critical data or essential to the correct working of a system. Flash error correction keeps track of a section of memory to tell if there's corruption, and provides ways to correct these small errors.
Yaffs can use hardware or software based ECC.
What is bad-block remapping?
File systems are built upon storing data on physical media. But all media suffers deterioration. Some hardware or flash media file systems keep lists of damaged regions and behind the scenes, substitute known good ones in their place.
Because of the way that Yaffs works, there's no need for bad block remapping because it isn’t a block structured file system.
What is over-provisioning ?
Knowing that the media will degrade and suffer errors, and needing space to alter data because of the nature of flash memory, sometimes a flash memory based file system puts aside a portion of the media for this use. This is overprovisioning. Often this space used when remapping bad blocks.
Because Yaffs is log structured, it has the advantage that it does not need over provisioning, making more memory available to store data.
What is flash block refreshing?
To counteract the problems of unreliable flash memory – for instance errors due to read and write disturbs – a flash filesystem can refresh the memory, by making a new copy of a block.
Yaffs includes flash block refreshing.
What is flash garbage collection?
When a file is deleted, or a part of a file is overwritten, file systems often simply mark the flash space as deleted, rather than removing it. Later they reclaim the space for reuse. This is garbage collection.
Yaffs has garbage collection to maximise the amount of data the file system can store.
What is flash block erase?
Data must be written into blank areas of the flash chip, but erasing takes time. Rather than erase and write at the same time, in order to speed writes, NAND and NOR flash file systems can prepare blocks for later use. This is not usually necessary for other storage media.
As part of garbage collection, Yaffs uses a block erase strategy.
What is flash write amplification ?
In many block-based flash file systems, when data changes the new data must be written to the disk, and then the old data must be marked as invalid. A small change to the data can have consequences that propagate involving writing to the memory twice or more as the old data is cleaned up by garbage collection and files are organised to take the minimum amount of space. This is write amplification - a single small write causing a cascade of writes (and erases) of whole blocks.
Yaffs avoids much of this problem by being log structured, meaning that flash memory is slower to reach it's maximum number of cycles, while writing is faster.
How does Yaffs work?
You can find full details in our paper How Yaffs Works but briefly, here's how it works.
It's a log-structured filing system. This also ensures that Yaffs is wear-levelling is built into the design because no one part of the flash memory is used any more than another.
A Yaffs object is anything that Yaffs stores - for instance a file or a directory.
The memory in NAND flash is arranged in pages. A page is the unit of allocation and programming. In Yaffs, the unit of allocation is called the chunk. Typically a chunk will be the same as a NAND page, but there is flexibility to use chunks which map to multiple pages (eg. A system may have two NAND chips in parallel requiring 2x2048 = 4096 byte chunks) . This distinction gives a lot of flexibility in how the system can be configured.
A fixed but configurable number of chunks form a block which is the unit of erasure.
NAND flash is shipped with bad blocks and further blocks may go bad during the operation of the device so Yaffs detects and marks bad blocks.
NAND flash also typically requires the use of some sort of error detection and correction code (ECC). Yaffs can either use existing ECC logic or provide its own.
Yaffs maintains data in RAM about the file system, but this is not needed for Yaffs to work - so the device can safely lose power at any point without data corruption.
Here's how the Yaffs filesystem works to ensure data safety and a very fast startup... At regular points and on controlled shutdown, checkpoint blocks are written to the flash memory, containing all the data to quickly rebuild the file system. Under usual circumstances this checkpoint is used when a device is started, to very quickly rebuild the RAM data about the file system. If the checkpoint is determined to be corrupted, or if the user requested then the file system is rebuilt by scanning.
To do this, Yaffs makes a prescan, to find the sequence numbers for blocks. Then it scans through blocks backwards to build up the list of chunks that make up objects. It speeds up this process by using Block Summaries, which are collections of all the tags in a data in a block. (But it's still always possible to go back to the chunks themselves, to find the tags, if a summary is missing or damaged.)
And tags are how Yaffs tells that a chunk belongs to a particular object.
Tags are also how Yaffs knows which chunks make up the current version of an object... Because the file system is log structured, if an object has been updated, only the latest chunks are used, giving the correct version of the object. A full description of the process is available in the technical documentation, and of course you can browse the code to see exactly how it all works; there's a lot more to tags, the metadata that they can hold, how they are stored, and how tags are used to link together objects into a file system with a POSIX interface.
And of course that's not the end of the story. There's caching to deal with repeated small changes to data. There's garbage collection to let space be re-used, and Yaffs deals with collecting garbage differently depending on whether there's lots of free space or only a little. And part of making Yaffs a high performance flash file system is to make sure that re-useable blocks are erased well before they are needed, so that writing involves only a single operation. There's lazy loading to reduce scanning time. And all of this is built in a portable way, so that Yaffs can be configured to match almost any hardware, and can be ported to any operating system, or work on bare metal without an operating system. There's a test harness which is used to subject Yaffs to power failure, and ensure it works even with external data corruption. That's what makes it robust enough to send into space and to handle hundreds of terabytes of mission critical data.
Why is Yaffs special as an embedded flash file system?
Yaffs has been in use since 2002, and so it is hardened. It has been used in everything from phones to sewing machines to satellites. It is popular with Aerospace companies, and firms managing large infrastructure and in Point-of-Sale (POS) equipment (where customer feedback is very rapid!) It has been used in extreme conditions where it must not lose data, and where there is no chance for maintenance. It's been used for very large file systems up to 190TB. It's been used for safety critical applications, and millions of consumer devices.
We carry out testing in a rig which can simulate random power failures and proved its reliability after tens to hundreds of millions of power failures. It's designed with an understanding of the constraints of flash memory and for speed.
Yaffs works on multiple operating systems – Linux, VxWorks, Windows CE, eCos. - and also directly on bare metal, with no operating system. And it's easy to integrate into your RTOS or application using the Yaffs Direct Interface. It works with multiple types of flash memory - NAND & NOR, SLC, MLC & TLC. It's endian neutral. It's been used with 32-bit and 64-bit CPUs including MIPS, 68000, ARM, ColdFire, PowerPC and x86 variants. Yaffs has even been used with various DSP architectures! And it'll work with 16-bit with some tuning. So it can be configured to work with your design and the flash geometry that you need.
And it's a free embedded flash file system - it’s open source! Grab the GPL version now! Check out our the active community. And that's not the whole story - there are lots more reasons that make Yaffs special.