Data storage device accessing garbage collected memory segments

A data storage device is disclosed comprising a non-volatile memory comprising a plurality of memory segments. A first write command is received from a host comprising first data and a first logical block address (LBA). The first data is written to a first memory segment and the first LBA is first mapped to a first physical block address (PBA) of the first memory segment. During a garbage collection operation, the first data is copied from the first memory segment to a second memory segment and the first LBA is second mapped to a second PBA of the second memory segment. After the garbage collection operation, a read command is received from the host comprising the first LBA. A selection is made between the first and second memory segments, and at least part of the first data is read from the selected memory segment.

BACKGROUND

Data storage devices (e.g., disk drives or non-volatile semiconductor memories) may be employed as mass storage for a computer system (e.g., desktop, laptop, portable, etc.) or a consumer device (e.g., music player, cell phone, camera, etc.) or other suitable application. The data storage device includes a non-volatile memory (e.g., a disk or a semiconductor memory) for storing user data in memory segments which are accessed using an address translation layer. For example, the address translation layer may map a logical block address (LBA) received from a host to a physical block address (PBA) representing a memory segment of the non-volatile memory. The indirect mapping of LBA to PBA facilitates aspects such as defect mapping, and log-structured file systems where the LBA to PBA mapping may change over time.

An example data storage device employing an address translation layer is a non-volatile semiconductor memory comprising one or more memory devices (such as a flash memory). Each memory device typically comprises a number of blocks which are accessed a page at a time. For example, a single block may comprise 128 pages where each page comprises 4096 bytes. Since a page typically cannot be overwritten without first being erased, a new page in a different block is typically selected to perform an “overwrite” operation. Accordingly, the address translation layer must maintain the appropriate LBA to PBA mapping as each write operation changes the physical location of the user data (similar to a log-structured file system). When the same LBA is written by the host, the data is written to a new PBA and the old PBA is marked invalid so that it may be reused (erased and overwritten with new data).

A similar dynamic LBA to PBA mapping may be employed in a disk drive, wherein the memory segments comprise data sectors of data tracks which may or may not be erased before being overwritten. The process of copying data from valid memory segments to new memory segments and reallocating the invalid memory segments is referred to as garbage collection.

DETAILED DESCRIPTION

FIG. 1Ashows a data storage device2according to an embodiment of the present invention comprising a non-volatile memory4comprising a plurality of memory segments. The data storage device2further comprises control circuitry6operable to execute the flow diagram ofFIG. 1B, wherein a first write command is received from a host (block8) comprising first data and a first logical block address (LBA). The first data is written to a first memory segment (block10) and the first LBA is first mapped to a first physical block address (PBA) of the first memory segment (block12). During a garbage collection operation (block14), the first data is copied from the first memory segment to a second memory segment (block16) and the first LBA is second mapped to a second PBA of the second memory segment (block18). After the garbage collection operation, a read command is received from the host comprising the first LBA (block20). In response to the read command, a selection is made between the first memory segment and the second memory segment (block21), and at least part of the first data is read from the selected memory segment (block22).

FIG. 1Cillustrates an embodiment of the present invention wherein data is first written to a first memory segment24A when servicing a write command from a host. An LBA of the write command is mapped to the PBA of the first memory segment24A. The first memory segment24A is part of a block of memory segments that may comprise other invalid memory segments, and is therefore eventually garbage collected in order to free the invalid memory segments for future write commands. During the garbage collection operation, the data stored in the first memory segment24A may still be valid and is therefore copied to a second memory segment24B with the LBA mapped to the PBA of the second memory segment24B. However, in one embodiment the data stored in first memory segment24A remains valid after the copy operation (i.e., the first memory segment24A is not immediately erased). Therefore in one embodiment the first mapping of the LBA to the first memory segment24A is retained in order to retain a copy of the data. The copy of the data may be used for any suitable reason, such as for error recovery when the second memory segment24B is unrecoverable, or to increase throughput of the data storage device.

FIG. 2Ashows a data storage device in the form of a non-volatile semiconductor memory-based storage device26comprising a memory controller28(e.g., a flash memory controller) and a memory device30(e.g., a flash memory) according to one embodiment. While the description herein refers to non-volatile semiconductor memory generally, it is understood that non-volatile semiconductor memory may comprise one or more of various types of memory devices such as flash integrated circuits, Chalcogenide RAM (C-RAM), Phase Change Memory (PC-RAM or PRAM), Programmable Metallization Cell RAM (PMC-RAM or PMCm), Ovonic Unified Memory (OUM), Resistance RAM (RRAM), NAND memory (e.g., single-level cell (SLC) memory, multi-level cell (MLC) memory, or any combination thereof), NOR memory, EEPROM, Ferroelectric Memory (FeRAM), Magnetoresistive RAM (MRAM), other discrete NVM (non-volatile memory) chips, or any combination thereof.

