A Short Study on Wear Leveling
By P Keith Garvin, November 2007
Over the past fifteen years, flash memory has been widely adopted in mainstream consumer grade products having short lifetimes, often measured in months. In recent years however, flash memory has begun to break into more industrial and commercial grade devices with lifetimes counted in years. There are many unique characteristics of flash memory that have fueled its growth across these varying market segments, such as its ability to retain data without continued power; this benefit, however, comes at a cost of a finite lifetime and endurance. The hardware architecture and software technologies that extend the life of a flash chip are often ill considered or, at times, given more worry than necessary. While the limited lifetime of flash memory may or may not be problematic for products that are expected to last ten or more years, flash management software can expand the breadth of available flash parts for your project.
This paper focuses on determining when the limitations of flash memory lifetime become significant and what can be done about them.
Flash Lifetime Metrics
Flash memory lifetimes are described in two primary metrics which are generally touted on the first page of any flash memory manufacturers’ data sheets:
• Data retention
• Endurance cycles
Data retention is often listed at 20 years at a given operating temperature. Increased temperature ranges reduce the data retention period which further decrease as the flash memory is used at or near its specified operating temperatures. It is important to note that data retention is measured from the time data is successfully programmed.
The second metric, endurance cycles, is a measure of the number of write and erase cycles that the flash memory can endure before becoming unreliable. Flash memories are organized into a number of erase blocks or sectors and each must be erased prior to writing data. A typical erase block is 128KB in size, however may range from 512B to 2,048KB or even more. Any given address within an erase block cannot be rewritten without an intervening erase. Erase cycles are cumulative and affect only those erase blocks being cycled. In other words, an error in any erase block is constrained to the data of that block.
Erase cycles range from 1,000 to 1,000,000. While these ranges have an order of magnitude difference, it is the application the flash is placed into that will primarily define the product lifetime.
What is Wear-Leveling?
Wear leveling is a process to ensure that an entire flash memory device or an array of devices is used in a uniform fashion in order to extend the overall lifetime of the flash.
For a simplistic example of wear-leveling, let’s look at a data recorder device with the following characteristics:
• Application: The device collects and stores the past 24 hours of field data by simply writing and rewriting the data to the same location on the flash.
• File size of data to be recorded: 128KB
• Erase block size (of the flash): 128KB
• Flash memory endurance: 1,000 cycles
With one spare area, the device is assumed one cycle per day each year:
(1,000 cycles ÷ 365 days) * 1 spare area = 2.74 years
In this example, it would take about 2.74 years to cycle that one erase sector 1,000 times.
For the data recorder device to accommodate the write erase rules of flash memory, it would have to complete an erase operation to start writing the next day’s set of data. To make the data recorder more robust – to ensure that it doesn’t lose a whole day’s worth of data – we can set aside a second erase block, and erase the first block only after the second set of data was recorded. The resulting side effect is the introduction of a simple wear-leveling scheme.
With two spare areas, the device is assumed one cycle every two days each year:
(1,000 cycles ÷ 365 days) * 2 spare areas = 5.48 years
With these parameters, the period of time prior to cycling the flash to its lifetime has just been increased to almost 5.5 years!
This simple example shows how distributing a fixed set of writes across more flash sectors can increase the period of time prior to cycling the flash to its specified limits. The following sections describe how to account for the important variables associated with wear-leveling techniques, and determine the expected lifetime of the flash in any application.
Figures 1 and 2 below depict the concept of wear leveling. The flash disk in this example has a maximum endurance of 100,000 cycles. Figure 1 represents a disk that does not employ any wear leveling software, while Figure 2 shows a disk that is managed with wear leveling schemes. Note that the sectors that have exceeded the 100,000 cycles in Figure 1 are no longer able to store data, and have corrupted the data that they were storing. These sectors represent the high-use areas of the disk; on a FAT disk, for example, this may be where the FAT table is stored. Lower use areas of the disk, which may include application and operating system code, will never reach the flash memory’s maximum endurance. Without wear leveling, these low-use sectors are essentially wasted flash lifetime. Meanwhile, the disk use in Figure 2 is spread evenly throughout the disk sectors, allowing the flash disk to be reliable for its maximum lifetime.
Datalight FlashFX® Pro Wear leveling Implementation
FlashFX Pro, an intelligent flash driver and flash manager from Datalight, moves data around in the flash disk to accommodate the fact that flash memory cannot simply be rewritten. The specific algorithms are beyond the scope of this paper, but we can reasonably assume that FlashFX Pro will attempt to efficiently write throughout the flash before rewriting the same location. Many basic file systems have a primitive form of wear leveling.
The wear leveling scheme implemented by FlashFX Pro consists of tracking the number of erases incurred on each flash erase block. In other words, FlashFX Pro monitors the high use areas (many erases) and low use areas (few erases) of the flash; this is often referred to as dynamic wear leveling. As erases accumulate, the difference between the highest and lowest counts is audited. If a specific set of constraints are met, a wear leveling operation – which swaps the least erased block with the most recently used erase block – is completed.
Two parameters control wear leveling erases; the first is a maximum difference allowed before wear leveling erases are incurred, and the second limits the frequency of wear leveling erases. Again, considering the necessity to maintain optimal read/write performance in the flash, FlashFX Pro will never incur wear leveling erases if they are not necessary. It will effectively move high use areas of the flash to low use areas over time and will keep the average erase cycle count within a predefined range. It is important to note that this system utilizes the entire flash disk by forcing static areas of the flash to move which would otherwise never be rewritten fully.
In order to ensure that the wear-leveling process will not degrade performance or compromise the integrity of fixed file system meta data, FlashFX Pro begins erases well before the cumulative writes equals the size of the flash disk.
Simplistic Calculation of Flash Cycles
In order to determine if a certain application will challenge the endurance cycles of the flash that are specified by the flash manufacturer, a number of variables must be considered. Assume the flash is used efficiently by the application and that all flash described by Stotal is available to be written prior to an erase cycle being incurred. Given this assumption, a single erase cycle will be incurred once the entire flash (Stotal) is written. The period of time elapsed over a given cycle count, and therefore the period of time before a flash chip wears out, is then calculated with the following formula:
P = C [Stotal ÷ ( F * Dwrite) ]
Stotal describes the total flash memory available (KB) to be used as a disk.
Dwrite describes the amount of data (KB) being regularly written into the disk.
F is the frequency of Dwrite to the disk per day.
C is a given number of cycles to calculate the period.
Example 1: Field Data Recorder (1 MB disk)
Below is a chart with an example of a field data recorder that collects and stores coordinates and other statistics at a rate of 1280 bytes per minute, and must maintain the last hour of data (75KB), for a total of 1800KB of writes per day. Although the entire flash size may be 1MB or more, only 256KB can be used to store data. The remaining space must store code and application data. The data requires one flash erase block (128KB - remember we cannot erase just 75KB); we will have the application swap between two flash erase blocks.
• Stotal = 256 KB
• Dwrite = 1800 KB
• F = 1 day
Stotal (disk size) C (cycles) P (period)
256KB 1,000 142 days
256KB 10,000 3.9 years
256KB 100,000 39 years
Table 1
If the field data recorder has a lifetime of 2 to 3 years and the flash management software implements efficient wear leveling, the data in Table 1 is assumed. If the flash memory’s endurance was limited to 1,000 cycles, we have a good cause to worry that the product’s lifetime is limited by the choice in flash memory. A flash endurance with 10,000 cycles might also be problematic, but with 100,000 cycles, the flash is expected to reasonably outlive our product. Fortunately, there are many flash memories on the market today with such an endurance capability.
Example 2: Field Data Recorder (1 MB disk)
Suppose the entire 1MB flash chip is managed by FlashFX Pro. In the previous example, our application was placed into the other 768KB of the flash chip, but now it can be placed into the FlashFX Pro disk along with the data that is being recorded. If FlashFX Pro did not employ any wear leveling, the results of the endurance calculations would not differ. Since the flash management software periodically moves the two erase blocks that store data, the entire 1MB can be utilized. Table 2 shows the much improved situation.
• Stotal = 1024 KB
• Dwrite = 1800 KB
• F = 1 day
Stotal (disk size) C (cycles) P (period)
1024KB 1,000 1.5 years
1024KB 10,000 15.5 years
1024KB 100,000 155 years
Table 2
In this example, the choice of flash memories now includes those rated for 10,000 cycles or greater.
The Other Data Management Considerations
The wear-leveling algorithm of the flash management software does not complete the story of assuring optimum flash life; there are, of course, a few more complex variables to introduce to the formula.
Static Data
In Example #1 above, 768KB of the 1MB flash chip was used for storing the application and the remaining 256KB was used for our data storage. A large portion of the chip – the 768KB – is a static area, data that is stale and otherwise rarely changed. If the flash management software provides a reasonable wear-leveling scheme, static areas can be largely ignored. However, for the purpose of this wear-leveling study, the variable Dstatic is added to the formula in order to accommodate calculations that have static data.
Flash Management Software Overhead
The second variable that must be added is a multiplier to account for the meta data that FlashFX Pro uses to manage the flash disk. In short, once FlashFX Pro prepares the disk for use, a certain amount of data is removed from the total available space in the flash disk. FlashFX Pro may reserve between 1.5% and 4% of the media for its own purposes. However, only 1.6% (typically 2 pages per 64 pages of NOR flash) is actually used for meta data. There are other FlashFX Pro parameters that may change the total overhead, but the meta data is fixed. NAND flash has even less overhead. To keep the formula relatively simplistic, this will be described as a factor of 0.96 (to account for either NOR or NAND flash) added to the Stotal variable.
File System Overhead
The file system will perform a similar task to reduce the amount of space available for writes, but, this overhead will not be considered. File system overhead does indeed limit the total space available for writes. However, writes to the disk are spread across the entire space available to FlashFX Pro.
While the lost useable space from the file system does not impact the cycling, additional writes of meta data are incurred which increase the number of writes to the disk. Suppose an application completes the following sequence of operations:
Open a log file Write 1280B Close the log file
With a FAT file system, a minimum of 3KB of data would be written to the media:
• Three 512B sectors of data,
• Two updates to the FAT tables, and
• One update to the directory entry.
In terms of percentage, that is a factor of 240% compared to the 1280B of data we are interested in. If the application is a little smarter, it could cache six minutes of data before each write, resulting in 9KB of writes to the media – a factor of 120%.
If Datalight Reliance™, a highly reliable transactional file system, is used we can control when the meta data is written, avoiding the cache and simply asking the file system to record a transaction point when we want. This transaction point event could occur every six minutes, upon an event of power down, or any time we deem it is necessary. In this case, the writes could be reduced even further to near 6KB.
The average overhead for Reliance is 5% to 11%, depending on how the product and disk caches are configured and how the application behaves. This dramatic difference is taking into account that the average write size is more than 4KB. (The additional overhead can easily range to 20% or more for any file system based on the behavior and configurations of the product and applications.) For simplicity, a conservative factor of 1.11 is added to the Dwrite variable. The final formula is shown below:
P = C [ (0.96 Stotal - Dstatic ) ÷ (F * 1.11 Dwrite) ]
Stotal describes the total flash memory available (KB) to be used as a disk.
Dwrite describes the amount of data (KB) being regularly written into the disk.
Dstatic Space within the flash disk that is not wear leveled.
F is the frequency of Dwrite to the disk per day.
C is a given number of cycles to calculate the period.
The Complete Story
Staying with the data recorder examples in Examples #1 and #2 above, the flash life calculations are updated. While the reduction in the expected lifetime is not very large, it does provide a more accurate representation of the expected lifetime of the flash.
• Stotal = 1024 KB
• Dwrite = 1800 KB
• Dstatic = 1800 KB
• F = 1 day
Stotal (disk size) C (cycles) P (period)
1024KB 1,000 1.3 years
1024KB 10,000 13.4 years
1024KB 100,000 134 years
Table 3
In contrast, recalculate the above example with flash management software that is not implementing wear leveling. In order to do this, Dstatic = 750KB.
• Stotal = 1024 KB
• Dwrite = 1800 KB
• Dstatic = 750 KB
• F = 1 day
Stotal (disk size) C (cycles) P (period)
1024KB 1,000 116 days
1024KB 10,000 3.1 years
1024KB 100,000 31 years
Table 4
Remember, the factors chosen above are making many assumptions that may not be accurate for your specific application and file system. Given the periods of time are so high in many cases, the variances are statistically unimportant.
A Real World Application: Marine GPS System
This example consists of a navigation system targeted at marine vehicles that are expected to be powered and running 24 hours per day, and in use for ten to fifteen years. A 2GB NAND flash chip is partitioned to store three different sets of data:
• Configuration data – Consists of application and system configuration information
o 200MB, updated every 30 days
o Total writes of configuration data per day = (200MB ÷ 30 days) = 6.7MB per day
• Travel data – Consists of GPS coordinates and travel history data
o 200KB, written every 15 seconds and stores up to 12 hours of history
o Total writes of travel data per day =
(200KB * 4) = 600KB per minute * 1,440 min per day = 864MB per day
• Map data
o 1GB, updated every 90 days
o 1.25GB of the 2GB NAND flash chip is reserved for the map data
o 0.75GB, or 750MB, of the flash disk can be used for the application and travel data
Therefore, Configuration data + Travel data = Total writes per day (Dwrite) = 870MB
The partitioning scheme above was chosen to maximize performance of updates to the map data. Plugging this data into our formula has the following results on the device endurance:
P = C [ (0.96 Stotal - Dstatic ) ÷ (F * 1.11 Dwrite) ]
• Stotal = 750MB
• Dwrite = 870MB
• Dstatic = 0
• F = 1 day
Stotal (disk size) C (cycles) P (period)
768MB 1,000 2 years
768MB 10,000 20 years
768MB 100,000 209 years
Table 5
At the 10,000 cycle range the endurance period is 20 years, which is likely a sufficient lifetime for the GPS device, but to reduce the risk as much as possible, a 100,000 cycle rated flash is needed or the application should be modified to account for the low cycles.
Earlier, flash partitioning was described in order to store the map data. However, if we had the entire flash part to distribute writes, the GPS device would be much more reliable. We have to account for the additional writes of 1GB of map data every 90 days.
o Total writes of map data per day = 1GB ÷ 90 days = 11.1MB per day
Therefore, Configuration data + Travel data + Map data = Total writes per day (Dwrite) = 881MB
Plugging this data into our formula has the following results on the device endurance:
• Stotal = 2048 MB
• Dwrite = 881 MB
• Dstatic = 0 MB
• F = 1 day
Stotal (disk size) C (cycles) P (period)
2048MB 1,000 5.5 years
2048MB 10,000 55 years
2048MB 100,000 551 years
Table 6
By using the entire 2GB of the flash chip to write data, the device can expect to have a life of over 50 years before the flash is fully cycled to the 10,000 mark; now, the options for flash memories are much broader.
Of course, these examples above assume that an efficient wear leveling scheme is implemented by the flash media management software. If each of these examples were recalculated with the Dstatic variable equal to the amount of data that is least updated, the life expectancies will drop significantly:
Stotal (disk size) C (cycles) P (period)
2048MB 1,000 1.5 years
2048MB 10,000 15 years
2048MB 100,000 150 years
Conclusions
It takes a very write intensive application to cycle flash memories to their limits. However, it is possible for your product to become a brick before you expect it if the flash limitations are not addressed. The examples shown here all target 10,000 cycle flash and there are many flash parts available that are guaranteed for 100,000 cycles once certain precautions are met.
If the flash media manager is actively wear leveling the flash memory you can expect the flash to endure its full expected life time. If there is no media manager, take a careful review of the flash specifications to ensure all tolerances are met, especially operating temperature ranges.
Finally, take a look through the references, there is a great deal of good information available from the flash manufacturers.
References
A good discussion on the endurance and data retention capabilities of Spansion flash:
http://www.spansion.com/application_notes/EndureRetentn_AN_A0.pdf
A discussion about hitting the 1,000,000 mark with SST flash:
http://www.sst.com/downloads/app_note/S72005.pdf
An interesting study about the endurance of some Solid State Flash Disks:
http://www.bitmicro.com/press_resources_flash_ssd_db.php
Download this Whitepaper and Others