Patent Description:
The use of network computing and storage has proliferated in recent years. The resources for network computing and storage are often provided by computing resource providers who leverage large-scale networks of computers, servers and storage drives to enable clients, including content providers, online merchants and the like, to host and execute a variety of applications and web services. Content providers and online merchants, who traditionally used on-site servers and storage equipment to host their websites and store and stream content to their customers, often forego on-site hosting and storage and turn to using the resources of the computing resource providers. The usage of network computing allows content providers and online merchants, among others, to efficiently and to adaptively satisfy their computing needs, whereby the computing and storage resources used by the content providers and online merchants are added or removed from a large pool provided by a computing resource provider as need and depending on their needs. The proliferation of network computing and storage, as well as the attendant increase in the number of entities dependent on network computing and storage, has increased the importance of optimizing data performance and integrity on network computing and storage systems. Data archival systems and services, for example, may use various types of error correcting and error tolerance schemes, such as the implementation of redundancy coding and data sharding. Furthermore, capacity and cost of persisting increasing quantities of data may be mitigated by the use of data storage devices or media that is considerably faster at sequential storage than random access storage, relative to other data storage devices. <CIT> discloses a distributed, web-services based storage system. <CIT> discloses a processing module that encodes data using a dispersed storage error coding function to produce a set of encoded data slices and identifies storage units for storage of the set of encoded data slices. <CIT> discloses an archival storage and retrieval system that enables fine grained control over data availability is implemented across a Quality of Service driven archival system. "<NPL>et al discloses HAIL (Hadoop Aggressive Indexing Library), a novel indexing approach for HDFS and Hadoop MapReduce.

The subject matter for which protection is sought is defined by the independent claims.

The present disclosure will be described with reference to the drawings, in which:.

Techniques described and suggested herein include systems and methods for storing original data of data archives ("archives") on data storage systems using redundancy coding techniques. For example, redundancy codes, such as erasure codes, may be applied to incoming archives (such as those received from a customer of a computing resource service provider implementing the storage techniques described herein) so as allow the storage of original data of the individual archives available on a minimum of volumes, such as those of a data storage system, while retaining availability, durability, and other guarantees imparted by the application of the redundancy code.

Archives, such as customer archives containing any quantity and nature of data, are received from customers of a computing resource service provider through a service, such as an archival storage service, provided by one or more resources of the computing resource service provider. The archives may be sorted according to one or more common attributes, such as the identity of the customer, the time of upload and/or receipt by, e.g., the archival storage service. Such sorting may be performed so as to minimize the number of volumes on which any given archive is stored. The original data of the archives is stored as a plurality of shards across a plurality of volumes, the quantity of which (either shards or volumes, which in some cases may have a one to one relationship) may be predetermined according to various factors, including the number of total shards necessary to reconstruct the original data using a redundancy code.

One or more indices may be generated in connection with, e.g., the order in which the archives are to be stored, as determined in connection with the sorting mentioned immediately above. An index may be generated for each volume of the plurality, and may reflect the archives stored on the respective volume to which it applies. The indices may be of any appropriate type, and may include sparse indices. Where sparse indices are used, the index (e.g., for a given volume) may point to a subset of archives stored or to be stored on, e.g., that volume. The subset may be selected on any basis and for any appropriate interval. Examples may include the identification of the archives located at an interval of x blocks or bytes of the volume, or the identification of the archives at an interval of n archives, where x or n may be predetermined by, e.g., the archival storage service or an administrator thereof.

The sparse indexes are used in connection with information relating to the sort order of the archives so as to locate archives without necessitating the use of dense indexes, e.g., those that account for every archive on a given volume. Such sort order-related information may reside on the volume(s) or, ion an entity separate from the volume(s). Similarly, the indexes may be stored on the same volume(s) to which they apply, or separately from such volume(s). Where the sort order-related information and/or the indexes are stored on the applicable volumes, they may be included with the original data of the archives and stored therewith as shards, as previously mentioned.

The original data of the archives (and, where the indices are stored on the volumes, the indices) is processed by an entity associated with, e.g., the archival storage service, using a redundancy code, such as an erasure code, so as to generate redundancy coded shards that may be used to regenerate the original data and, if applicable, the indices. The redundancy code may utilize a matrix of mathematical functions (a "generator matrix"), a portion of which may include an identity matrix. The redundancy coded shards may correspond, at least in part, to the portion of the generator matrix that is outside of the identity matrix. Redundancy coded shards so generated may be stored in further volumes. The total number of volumes may include the volumes bearing the original data (and indices) as well as the volumes containing the redundancy coded shards.

Retrieval of an archive stored in accordance with the techniques described herein may be requested by an entity, such as a client device under control of a customer of the computing resource service provider and/or the archival storage service provided therefrom, as described in further detail throughout this disclosure. In response to the request, the data storage system (e.g., the system including the aforementioned volumes, and providing the archival storage service) may locate, based on information regarding the sort order of the archives as stored on the volumes, the specific volume on which the archive is located. Thereafter, the index or indices may be used to locate the specific volume, whereupon it is read from the volume and provided to the requesting entity. Where sparse indexes are employed, the sort order information may be used to locate the nearest location (or archive) that is sequentially prior to the requested archive, whereupon the volume is sequentially read from that location or archive until the requested archive is found.

If one of the volumes or a shard stored thereon is detected as corrupt, missing, or otherwise unavailable, a new shard may be generated using the redundancy code applied to generate the shard(s) in the first instance. The new shard may be a replication of the unavailable shard, such as may be the case if the shard includes original data of the archive(s). The new shard may be selected from a set of potential shards as generated by, e.g., a generator matrix associated with the redundancy code, so as to differ in content from the unavailable shard (such as may be the case if the unavailable shard was a shard generated from the redundancy code, and therefore contains no original data of the archives). In such cases, an entirely new volume may be generated, rather than a shard.

<FIG> schematically illustrates an environment in which original data of archives may be stored on a data storage system implementing a redundancy code. One or more client entities <NUM>, such as those under control of a customer of a computing resource service provider, submit archive(s) <NUM> to a data storage system <NUM> for storage. The client entities <NUM> may be any entity capable of transacting data with a data storage system, such as over a network (including the Internet). Examples include physical computing systems (e.g., servers, desktop computers, laptop computers, thin clients, and handheld devices such as smartphones and tablets), virtual computing systems (e.g., as may be provided by the computing resource service provider using one or more resources associated therewith), services (e.g., such as those connecting to the data storage system <NUM> via application programming interface calls, web service calls, or other programmatic methods), and the like.

