Data conflict resolution for solid-state memory devices

In a particular embodiment, a controller is disclosed that is adapted to control read/write access to a storage media. The controller includes data corruption detection logic to reconstruct a logical block address (LBA) lookup table from metadata stored at the storage media upon restart and re-initialization after a power loss event. The controller further includes duplicate conflict resolution logic to identify a valid data block from multiple data blocks that refer to a single LBA. The duplicate conflict resolution logic counts a first number of valid physical pages and a second number of different sectors in each of the multiple data blocks. The duplicate conflict resolution logic selects the valid data block from the multiple data blocks based on at least one of the first and second numbers.

FIELD OF THE DISCLOSURE

The present disclosure is generally related to data conflict resolution for solid-state memory devices.

BACKGROUND

In general, data storage devices are susceptible to data loss or corruption in the event of a power interruption during operation. When a power loss event occurs during a write operation, the data can be corrupted. Further, when such an event occurs during an update of storage device configuration data, such as wear leveling data or directory mapping data, the data may not be recoverable upon subsequent power up and re-initialization.

In some instances, storage systems have incorporated auxiliary power supplies to provide power during a power loss event. Additionally, many storage systems have incorporated redundant data storage techniques to preserve one or more versions of the data in response to such power loss events. However, upon subsequent power up and re-initialization, multiple versions of the data may be stored in memory. Further, when metadata is spread into spare bytes of pages within a flash memory due to an out-of-space update, multiple copies may be mapped to the same logical block address, but only one copy is valid.

SUMMARY

In a particular embodiment, a controller is disclosed that is adapted to control read/write access to a storage media. The controller includes data corruption detection logic to reconstruct a logical block address (LBA) lookup table from metadata stored at the storage media upon restart and re-initialization after a power loss event. The controller further includes duplicate conflict resolution logic to identify a valid data block from multiple data blocks that refer to a single LBA. The duplicate conflict resolution logic counts a first number of valid physical pages and a second number of different sectors in each of the multiple data blocks. The duplicate conflict resolution logic selects the valid data block from the multiple data blocks based on at least one of the first and second numbers.

In another particular embodiment, a processor-readable medium embodies instructions executable by a processor to resolve a conflict between at least two copies of a data block that are mapped to a single logical block address. The instructions include a first instruction that is executable by a processor to reconstruct a logical block address (LBA) lookup table from metadata stored at a storage media after an unexpected power loss event. The instructions further include a second instruction that is executable by the processor to detect a data error including multiple copies of a data block mapped to a single logical block address associated with a storage media and include a third instruction that is executable by the processor to determine a valid physical page value for each copy of the multiple copies. Additionally, the instructions include a fourth instruction that is executable by the processor to determine a data diversity value for each copy of the multiple copies. Further, the instructions include a fifth instruction that is executable by the processor to select a copy from the multiple copies when one of the valid physical page value and the data diversity value associated with the copy is greater than respective valid physical page values and data diversity values of other copies of the multiple copies.

In still another particular embodiment, a method is disclosed that includes detecting a data error that includes a first data block and a second data block that are mapped to a single logical block address of a storage media of a storage device. The method further includes counting a first number of valid physical pages in the first data block and a second number of valid physical pages in the second data block and selecting the first data block as a valid data block when the first number is greater than the second number of valid physical pages. The method also includes selecting the second data block as the valid data block when the second number is greater than the first number of valid physical pages.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

FIG. 1is a block diagram of a particular illustrative embodiment of a system100including a storage device102with data conflict resolution logic. In a particular embodiment, the data storage device102is a solid-state memory device that is adapted to communicate with a host system104via an interface106. The host system104may be a computing system, such a personal computer, a personal digital assistant (PDA), processing logic, another electronic device, or any combination thereof.

