Static wear leveling

Methods for extending the service life of a data storage device and devices operable to perform those methods are presented. A master lookup table block may comprise lookup table blocks and store an erase count indicator for each lookup table block. Each lookup table block may be associated with a logical zone of a memory and comprise entries. Each entry may be associated with a logical block and comprise an erase count for a physical block corresponding to that logical block. A physical block erasure may be performed on a first physical block in the memory. The physical block erasure may be tracked by incrementally increasing a first erase count. An actual erase count may be determined for the first physical block. The entry for a logical block corresponding to the first physical block may be exchanged with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold. The different lookup table block may have a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block.

CROSS-REFERENCE TO RELATED APPLICATION

The present application is related to U.S. patent application Ser. No. 12/426,917 filed Apr. 20, 2009 and entitled “Logical-to-Physical Address Translation for a Removable Data Storage Device,” the disclosure of which is incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to improving performance in data storage devices. More specifically, the present invention relates to extending the service life of a data storage device.

2. Related Art

Wear leveling generally describes techniques for prolonging the service life of some kinds of erasable computer storage media, such as EEPROM and flash memory. Storage media such as EEPROM and flash memory media have individually erasable segments or blocks, each of which can be put through a limited number of erase cycles before becoming unreliable. When information is to be written to a particular block in EEPROM or flash memory, that entire block must first be erased. With some file systems such as FAT32, an operating system such as Microsoft Windows XP or Vista updates FAT tables for every megabyte written. This exemplifies how certain blocks may be highly stressed relative to other blocks in some kinds of erasable computer storage media.

Two general classes of wear leveling exist: dynamic wear leveling and static wear leveling. Dynamic wear leveling spreads out write operations by using a portion of the total blocks in a circular FIFO. This FIFO can be filled quickly during small file transfers resulting in the same set of free blocks being repeatedly erased. This can lead to a small set of blocks being over-stressed. In static wear leveling, data at rest is moved around within memory to ensure that all blocks in a medium are written to evenly, thereby increasing service life of that medium. Present implementations of static wear leveling suffer drawbacks affecting device performance. As such, there is a need for an improved technique for wear leveling.

SUMMARY OF THE INVENTION

Embodiments of the present technology allow the service life of a data storage device to be extended.

In a first claimed embodiment, a method for extending the service life of a data storage device is disclosed. The method includes performing a physical block erasure on a first physical block in the memory, wherein the memory comprises a plurality of logical zones, and each logical zone comprises a plurality of physical blocks. The physical block erasure may be tracked by incrementally increasing a first erase count, wherein a master lookup table block comprises a plurality of lookup table blocks and stores an erase count indicator for each lookup table block, each lookup table block being associated with one logical zone and comprising a plurality of entries, and each entry being associated with one logical block and comprising an erase count for a physical block corresponding to that logical block. An actual erase count may be determined for the first physical block. The entry for a logical block corresponding to the first physical block may be exchanged with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold, the different lookup table block having a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block.

In a second claimed embodiment, a data storage device set forth. The data storage device includes a memory for storing data and a controller communicatively coupled with the memory. The memory comprises a plurality of logical zones, of which each comprises a plurality of physical blocks. The controller comprises a logic module, a deletion module, and a scheduler module. The logic module may be executable by the controller for managing a master lookup table block. The master lookup table block may comprise a plurality of lookup table blocks and store an erase count indicator for each lookup table block. Each lookup table block may be associated with one logical zone and comprise a plurality of entries. Each entry may be associated with one logical block and comprising an erase count for a physical block corresponding to that logical block. The deletion module may be executable by the controller for performing a physical block erasure on a first physical block in the memory. The scheduler module may be executable by the controller for tracking the physical block erasure by incrementally increasing a first erase count and determining an actual erase count for the first physical block. The scheduler module may be further executable by the controller for exchanging the entry for a logical block corresponding to the first physical block with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold, the different lookup table block having a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block.

