Patent Description:
The present description relates to data recovery, and more specifically, to a system, method, and machine-readable storage medium for recovering data in a distributed storage system.

Networks and distributed storage allow data and storage space to be shared between devices located anywhere a connection is available. These implementations may range from a single machine offering a shared drive over a home network to an enterpriseclass cloud storage array with multiple copies of data distributed throughout the world. Larger implementations may incorporate Network Attached Storage (NAS) devices, Storage Area Network (SAN) devices, and other configurations of storage elements and controllers in order to provide data and manage its flow. Improvements in distributed storage have given rise to a cycle where applications demand increasing amounts of data delivered with reduced latency, greater reliability, and greater throughput. Hand-in-hand with this trend, system administrators have taken advantage of falling storage prices to add capacity wherever possible.

One consequence of the abundance of cheap storage is the need to protect and recover increasing amounts of data. Even though storage devices have become more reliable, they are not infallible. At the system level, multiple storage devices may be grouped in a RAID array or other grouping configured to provide redundancy using parity, mirroring, or other techniques. In theory, should a device fail, the storage system can recover lost data from the remaining devices. In practice, the probability of multipledevice failures increases with each storage device added, and any data protection scheme has a limit to how many concurrent failures can be tolerated. As a result, it is still possible for a catastrophic failure to exceed the ability of the RAID array to recover.

Other techniques for data recovery leverage the distributed nature of some storage environments. For example, a storage environment may be arranged as a cluster of discrete systems (e.g., storage nodes) coupled by a network. Copies of data and/or recovery information may be distributed over the storage nodes so that data is not lost should an entire storage node fail. However, when a node fails, the amount of data transferred over the network to rebuild the node may be several times larger than the amount contained in the node. For example, rebuilding a <NUM> TB node may entail transferring <NUM> PB or more between nodes. Even if the rebuild process does not halt all data transactions, the network burden may severely delay those transactions still being processed.

Accordingly, a technique for distributing data and for recovering data in the event of a node failure without rebuilding a node entirely would provide numerous practical and real-world advantages. Thus, while existing techniques for data recovery have been generally adequate, the techniques described herein provide a robust data protection scheme with greater recovery options.

<CIT> (A1) discloses a resilient distributed replicated data storage system. The storage system includes zones that are independent, and autonomous from each other. The zones include nodes that are independent and autonomous. The nodes includes storage devices. When a data item is stored, it is partitioned into a plurality of data objects and a plurality of parity objects are calculated. Reassembly instructions are created for the data item. The data objects, parity objects and reassembly instructions are spread across nodes and zones in the storage system according to a policy for the data item. When a zone is inaccessible, a virtual zone is created and used until the intended zone is available. When a read request is received, the data item is prepared from the lowest latency nodes according to the reassembly instructions, and a virtual zone is accessed in place of a real zone when the real zone is inaccessible.

The present disclosure is best understood from the following detailed description when read with the accompanying figures.

All examples and illustrative references are non-limiting and should not be used to limit the claims to specific implementations and embodiments described herein and their equivalents. For simplicity, reference numbers may be repeated between various examples. This repetition is for clarity only and does not dictate a relationship between the respective embodiments, unless noted otherwise. Finally, in view of this disclosure, particular features described in relation to one aspect or embodiment may be applied to other disclosed aspects or embodiments of the disclosure, even though not specifically shown in the drawings or described in the text.

Various embodiments include systems, methods, and computer programs for recovering data in a distributed storage system. In an embodiment, the distributed storage system divides data objects into groups of data chunks. Each group also contains recovery chunks generated according to an upper-level data protection scheme. The upper-level data protection scheme allows the data to be recreated should some of the chunks be lost. Each chunk (data or recovery) is distributed to a storage node for storing. At the storage node, the chunk is divided into segments and stored according to a lower-level data protection scheme, such as RAID <NUM>, <NUM>, or <NUM>.

If a storage node fails, the node data can be recreated by rebuilding the node, which includes requesting other chunks from other storage nodes in order to recreate each chunk of data stored on the storage node. Recovering all of the data chunks on the storage node in this manner may be referred to as a full rebuild of the node and is significantly taxing on both the node and the network. However, the present technique also provides other recovery options that are less burdensome. For example, if some storage devices of the storage node fail, the storage node may first attempt to recreate data on the failed storage devices using the lower-level data protection scheme. To do so, the storage node may read data from the remaining storage devices on the same node. Because this can be done without accessing the network, the impact on other nodes is minimized.

