Repair-optimal parity code

Techniques for generating parities and repairing data erasures using repair-optimal parities are disclosed. The system includes an encoding module, which receives a request to recreate data for a subset of a plurality of content stores. The encoding module generates a new first parity and a new second parity using a subset of remaining content from the plurality of content stores. The encoding module generates a first portion of the requested data using the new first parity and a first subset of an original first parity for the plurality of content stores and a second portion of the requested data using the new second parity and a second subset of an original second parity for the plurality of content stores. The encoding module may recreate the data for the content store using the first portion of the requested data and the second portion of requested data.

BACKGROUND

The present disclosure relates to repair-optimal parities for data recovery. In particular, the present disclosure relates to parities generated using a repair-optimal MDS code with optimal packetization.

Various algorithms are available for creating parity information for large amounts of data. Previous encoding techniques have shown that a large amount of data may be required to recreate lost data using parity information. Thus, there is a need for a parity code such that repairs from failure of any single storage device may be made using less of the remaining data.

SUMMARY

The present disclosure relates to systems and methods for repair-optimal parities for data recovery.

According to one innovative aspect, the subject matter described in this disclosure may be embodied in computer-implemented methods that include retrieving content from memory; generating a first part of a first parity of the content from memory, the first part including a horizontal parity of the content from memory; updating the first parity of the content from memory with a second part, the second part including each even row contribution of a first orthogonal permutation based on the content from memory; updating the first parity of the content from memory with a third part, the third part including a second orthogonal permutation based on a subset of the content from memory; generating a first part of a second parity of the content stored to memory, the first part including a third orthogonal permutation based on the content from memory; and updating the second parity of the content stored to memory with a subset of content from the second part of the first parity and the third part of the first parity, the subset of the content selected from even rows of the first parity.

Other implementations of one or more of these aspects include corresponding systems, apparatus, and computer programs, configured to perform the actions of the methods, encoded on computer storage devices. It should be understood that the language used in the present disclosure has been principally selected for readability and instructional purposes, and not to limit the scope of the subject matter disclosed herein.

DETAILED DESCRIPTION

Systems and methods for generating for repair-optimal parities for data recovery are described below. While the systems and methods of the present disclosure are described in the context of a particular system architecture, it should be understood that the systems and methods can be applied to other architectures and organizations of hardware.

FIG. 1is a high-level block diagram illustrating an example system100including a storage system having multiple storage devices112and a storage controller106. The system100includes clients102a. . .102n, a network104, and a storage system including storage devices112a. . .112n. In some embodiments, the system100may optionally include a storage controller106.

The client devices102a. . .102ncan be any computing device including one or more memory and one or more processors, for example, a laptop computer, a desktop computer, a tablet computer, a mobile telephone, a personal digital assistant (PDA), a mobile email device, a portable game player, a portable music player, a television with one or more processors embedded therein or coupled thereto or any other electronic device capable of making storage requests. A client device102may execute an application that makes storage requests (e.g., read, write, etc.) to the storage devices112. While the example ofFIG. 1includes two clients,102aand102n, it should be understood that any number of clients102may be present in the system. Clients may be directly coupled with storage sub-systems including individual storage devices (e.g., storage device112a) or storage systems behind a separate controller.

In some embodiments, the system100includes a storage controller106that provides a single interface for the client devices102to access the storage devices112in the storage system. In various embodiments, the storage devices may be directly connected with the storage controller106(e.g., storage device112a) or may be connected through a separate controller. The storage controller106may be a computing device configured to make some or all of the storage space on disks112available to clients102. As depicted in the example system100, client devices can be coupled to the storage controller106via network104(e.g., client102a) or directly (e.g., client102n).

The network104can be a conventional type, wired or wireless, and may have numerous different configurations including a star configuration, token ring configuration, or other configurations. Furthermore, the network104may include a local area network (LAN), a wide area network (WAN) (e.g., the internet), and/or other interconnected data paths across which multiple devices (e.g., storage controller106, client device112, etc.) may communicate. In some embodiments, the network104may be a peer-to-peer network. The network104may also be coupled with or include portions of a telecommunications network for sending data using a variety of different communication protocols. In some embodiments, the network104may include Bluetooth (or Bluetooth low energy) communication networks or a cellular communications network for sending and receiving data including via short messaging service (SMS), multimedia messaging service (MMS), hypertext transfer protocol (HTTP), direct data connection, WAP, email, etc. Although the example ofFIG. 1illustrates one network104, in practice one or more networks104can connect the entities of the system100.