A third claimed embodiment discloses a computer readable storage medium having a program embodied thereon. The program is executable by a processor to perform method for extending the service life of a data storage device. The method comprises performing a physical block erasure on a first physical block in the flash memory, wherein the memory comprises a plurality of logical zones, and each logical zone comprises a plurality of physical blocks; tracking the physical block erasure by incrementally increasing a first erase count, wherein a master lookup table block comprises a plurality of lookup table blocks and stores an erase count indicator for each lookup table block, each lookup table block is associated with one logical zone and comprises a plurality of entries, and each entry is associated with one logical block and comprises an erase count for a physical block corresponding to that logical block; determining an actual erase count for the first physical block; and exchanging the entry for a logical block corresponding to the first physical block with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold, the different lookup table block having a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

The present technology provides methods for extending the service life of a data storage device and devices operable to perform those methods. Erasures performed on a given physical block in memory are tracked by incrementally increasing a corresponding erase count included in an entry associated with a logical block correlated with that physical block. Each of a plurality of physical blocks included in the memory is associated with logical zones such that each logical zone comprises a different portion of the physical blocks. An average erase count, or other erase count indicator, is determined for each logical zone. According to exemplary embodiments, when the total number of erasures for the given physical block reaches a limit, the entry associated with the logical block correlated with that physical block is exchanged with another entry associated with a logical block correlated with a physical block in a logical zone having a lower average count. This allows erasures to be performed evenly over time in the memory, thereby extending service life.

Referring now toFIG. 1, a block diagram is presented of an exemplary environment100in which embodiments of the present technology may be practiced. As depicted, the environment100includes a data storage device105, a host device110, and a network115. The data storage device105is communicatively coupled with the host device110, which in turn in communicatively coupled with the network115. It is noteworthy that these communicative couplings may be wireless or wired. Furthermore, as depicted, the data storage device105includes a static wear leveling engine125. The static wear leveling engine125is discussed further in connection withFIG. 3.

The data storage device105may be any device used to store digital information. In some embodiments, the data storage device105is portable and can be coupled or decoupled by a user with any device such as the host device110. Examples of portable data storage devices include a USB flash drive, an external hard drives, and other peripheral storage devices. In other embodiments, the data storage device105is integral to the host device110. For example, the data storage device105may include an internal hard drive of the host device110. For illustrative purposes, the data storage device105is described herein in the context of a USB flash drive. The data storage device105is discussed in further detail in connection withFIG. 2.

The host device110includes any digital device that can interface with the data storage device105. Generally, the host device110may also interface with the network115. Examples of the host device110include a personal computer (PC), a personal digital assistant (PDA), a Smartphone, a digital camera, and other various devices. The host device110includes one or more communications interfaces (not depicted) to facilitate communicative coupling with the data storage device105. One or more communications interfaces may also facilitate communicative coupling to the network115. Additionally, the host device110includes a processor, memory such as RAM, and storage such as ROM (all not depicted). Those skilled in the art will be familiar with the components and functionality of digital devices such as the host device110.

The network115may be a wide-area network and include a private network (e.g., a leased line network) or a public network (e.g., the Internet). In some embodiments, the network115may be a local area network and cover a relatively small geographic range. Local area networks include wired networks (e.g., Ethernet) or wireless networks (e.g., Wi-Fi). The network115includes hardware and/or software elements that enable the exchange of information (e.g., voice and data) between the data storage device105or the host device110and other devices communicatively coupled with the network115. Routers or switches may be used to connect the network115with the host device110.

FIG. 2is a block diagram of an exemplary data storage device105employed in the environment100. As mentioned, the data storage device105can be any device that is used to store digital information, and may also be portable. The data storage device105depicted inFIG. 2includes a memory205, a controller210, and an interface215.

