Erasure correcting coding using data subsets and partial parity symbols

In an illustrative example, a method includes receiving data that includes a set of data symbols. The method further includes generating a set of parity symbols based on the set of data symbols using an erasure correcting code. The set of parity symbols includes at least a first parity symbol that is generated based on a first proper subset of the set of data symbols. The first parity symbol enables recovery of a data symbol of the first proper subset independently of a second proper subset of the set of data symbols.

FIELD OF THE DISCLOSURE

The present disclosure is generally related to electronic devices and more particularly to erasure correcting coding using data subsets for an electronic device.

DETAILED DESCRIPTION

Particular aspects of the disclosure are described below with reference to the drawings. In the description, common or similar features may be designated by common reference numbers. As used herein, “exemplary” may indicate an example, an implementation, and/or an aspect, and should not be construed as limiting or as indicating a preference or a preferred implementation. Although certain examples are described herein with reference to a data storage device, it should be appreciated that techniques described herein are applicable to other implementations. For example, information can be received by a communication device (e.g., wirelessly or from a wired network) alternatively or in addition to accessing information from a memory. Further, it is to be appreciated that certain ordinal terms (e.g., “first” or “second”) may be provided for ease of reference and do not necessarily imply physical characteristics or ordering. Therefore, as used herein, an ordinal term (e.g., “first,” “second,” “third,” etc.) used to modify an element, such as a structure, a component, an operation, etc., does not necessarily indicate priority or order of the element with respect to another element, but rather distinguishes the element from another element having a same name (but for use of the ordinal term). In addition, as used herein, indefinite articles (“a” and “an”) may indicate “one or more” rather than “one.” As used herein, a structure or operation that “comprises” or “includes” an element may include one or more other elements not explicitly recited. Further, an operation performed “based on” a condition or event may also be performed based on one or more other conditions or events not explicitly recited.

Referring toFIG. 1, a particular illustrative example of system is depicted and generally designated100. The system100includes a device102(e.g., a distributed storage system (DSS) or a data storage device) and a device180(e.g., an access device that accesses the device102). The device102includes a memory device103(e.g., an array of drives) and a controller130coupled to the memory device103. The device180may be coupled to the DSS via a wired connection (e.g., a bus or a wired network), a wireless connection, a local area connection (LAN), a wide area connection (WAN), the Internet, or a combination thereof.

The memory device103includes multiple devices, such as a first device106and a second device108. An example of a device of the memory device103is a memory die. Another example of a device of the memory device103is a memory drive, such as a flash memory drive, a resistive memory drive (e.g., a resistive random access memory (ReRAM) drive), a hard disk drive (HDD), or a hybrid HDD. The first device106may include a first memory104(e.g., a flash memory, a resistive memory, an HDD, or a hybrid HDD, as illustrative examples), and the second device108may include a second memory110(e.g., a flash memory, a resistive memory, an HDD, or a hybrid HDD, as illustrative examples).

The controller130may include an erasure correcting code engine132and an interface154(e.g., a host interface or an access device interface). The interface154is configured to receive data160from the device180in connection with a request for write access to the memory device103. The interface154is configured to provide the data160to the device180in connection with a request for read access to the memory device103. The controller130may store information138, such as a lookup table (LUT).

The erasure correcting code engine132may include an encoder134and a decoder136. The erasure correcting code engine132is configured to operate based on an erasure correcting code. For example, the encoder134is configured to encode the data160based on as erasure correcting code associated with a parity check matrix142. As another example, the decoder136is configured to decode data in accordance with parity check equations specified by the parity check matrix142.

During operation, the controller130may receive the data160from the device180. The data160may include a set of data symbols120. In an another example, the controller130may generate the set of data symbols120based on the data160, such as by encoding the data160based on an error correcting code (ECC), scrambling the data160, performing one or more other operations, or a combination thereof.

The controller130may encode the set of data symbols120in accordance with an erasure correcting code. For example, the controller130may input the data160to the erasure correcting code engine132to be encoded by the encoder134to generate a codeword140of an erasure correcting code associated with the parity check matrix142. The codeword140may include the set of data symbols120, parity symbols144generated based on the set of data symbols120in accordance with the erasure correcting code, and a set of “partial” parity symbols170.

The encoder134is configured to generate the set of partial parity symbols170based on subsets of the set of data symbols120using the erasure correcting code. As used herein, a “subset” refers to a proper subset of a set of elements (i.e., fewer than all elements of the set). The set of partial parity symbols170includes a first partial parity symbol172(e.g., a first partial parity symbol) that is generated based on a first subset of the set of data symbols120. For example, the first partial parity symbol172may be generated based on a first data symbol122of the set of data symbols120and further based on a second data symbol124of the set of data symbols120(e.g., independently of a third data symbol126of the set of data symbols120). The first partial parity symbol172enables recovery of a data symbol of the first subset independently of a second subset of the set of data symbols. For example, the first partial parity symbol172may enable recovery of the first data symbol122after an erasure event associated with the first data symbol122. As another example, the first partial parity symbol172may enable recovery of the second data symbol124after an erasure event associated with the second data symbol124. The second partial parity symbol174may be generated based on a different subset of the set of data symbols than the first partial parity symbol172.

The controller130may send the codeword140to the memory device103to be stored at one or more devices of the memory device103. For example, the controller130may send a write command to cause the memory device103to store the codeword140to the first device106, to the second device108, or a combination thereof. For example, one or more data symbols of the set of data symbols120may be stored at a different device of the memory device103as compared to one or more other data symbols of the set of data symbols120, such as by storing the first data symbol122to the first device106and by storing the second data symbol124to the second device108, as an illustrative example.