If the lower-level data protection scheme cannot recover the data alone, which may occur if too many storage devices fail concurrently, the present technique also provides a partial node rebuild option. In one example, the storage node identifies the inaccessible data segments on the failed storage device(s) and the chunks to which they correspond. The storage node requests only the chunks needed to rebuild the inaccessible chunks (not all the chunks stored on the node). From the received chunks, the storage node recreates the inaccessible chunks and from them, recreates the data of the inaccessible segments. This data can be written to a replacement storage device.

In this manner, the present technique provides an improvement to conventional data storage and recovery technique with substantial advantages. For example, far less data may be transferred during a partial node rebuild than during a full node rebuild because the size of the dataset being rebuilt is smaller. In this manner, a partial rebuild greatly reduces the network impact associated with a storage device failure. As another example, because the dataset is smaller, a partial rebuild may reduce the processing burden on the rebuilding node, which may allow the rebuilding node to continue to service transactions using the accessible segments. As yet another example, a partial node rebuild may be completed quicker than a full node rebuild. This reduces the rebuilding window when the storage node is most vulnerable to data loss caused by further device failures. Of course, these advantages are merely exemplary, and no particular advantage is required for any particular embodiment.

<FIG> is a schematic diagram of a computing architecture <NUM> according to aspects of the present disclosure. The computing architecture <NUM> includes one or more host systems <NUM> (hosts), each of which may interface with a distributed storage system <NUM> to store and manipulate data. The distributed storage system <NUM> may use any suitable architecture and protocol. For example, in some embodiments, the distributed storage system <NUM> is a StorageGR D system, an OpenStack Swift system, a Ceph system, or other suitable system. The distributed storage system <NUM> includes one or more storage nodes <NUM> over which the data is distributed. The storage nodes <NUM> are coupled via a back-end network <NUM>, which may include any number of wired and/or wireless networks such as a Local Area Network (LAN), an Ethernet subnet, a PCI or PCIe subnet, a switched PCIe subnet, a Wide Area Network (WAN), a Metropolitan Area Network (MAN), the Internet, or the like. In some embodiments, the storage nodes <NUM> are coupled by a TCP/IP back-end network <NUM>, which is local to a rack or datacenter, although additionally or in the alternative, the network <NUM> may extend between sites in a WAN configuration or be a virtual network extending throughout a cloud. As can be seen, the storage nodes <NUM> may be as physically close or as widely dispersed as the application may warrant. In some examples, the storage nodes <NUM> are housed in the same racks. In other examples, storage nodes <NUM> are located in different facilities at different sites anywhere in the world. The node arrangement may be determined based on cost, fault tolerance, network infrastructure, geography of the hosts, and other considerations. A technique for preserving and restoring the data contained in these storage nodes <NUM>, suitable for use with any of these arrangements, is described with reference to the figures that follow.

In the illustrated embodiment, the computing architecture <NUM> includes a plurality of storage nodes <NUM> in communication with a plurality of hosts <NUM>. It is understood that for clarity and ease of explanation, only limited number of storage nodes <NUM> and hosts <NUM> are illustrated, although the computing architecture <NUM> may include any number of hosts <NUM> in communication with a distributed storage system <NUM> containing any number of storage nodes <NUM>. An exemplary storage system <NUM> receives data transactions (e.g., requests to read and/or write data) from the hosts <NUM> and takes an action such as reading, writing, or otherwise accessing the requested data so that storage devices <NUM> of the storage nodes <NUM> appear to be directly connected (local) to the hosts <NUM>. This allows an application running on a host <NUM> to issue transactions directed to the data of the distributed storage system <NUM> and thereby access this data as easily as it can access data on storage devices local to the host <NUM>. In that regard, the storage devices <NUM> of the distributed storage system <NUM> and the hosts <NUM> may include hard disk drives (HDDs), solid state drives (SSDs), storage class memory (SCM), RAM drives, optical drives, and/or any other suitable volatile or non-volatile data storage medium.

