Space-efficient techniques for generating unique instances of data objects

Abstract

A set of data units associated with a data object is obtained, such that respective instances of the data object can be reconstructed from respective subsets of the set. Corresponding to a request for the data object, a first subset of the set is identified. The first subset meets a uniqueness criterion with respect to other subsets of the set that are used to respond to other requests for the data object. An instance of the data object is reconstructed from the first subset.

What is claimed is: 
     
       1. A system, comprising:
 one or more computing devices; 
 wherein the one or more computing devices include instructions that upon execution on or across one or more processors cause the one or more computing devices to:
 obtain an indication of an expected demand for a data object to be accessed via a network; 
 generate, from the data object, a first set of data units, wherein using the first set of data units respective unique instances of the data object can be reconstructed from respective subsets of the first set of data units, and wherein the number of data units generated is based at least in part on the expected demand; 
 store the first set of data units at one or more storage devices; 
 identify, corresponding to a first request for at least a portion of the data object, a first subset of the first set, wherein the first subset meets a uniqueness criterion for reconstructing an instance of at least a portion of the data object with respect to other subsets of the first set that are used to respond to other requests for at least the portion of the data object, wherein the uniqueness criterion comprises a requirement that respective members of the first subset and respective members of respective ones of the other subsets differ one to another by at least one data unit of the first set of data units; 
 reconstruct a first instance of at least the portion of the data object from the first subset, wherein the reconstruction comprises accessing at least one storage device of the one or more storage devices; and 
 cause the first instance to be provided to one or more requestors. 
 
 
     
     
       2. The system as recited in  claim 1 , wherein to identify that the first subset meets the uniqueness criterion, the one or more computing devices include further instructions that upon execution on or across one or more processors further cause the one or more computing devices to:
 verify that the first subset has not been used to respond to any other request. 
 
     
     
       3. The system as recited in  claim 1 , wherein the one or more computing devices include further instructions that upon execution on or across one or more processors further cause the one or more computing devices to:
 cause a plurality of instances of the data object to be provided to a plurality of requesters, wherein individual ones of the plurality of instances are reconstructed from respective subsets of the first set, and wherein the amount of storage to store the first set at the one or more storage devices is smaller than the product of (a) the size of the data object and (b) the total number of provided instances. 
 
     
     
       4. The system as recited in  claim 1 , wherein the one or more computing devices include further instructions that upon execution on or across the one or more processors further cause the one or more computing devices to:
 in response to obtaining an indication of an increase in demand of the data object, generate one or more additional data units from the data object after the first set of data units has been stored; and 
 reconstruct a second instance of at least a portion of the data object using at least one additional data unit of the one or more additional data units. 
 
     
     
       5. The system as recited in  claim 1 , wherein the first set of data units comprises a plurality of copies of a first data unit, and wherein the first subset comprises no more than one copy of the plurality of copies of the first data unit. 
     
     
       6. A method, comprising:
 performing, at one or more computing devices:
 generating, from a data object, a first set of data units, wherein using the first set of data units respective unique instances of the data object can be reconstructed from respective subsets of the first set of data units; 
 storing the first set of data units generated from a data object; 
 identifying, corresponding to a first request for at least a portion of the data object, a first subset of the first set, wherein the first subset meets a uniqueness criterion for reconstructing an instance of at least a portion of the data object with respect to other subsets of the first set that are used to respond to other requests for at least the portion of the data object, wherein the uniqueness criterion comprises a requirement that respective members of the first subset and respective members of respective ones of the other subsets differ one to another by at least one data unit of the first set of data units; and 
 providing a first instance of at least the portion of the data object, wherein the first instance is reconstructed from the first subset. 
 
 
     
     
       7. The method as recited in  claim 6 , further comprising performing, at the one or more computing devices:
 generating the first set of data units using a coding algorithm, wherein the coding algorithm comprises one or more of: a Reed-Solomon erasure-coding algorithm, an XOR (exclusive OR) based coding algorithm, a network coding algorithm, or a Mojette coding algorithm. 
 
     
     
       8. The method as recited in  claim 6 , further comprising performing, at the one or more computing devices:
 generating the first set of data units using a coding algorithm, wherein one or more parameters associated with the coding algorithm are selected based at least in part on one or more of: (a) an expected demand for the data object, (b) a size of the data object, (c) an availability requirement, (d) a data durability requirement, or (e) a geographical distribution requirement. 
 
     
     
       9. The method as recited in  claim 6 , further comprising performing, at the one or more computing devices:
 subdividing the data object into a plurality of segments, wherein the first set of data units includes at least one segment of the plurality of segments. 
 
     
     
       10. The method as recited in  claim 6 , further comprising performing, at the one or more computing devices:
 subdividing the data object into a plurality of segments; 
 generating, using one or more transformation functions, a plurality of derived data units from the plurality of segments, such that the data object cannot be reconstructed by concatenating derived data units, wherein the first set of data units (a) includes one or more derived data units and (b) does not include segments of the plurality of segments. 
 
     
     
       11. The method as recited in  claim 6 , further comprising performing, at the one or more computing devices:
 generating unique identifiers of respective subsets of the first set, including a first unique identifier of the first subset; and 
 storing, as an indicator that the first subset was used to respond to the first request, at least the unique identifier. 
 
     
     
       12. The method as recited in  claim 11 , further comprising performing, at the one or more computing devices:
 assigning, to individual ones of the data units of the first set, a respective position within a bitmap, wherein the generating of the unique identifiers comprises utilizing a bitmap in which entries assigned to the data units of the first subset are set to a selected value. 
 
     
     
       13. The method as recited in  claim 6 , wherein at least some data units of the first subset are stored at an edge device of a data distribution service. 
     
     
       14. The method as recited in  claim 6 , further comprising performing, at the one or more computing devices:
 providing, via a programmatic interface in response to a first request from a client of a data distribution service, an identifier of a second subset of the first set, wherein a second instance of at least a portion of the data object can be reconstructed from the second subset; and 
 generating, in response to a second request which includes the identifier, the second instance. 
 
     
     
       15. The method as recited in  claim 6 , wherein the data object comprises at least a portion of one or more of: (a) a video, (b) an audio recording, or (c) a text file. 
     
     
       16. One or more non-transitory computer-accessible storage media storing program instructions that when executed on or across one or more processors cause one or more computer systems to:
 generate, from a data object, a first set of data units, wherein using the first set of data units respective unique instances of the data object can be reconstructed from respective subsets of the first set of data units; 
 store the first set of data units associated with the data object; 
 identify, corresponding to a first request for at least a portion of the data object, a first subset of the first set, wherein the first subset meets a uniqueness criterion for reconstructing an instance of at least a portion of the data object with respect to other subsets of the first set that are used to respond to other requests for at least the portion of the data object, wherein the uniqueness criterion comprises a requirement that respective members of the first subset and respective members of respective ones of the other subsets differ one to another by at least one data unit of the first set of data units; and 
 cause a first instance of at least the portion of the data object to be reconstructed from the first subset. 
 
     
     
       17. The one or more non-transitory computer-accessible storage media as recited in  claim 16 , storing further program instructions that when executed on or across one or more processors further cause the one or more computer systems to:
 generate the first set of data units using a coding algorithm, wherein the coding algorithm comprises one or more of: a Reed-Solomon erasure-coding algorithm, an XOR (exclusive OR) based coding algorithm, a network coding algorithm, or a Mojette coding algorithm. 
 
     
     
       18. The one or more non-transitory computer-accessible storage media as recited in  claim 16 , storing further program instructions that when executed on or across one or more processors further cause the one or more computer systems to:
 generate the first set of data units using a coding algorithm, wherein one or more parameters of the coding algorithm are selected based at least in part on one or more of: (a) an expected demand for the data object, (b) a size of the data object, (c) a reliability requirement, (d) an availability requirement, or (e) a geographical distribution requirement. 
 
     
     
       19. The one or more non-transitory computer-accessible storage media as recited in  claim 16 , storing further program instructions that when executed on or across one or more processors further cause the one or more computer systems to:
 subdivide the data object into a plurality of segments, wherein the first set of data units includes at least one segment of the plurality of segments. 
 
     
     
       20. The one or more non-transitory computer-accessible storage media as recited in  claim 16 , storing further program instructions that when executed on or across one or more processors further cause the one or more computer systems to:
 subdivide the data object into a plurality of segments; 
 generate, using one or more transformation functions, a plurality of derived data units from the plurality of segments, wherein the first set of data units (a) includes one or more derived data units and (b) does not include segments of the plurality of segments.