In one embodiment, the memory controller28comprises a microprocessor32for implementing various algorithms, including LBA to PBA mapping, wear leveling, error correction code (etc.). The memory controller28further comprises a buffer34for buffering write/read data, and interface circuitry36for interfacing with one or more memory devices30. The interface circuitry36generates suitable control signals38and receives status information40from the memory device(s)30in connection with executing write/read commands initiated by the microprocessor32. The interface circuitry36also transmits and receives data over an I/O bus42, including write/read data stored in the buffer34or command data generated by the microprocessor32and transmitted to a controller44integrated with the memory device(s)30.

In one embodiment, the memory device(s)30comprises an array of memory cells46that are accessed in memory segments referred to as pages. During a write operation, write data received over the I/O bus42from the buffer34is first stored in a data register48. The controller44then transfers the write data from the data register48to a target page in the memory array46. During a read operation, a page in the memory array46is read into the data register48and then transferred over the I/O bus42where it is stored in the buffer34. In one embodiment, the memory array46comprises a plurality of blocks, each block comprises a plurality of pages, and the pages in a block are erased together by erasing the block.

When an LBA is written, the data is written to a free page of the current block allocated to servicing write commands. When the current block is filled with data, a new block is selected from a pool of free blocks, and the newly selected block is used to service the write commands. When an LBA is overwritten, the new data is written to a free page of the current block, and the old data stored in the page of the old block is marked as invalid.FIG. 2Billustrates a first block50A storing invalid pages and valid pages. During a garbage collection operation, the valid pages in the first block50A are copied to free pages of a second block50B. Conventionally, once this copying is completed, the valid pages in the first block50A would be marked invalid and subject to erasure. However, since the data in the first block50A is a copy of the valid data in the second block50B, embodiments of the present invention maintain mapping data that reference those pages in the first block50A and exploit the redundancy rather than immediately erasing the pages in the first block50A.

In one embodiment, the garbage collection operation for the non-volatile semiconductor memory-based storage device26shown inFIG. 2Ais divided into two stages. During a first stage, the valid pages of old blocks are copied to new blocks without erasing the old blocks. The first and second mapping to the old and new blocks is maintained so that the resulting redundancy can be exploited. In a second stage, when the number of free blocks falls below a threshold or when other factors such as wear leveling trigger erasure of blocks, a number of the old blocks storing the redundant copies of data are erased and placed in the pool of free blocks. When a page of an old block storing redundant data is erased, the corresponding LBA mapping information is also invalidated. Accordingly in this embodiment, the pages of old blocks storing redundant copies of data may be accessed during the interval between the first and second stages of the garbage collection operation, or until the LBA is overwritten as part of a new write command in which case the LBA mapping information to the page in the old block is also invalidated. Although the embodiments are described as operating on a page level, in some embodiments, valid/invalid data may be operated upon and/or mapped at a sector level or a different unit of granularity. For example, the same principles would be applicable in implementations where a page may include multiple sectors or other units of granularity.

FIG. 3Ashows a data storage device in the form of a disk drive comprising a head52actuated over a disk54by a voice coil motor (VCM). The disk drive further comprises control circuitry56for implementing the embodiments of the present invention, including to maintain first and second mappings for garbage collected LBAs. The disk comprises a plurality of data tracks, wherein in an example shown inFIG. 3Beach data track comprises a plurality of data sectors for storing user data and embedded servo sectors (SS) for storing servo positioning information (e.g., track address and servo bursts). In one embodiment, each memory segment corresponds to a data sector accessed through a PBA. Similar to a flash based memory device described above, the disk drive ofFIG. 3Amay implement a dynamic LBA to PBA mapping, for example, when implementing a log-structured file system. With a log-structured file system, data is typically written to a new memory segment (data sector) during each write operation (including overwrite operations). The old memory segments (data sectors) are invalidated and then reallocated using a garbage collection algorithm. A disk drive may implement a log-structured file system, for example, when implementing a shingled track system where write operations progress in the same radial direction so that the data tracks can overlap, thereby increasing the tracks per inch (TPI).