With respect to the storage nodes <NUM>, an exemplary storage node <NUM> contains any number of storage devices <NUM> in communication with one or more storage controllers <NUM>. The storage controllers <NUM> exercise low-level control over the storage devices <NUM> in order to execute (perform) data transactions on behalf of the hosts <NUM>, and in so doing, may group the storage devices for speed and/or redundancy using a protocol such as RAID (Redundant Array of Independent/Inexpensive Disks). The grouping protocol may also provide virtualization of the grouped storage devices <NUM>. At a high level, virtualization includes mapping physical addresses of the storage devices into a virtual address space and presenting the virtual address space to the hosts <NUM>, other storage nodes <NUM>, and other requestors. In this way, the storage node <NUM> represents the group of devices as a single device, often referred to as a volume. Thus, a requestor can access data within a volume without concern for how it is distributed among the underlying storage devices <NUM>.

In addition to storage nodes, the distributed storage system <NUM> may include ancillary systems or devices (e.g., load balancers <NUM>). For example, in some embodiments, a host <NUM> may initiate a data transaction by providing the transaction to a load balancer <NUM>. The load balancer <NUM> selects one or more storage nodes <NUM> to service the transaction. When more than one alternative is possible, the load balancer <NUM> may select a particular storage node <NUM> based on any suitable criteria including storage node load, storage node capacity, storage node health, network quality of service factors, and/or other suitable criteria. Upon selecting the storage node(s) <NUM> to service the transaction, the load balancer <NUM> may respond to the host <NUM> with a list of the storage nodes <NUM> or may forward the data transaction to the storage nodes <NUM>. Additionally or in the alternative, a host <NUM> may initiate a data transaction by contacting one or more of the storage nodes <NUM> directly rather than contacting the load balancer <NUM>.

Turning now to the hosts <NUM>, a host <NUM> includes any computing resource that is operable to exchange data with the distributed storage system <NUM> by providing (initiating) data transactions to the distributed storage system <NUM>. In an embodiment, a host <NUM> includes a host bus adapter (HBA) <NUM> in communication with the distributed storage system <NUM>. The HBA <NUM> provides an interface for communicating, and in that regard, may conform to any suitable hardware and/or software protocol. In various embodiments, the HBAs <NUM> include Serial Attached SCSI (SAS), iSCSI, InfiniBand, Fibre Channel, and/or Fibre Channel over Ethernet (FCoE) bus adapters. Other suitable protocols include SATA, eSATA, PATA, USB, and FireWire. In many embodiments, the host HBAs <NUM> are coupled to the distributed storage system <NUM> via a front-end network <NUM>, which may include any number of wired and/or wireless networks such as a LAN, an Ethernet subnet, a PCI or PCIe subnet, a switched PCIe subnet, a WAN, a MAN, the Internet, or the like. To interact with (e.g., read, write, modify, etc.) remote data, the HBA <NUM> of a host <NUM> sends one or more data transactions to the load balancer <NUM> or to a storage node <NUM> directly via the front-end network <NUM>. Data transactions may contain fields that encode a command, data (i.e., information read or written by an application), metadata (i.e., information used by a storage system to store, retrieve, or otherwise manipulate the data such as a physical address, a logical address, a current location, data attributes, etc.), and/or any other relevant information.

While the load balancers <NUM>, storage nodes <NUM>, and the hosts <NUM> are referred to as singular entities, a storage node <NUM> or host <NUM> may include any number of computing devices and may range from a single computing system to a system cluster of any size. Accordingly, each load balancer <NUM>, storage node <NUM>, and host <NUM> includes at least one computing system, which in turn includes a processor such as a microcontroller or a central processing unit (CPU) operable to perform various computing instructions. The computing system may also include a memory device such as random access memory (RAM); a non-transitory computer-readable storage medium such as a magnetic hard disk drive (HDD), a solid-state drive (SSD), or an optical memory (e.g., CD-ROM, DVD, BD); a video controller such as a graphics processing unit (GPU); a communication interface such as an Ethernet interface, a Wi-Fi (IEEE <NUM> or other suitable standard) interface, or any other suitable wired or wireless communication interface; and/or a user I/O interface coupled to one or more user I/O devices such as a keyboard, mouse, pointing device, or touchscreen.

As described above, the storage system <NUM> may distribute the hosts' data across the storage nodes <NUM> for performance reasons as well as redundancy. Such distribution of data is described with further reference to <FIG> is a schematic diagram of a portion of the computing architecture <NUM> showing data distribution according to aspects of the present disclosure. The computing architecture <NUM> includes a distributed storage system <NUM> having a plurality of storage nodes <NUM>, each substantially similar to those of <FIG>.