The data storage system <NUM> may be any computing resource or collection of such resources capable of processing data for storage, and interfacing with one or more resources to cause the storage of the processed data. Examples include physical computing systems (e.g., servers, desktop computers, laptop computers, thin clients, and handheld devices such as smartphones and tablets), virtual computing systems (e.g., as may be provided by the computing resource service provider using one or more resources associated therewith), services (e.g., such as those connecting to the data storage system <NUM> via application programming interface calls, web service calls, or other programmatic methods), and the like. The resources of the data storage system <NUM>, as well as the data storage system <NUM> itself, may be one or more resources of a computing resource service provider, such as that described in further detail below. The data storage system <NUM> and/or the computing resource service provider provides one or more archival storage services and/or data storage services, such as those described in further below, through which the client entities <NUM> may transact data such as the archives <NUM>.

The archives <NUM> may include any quantity of data in any format. For example, the archives <NUM> may be single files, or may include several files. The archives <NUM> may be encrypted by, e.g., the client device(s) <NUM>, or may be encrypted by a component of the data storage system <NUM> after receipt of the archives <NUM>, such as on the request of a customer of the data storage system <NUM> and/or the computing resource service provider.

The data storage system <NUM> may sort the archives <NUM> according to one or more criteria (and in the case where a plurality of criteria is used for the sort, such criteria may be sorted against sequentially and in any order appropriate for the implementation). Such criteria may be attributes common to some or all of the archives, and may include the identity of the customer, the time of upload (e.g., by the client device <NUM>) and/or receipt (by the data storage system <NUM>), archive size, expected volume and/or shard boundaries relative to the boundaries of the archives (e.g., so as to minimize the number of archives breaking across shards and/or volumes), and the like. As mentioned, such sorting may be performed so as to minimize the number of volumes on which any given archive is stored. Such techniques may be used, e.g., to optimize storage where the overhead of retrieving data from multiple volumes is greater than the benefit of parallelizing the retrieval from the multiple volumes. Information regarding the sort order may be persisted, e.g., by the data storage system <NUM>, for use in techniques described in further detail herein.

As previously discussed, one or more indices may be generated in connection with, e.g., the order in which the archives are to be stored, as determined in connection with the sorting mentioned immediately above. The index may be a single index or may be a multipart index, and may be of any appropriate architecture and may be generated according to any appropriate method. For example, the index may be a bitmap index, dense index, sparse index, or a reverse index. Where multiple indices are used, different types of indices may be implemented according to the properties of, e.g., the archives <NUM> to be stored via the data storage system <NUM>. For example, a data storage system <NUM> may generate a dense index for archives over a specified size (as the size of the index itself may be small relative to the number of archives stored on a given volume), and may also generate a sparse index for archives under that specified size (as the ratio of index size to archive size increases).

The data storage system <NUM> is connected to or includes one or more volumes <NUM> on which the archives <NUM>, and the generated indices, are stored. The volumes <NUM> may be any container, whether logical or physical, capable of storing or addressing data stored therein. The volumes <NUM> may map on a one-to-one basis with the data storage devices on which they reside (and may actually be the data storage devices themselves). The size and/or quantity of the volumes <NUM> may be independent of the capacity of the data storage devices on which they reside (e.g., a set of volumes may each be of a fixed size such that a second set of volumes may reside on the same data storage devices as the first set). The data storage devices may include any resource or collection of resources, such as those of a computing resource service provider, that are capable of storing data, and may be physical, virtual, or some combination of the two.

As previously described, one or more indices may be generated for each volume <NUM> of the plurality, and may reflect the archives stored on the respective volume <NUM> to which it applies. Where sparse indices are used, a sparse index for a given volume may point to a subset of archives <NUM> stored or to be stored on that volume <NUM>, such as those archives <NUM> which may be determined to be stored on the volume <NUM> based on the sort techniques mentioned previously. The subset of volumes to be indexed in the sparse index may be selected on any appropriate basis and for any appropriate interval. For example, the sparse index may identify the archives to be located at every x blocks or bytes of the volume (e.g., independently of the boundaries and/or quantity of the archives themselves). As another example, the sparse index may identify every nth archive to be stored on the volume <NUM>. As may be contemplated, the indices (whether sparse or otherwise), may be determined prior to actually storing the archives on the respective volumes. A space may be reserved on the volumes so as to generate and/or write the appropriate indices after the archives <NUM> have been written to the volumes <NUM>.

The sparse indexes are used in connection with information relating to the sort order of the archives so as to locate archives without necessitating the use of dense indexes, e.g., those that account for every archive <NUM> on a given volume <NUM>. Such sort order-related information may reside on the volume(s) <NUM> or on an entity separate from the volume(s) <NUM>, such as in a data store or other resource of a computing resource service provider. Similarly, the indexes may be stored on the same volume(s) <NUM> to which they apply, or separately from such volume(s) <NUM>.

As mentioned, the archives <NUM> are stored, bit for bit (e.g., the "original data" of the archives), on a subset of the plurality of volumes <NUM>. Also as mentioned, appropriate indices may also be stored on the applicable subset of the plurality of volumes <NUM>. The original data of the archives is stored as a plurality of shards across a plurality of volumes, the quantity of which (either shards or volumes, which in some cases may have a one to one relationship) may be predetermined according to various factors, including the number of total shards necessary to reconstruct the original data using a redundancy code. The number of volumes used to store the original data of the archives is the quantity of shards necessary to reconstruct the original data from a plurality of shards generated by a redundancy code from the original data. As an example, <FIG> illustrates five volumes, three of which contain original data <NUM> and two of which contain derived data <NUM>, such as redundancy coded data. In the illustrated example, the redundancy code used may require any three shards to regenerate original data, and therefore, a quantity of three volumes may be used to write the original data (even prior to any application of the redundancy code).

The volumes <NUM> bearing the original data <NUM> may each contain or be considered as shards unto themselves. Where the sort order-related information and/or the indexes are stored on the applicable volumes <NUM>, they may be included with the original data of the archives and stored therewith as shards, as previously mentioned. In the illustrated example, the original data <NUM> is stored as three shards (which may include the respective indices) on three associated volumes <NUM>. The original data <NUM> (and where the indices are stored on the volumes, the indices) is processed by an entity associated with, e.g., the archival storage service, using a redundancy code, such as an erasure code, so as to generate the remaining shards, which contain encoded information rather than the original data of the archives. The original data <NUM> may be processed using the redundancy code at any time after being sorted, such as prior to being stored on the volumes, contemporaneously with such storage, or after such storage.