The data storage device102includes a control circuit108that is adapted to communicate with a primary storage media110and with other memory114. For example, the other memory114can include flash memory, such as NAND flash memory and NOR flash memory, other solid-state memory, or any combination thereof. In a particular embodiment, the primary storage media110is a solid-state storage media that is adapted to store both data blocks and meta-data related to the data blocks. In a particular embodiment, the solid-state memory is a NAND flash memory, a NOR flash memory, other solid-solid state memory, or any combination thereof. In general, each flash page has spare bytes. In a particular example, for single-level cell (SLC) NAND flash, there are 16 spare bytes for every 512 bytes of data or 64 spare bytes for each two-kilobyte page of data. Metadata, including logical block address (LBA) data, is stored in those spare bytes. Thus, when data is corrupted, the same LBA data may appear in the metadata for different data blocks in the solid-state memory. In this particular example, the first data block copy132may include an LBA in its spare bytes and the second data block copy134may include the same LBA in its spare bytes.

The data storage media110includes a data storage area131and a reserved storage area136. In a particular embodiment, a logical block address (LBA) lookup table138can be stored at the reserved storage area136of the primary storage media110. In general, the LBA lookup table138is used to establish a relation between data blocks stored at the storage media data storage area131of the storage media110and logical block address data and other metadata stored in spare bytes of the data blocks, such as a first data block copy132and a second data block copy134within the data storage area131. The reserved storage area136may be a logical portion of the storage media110that is restricted for access only by the control circuit108. In this particular example, the LBA lookup table138is stored and updated at the reserved storage area136. In an alternative example, the LBA lookup table138is stored at the other memory114, such as at a NAND flash memory.

The control circuit108is also coupled to an auxiliary power component112. In a particular embodiment, the auxiliary power component112can be a capacitor or a battery that is adapted to supply power to the storage device102under certain operating conditions. In a particular example, the auxiliary power component112can provide a power supply to the control circuit108and to at least one of the primary storage media110and the other memory114to record data when power is unexpectedly turned off. The control circuit108is also coupled to duplicate conflict resolution logic116. In a particular example, the duplicate conflict resolution logic116is a set of instructions stored within a memory (such as a NOR flash memory) that is executable by the control circuit108to resolve data conflicts. For example, the duplicate conflict resolution logic116can be executed by the control circuit108to determine which data block copy out of multiple duplicate copies of a data block is valid.

The control circuit108includes data corruption detection logic118to detect data corruption. In a particular embodiment, the data corruption detection logic118is adapted to detect when the LBA lookup table138does not match the real status of the storage media110due to unplanned power loss. For example, after a write operation is performed to write updated data to the data portion131of the storage media110, power is lost due to an unplanned power loss event, and the LBA lookup table138in the reserved area136is not updated. In this instance, upon restart and re-initialization of the storage device102, the data corruption detection logic118detects multiple copies of a data block (such as the first and second data block copies132and134) that are mapped to the same LBA.

Upon restart and re-initialization of the storage device102after and unplanned power loss event, the control circuit108cannot rely on the integrity of the LBA lookup table138at the reserved storage area136. Instead, the control circuit108is adapted to scan all of the metadata stored at the data storage area131of the storage media110to reconstruct an LBA look-up table120, which is a mapping of a current state of the storage media110. During the process of reconstructing the LBA look-up table120, the control circuit108may encounter multiple data blocks, which include metadata in their spare bytes that refer to the same LBA. In this instance, the control circuit108uses the duplicate conflict resolution logic116to determine which data block is valid.

The duplicate conflict resolution logic116includes physical page counter logic122to count a number of physical pages associated with each data block, when there are multiple duplicate data blocks. The duplicate conflict resolution logic116also includes sector diversity counter logic124to count a number of different sectors associated with each data block. Further, the duplicate conflict resolution logic116includes data block selection logic126that is executable by the control circuit to select a particular data block from the multiple duplicate data blocks as a valid data block. The control circuit108can provide the selected data block to the host system104. Further, the control circuit108is adapted to update the LBA lookup table138at the reserved storage area136based on the selection when reconstruction of the LBA lookup table120is completed.

In a particular embodiment, the control circuit108is adapted to read metadata associated with the first data block132from spare bytes of the first data block132and to read metadata associated with the second data block134from spare bytes of the second data block134to reconstruct the LBA lookup table120. If the first and second data block copies132and134refer to the same LBA, the control circuit108uses the duplicate conflict resolution logic116to determine which copy is valid. The duplicate conflict resolution logic116is configured to identify which copy is the latest, freshest copy and selects the freshest copy as a valid copy. In a particular example, the duplicate conflict resolution logic116is used by the control circuit108to choose a copy that has a greatest number of valid physical pages, to choose a copy that has a greatest amount of data diversity, or any combination thereof.

