wear leveling
   HOME

TheInfoList



OR:

Wear leveling (also written as wear levelling) is a technique Wear leveling techniques for flash memory systems. for prolonging the
service life A product's service life is its period of use in service. Several related terms describe more precisely a product's life, from the point of manufacture, storage, and distribution, and eventual use. Service life has been defined as "a product li ...
of some kinds of erasable computer storage media, such as flash memory, which is used in
solid-state drive A solid-state drive (SSD) is a solid-state storage device that uses integrated circuit assemblies to store data persistently, typically using flash memory, and functioning as secondary storage in the hierarchy of computer storage. It is a ...
s (SSDs) and
USB flash drive Universal Serial Bus (USB) is an industry standard that establishes specifications for cables, connectors and protocols for connection, communication and power supply ( interfacing) between computers, peripherals and other computers. A bro ...
s, and
phase-change memory Phase-change memory (also known as PCM, PCME, PRAM, PCRAM, OUM (ovonic unified memory) and C-RAM or CRAM (chalcogenide RAM)) is a type of non-volatile random-access memory. PRAMs exploit the unique behaviour of chalcogenide glass. In PCM, heat pr ...
. There are several wear leveling mechanisms that provide varying levels of longevity enhancement in such memory systems. The term ''preemptive wear leveling'' (PWL) has been used by
Western Digital Western Digital Corporation (WDC, commonly known as Western Digital or WD) is an American computer drive manufacturer and data storage company, headquartered in San Jose, California. It designs, manufactures and sells data technology produc ...
to describe their preservation technique used on
hard disk drive A hard disk drive (HDD), hard disk, hard drive, or fixed disk is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magne ...
s (HDDs) designed for storing audio and video data. However, HDDs generally are not wear-leveled devices in the context of this article.


Rationale