Such encoded information may be any mathematically computed information derived from the original data, and depends on the specific redundancy code applied. As mentioned, the redundancy code may include erasure codes (such as online codes, Luby transform codes, raptor codes, parity codes, Reed-Solomon codes, Cauchy codes, Erasure Resilient Systematic Codes, regenerating codes, or maximum distance separable codes) or other forward error correction codes. The redundancy code may implement a generator matrix that implements mathematical functions to generate multiple encoded objects correlated with the original data to which the redundancy code is applied. An identity matrix may be used, wherein no mathematical functions are applied and the original data (and, if applicable, the indexes) are allowed to pass straight through. It may be therefore contemplated that the volumes bearing the original data (and the indexes) may correspond to objects encoded from that original data by the identity matrix rows of the generator matrix of the applied redundancy code, while volumes bearing derived data correspond to other rows of the generator matrix. In the example illustrated in <FIG>, the five volumes <NUM> include three volumes that have shards corresponding to the original data of the archives <NUM>, while two have shards corresponding to the derived data <NUM>. In this example, the applied redundancy code may result in the data being stored in a <NUM>:<NUM> scheme, wherein any three shards of the five stored shards are required to regenerate the original data, regardless of whether the selected three shards contain the original data or the derived data.

If one of the volumes <NUM> or a shard stored thereon is detected as corrupt, missing, or otherwise unavailable, a new shard may be generated using the redundancy code applied to generate the shard(s) in the first instance. The new shard may be stored on the same volume or a different volume, depending, for example, on whether the shard is unavailable for a reason other than the failure of the volume. The new shard may be generated by, e.g., the data storage system <NUM>, by using a quantity of the remaining shards necessary to regenerate the original data (and the index, if applicable) stored across all volumes, regenerating that original data, and either replacing the portion of the original data corresponding to that which was unavailable (in the case that the unavailable shard contains original data), or reapplying the redundancy code so as to provide derived data for the new shard.

As previously discussed, the new shard may be a replication of the unavailable shard, such as may be the case if the unavailable shard includes original data of the archive(s). The new shard may be selected from a set of potential shards as generated by, e.g., a generator matrix associated with the redundancy code, so as to differ in content from the unavailable shard (such as may be the case if the unavailable shard was a shard generated from the redundancy code, and therefore contains no original data of the archives).

Retrieval of an archive stored in accordance with the techniques described herein may be requested by an entity, such as a client entity <NUM> under control of a customer of the computing resource service provider and/or the archival storage service provided therefrom, as described in further detail throughout this disclosure. In response to the request, the data storage system <NUM> may locate, based on information regarding the sort order of the archives <NUM> as stored on the volumes <NUM>, the specific volume <NUM> on which the archive <NUM> is located. Thereafter, the index or indices may be used to locate the specific archive, whereupon it is read from the volume and provided to the requesting client entity <NUM>. Where sparse indexes are employed, the sort order information may be used to locate the nearest location (or archive) that is sequentially prior to the requested archive, whereupon the volume is sequentially read from that location or archive until the requested archive is found. Where multiple types of indices are employed, the data storage system <NUM> may initially determine which of the indices includes the most efficient location information for the request archive based on assessing the criteria used to deploy the multiple types of indices in the first instance. For example, if archives under a specific size are indexed in a sparse index and archives equal to or over that size are indexed in a parallel dense index, the data storage system <NUM> may first determine the size of the requested archive, and if the requested archive is larger than or equal to the aforementioned size boundary, the dense index may be used so as to more quickly obtain the precise location of the requested archive.

<FIG> schematically illustrates various workflows for storing original data of archives on a plurality of data stores of a data storage system. A data storage system <NUM>, which may be similar to the data storage system <NUM> described above in connection with <FIG>, includes or is connected to a plurality of volumes <NUM>, which may be similar to the volumes <NUM>, also described above in connection with <FIG>. Archives <NUM>, such as those received from client entities <NUM> described in connection with <FIG>, are processed by the data storage system <NUM> according to the techniques described in further detail herein.

As previously discussed, the data storage system <NUM> may sort the archives <NUM> according to one or more criteria (and in the case where a plurality of criteria is used for the sort, such criteria may be sorted against sequentially and in any order appropriate for the implementation). Such criteria may be attributes common to some or all of the archives, and may include the identity of the customer, abstractions defined by the customer (e.g., larger data objects associated with multiple archives of the same customer), the time of upload and/or receipt, archive size, expected volume and/or shard boundaries relative to the boundaries of the archives (e.g., so as to minimize the number of archives breaking across shards and/or volumes), unique identifiers of the archives themselves, and the like. As previously mentioned, such sorting may be performed so as to minimize the number of volumes on which any given archive is stored. For example, larger archives may be sorted based on expected volume size, such that larger archives are stored earlier in the volume and increasingly smaller archives are stored later in the volume. Such techniques may be used, e.g., to optimize storage where the overhead of retrieving data from multiple volumes is greater than the benefit of parallelizing the retrieval from the multiple volumes. For example, devices using removable media may incur significant latency penalties when the media are physically changed, and the sort order may concatenate and apportion archives so as to minimize the number of removable media necessary for the retrieval of the archives. As previously mentioned, information regarding the sort order may be persisted, e.g., by the data storage system <NUM>, for use in techniques described in further detail herein.

The data storage system <NUM> may sort the archives <NUM> two or more times, at least one of which may correspond to the various characteristics of the data storage system <NUM> and/or the volume <NUM> itself. For example, a first sort may, incident to actual storage of the archives <NUM> on one or more volumes <NUM>, sort the archives according to boundaries, storage space, and other volume characteristics, so as to optimize the storage of the archives <NUM>, and a second sort may re-sort the ones destined for each of the volumes <NUM>, influencing the actual storage within the volumes <NUM>. In this example, either or both sorts may include one or more of the criteria delineated above.

As previously described (e.g., in connection with <FIG>), one or more indices, of one or more types may be generated for each volume <NUM> of the plurality, and may reflect the archives stored on the respective volume <NUM> to which it applies. The indexes are used in connection with information relating to the sort order of the archives <NUM> so as to locate archives without necessitating the use of dense indexes, e.g., those that account for every archive <NUM> on a given volume <NUM>. Such sort order-related information may reside on the volume(s) <NUM> or on an entity separate from the volume(s) <NUM>, such as in a data store or other resource of a computing resource service provider. Similarly, the indexes may be stored on the same volume(s) <NUM> to which they apply, or separately from such volume(s) <NUM>.

