Computing system with data protection mechanism and method of operation thereof

A computing system includes: a data block including data pages and each of the data pages includes data sectors and each of the data sectors include sector data and a sector redundancy; a storage engine, coupled to the data block, configured to: apply a first protection across the data pages, apply a second protection across the data sectors, and correct at least one of the data sectors when a sector correction with the sector redundancy failed with the first protection and the second protection.

TECHNICAL FIELD

An embodiment of the present invention relates generally to a computing system, and more particularly to a system for data protection.

BACKGROUND

Modern consumer and industrial electronics, especially devices such as graphical computing systems, televisions, projectors, cellular phones, portable digital assistants, and combination devices, are providing increasing levels of functionality to support modern life including three-dimensional display services. Research and development in the existing technologies can take a myriad of different directions. As data become more pervasive, existing and new systems need to interoperate and provide data reliability.

Thus, a need still remains for a computing system with data protection mechanism to provide improved data reliability and recovery. 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 increasingly critical that answers be found to 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.

SUMMARY

An embodiment of the present invention provides an apparatus, including a data block including data pages and each of the data pages includes data sectors and each of the data sectors include sector data and a sector redundancy; a storage engine, coupled to the data block, configured to: apply a first protection across the data pages, apply a second protection across the data sectors, and correct at least one of the data sectors when a sector correction with the sector redundancy failed with the first protection and the second protection.

An embodiment of the present invention provides a method including providing a data block including data pages and each of the data pages includes data sectors and each of the data sectors include sector data and a sector redundancy; applying a first protection across the data pages; applying a second protection across the data sectors; and correcting at least one of the data sectors when a sector correction with the sector redundancy failed with the first protection and the second protection.

An embodiment of the present invention provides a non-transitory computer readable medium including: providing a data block including data pages and each of the data pages includes data sectors and each of the data sectors include sector data and a sector redundancy; applying a first protection across the data pages; applying a second protection across the data sectors; and correcting at least one of the data sectors when a sector correction with the sector redundancy failed with the first protection and the second protection.

DETAILED DESCRIPTION

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 an embodiment of the present invention, some well-known circuits, system configurations, and process steps are not disclosed in detail.

The term “module” referred to herein can include software, hardware, or a combination thereof in an embodiment of 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 pressure sensor, an inertial sensor, a microelectromechanical system (MEMS), passive devices, or a combination thereof.

Referring now toFIG. 1, therein is shown a computing system100with data protection mechanism in an embodiment of the present invention. The computing system100is depicted inFIG. 1as a functional block diagram of the computing system100with a data storage system101. The functional block diagram depicts the data storage system101, installed in a host computer102, such as a server or workstation including at least a host central processing unit104, host memory106coupled to the host central processing unit104, and a host bus controller108. The host bus controller108provides a host interface bus114, which allows the host computer102to utilize the data storage system101.

It is understood that the function of the host bus controller108can be provided by host central processing unit104in some implementations. The host central processing unit104can be implemented with hardware circuitry in a number of different manners. For example, the host central processing unit104can be a processor, an application specific integrated circuit (ASIC) an embedded processor, a microprocessor, a hardware control logic, a hardware finite state machine (FSM), a digital signal processor (DSP), or a combination thereof.

The data storage system101can be coupled to a solid state disk110, such as a non-volatile memory based storage device having a peripheral interface system, or a non-volatile memory112, such as an internal memory card for expanded or extended non-volatile system memory.

The data storage system101can also be coupled to hard disk drives (HDD)116that can be mounted in the host computer102, external to the host computer102, or a combination thereof. The solid state disk110, the non-volatile memory112, and the hard disk drives116can be considered as direct attached storage (DAS) devices, as an example.

The data storage system101can also support a network attach port118for coupling a network120. Examples of the network120can be a local area network (LAN) and a storage area network (SAN). The network attach port118can provide access to network attached storage (NAS) devices122.