The memory205includes a computer-readable storage medium having a plurality of physical blocks to which data can be written to. These physical blocks may be divided into two or more physical zones such that each physical zone includes a different portion of the physical blocks. The physical zones may each correspond to a different logical zone. While common forms of computer-readable storage media include, for example, a floppy disk, a flexible disk, a hard disk, magnetic tape, any other magnetic medium, a CD-ROM disk, digital video disk (DVD), and any other optical medium, the memory205is described in the context of non-volatile memory that can be electrically erased and rewritten. Examples of such non-volatile memory include flash memory such as NAND flash and NOR flash. Flash memory may include single level cells, multi level cells, or a combination thereof. Additionally, the memory205may include more than one chip, in accordance with some embodiments, wherein each chip comprises a different portion of the physical zones and, consequently, a different portion of the logical zones. Furthermore, the memory205may comprise other memory technologies as they become available.

The controller210may be a processor or microcontroller with an amount of on-chip ROM and/or RAM. The controller210is communicatively coupled with the memory205and the interface215. Additionally, the controller210includes software and/or firmware that may execute various modules described herein. As such, the controller210functions as an intermediary between the host device110and the memory205. For example, the controller210, or various modules executed thereby, may receive write commands from the host device110and determine how data associated with those write commands is managed with respect to the memory205.

As mentioned, the data storage device105is communicatively coupled with the host device110, either wirelessly or wired, in exemplary embodiments. The interface215facilitates this coupling by allowing information to be transferred between the data storage device105and the host device110. In exemplary embodiments, the interface215includes a USB plug that is insertable into a mating USB port of the host device110. Alternatively, the interface215may include other standards for communicative coupling such as FireWire, Ethernet, Wireless USB, or Bluetooth. Furthermore, the interface215may comprise other interface technologies as they become available.

FIG. 3is a block diagram of an exemplary static wear leveling engine125included in the data storage device105. In accordance with various embodiments, the static wear leveling engine125, or certain modules thereof, may be stored by on-chip ROM of the controller210and/or by the memory205. As depicted inFIG. 3, the static wear leveling engine125includes a logic module305, a deletion module310, a scheduler module315, a bad block management module320, and a power loss recovery module325. These modules may be executed by the controller210of the data storage device105to effectuate the functionality attributed thereto.

The static wear leveling engine125may be composed of more or fewer modules (or combinations of the same) and still fall within the scope of the present invention. For example, the functionality of the deletion module310and the functionality of the scheduler module315may be combined into a single module. Furthermore, the static wear leveling engine125may include various modules associated with reading and writing information to the memory205(not depicted).

Execution of the logic module305allows the controller210to manage a master lookup table block. The master lookup table block includes one or more lookup table blocks that, in turn, each include one or more entries. An exemplary lookup table block is described in connection withFIG. 4B, while an exemplary master table block is described in connection withFIG. 4C. Referring now toFIG. 4A, an exemplary entry405of a lookup table block is illustrated. The entry405is associated with a logical block correlated with a physical block. The entry405includes miscellaneous information410, an erase count415, a chip select number420, a physical zone number425, and a physical block number430. The entry405may have a fixed size in memory. In exemplary embodiments, the entry405has a size of four bytes. Accordingly, in one example, the miscellaneous information410may be allotted four bits, the erase count415may be allotted twelve bits, the chip select number420may be allotted three bits, the physical zone number425may be allotted four bits, and the physical block number430may be allotted nine bits.

The miscellaneous information410may be used to store any information related to the entry405, the logical block associated with the entry405, the physical block correlated with that logical block, or any other information. The erase count415may be used to track erasures performed on the physical block correlated with the logical block associated with the entry405. Since the amount of memory allotted to erase count415may be fixed, the erase count415may be reset to zero when the erase count415reaches a limit. For example, if the erase count415is allotted twelve bits, the erase count415can track4096erasures prior to resetting to zero. That resetting may then be reflected by a cycle count kept in the master lookup table block, as discussed further herein. As mentioned, the memory205may include more than one chip. The chip select number420may identify a chip that includes the physical block correlated with the logical block associated with the entry405. The physical block number430identifies the physical block correlated with the logical block associated with the entry405.