In some of the examples of <FIG>, the distributed storage system <NUM> is an object-based data system. In brief, object-based data systems provide a level of abstraction that allows data of any arbitrary size to be specified by an object identifier. In contrast, block-level data transactions refer to data using an address that corresponds to a sector of a storage device and may include a physical address (i.e., an address that directly map to a storage device) and/or a logical address (i.e., an address that is translated into a physical address of a storage device). Exemplary block-level protocols include iSCSI, Fibre Channel, and Fibre Channel over Ethernet (FCoE). As an alternative to block-level protocols, file-level protocols specify data locations by a file name. A file name is an identifier within a file system that can be used to uniquely identify corresponding memory addresses. File-level protocols rely on a computing system to translate the file name into respective storage device addresses. Exemplary file-level protocols include CIFS/SMB, SAMBA, and NFS. Object-level protocols are similar to file-level protocols in that data is specified via an object identifier that is eventually translated by a computing system into a storage device address. However, objects are more flexible groupings of data and may specify a cluster of data within a file or spread across multiple files. Object-level protocols include CDMI, HTTP, SWIFT, and S3. Referring to <FIG>, one of the many data objects <NUM> of the distributed storage system is illustrated, although it is understood that data object <NUM> represents any arbitrary unit of data regardless of whether it is organized as an object, a file, or a set of blocks.

The distributed storage system <NUM> utilizes an upper-level data protection scheme to protect against failure of a storage node <NUM> and a lower-level data protection scheme to protect against failure of a storage device <NUM>. For example, to implement an upper-level data protection scheme, the storage controllers <NUM> of storage nodes <NUM> may coordinate to divide the data object <NUM> into groups of chunks such that the data object <NUM> can be reconstructed if some of the chunks are lost. In the illustrated embodiment, each group includes one or more data chunks <NUM> (which contain data and/or metadata) and one or more recovery chunks <NUM> (which contain recovery information such as parity information). In an example, the storage controllers <NUM> implement an erasure coding technique, such as a Reed-Solomon erasure code or Tornado erasure code, to generate the recovery chunks <NUM> for each group, although other suitable techniques may be used. Many such techniques are characterized by the number of data chunks <NUM> and recovery chunks <NUM> in each group. For example, a computing architecture <NUM> utilizing a <NUM>+<NUM> Reed Solomon erasure coding system creates six data chunks <NUM> and three recovery chunks <NUM> per group. In this example, the data of the data chunks <NUM> can be recreated from any six chunks (data chunks <NUM> and/or recovery chunks <NUM>), provided none of the chunks are duplicates.

The chunks are then distributed among the storage nodes <NUM>. Dividing the data chunks <NUM> and the recovery chunks <NUM> among the storage nodes <NUM> provides redundancy in the event of a storage node <NUM> failure. This distribution may also improve transaction response time because the chunks can be retrieved in parallel. In some embodiments, the storage nodes <NUM> are configured as peers so that any storage node <NUM> may divide a data object into groups of chunks, distribute the chunks, retrieve chunks, and/or reassemble the chunks into the data object. To aid in this, a storage controller <NUM> of each storage node <NUM> may maintain a distribution index for tracking the storage location of chunks throughout the distributed storage system <NUM>. An example of a distribution index is described with reference to <FIG>.

<FIG> is a memory diagram of a data distribution index <NUM> according to aspects of the present disclosure. The data distribution index <NUM> includes a set of entries identifying data objects, their corresponding groups of chunks, and locations at which the chunks are stored. The entries may be maintained in any suitable representation including a linked list, a tree, a table such as a hash table, an associative array, a state table, a flat file, a relational database, and/or other memory structure. For example, the data distribution index <NUM> may be a distributed database such as an Apache Cassandra or other NoSQL database (e.g., MongoDB, RIAK, Redis, etc.) or an SQL database such as a MySQL database.

