Wear levelling

From Wikipedia, the free encyclopedia

Wear levelling (also written wear leveling) is a technique^[1] for prolonging the service life of some kinds of erasable computer storage media, such as flash memory. The term has also been used by Western Digital to describe their hard disk preservation technique, but hard disks are not generally wear-levelled devices. (The use of 'wear' is appropriate because it can refer to deterioration by use in addition to friction.)

1 Problem
2 Some solutions
3 References
4 External links

[edit] Problem

EEPROM and flash memory media have individually erasable segments, each of which can be put through a finite number of erase cycles before possibly starting to wear-out and becoming statistically unreliable: anywhere between 10,000 and 1,000,000 cycles, for example, for NAND flash devices. Erasable optical media such as CD-RW and DVD-RW are rated at up to 1,000 cycles (100,000 cycles for DVD-RAM media).

Conventional file systems like FAT, ext2 and NTFS were originally designed for magnetic disks and as such rewrite many of their data structures (such as their directories) repeatedly in place. Once the sector that contains the directory "wears out", the entire media must be discarded and replaced with fresh media, even if most of the remaining sectors had only been written a few times.

[edit] Some solutions

SanDisk, for example, describes a technique whereby unused media sectors are grouped into blocks.^[2] Each unused block is held in an erase pool until it is needed, and as additional writable space is requested, blocks are removed from the pool. Since sectors are grouped into blocks, a sector update can be performed by writing the updated data to a new sector within the block; the process is repeated until the block is filled. Once filled, a subsequent sector update would cause the sector to be written to an entirely new block, and the prior block is then erased and returned to the erase pool.^{[verification needed]} This technique, however, is not used exactly as described in any of SanDisk's current products; it also may not be correct since it misses the fact that the FAT structure (on FAT-formatted flash drives) is frequently re-written in-place and cannot be reallocated or moved after wear failure, except possibly by grouping sectors that do and do not contain the FAT as part of the same block.

There are several techniques for extending the life of the media. Generally these trade off more writes to other sectors (and so are slower than conventional systems), in order to vastly reduce the number of writes to the most-written-to sector.

Often, each block or sector of data includes additional check bytes which can be used to detect errors and in many cases correct errors.
There may also be a mechanism for remapping unreliable blocks to other unused blocks that are still working.
Even before that point, the wear-levelling feature may detect that a certain block is getting changed very often, and swap it for another block elsewhere that has not yet been written to very much.

Wear-levelling attempts to work around these limitations by arranging data so that erasures and re-writes are distributed evenly across the medium. In this way, no single sector prematurely fails due to a high concentration of write cycles.

On flash memory devices, wear-levelling can be implemented in hardware by a built-in microcontroller or in software by special-purpose file systems such as JFFS2 or YAFFS. On optical media, the UDF file system provides wear-levelling.

In particular, pure circular log-structured filesystems are inherently wear-leveling -- they always write every sector exactly the same number of times.

Some storage interfaces like DiskOnChip, Intelligent Stick or OneNAND (which allow flash memory devices to emulate regular ATA disks) do not in themselves perform wear levelling, but may do so with additional software below the filesystem layer.