FIG. 4Billustrates an exemplary lookup table block (LTB)435included in a master lookup table block. The lookup table block435includes any number of entries440a-440n, each being similar to entry405. In exemplary embodiments, each lookup table block is associated with one logical zone in that the entries (e.g., entry405) included in a particular lookup table block are associated with logical blocks correlated with physical blocks in a single logical zone. Additionally, duplicates of the entries440a-440nmay be included in the lookup table block435, in accordance with some embodiments, as discussed further in connection with the power loss recovery module325.

FIG. 4Cillustrates an exemplary master lookup table block (MLTB)445. The master lookup table block445includes any number of lookup table blocks (LTB)450a-450n, each being similar to lookup table block435. In addition to the lookup table blocks450a-450n, the master lookup table block445may further include one or more erase count indicators associated with each of the lookup table blocks450a-450n. One such erase count indicator is a lookup table block cycle count, which may be incrementally increased each time the erase count415of a constituent entry is reset to zero. A lookup table block cycle count (LTBCycCnt)455amay correspond to lookup table block450a, while lookup table block cycle count455nmay correspond to lookup table block450n. Incidentally, lookup table block cycle counts may be used in combination with erase count415to determine the actual erase count of a particular physical block. Another erase count indicator is an average erase count for the entries of a particular lookup table block. For example, the average erase count (AveErsCnt)455aindicates the average erase count of the entries included in the lookup table block450a, while the average erase count455nindicates the average erase count of the entries included in the lookup table block450n.

Returning toFIG. 3, execution of the deletion module310allows the controller210to perform physical block erasures on the physical blocks included in the memory205. As mentioned, when information is to be written to a particular physical block in EEPROM or flash memory, that entire physical block must first be erased. Accordingly, the physical block erasures performed via execution of the deletion module310may likely follow receipt of a write command from the host device110. Furthermore, these erasures may also be performed while the memory205is being formatted.

Execution of the scheduler module315allows the controller210to perform a number of functions with respect to wear leveling in the memory205of the data storage device105. For example, the schedule module315may be executed to track physical block erasures performed via execution of the deletion module310by incrementally increasing erase counts included in entries of the lookup table blocks. For example, if the deletion module210is executed to erase the physical block correlated with the logical block associated with the entry405(referring toFIG. 4A), the scheduler module315can be executed to track that erasure by incrementally increasing the erase count415. When the erase count415reaches a limit (e.g.,4096), the scheduler module315is executed to reset the erase count to zero. Accordingly, the scheduler module315may also be executed to incrementally increasing a lookup table block cycle count for a lookup table block when an erase count indicated in an entry of that lookup table block reaches the limit.

The scheduler module315may also be executed to determining actual erase counts for the physical blocks of the memory205. As mentioned, the actual erase count for a particular physical block may be determined with the erase count in the entry associated with the logical block correlated with that physical block in conjunction with the lookup table block cycle count for the lookup table block that includes that entry.

Additionally, the scheduler module315may be executed to exchange entries between different lookup table blocks. For example, an entry for a logical block correlated with a physical block that has been erased a threshold number of times can be exchanged with another entry that is included in a different lookup table block having a lower average erase count. The threshold number of erasures can be any value depending on characteristics of the memory205. In embodiments in which the memory205comprises more than on chip, the entries being exchanged may be associated with logical blocks associated with physical blocks on separate chips.

Execution of the bad block management module320allows the controller210to screen the physical blocks of the memory205to identify any inoperable physical blocks. In an event that inoperable physical blocks are identified, the scheduler module315is informed such that entries (e.g., entry405) are prevented from being exchanged with another entry associated with a logical zone correlated with the inoperable physical block. A bad block table (not depicted) may be maintained by the bad block management module320that tracks information related to inoperable physical blocks (e.g., physical block number, zone number, chip select number, etc.).