In the illustrated embodiment, an object entry <NUM> of the data distribution index <NUM> records a data object identifier and has a plurality of other entries associated with it (e.g., entries <NUM>, <NUM>, and <NUM>). A group entry <NUM> records a group identifier of a group of chunks that is part of the data object. A chunk entry <NUM> records a chunk identifier of a chunk within one such group. The chunk entry <NUM> also records a storage node identifier for a storage node upon which the chunk is stored. Multiple such entries may be maintained if mirrored copies of the chunk are stored at more than one storage node. A chunk entry <NUM> may also record a location at which the chunk is stored on the storage node. The entry may reference a logical address (e.g., LBA, LUN ID, etc.), a physical address, a file name, an object name, or any other mechanism for specifying the storage location.

In some embodiments, each node <NUM> only records storage locations (e.g., address, file name, or object name) for its own chunks. For other chunks, the storage node <NUM> records which other node is storing the chunk without necessarily tracking where it is stored on the node. For example, in some embodiments, the data distribution index <NUM> may contain a second type of chunk entry <NUM> that records a chunk identifier and a node identifier for the node <NUM> upon which the chunk is stored but does not necessarily record where the chunk is stored in the node <NUM>. In addition to reducing the size of the data distribution index <NUM>, this may reduce the number of updates to the data distribution index <NUM> as chunks are moved within other nodes. In such embodiments, any storage node <NUM> can still request a chunk from any other node using the chunk identifier. To further streamline the data distribution index <NUM>, in some embodiments, each node <NUM> only maintains entries for chunks stored on the node. Thus, the second type of chunk entry <NUM> may be omitted completely. In such embodiments, any storage node <NUM> can obtain chunks by providing the group identifier to each of the other storage nodes <NUM>, which each respond with a list of chunks matching the group identifier stored on the respective storage node <NUM>. Of course, data distribution index <NUM> is merely one example of a technique for tracking the distribution of data across the distributed storage system <NUM>. Other tracking mechanisms are both contemplated and provided for.

Referring back to <FIG>, for further protection, the storage controllers <NUM> of each storage node <NUM> implement a lower-level data protection scheme. For example, in some embodiments, a storage controller <NUM> implements protection and virtualization using RAID <NUM> (mirroring), RAID <NUM> (striping with parity), or RAID <NUM> (striping with double parity). Some examples utilize an <NUM>+<NUM> RAID <NUM> parity scheme where data is arranged in a stripe <NUM> containing eight data segments <NUM> and two recovery segments <NUM> (sometimes identified as p and q). In the illustrated embodiment, each segment (data or recovery) is stored on a different storage device <NUM>, of which a subset is shown.

Should a single storage device <NUM> fail, the associated storage node <NUM> attempts to recreate the data contained on the failed storage device <NUM> using the lower- level protection scheme. For stripes <NUM> in which the failed storage device <NUM> contained data segments <NUM>, the storage controller <NUM> may recover the data or metadata from the remaining data segments <NUM> and recovery segments <NUM> on the other storage devices <NUM>. For stripes <NUM> in which the failed storage device <NUM> contained recovery segments <NUM>, the storage controller <NUM> may regenerate the recovery data from the data segments <NUM> on the other storage devices <NUM>. The recovered segments may then be saved to a replacement storage device <NUM>. In some embodiments, the storage node <NUM> may continue to service transactions without any noticeable impairment during the recovery process; however, it is also common for data recovery to affect storage node <NUM> performance. For example, during recovery, the storage node <NUM> may stop performing other transactions or may continue to handle transactions directed to intact portions of the address space albeit with reduced performance.

Despite these safeguards, it is possible for more storage devices <NUM> to fail than the lower-level data protection scheme can recover. For example, a RAID <NUM> array can recover data when two storage devices <NUM> fail, but cannot recover from three failing storage devices <NUM> in the same RAID group. For a <NUM>-drive storage node <NUM> utilizing RAID <NUM> groups, three failing devices <NUM> represents only <NUM>% of the total storage capacity. However, this loss may be enough to render the group unusable.

If the storage node <NUM> cannot recover the data using the lower-level protection scheme, the upper-level protection scheme is utilized to reconstruct the data on the failed devices <NUM>. In the case of a full node rebuild, for each chunk stored on the failed storage node <NUM>, enough data chunks <NUM> and/or recovery chunks <NUM> are retrieved from the other storage nodes <NUM> to reconstruct the missing chunk. It should be noted that the amount of data retrieved may be many times larger than the amount of data being recovered. For example, a computing architecture <NUM> utilizing a <NUM>+<NUM> Reed Solomon erasure coding system utilizes six chunks (any combination of data chunks <NUM> and/or recovery chunks <NUM>) to recover up to three remaining chunks. Therefore, recovery may entail transferring six chunks for every one recovered. In order to perform a full node rebuild of a <NUM> TB storage node <NUM>, the distributed storage system may transfer <NUM> PB of data over the back-end network <NUM>. Therefore, a technique for recovering data using less than a full node rebuild is beneficial for both the storage nodes <NUM> and the back-end network <NUM>.