As mentioned, the original data <NUM> of archives <NUM> are stored on a subset of the plurality of volumes <NUM>, and the quantity of the subset of volumes may be equal to the minimum number of shards required by the redundancy code to regenerate the original data. Also as mentioned, appropriate indices may also be stored on the applicable subset of the plurality of volumes <NUM>, in connection with the original data <NUM> of the stored archives <NUM>. The original data of the archives is stored as a plurality of shards across a plurality of volumes, the quantity of which (either shards or volumes, which in some cases may have a one to one relationship) may be predetermined according to various factors, including the number of total shards necessary to reconstruct the original data using a redundancy code. As an example, <FIG> illustrates five volumes, three of which contain original data <NUM> of stored archives <NUM> (corresponding to the incoming archives <NUM>), and two of which contain data <NUM> derived from mathematical functions of the applied redundancy code. In the illustrated example, the redundancy code used may require any three shards to regenerate original data, and therefore, a quantity of three volumes may be used to write the original data (prior to any application of the redundancy code).

Similarly to previously discussed, the volumes <NUM> storing the original data <NUM> of the stored archives <NUM> are processed, at a volume level, by an entity associated with, e.g., the archival storage service, using a redundancy code, such as an erasure code, so as to generate the remaining shards <NUM>, which contain encoded information rather than the original data of the archives. As previously mentioned, the original data <NUM> may be processed using the redundancy code at any time after being sorted, such as prior to being stored on the volumes, contemporaneously with such storage, or after such storage. As illustrated by the shaded archive <NUM>, a given archive may, in certain cases, break between two (or possibly more) volumes <NUM>, due to size, placement, and the like. Where the redundancy code is applied at a volume level (e.g., the entirety of the contents of the volumes bearing the original data of the archives being considered as a single data object to be processed by the redundancy code), failure of one of the two volumes (or shards) on which the original data of the illustrated archive <NUM> resides may not necessitate rebuilding of both volumes, but only the volume that is unavailable.

The encoded information <NUM> may be any mathematically computed information derived from the original data <NUM>, and depends on the specific redundancy code applied. The redundancy code may implement a generator matrix that implements mathematical functions to generate multiple encoded objects correlated with the original data to which the redundancy code is applied. An identity matrix may be used, wherein no mathematical functions are applied and the original data (and, if applicable, the indexes) are allowed to pass straight through. It may be therefore contemplated that the volumes bearing the original data (and the indexes) <NUM> may correspond to objects encoded from that original data by the identity matrix rows of the generator matrix of the applied redundancy code, while volumes bearing derived data <NUM> correspond to other rows of the generator matrix.

Similarly to previously discussed, if one of the volumes <NUM> or a shard stored thereon is detected as corrupt, missing, or otherwise unavailable, a new shard may be generated using the redundancy code applied to generate the shard(s) in the first instance. The new shard may be stored on the same volume or a different volume, depending, for example, on whether the shard is unavailable for a reason other than the failure of the volume. The new shard may be generated by, e.g., the data storage system <NUM>, by using a quantity of the remaining shards necessary to regenerate the original data (and the index, if applicable) stored across all volumes, regenerating that original data, and either replacing the portion of the original data corresponding to that which was unavailable (in the case that the unavailable shard contains original data), or reapplying the redundancy code so as to provide derived data for the new shard.

<FIG> schematically illustrates various workflows for indexing and locating data stored on a data storage system. A representative volume <NUM>, which is similar to the volumes described above in connection with <FIG> and <FIG>, stores a plurality of archives <NUM>, including the original data <NUM> as, e.g., received from a customer, such as that of a data storage system or other resource and/or service of a computing resource service provider to which the data storage system is attached. The archives <NUM> may have been sorted in connection with one of the techniques described above in connection with <FIG> and <FIG>, and information regarding the sort order may be persisted by, e.g., a resource directly or indirectly connected with the volume <NUM>. The volume <NUM> may reside on (or consist of) one or more storage devices that are optimized for sequential data access, relative to random data access.

As previously discussed, one or more indices <NUM> may be generated in connection with, e.g., the order in which the archives are to be stored, as determined in connection with the sorting mentioned previously. The index may be a single index or may be a multipart index, and may be of any appropriate architecture and may be generated according to any appropriate method. For example, the index may be a bitmap index, dense index, sparse index, or a reverse index. Where multiple indices are used, different types of indices may be implemented according to the properties of, e.g., the archives <NUM> to be stored in the volume <NUM>. For example, the volume <NUM> may utilize a dense index for archives over a specified size (as the size of the index itself may be small relative to the number of archives stored on a given volume), and may also generate a sparse index for archives under that specified size (as the ratio of index size to archive size increases).

According to the present invention, sparse indices are used, and a sparse index <NUM> for a given volume points to subindexes <NUM>, which in turn mark representative locations on the volume. The subindexes <NUM> may be an abstraction that points to data that resides at a predetermined interval. The subindexes <NUM> may be additional data or metadata that is stored in connection with (or directly upon) the volume, and at a predetermined interval. It may be contemplated that the subindexes <NUM> may be stored as part of the shard on the volume, in a similar fashion as described in connection with <FIG> and <FIG> above for the index and the original data of the archives.

The predetermined interval may be in blocks, bytes, or other units of data. For example, the subindexes may identify the archives to be located at every x blocks or bytes of the volume (e.g., independently of the boundaries and/or quantity of the archives themselves). The predetermined interval may be delinated by number of volumes. For example, the subindex may point to every nth archive to be stored on the volume <NUM>. As may contemplated, the sparse index <NUM> (and the subindexes <NUM>) may be generated and/or written at a time before the storage of the archives <NUM>, contemporaneously with such storage, or after such storage. The sparse index <NUM> and the subindexes <NUM> may be stored in a reserved space on the volume, e.g., after the archives <NUM> have been stored.

The sparse index <NUM> is used in connection with information relating to the predetermined sort order of the archives <NUM> so as to locate specific archives. As previously mentioned, such sort order-related information may reside on the volume(s) <NUM> or on an entity separate from the volume(s) <NUM>, such as in a data store or other resource of a computing resource service provider. An entity requesting a given archive stored on the volume <NUM> may determine, based on the sort order-related information and by reading the index <NUM>, the nearest subindex that is sequentially prior to the requested archive on the volume <NUM>. The requesting entity may then cause the volume <NUM> to be sequentially read from the location of that subindex <NUM> until the requested archive is located and fully read.

Where multiple types of indices are employed, the requesting entity may initially determine which of the indices includes the most efficient location information for the requested archive based on assessing the criteria used to deploy the multiple types of indices in the first instance. For example, if archives under a specific size are indexed in a sparse index and archives equal to or over that size are indexed in a parallel dense index, the requesting entity may first determine the size of the requested archive, and if the requested archive is larger than or equal to the aforementioned size boundary, may use the dense index in favor of the sparse index as to more quickly obtain the precise location of the requested archive.

