Wear levelling
Encyclopedia
Wear leveling is a technique for prolonging the service life
Service life
A product's service life is its expected lifetime, or the acceptable period of use in service. It is the time that any manufactured item can be expected to be 'serviceable' or supported by its manufacturer....

 of some kinds of erasable computer storage
Computer storage
Computer data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is one of the core functions and fundamental components of computers....

 media, such as Flash memory
Flash memory
Flash memory is a non-volatile computer storage chip that can be electrically erased and reprogrammed. It was developed from EEPROM and must be erased in fairly large blocks before these can be rewritten with new data...

 used in solid-state drive
Solid-state drive
A solid-state drive , sometimes called a solid-state disk or electronic disk, is a data storage device that uses solid-state memory to store persistent data with the intention of providing access in the same manner of a traditional block i/o hard disk drive...

s (SSDs) and USB Flash drive
USB flash drive
A flash drive is a data storage device that consists of flash memory with an integrated Universal Serial Bus interface. flash drives are typically removable and rewritable, and physically much smaller than a floppy disk. Most weigh less than 30 g...

s. There are a few wear leveling mechanisms used in Flash memory systems, each with varying levels of longevity enhancement.

The term preemptive wear leveling (PWL) has been used by Western Digital
Western Digital
Western Digital Corporation is one of the largest computer hard disk drive manufacturers in the world. It has a long history in the electronics industry as an integrated circuit maker and a storage products company. Western Digital was founded on April 23, 1970 by Alvin B...

 to describe their preservation technique used on audio-video hard disk
Hard disk
A hard disk drive is a non-volatile, random access digital magnetic data storage device. It features rotating rigid platters on a motor-driven spindle within a protective enclosure. Data is magnetically read from and written to the platter by read/write heads that float on a film of air above the...

s, but hard disk drives are not generally wear-leveled devices in the context of this article.

Rationale

EEPROM
EEPROM
EEPROM stands for Electrically Erasable Programmable Read-Only Memory and is a type of non-volatile memory used in computers and other electronic devices to store small amounts of data that must be saved when power is removed, e.g., calibration...

 and flash memory media have individually erasable segments, each of which can be put through a limited number of erase cycles before becoming unreliable. This is usually around 3,000/5,000 cycles but many flash devices have one block with a specially extended life of 100,000+ cycles that can be used by the Flash memory controller
Flash memory controller
A flash memory controller manages the data stored on flash memory and communicates with a computer or electronic device. Flash memory controllers can be designed for operating in low duty-cycle environments like SD cards, CompactFlash cards, or other similar media for use in digital cameras, PDAs,...

 to track wear and movement of data across segments. Erasable optical media
Optical disc
In computing and optical disc recording technologies, an optical disc is a flat, usually circular disc which encodes binary data in the form of pits and lands on a special material on one of its flat surfaces...

 such as CD-RW
CD-RW
A CD-RW is a rewritable optical disc. It was introduced in 1997, and was known as "CD-Writable" during development. It was preceded by the CD-MO, which was never commercially released....

 and DVD-RW
DVD-RW
A DVD-RW disc is a rewritable optical disc with equal storage capacity to a DVD-R, typically 4.7 GB. The format was developed by Pioneer in November 1999 and has been approved by the DVD Forum. The smaller Mini DVD-RW holds 1.46 GB, with a diameter of 8 cm.The primary advantage of DVD-RW over...

 are rated at up to 1,000 cycles (100,000 cycles for DVD-RAM
DVD-RAM
DVD-RAM is a disc specification presented in 1996 by the DVD Forum, which specifies rewritable DVD-RAM media and the appropriate DVD writers. DVD-RAM media have been used in computers as well as camcorders and personal video recorders since 1998.-Design:DVD-RAM is one of three competing...

 media).

Wear leveling 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 erase block prematurely fails due to a high concentration of write cycles. In flash memory, a single block on the chip is designed for longer life than the others so that the memory controller can store operational data with less chance of its corruption.

Conventional file system
File system
A file system is a means to organize data expected to be retained after a program terminates by providing procedures to store, retrieve and update data, as well as manage the available space on the device which contain it. A file system organizes data in an efficient manner and is tuned to the...

s such as FAT
File Allocation Table
File Allocation Table is a computer file system architecture now widely used on many computer systems and most memory cards, such as those used with digital cameras. FAT file systems are commonly found on floppy disks, flash memory cards, digital cameras, and many other portable devices because of...

, UFS
Unix File System
The Unix file system is a file system used by many Unix and Unix-like operating systems. It is also called the Berkeley Fast File System, the BSD Fast File System or FFS...

, HFS
Hierarchical File System
Hierarchical File System is a file system developed by Apple Inc. for use in computer systems running Mac OS. Originally designed for use on floppy and hard disks, it can also be found on read-only media such as CD-ROMs...

, ext2
Ext2
The ext2 or second extended filesystem is a file system for the Linux kernel. It was initially designed by Rémy Card as a replacement for the extended file system ....

, and NTFS
NTFS
NTFS is the standard file system of Windows NT, including its later versions Windows 2000, Windows XP, Windows Server 2003, Windows Server 2008, Windows Vista, and Windows 7....

 were originally designed for magnetic disks and as such rewrite many of their data structures (such as their directories) repeatedly to the same area. Some file systems aggravate the problem by tracking last-access times, which can lead to file metadata
Metadata
The term metadata is an ambiguous term which is used for two fundamentally different concepts . Although the expression "data about data" is often used, it does not apply to both in the same way. Structural metadata, the design and specification of data structures, cannot be about data, because at...

 being constantly rewritten in-place.

Types