A system and technique for recovering data that utilizes a partial node rebuild, where appropriate, to reduce burden on the distributed storage system <NUM> is described with reference to <FIG>. <FIG> is a flow diagram of a method <NUM> of recovering data according to aspects of the present disclosure. It is understood that additional steps can be provided before, during, and after the steps of method <NUM>, and that some of the steps described can be replaced or eliminated for other embodiments of the method. <FIG> and <FIG> are system diagrams of a computing architecture <NUM> performing the method <NUM> of recovering data according to aspects of the present disclosure.

The computing environment <NUM> is substantially similar to the computing architecture <NUM> above and include a distributed storage system <NUM> and one or more storage nodes <NUM> each substantially similar to those described with reference to <FIG>. In that regard, the distributed storage system <NUM> may distribute data among the storage nodes <NUM> according to an upper-level data protection scheme. In turn, each of the storage nodes <NUM> may distribute its portion of the data across a plurality of storage devices <NUM> arranged and configured according to a lower-level data protection scheme. For example, the storage nodes <NUM> may distribute data across the storage devices <NUM> according to RAID <NUM>, RAID <NUM>, RAID <NUM>, or other suitable protocol.

Referring to block <NUM> of <FIG> and to <FIG>, a storage controller <NUM> of a storage node <NUM> determines that one or more storage devices <NUM> of the storage node <NUM> have failed. Referring to block <NUM> of <FIG>, the storage controller <NUM> identifies data that cannot be read from the failed storage devices <NUM> by segment (e.g., data segments <NUM> or recovery segments <NUM>) and identifies the stripes <NUM> to which the inaccessible segments correspond. Because a storage device <NUM> may have some bad sectors and some accessible sectors, in some examples, this includes identifying a subset of data or metadata on the failed storage device(s) <NUM> that cannot be read from the failed storage device(s) themselves. In such examples, accessible data and metadata may be copied directly to a replacement storage device <NUM> while inaccessible data and metadata may be recovered. The lower-level data protection scheme is used to verify any accessible data on a failed storage device <NUM> prior to or during the copying process. For example, parity information may be used to verify that the accessible data satisfies the parity relationship.

Referring to block <NUM> of <FIG>, the storage controller <NUM> determines whether the inaccessible segments stored on the failed storage device(s) <NUM> can be recovered using the lower-level data protection scheme. If so, referring to block <NUM> of <FIG>, the storage controller <NUM> recovers each inaccessible segment by reading the remaining segments (data segments <NUM> and/or recovery segments <NUM>) of the corresponding stripe <NUM> from the remaining storage devices <NUM>. This allows the storage controller to recreate the segments of the failed storage device(s) <NUM> by using a recovery algorithm of the lower-level protection scheme. In a RAID <NUM> or <NUM> example, inaccessible data segments <NUM> may be recovered by reading the remaining data segments <NUM>, reading the parity information in the recovery segments <NUM>, and solving for the missing data segment values using the parity equation(s). Similarly, inaccessible recovery segments <NUM> may be recovered by reading the data segments <NUM> and generating the parity information of the recovery segments <NUM> using the parity equation(s). Of course, other lower-level protections schemes may have other recovery algorithms. The storage controller <NUM> may then store the recreated segments to one or more replacement storage devices <NUM>.

If the storage controller <NUM> determines that the segments stored on the failed storage device(s) <NUM> cannot be recovered using the lower-level data protection scheme, the storage controller reconstructs the data segments <NUM> using the upper-level data protection scheme and recalculates the recovery segments <NUM> using the lower-level data protection scheme as described in blocks <NUM>-<NUM>. This may occur, for example, when more storage devices <NUM> have failed than the lower-level data protection scheme can tolerate. In block <NUM>, the storage controller <NUM> identifies one or more chunks of data (eg-, data chunks <NUM> and/or recovery chunks <NUM>) associated with the inaccessible data segments <NUM> of the failed storage device(s) <NUM>. This may be done using a data distribution index <NUM> such as the one described in the context of <FIG>. In an example, the storage controller <NUM> queries the chunk entries <NUM> of the data distribution index <NUM> to identify chunks stored on the stripes <NUM> with inaccessible data segments <NUM>.