While the network attached storage devices122are shown as hard disk drives, this is an example only. It is understood that the network attached storage devices122could include magnetic tape storage (not shown), and storage devices similar to the solid state disk110, the non-volatile memory112, or the hard disk drives116that are accessed through the network attach port118. Also, the network attached storage devices122can include just a bunch of disks (JBOD) systems or redundant array of intelligent disks (RAID) systems as well as other network attached storage devices122.

The data storage system101can be attached to the host interface bus114for providing access to and interfacing to multiple of the direct attached storage (DAS) devices via a cable124for storage interface, such as Serial Advanced Technology Attachment (SATA), the Serial Attached SCSI (SAS), or the Peripheral Component Interconnect—Express (PCI-e) attached storage devices.

The data storage system101can include a storage engine115and memory devices117. The storage engine115can be implemented with hardware circuitry, software, or a combination thereof in a number of ways. For example, the storage engine115can be implemented as a processor, an application specific integrated circuit (ASIC) an embedded processor, a microprocessor, a hardware control logic, a hardware finite state machine (FSM), a digital signal processor (DSP), or a combination thereof.

The storage engine115can control the flow and management of data to and from the host computer102, and from and to the direct attached storage (DAS) devices, the network attached storage devices122, or a combination thereof. The storage engine115can also perform data reliability check and correction, which will be further discussed later. The storage engine115can also control and manage the flow of data between the direct attached storage (DAS) devices and the network attached storage devices122and amongst themselves. The storage engine115can be implemented in hardware circuitry, a processor running software, or a combination thereof.

For illustrative purposes, the storage engine115is shown as part of the data storage system101, although the storage engine115can be implemented and partitioned differently. For example, the storage engine115can be implemented as part of in the host computer102, implemented partially in software and partially implemented in hardware, or a combination thereof. The storage engine115can be external to the data storage system101. As examples, the storage engine115can be part of the direct attached storage (DAS) devices described above, the network attached storage devices122, or a combination thereof. The functionalities of the storage engine115can be distributed as part of the host computer102, the direct attached storage (DAS) devices, the network attached storage devices122, or a combination thereof.

The memory devices117can function as a local cache to the data storage system101, the computing system100, or a combination thereof. The memory devices117can be a volatile memory or a nonvolatile memory. Examples of the volatile memory can be static random access memory (SRAM) or dynamic random access memory (DRAM).

The storage engine115and the memory devices117enable the data storage system101to meet the performance requirements of data provided by the host computer102and store that data in the solid state disk110, the non-volatile memory112, the hard disk drives116, or the network attached storage devices122.

For illustrative purposes, the data storage system101is shown as part of the host computer102, although the data storage system101can be implemented and partitioned differently. For example, the data storage system101can be implemented as a plug-in card in the host computer102, as part of a chip or chipset in the host computer102, as partially implement in software and partially implemented in hardware in the host computer102, or a combination thereof. The data storage system101can be external to the host computer102. As examples, the data storage system101can be part of the direct attached storage (DAS) devices described above, the network attached storage devices122, or a combination thereof. The data storage system101can be distributed as part of the host computer102, the direct attached storage (DAS) devices, the network attached storage devices122, or a combination thereof.

Referring now toFIG. 2, therein is shown architectural views of the data protection mechanism in an embodiment.FIG. 2depicts a number representation of the data protection mechanism. The figures depict a data block202, a first protection204, and a second protection206. The figures on the left depict the first protection204below the data block202while the second protection206is shown on the right-hand side of the data block202. The figures on right depict the first protection204relative to the data block202as before but the second protection206is depicted above the data block202at an opposing side to the first protection204.

The data block202includes data to be protected. The data block202represent physical storage. The data block202can include storage elements from the host computer102, the network attached storage devices122, the DAS devices, or a combination thereof. As a more specific example, the data block202can represent physical storage including the memory devices117, the solid state disk110, the non-volatile memory112, the hard disk drives116or a combination thereof. The data block202can also represent a super block, which represents is a subdivision of a larger storage subsystem. When a storage device is too large to address directly a super block can be used to account for a portion of the storage capacity. As an example, the super block can contain up to a maximum addressable space (in 32 bit addressing that is 4 GB) the number of super blocks can form the entire capacity. An example application where a super block can be utilized is in flash memory where the accounting of wear activity must be maintained for data protection and wear leveling.