<FIG> schematically illustrates an example process for processing, indexing, storing, and retrieving data stored on a data storage system. At step <NUM>, a resource of a data storage system, such as that implementing a redundancy code to store archives, determines which subset (e.g., quantity) of a plurality of volumes is necessary, based on, e.g., a redundancy code to be applied to the archives, to recreate the original data to be stored. For example, in accordance with the techniques described above in connection with at least <FIG> and <FIG>. , such information may be derived from predetermining the parameters of an erasure code with a specified ratio of shards necessary to regenerate the original data from which they derive to the total number of shards generated from the application of the erasure code.

At step <NUM>, original data, such as original data of archives received from customers of, e.g., a data storage system or a computing resource service provider as described in further detail above in connection with <FIG> and <FIG>, is sorted by, e.g., the data storage system or associated entity. For example, as previously described, the sort order may be implemented on one or more attributes of the incoming data.

At step <NUM>, one or more sparse indices are generated by, e.g., the data storage system, for the original data. As previously discussed in connection with at least <FIG>, there may be more than one index for a given volume, and such parallel indices may be of different types depending on the nature of the archives and/or original data being stored.

At step <NUM>, the original data is stored, e.g., by the data storage system, on the subset of volumes determined in connection with step <NUM>, and in the order determined in step <NUM>. Additionally, at step <NUM>, the index generated in step <NUM> is stored, e.g., by the data storage system, on an appropriate entity. As previously discussed, the index may be stored as part of a shard on which the original data is stored, or may be stored on a separate resource from that which persists the volume.

At step <NUM>, the redundancy code is applied, e.g., by the data storage system, to the determined subset of volumes (e.g., shards, as previously discussed in connection with <FIG>), and additional shards containing data derived from the application of the redundancy code are stored on a predetermined quantity of volumes outside the subset determined in connection with step <NUM>. For example, as previously discussed, the ratio of volumes (e.g., shards) storing the original data to the overall quantity of volumes (including those storing the derived data generated in this step <NUM>) may be prescribed by the recovery/encoding ratio of the redundancy code applied herein.

At step <NUM>, in normal operation, requested data may be retrieved, e.g., by the data storage system, directly from the subset of volumes storing the original data, without necessitating retrieval and further processing (e.g., by the redundancy code) from the volumes storing the derived data generated in step <NUM>. However, at step <NUM>, if any of the volumes are determined, e.g., by the data storage system, to be unavailable, a replacement shard may be generated by the data storage system by reconstructing the original data from a quorum of the remaining shards, and re-encoding using the redundancy code to generate the replacement shard. As previously discussed in connection with <FIG>, the replacement shard may be the same or different from the shard detected as unavailable.

<FIG> schematically illustrates an example process for indexing original data stored on a redundancy coded data storage system. At step <NUM>, similarly to step <NUM> of process <NUM> described in connection with <FIG>, original data is processed by, e.g., a data storage system, to determine the order of storage of archives containing the original data on a volume. Information regarding the sort order may be persisted on, e.g., the volume, or a separate entity from the volume, as discussed above in connection with <FIG>.

At step <NUM>, one or more indices, such as sparse indices, are generated by, e.g., the data storage system, and point to subindexes that identify predetermined locations on the volume. The locations may be predetermined based on the parameters of the specific implementation, such as the size of the volume, the speed of reading and/or writing the volume (e.g., sequentially), the number of archives per volume, and the like. As previously discussed, the subindexes may be abstractions, or may be data or metadata elements stored on or in connection with the volume.

At step <NUM>, the original data sorted in step <NUM> is stored by the data storage system on the volume, with subindexes associated with, pointing to, or stored at predetermined locations mentioned in step <NUM>. The index generated in step <NUM> is stored, at step <NUM>, by the data storage system on a resource associated with volume, or on the volume itself, according to the techniques described above in connection with at least <FIG>.

At step <NUM>, a request, such as from a client entity or other entity connected to the data storage system and/or the volume, for a subset of the original data stored on the volume, is received by the volume or the data storage system associated with the volume. The data storage system and/or the requesting entity may, as previously discussed, have access to information regarding the sort order of the original data as determined in step <NUM>, and, utilizing sparse indexes, may use the index to locate an appropriate subindex at step <NUM>. As previously discussed, the appropriate subindex is the nearest location, marked by the subindex, that is sequentially prior to the requested subset of original data as stored on the volume. Once the subindex is determined in step <NUM>, at step <NUM>, the volume is sequentially read (e.g., by the data storage system or the storage device on which the volume is implemented) from the location denoted by the appropriate subindex, until the requested subset of original data is located and retrieved.

<FIG> shows an example of a customer connected to a computing resource service provider. The computing resource service provider <NUM> may provide a variety of services to the customer <NUM> and the customer <NUM> may communicate with the computing resource service provider <NUM> via an interface <NUM>, which may be a web services interface or any other type of customer interface. While <FIG> shows one interface <NUM> for the services of the computing resource service provider <NUM>, each service may have its own interface and, generally, subsets of the services may have corresponding interfaces in addition to or as an alternative to the interface <NUM>. The customer <NUM> may be an organization that may utilize one or more of the services provided by the computing resource service provider <NUM> to maintain and deliver information to its employees, which may be located in various geographical locations. Additionally, the customer <NUM> may be an individual that utilizes the services of the computing resource service provider <NUM> to deliver content to a working group located remotely. As shown in <FIG>, the customer <NUM> may communicate with the computing resource service provider <NUM> through a network <NUM>, whereby the network <NUM> may be a communication network, such as the Internet, an intranet or an Internet service provider (ISP) network. Some communications from the customer <NUM> to the computing resource service provider <NUM> may cause the computing resource service provider <NUM> to operate in accordance with one or more examples described or a variation thereof.

The computing resource service provider <NUM> may provide various computing resource services to its customers. The services provided by the computing resource service provider <NUM>, in this example, include a virtual computer system service <NUM>, a block-level data storage service <NUM>, a cryptography service <NUM>, an on-demand data storage service <NUM>, a notification service <NUM>, an authentication system <NUM>, a policy management service <NUM>, a task service <NUM> and one or more other services <NUM>. It is noted that not all examples described include the services <NUM>-<NUM> described with reference to <FIG> and additional services may be provided in addition to or as an alternative to services explicitly described. As described, each of the services <NUM>-<NUM> may include one or more web service interfaces that enable the customer <NUM> to submit appropriately configured API calls to the various services through web service requests. In addition, each of the services may include one or more service interfaces that enable the services to access each other (e.g., to enable a virtual computer system of the virtual computer system service <NUM> to store data in or retrieve data from the on-demand data storage service <NUM> and/or to access one or more block-level data storage devices provided by the block level data storage service <NUM>).