There are three basic types of wear leveling mechanisms used in Flash memory storage devices:
  • No wear leveling
  • Dynamic wear leveling
  • Static wear leveling


A Flash memory storage system with no wear leveling will not last very long if it is writing data to the flash. Without wear leveling, the Flash controller must permanently assign the logical addresses from the Operating System
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...

 (OS) to the physical addresses of the Flash memory. This means that every write to a previously written block must first be read, erased, modified, and re-written to the same location. This is very time consuming and highly written locations will wear out quickly with other locations even being completely unused. Once a few blocks reach their end of life the drive is no longer operable.

The first type of real leveling is called dynamic wear leveling and it uses a map to link Logical Block Addresses (LBAs) from the OS to the physical Flash memory. Each time the OS writes replacement data, the map is updated so the original physical block is marked as invalid data, and a new block is linked to that map entry. Each time a block of data is re-written to the Flash memory it is written to a new location. However, blocks that never get replacement data sit with no additional wear on the Flash memory. The name comes from only the dynamic data is being recycled. The drive may last longer than one with no wear leveling, but there are blocks still remaining as active that will go unused when the drive is no longer operable.

The other type of wear leveling is called static wear leveling which also uses a map to link the LBA to physical memory addresses. Static wear leveling works the same as dynamic wear leveling except the static blocks that do not change are periodically moved so that these low usage cells are able to be used by other data. This rotational effect enables the SSD to operate until most of the blocks are near their end of life.
Comparison between Static and Dynamic wear leveling
Item Static Dynamic
Endurance
Endurance
Endurance is the ability for a human or animal to exert itself and remain active for a long period of time, as well as its ability to resist, withstand, recover from, and have immunity to trauma, wounds, or fatigue. In humans, it is usually used in aerobic or anaerobic exercise...

Longer life expectancy Shorter life expectancy
Performance Slower Faster
Design Complexity More complex Less complex
Typical Use SSDs USB Flash Drives

Techniques

There are several techniques for extending the life of the media:
  • A checksum or error-correcting
    Error detection and correction
    In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels...

     code can be kept for block or sector in order to detect errors or correct errors.
  • A pool of reserve space can also be kept. When a block or sector does fail, future reads and writes to it can be redirected to a replacement in that pool.
  • Blocks or sectors on the media can be tracked in a least recently used
    Cache algorithms
    In computing, cache algorithms are optimizing instructions – algorithms – that a computer program or a hardware-maintained structure can follow to manage a cache of information stored on the computer...

     queue of some sort. The data structures for the queue itself must either be stored off-device or in such a way that the space it uses is itself wear-leveled or, in the case of flash memory, in a block with a specially extended life.


M-Systems' product DiskOnChip used a software driver named TrueFFS which performed wear-leveling of NAND flash chips and made them appear to OS like a conventional disk drive. On most contemporary flash memory devices, such as CompactFlash
CompactFlash
CompactFlash is a mass storage device format used in portable electronic devices. Most CompactFlash devices contain flash memory in a standardized enclosure. The format was first specified and produced by SanDisk in 1994...

 and Secure Digital
Secure Digital card
Secure Digital is a non-volatile memory card format developed by the SD Card Association for use in portable devices. The SD technology is used by more than 400 brands across dozens of product categories and more than 8,000 models, and is considered the de-facto industry standard.Secure Digital...

 cards, these techniques are implemented in hardware by a built-in microcontroller
Microcontroller
A microcontroller is a small computer on a single integrated circuit containing a processor core, memory, and programmable input/output peripherals. Program memory in the form of NOR flash or OTP ROM is also often included on chip, as well as a typically small amount of RAM...

. On such devices, wear leveling is transparent
Transparency (computing)
Any change in a computing system, such as new feature or new component, is transparent if the system after change adheres to previous external interface as much as possible while changing its internal behaviour. The purpose is to shield from change all systems on the other end of the interface...

 and most conventional file systems can be used as-is on them.

Wear leveling can also be implemented in software by special-purpose file systems such as JFFS2
JFFS2
Journalling Flash File System version 2 or JFFS2 is a log-structured file system for use with flash memory devices. It is the successor to JFFS. JFFS2 has been included in the Linux kernel since the 2.4.10 release. JFFS2 is also available for a couple of bootloaders like Das U-Boot, Open...

 and YAFFS
YAFFS
YAFFS was designed and written by Charles Manning, of Whitecliffs, New Zealand, for the company .Yaffs1 is the first version of this file system and works on NAND chips that have 512 byte pages + 16 byte spare areas. These older chips also generally allow 2 or 3 write cycles per page, which...

 on flash media or UDF
Universal Disk Format
Universal Disk Format is an implementation of the specification known as ISO/IEC 13346 and ECMA-167 and is an open vendor-neutral file system for computer data storage for a broad range of media. In practice, it has been most widely used for DVDs and newer optical disc formats, supplanting ISO 9660...

 on optical media. All three are log-structured file system
Log-structured file system
A log-structured filesystem is a file system design first proposed in 1988 by John K. Ousterhout and Fred Douglis. Designed for high write throughput, all updates to data and metadata are written sequentially to a continuous stream, called a log...

s in that they treat their media as circular logs and write to them in sequential passes. File systems which implement Copy-on-write
Copy-on-write
Copy-on-write is an optimization strategy used in computer programming. The fundamental idea is that if multiple callers ask for resources which are initially indistinguishable, they can all be given pointers to the same resource...

 strategies, such as ZFS
ZFS
In computing, ZFS is a combined file system and logical volume manager designed by Sun Microsystems. The features of ZFS include data integrity verification against data corruption modes , support for high storage capacities, integration of the concepts of filesystem and volume management,...

, also implement a form of wear leveling.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK