# Patent

## Title
Data storage system with dynamic erase block grouping mechanism and method of operation thereof

## Abstract

Systems, methods and/or devices are used to enable dynamic erase block grouping. In one aspect, the method includes (1) maintaining metadata for each erase block of a plurality of erase blocks in a data storage system, wherein a respective metadata for a respective erase block includes one or more characteristics of the respective erase block, (2) allocating a set of erase blocks, of the plurality of erase blocks, as unassociated erase blocks, (3) selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics, and (4) grouping the two or more unassociated erase blocks with similar characteristics to form a super block.

## Background
RELATED APPLICATION
This application is a continuation of U.S. application Ser. No. 14/334,350, filed Jul. 17, 2014, which claims priority to U.S. Provisional Patent Application Ser. No. 61/863,419, filed Aug. 7, 2013, entitled “Data Storage System with Dynamic Erase Block Grouping Mechanism and Method of Operation Thereof,” which are hereby incorporated by reference in their entirety.


TECHNICAL FIELD
The present invention relates generally to a data storage system and more particularly to a system with a dynamic erase block grouping mechanism.
BACKGROUND
Data storage, often called storage or memory, refers to computer components and recording media that retain digital data. Data storage is a core function and fundamental component of consumer and industrial electronics, especially devices such as computers, televisions, cellular phones, mobile devices, and digital video cameras.
Recently, forms of long-term storage other than electromechanical hard disks have become feasible for use in computers. NOT-AND (NAND) flash is one form of non-volatile memory used in solid-state storage devices. The memory cells are arranged in typical row and column fashion with circuitry for accessing individual cells. The memory transistors of those cells are placed to store an analog value that can be interpreted to hold two logical states in the case of Single Level Cell (SLC) or more than two logical states in the case of Multi Level Cell (MLC).
A flash memory cell is light in weight, occupies very little space, and consumes less power than electromechanical disk drives. Construction of a storage system with this type of memory allows for much higher bandwidths and input/output operations per second (IOPS) than typical electromechanical disk drives. More importantly, it is especially rugged and can operate at a much high temperature range. It will withstand without adverse effects repeated drops, each of which would destroy a typical electromechanical hard disk drive. A problem exhibited by flash memory is that it tends to have a limited life in use.
Thus, a need still remains for better data management devices. In view of the increasing demand for data management devices, it is increasingly critical that answers be found to these problems. In view of the ever-increasing commercial competitive pressures, along with growing consumer expectations and the diminishing opportunities for meaningful product differentiation in the marketplace, it is critical that answers be found for these problems. Additionally, the need to reduce costs, improve efficiencies and performance, and meet competitive pressures adds an even greater urgency to the critical necessity for finding answers to these problems.
Solutions to these problems have been long sought but prior developments have not taught or suggested any solutions and, thus, solutions to these problems have long eluded those skilled in the art.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a data storage system in an embodiment of the present invention.
FIG. 2 is an example of a memory diagram of the data storage system.
FIG. 3 is an example of a super block configuration.
FIG. 4 is an example of the erase block selector module.
FIG. 5 is a first example of the configuration of one of the super blocks.
FIG. 6 is a second example of the configuration of one of the super blocks.
FIG. 7 is a flow chart of a method of operation of the data storage system in a further embodiment of the present invention.