EEPROM 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 A flash memory controller (or flash controller) manages data stored on flash memory (usually NAND flash) and communicates with a computer or electronic device. Flash memory controllers can be designed for operating in low duty-cycle environments ...
to track wear and movement of data across segments. Erasable
optical media In computing and optical disc recording technologies, an optical disc (OD) is a flat, usually circular disc that encodes binary data ( bits) in the form of pits and lands on a special material, often aluminum, on one of its flat surfaces ...
such as
CD-RW CD-RW (Compact Disc-Rewritable) is a digital optical disc storage format introduced in 1997. A CD-RW compact disc (CD-RWs) can be written, read, erased, and re-written. CD-RWs, as opposed to CDs, require specialized readers that have sensi ...
and
DVD-RW DVD recordable and DVD rewritable are optical disc recording technologies. Both terms describe DVD optical discs that can be written to by a DVD recorder, whereas only 'rewritable' discs are able to erase and rewrite data. Data is written ('bur ...
are rated at up to 1,000 cycles (100,000 cycles for
DVD-RAM DVD-RAM (DVD Random Access Memory) is a DVD-based 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 ...
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 systems such as
FAT In nutrition, biology, and chemistry, fat usually means any ester of fatty acids, or a mixture of such compounds, most commonly those that occur in living beings or in food. The term often refers specifically to triglycerides (triple est ...
, UFS, HFS, EXT, and
NTFS New Technology File System (NTFS) is a proprietary journaling file system developed by Microsoft. Starting with Windows NT 3.1, it is the default file system of the Windows NT family. It superseded File Allocation Table (FAT) as the preferred fil ...
were originally designed for magnetic disks and as such rewrite many of their data structures (such as their directories) repeatedly to the same area. When these systems are used on flash memory media, this becomes a problem. The problem is aggravated by the fact that some file systems track last-access times, which can lead to file metadata being constantly rewritten in-place.


Types

There are three basic types of wear leveling mechanisms used in flash memory storage devices:


No wear leveling

A flash memory storage system with ''no wear leveling'' will not last very long if data is written to the flash. Without wear leveling, the underlying flash controller must permanently assign the logical addresses from the
operating system An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs. Time-sharing operating systems schedule tasks for efficient use of the system and may also i ...
(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 approach is very time-consuming and frequently written locations will wear out quickly, while other locations will not be used at all. Once a few blocks reach their end of life, such a device becomes inoperable.


Dynamic wear leveling

The first type of wear 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, flash memory blocks that never get replacement data would sustain no additional wear, thus the name comes only from the dynamic data being recycled. Such a device may last longer than one with no wear leveling, but there are blocks still remaining as active even though the device is no longer operable.


Static wear leveling

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 an SSD to continue to operate until most of the blocks are near their end of life.


Global wear leveling

Both dynamic and static wear leveling are implemented at the local level. This simply means that in a multi-chip product, every chip is managed as a single resource. The number of defective blocks in different chips within a NAND flash memory varies: a given chip could have all its data blocks worn out while another chip in the same device could have all its blocks still active. Global wear leveling addresses this problem by managing all blocks from all chips in the flash memory together―in a single pool. It ensures that all the cells in all the chips within the product are worn out evenly.


Comparison

The following table compares static and dynamic wear leveling:


Techniques

There are several techniques for extending the media life: * A checksum or
error-correcting In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable commun ...
code can be kept for each 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 frequently used Least Frequently Used (LFU) is a type of cache algorithm used to manage memory within a computer. The standard characteristics of this method involve the system keeping track of the number of times a block is referenced in memory. When the cache i ...
(LFU) queue. 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. However, usual cache algorithms are designed to manage the data flow into and out of
RAM Ram, ram, or RAM may refer to: Animals * A male sheep * Ram cichlid, a freshwater tropical fish People * Ram (given name) * Ram (surname) * Ram (director) (Ramsubramaniam), an Indian Tamil film director * RAM (musician) (born 1974), Dutch * ...
-based caches, making them not directly suitable for flash-based storage devices as they have an asymmetrical nature reads are usually much faster than writes, and erase operations can be performed only one "block" at a time. *
Garbage collection Waste collection is a part of the process of waste management. It is the transfer of solid waste from the point of use and disposal to the point of treatment or landfill. Waste collection also includes the curbside collection of recyclabl ...
On some
Secure Digital card Secure Digital, officially abbreviated as SD, is a proprietary non-volatile flash memory card format developed by the SD Association (SDA) for use in portable devices. The standard was introduced in August 1999 by joint efforts between SanDis ...
s, techniques are implemented in hardware by a built-in microcontroller. On such devices, wear leveling is
transparent Transparency, transparence or transparent most often refer to: * Transparency (optics), the physical property of allowing the transmission of light through a material They may also refer to: Literal uses * Transparency (photography), a still, ...
, and conventional file systems can be used on them as-is. Wear leveling can also be implemented in software by special-purpose file systems such as
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 into the Linux kernel since September 23, 2001, when it was merged into th ...
and
YAFFS Yaffs (Yet Another Flash File System) is a file system designed and written by Charles Manning for the company Aleph One. Yaffs1 was the first version of this file system and was designed for the then-current NAND chips with 512 byte page size ( ...
on flash media or UDF on optical media. All three are
log-structured file system A log-structured filesystem is a file system in which data and metadata are written sequentially to a circular buffer, called a log. The design was first proposed in 1988 by John K. Ousterhout and Fred Douglis and first implemented in 1992 by ...
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 (COW), sometimes referred to as implicit sharing or shadowing, is a resource-management technique used in computer programming to efficiently implement a "duplicate" or "copy" operation on modifiable resources. If a resource is dupl ...
strategies, such as
ZFS ZFS (previously: Zettabyte File System) is a file system with volume management capabilities. It began as part of the Sun Microsystems Solaris operating system in 2001. Large parts of Solaris – including ZFS – were published under an ope ...
, also implement a form of wear leveling.


See also

* Flash file system *
Battery balancing Battery balancing and battery redistribution refer to techniques that improve the available capacity of a battery pack with multiple cells (usually in series) and increase each cell's longevity. A battery balancer or battery regulator is an ele ...


References


External links


Flash SSDs Inferior Technology or Closet Superstar?
bitmicro.com, archived from the original on February 2, 2007 {{DEFAULTSORT:Wear Leveling Computer memory Non-volatile memory Flash file systems Solid-state computer storage Balancing technology de:Wear-Leveling