FIG. 2is a block diagram illustrating an example system200for use as a storage controller. In one embodiment, the system200may be a client device102. In other embodiments, the system200may be storage controller106. In the example ofFIG. 2, the system200includes a network interface (I/F) module202, a processor204, a memory206, and a storage interface (I/F) module208. The components of the system200are communicatively coupled to a bus or software communication mechanism220for communication with each other.

The network interface module202is configured to connect system200to a network and/or other system (e.g., network104). For example, network interface module202may enable communication through one or more of the internet, cable networks, and wired networks. The network interface module202links the processor204to the network104that may in turn be coupled to other processing systems. The network interface module202also provides other conventional connections to the network104for distribution and/or retrieval of files and/or media objects using standard network protocols such as TCP/IP, HTTP, HTTPS, and SMTP as will be understood. In some implementations, the network interface module202includes a transceiver for sending and receiving signals using Wi-Fi, Bluetooth®, or cellular communications for wireless communication.

The processor204may include an arithmetic logic unit, a microprocessor, a general purpose controller or some other processor array to perform computations and provide electronic display signals to a display device. In some implementations, the processor204is a hardware processor having one or more processing cores. The processor204is coupled to the bus220for communication with the other components. Processor204processes data signals and may include various computing architectures including a complex instruction set computer (CISC) architecture, a reduced instruction set computer (RISC) architecture, or an architecture implementing a combination of instruction sets. Although only a single processor is shown in the example ofFIG. 2, multiple processors and/or processing cores may be included. It should be understood that other processor configurations are possible.

The memory206stores instructions and/or data that may be executed by the processor204. In the illustrated implementation, the memory206includes a storage manager210and an encoding module214. Although depicted as distinct modules in the example ofFIG. 2, the storage manager210may include the encoding module214or perform the functions of the encoding module as described herein. The memory206is coupled to the bus220for communication with the other components of the system200. The instructions and/or data stored in the memory206may include code for performing any and/or all of the techniques described herein. The memory206may be, for example, non-transitory memory such as a dynamic random access memory (DRAM) device, a static random access memory (SRAM) device, flash memory, or some other memory devices. In some implementations, the memory206also includes a non-volatile memory or similar permanent storage device and media, for example, a hard disk drive, a floppy disk drive, a compact disc read only memory (CD-ROM) device, a digital versatile disc read only memory (DVD-ROM) device, a digital versatile disc random access memories (DVD-RAM) device, a digital versatile disc rewritable (DVD-RW) device, a flash memory device, or some other non-volatile storage device.

Software communication mechanism220may be an object bus (e.g., CORBA), direct socket communication (e.g., TCP/IP sockets) among software modules, remote procedure calls, UDP broadcasts and receipts, HTTP connections, function or procedure calls, etc. Further, any or all of the communication could be secure (SSH, HTTPS, etc.). The software communication mechanism220can be implemented on any underlying hardware, for example, a network, the Internet, a bus, a combination thereof, etc.

The storage I/F module208cooperates with the storage manager210to access information requested by the client102. The information may be stored on any type of attached array of writable storage media, such as magnetic disk or tape, optical disk (e.g., CD-ROM or DVD), flash memory, solid-state drive (SSD), electronic random access memory (RAM), micro-electro mechanical and/or any other similar media adapted to store information, including data and parity information. However, as illustratively described herein, the information is stored on disks112. The storage I/F module208includes a plurality of ports having input/output (I/O) interface circuitry that couples with the disks over an I/O interconnect arrangement.

The storage manager212, stored on memory206and configured to be executed by processor204, facilitates access to data stored on the disks112. In certain embodiments, the storage manager212logically organizes data as a hierarchical structure of named directories and files on the disks112. The storage manager212cooperates with the encoding module214to encode data stored on the disks for recovery in the event of a failure of one or more disks. The storage manager, in some embodiments, may detect a failure of a disk and cooperate with the encoding module214to recreate the data stored on the failed disk.