The virtual computer system service <NUM> may be a collection of computing resources configured to instantiate virtual machine instances on behalf of the customer <NUM>. The customer <NUM> may interact with the virtual computer system service <NUM> (via appropriately configured and authenticated API calls) to provision and operate virtual computer systems that are instantiated on physical computing devices hosted and operated by the computing resource service provider <NUM>. The virtual computer systems may be used for various purposes, such as to operate as servers supporting a website, to operate business applications or, generally, to serve as computing power for the customer. Other applications for the virtual computer systems may be to support database applications, electronic commerce applications, business applications, and/or other applications. Although the virtual computer system service <NUM> is shown in <FIG>, any other computer system or computer system service may be utilized in the computing resource service provider <NUM>, such as a computer system or computer system service that does not employ virtualization or instantiation and instead provisions computing resources on dedicated or shared computers/servers and/or other physical devices.

The block-level data storage service <NUM> may comprise one or more computing resources that collectively operate to store data for a customer <NUM> using block-level storage devices (and/or virtualizations thereof). The block-level storage devices of the block-level data storage service <NUM> may, for instance, be operationally attached to virtual computer systems provided by the virtual computer system service <NUM> to serve as logical units (e.g., virtual drives) for the computer systems. A block-level storage device may enable the persistent storage of data used/generated by a corresponding virtual computer system where the virtual computer system service <NUM> may only provide ephemeral data storage.

The computing resource service provider <NUM> also includes a cryptography service <NUM>. The cryptography service <NUM> may utilize one or more storage services of the computing resource service provider <NUM> to store keys of the customers in encrypted form, whereby the keys may be usable to decrypt customer <NUM> keys accessible only to particular devices of the cryptography service <NUM>.

The computing resource service provider <NUM> further includes an on-demand data storage service <NUM>. The on-demand data storage service <NUM> may be a collection of computing resources configured to synchronously process requests to store and/or access data. The on-demand data storage service <NUM> may operate using computing resources (e.g., databases) that enable the on-demand data storage service <NUM> to locate and retrieve data quickly, to allow data to be provided in responses to requests for the data. For example, the on-demand data storage service <NUM> may maintain stored data in a manner such that, when a request for a data object is retrieved, the data object can be provided (or streaming of the data object can be initiated) in a response to the request. As noted, data stored in the on-demand data storage service <NUM> may be organized into data objects. The data objects may have arbitrary sizes except, perhaps, for certain constraints on size. Thus, the on-demand data storage service <NUM> may store numerous data objects of varying sizes. The on-demand data storage service <NUM> may operate as a key value store that associates data objects with identifiers of the data objects that may be used by the customer <NUM> to retrieve or perform other operations in connection with the data objects stored by the on-demand data storage service <NUM>.

In the environment illustrated in <FIG>, a notification service <NUM> is included. The notification service <NUM> may comprise a collection of computing resources collectively configured to provide a web service or other interface and browser-based management console. The management console can be used to configure topics for which customers seek to receive notifications, configure applications (or people), subscribe clients to the topics, publish messages, or configure delivery of the messages over clients' protocol of choice (i.e., hypertext transfer protocol (HTTP), e-mail and short message service (SMS), among others). The notification service <NUM> may provide notifications to clients using a "push" mechanism without the need to check periodically or "poll" for new information and updates. The notification service <NUM> may further be used for various purposes such as monitoring applications executing in the virtual computer system service <NUM>, workflow systems, time-sensitive information updates, mobile applications, and many others.

As illustrated in <FIG>, the computing resource service provider <NUM> includes an authentication system <NUM> and a policy management service <NUM>. The authentication system <NUM> is a computer system (i.e., collection of computing resources) configured to perform operations involved in authentication of users of the customer. For instance, one of the services <NUM>-<NUM> and <NUM>-<NUM> may provide information from a user to the authentication system <NUM> to receive information in return that indicates whether the user requests are authentic.

The policy management service <NUM> is a computer system configured to manage policies on behalf of customers (such as customer <NUM>) of the computing resource service provider <NUM>. The policy management service <NUM> may include an interface that enables customers to submit requests related to the management of policy. Such requests may, for instance, be requests to add, delete, change, or otherwise modify policy for a customer or for other administrative actions, such as providing an inventory of existing policies and the like.

The computing resource service provider <NUM> is also equipped with a task service <NUM>. The task service <NUM> is configured to receive a task package from the customer <NUM> and enable executing tasks as dictated by the task package. The task service <NUM> may be configured to use any resource of the computing resource service provider <NUM>, such as one or more instantiated virtual machines or virtual hosts, for executing the task. The task service <NUM> may configure the one or more instantiated virtual machines or virtual hosts to operate using a selected operating system and/or a selected execution application in accordance with a requirement of the customer <NUM>.

The computing resource service provider <NUM> additionally maintains one or more other services <NUM> based at least in part on the needs of its customers <NUM>. For instance, the computing resource service provider <NUM> may maintain a database service for its customers <NUM>. A database service may be a collection of computing resources that collectively operate to run one or more databases for one or more customers <NUM>. The customer <NUM> may operate and manage a database from the database service by utilizing appropriately configured API calls. This, in turn, may allow a customer <NUM> to maintain and potentially scale the operations in the database. Other services include, but are not limited to, object-level archival data storage services, services that manage and/or monitor other services.

The computing resource service provider <NUM> further includes an archival storage service <NUM>. The archival storage service <NUM> may comprise a collection of computing resources that collectively operate to provide storage for data archiving and backup of customer data. The data may comprise one or more data files that may be combined to form an archive. The archival storage service <NUM> may be configured to persistently store data that may be infrequently accessed and for which long retrieval times are acceptable to a customer utilizing the archival storage service <NUM>. A customer may interact with the archival storage service <NUM> (for example, through appropriately configured API calls made to the archival storage service <NUM>) to generate one or more archives, upload and retrieve the one or more archives or monitor the generation, upload or retrieval of the one or more archives.

<FIG> shows an illustrative example of a data storage service. The data storage service <NUM> may be a service of a computing resource provider used to operate an on-demand data storage service such as described above in connection with <FIG>. As illustrated in <FIG>, the data storage service <NUM> includes various subsystems such as a request processing subsystem <NUM> and a management subsystem <NUM>. The data storage service <NUM> may also include a plurality of data storage servers <NUM> and a metadata storage <NUM>, which may store metadata about various data objects stored among the data storage servers <NUM> as described. The request processing subsystem <NUM> is a collection of computing resources, such as webservers and application servers, collectively configured to process requests submitted to the data storage service <NUM>. The request processing subsystem <NUM>, for example, may include one or more webservers that provide a web service interface to enable customers of the data storage service <NUM> to submit requests to be processed by the data storage service <NUM>. The request processing subsystem <NUM> may include computers systems configured to make various determinations in connection with the processing of requests, such as whether policy allows fulfillment of a request, whether requests are authentic (e.g., electronically signed using a suitable cryptographic key) and otherwise.