The controller130may cause the memory device103to access a representation of the codeword140, such as in response to a request for read access from the device180. The controller130may send a read command to cause the memory device103to sense data at the memory device103. As an illustrative example, the controller130may send a read command to cause the memory device103to sense a representation112of the first data symbol122(e.g., a version of the first data symbol122that may differ from the first data symbol122due to one or more errors). The memory device103may provide the representation112of the first data symbol122to the controller130.

In some circumstances, the controller130may detect an erasure event associated with one or more data symbols of the set of data symbols120. For example, the controller130may detect an erasure event associated with the first data symbol122in response to failure of the first device106. In some implementations, the memory device103may return an error message to the controller130in response to the read command from the controller130(instead of providing the representation112of the first data symbol122). In another example, the representation112may include corrupted data.

In response to detecting an erasure event associated with the first data symbol122, the controller130may access each other data symbol of the first subset of the set of data symbols120. For example, since the first subset includes the first data symbol122and the second data symbol124, the controller130may send a read command to the memory device103to cause the memory device103to provide the second data symbol124(or a representation of the second data symbol124) to the controller130. The controller130may also access one or more partial parity symbols of the set of partial parity symbols170associated with the first subset, such as the first partial parity symbol172.

The controller130may input the second data symbol124and the first partial parity symbol172to the erasure correcting code engine132to initiate a process to recover the first data symbol122. For example, the decoder136may be configured to recover the first data symbol122using the second data symbol124and the first partial parity symbol172associated with the first subset of data symbols without also accessing the third data symbol126and the second partial parity symbol174. Thus, fewer memory access operations may be performed (e.g., as compared to accessing each portion of the codeword140). In some cases, if a number of erasures in the first subset of data symbols exceeds an erasure correcting capability of the first partial parity symbol172, then the third data symbol126and the second partial parity symbol174may also be accessed to enable enhanced correction capability.

FIG. 2depicts particular aspects of an example of an erasure correcting code and parity splitting schemes associated with the erasure correcting code. The erasure correcting code and parity splitting schemes described with reference toFIG. 2may be used by the controller130ofFIG. 1. The examples ofFIG. 2correspond to an illustrative t=3 implementation (where t indicates a “maximum” number of erasures correctable using the erasure correcting code). In other examples, t may have a different value. Further, it is noted that the parity splitting schemes depicted inFIG. 2are illustrative and other parity splitting schemes are also within the scope of the disclosure.

FIG. 2illustrates an example of a codeword210of an erasure correcting code. The codeword210may correspond to the codeword140ofFIG. 1prior to splitting one or more parity symbols of the parity symbols144to generate the set of partial parity symbols170. For example, the codeword210may include a set of data symbols212corresponding to the set of data symbols120ofFIG. 1and may further include a set of parity symbols p0, p1, and p2corresponding to the parity symbols144ofFIG. 1. In other examples, a different number of parity symbols may be used. As an example, in an illustrative t=4 implementation, the codeword210may further include a parity symbol p3.

FIG. 2also depicts a codeword220in which a parity symbol p0of the codeword210has been “split” into partial parity symbols p0,0and p0,1. The partial parity symbol p0,0may be generated based on a first subset222of the set of data symbols212, and the partial parity symbol p0,1may be generated based on a second subset224of the set of data symbols212.

In other examples, a parity symbol may be split into more than two partial parity symbols. To illustrate, a codeword230may include partial parity symbols p0,0, p0,1, and p0,2. The partial parity symbol p0,0may be generated based on a first subset232of the set of data symbols212, the partial parity symbol p0,1may be generated based on a second subset234of the set of data symbols212, and the partial parity symbol p0,2may be generated based on a third subset236of the set of data symbols212.

In some examples, a subset of data symbols may be associated with multiple partial parity symbols, such as if multiple parity symbols of the set of parity symbols p0, p1, and p2are split. To illustrate, a codeword240includes partial parity symbols p0,0, p1,0, p0,1, and p1,1. The partial parity symbols p0,0and p0,1may be split from the parity symbol p0, and the partial parity symbols p1,0and p1,1may be split from the parity symbol p1. The partial parity symbols p0,0and p1,0may be associated with a first subset242of the set of data symbols212, and the partial parity symbols p0,1and p1,1may be associated with a second subset244of the set of data symbols212.

Alternatively or in addition, one or more partial parity symbols may be split (e.g., to create partial-partial parity symbols). To illustrate, a codeword250may include a partial parity symbol p1,0associated with a first subset252and may further include a partial parity symbol p1,1associated with a second subset254. The partial parity symbols p1,0and p1,1may be split from the parity symbol p1. The codeword250may also include a partial-partial parity symbol p0,0,0associated with a first subset253and a partial-partial parity symbol p0,0,1associated with a second subset255. The codeword250may further include a partial-partial parity symbol p0,1,0associated with a subset257of the second subset254and a partial-partial parity symbol p0,1,1associated with a second subset259of the second subset254.

In some examples, “unequal” protection may be applied to data symbols of a codeword. For example, a codeword260may include a first subset262and a partial parity symbol p1,0associated with the first subset262. The codeword260may also include a partial-partial parity symbol p0,0,0associated with a first subset263of the first subset262and a partial-partial parity symbol p0,0,1associated with a second subset265of the first subset262. The codeword260may further include partial parity symbols p0,1and p1,1associated with a second subset264. The codeword260illustrates an example in which the partial parity symbols p0,1and p1,1are not split into partial-partial parity symbols. Thus, the subsets262and264may be protected “unequally.”

FIG. 3illustrates an example of the parity check matrix142(“H”). In the illustrative example ofFIG. 3, t=4. In other cases, t may have a different value. Further, although certain examples herein are described with reference to a Vandermonde matrix, in other implementations, a different systematic H matrix may be used instead of a Vandermonde matrix.

In the example ofFIG. 3, the parity check matrix142includes a first set of columns (“A”) associated with data symbols d0, d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, and d11(e.g., the data symbols120ofFIG. 1) and further includes a second set of columns (an identity matrix, “I”) associated with parity symbols p0, p1, p2, and p3. Each entry of the first set of columns includes an exponentiation of a coefficient (e.g., α^0=1, α^1=α, α^2, etc.).