The data block202can include and be organized into data pages208. Each of the data pages208can include data sectors210. As an example, the data block202can be distributed across multiple devices, such as host computer102, the direct attached storage (DAS) devices, the network attached storage devices122, or a combination thereof.

As an example, the data protection mechanism for the data block202can be implemented as a 2D RAID parity with the first protection204, the second protection206, or a combination thereof. In this example, the data block202can be a RAID block. The data page208can represent data organized in pages. Each of the data pages208can include the data sectors210. Each of the data sectors210can include sector data212and the sector redundancy214, which can be an error correction sector. The sector data212and a sector redundancy214can make up a codeword216. The sector redundancy214provides capabilities for the error detection, error correction, or a combination thereof.

Examples of sector redundancy214error correction codes (ECC), a cyclic redundancy check (CRC), or other types of error detection or correction schemes. As more specific examples, the sector redundancy214can be systematic code or nonsystematic code, a block code, or a convolution code. As further examples, the sector redundancy can be a Reed-Solomon code or low density parity check (LDPC) code.

For illustrative purposes, an embodiment is described with two-dimensional (2D) protection for the data block202with the first protection204and the second protection206, although it is understood that various embodiments are not limited to 2D protection. For example, other protection can be applied to the same data block202, the same data sectors210, or a combination thereof similarly as the first protection204, the second protection206, or a combination thereof for N-dimensional protection. As example, various embodiments can be for further protection applied to the data block202, the data sectors210, or a combination thereof for 3D, 4D, 5D, etc. protection.

The first protection204can also be considered as part of the data block202and as one of the data page208. The first protection204, in this example, can be considered one sector for RAID parity page for other instances of the data page208in the data block202. The second protection206can be a protection for each of the data sectors210in each of the data page208and can represent a sector for page parity sector for the remaining data sectors210in one of the data page208.

One function of the first protection204as the RAID parity page can include providing parity information across the data page208in the data block202as the RAID block. There are at least 2 ways in which this can be accomplished.

In an embodiment, the first protection204as the RAID parity page could be the sum of all the data pages208in the data block202as the RAID block. However, this would mean there is no protection with the sector redundancy214for this page.

In this approach, the first protection204as the RAID parity page could be formatted like the data page208where each of the data sectors210is protected by the sector redundancy214, such as an ECC. Here, the payload for the data sectors210is the parity for payloads of the data page208. However, there are 3 possibilities for the parity sector, as an example.

First, the parity sector could be used for the page parity like the parity sector for the remaining data sectors210on the data page208. However, this means that the parity sectors on the data page208in the data block202will not be protected by the RAID parity.

Second, the parity sector could be used for parity for the parity sectors on the data page208. In this case, the first protection204as the RAID parity page would not have page parity information.

Third, there could be two parity sectors. An embodiment can provide parity information for the sectors in the RAID parity page, as the first protection204, and the other would provide parity information for all the parity sectors in the data block202with the second protection206.

An embodiment of the present invention provides iterative RAID assisted decoding. For this embodiment, the first protection204is described as the RAID parity page for third example above. In this case all parity sectors as a portion of the data sectors210are covered by RAID parity and the RAID parity page behaves like the data page208.

Referring now toFIG. 3, therein is shown a flow chart of the computing system100in an embodiment of the present invention. In this embodiment, the computing system100can decode the entire data block202ofFIG. 2as a RAID block. In a block302, the computing system100can first attempt to correct each of the data sectors210ofFIG. 2using the sector redundancy214ofFIG. 2as the sector ECC.

Further the first protection204ofFIG. 2can utilize soft information218associated with the data page208ofFIG. 2. The soft information218ofFIG. 2is provides some measure of reliability from a channel. Examples of the soft information can include Flash Log-Likelihood-Ratio (LLR) and can be utilized by the first protection204.