Referring to block <NUM> of <FIG> and to <FIG>, for each inaccessible data segment <NUM> stored on the failed storage devices <NUM>, the storage controller <NUM>, having identified the chunk to which it corresponds, requests and retrieves the other chunks in the group from the other storage nodes <NUM>. This may include examining the group entries <NUM> and chunk entries <NUM> of the of the data distribution index <NUM> to identify a group and requesting the chunks of the group from the other storage nodes <NUM> using a chunk identifier and/or a group identifier. In some examples, the storage controller <NUM> retrieves only a subset of the chunks in the group. The subset may contain enough data chunks <NUM> and recovery chunks <NUM> to recover the inaccessible chunk. In the <NUM>+<NUM> Reed Solomon erasure coding example described above, the storage controller <NUM> selects any six of the chunks in the group because the upper-level data protection scheme can reconstruct the inaccessible chunk from any combination of six or more chunks. The storage controller <NUM> may select the subset based on any suitable criteria including storage node load, storage node capacity, storage node health, network quality of service factors, and/or other suitable criteria. Furthermore, in some embodiments, the storage controller retrieves a subset with more than the minimum number of chunks. The additional chunks can be used to verify the recovered chunk. While this approach may be undesirable during a full node rebuild because of the amount of data transferred, because the partial node rebuild reconstructs a smaller data set, the impact is not nearly as severe.

Referring to block <NUM> of <FIG> and to <FIG>, the storage controller <NUM> recovers the chunk <NUM> corresponding to the inaccessible data segment <NUM> using a recovery algorithm of the upper-level data protection scheme. Referring to block <NUM> of <FIG>, the inaccessible data segment <NUM> is recreated from the recovered chunk by merely dividing the recovered chunk into segments and determining which segment corresponds to the inaccessible data segment <NUM>. The corresponding data segment may then be stored to the replacement storage device <NUM>. In some embodiments, the storage controller <NUM> determines the location (e.g., LBA, LUN, etc.) at which the inaccessible data segment <NUM> was located and stores the recovered data segment <NUM> to the exact same location on the replacement storage device <NUM>.

It is noted that the chunks and stripes <NUM> may have any suitable size relationship. In that regard, a single chunk may span multiple stripes <NUM>, and a stripe <NUM> may contain data from more than one chunk. It can be seen that where a single chunk spans multiple stripes <NUM>, inaccessible segments from all of the stripes <NUM> can be recreated from a single recovered chunk. Likewise, where a stripe contains data from more than one chunk, the method <NUM> does not require all the chunks in the stripe to be recovered. This may reduce the number of chunks that are requested from the other storage nodes <NUM>.

Referring to block <NUM>, for each inaccessible recovery segment <NUM> stored on the failed storage devices <NUM>, the storage controller <NUM> may first recover all inaccessible data segments <NUM> in the stripe <NUM> (if any). The storage controller may then use the data segments <NUM> in the stripe to recalculate the recovery data of the inaccessible recovery segment <NUM>. The recovery data is then stored to the replacement storage device <NUM>.

By recovering only the data chunks associated with inaccessible data segments <NUM>, the storage controller may perform a partial rebuild of the storage node <NUM>. It can be seen that this provides a substantial improvement to conventional data recovery techniques with several possible advantages. First, far less data may be transferred during a partial node rebuild than during a full node rebuild because the size of the dataset being rebuilt is smaller. Depending on the upper-level protection scheme, rebuilding each chunk may require transferring many six, eight, ten chunks or more. Accordingly, rebuilding a 200TB dataset completely could entail retrieving <NUM>. 2PB of data over the back-end network. In this manner, a partial rebuild greatly reduces the network impact associated with a storage device failure. In an example, a storage node rebuilding only <NUM>% of its total chunks would request only <NUM>% as much data. Second, because the dataset is smaller, a partial rebuild may reduce the processing burden on the rebuilding node, which may allow the rebuilding node to continue to service transactions. Third, a partial node rebuild may be completed quicker than a full node rebuild. This reduces the rebuilding window when the storage node is most vulnerable to data loss caused by further device failures. Of course, these advantages are merely exemplary, and no particular advantage is required for any particular embodiment.

