Patent Description:
This disclosure relates generally to data management, and, more particularly, to methods and apparatus to assign indices and relocate object fragments in distributed storage systems.

In recent years, object-based storage, or distributed storage systems, have been implemented as alternates to file hierarchy or data block storage. Such distributed storage systems often provide redundancy and application specific policies. In some instances, Erasure Coding, or Error correction coding, is used in connection with object-based storage to break objects into fragments and distribute the fragments according to other storage policies.

<CIT> discloses a RAID storage system distributed over storage nodes. A data object is erasure encoded and broken into fragments. The fragments are stored in the distributed storage nodes of the RAID storage system. The data object comprises an inventory index to indicate a storage location where the data object is to be stored.

Distributed storage systems are implemented to distribute data (e.g., in the form of objects) and/or distribute the processing of data across any number of computing devices that may or may not be located in the same physical location (e.g., dispersed over a network of connected computers, such as, for example, the Internet). In some examples, distributed storage systems cluster multiple computing devices as storage devices or storage nodes.

In some examples, a cluster is a set of connected computing devices (e.g., nodes) that work together such that they are viewed as a single system. In some such examples, each computing device, or storage node, is used as a server. In some examples, a storage node is a physical machine having local storage (e.g., hard-disk drives, solid-state drives, etc.). In some examples, a storage node is a virtual machine with access to one or more storage drives. In some examples, the storage nodes are physically clustered in a single location. In some examples, the storage nodes are spread out across a network (e.g., the Internet) and digitally clustered (e.g., different servers from different locations are digitally designated as a single cluster). In some examples, the cluster of storage nodes is part of an Internet of Things network. In some examples, the nodes that make up the cluster are in communication with an object manager (e.g., a proxy server). Often, objects are distributed by the object manager to a plurality of storage nodes in one or more clusters.

Distributed storage systems attempt to provide (<NUM>) consistency, (<NUM>) availability, and (<NUM>) partition tolerance based on the structure of the distributed storage system.

As used herein, consistency is defined to be a property in which a requested object will be the same across numerous sources (e.g., object <NUM> stored in a first location should match object <NUM> stored in a second location). In some examples, consistency takes priority over partition tolerance and/or availability by design. These distributed storage systems are often called strongly consistent systems. In strongly consistent systems, an object is not acknowledged as complete (e.g., is not available) until it is consistent in all locations. In some examples, partition tolerance and/or availability take priority over consistency by design. Such example distributed storage systems are often called "eventually consistent" systems. In eventually consistent examples, locations (e.g., nodes) communicate to ensure each location has consistent information (e.g., during initial storage, upgrades, downgrades, etc.).

As used herein, availability is defined to be a property in which the stored object will be accessible even if consistency cannot be achieved. As used herein, partition tolerance is defined to be a property in which the system will continue to operate despite arbitrary partitioning due to network failures (e.g., system will work if communication between nodes is severed).

Availability and partition tolerance are provided through a combination of durability policies, structure design, and services that perform one or more tasks, such as, for example, balancing data across a cluster (e.g., redistributing data proportionate to capacity of storage devices within the cluster). For example, if there are <NUM> objects stored across <NUM> nodes (e.g., one node has two objects) and an <NUM>th node is added to the cluster, the <NUM> objects may be redistributed such that there is a single object in each node. Thus, if a node that originally stored two objects (e.g., but only stores one after redistribution) fails, only a single object is unavailable instead of two objects.

In some examples, the durability of data is important in view of the consistency, availability, and partition tolerance properties. As used herein, durability is defined to be a property in which an object will continue to exist once the object has been committed to the distributed storage system. Thus, any tasks performed to achieve, maintain, and/or overlook consistency, availability, and/or partition tolerance should not cause an object to become lost, corrupted, or otherwise non-existent.

In some examples, to avoid any object becoming unrecoverable/unavailable (e.g., increasing data durability and/or availability), the object manager encodes objects with error correction coding, or Erasure coding, to break the objects into one or more fragments that the object manager stores across various storage nodes. By encoding objects with error correction coding, the object manager can reconstruct objects when one or more fragments (e.g., bits, bytes, etc.) of the object are lost, corrupted, or otherwise incorrect during error correction decoding. For example, error correction coding determines p parity fragments based on an object having m data fragments using one or more error correction equations (e.g., Reed-Solomon coding). In such examples, the object manager creates a code word of m + p fragments. In other words, the example object manager encodes an object with error correction coding to form a code word. As used herein, a code word is defined to be the combination of the original data fragments of an object and parity fragments determined from the original data fragments based on the error correction code used to encode the object.

In some examples, encoding an object with error correction coding by calculating p parity fragments from m data fragments allows the object manager to correct up to p errors (e.g., incorrect data, data degradation, missing data, etc.) during decoding. In some examples, as long as any m fragments (e.g., data and/or parity) from a code word are available, the original code word can be reconstructed and the object encoded with error correction coding can be recovered. For example, a common Reed Solomon coding technique can correct up to <NUM> errors for a code word having <NUM> data fragments and <NUM> parity fragments (e.g., having a length of <NUM> fragments). The number of errors correctable by error correction coding differs amongst various error correction coding techniques. In some examples, any number of error correction coding techniques with varying numbers of parity fragments to correct various numbers of errors can be used without departing from the scope of the present disclosure.

An object may have errors for numerous reasons. For example, an object may be subject to noise, data corruption, hardware failures, execution of an incorrect instructions, etc. Error correction coding provides a capability to recover an object by creating data fragments and parities.

However, distributed storage systems may change topology due to failures (e.g., a server and/or network outage) and/or administrative reconfigurations (e.g., the addition or removal of servers), potentially relocating the fragments (and parity) created by error correction coding. Thus, object fragments and parities are also susceptible to becoming lost (e.g., as are objects themselves when error correction coding is not applied) due to a server or network outage, topology changes, or reconfigurations, in addition to being susceptible to errors from noise, data corruption, hardware failures, execution of an incorrect instruction, etc. If more than p fragments are erred or are lost, then the object cannot be recovered, even with error correction coding.

The aforementioned structures of a distributed storage system create difficulty in the tracking of where objects and/or fragments thereof are located in the distributed storage system. It is often difficult to track which storage nodes store which fragments after system failures, storage node handoffs, and/or topology reconfigurations.

<FIG> is a block diagram illustrating an example distributed storage system <NUM> including an example object manager <NUM> to store fragments of objects therein. In the illustrated example of <FIG>, the example distributed storage system <NUM> includes a first topology having the example object manager <NUM> communicatively connected to example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, and example storage node <NUM><NUM>.

The example object manager <NUM> is responsible for managing the example distributed storage system <NUM>. For example, the example object manager <NUM> receives requests from applications for the storage and/or retrieval of objects from the example distributed storage system <NUM>. The example object manager <NUM> identifies the locations where objects are to be stored and/or where objects are currently stored. The example object manager <NUM> routes the requests from the applications according to such locations (e.g., nodes).

As described above, an object may be fragmented based on one or more error correction codes. In such examples, the object manager <NUM> encodes objects based on an error correction code to create fragments of the object. Similarly, the example object manager <NUM> decodes retrieved fragments to recreate the objects. The example object manager <NUM> accesses an example error correction coding library, for example, to implement different error correction codes when requested by an application.

For example, an object may be defined as O. In such examples, the object O, may be encoded with error correction coding and broken into eight fragments, six corresponding to data fragments A, B, C, D, E, F, (e.g., extracted from O) and two corresponding to parity fragments Y, Z (e.g., calculated from A, B, C, D, E, F). Thus, an example code word based on the example object O may be A, B, C, D, E, F, Y, Z where the last two parity fragments Y, Z are calculated from the data fragments A, B, C, D, E, F. Of course, different error correction codes may produce different numbers of parity fragments and/or parity fragments with differing values.