Encoding module214may be stored in memory206and executed by processor204. The encoding module214is configured to encode parity data for a plurality of content stores. In one embodiment, to generate the parity data, the encoding module214encodes content stored to storage devices112to generate two parities of the content stored to storage devices112. In one embodiment, the first parity of the content stored to the storage devices112has three parts. The first part of the first parity of the content stored to the storage devices may be a horizontal parity. For example, assuming the content is stored across four content stores (e.g., storage devices112), the first data element of each content store is combined to create the first part of the first data element of the first parity. In one embodiment, the first data element of each content store is combined using an “exclusive or” (XOR) operation to create the first part of the first data element of the first parity. The second part of the first parity of the content stored to the storage devices may include a contribution of a content store for each even row of a first orthogonal permutation based on the content from the content stores. The third part of the first parity may include a second orthogonal permutation based on a subset of the content from the content stores.

In one embodiment, to create a first part of a second parity, the encoding module214may generate an orthogonal permutation of a first subset of the content stored to storage devices112and an orthogonal permutation of a second subset of content from the storage devices112in an inverse orientation to the orthogonal permutation of the first subset of content. For example, the encoding module214retrieves a first subset of content from memory and generates an orthogonal permutation of the first subset of content. In some embodiments, the encoding module214adds a correcting factor to the orthogonal permutation of the first subset of content. The encoding module214may then retrieve a second subset of content from memory and generates an orthogonal permutation of the second subset of content in an inverse orientation to the orthogonal permutation of the first subset of content. The encoding module214may, in some embodiments, add a correcting factor to the orthogonal permutation of the second subset of content. Thus, the encoding module214encodes content stored to the storage devices112using a recursive orthogonal permutation of the content, the correcting factors, to generate the first part of the second parity. A second part of the second parity, may be generated using a subset of content from the second part of the first parity and the third part of the first parity. In one embodiment, the second subset of content is selected from the even rows of the first parity.

In some embodiments, the encoding module214is configured to recreate lost content that was stored to a content store. In some embodiments, the encoding module214may recreate lost data on one or more disks by accessing only half of the remaining content in the content stores. To recreate the lost content, the encoding module214may generate a new first parity and a new second parity for the remaining content using the techniques described herein. The new first parity and the new second parity can be compared to original parities to recreate the lost content. The comparison may include computing an XOR operation on the new first parity and the first parity for the content stored to the plurality of content stores to generate a first portion of the lost content and a an XOR operation on the new second parity and the second parity for the content stored to the plurality of content stores to generate a second portion of the lost content.

In some embodiments, the encoding module214is configured to recreate lost content for a parity of a plurality of content stores. In some embodiments, the encoding module214may repair failure of a parity of the plurality of content stores by accessing half of the remaining content. To repair the failure of the parity, the encoding module214may retrieve a first subset of content from the plurality of content stores and a second subset of content from a remaining parity for the plurality of content stores. The encoding module214, may be configured to recreate the lost data for the second parity using the first subset of content from the plurality of content stores and the second subset of content from the remaining parity for the plurality of content stores. In one embodiment, the encoding module214may compute an XOR operation on the first subset of content from the plurality of content stores and the second subset of content from the remaining parity for the plurality of content stores to repair failure of the parity.

FIG. 3is a block diagram illustrating a construction for generating a portion of a repair-optimal parity for content stored across four content stores. In the example construction shown inFIG. 3, each of the content stores contains eight data elements. In general, for k content stores, the number of elements in each content store is 2k-1. The information element in column i and row j is denoted as Ci[j]. There are two parity nodes created for the content stored across the four content stores. The second parity is encoded according to the lines inFIG. 3. For each P2[i], the parity is encoded using the line corresponding to element C0[i]. For example, the first element of the second parity P2[0] is encoded according to the line that starts at element C0[0].

The element P2[i] is encoded as the parity of data elements in the line corresponding to data element C0[i]. In addition, if there are shaded elements in the line, a correcting factor is added to P2[i]. In one embodiment, for each shaded element in the line, the correcting factor includes all elements depicted to the right of the shaded element in the example construction ofFIG. 3. For example, for the second element in the second parity (P2[1]=C0[1]+C1[0]+C2[2]+C3[6]+C0[0]), the elements C0[1], C1[0], C2[2] and C3[6] form the parity element using the construction inFIG. 3. Additionally, since C1[0] is shaded, the element to the right of C1[0] (C0[0]) is also added to the parity element.