The present embodiments can take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment containing both hardware and software elements. Accordingly, it is understood that any operation of the computing systems of computing architecture <NUM> or computing architecture <NUM> may be implemented by the respective computing system using corresponding instructions stored on or in a non-transitory computer readable medium accessible by the processing system. For the purposes of this description, a tangible computer-usable or computer-readable medium can be any apparatus that can store the program for use by or in connection with the instruction execution system, apparatus, or device. The medium may include non-volatile memory including magnetic storage, solid-state storage, optical storage, cache memory, and Random Access Memory (RAM).

Thus, the present disclosure provides a system, method, and machine-readable storage medium for recovering data in a distributed storage system. The method includes identifying a failing storage device from a plurality of storage devices of a first storage node, the failing storage device having an inaccessible data segment stored thereupon. It is determined whether the inaccessible data segment can be recovered using a first data protection scheme utilizing data stored on the first storage node. When it is determined that the inaccessible data segment cannot be recovered using the first data protection scheme, a first chunk of data associated with the inaccessible data segment is identified and a group associated with the first chunk of data is identified. A second chunk of data associated with the group is selectively retrieved from a second storage node such that data associated with an accessible data segment of the first storage node is not retrieved. The inaccessible data segment is recovered by recovering the first chunk of data using a second data protection scheme and the second chunk of data. In some such embodiments, the method further includes determining a logical block address of the inaccessible data segment and storing the recovered inaccessible data segment on a replacement storage device at a location corresponding to the logical block address. In some such embodiments, the first storage node has an inaccessible protection segment, and the method further includes recovering the inaccessible protection segment using the first data protection scheme and the recovered inaccessible data segment.

The non-transitory machine-readable medium has instructions for performing the method of data recovery, including machine executable code, which when executed by at least one machine, causes the machine to: identify a first data segment of a storage device of a storage node that cannot be accessed, wherein the storage node comprises a plurality of storage devices; identify a second data segment of the storage node that can be accessed; determine that a number of failed storage devices exceeds a maximum supported by a first data protection scheme; identify a first set of data structures distributed across at least one storage node from which the first data segment can be recovered using a second data protection scheme; selectively retrieve the first set of data structures from the at least one storage node without a second set of data structures from which the second data segment can be recovered using the second data protection scheme;
and recover the first data segment using the first set of data structures. In some such embodiments, the first data protection scheme is a RAID data protection scheme and the second data protection scheme is one of a Reed-Solomon erasure code protection scheme or a Tornado erasure code protection scheme.

The computing device includes a memory containing a machine-readable medium comprising machine executable code having stored thereon instructions for performing a method of data recovery and a processor coupled to the memory. The processor is configured to execute the machine executable code to: identify a failing storage device from a plurality of storage devices of a first storage node and an inaccessible data segment stored thereupon; determine that the inaccessible data segment cannot be recovered using a data recovery technique; identify a first group of data stored upon a plurality of storage nodes associated with the inaccessible data segment; selectively retrieve the first group of data from the plurality of storage nodes, wherein selectively retrieving does not retrieve a second group of data associated with an accessible data segment; and recreate the inaccessible data segment using the first group of data segments. In some such embodiments, the data recovery technique comprises a RAID data recovery technique includes one of a RAID <NUM>, RAID <NUM>, or RAID <NUM> data recovery technique.

Claim 1:
A method comprising:
identifying a failing storage device (<NUM>) from a plurality of storage devices of a first storage node (<NUM>), the failing storage device having an inaccessible data segment (<NUM>) stored thereupon;
determining that the inaccessible data segment cannot be recovered using a first data protection scheme utilizing data stored on the first storage node;
based on determining that the inaccessible data segment cannot be recovered using the first data protection scheme, identifying a first chunk of data (<NUM>) associated with the inaccessible data segment and identifying a group associated with the first chunk of data;
selectively retrieving a second chunk of data (<NUM>) from a second storage node (<NUM>), wherein the second chunk of data is associated with the group, and wherein the selectively retrieving the second chunk of data does not retrieve data associated with an accessible data segment of the first storage node; and
recovering the inaccessible data segment by recovering the first chunk of data using a second data protection scheme and the second chunk of data.