Method and system for wear leveling in a solid state drive

A method and system for wear leveling in a solid state drive by mapping the logical regions of the solid state drive that hold static content or information into the physical regions of the solid state drive that have erase counts more than an average erase count of all of the physical regions. By doing so, it allows the solid state drive to wear level itself naturally through continued usage. In one embodiment of the invention, the erase count of each physical region is incremented with every erasing operation of each physical region. The physical regions that have a high count of erase count operations are mapped with content of the logical regions with static content so that the possibility of future erase operations of these physical regions is reduced.

FIELD OF THE INVENTION

This invention relates to a solid state drive, and more specifically but not exclusively, to a technique for wear leveling of the memory modules in a solid state drive.

BACKGROUND DESCRIPTION

Solid state drives (SSDs) often use multiple NAND flash memory blocks or modules to increase storage capacity. However, each NAND flash memory module has a limited number of write or erase cycles before it breaks down and this can affect the reliability of the SSD, especially in an environment where the host accesses of the SSD are unpredictable. Without any control of the write or erase operations to a particular SSD, some NAND flash memory modules may be written or erased more frequently than the other modules and therefore affect the reliability or life-time of the particular SSD.

DETAILED DESCRIPTION

Embodiments of the invention described herein are illustrated by way of example and not by way of limitation in the accompanying figures. For simplicity and clarity of illustration, elements illustrated in the figures are not necessarily drawn to scale. For example, the dimensions of some elements may be exaggerated relative to other elements for clarity. Further, where considered appropriate, reference numerals have been repeated among the figures to indicate corresponding or analogous elements. Reference in the specification to “one embodiment” or “an embodiment” of the invention means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. Thus, the appearances of the phrase “in one embodiment” in various places throughout the specification are not necessarily all referring to the same embodiment.

Embodiments of the invention provide a method and system for wear leveling in a SSD by mapping the logical regions of the SSD that hold static content or information into the physical regions of the SSD that have erase counts more than an average erase count of all of the physical regions. By doing so, it allows the SSD to wear level itself naturally through continued usage. In one embodiment of the invention, the erase count of each physical region is incremented with every erasing operation of each physical region. The physical regions that have a high count of erase count operations are mapped with content of the logical regions with static content so that the possibility of future erase operations of these physical regions is reduced.

In one embodiment of the invention, the wear leveling in the SSD is performed when the difference between the average erase count of all the physical regions and the minimum erase count of all the physical regions has exceeded a threshold. The wear leveling in the SSD is also performed when the difference between the maximum erase count of all the physical regions and the average erase count of all the physical regions has exceeded a threshold. In one embodiment of the invention, the threshold for both scenarios is the same. In another embodiment of the invention, each scenario uses a different threshold. The use of the threshold allows the SSD to wear level with minimal negative performance impact when the thresholds are not exceeded.

FIG. 1illustrates a block diagram100of a solid state drive102in accordance with one embodiment of the invention. The SSD102has a controller130, a host interface module110, a buffer120, and memory module0140, memory module1142, memory module2144, and memory module3146. In one embodiment of the invention, the host interface module110provides an interface to connect with a host device or system. The host interface module110operates in accordance with a communication protocol, including but not limited to, Serial Advanced Technology Attachment (SATA) Revision 1.x, SATA Revision 2.x, SATA Revision 3.x, and any other type of communication protocol.

The buffer120provides temporary storage to the SSD102in one embodiment of the invention. The buffer includes Synchronous Dynamic Random Access Memory (SDRAM), Dynamic Random Access Memory (DRAM), RAMBUS Dynamic Random Access Memory (RDRAM), and/or any other type of random access memory device.

The controller130has logic to facilitate access to the memory modules0-3and enables wear leveling of the memory modules0-3140,142,144, and146in one embodiment of the invention. The controller130partitions or separates the memory modules0-3140,142,144, and146into logical bands and physical bands and performs wear leveling by relocating static content in the logical bands to the physical bands that have an erase count that exceeds an average erase count of all the physical bands.

In one embodiment of the invention, the memory modules0-3140,142,144, and146include, but are not limited to, NAND flash memories, and memories that have a limited number of write or erase cycles. The number of memory modules shown inFIG. 1is not meant to be limiting and in other embodiments of the invention, there can be more or less than four memory modules.

FIG. 2illustrates an arrangement200of a solid state drive102in accordance with one embodiment of the invention. For clarity of illustration,FIG. 2is discussed with reference toFIG. 1. In one embodiment of the invention, the controller130segregates or divides the memory modules0-3140,142,144, and146into a logical area and a physical area.