The example ofFIG. 3indicates that the data symbols d0-11may be divided into subsets in multiple levels. Each level of division is represented by one or more groups covering the same number of rows, but different columns of the parity check matrix142. To illustrate, a first level division of data set is illustrated by two groups covering the first three rows of the parity check matrix142, a second level division of data subset is indicated by the groups covering the first two rows of the parity check matrix, and a third level division of data subset is shown by the groups covering the first row of the parity check matrix. In other cases, data subset division may be performed differently than as illustrated in the example ofFIG. 3.

A particular subset of the data symbols d0-d11and a particular level of the parity check matrix142may define a group of coefficients of the parity check matrix142. For example, a subset d0-d5and a first level may define a group312. As another example, a subset d6-d11and the first level may define a group314. A subset d0-d2and the second level may define a group316, and a subset d3-d5and the second level may define a group318. A subset d6-d9and the second level may define a group320, and a subset d10-d11and the second level may define a group322.

FIG. 4depicts an illustrative example of the encoder134. The encoder134may include an adder circuit402, a multiplier circuit404, and a register406coupled to the adder circuit402and to the multiplier circuit404. The encoder134ofFIG. 4may correspond to a Vandermonde matrix implementation of the parity check matrix142. It should be appreciated that the example ofFIG. 4is illustrative and that other implementations are within the scope of the disclosure. For example, the encoder134may have a different configuration, such as if a systematic parity check matrix other than using a Vandermonde matrix is implemented as the parity check matrix142.

The adder circuit402may be configured to receive a first subset of a set of data symbols, such as the set of data symbols120ofFIG. 1. In the example ofFIG. 4, the set of data symbols120includes data symbols d0, . . . dk-2, dk-1. The multiplier circuit404may be configured to receive exponentiations of coefficients (e.g., αi) of the parity check matrix142ofFIG. 1.

The register406may be configured to receive a reset signal410to reset a state of the register406prior to processing of a second subset of the set of data symbols by the adder circuit402to enable separate encoding of multiple subsets of the set of data symbols120. For example, a reset input408of the register406may be configured to receive the reset signal410to reset the state of the register406to initialize the register406for processing of the second subset of the set of data symbols120. The register406may be further configured to output a first parity symbol piassociated with the first subset. For example, to encode subsets associated with the second level ofFIG. 3, the reset signal410may be applied after receiving (or processing) the data symbol d2at the encoder134, after receiving (or processing) the data symbol d5at the encoder134, and after receiving (or processing) the data symbol d9at the encoder134to enable generation of partial parity symbols for the groups316,318,320, and322.

FIG. 5depicts an illustrative example of the decoder136. The decoder136ofFIG. 5may correspond to a Vandermonde matrix implementation of the parity check matrix142. It should be appreciated that the example ofFIG. 5is illustrative and that other implementations are within the scope of the disclosure. For example, the decoder136may have a different configuration, such as if a systematic parity check matrix other than using a Vandermonde matrix is implemented as the parity check matrix142.

The decoder136may include a set of multiply-add (MA) circuits, such as a first MA circuit502and a second MA circuit504. The decoder136also includes a parity integration and pre-correction circuit506coupled to the set of MA circuits. The decoder136may also include control circuitry508, a lookup table (LUT)512, and a coefficient generator514. The LUT512may correspond to the information138ofFIG. 1. An MA circuit illustrated inFIG. 5may correspond to the encoder134ofFIG. 4(e.g., an MA circuit ofFIG. 5may include an adder circuit, a multiplier circuit, and a register, such as illustrated in the example ofFIG. 4).

The first MA circuit502may be configured to receive a first data symbol and to generate a first output based on the first data symbol. The second MA circuit504may be configured to receive the first data symbol and to generate a second output based on the first data symbol. The parity integration and pre-correction circuit506is configured to update the second output based on the first output. For example, the parity integration and pre-correction circuit506may include a multiplexer (MUX)516configured to select a corrected data value from the first output and to update the second output by inserting the corrected data value at the second output. The MUX516may be included in a circuit520of the parity integration and pre-correction circuit506, and the parity integration and pre-correction circuit506may include multiple copies of the circuit520each coupled to a corresponding MA circuit of the decoder136.

The decoder136may also include a MUX518coupled to the first MA circuit502. The MUX518may be configured to select one of a data value and a partial parity symbol and to provide the data value or the partial parity symbol to the first MA circuit502.

Referring toFIG. 6, a particular illustrative example of a method is depicted and generally designated600. The method600may be performed at a device, such as at the device102ofFIG. 1.

The method600includes receiving data that includes a set of data symbols, at602. The data may correspond to the data160ofFIG. 1or a version of the data160that is generated by the controller130based on the data160, and the set of data symbols may correspond to the set of data symbols120ofFIG. 1, as illustrative examples.

The method600further includes generating a set of parity symbols based on the set of data symbols using an erasure correcting code, at604. The set of parity symbols includes at least a first parity symbol that is generated based on a first subset of the set of data symbols, and the first parity symbol enables recovery of a data symbol of the first subset independently of a second subset of the set of data symbols. To illustrate, the set of parity symbols may correspond to the set of partial parity symbols170ofFIG. 1, and the first parity symbol may correspond to the first partial parity symbol172ofFIG. 1. The first subset may correspond to a subset of the set of data symbols120, such as the data symbols122and124, as an illustrative example. In this example, the second subset may include the third data symbol126, one or more other data symbols, or a combination thereof. Each data symbol of the second subset may be excluded from the first subset.