In a particular embodiment, the data storage device102includes the storage media110that is adapted to store data and to store metadata within spare bytes. The data storage device102further includes a controller, such as the control circuit108, a processor, or any combination thereof. The control circuit108is adapted to control read/write access to the storage media110. Further, the control circuit108includes data corruption detection logic118. Upon startup and re-initialization, the data corruption detection logic118is adapted to determine that an unexpected power loss event occurred previously. The control circuit108also includes duplicate conflict resolution logic116to detect and resolve data corruption errors by reconstructing the LBA lookup table120from metadata stored at the storage media110. For example, the primary storage media110can include a first data block copy132and a second data block copy134that include metadata that refers to the same LBA, where only one of the copies is valid. The control circuit108uses the physical page counter logic122and the sector diversity counter logic124of the duplicate conflict resolution logic116to count a first number of valid physical pages and a second number of different sectors, respectively, in the first and second data block copies132and134. In a particular example, the control circuit108also uses the data block selection logic126to select a latest, freshest copy as a valid copy, which may be a copy having at least one of a largest first number and a largest second number.

In a particular embodiment, when the number of pages and the number of different sectors in each of the multiple copies is the same, the control circuit108is adapted to apply another selection algorithm to select one of the multiple copies as a valid copy. In a particular embodiment, the selection algorithm can be a random selection algorithm adapted to randomly select the copy from the at least two copies. In another particular embodiment, the selection algorithm can be a date/time selection algorithm. In still another particular embodiment, the control circuit108may select a particular copy as the valid copy based on load-balancing considerations because some solid-state memory devices degrade with usage. Thus, the particular copy may be selected based on usage to enhance the usable life of the storage media110.

FIG. 2is a block diagram of a second particular illustrative embodiment of a system200including a hybrid storage device202with data conflict resolution logic. As used herein, the term “hybrid storage device” refers to a data storage device that includes both rotating storage media and solid-state storage media. The hybrid storage device202is adapted to communicate with a host system204. In a particular embodiment, the host system204can be a computer, a processor, a personal digital assistant (PDA), another electronic device, or any combination thereof.

The hybrid storage device202includes recording subsystem circuitry206and a head-disc assembly208. The recording subsystem206includes storage device read/write control circuitry210and disc-head assembly control circuitry220. The recording subsystem circuitry206includes an interface circuit212, which includes a data buffer for temporarily buffering the data and a sequencer for directing the operation of the read/write channel216and the preamplifier250during data transfer operations. The interface circuit212is coupled to the host system204and to a control processor218, which is adapted to control operation of the hybrid storage device202. In a particular embodiment, the control processor218includes data corruption detection logic238that is adapted to detect data corruption, for example, when two data blocks are mapped to the same logical block address. In a particular embodiment, that data corruption detection logic238can be processor executable instructions that are executed by the control processor218.

The control processor218is coupled to a servo circuit222that is adapted to control the position of one or more read/write heads254relative to one or more discs256as part of a servo loop established by the one or more read/write heads254. Generally, the one or more read/write heads254are mounted to a rotary actuator assembly to which a coil252of a voice coil motor (VCM) is attached. As is known in the art, a VCM includes a pair of magnetic flux paths between which the coil252is disposed so that the passage of current through the coil causes magnetic interaction between the coil252and the magnetic flux paths, resulting in the controlled rotation of the actuator assembly and the movement of the one or more heads254relative to the surfaces of the one or more discs256. The servo circuit222is used to control the application of current to the coil252, and hence the position of the heads254with respect to the tracks of the one or more discs256.

In general, the disc-head assembly control circuitry220includes the servo circuit222and includes a spindle circuit226that is coupled to a spindle motor258to control the rotation of the one or more discs256. The hybrid storage device202also includes an auxiliary power device228that is coupled to the disc-head assembly control circuitry220and that is adapted to operate as a power source when power to the hybrid storage device202is lost. In a particular embodiment, the auxiliary power device228can be a capacitor or a battery that is adapted to supply power to the hybrid storage device202under certain operating conditions. In a particular example, the auxiliary power device228can provide a power supply to the recording subsystem assembly206and to the disc-head assembly208to record data to the one or more discs256when power is turned off. Further, the auxiliary power device228may supply power to the recording subsystem assembly206to record data to a data (NAND) flash230or to a code (NOR) flash234when power is turned off.