As disclosed herein, objects and fragments thereof may be any size (e.g., bit-sized, byte-sized, megabyte-sized, etc.). Thus, in some examples, an object may be <NUM> megabytes and the fragments A, B, C, D, E, F, Y, Z may be <NUM> megabytes each (e.g., totaling an <NUM> megabyte code word). In some examples, an object may be <NUM> bits and the fragments A, B, C, D, E, F, Y, Z may be <NUM> bit each (e.g., totaling an <NUM> bit or <NUM> byte code word). Of course, objects and fragments thereof may have differing sizes (e.g., a first fragment is <NUM> megabytes while a second fragment is <NUM> megabytes).

In some examples, the object manager <NUM> distributes fragments of objects to the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> for storage thereof. In the illustrated example, the object manager <NUM> stores the fragments of the object in the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> in sequential order. In other words, the example object manager <NUM> stores a first fragment in the storage node <NUM> (e.g., storage node <NUM>), a second fragment in the storage node <NUM> (e.g., storage node <NUM>), etc..

For example, for the example code word A, B, C, D, E, F, Y, Z, the object manager <NUM> stores the first fragment "A" in the storage node <NUM>, the object manager <NUM> stores the second fragment "B" in the storage node <NUM>, the object manager <NUM> stores the third fragment "C" in the storage node <NUM>, the object manager <NUM> stores the fourth fragment "D" in the storage node <NUM>, the object manager <NUM> stores the fifth fragment "E" in the storage node <NUM>, the object manager <NUM> stores the sixth fragment "F" in the storage node <NUM>, the object manager <NUM> stores the seventh fragment "Y" in the storage node <NUM>, and the object manager <NUM> stores the eighth fragment "Z" in the storage node <NUM>.

In some examples, the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> contain only the fragments of the code word (e.g., object and parity fragments). Alternatively, the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> may be separated into buckets, bins, or other storage containers, such that each storage node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> contains different types and sizes of data along with the fragments of the code word (e.g., multiple fragments from different code words, multiple fragments from the same code word, other objects, etc.).

In some examples, the object manager <NUM> retrieves the fragments of code word from the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> in response to a request from an application. The example object manager <NUM> sends requests to the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> for the respective fragments of the code word stored therein. The example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> send the respective fragments of the code word to the example object manager <NUM> for compilation of the same.

In some examples, the example object manager <NUM> compiles the fragments of the code word based on the order of the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. In other words, the example object manager <NUM> requests a first fragment (e.g., the first fragment "A") from a first storage node <NUM> (e.g., storage node <NUM>), a second fragment (e.g., the second fragment "B" ) from a second storage node <NUM> (e.g., storage node <NUM>), etc. In some examples, the object manager <NUM> concatenates, or otherwise arranges, the fragments accordingly to achieve the proper order. In some examples, the object manager <NUM> decodes the fragments of the code word independent of the order in which the fragments are stored. The error correction code used to encode the object may determine whether the order of the fragments is required.

For example, the example object manager <NUM> compiles the example code word A, B, C, D, E, F, Y, Z, from the fragments stored within the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. The example object manager <NUM> then recovers the object O by removing the previously calculated parity fragments X, Y from the data fragments A, B, C, D, E, F. As disclosed herein, the number of fragments (e.g., data and/or parity) required to recover object O varies based on various error correction schemes, and not all fragments (data or parity) are required to recover the object O.

However, distributed storage systems frequently add nodes to clusters, remove nodes from clusters, and balance data across a cluster (e.g., redistribute data proportionate to capacity of storage devices within the cluster) to provide increased data availability, especially in response to a network outage, server failure, etc. In some examples, rearranging the locations of the fragments makes it difficult to locate where a fragment is located.

In the examples where p or less fragments are missing, corrupted, in a different node, or otherwise unavailable, the example object manager <NUM> can recreate the example code word based on the error correction coding (e.g., correction for up to t errors in a code word). In some examples, if more thanp fragments are missing and/or the order of the available fragments change due to the example distributed storage system redistributing data, then the example object manager <NUM> will fail to reproduce the example code word and the example distributed storage system <NUM> fails to recover the object associated with that code word. For example, in some error correction schemes, even if all the example fragments A, B, C, D, E, F, Y, Z, are available, but they are rearranged such that more than p fragments are not where they were originally (e.g., F, E, D, C, B, A, Y, Z), the error correction coding may fail to recreate the code word A, B, C, D, E, F, Y, Z.

<FIG> illustrate a block diagram of the example distributed storage system <NUM> undergoing a topology change. In the illustrated example of <FIG>, the example distributed storage system <NUM> includes a second topology having the example object manager <NUM> communicatively connected to example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, and example storage node <NUM><NUM>. In the illustrated example of <FIG>, storage node <NUM><NUM> has gone offline due to an outage of some kind (e.g., network outage, server failure, etc.). In some examples, when storage node <NUM><NUM> goes offline, data from storage node <NUM><NUM> may be stored in a handoff node <NUM> (e.g., an extra server, another storage node acting as a handoff node, a new server, etc.). While the illustrated example of <FIG> depicts a single handoff node <NUM>, any number of handoff nodes may be present, added, removed, etc..

In some examples, when storage node <NUM><NUM> goes offline, the data stored therein becomes unavailable. Therefore, in the illustrated example of <FIG>, the data (e.g., a fragment) from storage node <NUM><NUM> is rebuilt (e.g., recreated) based on the remaining fragments in the other nodes and the error correction coding. For example, if the object manager breaks an object into eight fragments (e.g., <NUM> data fragments and <NUM> parity fragments) and distributes the eight fragments into eight nodes (e.g., storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) and storage node <NUM><NUM> goes offline, the object manager <NUM> utilizes the other seven fragments from storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> and the error correction coding (e.g., equations, processes, functions, etc.) to recreate the missing eighth fragment and store it in the handoff node <NUM>.

In the illustrated example of <FIG>, the example distributed storage system <NUM> includes the first topology having the example object manager <NUM> communicatively connected to example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, and example storage node <NUM><NUM>. For example, the outage that caused storage node <NUM><NUM> to go offline is corrected. In some examples, once the outage is corrected (e.g., storage node <NUM><NUM> comes back online), the object manager <NUM> sends the fragment within the handoff node <NUM> to one or more of the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> within the distributed storage system, depending on the policies of the distributed storage system. For example, the object manager <NUM> may send the fragment from the handoff node <NUM> to storage node <NUM><NUM>. In such examples, storage node <NUM><NUM> and storage node <NUM><NUM> both contain the same fragment (e.g., creating an error in the code word) because the fragment that was in the storage node <NUM><NUM> when it went offline is still located in the storage node <NUM><NUM> when it comes back online, and the fragment that was in the storage node <NUM><NUM> is overwritten with the fragment from the handoff node <NUM>. In some examples, the object manager <NUM> sends the fragment from the handoff node <NUM> to all the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. In such examples, all the fragments may be overwritten with the fragment from the handoff node <NUM> (e.g., creating at least seven errors). As disclosed herein, when more than p errors occur (e.g., p = <NUM> in the above example), then the example object manager <NUM> fails to reproduce the example code word and the example distributed storage system <NUM> fails to recover the object associated with that code word.