As a further example, the soft information218can also be obtained for the nonvolatile memory112ofFIG. 1. As a specific example, the nonvolatile memory112can include a multi-level cell (MLC) with coupled page and error transition probability due to the degradation that can result in MLC type for the nonvolatile memory112. For a two-bit per cell example for a MLC nonvolatile memory112, there are likely errors using Gray code:

In this example, the above transitions are the likely error transition state. And in MLC nonvolatile memory112, the most significant bit (MSB) page and least significant bit (LSB) page are in different memory page. By reading the error page's coupled page, the computing system100can determine the current states of both MSB page and LSB page. From the current states, the computing system100can figure out what is the likely state of the correct state. For example, if the error data unit is in MSB page and through XOR, the computing system100found out a total set of likely error locations which can be the sum of more than one error data unit. The computing system100can read the LSB page of the error data unit. And we can figure out the transition state possibility as shown in the table, as illustrated below:

If the current error data unit is LSB page, then the nonvolatile memory112can include the likely transition of the state as in the following table:

By reviewing at the summation of multiple page error pattern and the coupled page current state, the computing system100can narrow down the error bit assuming that different pages will have different current state value. For MSB bit page, the computing system100can mask out on average 75% of the bits in the data unit for error flip, as an example. For LSB bit page, the computing system100can mask out on average 25% of the bits in the data unit for error flip.

Returning to the description of the flow chart, if the block302is successful as determined by a block304, then the process can continue to process the data sector210. If it is uncorrectable as determined in the block304, the computing system100can apply RAID assisted decoding. As a more specific example, the codeword216ofFIG. 2can be a Bose, Chaudhuri, and Hocquenghem (BCH) codeword and the data protection mechanism as a RAID parity as noted above.

For illustrative purposes, the codeword216is descried as a BCH codeword, although it is understood the codeword216can be other types using different error detection and correction codes. For example, other block codes can be utilized to form the codeword216. As more specific examples, the codeword216can be formed with Reed-Solomon code or Low Density Parity Check (LDPC) code.

Assuming that c is uncorrectable in the block304, the computing system100with a block306compute the parities:

where s(i)=pQ(i){circumflex over ( )}pR(i) is the ithbit of s.

The computing system100can apply the BCH correcting to the resulting word (i.e. s+c). If c is the only erroneous codeword and s(i)=1 then c(i) is incorrect and will be corrected by this procedure.

If c(i) is incorrect the procedure fails to correct it if there are an odd number of error patterns in Q or R that have an error in position i. This is because at least one of the parity checks will be satisfied so s(i)=0. In addition, if c(i) is correct, then s(i)=1 if both Q and R contain and odd number of error patterns. In this case, the procedure forces c(i) to be incorrect. On the other hand, c(i) will be corrected if there are 0, 2, . . . , └q/2┘ errors for Q and 0, 2, . . . , └r/2┘ for R in position i.

Assume c has e>t and that we correct u errors and introduce v errors. The procedure fails if
e−u+v>t.(Equation 4)

In other words, the computing system100can attempt to correct c by first flipping bits220ofFIG. 2in c corresponding to the nonzero positions in s. Where the computing system100flip the bits220in the uncorrectable sector, as determined by a block308, corresponding to the nonzero bits220in where Q and R are the page and RAID parities and attempt correction again, iterating back to the block302, with the sector redundancy214in a block310. If the one of the data sectors210being decoded is still uncorrectable as determined in a block312, then an embodiment can continue to apply RAID assisted decoding to the other data page208in the data block202by iterating back to the block302.