Additionally, the hybrid storage device202includes the data (NAND) flash230, a dynamic random access memory (DRAM)232, the code (NOR) flash234, other memory236, or any combination thereof. In a particular embodiment, the code (NOR) flash234stores duplicate data conflict resolution instructions240. In a particular embodiment, the NAND flash230may store a logical block address (LBA) lookup table that represents a mapping of logical block addresses to physical memory locations within the one or more discs256.

In a particular embodiment, the code (NOR) flash234is a processor-readable medium that embodies duplicate conflict resolution instructions240that are executable by the control processor218to resolve a conflict between at least two copies of a data block that are mapped to a single logical block address. In a particular embodiment, after an unexpected power loss event, the data corruption detection logic238detects that the unexpected power loss event previously occurred. The data corruption detection logic238is adapted to access metadata associated with data blocks stored at the one or more discs256to reconstruct the LBA lookup table231. The metadata may be stored at a reserved area at the one or more discs256, where the reserved area is restricted to access by the control processor218and is reserved for storage of metadata, including LBA data. In a particular example, the reserved area may represent a physical area or a logical area of the one or more discs256. In another particular example, the LBA lookup table231may be reconstructed using the stored metadata from the one or more discs256and metadata associated with another memory, such as the data NAND flash230.

During reconstruction of the LBA lookup table231, the data corruption detection logic238may detect metadata associated with two or more data blocks that refer to the same LBA. In this instance, the data corruption detection logic238is adapted to initiate the duplicate conflict resolution logic240to identify and select one of the data blocks as a valid data block based on the metadata. For example, the duplicate conflict resolution instructions240is adapted to determine a valid physical page value for each copy of the multiple copies, to determine a data diversity value for each copy of the multiple copies, and to select one of the copies as valid that has a greatest number of valid physical pages, a greatest amount of data diversity, or any combination thereof. In a particular example, a most recent copy includes recently added data, resulting in more valid physical pages and higher data diversity.

In a particular embodiment, the duplicate conflict resolution instructions240include a fifth instruction to select the copy from the multiple copies using a random selection algorithm when the valid physical page values and the data diversity values of the multiple copies are equal. For example, if there are two duplicate data blocks having the same number of pages and the same data diversity, the duplicate conflict resolution instructions240are executable by the control processor218to pick one as a valid data block.

In another particular embodiment, the head-disc assembly208can be replaced with a solid-state storage media, such as a flash memory, an electrically programmable memory, other programmable solid-state memory, or any combination thereof. When the head-disc assembly208is replaced with a solid-state storage media, the spindle circuit222and the servo circuit222can also be omitted.

In a particular embodiment, the code (NOR) flash234is a processor-readable medium that is accessible to the control processor218. The code (NOR) flash234stores a plurality of instructions that are executable by the control processor218. In a particular example, the code (NOR) flash234includes operating instructions for the control processor218, including the duplicate conflict resolution instructions240and the data corruption detection logic238. In a particular embodiment, the duplicate conflict resolution instructions240include a first instruction that is executable by a processor to reconstruct a logical block address (LBA) lookup table from metadata stored at a storage media after an unexpected power loss event. The duplicate conflict resolution instructions240further include a second instruction that is executable by the processor to detect a data error including multiple copies of a data block mapped to a single logical block address associated with a storage media and include a third instruction that is executable by the processor to determine a valid physical page value for each copy of the multiple copies. Additionally, the duplicate conflict resolution instructions240include a fourth instruction that is executable by the processor to determine a data diversity value for each copy of the multiple copies. In a particular embodiment, the valid physical page value and the data diversity value are determined from metadata associated with data blocks stored at the storage media. The metadata may be stored in spare bytes of the storage media or at a reserved area of the storage media. Further, the duplicate conflict resolution instructions240include a fifth instruction that is executable by the processor to select a copy from the multiple copies when one of the valid physical page value and the data diversity value associated with the copy is greater than respective valid physical page values and data diversity values of other copies of the multiple copies.