The shaded elements inFIG. 3are those Ci[j], for which the ith bit in the binary representation of j over k−1 bits is equal to i−1th bit, where, if the i−1th bit is −1, the −1th bit is considered as 0, and k is the total number of content stores. In the example ofFIG. 3, where k=4 and in the case of C1[3], the binary representation of j over k−1 bits is 011 (i.e., j=3 and k−1=3). Continuing with the example of C1[3], where i=1, the ith bit is the 1st bit and the i−1th bit is the 0th bit. In the binary representation 011, the 0th bit is 1, the 1st bit is 1 and the 2nd bit is 0. Thus, since the ith bit is equal to the i−1th bit (i.e., the 1st bit and the 0th bit are both 1), the element is shaded and a correcting factor is added to the second parity along with the element C1[3]. The first parity and the second parity are described below in more detail with reference toFIGS. 4, 5A, and 5B.

FIG. 4is a block diagram illustrating contents of two content stores, a first parity, and a second parity for the two content stores, according to a butterfly code. In the example ofFIG. 4, the second parity for the two content stores are generated using an orthogonal permutation as shown above inFIG. 3. In the example ofFIG. 4, the content stores402and404are referred to as C1and C0, respectively below. The first parity406is referred to below as P1and the second parity408is referred to below as P2. In this example, the first data element (e.g., bit, byte, block, or the like) stored to content store C0is C0[0], the first data element stored to content store C1is C1[0], the second data element stored to content store C0is C0[1], and the second data element stored to content store C1is C1[1]. While depicted in the example ofFIG. 4as distinct content stores, it should be understood that one or more of the content stores may be stored on the same hardware or various hardware devices.

In one embodiment, to generate the first parity406of this example, a combinatorial circuit may be used to “XOR” all of the corresponding bits stored to content stores C0and C1. For example, the first data element of the first parity406is a horizontal parity of the first data elements of content stores402and404. As shown in the example ofFIG. 4, the first data element of the first parity406is represented by C0[0]+C1[0] in the first row, which is calculated by XOR-ing C0[0] from the first row of C0and C1[0] from the first row of C1. In some embodiments, the second parity P2may be generated using an orthogonal permutation of the content from the content stores C0and C1and a correcting factor.

FIGS. 5A and 5Bdepict a block diagram illustrating contents of four content stores, a first parity, and a second parity for the four content stores. In the example ofFIGS. 5A and 5B, the first parity and the second parity are generated according to a butterfly code construction. Butterfly code is a 2-parity maximum distance separable (MDS) erasure code over GF(2) with an efficient recovery ratio. The butterfly code has a code rate of k/k+2, where k is the number of systematic nodes or contents stores in the system. The butterfly code has an additional property that allows for recovery from failure of one content store using only half of the remaining data.

In the example ofFIG. 5A, the content stores502-508are referred to as C0, C1, C2, and C3, respectively, and the first parity504is referred to as P1. As described above, the first parity510may be calculated as a horizontal parity of the data elements in the content stores502-508. For example, the first data element of P1includes C0[0], C1[0], C2[0] and C3[0] which is calculated by the XOR combination of the first data element of each content store. While depicted in the example ofFIGS. 5A and 5Bas distinct content stores and parities, it should be understood that one or more of the content stores and the parities may be stored on the same hardware or various hardware devices.

The parities for butterfly code may be generated in a recursive manner. For example, the encoding module214encodes the first two data elements stored to content stores C0and C1to generate a first portion514of the second parity512. The first portion514is a butterfly code for k=2 (e.g., for two data stores). In one embodiment, the encoding module may calculate the first portion514using techniques described above with reference toFIG. 3. The encoding module may then generate a second portion520of the second parity512. The second portion520of the second parity512is a second parity for k=3, generated using butterfly code and includes the first portion514including a first orthogonal permutation and a correcting factor, a second portion516including a second orthogonal permutation in an inverse orientation to the first and a correcting factor, and a portion518including the data from the content store C2and a correcting factor. Thus, the construction of the second parity512may be broken down into recursively smaller constructions of two k−1 construction and correcting factors.

FIGS. 5C and 5Ddepict a block diagram illustrating contents of four content stores, a first parity, and a second parity for the four content stores. In the example ofFIGS. 5A and 5B, the first parity and the second parity are generated according to a repair-optimal monarch code construction. Monarch code is a repair optimal (k+2, k) maximum distance separable (MDS) code for all nodes, including the first and second parities. The monarch code has the property of the butterfly code that allows for recovery from any two systematic node failures. Further, the monarch code allows for recovery from failure of one content store using only half of the remaining data. The monarch code has an additional property that allows for recovery from failure of any parity using only half of the remaining data.

