Source: https://patents.justia.com/patent/10127105
Timestamp: 2019-04-23 14:32:30
Document Index: 389530624

Matched Legal Cases: ['art 1', 'art 2', 'art 3', 'art 4', 'art 1', 'art 1', 'art 2', 'art 2', 'art 3', 'art 3']

US Patent for Techniques for extending grids in data storage systems Patent (Patent # 10,127,105 issued November 13, 2018) - Justia Patents Search
Justia Patents Arrayed (e.g., Raids)US Patent for Techniques for extending grids in data storage systems Patent (Patent # 10,127,105)
Techniques for extending grids in data storage systems
One or more grids of redundancy coded shards, such as those stored or otherwise represented on grid encoded storage systems, are configured to be extensible. For example, a grid of shards may include data shards, derived shards (derived from the data shards), and null shard, indexed by, e.g., row and column. A grid of shards so configured may include data shards and derived shards in one set of columns of the grid, and the null shards in another set of columns of the grid. As additional data is added to the grid, the grid may be extended by converting some of the null shards into data or derived shards, on a row-by-row basis, and regenerating or re-deriving additional shards as necessary.
This application incorporates by reference for all purposes the full disclosure of co-pending U.S. patent application Ser. No. 14/741,409, filed Jun. 16, 2015, entitled “ADAPTIVE DATA LOSS MITIGATION FOR REDUNDANCY CODING SYSTEMS,” co-pending U.S. patent application Ser. No. 14/789,778, filed Jul. 1, 2015, entitled “INCREMENTAL MEDIA SIZE EXTENSION FOR GRID ENCODED DATA STORAGE SYSTEMS,” co-pending U.S. patent application Ser. No. 14/789,783, filed Jul. 1, 2015, entitled “GRID ENCODED DATA STORAGE SYSTEMS FOR EFFICIENT DATA REPAIR,” co-pending U.S. patent application Ser. No. 14/789,789, filed Jul. 1, 2015, entitled “CROSS-DATACENTER EXTENSION OF GRID ENCODED DATA STORAGE SYSTEMS,” co-pending U.S. patent application Ser. No. 14/789,799, filed Jul. 1, 2015, entitled “CROSS-DATACENTER VALIDATION OF GRID ENCODED DATA STORAGE SYSTEMS,” co-pending U.S. patent application Ser. No. 14/789,810, filed Jul. 1, 2015, entitled “INCREMENTAL UPDATES OF GRID ENCODED DATA STORAGE SYSTEMS,” co-pending U.S. patent application Ser. No. 14/789,815, filed Jul. 1, 2015, entitled “NON-PARITY IN GRID ENCODED DATA STORAGE SYSTEMS,” co-pending U.S. patent application Ser. No. 14/789,825, filed Jul. 1, 2015, entitled “REBUNDLING GRID ENCODED DATA STORAGE SYSTEMS,” co-pending U.S. patent application Ser. No. 14/860,706, filed Sep. 21, 2015, entitled “EXPLOITING VARIABLE MEDIA SIZE IN GRID ENCODED DATA STORAGE SYSTEMS,” co-pending U.S. patent application Ser. No. 14/789,837, filed Jul. 1, 2015, entitled “DETERMINING DATA REDUNDANCY IN GRID ENCODED DATA STORAGE SYSTEMS,” co-pending U.S. patent application Ser. No. 14/973,712, filed concurrently herewith, entitled “TECHNIQUES FOR COMBINING GRID-ENCODED DATA STORAGE SYSTEMS,” and co-pending U.S. patent application Ser. No. 14/973,716, filed concurrently herewith, entitled “FLEXIBLE DATA STORAGE DEVICE MAPPING FOR DATA STORAGE SYSTEMS.”
Modern computer systems make extensive use of network computing and network data storage systems. Such use has proliferated in recent years, particularly in distributed or virtualized computer systems where multiple computer systems may share the performance of the tasks associated with the computer system. Such computer systems frequently utilize distributed data storage in multiple locations to store shared data items so that such data items may be made available to a plurality of consumers. The resources for network computing and network data storage are often provided by computing resource providers who leverage large-scale networks of computers, servers and storage drives to enable customers to host and execute a variety of applications and web services. The usage of network computing and network data storage allows customers to efficiently and to adaptively satisfy their varying computing needs, whereby the computing and data storage resources that may be required by the customers are added or removed from a large pool provided by a computing resource provider as needed.
The proliferation of network computing and network data storage, as well as the attendant increase in the number of entities dependent on network computing and network data storage, has increased the importance of balancing both data availability and data integrity on such network computing and network data storage systems. For example, data archival systems and services may use various types of error correcting and error tolerance schemes to ensure data integrity and the expense of data availability leading to a degraded customer experience due to delays in retrieving the data from the data archive.
FIG. 1 illustrates an example environment in which a generator matrix is used to generate initial grids of shards to be combined into a target grid, in accordance with some embodiments;
FIG. 2 illustrates an example environment in which a grid of shards can be extended to include further columns of shards by use of null shards, in accordance with some embodiments;
FIG. 3 illustrates an example environment in which a bundle or grid of shards may be flexibly mapped to a set of data storage devices, in accordance with some embodiments;
FIG. 4 illustrates an example process for combining shards of two or more initial grids, generated by a generator matrix configured to generate a larger target grid, into a target grid, in accordance with some embodiments;
FIG. 5 illustrates an example process for generating a grid of shards that is configurable to be expanded to include additional columns of shards, in accordance with some embodiments;
FIG. 6 illustrates an example process for configuring a bundle or grid of shards to be flexibly mapped to a set of data storage devices, in accordance with some embodiments;
Techniques described and suggested herein include methods, systems, and processes for storing original data of data archives on data storage systems using grid encoding techniques. Grid encoding techniques may be applied to data archives of a computing resource service provider by implementing the storage techniques described herein to increase, for example, availability, redundancy, and durability while minimizing the number of extra storage volume required. In many grid encoding techniques, the stretch factor (i.e., the number of storage volumes required store a volume's worth of data) can approach theoretical minimums as is detailed further herein. Application of such grid encoding techniques allows the storage of original data of the individual archives and redundant storage in other archives, while providing ways to recover from extensive loss of many storage devices and even the recovery of data after the loss of entire data storage facilities.
Data items, which may also be referred to herein as “data archives,” “data objects,” or more simply as “data,” may be received from customers of a computing resource service provider for storage using a grid storage service. Data archives may be received from an archival storage service. Data archives may also be received from other services provided by the computing resource service provider including, but not limited to, redundant storage services, block storage services, virtual machine services, or other such services.
Using a grid encoding technique, data items stored within the grid may be grouped into a collection of shards where each shard represents a logical distribution of the data items stored in the grid. A shard, as used herein, is a logical representation of a set of data stored in the grid and while, in some embodiments, a grid of shards is a partitioning of the data stored in the grid (i.e., each shard is a disjoint set of data items), in other embodiments, shards contain data items that are also stored in other shards. For example, a grid of shards (as described herein) is an abstract representation of a set of storage device locations that are used to store the grid encoded data storage system associated with the grid. Each shard of the grid may be a data shard (i.e., may be configured to store data), a derived shard (i.e., configured to store redundancy encoded representations of that data), a “null” shard (i.e., a virtual or purely abstract shard), or a combination of these. Shards may have an associated set data and/or metadata associated with the shard and/or the grid (e.g., the row and column index of the shard within the grid). Unless otherwise stated or made clear from context, the data items that are represented by the shard and stored in the grid are referred to herein as “shard data” and the data and/or metadata associated with the shard and/or the grid are referred to herein as “shard metadata.”
Each shard may have an associated data storage device and/or an associated data storage volume. A collection of shards may include one or more data shards (e.g., shards associated with data in the data archives), one or more derived shards (e.g., shards associated with grid encoded data associated with the data in the data archives), and/or one more null shards (e.g., shards that are empty and/or are not associated with any data). As used herein, the term “shard” may be used to refer to the data storage abstraction of a shard (i.e., the logical storage device), the associated data storage device of the shard (i.e., the physical storage device), and/or the associated data storage volume of the shard. The shards may be stored using a collection of data storage devices including, but not limited to, tape drives, tapes, disk drives (including both solid state drives and spinning drives), removable media, computer memory, flash drives, various magnetic media, and/or other such storage devices. Each data archive may be stored on one or more data storage devices of the collection of data storage devices, including both homogenous and heterogeneous collections of data storage devices such as, for example, sets of tape drives, sets of disk drives, or sets containing both tape drives and disk drives.
A grid of shards may include a plurality of data shards and one or more derived shards. A grid of shards may also include only derived shards, provided those derived shards are consistent with the redundancy encoding scheme of the grid of shards. The derived shards may include a set of corresponding derived shards for each dimension of the grid. For example, in a two-dimensional grid of shards, the corresponding derived shards may include one or more horizontally derived shards, and one or more vertically derived shards. In a grid of shards, the quantity of derived shards is at least equal to a minimum number of shards required to implement a grid encoding scheme associated with the collection of shards in each dimension. In a first example, a collection of shards may contain two data shards containing data and one derived shard as required to implement parity encoding in the horizontal dimension and may also include three “rows” with a fourth row of vertically derived shards as required to implement a parity encoding in the vertical dimension. Such a grid would include six data shards (two in each of the first three rows), three horizontally derived shards (one in each of the first three rows), and three-vertically derived shards (in the fourth row). As used herein, a derived shard required in association with a parity encoding, which may be referred to as a parity shard, may be configured to store the “exclusive or” (denoted “XOR” or “s”) of the data stored in the other (e.g., data and/or derived) shards.
In an illustrative example, a first simple sixteen-bit data shard may contain “0010 1011 0110 1011” and a second simple sixteen-bit data shard may contain “0100 1101 0100 1011.” The XOR of these two simple sixteen-bit data shards is “0110 0110 0010 0000” and this XOR value (e.g., the value obtained from XORing the two simple sixteen-bit data shards) may then be stored in a parity shard. As described herein, a parity encoding is a linear redundancy encoding scheme based on XOR operations. With two data shards and a parity shard, one of the three values may be lost, and the lost value can be reconstructed from the XOR of the remaining two values. For example, if the first data shard is designated “A,” the second data shard is designated “B,” and the parity shard is designated “C,” then A⊕B=C, A⊕C=B, and B⊕C=A (i.e., any of the shards can be reconstructed from the other two). Storing the “exclusive or” of the data shards ensures that even parity is maintained over the three shards because, if A⊕B=C, then A⊕B⊕C=0. Single parity shards may also be used with larger quantities of data shards to the same effect, allowing the reconstruction of any single lost data value. An additional property of a shard is that a portion of a shard can be reconstructed from corresponding portions of the other shard. In the illustrative example above, each of the four-bit groups of data in the sixteen bit parity shard may be interpreted as a four-bit parity shard for the corresponding four-bit values in data shard “A” and data shard “B.”
Similar redundancy encoding techniques may be used in other dimensions of the grid or, in some embodiments, more complex redundancy encoding techniques are used. In a more complex example, four data shards may be combined with two corresponding derived shards (for a total of six shards in the collection of shards) to allow the reconstruction of up to two lost shards (also referred to herein as “damaged shards”) where the lost shards may be data shards, they may be derived shards, or they may be one of each. Reconstruction of shards in such an example may require redundancy codes such as, for example, an online code, a Luby transform code, a Reed-Solomon code, a Cauchy Reed-Solomon code, a regenerating code, a maximum distance separable code, a repetition code, a cyclic code, a Hamming code, a Reed-Muller code, a Goppa code, a BCH code, a Golay code, an expander code, a linear block code, a linear erasure code, and/or some other redundancy code.
In some embodiments, the grid is encoded with a linear block code such as those described herein. A linear block code allows vertically derived shards such as those described herein to be repaired using the horizontal redundancy encoding scheme of the grid. In some embodiments, the grid is encoded with maximum distance separable codes such as those described herein. A maximum distance separable code allows shards to be derived from any sufficiently large subset of the set of shards in the bundle to be used to reproduce any of the other shards. So, for example, in a 6:4 encoding (e.g., an encoding with six shards, four of which are data shards and two of which are derived shards that are derived using a 6:4 redundancy encoding scheme) with a maximum distance separable code, any four of the shards could be used to reproduce a lost and/or damaged shard of the bundle (i.e., either four data shards, three data shards and one derived shard, or two data shards and two derived shards).
A collection of shards may have any arbitrary number of null shards added to the collection of shards without affecting the redundancy code associated with the collection of shards. For example, because a parity encoding is based on the parity of the data shards, and because a null shard (i.e., a shard with all zeros or an empty shard) does not affect that parity, adding a null shard to that set maintains that parity and, inductively, adding an arbitrary number of null shards to the collection of shards also does not affect that parity. The addition of null shards to collections of shards with more complex redundancy codes also does not affect the more complex redundancy code associated with the collection of shards (e.g., Reed-Solomon codes or Cauchy codes) because the application of such codes to additional null shards simply adds null terms to the associated redundancy encoding calculations. This property of a grid holds when, for example, the grid encoding scheme includes one or more linear block codes as described above. Such linear block codes (e.g., parity, Reed-Solomon) may express the encoding operation as a matrix multiplication of the vector of inputs (e.g., the shards in the grid) with a linear encoding matrix (also referred to herein as a “generator matrix”).
Each shard of a collection of shards may also be padded with any arbitrary corresponding number of zero values (i.e., the arbitrary number of zero values corresponding to each shard) without affecting the redundancy encoding associated with the collection of shards when a linear block code is used. It should be noted that when a linear block code is used to do erasure encoding in a grid, the input data stream (i.e., the data objects) is parsed into a stream of symbols (also referred to herein as “slicing”). Symbols at the same offset are then grouped together and the grouped symbols are encoded (using, for example, the linear block code) into a set of output code words. The code can then be made systematic by fixing some set of the code words, decoding them to obtain the input symbols, and then deriving the remaining code words. In some embodiments, the vertical and horizontal linear erasure codes used for a grid encoding scheme must be linear in the same field (as described below) to support such encoding and decoding.
Linear block coding allows appending zeros because such appending is equivalent to fixing a set of code words to be zero, decoding those zero code words to also be a set of zero symbols, and encoding again to obtain a set of zero code words for the remaining code word positions. The padding of a shard with an amount of data (e.g., zero values) may be illustrated using the previously described example of a first simple sixteen-bit data shard that contains “0010 1011 0110 1011” and a second simple sixteen-bit data shard that contains “0100 1101 0100 1011.” The XOR of these two simple sixteen-bit data shards is “0110 0110 0010 0000” as described above. Padding each of the shards with “0000 0000” does not change the redundancy encoding calculation since “0010 1011 0110 1011 0000 0000”⊕“0100 1101 0100 1011 0000 0000” is “0110 0110 0010 0000 0000 0000” (i.e., the result is similarly padded with “0000 0000”). Other properties associated with padding shards with an arbitrary number of zero (or “null”) values are described below.
A customer device or other entity connects with a data storage service, such as over a network, so as to transact sets of data 102 to be stored as, e.g., a grid of shards on volumes of durable storage associated with the data storage service. The incoming data 102 is processed by the data storage service using, e.g., a redundancy code implementing a generator matrix 104, so as to generate a grid of shards therefrom. The generator matrix may be configured so as to be capable of generating an output grid 114 of the eventual desired size (or, in some embodiments, larger than the eventual desired size), but may also be configurable to generate smaller initial grids 110, 112 which are combinable to generate the output grid 114 using techniques further described herein.
The network may be a communication network, such as the Internet, an intranet or an Internet service provider (ISP) network. Some communications from the customer device to the data storage system may cause the data storage system to operate in accordance with one or more embodiments described or a variation thereof. The front end through which the data storage service 106, as well as other services as further described herein, operates, may be any entity capable of interfacing via the network with the customer device, as well as various other components of a data storage system, so as to coordinate and/or direct data and requests to the appropriate entities. 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), hardware or software-based storage devices (such as hard drives, optical drives, solid state devices, virtual storage devices such as provided by the computing resource service provider, and the like), services (e.g., such as those accessible via application programming interface calls, web service calls, or other programmatic methods), and the like.
The data stored across the durable storage volumes, such as in a grid of shards 110, 112, 114, may have an associated durability that may be based on, for example, an annual failure rate (“AFR”) of the data storage volume or the mapped data storage volume. For a given AFR, it may be assumed that the daily failure rate (“DFR”) for the data storage volume or the mapped data storage volume is the AFR divided by three-hundred and sixty-five (i.e., the number of days in a year) and the hourly failure rate (“HFR”) of the data storage volume or the mapped data storage volume is the DFR divided by twenty-four (i.e., the number of hours in a day). For example, if a data storage volume or the mapped data storage volume has an AFR of 2 percent, the data storage volume or the mapped data storage volume has a DFR of 0.0055 percent and an HFR of 0.00023 percent.
When the data is migrated or otherwise stored via the data storage service, the data storage service may store the data using one or more redundancy encoding techniques such as those described herein. For example, the data storage service may encode the data by producing one or more data shards 126, 130 and may store the one or more data shards on one or more volumes of a set of volumes of durable storage configured to store the redundancy encoded data as described herein. Depending on the redundancy encoding technique used by the data storage service, some or all of the shards stored may consist entirely of original data (identity shards 126, 130) or derived data (derived shards 120, 122, 124, 128, 132). In some embodiments, the shards may be apportioned on a one-to-one basis to the volumes of durable storage. Accordingly, in such embodiments, some volumes may include directly readable, original data (identity shards), while others contain only derived data (derived shards). In the illustrated example, the data is stored as a grid of shards such that a minimum quorum quantity of the shards within the grid, either vertically in a column 116, 118 and/or horizontally in a row (e.g., across columns), may be used to reconstruct any of the data represented therewith.
If, for example, the illustrated grid of shards 116 (or 118) has a minimum quorum quantity of two shards out of the three illustrated in a given row within the grid, any two of that row of shards—regardless of whether the shard is an identity shard 126 or a derived shard 128, may be processed using the redundancy code so as to regenerate the data. Additionally, the original data may be regenerated by directly reading the identity shards, e.g., 126.
The generator matrix 104, as previously mentioned, may be configured so as to generate a grid of shards of varying sizes (e.g., 116, 118, 114). Each initial (constituent) grid 116, 118 generated using the generator matrix 108 may be generated using a designated portion of the generator matrix. For example, the first portion 106 may be used to generate the shards of initial grid 110, while the second portion 108 may be used to generate the shards of initial grid 112. The portions 106, 108 may be designated by, e.g., matrix or shard index, such as by ranges of shard indices, from which the shards of a given grid may be generated.
However, by virtue of being generated using the same generator matrix 104, the initial (constituent) grids 110, 112 can be combined into a larger, output (target) grid 114 without recalculating or regenerating the derived shards 128, 132, either horizontally or vertically. In some embodiments, the “empty” spaces within the initial grids 110, 112 are populated with null shards, e.g., corresponding to shard indices outside of the range designated by the portion 106, 108 of the generator matrix 104 used to generate that grid. In some embodiments, the initial grids 110, 112 are combined by performing a matrix operation, such as matrix addition, of each shard of the first initial grid 116 with its corresponding shard (null or otherwise) in the second initial grid 118. Thus, with regards to the data shards 126, 130 and the derived shards 128, 132, those shards may simply be allocated or copied from the respective initial grid 116, 118 to the combined output grid 114 with little or no computation.
The vertically derived shards 120, 122 are, in the illustrated example, also combined using matrix operations, such as matrix addition. As the derived shards 120 of the first grid 110 and the derived shards 122 of the second grid 112 have the same relative position (e.g., same row indices), matrix addition of the respective shards 120, 122 generate combined vertically derived shards 124, which are then allocated to the same relative position (e.g., row indices) in the output grid 114. Such combination may use partial sum reconstruction techniques described elsewhere in this disclosure and the disclosures incorporated herein by reference.
After combination, the output grid 114 retains the horizontal reconstruction characteristics of the input grids 116, 118 (e.g., if two of three shards, as illustrated, are sufficient to reconstruct any of the shards in a given row in the input grids 116, 118, two of three shards are sufficient to reconstruct any of the shards in a given row in the target grid 114). However, the vertical redundancy changes; in the illustrated example, while the data represented by the initial grids 110, 112 may be vertically reconstructable with a total of four vertically derived shards 120, 122 associated with that data, when combined into the output grid 114, only two vertically derived shards 124 are available for vertical reconstruction within a given column after combination. Such techniques may be used to optimize the level of vertical redundancy for the failure and other operational characteristics of the implementing system.
FIG. 2 illustrates an example environment in which a grid of shards can be extended to include further columns of shards by use of null shards, in accordance with some embodiments.
An initial grid of shards as illustrated in FIG. 2 may include, for example, a set of columns 224, 226, 228 respectively associated with, e.g., a set of datacenters of a data storage system. Each set of columns 224, 226, 228 may initially include, respectively, a column 214 of data shards 202, 208 and derived shards 210, 212, and a column 222 of null shards 232, 234. In some embodiments, the column 222 having null shards may also have vertically derived shards 220, which may also be null (by virtue of being derived from a set of null shards 232, 234). Furthermore, for a given row of shards 230, one or more of the columns not initially having data shards 202, 204 may include a horizontally derived shard 230 marked or otherwise treated as failed (and, in some embodiments, may in fact be another null shard which is treated by an administering system as a failed derived shard. In some embodiments, in columns not initially having data shards 202, 204, the failed derived shard may be considered a “virtual” shard, which may be considered a placeholder (in some cases) or, in the alternative, is a derived shard that initially includes data derived from both data shards (and/or other derived shards) as well as null shards.
In the initial state, such a grid may, e.g., be treated as a smaller initial grid having, as in the illustrated case, three shards per row, which may for example be implemented such that two of the shards in a given row are sufficient to regenerate any of the three in the row 206. When additional data is to be added to the grid, in some embodiments, the new data is added on a per-row basis. In other words, all null shards 232 in a given row of the grid are populated at a given time. In the illustrated example, the null shards 232 in row 206 are converted to data shards 216. A new derived shard 218 is generated, placed where the failed derived shard 230 previously was, and, in some embodiments, derived shard 204 is also updated (rederived) to reflect the new scheme and additional data shards. The illustrated example demonstrates a 3:2 initial grid moving to a 6:4 scheme, horizontally.
In connection with the horizontal update just described, the vertical shards in the newly populated column 222 (and other columns likewise updated) are updated (e.g., rederived) to reflect the conversion. In some embodiments, an implementing system may delay the updating of vertically derived shards 220 until multiple rows 206 are populated with data, so as to batch together row-wise updates when recalculating the vertically derived shards. Similarly, incoming data may be delayed from migrating to a given row until a sufficient amount of data is available to fully populate that row 206.
FIG. 3 illustrates an example environment in which a bundle or grid of shards (e.g., data shards 304, derived shards 308, 316, of which some may be vertically derived 316 if the redundancy coding scheme is a grid encoding scheme) may be flexibly mapped to a set of data storage devices, in accordance with some embodiments. A column (e.g., of a grid) or bundle of shards 302 to be stored on a set of data storage devices 306, the quantity of which may not necessarily equal the number of shards to be stored on the set, are mapped to a logical storage layer that is apportioned into addressable zones 310. The addressable zones 310 may correspond to address ranges of the shards 304, 308, 316, and in some embodiments, the addressable zones 310 are allocated so as to be of equal size (e.g., the address ranges of the shards to which they map are of equal size).
The shards themselves may be generated, using a redundancy coding scheme as described elsewhere herein and in the incorporated disclosures, to be of a size specified in connection with characteristics of the data storage devices 306 to which they will be stored. For example, the shard size may be generated so as to be no larger than the smallest available capacity of any medium within the set of data storage devices, so as to limit association of a given medium within the set to no more than two shards.
The set of data storage devices is then allocated, in some embodiments independently of the shards or the addressable zones, in a continuum according to their available capacity, which may vary between media of the set of storage devices 306. As illustrated, the first storage medium 306 is associated with the first two addressable zones, but not all of the second one (and thus does not fully store the first shard 304. When data requests (such as read, write, or repair requests) arrive, in some embodiments, they are executed on a per-zone 310 basis, and the mechanisms may differ based on whether the request involves a read, a write, a repair, or some combination thereof, on the associated data storage medium.
For example, if the second medium 306 goes offline and a repair is needed, the repair may be performed on a per-zone 310 basis such that the second addressable zone associated with the first shard is first repaired and written to a different, available medium, thereby bringing the first shard fully online, then the first and second addressable zones associated with the second shard is repaired, thereby bringing the second shard online. Accordingly, the durability calculations for the shards remains unperturbed even if the data storage media are logically decoupled from the boundaries of the shards themselves, thereby increasing storage efficiency (e.g., less slack space).
FIG. 4 illustrates an example process for combining shards of two or more initial grids, generated by a generator matrix configured to generate a larger target grid, into a target grid, in accordance with some embodiments.
At step 402, an entity, such as a grid storage system, creates a generator matrix with sufficient information to generate a grid of the size of the target grid. Such a grid may have a surplus of rows, columns, or shard indices, relative to the size of initial or even target grids, so as to allow for future expansion of generated grids.
At step 404, portions, such as ranges of shard indices, of the generator matrix are used by a system, such a data storage system to generate the initial grids of shards from input data received by the system from, e.g., a customer device. As previously mentioned, the initial grids may be used normally until such a time as it is desired to combine them into a larger target grid, e.g., to accommodate changing system or customer requirements.
At step 406, when the grids are to be combined, the initial grids generated and populated in steps 402 and 404 are combined by, e.g., an entity of a grid storage system, by first allocating the data and horizontally derived shards of each grid to their respective positions in the target grid. In some embodiments, such combination may require little or no computation, as null shards are added to other shards.
At step 408, the vertically derived shards are combined, e.g., by an entity of the grid storage system, using matrix operations such as matrix additions and using techniques described in incorporated disclosures, such as partial sum reconstruction. At step 410, the combined vertically derived shards generated in step 408 are added to their respective positions in the target grid. As may be contemplated, further grids may be added to the target grids, and target grids added to other target grids, so long as they share a common generator matrix and use disparate portions thereof for generation of the shards that populate them.
FIG. 5 illustrates an example process for generating a grid of shards that is configurable to be expanded to include additional columns of shards, in accordance with some embodiments.
At step 502, an entity, such as a grid storage system, generates a grid with the desired eventual column width, and step 504, only some of the columns are populated with data shards and derived shards (e.g., horizontally and vertically derived shards) so as to leave some of the columns unpopulated. As previously mentioned, such population may take place so as to accommodate a desired initial grid encoding, such as 3:2, while the remainder of a desired target grid (e.g., the other three columns in a desired target 6:4 encoding) are populated by the entity with null shards at step 506. At step 508, some of the unpopulated columns are populated, or otherwise treated as, failed derived shards, even if the underlying shard populating that column (e.g., at step 506) is a null shard.
At step 510, in connection with a grid update, e.g., as triggered by additional incoming data where a grid expansion would be desirable, the null shards are replaced, on a row-by-row-basis, with data shards. At step 512, the shards designated as failed derived shards 508 are replaced with active derived shards that are based on the new data shards in the respective row, and at step 514, associated vertically derived shards in the same column as the new data shards are also rederived or otherwise updated.
FIG. 6 illustrates an example process for configuring a bundle or grid of shards to be flexibly mapped to a set of data storage devices, in accordance with some embodiments.
At step 602, a system, such as a data storage system, determines the optimal shard size to generate based on the smallest expected data storage device capacity of a set of data storage devices to which the generated shards are to be stored. As previously discussed, the optimal shard size may be no larger than the smallest available capacity of any data storage device of the set.
At step 604, the shards are generated by the data storage system in accordance with the optimal shard size determined in step 602, and at step 606, two or more addressable zones of a logical storage layer are associated with each shard. Thereafter, at step 608, the logical storage layer is correlated to the set of data storage devices, such that the boundaries of either the shards or the addressable zones are not necessarily associated with the boundaries of the individual media of the set of data storage devices. At step 610, as data is to be manipulated (e.g., written, read, repaired, the manipulation occurs on a per-addressable zone basis and involves whichever data storage devices are associated with the addressable zones manipulated, and, conversely, if an operation involves a given data storage device, the manipulations (e.g., repairs), occur with relation to the addressable zones.
A customer, via a customer device 702, may connect via a network 704 to one or more services 706 provided by a computing resource service provider 718. In some embodiments, the computing resource service provider 718 may provide a distributed, virtualized and/or datacenter environment within which one or more applications, processes, services, virtual machines, and/or other such computer system entities may be executed. In some embodiments, the customer may be a person, or may be a process running on one or more remote computer systems, or may be some other computer system entity, user, or process. The customer device 702 and the network 704 may be similar to that described in connection with at least FIG. 1 above.
FIG. 8 illustrates an example environment 800 where a redundancy encoding technique is applied to data stored in durable storage as described in connection with FIGS. 1-7 and in accordance with an embodiment. The redundancy encoding technique illustrated in FIG. 8 is an example of a grid encoding technique wherein each identity shard is part of a first set of one or more identity shards which may be bundled with one or more derived shards in a first group or bundle (i.e., in one dimension or direction) and each identity shard is also part of at least a second set of one or more identity shards which may be bundled with one or more other derived shards in a second bundle or group (i.e., in a second dimension or direction). As is illustrated in FIG. 8, a grid encoding technique is often implemented as a two-dimensional grid, with each shard being part of two bundles (i.e., both “horizontal” and “vertical” bundles). However, a grid encoding technique may also be implemented as a three-dimensional grid, with each shard being part of three bundles, or a four-dimensional grid, with each shard being part of four bundles, or as a larger-dimensional grid. Additional details of grid encoding techniques are described in U.S. patent application Ser. No. 14/789,783, filed Jul. 1, 2015, entitled “GRID ENCODED DATA STORAGE SYSTEMS FOR EFFICIENT DATA REPAIR,” which is incorporated by reference herein.
In the example illustrated in FIG. 8, data 802 from preliminary storage is provided for storage in durable storage using a redundancy encoding technique with both horizontal derived shards and vertical derived shards. In the example illustrated in FIG. 8, a first datacenter 812 may contain data shards (denoted as a square shard with the letter “I”), horizontal derived shards (denoted as a triangular shard with the Greek letter “8” or delta), and vertical derived shards (denoted as an inverted triangle with the Greek letter “8”) all of which may be stored on durable storage volumes within the first datacenter 812. A second datacenter 814, which may be geographically and/or logically separate from the first datacenter 812, may also contain data shards, horizontal derived shards, and/or vertical derived shards. A third datacenter 816, which may be geographically and/or logically separate from the first datacenter 812 and from the second datacenter 814, may also contain data shards, horizontal derived shards, and/or vertical derived shards. As illustrated in FIG. 8, each of the three datacenters may be a single vertical bundle. In an embodiment, each of the datacenters can include multiple vertical bundles. As may be contemplated, the number of datacenters illustrated in FIG. 8 and/or the composition of the datacenters illustrated in FIG. 8 are merely illustrative examples and other numbers and/or compositions of datacenters may be considered as within the scope of the present disclosure. The datacenters may be co-located or may be located in one or more separate datacenter locations.
FIG. 10 illustrates an example process 1000 for applying redundancy encoding techniques to data stored in durable storage as described herein in connection with FIG. 1 and in accordance with at least one embodiment. The example process 1000 illustrated in FIG. 10 illustrates the processing, indexing, storing, and retrieving of data stored on a data storage system. The data may be retrieved from preliminary storage as described herein. The example process 1000 illustrated in FIG. 10 may be used in conjunction with a grid encoding technique such that described in connection with FIG. 8, in conjunction with a bundle encoding technique such as that described in connection with FIG. 9, or with some other redundancy encoding technique. A data storage service such as the data storage service described herein may perform the example process 1000 illustrated in FIG. 10.
FIG. 11 illustrates aspects of an example environment 1100 for implementing aspects in accordance with various embodiments. 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 embodiments. The environment includes an electronic client device 1102, which can include any appropriate device operable to send and/or receive requests, messages, or information over an appropriate network 1104 and, in some embodiments, 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 1106 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 1108 and a data store 1110. 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 1102 and the application server 1108, 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 various embodiments 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.
In embodiments utilizing a web server, 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 (“CGP”) 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.
generating, from a first data set using an erasure code, a grid of shards representing the first data set, wherein the grid of shards comprises a set of data shards, a set of null shards, a set of virtual shards, and a set of derived shards, the set of derived shards comprising a first set of columns and a second set of columns, the first set of columns including a set of horizontally derived shards and a set of vertically derived shards, each derived shard of the set of derived shards being respectively reproducible from a subset of the horizontally derived shards in a corresponding row and a subset of the vertically derived shards in a corresponding column, the second set of columns including the set of virtual shards and the set of null shards;
allocating the grid of shards at a set of datacenter locations by at least, on a respective device at each datacenter location of the set of datacenter locations, storing corresponding first shards of the first set of columns and corresponding second shards of the second set of columns;
processing a second data set by at least: generating, from a first null shard, a second null shard, and the second data set, a respective first converted data shard and a respective second converted data shard, each including at least a portion of the second data set; generating, by applying the erasure code to the first converted data shard and the second converted data shard, a third converted derived shard; and generating, by respectively applying the erasure code to the first converted data shard, the second converted data shard, and the third converted derived shard, a respective new first derived shard, a respective new second derived shard, and a respective new third derived shard; and
causing the set of datacenter locations to provide access to both the first data set and the second data set while retaining at least one storage characteristic associated with the first data set, by at least: adding, to the corresponding first shards stored at the set of datacenter locations, the new first derived shard, the new second derived shard, and the new third derived shard; and replacing some of the corresponding second shards stored at the set of data center locations with the first converted data shard, the second converted data shard, and the third converted data shard.
2. The computer-implemented method of claim 1, wherein the virtual shard is configured as a failed derived shard.
3. The computer-implemented method of claim 1, further comprising, prior to generating the first derived shard and the second derived shard:
converting a third null shard to a third converted data shard;
converting a fourth null shard to a fourth converted data shard; and
converting a second virtual shard to a second converted derived shard by applying the erasure code to the fourth converted data shard and the third converted data shard.
4. The computer-implemented method of claim 1, wherein the erasure code is Reed-Solomon.
generate, by applying a first redundancy code to a first set of data, a grid of shards comprising a first set of columns including a set of data shards and a set of virtual shards, and a second set of columns including a set of null shards and a set of derived shards, wherein each shard of the grid of shards has a corresponding first index and a corresponding second index, each shard other than a null shard or a virtual shard configured such that the shard is reproducible from other shards associated with the first index and the shard is reproducible from other shards associated with the second index;
storing, at each datacenter location of a set of datacenter locations associated with the system, first shards of the first set of columns and second shards of the second set of columns; and
as a result of a request to store a second set of data, processing the second set of data by at least: generating, from a first null shard, a second null shard, and the second set of data, a respective first converted data shard and a respective second converted data shard, each including at least a portion of the second set of data; generating a third converted derived shard by applying the first redundancy code to the first converted data shard and the second converted data shard; generating, by applying the first redundancy code to the first converted data shard, the second converted data shard, and the third converted derived shard, a respective first derived shard, second derived shard, and third derived shard; and updating the first shards and the second shards to include the first converted data shard, the second converted data shard, the third converted data shard, the first derived shard, the second derived shard, and the third derived shard to enable the set of datacenter locations to provide access to both the first data set and the second data set while retaining at least one storage characteristic associated with the first data set.
6. The system of claim 5, wherein the one or more services further generate the grid of shards using a generator matrix.
7. The system of claim 5, wherein the one or more services further update the first shards and the second shards using a second redundancy code.
8. The system of claim 7, wherein the second redundancy code is different than the first redundancy code.
9. The system of claim 8, wherein the second redundancy code is a parity code.
10. The system of claim 5, wherein the first redundancy code is Reed-Solomon.
select a shard of the grid of shards;
select a set of other shards based at least in part on the first index of the selected shard; and
reproduce the selected shard from a subset of the set of other shards.
12. The system of claim 5, wherein the one or more services further:
select a set of other shards based at least in part on the second index of the selected shard; and
process a first data object using a redundancy code to generate a grid of shards comprising a set of null shards, a set of virtual shards, and a set of derived shards, each shard of the grid of shards having a corresponding first index and a corresponding second index, each shard being independently reproducible from other shards associated with the first index and other shards associated with the second index; and
enable the computer system to retain at least one storage characteristic associated with a first data set while providing access to a second data object via the grid of shards by at least: generating, by applying the redundancy code to the second data object and a first null shard and a second null shard of the set of null shards having the same first index, a respective first data shard and a second data shard, each including at least a portion of the second data object, to replace the first null shard and the second null shard; generating, by applying the redundancy code to the first data shard and a second data shard, a third derived shard to replace a virtual shard having the same first index; and generating a new set of derived shards to replace a subset of the set of derived shards, each shard of the subset corresponding to respective second indices associated with the first data shard, the second data shard, and the third derived shard.
the redundancy code is a first linear erasure code; and
the new set of derived shards is generated using a different second linear erasure code.
the first linear erasure code is a parity code; and
the second linear erasure code is a Reed-Solomon code.
16. The non-transitory computer-readable storage medium of claim 15, wherein each shard of the grid of shards has a corresponding set of grid metadata, the set of grid metadata including a first set of constants associated with the first linear erasure code and a second set of constants associated with the second linear erasure code.
17. The non-transitory computer-readable storage medium of claim 16, wherein the set of grid metadata includes a third set of constants associated with a cyclic redundancy check usable to validate the grid of shards.
18. The non-transitory computer-readable storage medium of claim 13, wherein the instructions further include instructions that, as a result of execution, process the received second data object by applying a first subset of a generator matrix of the redundancy code to the second data object.
19. The non-transitory computer-readable storage medium of claim 13, wherein the corresponding second index of each shard of the grid of shards is based at least in part on a geographical location of the shard.
20. The non-transitory computer-readable storage medium of claim 13, wherein the new set of derived shards is derived from shards outside of the sub set.
5729671 March 17, 1998 Peterson et al.
6779150 August 17, 2004 Walton et al.
6862362 March 1, 2005 Gangadhar
7117294 October 3, 2006 Mi et al.
7142150 November 28, 2006 Thackray
7380129 May 27, 2008 Keohane et al.
7490013 February 10, 2009 Wells
7693813 April 6, 2010 Cao et al.
7805706 September 28, 2010 Ly et al.
7930611 April 19, 2011 Huang et al.
8386841 February 26, 2013 Renade
8413187 April 2, 2013 Del Sesto et al.
8479078 July 2, 2013 Resch et al.
8504518 August 6, 2013 Ghemawat et al.
8612219 December 17, 2013 Tsuchinaga et al.
8621069 December 31, 2013 Tompkins
8706980 April 22, 2014 Dhuse et al.
8769049 July 1, 2014 Murphy et al.
8788855 July 22, 2014 Cong et al.
8806296 August 12, 2014 Lazier
8850288 September 30, 2014 Lazier et al.
8868825 October 21, 2014 Hayes et al.
8869001 October 21, 2014 Lazier
8935221 January 13, 2015 Lazier et al.
8935761 January 13, 2015 Gladwin et al.
8938591 January 20, 2015 Mark et al.
8959067 February 17, 2015 Patiejunas et al.
8984363 March 17, 2015 Juels et al.
8984384 March 17, 2015 Juels et al.
9002805 April 7, 2015 Barber et al.
9003144 April 7, 2015 Hayes et al.
9009491 April 14, 2015 Resch
9021297 April 28, 2015 Hayes et al.
9047214 June 2, 2015 Northcott
9052942 June 9, 2015 Barber et al.
9110797 August 18, 2015 Lazier
9165002 October 20, 2015 Lazier
9208018 December 8, 2015 Northcott et al.
9213485 December 15, 2015 Hayes et al.
9213709 December 15, 2015 Patiejunas et al.
9218244 December 22, 2015 Hayes et al.
9223789 December 29, 2015 Seigle et al.
9225675 December 29, 2015 Patiejunas et al.
9244761 January 26, 2016 Yekhanin et al.
9250811 February 2, 2016 Patiejunas
9251097 February 2, 2016 Kumar et al.
9256761 February 9, 2016 Sahu et al.
9271052 February 23, 2016 Holden
9281845 March 8, 2016 Lazier
9298760 March 29, 2016 Li et al.
9354683 May 31, 2016 Patiejunas et al.
9378084 June 28, 2016 Calder et al.
9405333 August 2, 2016 Pine
9448614 September 20, 2016 Slik
9459959 October 4, 2016 Franklin et al.
9495249 November 15, 2016 Franklin et al.
9495255 November 15, 2016 Davis et al.
9563681 February 7, 2017 Patiejunas et al.
9753669 September 5, 2017 Ben-Shaul et al.
9785495 October 10, 2017 Lazier et al.
9792179 October 17, 2017 Lazier
9825625 November 21, 2017 Thalheim
9825652 November 21, 2017 Lazier
9838041 December 5, 2017 Lazier
9838042 December 5, 2017 Lazier
9853662 December 26, 2017 Lazier et al.
9866242 January 9, 2018 Lazier
9904589 February 27, 2018 Donlan et al.
9923966 March 20, 2018 Franklin et al.
20040040025 February 26, 2004 Lehtinen
20040054997 March 18, 2004 Katragadda et al.
20040128470 July 1, 2004 Hetzler et al.
20040230764 November 18, 2004 Merchant et al.
20040268037 December 30, 2004 Buchanan et al.
20060080574 April 13, 2006 Saito et al.
20060136928 June 22, 2006 Crawford et al.
20060168575 July 27, 2006 Bhatt et al.
20060168581 July 27, 2006 Goger et al.
20070124020 May 31, 2007 Staples
20070180294 August 2, 2007 Kameyama et al.
20090094250 April 9, 2009 Dhuse et al.
20090319078 December 24, 2009 Jackson
20100131792 May 27, 2010 Herrod
20100153941 June 17, 2010 Borissov et al.
20100318999 December 16, 2010 Zhao et al.
20100328528 December 30, 2010 Eggert
20100332751 December 30, 2010 Quigley
20110022633 January 27, 2011 Bernosky et al.
20110055661 March 3, 2011 Grube et al.
20110078277 March 31, 2011 Baptist
20110202929 August 18, 2011 Schleimer et al.
20110225209 September 15, 2011 Volvovski et al.
20110264717 October 27, 2011 Grube et al.
20110296195 December 1, 2011 Nakagawa et al.
20120011398 January 12, 2012 Eckhardt et al.
20120017096 January 19, 2012 Snider
20120079189 March 29, 2012 Colgrove et al.
20120079190 March 29, 2012 Colgrove et al.
20120243687 September 27, 2012 Li et al.
20120254089 October 4, 2012 Alba et al.
20120254175 October 4, 2012 Horowitz et al.
20120254690 October 4, 2012 Resch et al.
20120290539 November 15, 2012 Bryant et al.
20120322422 December 20, 2012 Frecks, Jr. et al.
20130007511 January 3, 2013 Gaertner et al.
20130029641 January 31, 2013 Hickie
20130073600 March 21, 2013 Jenkins et al.
20130191527 July 25, 2013 Ashok et al.
20140006458 January 2, 2014 Hsieh et al.
20140007214 January 2, 2014 Qureshi et al.
20140046906 February 13, 2014 Patiejunas et al.
20140046908 February 13, 2014 Patiejunas et al.
20140047261 February 13, 2014 Patiejunas et al.
20140122572 May 1, 2014 Finkelstein et al.
20140149794 May 29, 2014 Shetty et al.
20140149986 May 29, 2014 S M et al.
20140153481 June 5, 2014 Draznin et al.
20140156632 June 5, 2014 Yu
20140173058 June 19, 2014 Twitchell, Jr.
20140189388 July 3, 2014 Lynar et al.
20140201541 July 17, 2014 Paul et al.
20140298134 October 2, 2014 Grube et al.
20140304356 October 9, 2014 Allen, Sr. et al.
20140310571 October 16, 2014 Fetterly
20140351632 November 27, 2014 Grube et al.
20140372383 December 18, 2014 Sipek
20140380126 December 25, 2014 Yekhanin et al.
20150149870 May 28, 2015 Kozat
20150169716 June 18, 2015 Franklin et al.
20150278324 October 1, 2015 Wong et al.
20150324745 November 12, 2015 Goodall et al.
20150331635 November 19, 2015 Ben-Shaul et al.
20150355974 December 10, 2015 Hayes et al.
20150356005 December 10, 2015 Hayes et al.
20160011816 January 14, 2016 Aizman
20160034295 February 4, 2016 Cochran
20160041868 February 11, 2016 Davis et al.
20160041869 February 11, 2016 Davis
20160041878 February 11, 2016 Davis et al.
20160041887 February 11, 2016 Davis et al.
20160048399 February 18, 2016 Shaw
20160062623 March 3, 2016 Howard et al.
20160085797 March 24, 2016 Patiejunas et al.
20160092248 March 31, 2016 Shani et al.
20160179824 June 23, 2016 Donlan et al.
20160216991 July 28, 2016 Ansari et al.
20160335310 November 17, 2016 Lahiri et al.
20170024281 January 26, 2017 Franklin et al.
20170060687 March 2, 2017 Franklin et al.
20170222814 August 3, 2017 Oberhauser et al.
20170250801 August 31, 2017 Chen et al.
20170331896 November 16, 2017 Holloway et al.
2014047073 March 2014 WO
“New! xTablet T7000 Rugged Mini Tablet PC,” MobileDemand, copyright 2012 [web archive Mar. 12, 2012], https://web.archive.org/web/20120312010139/http://www.ruggedtabletpc.com/products/xtablet-t7000-rugged-mini-tablet-pc/, 3 pages.
Binns, “Elasticsearch Failure and Recovery,” TechRabbit, Oct. 31, 2014 [retrieved Nov. 17, 2017], http://tech.taskrabbit.com/blog/2014/10/31/es-failure-recovery/, four pages.
Franco, “Understanding Bitcoin: Cryptography, Engineering and Economics,” Wiley, Nov. 24, 2014, 167 pages.
He et al., “Elastic Application Container: A Lightweight Approach for Cloud Resource Provisioning,” 26th IEEE International Conference on Advanced Information Networking and Applications, Mar. 26, 2012, pp. 15-22.
International Organization for Standardization/ International Electrotechnical Commission, “Information technology—Trusted Platform Module—Part 1: Overview,” International Standard, ISO/IEC 11889-1(E), May 15, 2009, 20 pages.
International Organization for Standardization/International Electrotechnical Commission, “Information technology—Trusted Platform Module—Part 2: Design principles,” International Standard, ISO/IEC 11889-2(E), May 15, 2009, 152 pages.
International Organization for Standardization/International Electrotechnical Commission, “Information technology—Trusted Platform Module—Part 3: Structures,” International Standard, ISO/IEC 11889-3:2009(E), 204 pages.
International Organization for Standardization/International Electrotechnical Commission, “Information technology—Trusted Platform Module—Part 4: Commands,” International Standard, ISO/IEC 11889-4:2009(E), 254 pages.
Kim, “How Sharding Works,” Medium, Dec. 5, 2014 [retrieved Nov. 17, 2017], https://medium.com/@jeeyoungk/how-sharding-works-b4dec46b3f6, 12 pages.
MacCarthaigh, “Shuffle Sharding: Massive and Magical Fault Isolation,” AWS Architecture Blog, Apr. 14, 2014 [retrieved Nov. 27, 2017], https://aws.amazon.com/blogs/architecture/shuffle-sharding-massive-and-magical-fault-isolation/, six pages.
Pikkarainen et al., “The impact of agile practices on communication in software development,” Empirical Software Engineering 13(3):303-37, Jun. 1, 2008.
Ramamritham, “Allocation and scheduling of precedence-related periodic tasks,” IEEE Transactions on Parallel and Distributed Systems 6(4):412-420, Apr. 1995.
Soltesz et al., “Container-based operating system virtualization: a scalable, high-performance alternative to hypervisors,” ACM SIGOPS Operating Systems Review 41(3):275-287, Mar. 2007.
Swan, “Blockchain: Blueprint for a New Economy,” O'Reilly Media, Inc., Jan. 22, 2015, 144 pages.
Thiele et al., “Embedded Software in Network Processors—Models and Algorithms,” Lecture Notes in Computer Science 2211:416-34, Oct. 8, 2001.
Trusted Computing Group, “TPM Main, Part 1 Design Principles,” Specification Version 1.2, Level 2 Revision 103, Jul. 9, 2007, 182 pages.
Trusted Computing Group, “TPM Main, Part 1 Design Principles,” Specification Version 1.2, Revision 116, Mar. 1, 2011, 184 pages.
Trusted Computing Group, “TPM Main, Part 2 TPM Structures,” Specification Version 1.2, Level 2 Revision 103, Jul. 9, 2007, 198 pages.
Trusted Computing Group, “TPM Main, Part 2 TPM Structures,” Specification Version 1.2, Revision 116, Mar. 1, 2011, 201 pages.
Trusted Computing Group, “TPM Main, Part 3 Commands,” Specification Version 1.2, Level 2 Revision 103, Jul. 9, 2007, 330 pages.
Trusted Computing Group, “TPM Main, Part 3 Commands,” Specification Version 1.2, Revision 116, Mar. 1, 2011, 339 pages.
Van et al., “SLA-aware Virtual Resource Management for Cloud Infrastructures,” IEEE Ninth International Conference on Computer and Information Technology, Oct. 11, 2009, pp. 357-362.
Wikipedia, “IEEE 802.11,” Wikipedia, the Free Encyclopedia, page last modified Feb. 7, 2017, retrieved Feb. 13, 2017, https://en.wikipedia.org/wiki/IEEE_802.11, 9 pages.
Wikipedia, “IEEE 802.16,” Wikipedia, the Free Encyclopedia, page last modified Nov. 21, 2016, retrieved Feb. 13, 2017, https://en.wikipedia.org/wiki/IEEE_802.16, 8 pages.
Wikipedia, “IEEE 802.21,” Wikipedia, the Free Encyclopedia, page last modified Aug. 4, 2016, retrieved Feb. 13, 2017, https://en.wikipedia.org/wiki/IEEE_802.21, 3 pages.
Xavier et al., “Performance evaluation of container-based virtualization for high performance computing environments,” Parallel, Distributed and Network-Based Processing (PDP), 2013 21st Euromicro International Conference, Feb. 2013, pp. 233-240.
Zhao et al., “Experimental study of virtual machine migration in support of reservation of cluster resources,” Proceedings of the 2nd international workshop on Virtualization technology in distributed computing, Nov. 2007, pp. 1-8.
Zheng et al., “Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services,” The VLDB Journal—The International Journal on Very Large Data Bases 15(1):21-39, online publication Jul. 22, 2005, print publication Jan. 1, 2006.
Amazon, “Batch Cloud Data Transfer Services—Amazon Import/Export Snowball Appliance,” Jun. 17, 2016, retrieved Oct. 8, 2016, https://web.archive.org/web/20160617044144/http://aws.amazon.com/importexport/, 6 pages.
Barr, “AWS Import/Export: Ship Us That Disk!,” Amazon Web Services Blog, May 21, 2009, retrieved Mar. 14, 2017, https://aws.amazon.com/blogs/aws/send-us-that-data/, 7 pages.
Dang, “Recommendation for Applications Using Approved Hash Algorithms,” National Institute of Standards and Technology (NIST) Special Publication 800-107 Revision 1, Aug. 2010, retrieved Nov. 24, 2015, http://csrc.nist.gov/publications/nistpubs/800-107-rev1/sp800-107-rev1.pdf, 25 pages.
Storer et al., “POTSHARDS—A Secure, Recoverable, Long-Term Archival Storage System,” ACM Transactions on Storage, Published Jun. 2009, vol. 5, No. 2, Article 5, pp. 5:1 to 5:35.
Zyga, “Light-up Cereal Boxes Powered by Shelvers on Display at CES,” Phys.org, Jan. 11, 2011, retrieved May 19, 2015, http://phys.org/news/201101lightupcerealpoweredshelvesces.html, 13 pages.
Patent number: 10127105
Inventor: Bryan James Donlan (Seattle, WA)
Application Number: 14/973,708
International Classification: G06F 11/10 (20060101); G06F 3/06 (20060101);