In some examples, the fragment originally stored in the storage node <NUM><NUM> may be relocated to the storage node <NUM><NUM> and the fragment originally stored in the storage node <NUM><NUM> may be relocated to the storage node <NUM><NUM> (e.g., the first fragment "A" is stored in the storage node <NUM><NUM> and the third fragment "C" is stored in the storage node <NUM><NUM>). As described above, in some examples the example object manager <NUM> (<FIG>) concatenates, or otherwise arranges, the fragments according to the order of the storage nodes. As a result, the object manager <NUM> of <FIG> would compile the fragments stored within the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> to produce a code word C, B, A, D, E, F, Y, Z, instead of the original code word A, B, C, D, E, F, Y, Z. In other words, two "errors" have occurred (e.g., errors marked by x's in the following sequence: x, B, x, D, E, F, Y, Z). If the error correction coding used to create the code word is only able to correct for one error in the code word, the example object manager <NUM> would fail to recreate the original code word even when the object is encoded with the error correction coding. However, in the examples wherein the order of the fragments does not matter, no "errors" would have occurred.

Multiple errors may occur in a code word due to, for example, multiple nodes storing fragments becoming inaccessible. When the number of errors exceeds the error correction capacity of the error correction coding, the object manager <NUM> of <FIG> cannot recreate the original code words and thus the objects from which the code words were created. For example, if an error correction coding can correct up to <NUM> errors and <NUM> errors occur, the error correction coding cannot reconstruct the code word leading to a reconstruction error.

In some examples, a plurality of nodes may become unavailable (e.g., including one or more handoff nodes). Thus a fragment stored in a first node may be handed off (e.g., rebuilt based on error correction coding) to one of many different nodes. Additionally, fragments may be redistributed across any and/or all available nodes. In some examples, as the number of inaccessible nodes increases and/or the number of data redistributions increases, the location to which a fragment has been relocated becomes increasingly obscure. If a fragment cannot be located, the object manager <NUM> treats the missing fragment as an error. As disclosed herein, if enough other fragments are available, the object manager <NUM> can recreate a missing fragment. However, when multiple errors occur and/or there are multiple missing fragments, the object manager <NUM> cannot reconstruct the code word and the object associated with the code word.

Example methods and apparatus of the present disclosure assign indices to fragments in distributed storage systems to uniquely identify fragments and determine which fragments are stored within which node at any point in time. For example, once an index is assigned to a fragment (e.g., based on the node where it was originally stored), that fragment index remains the same even when the fragment is relocated to a different node. In some examples, the fragments (and the corresponding indices) are relocated based on the assigned indices. For example, if the fragment index of the fragment within a node does not match the node index, the fragment is relocated to the node that has a node index matching the fragment index. While examples disclosed herein refer to the storage of object fragments, the teachings of this disclosure are also applicable to the storage of whole objects (e.g., not fragmented), object segments, etc. Further, the fragments may be of any size (e.g., bytes, megabytes, gigabytes, etc.).

<FIG> are block diagrams illustrating an example distributed storage system <NUM> in which an example object manager <NUM> stores and/or retrieves an object in accordance with the teachings of this disclosure. In operation, the example object manager <NUM> of <FIG> is responsible for managing the example distributed storage system <NUM>. For example, the example object manager <NUM> of <FIG> receives requests from applications for the storage of objects to and/or retrieval of objects from the example distributed storage system <NUM>. In some examples, the object manager <NUM> of <FIG> uses one or more error correction codes to break an object into code word fragments. The example object manager <NUM> of <FIG> identifies locations (e.g., nodes) where the code word fragments are to be stored and/or where code word fragments are currently stored. In some examples, if a node is unavailable when storing, the object manager <NUM> of the example of <FIG> will identify a handoff node for temporary storage. In some examples, the object manager <NUM> of <FIG> redistributes fragment across the distributed storage system <NUM>. In some examples, the object manager <NUM> of <FIG> is implemented to be a proxy server.

In the illustrated example of <FIG>, the example distributed storage system <NUM> includes a first topology having the example object manager <NUM> communicatively connected to example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, and example storage node <NUM><NUM>. In some examples, one or more handoff nodes <NUM> (e.g., an extra server, another storage node acting as a handoff node, a new server, etc.) are available in the distributed storage system <NUM>.

In the illustrated example of <FIG>, the example object manager <NUM> stores fragments in the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, similar to the example object manager <NUM> shown in connection with <FIG>. The object manager <NUM> applies error correction coding to an example object to create an example code word including data fragments from the example object and parity fragments calculated from the data fragments. The example object manager <NUM> stores fragments of the example code word in the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>.

For example, for the example code word A, B, C, D, E, F, Y, Z (e.g., based on the example object O and corresponding data fragments A, B, C, D, E, F), the example object manager <NUM> stores the first fragment "A" in the example storage node <NUM><NUM>, the example object manager <NUM> stores the second fragment "B" in the example storage node <NUM><NUM>, the example object manager <NUM> stores the third fragment "C" in the example storage node <NUM><NUM>, the example object manager <NUM> stores the fourth fragment "D" in the example storage node <NUM><NUM>, the example object manager <NUM> stores the fifth fragment "E" in the example storage node <NUM><NUM>, the example object manager <NUM> stores the sixth fragment "F" in the example storage node <NUM><NUM>, the example object manager <NUM> stores the seventh fragment "Y" in the example storage node <NUM><NUM>, and the example object manager <NUM> stores the eighth fragment "Z" in the example storage node <NUM><NUM>.

In some examples, the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> contain only the fragments of the code word (e.g., object data and parity fragments). Alternatively, the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> may be separated into buckets, bins, or other storage containers, such that each storage node <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> contains different types and sizes of data along with the fragments of the code word. For example, the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> may contain multiple fragments from different code words, multiple fragments from the same code word, other objects, etc..

However, in some examples, the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, in which the fragments of objects are stored may go offline, fail, begin failing, begin producing errors, or otherwise become inaccessible. To illustrate such an occurrence, the example distributed storage system <NUM> of <FIG> includes a second topology when storage node <NUM><NUM> goes offline. The example second topology of the example distributed storage system <NUM> includes the example object manager <NUM> communicatively connected to example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, and example storage node <NUM><NUM>. In the illustrated example of <FIG>, example storage node <NUM><NUM> has gone offline, is failing, has failed, is producing errors, or is otherwise inaccessible. As disclosed herein, the example object manager <NUM> reconstructs the fragment (e.g., fragment "A") that was stored in the example storage node <NUM><NUM> using the fragments stored in the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. The example object manager <NUM> stores the reconstructed fragment in the example handoff node <NUM>.

<FIG> is a block diagram illustrating the example distributed storage system <NUM> including a third topology when storage node <NUM><NUM> comes back online. In the illustrated example of <FIG>, the third topology of the example distributed storage system <NUM> includes the example object manager <NUM> communicatively connected to example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, example storage node <NUM><NUM>, and example storage node <NUM><NUM>. For example, the outage that caused storage node <NUM><NUM> to go offline is corrected.

In some examples, once the outage is corrected (e.g., storage node <NUM><NUM> comes back online), the object manager <NUM> sends the fragment within the handoff node <NUM> (e.g., fragment "A") to one or more of the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> within the distributed storage system, depending on the policies of the distributed storage system. For example, the object manager <NUM> may send the fragment (e.g., fragment "A") from the handoff node <NUM> to storage node <NUM><NUM>. In such examples, storage node <NUM><NUM> and storage node <NUM> both contain the same fragment (e.g., fragment "A"). However, as disclosed herein, the example object manager <NUM> assigns indices to fragments for unique identification. Therefore, while both storage node <NUM><NUM> and storage node <NUM><NUM> may contain the same fragment (e.g., fragment "A"), storage node <NUM><NUM> contains an additional distinguishable fragment (e.g., fragment "C").

In some examples, the fragment originally stored in the storage node <NUM><NUM> may be relocated to storage node <NUM><NUM> and the fragment originally stored in the storage node <NUM><NUM> may be relocated to the storage node <NUM><NUM> (e.g., the first fragment "A" is stored in the storage node <NUM><NUM> and the third fragment "C" is stored in the storage node <NUM><NUM>). However, upon request by the example object manager <NUM>, each node can identify which fragment is stored within each node. Thus, the example object manager <NUM> can determine where each fragment is located and how to arrange the fragments prior to and/or during compilation of an example code word. In contrast, the example object manager <NUM> of <FIG> would be unaware that the first fragment "A" is stored in the storage node <NUM><NUM> and the third fragment "C" is stored in the storage node <NUM><NUM>.

In some examples, the object manager <NUM> identifies that the fragment stored in the handoff node <NUM> (e.g., fragment "A") belongs in the storage node <NUM><NUM> and moves the fragment from handoff node <NUM> to storage node <NUM><NUM> accordingly. Example methods and apparatus disclosed herein advantageously encode a fragment index into code word fragments to track and/or relocate the code word fragments to reduce and/or eliminate reconstruction error. Some such example methods and apparatus reconstruct original objects when a topology of a distributed storage system is changed after storage. Such example methods and apparatus are further described below in connection with the example object manager <NUM> of <FIG>. As will be apparent from the disclosure below, unlike the object manager <NUM> of <FIG>, the example object manager <NUM> of the illustrated example of <FIG> compiles the code word fragments stored within the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> to produce original code words. For example, the object manager <NUM> of <FIG> recreates the code word A, B, C, D, E, F, Y, Z, even when the topology of the distributed storage system <NUM> changes.

<FIG> is a block diagram illustrating an example implementation of the example object manager <NUM> of <FIG>. The example object manager <NUM> includes an example object fragmenter <NUM>, an example node index assigner <NUM>, an example fragment index assigner <NUM>, an example index database <NUM>, an example fragment compiler <NUM>, and an example node manager <NUM>.

The example object fragmenter <NUM> of <FIG> receives objects from applications and receives requests to store the objects in the distributed storage system <NUM> (<FIG>). In the illustrated example, the object fragmenter <NUM> encodes objects with error correction coding. In some examples, the object fragmenter <NUM> access an error correction coding library for error correction coding equations, processes, functions, etc. Based on the error correction coding, the example object fragmenter creates code words from the objects. The example code words include data fragment corresponding to the example object and one or more check symbols (e.g., parity fragments). As used herein, an example code word is defined to be an object encoded via error correction coding having data fragments and parity fragments.

The example object fragmenter <NUM> of <FIG> breaks up the example codes words into code word fragments. The example code word fragments may be any size (e.g., bit-sized, byte-sized, megabyte-sized, etc.). Additionally, the example object fragmenter <NUM> distributes and/or stores the example code word fragments into storage nodes based on a node index and/or a fragment index. In some examples, the object fragmenter <NUM> uses one or more rings (e.g., consistent hashing rings), which represent mappings between names of objects/fragments/containers stored on a disk and their physical location.

In some examples, the example object fragmenter <NUM> stores multiple fragments from different code words within the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. In examples wherein the storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> contain multiple fragments from different code words, the example object fragmenter <NUM> stores indications of which object with which the example fragments are associated. In some examples, the example object fragmenter <NUM> stores indications of the object from which the fragments are based within metadata associated with the fragments. In some examples, the example object fragmenter <NUM> stores indications of the object from which the fragments are based in an identifier (e.g., a name) of the fragment (e.g., obj1_fragment1, obj2_fragment1, etc.).

Additionally or alternatively, the example object fragmenter <NUM> of <FIG> separates objects into segments (e.g., without calculating parity segments) prior to encoding and fragmenting the objects. For example, an object may be <NUM> megabytes and the example object fragmenter <NUM> can separate the object into two <NUM> megabyte segments without calculating parity segments. The example object fragmenter <NUM> encodes the segments with error correction coding and fragment code words based on the segments, instead of based on the objects as disclosed herein. For example, a <NUM> megabyte object is broken into two <NUM> megabyte segments, each segment being encoded with erasure coding to break the segments into five <NUM> megabyte data fragments and two <NUM> megabyte parity fragments (e.g., calculated from the segment data fragments). In such examples, large objects can be separated into a collection of manageable smaller segments and/or code word fragments. In such examples, the parity fragment calculations may take less time and processing. For example, instead of calculating four <NUM> megabyte parity fragments from ten <NUM> megabyte data fragments, two megabyte parity fragments are calculated for five <NUM> megabyte data fragments twice.

The example node index assigner <NUM> of <FIG> generates a node index to assign identifiers to nodes (e.g., servers) that will store code word fragments. In some examples, the node index assigner <NUM> initially assigns the node index based on the object name (e.g., object node <NUM>, object node <NUM>, etc.) when fragments of the object are to be stored in respective nodes such that the same set of nodes are retrieved on subsequent requests for that object. In some examples, the node index is derived from a hash of the object's name (e.g., object name <NUM> → <NUM>, object name <NUM> → <NUM>, etc.). In the illustrated example of <FIG>, the node index identifies the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. In the illustrated example, the node index assigner <NUM> assigns a node index with zero-based values (e.g., the first index begins with zero). For example, the first storage node <NUM> is storage node <NUM>, the second storage node <NUM> is storage node <NUM>, the third storage node <NUM> is storage node <NUM>, the fourth storage node <NUM> is storage node <NUM>, the fifth storage node <NUM> is storage node <NUM>, the sixth storage node <NUM> is storage node <NUM>, the seventh storage node <NUM> is storage node <NUM>, and the eighth storage node <NUM> is storage node <NUM>.

In some examples, the node index is numerical. In some examples, the node index is alpha-numerical. In the illustrated example of <FIG>, the node index assigner <NUM> stores the node index in the index database <NUM>. The labels "storage node <NUM>," "storage node <NUM>," "storage node <NUM>," "storage node <NUM>," "storage node <NUM>," "storage node <NUM>," "storage node <NUM>," and "storage node <NUM>" of <FIG> are shown for illustrative purposes only.

The example fragment index assigner <NUM> of <FIG> generates a fragment index assigning identifiers to the code word fragments themselves. In some examples, the fragment index is based on the node index (e.g., the code word fragment to be stored in the storage node <NUM> is indexed as <NUM>, the code word fragment to be stored in the storage node <NUM> is indexed as <NUM>, etc.). In some examples, the fragment index assigner <NUM> encodes the fragment index into an identifier of the code word fragment, such as, for example, the name of the code word fragment (e.g., fragment name <NUM>). In some examples, the fragment index assigner <NUM> assigns the fragment index between the identifier (e.g., name) of the code word fragment and the file extension (e.g.,. data) of the code word fragment (e.g., fragmentname0. In some examples, the fragment index assigner <NUM> encodes the fragment index into metadata associated with the code word fragment. In some examples, the fragment index is numerical, alphabetical, alpha-numerical, etc..

Additionally or alternatively, the example fragment index assigner <NUM> may assign additional indices to other variations of objects (e.g., segments) as discussed herein. For example, the fragment index assigner <NUM> assigns an index to an object, an index to a segment of the object, and an index to a code word fragment of the segment of the object (e.g., object A, segment a, fragment <NUM>).

In the illustrated example of <FIG>, the example index database <NUM> is a storage device (e.g., hard drives, solid state drives, floppy disks, compact disks, Blu-ray disks, RAID systems, and digital versatile disks (DVD), etc.) that stores node indices and/or copies of fragment indices. In some examples, the index database <NUM> includes mapping tables associating node indexes with fragment indices.

The example fragment compiler <NUM> of <FIG> receives requests from applications to retrieve objects stored in the example distributed storage system <NUM> (<FIG>). Based on the requests, the example fragment compiler <NUM> requests code word fragments from storage nodes. In some examples, the fragment compiler <NUM> checks fragment indices associated with the code word fragments to determine whether the fragment indices match a node index.

When a fragment index matches a node index, the example fragment compiler <NUM> of <FIG> compiles code word fragments together according to the node index and/or the fragment index (e.g., because they are the same). For example, when the example code word A, B, C, D, E, F, Y, Z, is stored within the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> the example fragment compiler <NUM> requests the first code word fragment (e.g., fragment "A") from the example storage node <NUM><NUM>. If the fragment index (e.g., fragment <NUM>) matches the node index (e.g., storage node <NUM>), the example fragment compiler <NUM> retrieves the first code word fragment (e.g., fragment "A") and begins to recreate the example code word using the retrieved code word fragment as the beginning of the code word.

Similarly, the example fragment compiler <NUM> of <FIG> requests and retrieves the remaining code word fragments. In some examples, the fragment compiler <NUM> concatenates the fragments when the fragment index of each fragment matches the node index. For example, the example fragment compiler <NUM> retrieves the second code word fragment from the corresponding storage node <NUM> and concatenates the second code word fragment to the first code word fragment (e.g., places the second code word fragment in the second position A, B). The example fragment compiler <NUM> retrieves the third code word fragment from the corresponding storage node <NUM><NUM> and concatenates the third code word fragment to the first and second code word fragments (e.g., places the third code word fragment in the third position A, B, C). The example fragment compiler <NUM> retrieves the fourth fragment from the corresponding storage node <NUM> and concatenates the fourth code word fragment to the first, second, and third code word fragments (e.g., places the fourth fragment in the fourth position A, B, C, D), etc. In some examples, the fragment compiler <NUM> does not concatenate the code word fragments. In some error correction schemes, a code word can be decoded without concatenation as long as enough uniquely identifiable fragments are available for the error correction scheme to correct for the errors/missing fragments.

When a fragment index does not match the node index, the example fragment compiler <NUM> of <FIG> communicates with the node to determine which code word fragment(s) are stored in that node. In such examples, the fragment compiler <NUM> retrieves and compiles code word fragments together according to the fragment index (e.g., because the node index may be incorrect due to data redistribution, server outage, data loss, etc.).

For instance, assume the code word A, B, C, D, E, F, Y, Z, was initially stored within the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> (<FIG>). Further, assume that after a topology change, example storage node <NUM><NUM> currently stores the third fragment "C" of the code word and example storage node <NUM><NUM> may currently stores the first fragment "A" of the code word. In such an example, the fragment compiler <NUM> of <FIG> requests the first code word fragment (e.g., fragment "A") from the storage node <NUM><NUM> (e.g., because the storage node <NUM><NUM> is in the location associated with the first node in the node index). In the illustrated example of <FIG>, the fragment compiler <NUM> determines that the fragment index (e.g., fragment <NUM>) does not match the node index (e.g., storage node <NUM>) and thus, the fragment compiler <NUM> determines that the first code word fragment is not stored in the storage node <NUM><NUM> (e.g., the first code word fragment (fragment "A") was requested from the first node, but the third code word fragment (fragment "C") is stored in the first node).

In some examples, the example fragment compiler <NUM> determines the third code word fragment is stored in the storage node <NUM><NUM> based on the fragment index of that code word fragment (e.g., fragment index is <NUM>, which refers to the third code word fragment (fragment "C") in a zero-based value scheme) without retrieving the code word fragment. In some examples, the fragment compiler <NUM> retrieves the third code word fragment (e.g., fragment "C") in response to an application request, and the fragment compiler <NUM> begins to recreate the example code word by placing the retrieved code word fragment in the third position of the code word (e.g., "_, _, C, _. ") based on the fragment index.

In some examples, the example fragment compiler <NUM> of <FIG> requests and retrieves the remaining code word fragments. For example, the fragment compiler <NUM> retrieves the second code word fragment from the corresponding storage node <NUM><NUM> and places the retrieved code word fragment in the second position (e.g., "_, B, C, _. The example fragment compiler <NUM> retrieves the first code word fragment from the corresponding storage node <NUM><NUM> and places the retrieved code word fragment in the first position (e.g., "A, B, C, _. The example fragment compiler <NUM> retrieves the fourth code word fragment from the appropriate storage node <NUM><NUM> and places the fourth code word fragment in the fourth position (e.g., "A, B, C, D,. "), etc. By indexing the example fragments as disclosed herein, the example object manager <NUM> recreates code words, and thus the objects from which the code words are generated, from fragments even when the fragments have been relocated (e.g., redistributed).

In some examples, the example fragment compiler <NUM> recreates missing and/or erred fragments. For example, in the illustrated example of <FIG> when example storage node <NUM><NUM> goes offline, the fragment stored therein (e.g., fragment "A") becomes unavailable. In such examples, the example fragment compiler <NUM> reconstructs that fragment (e.g., fragment "A") using the error correction coding and the remaining fragments from example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. Additionally or alternatively, the example fragment compiler <NUM> uses the error correction coding when requests for the fragments of the object return one or more erred fragments and/or when requests for the fragments of the object result in missing fragments. For example, if the example fragment compiler <NUM> requests eight unique fragments (e.g., A, B, C, D, E, F, Y, Z) from the eight storage nodes and only receives seven unique fragments (e.g., A, B, B, D, E, F, Y, Z), the example fragment compiler <NUM> recreates the third fragment (e.g., fragment "C") from the non-erred fragments (e.g., A, B, D, E, F, Y, Z).

In some examples, the node manager <NUM> of <FIG> identifies when code word fragments are located in nodes different from where the code word fragments were originally stored and relocates them accordingly. For example, the node manager <NUM> determines for the storage node <NUM><NUM> that the fragment index (e.g., fragment <NUM>) does not match the node index (e.g., storage node <NUM>). The example node manager <NUM> determines that the third code word fragment (e.g., fragment "C") is stored in the storage node <NUM><NUM> based on the fragment index (e.g., fragment <NUM> is associated with the third code word fragment). Additionally, the example node manager identifies a storage node associated with the fragment index (e.g., storage node <NUM> is associated with the fragment index (e.g., <NUM>) of the third code word fragment (e.g., fragment "C"). The example node manager <NUM> moves the third code word fragment into the storage node <NUM><NUM>. In such examples, data within the storage node <NUM><NUM> will not be overwritten because the third code word fragment is distinguishable from any other data within the storage node <NUM> (e.g., distinguished by the fragment index).

If there are additional fragments within the example storage node <NUM><NUM>, the above process repeats. If there are no additional fragments in the example storage node <NUM><NUM>, the example node manager <NUM> moves onto examining/processing the next node. For example, the example node manager <NUM> determines that the first code word fragment (e.g., fragment "A") is stored in the storage node <NUM><NUM> based on the fragment index (e.g., fragment <NUM> is associated with the first code word fragment). Next, the example node manager <NUM> identifies the storage node associated with the fragment index (e.g., storage node <NUM> is associated with the fragment index (<NUM>) of the first code word fragment). The example node manager <NUM> moves the first code word fragment into the storage node <NUM><NUM>. Such processing may be performed in parallel as opposed to the serial processing described above. Accordingly, the example node manager <NUM> identifies and relocates code word fragment(s) based on the fragment indic(es) and/or the node indic(es).

In operation, the example object fragmenter <NUM> of <FIG> receives an example object from an application. In the illustrated example, the object fragmenter <NUM> applies error correction coding to create a code word based on the example object. For example, the object fragmenter <NUM> calculates one or more parity fragments to add to data fragments of the object. The example object fragmenter <NUM> breaks up the example code word (e.g., the data fragments plus the parity fragments) into code word fragments.

In the illustrated example of <FIG>, the node index assigner <NUM> generates a node index. In some examples, the node index is associated with the object (e.g., based on a name of the object). In some examples, the node index assigner <NUM> stores the node index in the index database <NUM>. Additionally, the example fragment index assigner <NUM> generates an example fragment index. In some examples, the fragment index is based on the node index (e.g., identical to the node index at the time of storage). The example object fragmenter <NUM> encodes the code word fragments with the example fragment index. In some examples, the fragment index is encoded into an identifier of the code word fragment (e.g., the fragment name). In some examples, the fragment index is encoded into metadata associated with the code word fragment. The example object fragmenter <NUM> stores the code word fragments and the corresponding fragment indices in respective storage nodes (e.g., storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) according to the example node index. The example fragmenter <NUM> encodes the fragment index in the code word fragments themselves such that redistribution of the code word fragments into new nodes does not obfuscate the original configuration.

In some examples, one or more of the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> go offline after fragments are stored therein, thereby making fragments unavailable. For example, in the illustrated example of <FIG>, when example storage node <NUM><NUM> goes offline, the fragment stored therein (e.g., fragment "A") becomes unavailable. In such examples, the example fragment compiler <NUM> reconstructs the unavailable fragment (e.g., fragment "A") using the error correction coding and the available fragments from example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>. The example fragmenter <NUM> stores the recreated fragment in the example handoff node <NUM>. This process may occur many times during the storage of the example fragments, occur in different handoff nodes, and may continue so long as less than p fragments are erred or become unavailable.

The example fragment compiler <NUM> of <FIG> receives a request from the application for the example object stored in the example distributed storage system <NUM> (<FIG>). The example fragment compiler <NUM> sends requests to the storage nodes according to the example node index stored in the example index database <NUM>.

In the illustrated example, when the fragment compiler <NUM> of <FIG> sends a request (e.g., a message) to the storage node <NUM><NUM> for a first code word fragment, the storage node <NUM><NUM> responds to the fragment compiler <NUM> indicating the fragment index of the code word fragment stored therein. In some examples, the fragment compiler <NUM> receives a response from the storage node <NUM><NUM> that the fragment index of the code word fragment stored therein indicates that the code word fragment is not the first code word fragment (e.g., node <NUM> does not have fragment <NUM>). In some examples, the fragment compiler <NUM> receives a response from the storage node <NUM><NUM> that the fragment index of the code word fragment stored therein indicates that the code word fragment is a different code word fragment (e.g., node <NUM> has fragment <NUM>). In some examples, the fragment compiler <NUM> receives a response from the storage node <NUM><NUM> that the fragment index of the code word fragment stored therein indicates that the code word fragment is not the first code word fragment and the code word fragment stored therein is a different code word fragment (e.g., node <NUM> does not have fragment <NUM>; node <NUM> has fragment <NUM>). In some examples, the fragment compiler <NUM> receives a response from the storage node <NUM><NUM> that multiple code word fragments are stored in the storage node <NUM><NUM> (e.g., node <NUM> has fragment <NUM> and fragment <NUM>).

In some examples, the fragment compiler <NUM> determines whether the fragment index of the code word fragment stored in the storage node <NUM><NUM> matches the node index (e.g., is fragment <NUM> in node <NUM>?). In some examples, the example fragment compiler <NUM> accesses the fragment index of the code word fragment without retrieving the code word fragment itself. If the example fragment index of the code word fragment stored in the example storage node <NUM><NUM> matches the example node index, then the example fragment compiler <NUM> retrieves the requested code word fragment from the example storage node <NUM><NUM>. The example fragment compiler <NUM> compiles code word fragments according to the example node index when the example node index matches the fragment index.

In some examples, if the example fragment index of the code word fragment stored in the example storage node <NUM><NUM> does not match the example node index, then the example fragment compiler <NUM> of <FIG> retrieves the code word fragment from the example storage node <NUM><NUM> even though that code word fragment was not the requested code word fragment. However, because the example fragment compiler <NUM> can uniquely identify the retrieved code word fragment by its fragment index, the fragment compiler <NUM> can compile the original code word correctly. In such examples, the example fragment compiler <NUM> compiles the code word fragment(s) according to the fragment indic(es) when the example node indic(es) does not match the fragment indic(es).

In some examples, the node manager <NUM> of <FIG> relocates code word fragments into storage nodes based on the fragment index prior to the example fragment compiler <NUM> requesting and/or retrieving the code word fragment from the storage nodes. For example, the node manager <NUM> determines whether the fragment index of the code word fragment stored in the storage node <NUM><NUM> matches the node index (e.g., is fragment <NUM> in node <NUM>?). If the example fragment index of the code word fragment stored in the example storage node <NUM><NUM> does not match the example node index, then the example node manager <NUM> identifies the example node associated with a node index matching the fragment index. For example, if fragment <NUM> is in node <NUM>, the node manager <NUM> identifies node <NUM>. The example node manager <NUM> moves the code word fragment from node <NUM> (e.g., example storage node <NUM><NUM>) to node <NUM> (e.g., example storage node <NUM><NUM>). Similarly, if fragment <NUM> is in node <NUM>, the example node manager <NUM> identifies node <NUM> and moves fragment <NUM> from node <NUM> (e.g., example storage node <NUM><NUM>) to node <NUM> (e.g., example storage node <NUM><NUM>). The example node manager <NUM> may move fragments between nodes one at a time (e.g., serial processing) or at the same time (e.g., parallel processing).

While an example manner of implementing the example object manager <NUM> of <FIG> is illustrated in <FIG>, one or more of the elements, processes and/or devices illustrated in <FIG> may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example object fragmenter <NUM>, the example node index assigner <NUM>, the example fragment index assigner <NUM>, the example index database <NUM>, the example fragment compiler <NUM>, the example node manager <NUM>, and/or, more generally, the example object manager <NUM>, the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, the example handoff node <NUM>, and/or more generally, the example distributed storage system <NUM> of <FIG>may be implemented individually and/or collectively by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example object fragmenter <NUM>, the example node index assigner <NUM>, the example fragment index assigner <NUM>, the example index database <NUM>, the example fragment compiler <NUM>, the example node manager <NUM>, and/or, more generally, the example object manager <NUM>, the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, the example handoff node <NUM>, and/or more generally, the example distributed storage system <NUM> of <FIG> could be implemented individually and/or collectively by one or more analog or digital circuit(s), discrete and/or integrated circuitry, logic circuits, glue logic, programmable processor(s), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)). When reading any of the apparatus or system claims of this patent to cover a purely software and/or firmware implementation, at least one of the example object fragmenter <NUM>, the example node index assigner <NUM>, the example fragment index assigner <NUM>, the example index database <NUM>, the example fragment compiler <NUM>, the example node manager <NUM>, and/or, more generally, the example object manager <NUM>, the example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, the example handoff node <NUM>, and/or more generally, the example distributed storage system <NUM> of <FIG> is/are hereby expressly defined to include a tangible computer readable storage device or storage disk such as a memory, a digital versatile disk (DVD), a compact disk (CD), a Blu-ray disk, etc. storing the software and/or firmware. Further still, the example object manager <NUM> of <FIG> may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated in <FIG>, and/or may include more than one of any or all of the illustrated elements, processes and devices.

Flowcharts representative of example machine readable instructions for implementing the example object manager <NUM> of <FIG> are shown in <FIG>. In these examples, the machine readable instructions comprise programs for execution by a processor such as the processor <NUM> shown in the example processor platform <NUM> discussed below in connection with <FIG>. The programs may be embodied in software stored on a tangible computer readable storage medium such as a CD-ROM, a floppy disk, a hard drive, a digital versatile disk (DVD), a Blu-ray disk, or a memory associated with the processor <NUM>, but the entire programs and/or parts thereof could alternatively be executed by a device other than the processor <NUM> and/or embodied in firmware or dedicated hardware. Further, although the example programs are described with reference to the flowcharts illustrated in <FIG>, many other methods of implementing the example object manager <NUM> may alternatively be used. For example, the order of execution of the blocks may be changed, and/or some of the blocks described may be changed, eliminated, or combined.

As mentioned above, the example processes of <FIG> may be implemented using coded instructions (e.g., computer and/or machine readable instructions) stored on a tangible computer readable storage medium such as a hard disk drive, a flash memory, a read-only memory (ROM), a compact disk (CD), a digital versatile disk (DVD), a cache, a random-access memory (RAM) and/or any other storage device or storage disk in which information is stored for any duration (e.g., for extended time periods, permanently, for brief instances, for temporarily buffering, and/or for caching of the information). As used herein, the term tangible computer readable storage medium is expressly defined to include any type of computer readable storage device and/or storage disk and to exclude propagating signals and transmission media. As used herein, "tangible computer readable storage medium" and "tangible machine readable storage medium" are used interchangeably. Additionally or altematively, the example processes of <FIG> may be implemented using coded instructions (e.g., computer and/or machine readable instructions) stored on a non-transitory computer and/or machine readable medium such as a hard disk drive, a flash memory, a read-only memory, a compact disk, a digital versatile disk, a cache, a random-access memory and/or any other storage device or storage disk in which information is stored for any duration (e.g., for extended time periods, permanently, for brief instances, for temporarily buffering, and/or for caching of the information). As used herein, the term non-transitory computer readable medium is expressly defined to include any type of computer readable storage device and/or storage disk and to exclude propagating signals and transmission media. As used herein, when the phrase "at least" is used as the transition term in a preamble of a claim, it is open-ended in the same manner as the term "comprising" is open ended.

<FIG> is an example flow diagram representative of example machine-readable instructions <NUM> that may be executed to implement the example object manager <NUM> of <FIG>. The example machine-readable instructions <NUM> of <FIG> begin at block <NUM>. At block <NUM>, the example object fragmenter <NUM> of the example object manager <NUM> receives an object to be stored in the distributed storage system <NUM> (<FIG>). In some examples, the object is to be stored in a single storage device. In some examples, the object is to be fragmented. In the illustrated example of <FIG>, the example object fragmenter <NUM> determines whether the object is to be fragmented (block <NUM>). In some examples, the object fragmenter <NUM> determines the object is to be fragmented to provide data durability, reliable data availability and/or error protection/correction. In some examples, the object fragmenter <NUM> determines to fragment the object based on a policy of the distributed storage system <NUM>. In some examples, the object fragmenter <NUM> determines to fragment the object based on instructions from an application.

If the example object fragmenter <NUM> determines that the object is to be fragmented (block <NUM>: YES), control proceeds to block <NUM>. If the example object fragmenter <NUM> determines that the object is not to be fragmented (block <NUM>: NO), the example machine-readable instructions <NUM> cease execution.

At block <NUM>, the example object fragmenter <NUM> breaks the example object into code word fragments. In some examples, the fragmenter <NUM> breaks the object into fragments and calculates additional fragments (e.g., parity fragments) to create the code word fragments. The example fragmenter <NUM> determines the number of fragments and/or additional fragments based on the type of error correction coding used to encode the object. For example, the fragmenter <NUM> can calculate four parity fragments for an object having ten data fragments to create a fourteen fragment code word (e.g., a <NUM>:<NUM> Reed-Solomon coding technique).

Once the example fragmenter <NUM> has broken the example object into code word fragments, the example node index assigner <NUM> determines which nodes the code word fragments will be stored in. The example node index assigner <NUM> generates and assigns an example node index for each node in which a code word fragment will be stored (block <NUM>). In some examples, the node index is based on a name of the object such that the same set of nodes are retrieved on subsequent requests for that object. In some examples, the node index is stored in the index database <NUM>.

Once the example node index assigner <NUM> determines which nodes in which the code word fragments will be stored (block <NUM>), the example fragment index assigner <NUM> generates and assigns an example fragment index for each code word fragment (block <NUM>). In some examples, the fragment index is derived from the node index. In some examples, the fragment index is identical to the node index at the time a code word fragment is stored within a corresponding node. In the illustrated example, the fragment index assigner <NUM> assigns fragment indices to corresponding fragments. In some examples, the fragment index assigner <NUM> encodes fragment indices into identifiers (e.g., fragment names) of the fragments. In some examples, the fragment index assigner <NUM> encodes fragment indices into metadata associated with fragments. The example fragmenter <NUM> distributes the code word fragments and the corresponding fragment indices to example storage nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> (<FIG>) (block <NUM>). Thereafter, the example machine-readable instructions <NUM> cease execution. While the example machine-readable instructions <NUM> are illustrated as a serial process, one or more blocks may be processed in parallel without departing from the scope of the present disclosure.

<FIG> is an example flow diagram representative of example machine-readable instructions <NUM> that may be executed to implement the example fragment compiler <NUM> to retrieve objects from the example distributed storage system <NUM>. The example machine-readable instructions <NUM> of <FIG> begin at block <NUM>. At block <NUM>, the example fragment compiler <NUM> requests a code word fragment of the example object from a storage node according to the node index stored in the example index database <NUM>. The example fragment compiler <NUM> determines whether the fragment index associated with the code word fragment in the storage node matches the node index (block <NUM>). If the fragment index is the same as the node index (block <NUM>: YES), then control proceeds to block <NUM>.

At block <NUM>, the example fragment compiler <NUM> receives acknowledgment from the storage node that the code word fragment in the example node has a fragment index matching the node index. The example fragment compiler <NUM> retrieves the example code word fragment from the example node (block <NUM>). The example fragment compiler <NUM> begins to compile (e.g., concatenate) the example object using the retrieved example code word fragment according to the example node index and/or the fragment index (e.g., the code word fragment from the first node is the first code word fragment of the code word, the code word fragment from the second node is the second code word fragment of the code word, etc.) (block <NUM>). The example fragment compiler <NUM> determines whether there are additional nodes with code word fragments (block <NUM>). If there are additional nodes with code word fragments (block <NUM>: YES), then control returns to block <NUM>. If there are no additional nodes with fragments (block <NUM>: NO), the example machine-readable instructions <NUM> cease execution. In some examples, the example fragment complier <NUM> queries the example nodes for example code word fragment indices without retrieving the example code word fragments.

However, if the fragment index is not the same as the node index (block <NUM>: NO), then control proceeds to block <NUM>. At block <NUM>, the storage node responds to the example fragment compiler <NUM> with the fragment index associated with the code word fragment within the storage node. For example, the example fragment compiler <NUM> requests a first code word fragment (e.g., fragment <NUM> - fragment "A") from the storage node <NUM><NUM> (<FIG>). In such examples, the storage node <NUM><NUM> responds to the example fragment compiler <NUM> with the fragment index of the code word fragment stored in the storage node <NUM><NUM> (e.g., the storage node <NUM><NUM> responds that fragment <NUM> (fragment "C") is stored within the storage node <NUM><NUM>, not fragment <NUM> (fragment "A")). At block <NUM>, the example fragment compiler <NUM> notes the fragment index associated with the example code word fragment (e.g., <NUM>) and retrieves the code word fragment from the storage node. At block <NUM>, the example fragment compiler <NUM> begins to compile (e.g., concatenate, decode, etc.) the object using the retrieved code word fragment according to the fragment index (e.g., the code word fragment from the first node is the third code word fragment of the code word, the code word fragment from the second node is the second code word fragment of the code word, the code word fragment from the third node is the first code word fragment of the code word, etc.). Thus, the example fragment compiler <NUM> compiles the code word correctly when the topology of the storage nodes and/or the data within the storage nodes have been rearranged as shown in connection to the example distributed storage system <NUM> in <FIG>. Thereafter, control the proceeds to block <NUM>. As described above, if there are additional nodes with fragments (block <NUM>: YES), then control returns to block <NUM>. If there are no additional nodes with fragments (block <NUM>: NO), the example machine-readable instructions <NUM> cease execution. As described here, once an example code word has been recreated, the example fragment compiler <NUM> can determine the object from which the code word was created (e.g., the code word is the object encoded with error correction coding) and send the object to the requesting application. While the example machine-readable instructions <NUM> are illustrated as a serial process, one or more blocks may be processed in parallel without departing from the scope of the present disclosure.

<FIG> is an example flow diagram representative of example machine-readable instructions <NUM> that may be executed to implement the example node manager <NUM> of <FIG>. In some examples, the machine-readable instructions <NUM> may be executed prior to the machine-readable instructions <NUM> to relocate code word fragments into nodes in which the code word fragments were originally stored. The example machine-readable instructions <NUM> of <FIG> begin at block <NUM>. At block <NUM>, the example node manager <NUM> determines whether the fragment index associated with a first code word fragment in a first node matches the node index, similarly to the example fragment compiler <NUM> described in connection with <FIG> (block <NUM>). If the fragment index associated with the first code word fragment in the first node is the same as the node index (block <NUM>: YES), then the example node manager <NUM> need not relocate the example code word fragment and control proceeds to block <NUM>.

If the example fragment index associated with the first code word fragment in the first node is not the same as the example node index (block <NUM>: NO), then control proceeds to block <NUM>. At block <NUM>, the example node manager <NUM> identifies the first code word fragment located at the first node based on the fragment index (e.g., storage node <NUM> stores fragment <NUM>). In the illustrated example, the node manager <NUM> identifies a next node corresponding to the fragment index of the first code word fragment (e.g., if the first fragment is fragment <NUM>, then the next node is storage node <NUM>) (block <NUM>). In the illustrated example of <FIG>, the node manager <NUM> moves (e.g., copy/cut and paste) the first code word fragment from the first node to the next node (block <NUM>) and control proceeds to block <NUM>. At block <NUM>, the example node manager <NUM> identifies whether there is another fragment in the first node. If the example node manager <NUM> identifies that there are no additional fragments within the first node (block <NUM>: NO), control proceeds to block <NUM>. If the example node manager <NUM> identifies there is another fragment within the first node (block <NUM>: YES), control proceeds to block <NUM>. At block <NUM>, the example node manager <NUM> treats the other fragment within the first node as the first fragment and control returns to block <NUM>.

At block <NUM>, the example node manager <NUM> determines whether there are additional nodes with code word fragments. If there are additional nodes with code word fragments (block <NUM>: YES), then control proceeds to block <NUM>. At block <NUM>, the example node manager <NUM> increments a node counter (e.g., first node = first node + <NUM>) such that a subsequent node is processed as discussed in connection with the first node disclosed above. Thereafter, control returns to block <NUM>. If there are no additional nodes with code word fragments (block <NUM>: NO), the example machine-readable instructions <NUM> cease execution.

The example machine-readable instructions <NUM> of <FIG> relocate code word fragments that have been redistributed (e.g., due to a network outage, server failure, etc.) from the example nodes in which the code word fragments were originally stored using the fragment indices generated and assigned to the example code word fragments by the example fragment index assigner <NUM> of the example object manager <NUM> (<FIG>). In some examples, the machine-readable instructions <NUM> may be implemented by a background daemon of the example distributed storage system <NUM> (<FIG>) instead of or in connection with the example node manager <NUM>. In some examples, the fragment compiler <NUM> compiles (e.g., concatenates, decodes, etc.) the code word fragments according to the example node index (e.g., the order in which the fragments of the object were originally stored). In some examples, the fragment compiler <NUM> decodes the fragments independent of the order of fragments. While the example machine-readable instructions <NUM> are illustrated as a serial process, one or more blocks may be processed in parallel without departing from the scope of the present disclosure.

<FIG> is a block diagram of an example processor platform <NUM> capable of executing the instructions of <FIG> to implement the example object manager <NUM> of <FIG>. The processor platform <NUM> can be, for example, a server, a personal computer, a mobile device (e.g., a cell phone, a smart phone, a tablet such as an iPad™), a personal digital assistant (PDA), , or any other type of computing device.

In the illustrated example, the processor <NUM> is programmed to implement the example object fragmenter <NUM>, the example node index assigner <NUM>, the example fragment index assigner <NUM>, the example fragment compiler <NUM>, and the example node manager <NUM>.

The input device(s) <NUM> permit(s) a user to enter data and commands into the processor <NUM>.

The output devices <NUM> can be implemented, for example, by display devices (e.g., a light emitting diode (LED), an organic light emitting diode (OLED), a liquid crystal display, a cathode ray tube display (CRT), a touchscreen, a tactile output device, a light emitting diode (LED), a printer and/or speakers). The interface circuit <NUM> of the illustrated example, thus, typically includes a graphics driver card, a graphics driver chip or a graphics driver processor.

In the illustrated example, the one or more mass storage devices include the example index database <NUM>.

The coded instructions <NUM> of <FIG> may be stored in the mass storage device <NUM>, in the volatile memory <NUM>, in the non-volatile memory <NUM>, and/or on a removable tangible computer readable storage medium such as a CD or DVD.

From the foregoing, it will be appreciated that example methods, apparatus and articles of manufacture have been disclosed which provide indexing of fragments in distributed storage systems such that fragments can be tracked despite their relocation. Example methods, apparatus and articles of manufacture disclosed herein provide fragment relocation based on the assigned indices. Such fragment indexing reduces the number of missing fragments in an error correction encoded code word. Example disclosed methods, apparatus and articles of manufacture disclosed herein increase an error correction rate such that an increased number of objects can be recovered when fragments are relocated, lost, or otherwise unavailable, thus making distributed storage systems more efficient and reliable.

Claim 1:
An apparatus to index fragments of objects, comprising:
a fragmenter (<NUM>) to encode an object with error correction coding to separate the object into fragments;
a node index assigner (<NUM>) to create a first index indicative of storage nodes where the fragments of the object are to be stored; and
a fragment index assigner (<NUM>) to encode a second index into identifiers of the fragments of the object, the second index based on the first index, the fragmenter to store the fragments of the object and the corresponding second index encoded identifiers in the storage nodes based on the first index; further including a fragment compiler to:
send a message to a first one of the storage nodes requesting a first one of the fragments of the object; and
receive a response from the first one of the storage nodes, the response indicating that the first one of the fragments of the object is not stored in the first one of the storage nodes and that a second one of the fragments of the object is stored in the first one of the storage nodes.