In a particular embodiment, the duplicate conflict resolution instructions240further include a sixth instruction executable by the processor to select the copy from the multiple copies using a random selection algorithm or a load-balancing selection algorithm when the valid physical page values and the data diversity values of the multiple copies are equal.

FIG. 3is a block diagram of a third particular illustrative embodiment of a system300including a storage device302with data conflict resolution logic. The storage device302is adapted to communicate with a host system304, which may be a computer, a processor, another device, or any combination thereof. The storage device302includes an interface306that is coupled to the host system304. The interface306is also coupled to a controller308, which is adapted to control operation of the storage device302. In a particular example, the controller308can be a processor, a control circuit, or any combination thereof. The controller308is also coupled to a storage media310.

The controller308includes duplicate conflict resolution logic312to detect and resolve conflicts between duplicate data blocks. In a particular embodiment, the duplicate conflict resolution logic312includes instructions that are executable by the controller308. In a particular embodiment, upon restart and re-initialization after an unexpected power loss event, the duplicate conflict resolution logic312is adapted to determine that an unexpected power loss event had previously occurred and to reconstruct an LBA lookup table based on actual data stored at the storage media310to produce a reconstructed LBA lookup table314. During reconstruction of the LBA lookup table, the duplicate conflict resolution logic is adapted to detect data corruption, such as two data blocks having metadata that refers to the same logical block address (LBA). The duplicate conflict resolution logic312is adapted to resolve conflicts between such LBA conflicts in response to detecting the data corruption. In a particular embodiment, the duplicate conflict resolution logic312is adapted to select a particular data block as a valid data block based on the metadata in order to complete the reconstructed LBA lookup table314.

The storage media310includes a first data block310and a second data block340. The first data block310includes one or more pages of data322and associated metadata including LBA data324. In a particular embodiment, the storage media310is a solid-state memory device, such as a NAND flash memory, and the metadata including LBA data324is stored in spare bytes of the storage media310. The second data block340also includes one or more pages of data342and associated metadata including LBA data344.

In a particular embodiment, after an unexpected power loss event, the controller308loads the duplicate conflict resolution logic312from a memory, such as the code NOR flash234illustrated inFIG. 2. The controller308executes the duplicate conflict resolution logic312to determine that the unexpected power loss event previously occurred. In this instance, the controller308does not load an LBA lookup table from memory, since the LBA lookup table may not match the state of data stored at the storage media310. Instead, the duplicate conflict resolution logic312scans the metadata stored at the storage device310, including the metadata including the LBA data324and344of the first and second data blocks320and340, to produce the reconstructed LBA lookup table314.

In a particular embodiment, the metadata including the LBA data324and344of the first and second data blocks320and340refers to the same LBA. In this instance, the duplicate conflict resolution logic312is adapted to identify a latest copy from the first and second data blocks320and340as a valid copy. In a particular embodiment, the latest copy is determined based on a number of valid physical pages, based on a number of different sectors (i.e., data diversity), or any combination thereof. In another particular embodiment, the latest copy may be selected randomly if the number of valid physical pages and the data diversity were the same between the first and second data blocks. Once the valid copy is determined, the duplicate conflict resolution logic312updates the reconstructed LBA lookup table314using the valid data. Further, the controller308is adapted to write the reconstructed LBA lookup table314to the storage media310.

In a particular example, the first data block320has the most valid physical pages according to a comparison of the first and second metadata including LBA data324and344. Accordingly, the duplicate conflict resolution logic312selects the first data block320as the valid data block. In another particular example, the first and second data blocks320and340have the same number of valid physical pages, but the second data block340has greater data diversity (more different sectors) than the first data block320. In this instance, the duplicate conflict resolution logic312selects the second data block340as the valid data block. In still another particular example, when the first and second data blocks320and340include the same number of valid physical pages and the same data diversity, the duplicate conflict resolution logic312selects one of the data blocks, using another selection strategy. In a particular example, the other selection strategy may be used by the duplicate conflict resolution logic312to select a most recent data block, to randomly select the data block, to choose a data block from a sector that is less frequently used than another to load balance the usage of the storage media. In a particular example, any selection techniques can be used, when the first and second data blocks320and340are otherwise equal.