In the example ofFIG. 5C, the content stores502-508are referred to as C0, C1, C2, and C3, respectively, and the first parity530is referred to as P1. As described above, the first parity530using monarch code may be calculated in three parts. The first part532of the first parity is a horizontal parity of the data elements in the content stores502-508. For example, the first part of the first data element of P1includes C0[0], C1[0], C2[0] and C3[0] which is calculated by the XOR combination of the first data element of each content store, as described with reference toFIG. 5A. The second part534of the first parity P1is an even row contribution of an orthogonal permutation of the content from the content stores. In the example ofFIG. 5C, the first orthogonal permutation is the butterfly code described with reference toFIGS. 5A and 5B. For example, the elements of the second part534of the first parity530is the even row contribution of the content store C0in an orthogonal permutation of the content from the content stores. The encoding module214, updates the first parity with a third part536. In the example ofFIG. 5C, the third part536of the first parity P1includes elements generated by an orthogonal permutation over even rows of content stores C1, C2, and C3. In the example ofFIG. 5C, the third part536of the first parity530includes all elements of content stores C1, C2and C3from the even rows of the second parity512generated using the butterfly code, described with reference toFIG. 5B.

The second parity540using monarch code may be generated in two parts. For example, the encoding module214encodes the data elements stored to content stores C0, C1, C2and C3in a manner such that the first part542of the second parity540is a butterfly code of the content stores C0-C3without elements from content store C0in the lower right triangle. In one embodiment, the encoding module214may generate a subset of the first part of the second parity using techniques described with reference toFIG. 5B. For example, while generating the first part of the second parity, the encoding module214omits the contribution of the content store C0in the correcting factor of the orthogonal permutation in an inverse orientation. With reference toFIG. 5B, the orthogonal permutation in an inverse orientation for k=2 is 516. The encoding module214next, updates the second parity540with a second part544. The second part544of the second parity540is selected from the even rows of the second part534and the third part536of the first parity530. For example, the second part of the second parity540includes 2ith row elements from the second and third part of the first parity for each i, where i=1 . . . k−2, and a reflection of all elements before the 2ith row for all values of i. In the example ofFIG. 5D, the third row of the second part544of the second parity540is the 21th row of the second part534and the third part536of the first parity530. In this case, there is no element before the 21th row. The fifth row of the second part544of the second parity540is the 22th row of the second part534and the third part536of the first parity530. The reflection of the 22th row of the second and third part of the first parity530is the 21th row. Thus, the seventh row of the second part544of the second parity540is the reflection of the 22th row of the second and third part of the first parity530. In this example, since the value of k is 4, the values of i will be 1 and 2. While depicted in the example ofFIGS. 5C and 5Das distinct content stores and parities, it should be understood that one or more of the content stores and the parities may be stored on the same hardware or various hardware devices.

FIG. 6is a flowchart of an example method600for encoding data stored to a plurality of content stores to generate a first parity (e.g., P1as shown in the example ofFIG. 5C) and a second parity (e.g., P2as shown in the example ofFIG. 5D) using monarch code. At602, the encoding module214retrieves content from memory. In one embodiment, the memory may be a primary memory, for example, non-transitory memory such as a dynamic random access memory (DRAM) device and a static random access memory (SRAM). In one embodiment, the memory may include systematic nodes residing on separate disks. In another embodiment, the memory may include content stores residing on the same disk. The encoding module214may retrieve the content in response to a request to encode data (e.g., when the memory includes a threshold amount of data). In some embodiments, the encoding module214may be configured to encode content as it is received from a client device102and stored to disk112.

At604, the encoding module214generates a first part of a first parity of the content from memory. The encoding module214calculates the first part of the first parity as a horizontal parity for the content from memory. For example, the first part of the first element of the first parity is calculated by performing an XOR operation on the first data element (e.g., bit, byte, block, etc.) of each content store from memory. As depicted in the example ofFIG. 5C, the encoding module214calculates the first data element of the first part532of the first parity530by performing an XOR operation on the first data element of the first content store (C0[0]), the first data element of the second content store (C1[0]), the first data element of the third content store (C2[0]) and the first data element of the fourth content store (C3[0]). Similarly, the second data element of the first part532of the first parity530is calculated by performing an XOR operation on the second data element of the first content store (C0[1]), the second data element of the second content store (C1[1]), the second data element of the third content store (C2[1]) and the second data element of the fourth content store (C3[1]).