Components of the request processing subsystem may interact with other components of the data storage service <NUM> (e.g., through network communications). For example, some requests submitted to the request processing subsystem <NUM> may involve the management of computing resources which may include data objects stored by the data storage servers <NUM>. The request processing subsystem <NUM>, for example, may receive and process requests to modify computing resources. For instance, in some examples, data objects are logically organized into logical data containers. Data objects associated with a logical data container may, for example, be said to be in the logical data container. Requests to the data processing subsystem <NUM> may include requests for creating logical data containers, deleting logical data containers, providing an inventory of a logical data container, providing or updating access control policy with respect to one or more logical data containers and the like.

The requests may be processed by the management subsystem <NUM> upon receipt by the request processing subsystem <NUM>. If applicable, various requests processed by the request processing subsystem <NUM> and/or management subsystem <NUM>, may result in the management subsystem <NUM> updating metadata associated with data objects and logical data containers stored in the metadata store <NUM>. Other requests that may be processed by the request processing subsystem <NUM> include requests to perform operations in connection with data objects. The requests, for example, may include requests to upload data objects to the data storage service <NUM>, to download data objects from the data storage service <NUM>, to delete data objects stored by the data storage service <NUM> and/or other operations that may be performed.

Requests processed by the request processing subsystem <NUM> that involve operations on data objects (upload, download, delete, e.g.) may include interaction between the request processing subsystem <NUM> and one or more data storage servers <NUM>. The data storage servers <NUM> may be computer system communicatively coupled with one or more storage devices for the persistent of data objects. For example, in order to process a request to upload a data object, the request processing subsystem may transmit data to a data storage server <NUM> for persistent storage. It is noted, however, that client (e.g., customer) computer systems may transmit data directly to the data storage servers <NUM> instead of through severs in the request processing subsystem.

The request processing subsystem <NUM> transmits data to multiple data storage servers <NUM> for the purposes of redundantly storing the data to allow the retrievability of data in the event of failure of an individual data storage server <NUM> and/or associated data storage device. For example, the request processing subsystem uses a redundancy in coding scheme such as erasure coding to deconstruct a data object into multiple parts that are stored among the data storage servers <NUM>. The parts may be configured such that if access to a certain number of parts is lost, the data object may nevertheless be reconstructible from the remaining parts that remain accessible.

To enable efficient transfer of data between the request processing subsystem <NUM> and the data storage servers <NUM> and/or generally to enable quick processing of requests, the request processing subsystem <NUM> may include one or more databases that enable the location of data among the data storage servers <NUM>. For example, the request processing subsystem <NUM> may operate a key value store that serves to associate identifiers of data objects with locations among the data storage servers <NUM> for accessing data of the data objects.

<FIG> illustrates aspects of an example environment <NUM> for implementing aspects. As will be appreciated, although a web-based environment is used for purposes of explanation, different environments may be used, as appropriate, to implement various aspects. The environment includes an electronic client device <NUM>, which can include any appropriate device operable to send and/or receive requests, messages or information over an appropriate network <NUM> and convey information back to a user of the device. Examples of such client devices include personal computers, cell phones, handheld messaging devices, laptop computers, tablet computers, set-top boxes, personal data assistants, embedded computer systems, electronic book readers and the like. The network can include any appropriate network, including an intranet, the Internet, a cellular network, a local area network, a satellite network or any other such network and/or combination thereof. Components used for such a system can depend at least in part upon the type of network and/or environment selected. Protocols and components for communicating via such a network are well known and will not be discussed herein in detail. Communication over the network can be enabled by wired or wireless connections and combinations thereof. In this example, the network includes the Internet, as the environment includes a web server <NUM> for receiving requests and serving content in response thereto, although for other networks an alternative device serving a similar purpose could be used as would be apparent to one of ordinary skill in the art.

The illustrative environment includes at least one application server <NUM> and a data store <NUM>. It should be understood that there can be several application servers, layers or other elements, processes or components, which may be chained or otherwise configured, which can interact to perform tasks such as obtaining data from an appropriate data store. Servers, as used herein, may be implemented in various ways, such as hardware devices or virtual computer systems. In some contexts, servers may refer to a programming module being executed on a computer system. As used herein, unless otherwise stated or clear from context, the term "data store" refers to any device or combination of devices capable of storing, accessing and retrieving data, which may include any combination and number of data servers, databases, data storage devices and data storage media, in any standard, distributed, virtual or clustered environment. The application server can include any appropriate hardware, software and firmware for integrating with the data store as needed to execute aspects of one or more applications for the client device, handling some or all of the data access and business logic for an application. The application server may provide access control services in cooperation with the data store and is able to generate content including, but not limited to, text, graphics, audio, video and/or other content usable to be provided to the user, which may be served to the user by the web server in the form of HyperText Markup Language ("HTML"), Extensible Markup Language ("XML"), JavaScript, Cascading Style Sheets ("CSS") or another appropriate client-side structured language. Content transferred to a client device may be processed by the client device to provide the content in one or more forms including, but not limited to, forms that are perceptible to the user audibly, visually and/or through other senses including touch, taste, and/or smell. The handling of all requests and responses, as well as the delivery of content between the client device <NUM> and the application server <NUM>, can be handled by the web server using PHP: Hypertext Preprocessor ("PHP"), Python, Ruby, Perl, Java, HTML, XML or another appropriate server-side structured language in this example. It should be understood that the web and application servers are not required and are merely example components, as structured code discussed herein can be executed on any appropriate device or host machine as discussed elsewhere herein. Further, operations described herein as being performed by a single device may, unless otherwise clear from context, be performed collectively by multiple devices, which may form a distributed and/or virtual system.