The logical area is illustrated with logical area (L-area)1221, L-area2222, L-area3223, and L-area4224. In one embodiment of the invention, the logical area is divided or granulized into smaller units or elements that matches the size of a logical band (L-band). The L-bands210has L-band1(L1) to L-band22(L22). In one embodiment of the invention, the size of each L-band is the size of an erase block that has one or more pages. The host usage of each L-band is tracked by the controller130in one embodiment of the invention. In another embodiment of the invention, a firmware or software can loaded to the controller130to track the host usage of each L-band.

A L-band with a relatively high rate of host writes is considered dynamic and a L-Band with a relatively low rate of host writes is considered static in one embodiment of the invention. In one embodiment of the invention, a L-band is considered dynamic when its rate of host writes is higher than the average rate of host writes of all the L-bands. In another embodiment of the invention, a L-band is considered static when its rate of host writes is lower than the average rate of host writes of all the L-bands. In one embodiment of the invention, the rate or frequency of the host writes to a particular L-band is an weighted average of the recent host writes to the particular L-band.

When a host write operation is performed on a particular L-band, it causes the particular L-band to become dynamic. When no host write operations are performed on the particular L-band, a slow periodic decay function causes the particular L-band to become static. The static L-bands235and the dynamic L-bands230shows a list of static L-bands and dynamic L-bands respectively. A particular L-band can move from the static L-bands235to the dynamic L-bands230and vice-versa.

For example, in one embodiment of the invention, L-area1221is made up of five L-bands (L1-L5). When a host writes data to the L-area1221, the controller130sets the five L-bands associated with the L-area1221as dynamic. The L1-L5are moved from the list of static L-bands235to the list of dynamic L-bands230. In another example, the L-area2222is made up of four L-bands (L6-L9). When no data is written to the L-area2222, the controller130sets the four L-bands associated with the L-area2222to be static based on a slow periodic decay function. The L6-L9are moved from the list of dynamic L-bands230to the list of static L-bands235. In one embodiment of the invention, the controller130checks after a periodic or fixed number of machine cycles if the logical area has been assessed. Based on the slow periodic decay function, the controller130determines when to set the L-bands of the logical area as static.

The method of classifying the L-bands210is not meant to be limiting and one of ordinary skill in the relevant will readily appreciate that other methods of classification can be used without affecting the workings of the invention.

The physical area is also divided or granulized into smaller units or elements shown as physical bands (P-bands)240. The physical area is illustrated with twenty-two P-bands (P1to P22). The contents in the P-band1(P1) to P6, P9to P10, and P13to P16are clean or have been erased. P7to P8, P11-P12and P17to P22are utilized to store content. In one embodiment of the invention, the size of each P-band is an erase block that has one or more pages.

The controller130sets an erase counter for each P-band and each erase count of each P-band is incremented with every erasing operation of each P-band in one embodiment of the invention. The erase counter for each P-band describes the number of times that a particular P-Band has been erased and it allows the controller130to track or monitor the usage pattern of each P-band. The erase count in each P-band is illustrated in brackets. For example, the P1has an erase count of 142.

In one embodiment of the invention, the controller130creates a clean list250based on the erase counters of the P-bands240. The clean list250is made up of a list of the index of the P-bands that are clean or have been erased and is sorted by the erase count of the P-bands. For example, P1is inserted at the top of the clean list250as it has the highest erase count among the P-bands that are clean or have been erased. P10is inserted at the end of the clean list250as it has the lowest erase count among the P-bands that are clean or have been erased. The end of the clean list250is termed as the cold end of the clean list, and the end of the clean list250is termed as the hot end of the clean list.

The allocation of a particular P-band from the clean list250is based on the expected usage of the particular P-band in one embodiment of the invention. For example, in one embodiment of the invention, the allocation of a new P-band in which to write or store new host information always occurs from the cold end of the clean list250. In another embodiment of the invention, when a dynamic L-band is required to be stored, the dynamic L-band is mapped to the P-band at the coldest end of the clean list250. When a static L-band is required to be stored, the static L-band is mapped to the P-band at the hottest end of the clean list250. In yet another embodiment of the invention, the P-band at the middle of the clean list250can be used based on other storage requirements. By allocating P-bands in the clean list250based on their expected usage, the controller130can perform wear leveling of the memory modules0-3140,142,144, and146that does not add any cost in the write amplification.

In one embodiment of the invention, the controller130determines the average erase count, minimum erase count and the maximum erase count from the clean list250. The minimum and maximum erase counts are set as the lowest and highest erase counts in the clean list250respectively in one embodiment of the invention.

In one embodiment of the invention, the controller determines or calculates the difference between the average erase count and the minimum erase count and checks if the difference is greater than a threshold. When the threshold is exceeded, the P-band at the end of the clean list250is considered to be too cold. The controller130performs wear leveling by mapping the cold static content to the hottest P-band in the clean list250in one embodiment of the invention. Using the clean list250as an example, the controller130performs wear leveling by moving or relocating the static logical content to the P1that has an erase count142. By doing so, the controller130ensures that P-bands with the lowest or minimum erase count are circulated through normal usage, instead of being stuck with static content.