FIG. 4is a flow diagram of a particular illustrative embodiment of a method of resolving a data conflict within a memory device. At402, a first data block and a second data block are identified that are mapped to a single logical block address (i.e., the same logical block address). Moving to404, a first number of valid physical pages associated with the first data block and a second number of valid physical pages associated with the second data block are counted. Advancing to406, when the first number and the second number are not equal, the method advances to408and one of the first or the second data block is selected that has the greatest number of valid physical pages. The method terminates at410.

Returning to406, if the first number and the second number are equal, the method advances to412and a first number of sectors associated with the first data block and a second number of sectors associated with the second data block are determined. Continuing to414, if the first and second numbers of sectors are not equal, the method proceeds to416and one of the first or the second data block is selected that has the larger number of different sectors (i.e., the selected data block has greater data diversity). The method terminates at410.

Returning to414, if the first and second numbers of sectors are equal, one of the first or the second data block is selected based on another criterion. The method terminates at410.

FIG. 5is a flow diagram of a second particular illustrative embodiment of a method of resolving a data conflict within a memory device. At502, a data error is detected that include a first data block and a second data block that are mapped to a single logical block address of a storage media of a storage device. In a particular example, the data error is detected when first meta-data associated with the first data block and second meta-data associated with the second data block indicate the single logical block address. In a particular embodiment, the data error is detected by error detection logic associated with a controller of the storage device. In a particular example, the storage media is a solid-state data storage media.

Moving to504, a first number of valid physical pages in the first data block and a second number of valid physical pages in the second data block are counted. Continuing to506, the first data block is selected as a valid data block when the first number is greater than the second number of valid physical pages. Advancing to508, the second data block is selected as the valid data block when the second number is greater than the first number of valid physical pages. The method terminates at510.

In a particular embodiment, when the first number is equal to the second number of valid physical pages, the method further includes counting a third number of different sectors in the first data block and a fourth number of different sectors in the second data block, selecting the first data block when the third number is greater than the fourth number of different sectors, and selecting the second data block when the fourth number is greater than the third number of different sectors. In a particular embodiment, the third number and the fourth number of different sectors are counted using first spare data of a first page associated with meta-data related to the first data block and second spare data of a second page related to the second data block to determine a data usage frequency and a diversity of data contained in the first data block and the second data block. In a particular example, one of the first data block and the second data block is selected based on the usage frequency and the diversity of data.

In a particular example, when the third number is equal to the fourth number, the method further includes applying a selection algorithm to select one of the first data block and the second data block. In a particular example, the selection algorithm includes a modification date selection algorithm or a random data block selection algorithm. In another particular embodiment, the method includes detecting that an unexpected power loss event previously occurred and reconstructing a logical block address (LBA) lookup table from metadata associated with data blocks stored at the storage media. The data error is detected during reconstruction of the LBA lookup table.

In general, the systems and methods illustrated and described with respect toFIGS. 1-5above can be applied to different types of storage devices, including solid-state storage devices, storage devices that have rotatable storage media, or hybrid storage devices that include both solid-state storage media and rotatable storage media. Further, it should be understood that the methods disclosed with respect toFIGS. 4 and 5can be implemented to resolve a data conflict between metadata for multiple data blocks that refers to the same logical block address (LBA). Generally, the conflict arises after an unexpected power loss event where the stored LBA lookup table cannot be relied upon to contain the most up-to-date data related to data blocks stored at the storage media. Accordingly, the controller of the storage device is adapted to reconstruct the LBA lookup table from metadata associated with the data blocks by scanning the metadata of the storage media. In some instances, the data and the metadata may be stored at the same storage media. In another instance, the metadata and the data blocks may be stored at different storage media. In either case, the LBA lookup table is reconstructed from the metadata, and the duplicate conflict resolution logic is used to resolve conflicts when two or more metadata associated with different data blocks refers to the same LBA. The duplicate conflict resolution logic is adapted to select a latest copy of the data block from the multiple data blocks based on the number of valid physical pages and the amount of data diversity among the multiple data blocks.