As a more specific example, the computing system100can choose the first sector from the data sectors210ofFIG. 2on the first page from the data page208as the “target” sector, which can be used to measure performance The computing system100can generate all the data pages208in the data block202. In the block302, the computing system100then attempt to decode every one of the data sectors210in the target instance of the data page208using the sector redundancy214ofFIG. 2, such as the sector ECC, for each of the data sectors210. If the target sector is correctable, as determined in the block304, then an embodiment can be done or continue to process the data sector in the block314, otherwise an embodiment can apply RAID assist for the target sector in the block306. If this fails as determined in the block312, the computing system100continues to apply RAID assist to each uncorrectable instance of the data sectors210in the target instance of the data page208.

Whenever RAID assist is successful on a previously uncorrectable instance of the data sectors210, the computing system100can reapply RAID assist for the target sector. This is repeated until the computing system100are able to correct the target sector or the computing system100has applied RAID assist to every uncorrectable instance of the data sectors210in the target sector. If the computing system100have attempted correction on every uncorrectable instance of the data sectors210on the target page, the computing system100repeat the correction process with the next instance of the data page208. This continues, until the computing system100has processed all the data pages208or the computing system100is able to correctly decode the target sector.

In a further embodiment, the second protection206can be implemented with a row-enhanced Hamming code, which is expressed in the following matrix:

The row-enhanced Hamming code, as shown in Matrix 1, provides an all 1's row to the parity check matrix expressed below:

Matrix 2 is an example of a parity check matrix for an m-bit Hamming code can be constructed by choosing the columns to be all the nonzero binary vectors of length m. Matrix 2 is an example of a parity check matrix for m=3. For this example of H in matrix 2, a nonzero syndrome is the binary representation of the error location. For example, if the received word, w, has an error in location 6, then s=wHT=[0 1 1]6.

The row-enhanced Hamming code includes the parity row providing that every combination of 3 columns of row-enhanced Hamming code is linearly independent. As a result, it follows that the Hamming parity code has minimum distance at least 4. In addition, we also note for this choice of H for the row-enhanced Hamming code, we can still identify the error location by shifting the syndrome, left one bit (i.e. shift out the parity check bit).

Referring now toFIG. 3, therein is shown a graph depicting an example improvement in an embodiment of the present invention. The graph depicts the sector error rate along the y-axis and the raw bit error rate along the x-axis. There are two plots depicted on the graph. One depicts the sector failure rate with a worse performance for a given raw bit error rate than the other graph with the RAID parity approach as described in an embodiment of the present invention.

For illustrative purposes, the computing system100is described operating on the data block202ofFIG. 2, the first protection204ofFIG. 2, and the second protection206ofFIG. 2independent of location. It is understood that the data storage system101ofFIG. 1, the storage engine115ofFIG. 1, the DAS devices ofFIG. 1, the network attached storage devices122ofFIG. 1can provide the data block202, the first protection204, the second protection206, or a combination thereof. The data block202can also represent the non-volatile memory112, the memory devices117, the solid state disk110, the hard disk drives116, or a combination thereof.

The functions described in this application can be implemented as instructions stored on a non-transitory computer readable medium to be executed by the host central processing unit104ofFIG. 1, the data storage system101, the storage engine115, or a combination thereof. The non-transitory computer medium can include the host memory ofFIG. 1, the DAS devices ofFIG. 1, the network attached storage devices122, the non-volatile memory112, the memory devices117, the solid state disk110, the hard disk drives116, or a combination thereof. The non-transitory computer readable medium can include compact disk (CD), digital video disk (DVD), or universal serial bus (USB) flash memory devices. The non-transitory computer readable medium can be integrated as a part of the computing system100or installed as a removable portion of the computing system100.

Referring now toFIG. 5, therein is shown a flow chart of a method500of operation of a computing system100in an embodiment of the present invention. The method500includes: providing a data block including data pages and each of the data pages includes data sectors and each of the data sectors include sector data and a sector redundancy in a block502; applying a first protection across the data pages in a block504; applying a second protection across the data sectors in a block506; and correcting at least one of the data sectors when a sector correction with the sector redundancy failed with the first protection and the second protection in a block508.

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 an embodiment 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 an embodiment of the present invention consequently further the state of the technology to at least the next level.