Returning to the example ofFIG. 6, the encoding module214updates606the first parity of the content from memory with a second part, the second part including an even row contribution of a first orthogonal permutation of the content from memory. For example, the first orthogonal permutation may be generated using the butterfly construction described inFIG. 5B. As shown in the example ofFIG. 5C, the even row contribution of the first content store is C0[0] for the second row, C0[0] for the fourth row, C0[2] for the sixth row and C0[0] for the eighth row.

Returning toFIG. 6, the encoding module214updates608the first parity of the content from memory with a third part, the third part including a second orthogonal permutation based on a first subset of the content from memory. In some embodiments, the first subset of content includes even rows of the plurality of content stores without the first content store. The second orthogonal permutation may be a butterfly construction over the even rows of content stores C1, C2and C3, generated using techniques described inFIG. 5B.

The encoding module214, generates610a first part of a second parity of the content from memory, the first part including a third orthogonal permutation based on the content from memory. For example, the encoding module214generates the first part of the second parity using the butterfly code described inFIG. 5B. In some embodiments, the third orthogonal permutation does not include data elements from the first content store (C0) in the correcting factor of the orthogonal permutation in an inverse orientation, while generating the second parity using techniques described inFIG. 5B.

The encoding module214updates612the second parity of the content from memory with a second subset of content. In one embodiment, the second subset of content is selected from the even rows of second part of the first parity and the third part of the first parity. In the example ofFIGS. 5C and 5D, the second part544of the second parity540includes 2ith row elements from the second part534and third part536of the first parity530for each i, where i=1 . . . k−2, and a reflection of all elements before the 2ith row for all values of i.

The encoding module may write the first parity on a first content store (e.g., storage device112) and the second parity on a second content store (e.g., storage device112). Although the examples ofFIGS. 3, 4 and 5show parities determined for a code word where k=4, the repair optimal parities may be generated for any value of k.

FIG. 7is a flowchart of an example method for recreating data for a content store from a plurality of content stores including a parity. At702, the encoding module214receives a request to recreate data for a content store of a plurality of content stores. In one embodiment, the request may be a failure notification of a particular content store. The encoding module214may retrieve a subset of the content from the remaining content stores in response to a request to recreate data. In another embodiment, the encoding module may receive a request to recreate data for more than one content store. At704, the encoding module214generates a new first parity using a subset of remaining content from the plurality of content stores. The new first parity may be calculated using methods described with reference toFIGS. 5 and 6. The subset of remaining content may be selected based on the failed content store. In some embodiments, the subset of remaining content may be pre-determined for failure of a particular content store. For example, the subset of content may be half of the rows of the remaining content stores for failure of any one content store.

At706, the encoding module214generates a new second parity using the subset of the remaining content from the plurality of content stores using the construction described above with reference toFIGS. 5 and 6. At708, the encoding module214generates a first portion of the requested data using the new first parity and a first subset of an original first parity for the plurality of content stores. In some embodiments, the original first parity for the plurality of content stores was encoded when the data was stored to the plurality of content stores. In one embodiment, the encoding module214compares the new first parity with half of the original first parity for the plurality of content stores to determine the first portion of the requested data. For example, the encoding module determines the first portion of the requested data using an XOR operation on the new first parity and a subset of data elements from the original first parity for the plurality of content stores. At710, the encoding module214generates a second portion of the requested data using the new second parity and a second subset of an original second parity for the plurality of content stores. In some embodiments, the encoding module214may compare the new second parity with half of the original second parity for the plurality of content stores. For example, in order to recreate lost data for two content stores, the comparison will result in data elements from the new first parity and the new second parity, some including more than one element of lost data. At712, the encoding module214recreates the data for the content store using the first portion of the requested data and the second portion of requested data. For example, the lost data for two content stores may be obtained by linear clearing. In one embodiment, the lost data may be obtained by another XOR operation between the first portion of requested data and the second portion of the requested data. The method for recreating data for a content store is depicted in the example data shown inFIGS. 8A and 8B.