The dynamic LBA to PBA mapping may be implemented using any suitable technique, such as shown inFIG. 4Awhere the disk54is accessed as a circular buffer. The data tracks are written from the ID toward the OD (or vice versa), and when the last data track is reached, the writing operation wraps around so as to overwrite the old data tracks at the tail of the circular buffer. In an alternative embodiment shown inFIG. 4B, the disk may be divided into a number of zoned blocks (Z1-ZN), wherein each zone comprises a plurality of contiguous data tracks. The zoned blocks are accessed similar to the blocks in the non-volatile semiconductor memory-based storage device described above with reference toFIG. 2A. That is, one of the zones is selected to service the current write commands, and when the current zone is filled, a new zone is selected from a pool of free zones. During a garbage collection operation, the valid data sectors of an old zone are copied to a new zone, and the control circuitry56maintains the first mapping to the data sector of the old zone as well as the second mapping to the data sector of the new zone. In one embodiment, the data sectors storing redundant data are eventually overwritten when the corresponding zone is selected to service new write commands. An old zone may or may not be erased prior to overwriting the data sectors. In either embodiment, the LBA mapping to the old data sector is invalidated when the data sector in the old zone is erased or overwritten, or when the same LBA is overwritten as part of a new write command.

The mapping of LBAs to PBAs may be implemented in any suitable manner in the embodiments of the present invention.FIG. 5Ashows an embodiment wherein the control circuitry6of the data storage device2(FIG. 1A) maintains a LBA mapping table comprising a plurality of entries, wherein each entry maps an LBA to a primary PBA (PBA_1) and to a redundant PBA (PBA_2). The primary PBA stores newly written data for the LBA, and the redundant PBA stores a copy of the data when generated as part of the garbage collection operation. When an LBA does not have a corresponding redundant PBA, a NULL entry is assigned in the LBA mapping table. The LBA mapping table shown inFIG. 5Acomprises an entry for each LBA; however, other embodiments may employ run-length encoding in order to reduce the size of the LBA mapping table.

FIG. 5Bshows an alternative embodiment of the present invention wherein the control circuitry6maintains two mapping tables: a primary LBA mapping table for storing the LBA to PBA mapping for the most recent write operation, and a garbage collection LBA mapping table for storing the LBA to PBA mapping to the redundant memory segments generated as part of the garbage collection operation. When the LBA to PBA mapping to a redundant memory segment becomes invalid (due to an erase or overwrite), the corresponding entry in the garbage collection LBA mapping table is deleted. This embodiment may reduce the amount of memory needed to maintain the LBA mapping information since the garbage collection LBA mapping table may be significantly smaller than the primary LBA mapping table.

In one embodiment, the control circuitry6maintains the LBA mapping table(s) in a volatile semiconductor memory (e.g., a random access memory (RAM)) and updates the LBA mapping table(s) as new write commands are received by the host as well as when write commands are generated during the garbage collection operation. Periodically the control circuitry6writes (flushes) the updated LBA mapping table(s) to the non-volatile memory4so that the updates are saved when the data storage device is powered down. However, if the data storage device is subject to a power failure, the most recent updates to the LBA mapping table(s) that occur after the last flush operation will be lost. In one embodiment, the control circuitry6writes in-line mapping information to a memory segment of the non-volatile memory4when servicing each write command so that the in-line mapping information can be used to rebuild the LBA mapping table(s) when recovering from a power failure.FIG. 6Ashows an embodiment of in-line mapping information written to the last page of the current block when servicing write commands in the non-volatile semiconductor memory-based storage device26ofFIG. 2A, andFIG. 6Bshows an embodiment of in-line mapping information written to the last data sector following a write command to the disk of the disk drive ofFIG. 3A. The in-line mapping information comprises the LBAs of the write command so that when the data storage devices recovers from a power failure, the in-line mapping information can be read from the most recently written blocks of memory segments and used to rebuild the LBA mapping table(s). In one embodiment, the in-line mapping information comprises a flag (denoted by the example value [R] as shown) that indicates whether the LBA was written as part of a garbage collection operation so that the LBA mapping table(s) can be rebuilt with mapping to the primary PBA and the redundant PBA when appropriate.

FIG. 7is a flow diagram according to an embodiment of the present invention for rebuilding the LBA mapping table(s) when the data storage device recovers from a power failure. When the data storage device is powered on and a power fail condition is detected (block58), the LBA mapping table(s) last flushed to the non-volatile memory4is read into a volatile semiconductor memory (e.g., RAM). The block(s) being written prior to the power failure operation are then accessed in order to recover the in-line mapping information (block62). For each entry in the in-line mapping information, the primary entry of the LBA mapping table is updated (block64), and if the in-line mapping information indicates a redundant memory segment, the redundant entry of the LBA mapping table is updated (block68), otherwise the redundant entry of the LBA mapping table is nullified or deleted (block70). The flow diagram is then repeated from block64until all of the in-line mapping information has been processed (block72). The updated LBA mapping table(s) is then written to the non-volatile memory (block74).