DETAILED DESCRIPTION
The various implementations described herein include systems, methods and/or devices used to enable dynamic erase block grouping. Some implementations include systems, methods and/or devices to select two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics and group the two or more unassociated erase blocks with similar characteristics to form a super block.
More specifically, some embodiments include a method of operation of a data storage system. In some embodiments, the method includes (1) maintaining metadata for each erase block of a plurality of erase blocks in the data storage system, wherein a respective metadata for a respective erase block includes one or more characteristics of the respective erase block, (2) allocating a set of erase blocks, of the plurality of erase blocks, as unassociated erase blocks, (3) selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics, and (4) grouping the two or more unassociated erase blocks with similar characteristics to form a super block.
In some embodiments, the one or more characteristics of the respective erase block include at least one characteristic selected from the group consisting of age information, wear statistics, physical location, and operation parameters.
In some embodiments, the metadata is maintained in a persistent storage mechanism.
In some embodiments, the super block includes two or more unassociated erase blocks from different memory die of the data storage system.
In some embodiments, selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes selecting two or more unassociated erase blocks with similar ages.
In some embodiments, selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes (1) selecting a first unassociated erase block from a first die of the data storage system, (2) selecting a second unassociated erase block from a second die of the data storage system, and (3) forgoing selection of a third unassociated erase block from a third die of the data storage system, wherein the third die is relatively worn in comparison to the first die and second die.
In some embodiments, the method further includes (1) aggregating metadata from the two or more unassociated erase blocks of the super block, and (2) storing the aggregated metadata as metadata for the super block.
In some embodiments, the method further includes (1) selecting one or more erase blocks, in accordance with the one or more characteristics of the one or more erase blocks, for recycling, (2) recycling the selected one or more erase blocks, and (3) allocating the recycled one or more erase blocks as unassociated erase blocks.
In some embodiments, the method further includes selecting, from the super block, a relatively old erase block to store parity information.
In some embodiments, the method includes enforcing a minimum amount of dwell time for the unassociated erase blocks, wherein dwell time is the amount of time between operations on a respective erase block.
In another aspect, any of the methods described above are performed by a data storage system, the data storage system including (1) one or more processors, and (2) memory storing one or more programs to be executed by the one or more processors, the one or more programs comprising instructions for performing or controlling performance of any of the methods described herein.
In yet another aspect, some embodiments include a non-transitory computer readable storage medium, storing one or more programs configured for execution by one or more processors of a data storage system, the one or more programs including instructions for performing or controlling performance of any of the methods described herein.
The following embodiments are described in sufficient detail to enable those skilled in the art to make and use the invention. It is to be understood that other embodiments would be evident based on the present disclosure, and that system, process, or mechanical changes may be made without departing from the scope of the present invention.
In the following description, numerous specific details are given to provide a thorough understanding of the invention. However, it will be apparent that the invention may be practiced without these specific details. In order to avoid obscuring the present invention, some well-known circuits, system configurations, and process steps are not disclosed in detail.
The drawings showing embodiments of the system are semi-diagrammatic and not to scale and, particularly, some of the dimensions are for the clarity of presentation and are shown exaggerated in the drawing FIGs.
Where multiple embodiments are disclosed and described having some features in common, for clarity and ease of illustration, description, and comprehension thereof, similar and like features one to another will ordinarily be described with similar reference numerals. The embodiments have been numbered first embodiment, second embodiment, etc. as a matter of descriptive convenience and are not intended to have any other significance or provide limitations for the present invention.
The term “module” referred to herein can include software, hardware, or a combination thereof in the present invention in accordance with the context in which the term is used. For example, the software can be machine code, firmware, embedded code, and application software. Also for example, the hardware can be circuitry, processor, computer, integrated circuit, integrated circuit cores, a microelectromechanical system (MEMS), passive devices, environmental sensors including temperature sensors, or a combination thereof.
The term “bit error rate” (BER) referred to herein is defined as a number of incorrect bits in a data stream stored in a memory device including NAND. The term “error correction code” referred to herein is defined as parity data generated over a set of data grouped into a code word.
The term “erase block” referred to herein is defined as a group of pages, which is the smallest number of pages that are erased at one time. The term “memory page” referred to herein is defined as a memory component within an erase block that is programmed as an individual unit. The memory page is a smallest group of data bytes that are read from or written to in an erase block.
The term “retention” referred to herein is defined as an ability of memory cells to retain the programmed or correct information. Retention refers to an amount of correct data after a given period, which is a time when a drive is powered, not powered, or a combination thereof. The term “program erase cycle” (PE cycle) referred to herein is defined as a base level operation of how data is replaced within an erase block. For example, a memory device including NAND and other memory types can have a limited number of useful PE cycles.
The term “age” referred to herein indicates how long a storage system or a memory component has existed or has been in operation. For example, the age can be based on a number of erase cycles, how long it has been since the last time an erase block was written, an average BER an erase block is yielding, a temperature at which a device has been run, or a combination thereof.
The term “recycling” or “recycle” referred to herein is defined as moving data from one flash page to another flash page, for the purposes of either freeing up erase blocks to write new host data, or to ensure that the data on the erase block is preserved. The term “endurance” referred to herein is defined as a number of operations a memory device including NAND flash device tolerates over a given period of operational life of a storage system including a solid-state disk drive (SSD).
The term “young erase block” referred to herein is defined as an erase block with a low age, either in absolute terms or relative to other erase blocks on the drive. The term “old erase block” referred to herein is defined as an erase block with a high age, either in absolute terms or relative to other erase blocks on the drive.
The term “dwell time” referred to herein is defined as the amount of time that an erase block experiences in between erase operations. The term “unassociated erase block” referred to herein is defined as an erase block that is not part of a larger grouping of erase blocks. An unassociated erase block is part of the spare pool.
Referring now to FIG. 1, therein is shown a block diagram of a data storage system in an embodiment of the present invention. The data storage system includes a memory array coupled to a controller via a memory bus.
The controller is a processing unit for managing the storage and retrieval of data in the memory array. The controller can be an embedded processor, control logic, or a combination thereof. The controller can transfer stored data from the memory array to a host device.
The memory array is a non-volatile memory unit for storing data. The memory array can include NAND flash memory arrays, NOR flash memory arrays, other non-volatile memory arrays, or a combination thereof.
The memory array can be formed with memory dice. The memory dice are semiconductor devices for storing information. The memory dice are the minimum unit that can independently execute commands and report status. For example, the memory dice can be flash memory devices, NAND flash memory chips, NOR flash memory devices, or a combination thereof.
The memory bus is a communication channel. The memory bus conveys data and control information between the controller and the memory array.
The memory dice can include a cell array. The cell array is a set of non-volatile flash memory cells for storing data. For example, the cell array can include a single-level cell flash memory, a multi-level cell flash memory, a mixed functionality cell, or a combination thereof.
The cell array can include memory cells. The memory cells are electronic structures for storing information. For example, the memory cells can be floating gate flash memory devices.
The memory array can include an array logic unit coupled to the cell array. The array logic unit is circuitry to provide addressing, data transfer and sensing, and other support to control the memory array for saving and retrieving information from the cell array.
The controller can include a memory interface coupled to the memory array. The memory interface can include circuitry for communicating with the memory array over the memory bus.
The controller can include a control unit coupled to the memory interface and a host interface. A read only memory can be coupled to the control unit. A random access memory can be coupled to the control unit and to the read only memory. The random access memory can be utilized as a buffer memory for temporary storage of data being written to or read from the memory array.
The random access memory can include a controller database. The controller database is a data storage and retrieval system. The controller database can store information about the data storage system.
The read only memory can include a software for operating the control unit. The software is executable code for implementing the intelligence of the data storage system.
The controller can include an error correction code unit coupled to the control unit. The error correction code unit is a processing hardware for calculating an error correction code value that can be used to detect errors, correct errors, or a combination thereof in data stored or transmitted from the memory array.
The error correction code unit can calculate one or more error correction code values using different methods such as a Reed-Solomon code, a Hamming code, a Bose-Chauduri-Hocquenghem (BCH) code, or a combination thereof. Although the error correction code unit is a dedicated element for calculating error correction codes, it is understood that error correction codes can also be calculated in other ways, such as using the control unit to calculate error correction codes.
The controller can include the host interface coupled to the host device via a digital connection. The host device is a computing device that can use the data storage system for storing data. For example, the host device can be a laptop computer, a desktop computer, a server, a smart phone, or a combination thereof.
The host interface can communicate commands and data between the host device and the controller with the digital connection. For example, the host interface can detect a connection to the host device and generate command based on the connection to the host device.
The data storage system can be connected to the host device with the digital connection. The digital connection is a communication link for transferring digital information between the data storage system and the host device.
The digital connection can be formed in a variety of ways. For example, the digital connection can be a universal serial bus (USB) connection for transferring information. In another example, the digital connection can be a wireless communication mechanism, such as Wireless Fidelity (Wi-Fi), infrared communication mechanism, optical communication system, near field communication system, or a combination thereof.
Referring now to FIG. 2, therein is shown an example of a memory diagram of the data storage system of FIG. 1. The memory diagram shows the data storage system including memory pages, memory blocks, and a data register. The data storage system can be formed using the memory dice of FIG. 1. The memory dice include the memory cells of FIG. 1 for storing data.
The data storage system can have a variety of storage capacities determined by the number of the memory dice used to form the data storage system. For example, the data storage system can include 2 gigabytes (GB) of flash memory, 8 GB, 16 GB, or other memory sizes.
The data storage system can include a number of the memory blocks. The memory blocks are portions of the memory array of FIG. 1. For example, the data storage system with capacity of 2 GB can have 4,096 of the memory blocks.
The memory blocks can include erase blocks. The erase blocks are the smallest unit of memory that can be erased as a single entity at one time.
Each of the erase blocks can have a program erase cycle count. When one of the erase blocks is erased, then the program erase cycle count can be incremented. The program erase cycle count can represent the age or level of wear of one of the memory blocks. The program erase cycle count is a measure of the level of usage within one of the erase blocks. The flash memory devices, such as NAND flash, have a limited number of useful program erase cycles.
The memory blocks can be divided into the memory pages. The memory pages are the smallest group of data bytes that can be read or written in the data storage system. The memory pages are the smallest addressable unit of memory that can be programmed. For example, each of the memory blocks can have 64 of the memory pages.
The memory pages include a data area and a spare area. The data area is a group of memory cells used to store user data. The data area can be various sizes. For example, the data area of one of the memory pages can be bytes.
The spare area is a group of memory cells to store metadata about the data area. For example, the spare area can include error correction code information, status information, or a combination thereof. The spare area can have a variety of sizes. For example, the spare area can be bytes. The memory pages can have a size of bytes for the data area and the spare area.
The memory array of FIG. 1 can be updated by erasing the memory blocks and programming new data into the memory blocks that have been erased. Programming the memory blocks writes data into the memory blocks.
Reading one of the memory pages can result in reading errors where one or more of the bits in the memory pages are incorrect. The number of individual bit errors in a stream of data is described as a bit error rate. The bit error rate is defined as numbers of incorrect bits in a data stream stored in the data storage system. The incorrect bits can be detected within a code word protected by an error-correcting code.
The code word refers to a group of data bytes covered by a single instance of multiple ECC parity words. The error-correcting code refers to parity or redundant data generated over a set of host or user data grouped into the code word. The bit error rate is the number of incorrect bits in a data stream stored in the flash memory.
The data storage system can be divided into two physical planes. The planes can include all odd numbered blocks and all even numbered blocks, respectively. Configuring the data storage system into multiples of the planes can allow concurrent access to each plane to increase performance. With the data storage system configured with two of the planes, the data storage system can perform two concurrent reads, perform two concurrent erase operations, program two pages concurrently, or a combination thereof. Each individual operation can be performed on the memory blocks of one of the planes. The data storage system is described with two of the planes, but it is understood that more than two planes can be configured.
Referring now to FIG. 3, therein is shown an example of a super block configuration. The super blocks can be formed from a pool of the erase blocks that are unassociated with other ones of the erase blocks. The data storage system can operate on one of the super blocks as a unit.
The pool of the unassociated erase blocks can form one of the super blocks. Each of the erase blocks in the pool of unassociated erase blocks can have erase block metadata including age information, wear statistics, physical location, operation parameters, or a combination thereof. The individual erase block metadata is aggregated when the data storage system creates one of the super blocks and the super block metadata.
The data storage system maintains an erase block pools for the unassociated erase blocks for each of the memory dice or each of the planes within one of the memory dice. The erase block pool can be sorted by an important metric, such as age. This allows an erase block selector to construct the super blocks that will improve the wear leveling on the data storage system. The erase block selector is a module having the intelligence to create each of the super blocks based on a set of rules and criteria.
The data storage system must leave some of the erase blocks empty in a spare pool, so it has space to write new and recycled data and the erase block metadata. The erase block pool is a group of the erase blocks that are unassociated with other of the erase blocks. By keeping some of the erase blocks unassociated, the data storage system can choose when and how to group them together.
The erase block metadata can be stored in the controller database. The erase block metadata can include information for every one of the erase blocks in the drive, including the unassociated erase blocks. The erase block metadata can include the erase block age for each of the erase blocks.
For the erase blocks in the unassociated list, the erase block metadata is kept in non-volatile memory. For example, the erase block metadata for unassociated erase blocks can be stored in an area of volatile memory that can be guaranteed to commit to NAND memory upon detection of a power loss event. When the erase blocks are grouped together into one of the super blocks, the erase block metadata is aggregated for one of the super blocks and written out to the super blocks as the super block metadata.
Referring now to FIG. 4, therein is shown an example of the erase block selector module. The erase block selector can create the super blocks from the unassociated pool of the erase blocks.
The erase block selector can use lists of unassociated erase blocks lists sorted by the age of the erase blocks to construct the super blocks using erase blocks from different one of the memory dice. For example, the age of one of the erase blocks is a number having an increasing value for indicating higher wear.
The erase block selector can configure the erase blocks to improve the life of the drive by creating the super blocks. Grouping the erase blocks into the super blocks can reduce the amount of data required to manage the data storage system and improve performance. The erase block selector can aggregate the erase block metadata to form the super block metadata.
It has been found that by providing the erase block selector with information on the age of each of the unassociated erase blocks can allow the erase block selector to improve the lifespan of the data storage system by using “per-erase block age metadata” and the notion of unassociated erase blocks when forming the super blocks. The erase block selector can reduce overall wear, minimize data traffic, and increase performance of the data storage system by optimizing the configuration of the super blocks.
The erase block selector can optimize the configuration of the super blocks in a variety of ways. The erase block selector can configure the super blocks by grouping the erase blocks having similar values for the age, selecting the erase blocks having the youngest age together, forming the super blocks based on the roles of the erase blocks, configuring the super blocks based on the dwell time, configuring the data storage system to support multiple concurrent operations, selecting the erase blocks based on the physical topology of the memory dice, or a combination thereof.
The erase block selector can form groups of the erase blocks having similar values of the erase block age. This allows the data storage system to make further wear-leveling decisions for each of the super blocks to improve the life of the data storage system.
The data storage system can measure different types of age in a variety of ways. For example, the super block age can be the average age of the erase blocks of one of the super blocks. In another example, the memory dice age can be average or maximum age of the erase blocks for one of the memory dice. In yet another example, the drive age can be the average or maximum age of the erase blocks of the data storage system.
The memory element age can have varying impacts on the performance of the data storage system. For example, one of the super blocks having mostly the erase blocks have low values for the age should get more of the program erase cycles applied to it than another of the super blocks having mostly the erase blocks having larger values for the age. Using young erase blocks can increase the overall effective life of the data storage system.
The erase block age indicates the level of wear for one of the erase blocks. The erase block age can be based on a number of program erase cycles, how long it has been since the last time an erase block was written, an average values of a bit error rate one of the erase blocks is yielding, a temperature at which a device has been run, or a combination thereof.
Similarity is a measure of how close two or more of the erase blocks are in terms of a measuring parameter. For example, two or more of the erase blocks can be similar if the age of each of the erase blocks is within an age range threshold of one another. The age measurement can be any of a variety of data types as shown above.
In another example, similarity can be based on categorizing some of the erase blocks, such as grouping the erase blocks having the lowest 16 values of the erase block age. In yet another example, the erase blocks can be grouped by similarity if the age of each of the erase blocks is within a certain percentage of one another, such as with 20% of one another. In another example, the erase blocks can be grouped by similarity if the bit error rate of each of the erase blocks is within a threshold value of one another.
During the formation of one of the super blocks, the data storage system can try to completely fill the super blocks with the erase blocks that fulfill the criteria. However, it is understood that one of the super blocks can be formed with a different number of the erase blocks if an insufficient number of the erase blocks are similar to one another. The super blocks can be formed by combining some of the erase blocks using different criteria.
The erase block selector can allocate the erase blocks having the lowest values for the age first, while allocating the erase blocks having larger values for the age remain in the unassociated pools for a longer time. By evenly distributing wear by applying more write operations to the erase blocks having a lower value for the age, the erase blocks with a higher value for age can be spared from excessive write operations.
The super blocks can be homogenous by having all of the erase blocks having similar criteria. However, it is understood that the super blocks can be heterogeneous by having some of the erase blocks in one of the super blocks with different criteria that are not similar. For example, one of the erase blocks can have a higher value for the age than some of the other ones of the erase blocks.
The erase block selector can allocate some of the erase blocks to one of the super blocks based on roles. The roles are a type of usage descriptor for the erase blocks.
The data storage system can include a variety of the roles. For example, the roles can include parity blocks, error correction code blocks, host data blocks, metadata blocks, a priori types, hot usage, cold usage, frequency, or a combination thereof. The roles can be based on relative or absolute ages.
The erase blocks of one of the super blocks can be homogenous and have similar types of the roles. However, it is understood that the erase blocks of one of the super blocks can be heterogeneous and have different types of the roles. For example, the super blocks can include some of the erase blocks having host data roles and parity roles.
For example, if the super blocks include parity protection, the erase block selector may choose a relatively old one of the erase blocks to store the parity information, since the parity information is accessed infrequently and thus would suffer few read-disturb errors or read retries. The erase block selector can ensure that the erase blocks that are unassociated are given additional amount of the dwell time that they each need to store data reliably once they are written.
Dwell time is the amount of time between operations on one of the erase blocks. Dwell time can be the amount of time between erase operations. It has been discovered that enforcing a minimum amount of the dwell time can reduce the bit error rate for reading one of the erase blocks by allowing the insulators of the floating gates forming the flash memory cells to heal between operations.
The minimum amount of the dwell time can vary based on the technology used to fabricate the memory dice. Each different flash technology and generation can have different requirements for the dwell time. The minimum value for the dwell time having the optimal results can be determined experimentally, by computer analysis, be provided by the manufacturer of the flash memory, be calculated, be estimated, or a combination thereof. Although timing flash memory operations for the minimum value of the dwell time can increase performance, it is understood that maximizing the value of the dwell time can increase performance and reduce the bit error rate for one of the erase blocks.
The dwell time can be determined in a variety of ways. For example, the dwell time can be estimated using a sequence number of one of the erase blocks. The sequence number can be a value indicating when one of the erase blocks was last accessed. The sequence number can be relative or absolute. For example, the sequence number for each of the erase blocks can be an incremented number for each serial operation performed on the erase blocks. The sequence number can indicate the order in which the erase blocks have been written.
The scope of the dwell time can be determined in a variety of ways. For example, the dwell time can be determined for each of the erase blocks, each of the super blocks, or a combination thereof. The dwell time of the super blocks can be based on the individual values of the dwell time for the erase blocks.
It has been discovered that letting the erase blocks have longer amount of the dwell time will improve their age characteristics, especially on worn flash memory dice. Thus, enforcing minimum amount of the dwell time and allowing the oldest of the erase blocks more of the dwell time will make the SSD last longer.
For some flash memory, there is a benefit to doing operations on multiple erase blocks within the memory dice at one time. For example, the memory dice may allow the data storage system to erase or program two of the erase blocks simultaneously if certain operational rules are satisfied.
The erase block selector can allocate the erase blocks to one of the super blocks to ensure that one of the super blocks is constructed to allow for these multiple-erase block operations. The super blocks can be configured to reside on a set of mutually exclusive memory dice to support multiple simultaneous operations.
For example, one of the super blocks can be configured to use the memory dice identified as units 0-7, which another of the super blocks can be configured to use the memory dice 8-15. Because the super blocks operate on mutually exclusive memory dice, two memory operations can be performed simultaneously without interference. In an illustrative example, the data storage system can erase one of the super blocks at the same time as writing information to another of the super blocks.
It has been discovered that configuring the super blocks to have mutually exclusive memory dice configurations can increase write performance by allowing multiple simultaneous write operations.
In another example, the super blocks can be configured horizontally across a number of channels in the flash memory device to increase performance. However, it is understood that the super blocks can be configured vertically with all of the erase blocks in one the channels.
The operational rules can be sets of conditions required for performing certain operations. For example, the operational rules can permit multiple write operations based on the configuration of the erase blocks in the super blocks. In another example, the operational rules can prevent multiple operations based on the configuration of the erase blocks.
The operational rules can be provided at a product level, as part of manufacturer level data, on a component level, or a combination thereof. The operational rules can be dynamic and change over time. The operational rules can be based on state information for the memory blocks, memory pages, the erase blocks, the super blocks, or groups of the super blocks.
The erase block selector can select some of the erase blocks based on the physical flash topology, in order to allow for more parallel operations. For example, the erase blocks for the super blocks can be selected to have mutually exclusive physical locations on different ones of the memory dice.
It has been discovered that configuring the erase blocks of the super blocks based on the physical location of the erase blocks can support protection from memory plane failure or memory die failure by using parity protection. The erase blocks can be configured based on a redundant array of inexpensive drives level zero (RAID-0) or RAID level one (RAID-1) depending on need. For example, the erase blocks of the super blocks can be arranged in a RAID-0 or a RAID-1 configuration for data recovery and performance.
Different configurations of striping and mirroring can be used to configure the erase blocks of the super blocks based on desired performance and data safety criteria. Such configuration can support the recovery of data due to the failure of one of the data planes, one of the memory dice, one of the erase blocks, a parity block, or a combination thereof. For example, the erase blocks of one of the super blocks can be configured in a 31:1 data parity ratio to protect 31 of the erase blocks having host data with one of the erase blocks having parity information for data recovery.
It has been found that an important aspect of this invention is ability of the erase block selector to choose erase blocks from the unassociated pool to use in one of the super blocks based on the super block's intended type of the roles in the data storage system.
For example, the erase block selector may choose to build one of the super blocks using some of the erase blocks having a lower values of the age to use for hot data or build one of the super blocks using some of the erase blocks having a higher value of the age for cold data. Hot data is data that is used frequently, while cold data is not used frequently. The erase block selector can form one of the super blocks with some of the erase blocks based on whether the super blocks will be used for host data or metadata.
The erase block selector can build some of the super blocks having varying sizes based on engineering need. For example, the super blocks can have less than a full complement of the erase blocks based on the age of the erase blocks, the status of the data channels, the physical configuration of each of the memory dice, the state of the memory elements, or a combination thereof. In another example, because individual flash memory dice vary in their wear capability based on manufacturing and other physical properties, the erase block selector may use the age information to skip certain flash die when building one of the super blocks.
The data storage system includes a number of functions within the erase block selector. One of the functions assembles drives with memory components that have been configures the erase blocks into the super blocks. Another of the functions groups component of similar or same characteristics and like or same roles during normal runtime operations on the data storage system as the system ages. Another of the functions determines the super block metadata by aggregating erase block metadata.
The functions described above provide a process, implemented in the elements of the data storage system that are different for specific applications or purposes. For example, the process can form the data storage system with the components or the non-volatile memory devices that are more capable and another group of the drives with the components that are less capable. The functions described above can build the data storage system that uses a predetermined wide range of component and system characteristics to help improve performance and operations.
The data storage system can reconfigure and recycle the memory elements, such as the erase blocks and the super blocks, based on the operational capabilities. The memory elements are continuously regrouped, recycled, or reformed into groups of the erase blocks and the super blocks to get better or improved aging, endurance, and reliability of the data storage system. In other words, the memory elements are not all treated or determined to be identical as they are being used during the runtime operations.
Functions or operations of the controller of the data storage system as described above can be implemented using modules. The functions or the operations of the controller can be implemented in hardware, software, or a combination thereof. The modules can be implemented using the control unit, the read only memory unit, the random access memory unit, the memory interface unit, the host interface unit, the ECC unit, or a combination thereof.
The data storage system is described with module functions or order as an example. The modules can be partitioned differently. Each of the modules can operate individually and independently of the other modules.
Further, information generated in one module can be used by another module without being directly coupled to each other. Yet further, the modules can be implemented as hardware accelerators (not shown) within the control unit or can be implemented as hardware accelerators in the controller or outside of the controller. The controller can be coupled to the memory array and the host. The control unit can be coupled to the host interface, the memory interface, the ECC unit, the read only memory, and the random access memory.
The physical transformation of determining the configuration of the bits in the super blocks of the data storage system results in movement in the physical world, such as people using the data storage system based on the operation the super blocks and the erase blocks. As the movement in the physical world occurs, the movement itself creates additional information that is converted back to assigning the user data and metadata for the super blocks. The use of the user data that is updated during the runtime operations of the data storage system can continue the movement in the physical world. For example, one of the users can move the data storage system between different hosts to transfer data bits that are encoded the erase blocks of the super blocks.
It has been found that using the erase block selector to form super blocks from the erase blocks having similar ages improves performance. Grouping the erase blocks into a homogenous type of the super blocks reduces wear and promotes even usage.
It has been discovered that forming the super blocks based on the erase blocks having similar roles improves performance and promotes even wear across the memory dice. Tailoring the individual erase blocks base on role can maximize the effective use of the erase blocks.
It has been discovered that forming the super blocks based on the physical location of the erase blocks to evenly spread out the erase blocks over multiple memory dice improves performance. By supporting parallel operations that do not interfere with one another allows more operations to be performed simultaneously to increase performance.
Referring now to FIG. 5, therein is shown a first example of the configuration of one of the super blocks. The super blocks can be grouped based on the age of the erase blocks.
The erase block selector can form one of the super blocks having N of the erase blocks. However, if some of the memory dice do not have any of the erase blocks with ages similar to the other ones of the erase blocks, then some of the memory dice can be skipped and a smaller one of the super blocks can be created.
It has been discovered that creating the super blocks with varying sizing can increase performance and efficiency by utilizing more of the available ones of the erase blocks. Forming the super blocks with a different number of similar erase blocks can effectively utilizing the available erase blocks. As flash memory dice variability increases, the ability to craft some of the super blocks based on the age becomes more valuable.
The erase blocks for one of the super blocks can be allocated based on the decision to recycle another of the super blocks. For example, if one of the super blocks requires more of the erase blocks having a certain age, then an existing one of the super blocks having similar values for the age can be recycled so the erase blocks of the new one of the super blocks can form the new one of the super blocks.
It has been discovered that device performance can be increased by recycling one of the super blocks that is not closely matched in age. Reforming one of the super blocks having more consistency and similarity increases performance and reduces wear.
The erase block metadata can be aggregated into the super block metadata when forming the super blocks. When the data storage system forms one of the super blocks, it can aggregate the erase block metadata for each of the erase blocks associated with the active one of the super blocks. The erase block metadata is associated with one of the super blocks but contains all the information needed to pull one of the super blocks apart again into the individual ones of the erase blocks components with all the individual values of the erase block metadata. The super block metadata is stored in the non-volatile NAND flash memory of the memory dice.
The super blocks can include a super block header and a super block footer. The super block header and the super block footer can be data storage areas for holding configuration information about the super blocks. The super block header and the super block footer can be stored in non-volatile memory, such as in the erase blocks.
The super block header and the super block footer can store the super block metadata. The super block metadata can include all of the erase block metadata from each of the erase blocks. The super block metadata can include information regarding the configuration of the super blocks such as list of the erase blocks, the age, general structural information, other a priori information about the hardware or software configuration, mapping information, LBA tables, physical to logical table information, performance information, or a combination thereof.
The super block metadata can be stored redundantly for data protection. The super block metadata can be stored in the super block header, the super block footer, one of the erase blocks, or a combination thereof. The super block metadata is stored in the non-volatile NAND flash memory die in a redundant fashion, so it can be preserved if one of the components of one of the super blocks becomes unusable, such as with a plane or die failure.
If one of the super blocks is used for a parity stripe, the super block metadata can provide the information needed to recover the lost data using parity. The data storage system can use a RAID-1 configuration to protect the data on in the super blocks and helps ensure that the data storage system can retrieve the information in the super blocks if any individual one of the erase blocks becomes unreadable.
It has been discovered that forming the super blocks having varying sizes improves efficiency and reduces errors. By maximizing the utilization of the erase blocks in the memory dice, more of the available erase blocks can be used reducing waste.
Referring now to FIG. 6, therein is shown a second example of the configuration of one of the super blocks. The super blocks can include the super block metadata including the erase block metadata. The super blocks can be configured across multiple of the memory dice. The super block metadata can be protected with RAID-1 to increase reliability for retrieving the super block metadata, offering protection before determining the type of association for each of the erase blocks.
The data storage system can include other aspects. The data storage system can leave some of the erase blocks in ungrouped pools as spare erase blocks or unassociated erase blocks, and group them together into the super blocks. The data storage system uses a persistent storage mechanism to store metadata about the unassociated erase blocks. The persistent storage mechanism can include the non-volatile NAND flash memory dice.
The data storage system sorts the unassociated erase blocks by criteria based on the erase block metadata to allow for grouping into one of the super blocks for improved wear leveling and performance. When the erase blocks are grouped into the super blocks, the erase block metadata for each of the erase blocks is aggregated in one of the super blocks to save space and endurance.
When the unassociated erase blocks are combined into one of the super blocks, the data storage system can use the erase block metadata to make informed decisions about how to build the super blocks for better wear and thus extend the drive's useful life.
For example, the data storage system can group the erase blocks with similar current or anticipated wear characteristics, so it can make better wear-leveling decisions about the entire super blocks. The data storage system can build the erase blocks have the lowest values of the age first, so they can have more wear applied to them.
The data storage system can use the relative wear of the erase blocks to make decisions about which of the erase blocks to use for different types of the roles within the super blocks. The data storage system can enforce a minimum dwell time for each of the erase blocks to be allowed to heal before re-use.
The data storage system can choose which flash components, such as the memory dice, to use when building the super blocks. For example, for a particular one of the super blocks the data storage system may skip using any of the erase blocks from a relatively worn one of the memory dice in order to apply less wear to it.
The data storage system can use the erase block metadata to determine how to build one of the super blocks based on the intended use of one of the super blocks.
The data storage system can choose some of the super blocks to recycle based to some extent on which of the erase blocks it would like to use to build new ones of the super blocks in the future.
It has been discovered that forming the super block metadata by aggregating the erase block metadata provides increased performance and improved operational integrity. Providing redundant information reduces the likelihood of failure of the data storage system by allowing the recovery of information in case of component failure.
Referring now to FIG. 7, therein is shown a flow chart of a method of operation of the data storage system of FIG. 1 in a further embodiment of the present invention. The method includes: selecting an erase block from an erase block pool in a block; and forming a super block having the erase block in another block.
Thus, it has been discovered that the data storage system of the present invention furnishes important and heretofore unknown and unavailable solutions, capabilities, and functional aspects for a data storage system with dynamic erase block grouping mechanism. The resulting method, process, apparatus, device, product, and/or system is straightforward, cost-effective, uncomplicated, highly versatile, accurate, sensitive, and effective, and can be implemented by adapting known components for ready, efficient, and economical manufacturing, application, and utilization.
Another important aspect of the present invention is that it valuably supports and services the historical trend of reducing costs, simplifying systems, and increasing performance.
These and other valuable aspects of the present invention consequently further the state of the technology to at least the next level.
It will be understood that, although the terms “first,” “second,” etc. may be used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another. For example, a first erase block could be termed a second erase block, and, similarly, a second erase block could be termed a first erase block, without changing the meaning of the description, so long as all occurrences of the “first erase block” are renamed consistently and all occurrences of the “second erase block” are renamed consistently. The first erase block and the second erase block are both erase blocks, but they are not the same erase block.
The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the claims. As used in the description of the embodiments and the appended claims, the singular forms “a,” “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term “and/or” as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items. It will be further understood that the terms “comprises” and/or “comprising,” when used in this specification, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.
As used herein, the term “if” may be construed to mean “when” or “upon” or “in response to determining” or “in accordance with a determination” or “in response to detecting,” that a stated condition precedent is true, depending on the context. Similarly, the phrase “if it is determined [that a stated condition precedent is true]” or “if [a stated condition precedent is true]” or “when [a stated condition precedent is true]” may be construed to mean “upon determining” or “in response to determining” or “in accordance with a determination” or “upon detecting” or “in response to detecting” that the stated condition precedent is true, depending on the context.
The foregoing description, for purpose of explanation, has been described with reference to specific embodiments. However, the illustrative discussions above are not intended to be exhaustive or to limit the claims to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The embodiments were chosen and described in order to best explain principles of operation and practical applications, to thereby enable others skilled in the art.