In another embodiment of the invention, the controller determines or calculates the difference between the maximum erase count and the average erase count and checks if the difference is greater than a threshold. When the threshold is exceeded, the P-band at the top of the clean list250is considered to be too hot, i.e., the erase count of the P-band with the maximum erase count should not be increased anymore. The controller130performs wear leveling by mapping L-bands with static content to the P-band with the maximum erase count. Using the clean list250as an example, the controller130performs wear leveling by moving or relocating one of the static L-bands associated with L-area1221to the P1with erase count142. By doing so, the P1with erase count142or maximum erase count has a smaller chance of being erased again as it is holding static content. The wear leveling techniques of the controller allows the SSD102to be written more without suffering any endurance-related reliability problems in one embodiment of the invention.

In one embodiment of the invention, the controller130does not need the clean list250and creates an array of the erase counts in the120. One of ordinary skill in the relevant art will readily appreciate that other methods of tracking the erase counters can be used without affecting the workings of the invention.

FIG. 3Aillustrates a flow chart300of the steps to perform wear leveling in a solid state drive102in accordance with one embodiment of the invention. For clarity of illustration,FIG. 3Ais discussed with reference toFIGS. 1 and 2. The flow300has two main phases: the initialization phase302and the wear leveling phase304. During the initialization phase302, the controller130tracks the host usage of the L-bands210in step350. In one embodiment of the invention, every L-band is initialized as static when the SSD102is powered up or enabled. In another embodiment of the invention, the static/dynamic state of every L-band is stored in a non-volatile storage and is restored from the non-volatile storage when the SSD102is powered up or enabled. When a particular L-band is written or accessed by a host machine, the controller130sets the particular L-band as dynamic. The particular L-band is reverted back to static based on a slow decay function when no further write operations are performed on the particular L-band.

In step352, the controller130tracks the erase count of each P-band. In one embodiment of the invention, the erase count of each P-band is stored in a non-volatile manner. This allows the controller130to keep a current record of the erase count of each P-band even when the SSD102is powered off or disabled. In step354, the controller130populates a clean list250from non-volatile storage that tracks the erase counts of the P-bands240by indexing the P-band number. The order of the clean list250is based on the erase counts of the P-bands240.

The wear leveling phase304begins with step315where the controller130determines the minimum erase count, maximum erase count and average erase count from the clean list250. In step320, the controller130checks if the coldest region or end in the clean list250is too far from the average erase count. In one embodiment of the invention, the controller130performs step320by checking if the difference between average erase count and the minimum erase count is greater than a threshold. If yes, the flow300goes to step3B. If no, the flow checks if the hottest region or end in the clean list250is too far from the average erase count. In one embodiment of the invention, the controller130performs step320by checking if the difference between maximum erase count and the average erase count is greater than a threshold. If yes, the flow300goes to step3C. If no, the flow300ends.

FIG. 3Billustrates a flow chart330of the steps to perform wear leveling in a solid state drive102in accordance with one embodiment of the invention. For clarity of illustration,FIG. 3Bis discussed with reference toFIGS. 1,2and3A. In step322, the controller130checks if the coldest region or part in the clean list250is holding static content. In one embodiment of the invention, the controller130performs step322by checking if the logical area associated with the P-band with the minimum erase count in the clean list250is holding static content, i.e., the L-band of the logical area is static. If yes, the controller130map the static content into the P-band with the highest erase count in the clean list250in step326and the flow330goes to step360. If no, the controller130selects another P-band with a low erase count and relocates the content of the logical area associated with the P-band with the minimum erase count to the selected P-band and the flow goes to step360. This allows the coldest region of the clean list250to be released so that it receives more erase cycles.

FIG. 3Cillustrates a flow chart340of the steps to perform wear leveling in a solid state drive in accordance with one embodiment of the invention. For clarity of illustration,FIG. 3Cis discussed with reference toFIGS. 1,2and3A. In step332, the controller130checks if there are any static content, i.e., whether there are any static L-bands. If yes, the controller130maps the static content into the P-band with the highest erase count in the clean list250in step334and the flow330ends. If no, the controller130looks for the next sequential logical region with valid data in step336. In step338, the controller130maps the valid data of the next sequential logical region into the P-band with the highest erase count in the clean list250and the flow330ends. This allows the controller130to manage host workloads where the number of static regions is insufficient and it maps the logical regions to the physical regions using a circular model that causes all physical bands to rotate thru the clean list250and be sorted accordingly.