The first parity symbol and at least a second parity symbol of the set of parity symbols may correspond to partial parity symbols of a particular parity symbol associated with the erasure correcting code. As illustrative, non-limiting examples,FIGS. 2 and 3illustrate that the parity symbol p0may be split to form the partial parity symbols p0,0and p0,1, the partial parity symbols p0,0, p0,1, and p0,2, the partial parity symbols p0,0,0, p0,0,1, p0,1,0, and p0,1,1, or the partial parity symbols p0,0,0, p0,0,1, and p0,1. Alternatively or in addition, the parity symbol p1may be split to form the partial parity symbols p1,0and p1,1, as depicted with reference toFIGS. 2 and 3. Alternatively or in addition, the parity symbol p2may be split to form partial parity symbols associated with the groups312,314ofFIG. 3.

The set of parity symbols may further include a second parity symbol (e.g., the second partial parity symbol174) that is generated based on a third subset of the set of data symbols. In some examples, the third subset is included in the first subset. To illustrate, the subsets253,255are included in the first subset252, and the subsets257,259are included in the second subset254. As another example, the subsets263,265are included in the first subset262. To further illustrate,FIG. 3depicts that the groups316,318are included in the group312. In other examples, the third subset is larger than the first subset. In another example, the first subset may be the same as the third subset (i.e., the first subset and the third subset may include the same data symbols in some cases).

In some examples, the first subset and the third subset are associated with different levels (e.g., different sets of one or more rows) of the parity check matrix142. To illustrate, the subsets253,255,257, and259are associated with a different level as compared to the subsets252,254. As another example, the subsets263,265are associated with a different level as compared to the first subset262. To further illustrate,FIG. 3depicts that the groups316,318are associated with a different level as compared to the group312. Each of the groups316,318also includes one or more subsets that are associated with a different level as compared to the groups316,318. In other examples, the third subset is associated with a common level (e.g., a common set of one or more rows) of the parity check matrix142.

A cardinality of the first subset may be the same as a cardinality of the third subset. In this case, a number of data symbols of the first subset corresponds to a number of data symbols of the third subset. In other examples, a cardinality of the first subset is different than a cardinality of the third subset.

The method600may optionally include dividing the data into multiple subsets associated with different levels, where the multiple subsets include the first subset and the second subset. For example, the controller130may divide the set of data symbols120into multiple subsets, such as the first subset, the second subset, and the third subset.

The method600may optionally include generating an erasure correcting codeword based on the first subset and the second subset, such as by generating the codeword140. The method600may optionally include sending the set of data symbols and the set of parity symbols to one or more devices of a DSS. For example, the controller130may send the codeword140to the memory device103for storage at one or more devices of the memory device103.

Referring toFIG. 7, a particular illustrative example of a method is depicted and generally designated700. The method700may be performed at a device, such as at the device102ofFIG. 1.

The method700includes receiving a second data symbol of a set of data symbols in response to an erasure event associated with a first data symbol of the set of data symbols, at702. The first data symbol and the second data symbol correspond to a proper subset of the set of data symbols. To illustrate, the controller130may receive the second data symbol124in response to an erasure event associated with the first data symbol122, as described with reference toFIG. 1. The first data symbol122and the second data symbol124may be associated with a proper subset of the set of data symbols120(e.g., the first subset described with reference toFIG. 1).

The method700further includes receiving a first parity symbol associated with the proper subset, at704. For example, the controller130may receive the first partial parity symbol172, and the first partial parity symbol172may be associated with a proper subset of the set of data symbols120(where the proper subset includes the first data symbol122and the second data symbol124).

The method700further includes recovering the first data symbol based on the second data symbol and the first parity symbol, at706. For example, recovering the first data symbol may include performing an exclusive-or (XOR) operation based at least in part on the second data symbol and the first parity symbol by the parity integration and pre-correction circuit506. The XOR operation may be based further on an exponentiation of a coefficient of the parity check matrix142(e.g., for partial parity values of p1and partial parity values of p2).

In an illustrative example, the second data symbol is further associated with a second proper subset of the set of data symbols, and the method700further includes receiving a third data symbol associated with the second proper subset prior to recovering the first data symbol and receiving a second parity symbol associated with the second proper subset prior to recovering the first data symbol. In this example, the method700may also include recovering the second data symbol based on the third data symbol and the second parity symbol. As an illustrative example, a particular data symbol of the second subset254may be recovered (e.g., in response to an erasure event of the particular data symbol) based on other data symbols of the second subset254and further based on the partial parity symbol p1,1. If the particular data symbol is included in a smaller subset that is within the second subset254(e.g., the subset257or the subset259), then the third data symbol and the second parity symbol may be selected based on the smallest subset that includes the particular parity symbol (e.g., by using the subset257and the partial parity value p0,1,0, or the subset259and the partial parity symbol p0,1,1instead of using the second subset254and the partial parity symbol p1,1).

The method700may optionally include accessing information in response to the erasure event to determine that the first data symbol is associated with the second data symbol. For example, the information may correspond the information138, the LUT512, or both. The information may indicate a mapping of data symbols to subsets or boundaries of subsets of data symbols (e.g., that the data symbols d0and d5form boundaries of a subset associated with the first level, as depicted in the example ofFIG. 3).

The information may indicate that the first data symbol is included in multiple subsets of the set of data symbols, and the method700may include selecting the second data symbol in response to determining that the subset is of a lower cardinality than other subsets of the multiple subsets. For example, if the second data symbol is included in the subset257(and the second subset254), then the controller130may select the subset257instead of the second subset254in response to determining that the subset257is of a lower cardinality of the second subset254.

Erasure codes may be adopted to achieve reliable data storage. For large-scale distributed storage, besides redundancy, locality (e.g., the number of data and parity symbols accessed for failure recovery) may be reduced to increase data availability, lower network traffic, and reduce recovery latency. Aspects in accordance with the present disclosure describes may enable a flexible and low-complexity scheme for local erasure recovery. A code in accordance with the disclosure may have a reduced number of constraints associated with locality and/or a reduced number of parameters of the code as compared to certain other locally recoverable codes. The code may enable an easy tradeoff on the locality and redundancy and may achieve unequal protection over drives with different reliability. In addition, a code in accordance with the disclosure may feature a reduced computational overhead as compared to other erasure codes that do not support local recovery when the erasure-correction capability is relatively small (such as 2, 3 or 4).