FIGS. 8A and 8Bdepict a block diagram illustrating an example of recreating data for a content store. In the example ofFIGS. 8A and 8B, the data stored on content store C0is lost, for example through a disk failure or the like. For one failure recovery, the present invention uses half of the remaining data elements (e.g., half of the original content stored to the content stores, half of the content stored to the original first parity, half of the content stored to the original second parity) to recreate the lost content store. In the example ofFIG. 8A, where content store C0is lost, a subset of the remaining data used to recreate C0is the first row802of the remaining content stores, the third row804of the remaining content stores, the fifth row806of the remaining content stores and the seventh row808of the remaining content stores. In order to recreate lost data for content store C0, the encoding module214, generates a new first parity and a new second parity with the subset of the remaining data using techniques described herein with reference toFIGS. 3-6. The encoding module214then compares the new first parity with a subset of an original first parity for the plurality of content stores (e.g., the subset of the original first parity described above with respect toFIG. 8Ais the first row810of the original first parity, the third row812of the original first parity, the fifth row814of the original first parity and the seventh row816of the original first parity) to determine a first portion of the lost data.

The encoding module214may also compare the new second parity with a subset of the original second parity for the plurality of content stores (e.g., the second parity P2described with reference toFIG. 5B) to determine a second portion of the lost data. As shown in the example ofFIGS. 8A and 8B, the encoding module214generates the new second parity by using the first row802of the remaining content stores, the third row804of the remaining content stores, the fifth row806of the remaining content stores and the seventh row808of the remaining content stores. The encoding module214, then compares the new second parity with a subset of the second parity described inFIG. 8B(e.g., the subset of the original second parity described above with respect toFIG. 8Bis the second row850of the original second parity, the fourth row852of the original second parity, the sixth row854of the original second parity and the eighth row856of the original second parity). The encoding module214may then recreate the data for the content store C0using the first comparison results and the second comparison results. The encoding module214may then return the result to be recreated on a new content store.

FIG. 9is a flowchart of an example method for recreating data for a parity of a plurality of content stores. At902, the encoding module214receives a request to recreate data for a parity of a plurality of content stores. In one embodiment, the request may be a failure notification of the second parity of the plurality of content stores. At904, the encoding module214retrieves a first subset of content from the plurality of content stores. The first subset of content may be half of the rows of the plurality of content stores. In some embodiments, the first subset of content may be pre-determined for failure of the parity.

At906, the encoding module214retrieves a second subset of content from a remaining parity for the plurality of content stores. In some embodiments, the remaining parity is a first parity for the plurality of content stores, which was encoded when the data was stored to the plurality of content stores. In one embodiment, the encoding module214retrieves half of the remaining parity for the plurality of content stores. At908, the encoding module214recreates the data for the second parity using the first subset of content from the plurality of content stores and the second subset of content from the remaining parity for the plurality of content stores. In some embodiments, the lost data for two content stores may be obtained by using techniques described with reference toFIG. 3-6. The method for recreating data for a content store is depicted in the example data shown inFIGS. 10A and 10B.

FIG. 10Adepicts a block diagram illustrating an example of recreating data for a first parity of a plurality of content stores. In the example ofFIG. 10A, the data elements of a first parity are lost, for example through a disk failure or the like. For the failure recovery of the first parity, the present invention uses half of the remaining data elements (e.g., half of the original content stored to the content stores and half of the content stored to the second parity of the plurality of content stores) to recreate the lost first parity. In the example ofFIG. 10A, in order to recreate lost data for the first parity, the encoding module214, retrieves the fifth row1002of the content stores (C0[4], C1[4], C2[4], C3[4]), the sixth row1004of the content stores (C0[5], C1[5], C2[5], C3[5]), the seventh row1006of the content stores (C0[6], C1[6], C2[6], C3[6]) and the eighth row1008of the content stores (C0[7], C1[7], C2[7], C3[7]). The encoding module214also retrieves the fifth row1010of the second parity of the plurality of content stores, the sixth row1012of the second parity of the plurality of content stores, the seventh row1014of the second parity of the plurality of content stores and the eighth row1016of the second parity of the plurality of content stores. The encoding module214generates the lost first parity by using the retrieved portions from the content stores and the retrieved portion from the second parity of the plurality of content stores. The encoding module214may generate the first parity using techniques described with reference toFIG. 3-6.