FIG. 4illustrates a system400to implement the methods disclosed herein in accordance with one embodiment of the invention. The system400includes, but is not limited to, a desktop computer, a laptop computer, a netbook, a notebook computer, a personal digital assistant (PDA), a server, a workstation, a cellular telephone, a mobile computing device, an Internet appliance or any other type of computing device. In another embodiment, the system400used to implement the methods disclosed herein may be a system on a chip (SOC) system.

The processor410has a processing core412to execute instructions of the system400. The processing core412includes, but is not limited to, pre-fetch logic to fetch instructions, decode logic to decode the instructions, execution logic to execute instructions and the like. The processor410has a cache memory416to cache instructions and/or data of the system400. In another embodiment of the invention, the cache memory416includes, but is not limited to, level one, level two and level three, cache memory or any other configuration of the cache memory within the processor410.

The memory control hub (MCH)414performs functions that enable the processor410to access and communicate with a memory430that includes a volatile memory432and/or a non-volatile memory434. The volatile memory432includes, but is not limited to, Synchronous Dynamic Random Access Memory (SDRAM), Dynamic Random Access Memory (DRAM), RAMBUS Dynamic Random Access Memory (RDRAM), and/or any other type of random access memory device. The non-volatile memory434includes, but is not limited to, NAND flash memory, phase change memory (PCM), read only memory (ROM), electrically erasable programmable read only memory (EEPROM), or any other type of non-volatile memory device.

The memory430stores information and instructions to be executed by the processor410. The memory430may also stores temporary variables or other intermediate information while the processor410is executing instructions. The chipset420connects with the processor410via Point-to-Point (PtP) interfaces417and422. The chipset420enables the processor410to connect to other modules in the system400. In one embodiment of the invention, the interfaces417and422operate in accordance with a PtP communication protocol such as the Intel® QuickPath Interconnect (QPI) or the like.

The chipset420connects to a display device440that includes, but is not limited to, liquid crystal display (LCD), cathode ray tube (CRT) display, or any other form of visual display device. In one embodiment of the invention, the processor410and the chipset420are merged into a SOC. In addition, the chipset420connects to one or more buses450and455that interconnect the various modules474,460,462,464, and466. Buses450and455may be interconnected together via a bus bridge472if there is a mismatch in bus speed or communication protocol. The chipset420couples with, but is not limited to, a non-volatile memory460, a storage device(s)462, a keyboard/mouse464and a network interface466. In one embodiment of the invention, the solid state drive102is the storage device462.

While the modules shown inFIG. 4are depicted as separate blocks within the system400, the functions performed by some of these blocks may be integrated within a single semiconductor circuit or may be implemented using two or more separate integrated circuits. For example, although the cache memory416is depicted as a separate block within the processor410, the cache memory416can be incorporated into the processor core412respectively. The system400may include more than one processor/processing core in another embodiment of the invention.

The methods disclosed herein can be implemented in hardware, software, firmware, or any other combination thereof. Although examples of the embodiments of the disclosed subject matter are described, one of ordinary skill in the relevant art will readily appreciate that many other methods of implementing the disclosed subject matter may alternatively be used. In the preceding description, various aspects of the disclosed subject matter have been described. For purposes of explanation, specific numbers, systems and configurations were set forth in order to provide a thorough understanding of the subject matter. However, it is apparent to one skilled in the relevant art having the benefit of this disclosure that the subject matter may be practiced without the specific details. In other instances, well-known features, components, or modules were omitted, simplified, combined, or split in order not to obscure the disclosed subject matter.

The term “is operable” used herein means that the device, system, protocol etc, is able to operate or is adapted to operate for its desired functionality when the device or system is in off-powered state. Various embodiments of the disclosed subject matter may be implemented in hardware, firmware, software, or combination thereof, and may be described by reference to or in conjunction with program code, such as instructions, functions, procedures, data structures, logic, application programs, design representations or formats for simulation, emulation, and fabrication of a design, which when accessed by a machine results in the machine performing tasks, defining abstract data types or low-level hardware contexts, or producing a result.

The techniques shown in the figures can be implemented using code and data stored and executed on one or more computing devices such as general purpose computers or computing devices. Such computing devices store and communicate (internally and with other computing devices over a network) code and data using machine-readable media, such as machine readable storage media (e.g., magnetic disks; optical disks; random access memory; read only memory; flash memory devices; phase-change memory) and machine readable communication media (e.g., electrical, optical, acoustical or other form of propagated signals—such as carrier waves, infrared signals, digital signals, etc.).

While the disclosed subject matter has been described with reference to illustrative embodiments, this description is not intended to be construed in a limiting sense. Various modifications of the illustrative embodiments, as well as other embodiments of the subject matter, which are apparent to persons skilled in the art to which the disclosed subject matter pertains are deemed to lie within the scope of the disclosed subject matter.