In one embodiment when executing the garbage collection operation the data in the valid memory segments are copied to a reserved area of the non-volatile memory, such as a pool of reserved blocks in the non-volatile semiconductor memory-based storage device26ofFIG. 2A, or a pool of reserved zones on the disk of the disk drive ofFIG. 3A. The data for new write commands received from the host are written to a different reserved area in the non-volatile memory. In this embodiment, in-line mapping information is written to both reserved areas, and when recovering from a power failure, the in-line information is recovered from both reserved areas. The in-line mapping information for the garbage collection area need not include a flag to indicate whether the LBA is a redundant copy since all LBAs in the garbage collection area are a redundant copy. In one embodiment, the in-line mapping information for both reserved areas includes a sequence number so that the order in which the garbage collection copy commands and the host write commands can be determined and used to accurately rebuild the LBA mapping table(s).

FIG. 8is a flow diagram according to an embodiment of the present invention which is an extension to the flow diagram ofFIG. 1B. When a write command is received from the host to overwrite the first LBA with second data (block76), the second data is written to a third memory segment (block78), the LBA is mapped to a third PBA of the third memory segment (block80), and the first and second mappings (generated at block12and block18ofFIG. 1B) are invalidated (block82). That is when an LBA is overwritten with new data, the previous LBA mappings (primary and redundant) are invalidated since they no longer correspond to the LBA (the primary and redundant memory segments become invalid).

FIG. 9is a flow diagram according to an embodiment of the present invention which is an extension to the flow diagram ofFIG. 1B. When a write command is received from the host to write second data to a second LBA (block84), the second data may overwrite the first memory segment (block86). That is, the first memory segment may be part of a free block selected to service the new write commands, and therefore the first memory segment is eventually overwritten. The second LBA is mapped to the first PBA of the first memory segment (block88) and the first mapping (generated at block12ofFIG. 1B) is invalidated. That is, the overwrite operation invalidates the redundant copy of the first LBA, but the primary copy for the first LBA (stored in the second memory segment) is still available.

FIG. 10is a flow diagram according to an embodiment of the present invention which is an extension to the flow diagram ofFIG. 1B. In the embodiment wherein the garbage collection operation eventually erases the memory segments (block92), the first memory segment is eventually erased (block94) and the first mapping (generated at block12ofFIG. 1B) is invalidated. That is, the erase operation invalidates the redundant copy of the first LBA, but the primary copy for the first LBA (stored in the second memory segment) is still available.

FIG. 11is a flow diagram according to an embodiment of the present invention wherein the redundant copy of data stored in a garbage collected memory segment may be used to recover data when the primary copy of the data cannot be recovered (e.g., due to a defect). When a read command is received to read the first LBA (block98), the control circuitry first attempts to read the first data from the second memory segment (block100) which stores the primary copy. If the first data cannot be recovered from the second memory segment (block102), the control circuitry attempts to read the first data from the first memory segment (block104) which stores the redundant copy. In one embodiment if the first data is recoverable from the first memory segment (block106), the first data is copied to a third memory segment (block108) and the first LBA is mapped to a third PBA of the third memory segment (block110). That is, the garbage collection operation is repeated for the first LBA so as to store another primary copy of the data in a different memory segment. The second mapping of the LBA to the second memory segment is invalidated (block112) and in one embodiment the second memory segment may be mapped out as defective.

FIG. 12is a flow diagram according to an embodiment of the present invention wherein the data storage device comprises the disk drive shown inFIG. 3A. The control circuitry56queues a number of access commands received from the host, and then executes a rotational position optimization (RPO) algorithm in order to select and execute the access commands from the command queue in an order that minimizes the seek latency of the head52and the rotational latency of the disk54needed to access the corresponding memory segments (data sectors). Accordingly, when a read command is received from the host comprising the first LBA (FIG. 1B) that is mapped to first and second memory segments, the control circuitry selects between the first memory segment and the second memory segment using the RPO algorithm, and then reads the first data from the selected memory segment. In this embodiment, the redundant memory segments generated through the garbage collection operation improves performance of the RPO algorithm.

In a similar manner, in one embodiment, the availability of the redundant copy may be used to improve data transfer performance in the non-volatile semiconductor memory-based storage device26ofFIG. 2A. The redundant copy may enable the controller28to exploit the parallelism in data channels employing multiple memory devices30. In one embodiment, a first memory device30comprises a first memory array46accessed over a first channel, and a second memory device30comprises a second memory array46accessed over a second channel. When servicing a read command for a particular LBA, if the primary copy resides in a memory array that is serviced by a busy channel with a long queue of requests, the controller may choose to access the redundant copy if it resides in a different memory array serviced by a less busy channel. In addition, if the primary and redundant copies are accessible through different channels, the controller28may also choose to obtain a part of the data from the primary copy and a part of the data from the redundant copy and combine the parts to effectively increase the overall transfer rate.