## Claims

1. A method of operation of a data storage system, the method comprising:
maintaining metadata for each erase block of a plurality of erase blocks in the data storage system, wherein a respective metadata for a respective erase block includes one or more characteristics of the respective erase block;
allocating a set of erase blocks, of the plurality of erase blocks, as unassociated erase blocks; and
forming a plurality of super blocks, including, for each super block to be formed:
selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics, wherein said characteristics of the unassociated erase blocks, in accordance with which the two or more unassociated erase blocks are selected, include at least one characteristic selected from the group consisting of age information, bit error rate, wear statistics, and operation parameters;
grouping the two or more selected erase blocks to form the super block;
aggregating metadata from the two or more selected erase blocks; and
storing the aggregated metadata as metadata for the super block.

2. The method of claim 1, wherein the selecting includes enforcing a minimum amount of dwell time for the unassociated erase blocks, wherein dwell time is the amount of time between operations on a respective erase block.

3. The method of claim 1, wherein the metadata is maintained in persistent storage in the data storage system.

4. The method of claim 1, wherein the super block includes two or more unassociated erase blocks from different memory die of the data storage system.

5. The method of claim 1, wherein selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes selecting two or more unassociated erase blocks with similar ages.

6. The method of claim 1, wherein selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes:
selecting a first unassociated erase block from a first die of the data storage system;
selecting a second unassociated erase block from a second die of the data storage system; and
forgoing selection of a third unassociated erase block from a third die of the data storage system, wherein the third die is relatively worn in comparison to the first die and second die.