Cloud computing and big data applications may use distributed storage system that can recover from several failures. Erasure codes may be used to recover from failures. In addition to redundancy, locality in terms of the number of symbols to access to recover erasures may affect data availability, network traffic, recovery latency for large-scale distributed systems.

Certain systems use Reed-Solomon (RS) codes, EVENODD codes, and other similar array codes for addressing disk failures. These codes may be maximum distance separable (MDS) codes, and they may feature a relatively small amount of redundancy as compared to certain other codes. In these codes, for an (n, k) code, k symbols may be used for recovery (regardless of the actual erasure number). In most cases, there are fewer failures than the designed “maximum” correction capability t. To improve the locality in these cases, diagonal parities may be used to reduce the number of symbols used to recover from a single failure in EVENODD codes by around ¼. As in certain classical EVENODD codes, this scheme has t=2, and the applicable n and k may be limited. Rotated RS and piggybacking frameworks may spread symbols across multiple stripes of existing codes and may correspond to MDS codes (if the underlying codes are MDS). These codes may be associated with certain constraints on the code parameters, and locality improvement of these codes may depend on the positions of the failed disks. Certain other codes may use expensive polynomial evaluation and interpolation over finite fields for encoding and decoding.

A technique in accordance with the disclosure uses a flexible yet low-complexity scheme for local erasure recovery using systematic parity check matrices of maximum distance separable (MDS) codes. Data symbols may be divided into multiple levels of subsets. The subsets in upper levels may be appended with more parities and hence may address more erasures. In an illustrative example, to recover from failures, only the symbols in the smallest subset with sufficient erasure-correction capability are used for recovery. As a result, significant locality reduction may be achieved. Although a code in accordance with the disclosure may not be MDS, such a code may not be associated with constraints on the code parameters and may not be associated with constraints on the cardinalities of the subsets (and hence locality reduction). Further, the subsets in the same level can be of different sizes. This aspect may enable unequal protection over heterogeneous drives with different reliability. A tradeoff on the locality and redundancy may be achieved through adjusting the number of levels of the subsets and cardinalities of the subsets.

An erasure-correction capability to be achieved in connection with certain systems may be relatively small, such as 2, 3 or 4, and a code in accordance with the disclosure may use Vandermonde matrices to generate parities. The Vandermonde matrices may enable efficient encoder and decoder implementations. For example, erasure recovery may be performed based on linear equations, which may be associated with a lower complexity than certain erasure-only Berlekamp-Massey Algorithm (BMA) techniques for RS decoding.

A minimum distance of an (n, k) linear block code may be at most n−k+1. When this bound is achieved, the code may be referred to as MDS, and a MDS code may be t=n−k erasure-correcting. Linear block codes may be defined by a parity check matrix H. A systematic parity check matrix H may have a format of H=[A|I]. A may be an (n−k)×k matrix, and I may be an (n−k)×(n−k) identity matrix. The corresponding codewords may include data symbols followed by parity symbols. A code corresponding to such a parity check matrix may be MDS if and only if each square submatrix formed by any i rows and any i columns for any i=1, 2, . . . , min{k, n−k} of A is nonsingular. A matrix that satisfies this condition is the Cauchy matrix, in which the entries are 1/(xi, yj), where (xi) and (yj) are sequences of distinct finite field elements, and where xi≠yjfor 0≤i<(n−k) and 0≤j<k. In some circumstances, encoding and decoding according to this matrix may have relatively high complexity. In some implementations, individual drives may be sufficiently reliable so that a large number of failures is relatively unlikely. If the erasure-correction capability, t, is relatively small (e.g., 2, 3, or 4), the Vandermonde matrix may be used as the A matrix for constructing MDS codes in order to simplify an encoder and a decoder. Such a parity check matrix for t-erasure correction may have the format

where α may indicate a primitive element of a finite field GF(2r) (k≤2r−1). Since αi≠αjand α2i≠α2jfor i≠j, all square submatrices in A2(V)and A3(V)are nonsingular. Hence, H2(V)and H3(V)may correspond to parity check matrices of MDS codes with t=2 and t=3, respectively, whose k can be any value less than 2r. H2(V)and H3(V)may correspond to the parity check matrices for a RAID-6 and triply-extended RS code. For Vandermonde matrices with four or more rows, a maximum number of columns in which there is no singular square submatrices may correspond to the maximum k of the MDS codes that can be constructed. The maximum k may depend on α or the primitive polynomial of which it is a root. For GF(28), the maximum k may be 27 for 4-erasure correction, and this value may be increased to 67 if the code is constructed over GF(210). The maximum k may be less for larger t since a Vandermonde matrix with more rows is more likely to have singular submatrices.

A flexible scheme in accordance with the disclosure may use a fraction of the codeword symbols for recovery in cases in which the erasure number is smaller than t. The scheme may be applied to any systematic parity check matrix, such as a scheme that uses a Cauchy matrix. In some circumstances, use of the Vandermonde matrix may result in lower complexity encoding and decoding.

H=[A|I] may correspond to a parity check matrix of a (k+t, k) MDS code, which is t-erasure-correcting. The entries of A may be indicated as ai,j(0≤i<t, 0≤j<k), the data symbols may be indicated by d0, d1, . . . , dk-1, and the parity symbols may be indicated by p0, p1, . . . , pt-1. In this example,

In certain conventional devices, if one erasure occurs associated with location j, data symbol djmay be recovered based on:

Such a device may access each of the other data symbols and p0. In response to i erasures, recovery may be performed based on i linear equations specified by the first i rows of H using the other data symbols and p0, p1, . . . pi-1. Locality may be defined as a number of symbols (including data symbols and parity symbols) accessed to in order to recover symbols of a particular number of erasures. In certain conventional devices, locality may be k−i+i=k regardless of the number of erasures.

If H is the parity check matrix of a (k+t, k) MDS code, then any k′<k columns of A and I (where I includes t rows and t columns) form the parity check matrix of a (k′+t, k′) MDS code, which is t-erasure-correcting. Therefore, instead of involving all data symbols in each parity, the data symbols may be divided into subsets, and parities may be generated for each subset to achieve local erasure recovery. Such a technique may include “breaking up” a code into independent pieces and generating t parities for each subset, which causes large storage overhead. Further, most instances of failures may include a relatively small number of erasures (e.g., much smaller than t). In this case, the failures may be recovered based on fewer linear equations involving fewer rows of H. Accordingly, subset division and parity padding may be performed in a hierarchical manner.

To enable t-erasure correction, all data symbols may be included in the pt-1parity. Further, p0, p1, . . . , pt-2may be “split” into partial parities, and each partial parity may be generated based on a subset of the data symbols. If the k data symbols are divided into l0subsets Sj(0≤j<l0), then pi(0≤i<t−2) may be split into pi,0, pi,1. . . pi,l0-1. Pi,jmay be determined based on the first i+1 rows of H in the columns corresponding to the subset Sj. Since any columns in the first t−1 rows of A padded with I(t-1)×(t-1)may form the parity check matrix of a code with a minimum distance t, then t−1-erasure correction may be facilitated for the data symbols in Sjusing p0,j, p1,j, . . . , pt-2,j. If pi(i=0, 1, . . . , t−2) are needed for t-erasure correction, pimay be generated by determining a sum of the partial parities based on:

Further, Sjmay be further divided into l1,jsubsets S1,j(0≤m≤li,j), and pi,j(0≤i<t−3) may be further split into pi,j,m(m=0, 1, . . . , l1,j-1). The data symbols in Sj,mand the t−2 parities pi,j,m(0≤i≤t−3) may be t−2-erasure-correcting. Pi,j,mmay be summed to recover pi,jfor correcting more erasures. This parity splitting process may be iterated. A device in accordance with the disclosure may include circuitry configured to generate the partial parities, to use the partial parities for erasure recovery, or both.

In some examples, redundancy and locality may be “tuned” by changing the number of levels and cardinalities of the subsets. Smaller subsets may be associated with reduced locality and also with more subsets (and more parities). Advantageously, cardinalities of the subsets in a particular level may be unequal. For example, one or more data symbols with higher failure probabilities may be allocated more parities to increase protection as compared to one or more data symbols with lower failure probabilities.

FIG. 2shows examples of a parity splitting scheme for t=3. InFIG. 2, shaded areas indicate data symbols, and parities within a rectangle are generated for data symbols in the same rectangle. For each example ofFIG. 2, Table 1 lists illustrative redundancy and locality in terms of the number of symbols accessed to recover all erasures (assuming the erasures are on the data symbols).

In the case that the locality differs with the erasure pattern, the digits in parentheses in Table 1 indicate the numbers of erasures in the last-level data subsets. In Table 1, scheme (a) may correspond to the codeword210, scheme (b) may correspond to the codeword220, scheme (c) may correspond to the codeword230, scheme (d) may correspond to the codeword240, scheme (e) may correspond to the codeword250, and scheme (f) may correspond to the codeword260.

To further illustrate, the codeword250ofFIG. 2includes four data subsets (the subsets253,255,257, and259) in the last level. In this example, if three erasures occur and the erasures are associated with different last-level subsets (denoted by (1, 1, 1, 0) in Table 1), then Table 1 indicates that 3 k/4 data and parity symbols may be accessed for recovery of the three erasures.

In scheme (b), by splitting data symbols into two subsets and dividing p0into two partial parity symbols, a single erasure may be recoverable by accessing k/2−1 data symbols and one parity symbol. Locality for correcting two or more erasures may correspond to k. By including more subsets and/or by allocating more parities to lower level subsets, locality for correcting two or more erasures may be improved, as indicated in schemes (c)-(f).

Erasures may be corrected using only the symbols in the smallest subsets with sufficient erasure-correction capability. To illustrate, if two erasures in S0,0and one erasure in S0,1occur in connection with scheme (e), then the erasure in S0,1may be corrected using p0,0,1and other data symbols in S0,1. After recovering the erasure in S0,1, erasures in S0,0may be corrected using p0,0,0, p1,0, and other data symbols in S0,0and S0,1. In this example, locality may correspond to k/4−1+1+k/4−2+1+1=k/2.

Scheme (f) illustrates an example of “unequal” protection. “Unequal” protection may be applied to increase protection for one or more devices associated with higher probability of failure as compared to one or more other devices. In an illustrative example, data symbols of the first subset262are stored at one or more devices of the memory device103that have a first reliability, and data symbols of the second subset264are stored at one or more devices of the memory device103that have a second reliability that is less than the first reliability.

In some cases, a technique in accordance with the disclosure may be used to correct more erasures than t. For example, seven erasures with an erasure pattern (3, 1, 2, 1) (e.g., where three erasures occur in the first subset253, one erasure occurs in the subset255, two erasures occur in the subset257, and one erasure occurs in the subset259) may be corrected in accordance with scheme (e).

FIG. 2shows certain examples that may be used based on probability and distribution of erasures. Although the examples ofFIG. 2correspond to t=3, in other examples t≥4.

Certain illustrative encoder and decoder implementation architectures may be configured to operate in accordance with Vandermonde matrices. For Vandermonde matrices, the parity computation may be performed based on:

To increase throughput, multiple data symbols to be written to a device of the memory device103may be processed in each clock cycle. The multiple data symbols may belong to different codewords (e.g., the codeword140and one or more other codewords), and multiple encoders (e.g., the encoder134and one or more other encoders) may be used, where one encoder processes one data symbol at a time. Instead of a general finite field multiplier, a “constant” multiplier (e.g., the multiplier circuit404) may be used to reduce a number of logic gates. To reduce encoder complexity, Horner's rule is applied so that:
pi=αi( . . . (αi(αidk-1+dk-2)+dk-3. . . +d1)+d0.

Accordingly, an encoder (e.g., the encoder134) may be implemented using a feedback loop (e.g., as illustrated byFIG. 4). To enable parity splitting operations, the register406may be reset (e.g., using the reset signal410) when data of the next subset is input to the encoder134(e.g., at the adder circuit402). In this case, the lower-level parities associated with pi(i>0) may no longer sum to pi. Accordingly, a decoding process may include multiplying the lower-level parities with αis, where s is the total cardinalities of the previous subsets in the same level as the current subset. For example, if each last-level subset has k/3 symbols in scheme (f) of Table 1, then the encoder134may be reset at clock cycle 0, at clock cycle k/3, and at clock cycle 2 k/3 to generate p0,0,0, p0,0,1, and p0,1. The first MA circuit502(or another circuit, such as another MA circuit that operates in parallel with the first MA circuit502) may be reset at clock cycle 0 and at clock cycle 2 k/3 to generate p1,0and p1,1. In this example,
p1=p1,0+α2k/3p1,1.

During a decoding process, if data to be decoded includes last-level subsets with one erasure, the erasure may be first recovered by XORing the other data symbols and the partial p0for the same subset. Then contributions of the last-level subsets may be added to the parities to recover the other erasures. This single-erasure pre-correction may reduce locality as compared to other techniques. For example, without pre-correction, a decoding process in accordance with scheme (e) of Table 1 to correct erasures having the pattern (2, 1, 0, 0) may include accessing p0,0,0, p0,0,1, p1,0, p2and each other (non-erased) data symbol. In this example, the locality may be k+1.

FIG. 5illustrates an example decoder architecture for t=4. In the example ofFIG. 5, erasures may be located at positions w, x, y, and z, and
qi=pi+Σj≠w,x,y,zαijdjfor 0≤i≤3.

The values qimay be computed by the MA circuits and the parity integration and pre-correction circuit506. The MA circuits ofFIG. 5may be as described with reference to the encoder134ofFIG. 4, except that djmay be set to zero when j=w, x, y or z. The LUT512may store αjfor 0≤j<k, and the coefficient generator514may compute all coefficients involving powers of a used by the decoder136. The parity integration and pre-correction circuit506may include three copies of the circuit520that connect to MAi(i=1, 2, 3). The data subsets may be processed out-of-order during decoding due to the parity integration and pre-correction circuit506.

After each subset is processed at the decoder136, the parity integration and pre-correction circuit506may add the output of MAito the partial parity of the same subset, and the sum may be multiplied by αis. Such products from different subsets may be accumulated by the adder-register loop of the circuit520to generate qi(i=1, 2, 3). The partial parities of p0may be added up by a XOR operation performed by the decoder136, such as by “sharing” the first MA circuit502(MA0).

A recovered erasure in a subset (e.g., dw) may be provided at the output of the first MA circuit502. The recovered erasure may be multiplied with αiwand added to an “intermediate” value, qi(i=1, 2, 3) by sharing the multipliers and feedback loops in the parity integration and pre-correction circuit506.

The erasures may be recovered based on linear equations. A device that operates based on properties of the Vandermonde matrix may enable simplification of certain operations. For example, dw, dx, dy, and dzmay be expressed as:

If three erasures occur, the decoder136may be configured to recover the erasures by performing operations based on the last three formulas in Equation 2 (e.g., without the product terms involving dz). If two erasures occur, the decoder136may be configured to recover the erasures by performing operations based on the last two formulas of Equation 2 (e.g., without the product terms involving dzand dy). The decoder136may be configured to recover a single erasure by performing operations based on dw=q0.

In some examples, erasures belong to different drives and are written back at different clock cycles. In this case, pipelining of operations may be implemented without causing additional latency. Two or more coefficients of Equation 2 may be determined in parallel with qi. For example, determination of qimay be performed in parallel with determining coefficients by the coefficient generator514. Because determination of qimay use a relatively large number of clock cycles, a relatively small number of logic circuits (e.g., multiplier circuits, adder circuits, and registers) may be implemented in the coefficient generator514using a time-multiplexing technique.

Although various components depicted herein are illustrated as block components and described in general terms, such components may include one or more microprocessors, state machines, or other circuits configured to enable such components to perform one or more operations described herein. For example, the erasure correcting code engine132may represent physical components, such as hardware controllers, state machines, logic circuits, or other structures, to enable the controller130to encode and decode partial parity symbols of an erasure correcting code.

Alternatively or in addition, the erasure correcting code engine132may be implemented using a microprocessor or microcontroller programmed to perform a hash operation. In a particular embodiment, the erasure correcting code engine132includes a processor executing instructions (e.g., firmware) that are stored at a drive of the memory device103. Alternatively, or in addition, executable instructions that are executed by the processor may be stored at a separate memory location that is not part of the memory device103, such as at a read-only memory (ROM) of the controller130.

It should be appreciated that one or more operations described herein as being performed by the controller130may be performed at the memory device103. As an illustrative example, in-memory ECC operations (e.g., encoding operations and/or decoding operations) may be performed at the memory device103alternatively or in addition to performing such operations at the controller130.

The device102may be coupled to, attached to, or embedded within one or more accessing devices, such as within a housing of the device180. For example, the device102may be embedded within the device180in accordance with a Joint Electron Devices Engineering Council (JEDEC) Solid State Technology Association Universal Flash Storage (UFS) configuration. To further illustrate, the device102may be integrated within an electronic device (e.g., the device180), such as a mobile telephone, a computer (e.g., a laptop, a tablet, or a notebook computer), a music player, a video player, a gaming device or console, an electronic book reader, a personal digital assistant (PDA), a portable navigation device, or other device that uses internal non-volatile memory.

In one or more other implementations, the device102may be implemented in a portable device configured to be selectively coupled to one or more external devices, such as a host device. For example, the device102may be removable from the device180(i.e., “removably” coupled to the device180). As an example, the device102may be removably coupled to the device180in accordance with a removable universal serial bus (USB) configuration.

The device180may correspond to a mobile telephone, a computer (e.g., a laptop, a tablet, or a notebook computer), a music player, a video player, a gaming device or console, an electronic book reader, a personal digital assistant (PDA), a portable navigation device, another electronic device, or a combination thereof. The device180may communicate via a controller, which may enable the device180to communicate with the device102. The device180may operate in compliance with a JEDEC Solid State Technology Association industry specification, such as an embedded MultiMedia Card (eMMC) specification or a Universal Flash Storage (UFS) Host Controller Interface specification. The device180may operate in compliance with one or more other specifications, such as a Secure Digital (SD) Host Controller specification as an illustrative example. Alternatively, the device180may communicate with the device102in accordance with another communication protocol. In some implementations, the device102may be integrated within a network-accessible data storage system, such as an enterprise data system, an NAS system, or a cloud data storage system, as illustrative examples.

In some implementations, the device102may include a solid state drive (SSD). The device102may function as an embedded storage drive (e.g., an embedded SSD drive of a mobile device), an enterprise storage drive (ESD), a cloud storage device, a network-attached storage (NAS) device, or a client storage device, as illustrative, non-limiting examples. In some implementations, the device102may be coupled to the device180via a network. For example, the network may include a data center storage system network, an enterprise storage system network, a storage area network, a cloud storage network, a local area network (LAN), a wide area network (WAN), the Internet, and/or another network.

To further illustrate, the device102may be configured to be coupled to the device180as embedded memory, such as in connection with an embedded MultiMedia Card (eMMC®) (trademark of JEDEC Solid State Technology Association, Arlington, Va.) configuration, as an illustrative example. The device102may correspond to an eMMC device. As another example, the device102may correspond to a memory card, such as a Secure Digital (SD®) card, a microSD® card, a miniSD™ card (trademarks of SD-3C LLC, Wilmington, Del.), a MultiMediaCard™ (MMC™) card (trademark of JEDEC Solid State Technology Association, Arlington, Va.), or a CompactFlash® (CF) card (trademark of SanDisk Corporation, Milpitas, Calif.). The device102may operate in compliance with a JEDEC industry specification. For example, the device102may operate in compliance with a JEDEC eMMC specification, a JEDEC Universal Flash Storage (UFS) specification, one or more other specifications, or a combination thereof.

A memory (e.g., a drive of the memory device103) may include a resistive random access memory (ReRAM), a flash memory (e.g., a NAND memory, a NOR memory, a single-level cell (SLC) flash memory, a multi-level cell (MLC) flash memory, a divided bit-line NOR (DINOR) memory, an AND memory, a high capacitive coupling ratio (HiCR) device, an asymmetrical contactless transistor (ACT) device, or another flash memory), an erasable programmable read-only memory (EPROM), an electrically-erasable programmable read-only memory (EEPROM), a read-only memory (ROM), a one-time programmable memory (OTP), another type of memory, or a combination thereof. In a particular embodiment, the device102is indirectly coupled to an accessing device (e.g., the device180) via a network. For example, the device102may be a network-attached storage (NAS) device or a component (e.g., a solid-state drive (SSD) component) of a data center storage system, an enterprise storage system, or a storage area network.

The semiconductor memory elements located within and/or over a substrate may be arranged in two or three dimensions, such as a two dimensional memory structure or a three dimensional memory structure. In a two dimensional memory structure, the semiconductor memory elements are arranged in a single plane or a single memory device level. Typically, in a two dimensional memory structure, memory elements are arranged in a plane (e.g., in an x-z direction plane) which extends substantially parallel to a major surface of a substrate that supports the memory elements. The substrate may be a wafer over or in which the layer of the memory elements are formed or it may be a carrier substrate which is attached to the memory elements after they are formed. As a non-limiting example, the substrate may include a semiconductor such as silicon.

A three dimensional memory array is arranged so that memory elements occupy multiple planes or multiple memory device levels, thereby forming a structure in three dimensions (i.e., in the x, y and z directions, where the y direction is substantially perpendicular and the x and z directions are substantially parallel to the major surface of the substrate). As a non-limiting example, a three dimensional memory structure may be vertically arranged as a stack of multiple two dimensional memory device levels. As another non-limiting example, a three dimensional memory array may be arranged as multiple vertical columns (e.g., columns extending substantially perpendicular to the major surface of the substrate, i.e., in they direction) with each column having multiple memory elements in each column. The columns may be arranged in a two dimensional configuration, e.g., in an x-z plane, resulting in a three dimensional arrangement of memory elements with elements on multiple vertically stacked memory planes. Other configurations of memory elements in three dimensions can also constitute a three dimensional memory array.

One of skill in the art will recognize that this disclosure is not limited to the two dimensional and three dimensional exemplary structures described but cover all relevant memory structures within the spirit and scope of the disclosure as described herein and as understood by one of skill in the art. The illustrations of the embodiments described herein are intended to provide a general understanding of the various embodiments. Other embodiments may be utilized and derived from the disclosure, such that structural and logical substitutions and changes may be made without departing from the scope of the disclosure. This disclosure is intended to cover any and all subsequent adaptations or variations of various embodiments. Those of skill in the art will recognize that such modifications are within the scope of the present disclosure.