Execution of the power loss recovery module325allows the controller210to reconstruct lookup table blocks after a loss of power to the data storage device105. As mentioned, duplicates of entries (e.g., duplicates of the entries440a-440n) may be included in lookup table blocks (e.g., the lookup table block435), in accordance with some embodiments. The entries and duplicates may be stored temporarily in a buffer during operation of the data storage device105. The buffer may be included in on-chip RAM of the controller210. When an entry included in the master lookup table block matches what is reflected in the buffer, that entry included in the master lookup table block is considered valid. This is likewise true for the duplicates included in the master lookup table. In an event of sudden or unexpected loss of power to the data storage device105, a most current update of entries and/or duplicates in the buffer may be lost. Upon re-powering of the data storage device105, the power loss recover module325can be executed to determine whether a given entry and duplicate are valid. If both the given entry and duplicate are invalid, either the entry or the duplicate may be selected and used to reconstruct update the corresponding lookup table block.

Turning now toFIG. 5, an exemplary lookup table block updation sequence500is illustrated. For brevity, a subset of stages (i.e., stages505,510, and515) of the updation sequence500is depicted inFIG. 5. As depicted in stage505, the lookup table block520includes entries525a-525n. Each of the entries525a-525nis associated with a logical block correlated with a physical block. For example, the entry525ais associated with a logical block correlated with physical block number zero (PB0), which has been erased zero times denoted by ‘PB0: 0’. The lookup table block530, as depicted in stage505, includes entries535a-535n. Similarly, the entries535a-535neach are associated with a logical block correlated with a physical block. For example, the entry535mis associated with a logical block correlated with physical block number ninety one (PB91), which has been erased zero times denoted by ‘PB91: 0’.

In stage510, physical block zero (PB0) has been erased fifty times, denoted as ‘PB0: 50’ in the entry525a. Since several erasures have occurred in physical blocks associated with the lookup table block520, the lookup table block520may be considered ‘hot’. Conversely, lookup table block530may be considered ‘cold’ since few in any erasures have occurred in physical blocks associated with the lookup table block530. Assuming, for this example, that fifty erasures is a threshold, the entry525ashould be exchanged with an entry from a ‘cold’ lookup table block. In stage515, entry525ahas been exchanged with entry5351from lookup table block530. Resultantly, erasures concentrated to certain logical blocks may be spread across numerous physical blocks, thereby extending the service life of the data storage device105.

FIG. 6is a flowchart of an exemplary method600for static wear leveling in the data storage device105. The steps of the method600may be performed in varying orders. Steps may be added or subtracted from the method600and still fall within the scope of the present technology.

In step605, a physical block erasure is performed. This may be performed on a first physical block in the memory205, wherein the memory205comprises a plurality of logical zones, and each logical zone comprises a plurality of physical blocks. In exemplary embodiments, step605is performed through execution of the deletion module310.

In step610, the physical block erasure is tracked. According to exemplary embodiments, the physical block erasure is tracked by incrementally increasing a first erase count. It is noted that a master lookup table block may comprise a plurality of lookup table blocks and store an erase count indicator for each lookup table block. In turn, each lookup table block may be associated with one logical zone and comprise a plurality of entries. Each entry may be associated with one logical block and comprising an erase count for that logical block. The logic module305may be executed to manage the master lookup table block and the constituent parts, while the scheduler module315may be executed to perform step610.

In step615, an actual erase count is determined. For example, the scheduler module315may be executed to determine an actual erase count for the first physical block. The actual erase count for the first physical block may be determined using the first erase count in conjunction with an erase count indicator for the corresponding lookup table block.

In step620, entries are exchanged when the actual erase count exceeds a threshold. In exemplary embodiments, the entry for a logical block corresponding to the first physical block may be exchanged with another entry within a different lookup table block when the actual erase count for the first physical block exceeds a threshold. The different lookup table block may have a lower erase count indicator relative to that of the lookup table block comprising the entry for the logical block corresponding to the first physical block. Step620may be performed by the scheduler module315.