7. The method of claim 1, further comprising:
selecting one or more erase blocks, in accordance with the one or more characteristics of the one or more erase blocks, for recycling;
recycling the selected one or more erase blocks; and
allocating the recycled one or more erase blocks as unassociated erase blocks.

8. The method of claim 1, further comprising:
selecting, from the super block, a relatively old erase block to store parity information.

9. A data storage system, comprising:
one or more processors; and
memory storing one or more programs to be executed by the one or more processors, the one or more programs comprising instructions for:
maintaining metadata for each erase block of a plurality of erase blocks in the data storage system, wherein a respective metadata for a respective erase block includes one or more characteristics of the respective erase block;
allocating a set of erase blocks, of the plurality of erase blocks, as unassociated erase blocks; and
forming a plurality of super blocks, including, for each super block to be formed:
selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics, wherein said characteristics of the unassociated erase blocks, in accordance with which the two or more unassociated erase blocks are selected, include at least one characteristic selected from the group consisting of age information, bit error rate, wear statistics, and operation parameters;
grouping the two or more selected erase blocks to form the super block;
aggregating metadata from the two or more selected erase blocks; and
storing the aggregated metadata as metadata for the super block.

10. The data storage system of claim 9, wherein selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes enforcing a minimum amount of dwell time for the unassociated erase blocks, wherein dwell time is the amount of time between operations on a respective erase block.