The data store <NUM> can include several separate data tables, databases, data documents, dynamic data storage schemes and/or other data storage mechanisms and media for storing data relating to a particular aspect of the present disclosure. For example, the data store illustrated may include mechanisms for storing production data <NUM> and user information <NUM>, which can be used to serve content for the production side. The data store also is shown to include a mechanism for storing log data <NUM>, which can be used for reporting, analysis or other such purposes. It should be understood that there can be many other aspects that may need to be stored in the data store, such as page image information and access rights information, which can be stored in any of the above listed mechanisms as appropriate or in additional mechanisms in the data store <NUM>. The data store <NUM> is operable, through logic associated therewith, to receive instructions from the application server <NUM> and obtain, update or otherwise process data in response thereto. The application server <NUM> may provide static, dynamic or a combination of static and dynamic data in response to the received instructions. Dynamic data, such as data used in web logs (blogs), shopping applications, news services and other such applications may be generated by server-side structured languages as described herein or may be provided by a content management system ("CMS") operating on, or under the control of, the application server. In one example, a user, through a device operated by the user, might submit a search request for a certain type of item. In this case, the data store might access the user information to verify the identity of the user and can access the catalog detail information to obtain information about items of that type. The information then can be returned to the user, such as in a results listing on a web page that the user is able to view via a browser on the user device <NUM>. Information for a particular item of interest can be viewed in a dedicated page or window of the browser. It should be noted, however, that the present disclosure is not necessarily limited to the context of web pages, but may be more generally applicable to processing requests in general, where the requests are not necessarily requests for content.

Each server typically will include an operating system that provides executable program instructions for the general administration and operation of that server and typically will include a computer-readable storage medium (e.g., a hard disk, random access memory, read only memory, etc.) storing instructions that, when executed by a processor of the server, allow the server to perform its intended functions. Suitable implementations for the operating system and general functionality of the servers are known or commercially available and are readily implemented by persons having ordinary skill in the art, particularly in light of the disclosure herein.

The environment may be a distributed and/or virtual computing environment utilizing several computer systems and components that are interconnected via communication links, using one or more computer networks or direct connections. However, it will be appreciated by those of ordinary skill in the art that such a system could operate equally well in a system having fewer or a greater number of components than are illustrated in <FIG>. Thus, the depiction of the system <NUM> in <FIG> should be taken as being illustrative in nature and not limiting to the scope of the disclosure.

The various aspects further can be implemented in a wide variety of operating environments, which in some cases can include one or more user computers, computing devices or processing devices which can be used to operate any of a number of applications. User or client devices can include any of a number of general purpose personal computers, such as desktop, laptop or tablet computers running a standard operating system, as well as cellular, wireless and handheld devices running mobile software and capable of supporting a number of networking and messaging protocols. Such a system also can include a number of workstations running any of a variety of commercially-available operating systems and other known applications for purposes such as development and database management. These devices also can include other electronic devices, such as dummy terminals, thin-clients, gaming systems and other devices capable of communicating via a network. These devices also can include virtual devices such as virtual machines, hypervisors and other virtual devices capable of communicating via a network.

Various aspects of the present disclosure utilize at least one network that would be familiar to those skilled in the art for supporting communications using any of a variety of commercially-available protocols, such as Transmission Control Protocol/Internet Protocol ("TCP/IP"), User Datagram Protocol ("UDP"), protocols operating in various layers of the Open System Interconnection ("OSI") model, File Transfer Protocol ("FTP"), Universal Plug and Play ("UpnP"), Network File System ("NFS"), Common Internet File System ("CIFS") and AppleTalk. The network can be, for example, a local area network, a wide-area network, a virtual private network, the Internet, an intranet, an extranet, a public switched telephone network, an infrared network, a wireless network, a satellite network and any combination thereof.

Where a web server is utilized, the web server can run any of a variety of server or mid-tier applications, including Hypertext Transfer Protocol ("HTTP") servers, FTP servers, Common Gateway Interface ("CGI") servers, data servers, Java servers, Apache servers and business application servers. The server(s) also may be capable of executing programs or scripts in response to requests from user devices, such as by executing one or more web applications that may be implemented as one or more scripts or programs written in any programming language, such as Java®, C, C# or C++, or any scripting language, such as Ruby, PHP, Perl, Python or TCL, as well as combinations thereof. The server(s) may also include database servers, including without limitation those commercially available from Oracle®, Microsoft®, Sybase® and IBM® as well as open-source servers such as MySQL, Postgres, SQLite, MongoDB, and any other server capable of storing, retrieving and accessing structured or unstructured data. Database servers may include table-based servers, document-based servers, unstructured servers, relational servers, non-relational servers or combinations of these and/or other database servers.

The environment can include a variety of data stores and other memory and storage media as discussed above. These can reside in a variety of locations, such as on a storage medium local to (and/or resident in) one or more of the computers or remote from any or all of the computers across the network. The information may reside in a storage-area network ("SAN") familiar to those skilled in the art. Similarly, any necessary files for performing the functions attributed to the computers, servers or other network devices may be stored locally and/or remotely, as appropriate. Where a system includes computerized devices, each such device can include hardware elements that may be electrically coupled via a bus, the elements including, for example, at least one central processing unit ("CPU" or "processor"), at least one input device (e.g., a mouse, keyboard, controller, touch screen or keypad) and at least one output device (e.g., a display device, printer or speaker). Such a system may also include one or more storage devices, such as disk drives, optical storage devices and solid-state storage devices such as random access memory ("RAM") or read-only memory ("ROM"), as well as removable media devices, memory cards, flash cards, etc..

Such devices also can include a computer-readable storage media reader, a communications device (e.g., a modem, a network card (wireless or wired), an infrared communication device, etc.) and working memory as described above. The computer-readable storage media reader can be connected with, or configured to receive, a computer-readable storage medium, representing remote, local, fixed and/or removable storage devices as well as storage media for temporarily and/or more permanently containing, storing, transmitting and retrieving computer-readable information. The system and various devices also typically will include a number of software applications, modules, services or other elements located within at least one working memory device, including an operating system and application programs, such as a client application or web browser. It should be appreciated that alternates may have numerous variations from that described above. For example, customized hardware might also be used and/or particular elements might be implemented in hardware, software (including portable software, such as applets) or both.

Claim 1:
A computer-implemented method, comprising:
processing a plurality of archives to be stored on a plurality of volumes so as to:
sort (<NUM>) the plurality of archives according to at least one criterion shared by the plurality of archives; and
determine which archives (<NUM>) of the sorted plurality of archives will be stored on each volume (<NUM>) of the plurality of volumes;
generating (<NUM>) one or more sparse indexes (<NUM>) for each of the plurality of volumes, each sparse index pointing to a subindex (<NUM>) that identifies a location on a corresponding volume;
storing (<NUM>, <NUM>) the sorted plurality of archives and the generated one or more sparse indexes on a subset of the plurality of volumes, thereby generating a plurality of shards, wherein the plurality of shards include the subindexes;
applying (<NUM>) a redundancy code to the sorted plurality of archives and the generated one or more sparse indexes to generate encoded shards; and
storing the encoded shards on corresponding volumes outside of the subset of the plurality of volumes.