FIG. 10Bdepict a block diagram illustrating an example of recreating data for a second parity of a plurality of content stores. In the example ofFIG. 10, the data elements of a second parity are lost, for example through a disk failure or the like. For the failure recovery of the second parity, the present invention uses half of the remaining data elements (e.g., half of the original content stored to the content stores and half of the content stored to the original first parity) to recreate the lost second parity. In the example ofFIG. 10B, in order to recreate lost data for the second parity, the encoding module214, retrieves the first element1022of the first content store (C0[0]), the third element1024of the first content store (C0[2]), the fifth element1026of the first content store (C0[4]) and the seventh element1028of the first content store (C0[6]). The encoding module214also retrieves the second row1030of the remaining content stores (C1[1], C2[1], C3[1]), the fourth row1032of the remaining content stores (C1[3], C2[3], C3[3]), the sixth row1034of the remaining content stores (C1[5], C2[5], C3[5]) and the eighth row1036of the remaining content stores (C1[7], C2[7], C3[7]).

The encoding module214then retrieves the second row1040of the original first parity, the fourth row1042of the original first parity, the sixth row1044of the original first parity and the eighth row1046of the original first parity. The encoding module214generates the lost second parity by using the retrieved portions from the content stores and the retrieved portion from the original first parity. Finally, the encoding module214may return the result to be recreated on a new storage disk.

Systems and methods for generating repair-optimal parities for data recovery have been described. In the above description, for purposes of explanation, numerous specific details were set forth. It will be apparent, however, that the disclosed technologies can be practiced without any given subset of these specific details. In other instances, structures and devices are shown in block diagram form. For example, the disclosed technologies are described in some implementations above with reference to user interfaces and particular hardware. Moreover, the technologies disclosed above primarily in the context of on line services; however, the disclosed technologies apply to other data sources and other data types (e.g., collections of other resources for example images, audio, web pages).

Reference in the specification to “one implementation” or “an implementation” means that a particular feature, structure, or characteristic described in connection with the implementation is included in at least one implementation of the disclosed technologies. The appearances of the phrase “in one implementation” in various places in the specification are not necessarily all referring to the same implementation.

Some portions of the detailed descriptions above were presented in terms of processes and symbolic representations of operations on data bits within a computer memory. A process can generally be considered a self-consistent sequence of steps leading to a result. The steps may involve physical manipulations of physical quantities. These quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. These signals may be referred to as being in the form of bits, values, elements, symbols, characters, terms, numbers or the like.

These and similar terms can be associated with the appropriate physical quantities and can be considered labels applied to these quantities. Unless specifically stated otherwise as apparent from the prior discussion, it is appreciated that throughout the description, discussions utilizing terms for example “processing” or “computing” or “calculating” or “determining” or “displaying” or the like, may refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

The disclosed technologies can take the form of an entirely hardware implementation, an entirely software implementation or an implementation containing both hardware and software elements. In some implementations, the technology is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

A computing system or data processing system suitable for storing and/or executing program code will include at least one processor (e.g., a hardware processor) coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution.

Finally, the processes and displays presented herein may not be inherently related to any particular computer or other apparatus. Various general-purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from the description below. In addition, the disclosed technologies were not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the technologies as described herein.

The foregoing description of the implementations of the present techniques and technologies has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the present techniques and technologies to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the present techniques and technologies be limited not by this detailed description. The present techniques and technologies may be implemented in other specific forms without departing from the spirit or essential characteristics thereof. Likewise, the particular naming and division of the modules, routines, features, attributes, methodologies and other aspects are not mandatory or significant, and the mechanisms that implement the present techniques and technologies or its features may have different names, divisions and/or formats. Furthermore, the modules, routines, features, attributes, methodologies and other aspects of the present technology can be implemented as software, hardware, firmware or any combination of the three. Also, wherever a component, an example of which is a module, is implemented as software, the component can be implemented as a standalone program, as part of a larger program, as a plurality of separate programs, as a statically or dynamically linked library, as a kernel loadable module, as a device driver, and/or in every and any other way known now or in the future in computer programming. Additionally, the present techniques and technologies are in no way limited to implementation in any specific programming language, or for any specific operating system or environment. Accordingly, the disclosure of the present techniques and technologies is intended to be illustrative, but not limiting.