11. The data storage system of claim 9, wherein the metadata is maintained in persistent storage in the data storage system.

12. The data storage system of claim 9, wherein the super block includes two or more unassociated erase blocks from different memory die of the data storage system.

13. The data storage system of claim 9, wherein selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes selecting two or more unassociated erase blocks with similar ages.

14. The data storage system of claim 9, wherein selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes:
selecting a first unassociated erase block from a first die of the data storage system;
selecting a second unassociated erase block from a second die of the data storage system; and
forgoing selection of a third unassociated erase block from a third die of the data storage system, wherein the third die is relatively worn in comparison to the first die and second die.

15. The data storage system of claim 9, wherein the one or more programs further comprise instructions for:
selecting one or more erase blocks, in accordance with the one or more characteristics of the one or more erase blocks, for recycling;
recycling the selected one or more erase blocks; and
allocating the recycled one or more erase blocks as unassociated erase blocks.

16. The data storage system of claim 9, wherein the one or more programs further comprise instructions for selecting, from the super block, a relatively old erase block to store parity information.

17. A non-transitory computer readable storage medium, storing one or more programs configured for execution by one or more processors of a data storage system, the one or more programs including instructions for:
maintaining metadata for each erase block of a plurality of erase blocks in the data storage system, wherein a respective metadata for a respective erase block includes one or more characteristics of the respective erase block;
allocating a set of erase blocks, of the plurality of erase blocks, as unassociated erase blocks; and
forming a plurality of super blocks, including, for each super block to be formed:
selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics, wherein said characteristics of the unassociated erase blocks, in accordance with which the two or more unassociated erase blocks are selected, include at least one characteristic selected from the group consisting of age information, bit error rate, wear statistics, and operation parameters;
grouping the two or more selected erase blocks to form the super block;
aggregating metadata from the two or more selected erase blocks; and
storing the aggregated metadata as metadata for the super block.

18. The non-transitory computer readable storage medium of claim 17, wherein the selecting includes enforcing a minimum amount of dwell time for the unassociated erase blocks, wherein dwell time is the amount of time between operations on a respective erase block.

19. The non-transitory computer readable storage medium of claim 17, wherein selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes selecting two or more unassociated erase blocks with similar ages.

20. The non-transitory computer readable storage medium of claim 17, wherein selecting two or more unassociated erase blocks in accordance with characteristics of the unassociated erase blocks so as to select unassociated erase blocks with similar characteristics includes:
selecting a first unassociated erase block from a first die of the data storage system;
selecting a second unassociated erase block from a second die of the data storage system; and
forgoing selection of a third unassociated erase block from a third die of the data storage system, wherein the third die is relatively worn in comparison to the first die and second die.