Multi-layer encoding for distributed container-based storage of smaller data objects

1. A computer-implemented method, comprising:

setting a level-one spreading divisor (SD 1 ) to a first positive natural number;

setting a level-two spreading divisor (SD 2 ) to a second positive natural number;

dividing a data object into SD 1 first-level data pieces, wherein the data object is subject to multi-level redundant encoded distributed storage;

storing each specific one of the SD 1 first-level data pieces in a corresponding first-level container object on a corresponding first-level storage entity;

storing a redundant encoding of the corresponding first-level container objects in additional first-level container objects of level-one redundancy level (RL 1 ) on additional first-level storage entities of RL 1 , thereby resulting in SD 1 plus RL 1 first-level container objects stored on SD 1 plus RL 1 first-level storage entities, wherein the data object is retrievable from any SD 1 of the SD 1 plus RL 1 first-level container objects; and

on each specific one of the SD 1 plus RL 1 first-level storage entities:

dividing a locally-stored first-level container object into SD 2 local second-level data pieces;

storing each specific one of the SD 2 local second-level data pieces in a corresponding second-level container object on a corresponding second-level storage entity of the specific first-level storage entity, wherein each specific one of the first-level storage entities further comprises SD 2 plus second-level storage entities of level-two redundancy level (RL 2 ); and

storing a redundant encoding of the corresponding second-level container objects in RL 2 additional second-level container objects on RL 2 additional second-level storage entities of the specific first-level storage entity, thereby resulting in SD 2 plus RL 2 second-level container objects stored on SD 2 plus RL 2 second-level storage entities of the specific first-level storage entity, wherein the locally-stored first-level container object is retrievable from any SD 2 of the SD 2 plus RL 2 second-level container objects;

wherein the data object is retrievable in a circumstance in which any specific one of the SD 1 plus RL 1 first-level storage entities is not available, and any specific one of the SD 2 plus RL 2 second-level storage entities of each available first-level storage entity is not available.

2. The computer-implemented method of claim 1 , wherein:

each first-level storage entity comprises a datacenter; and

each second-level storage entity comprises a storage server, a hard disk, or a solid state drive in a corresponding datacenter.

3. The computer-implemented method of claim 1 , further comprising:

maintaining a distributed storage system comprising SD 1 plus RL 1 first-level storage entities, and further comprising SD 2 plus RL 2 second-level storage entities in each first-level storage entity.

4. The computer-implemented method of claim 1 , further comprising:

setting a level-three spreading divisor (SD 3 ) to a third positive natural number;

maintaining a distributed storage system comprising SD 1 plus RL 1 first-level storage entities, SD 2 plus RL 2 second-level storage entities in each first-level storage entity, and SD 3 plus third-level storage entities of level-three redundancy level (RL 3 ) in each second-level storage entity; and

on each specific one of the SD 2 plus RL 2 second-level storage entities:

dividing a locally-stored second-level container object into SD 3 local third-level data pieces;

storing each specific one of the SD 3 local third-level data pieces in a corresponding third-level container object on a corresponding third-level storage entity of the specific second-level storage entity, wherein each specific one of the second-level storage entities further comprises SD 3 plus RL 3 third-level storage entities; and

storing a redundant encoding of the corresponding third-level container objects in RL 3 additional third-level container objects on RL 3 additional third-level storage entities of the specific second-level storage entity, thereby resulting in SD 3 plus RL 3 third-level container objects stored on SD 3 plus RL 3 third-level storage entities of the specific second-level storage entity;

wherein the locally-stored second-level container object is retrievable from any SD 3 of the SD 3 plus RL 3 third-level container objects.

5. The computer-implemented method of claim 1 , wherein storing a redundant encoding of multiple container objects further comprises:

performing a bitwise exclusive or (XOR) of the multiple container objects; and

storing results of the performed bitwise XOR.

6. The computer-implemented method of claim 1 , wherein storing a redundant encoding of multiple container objects further comprises:

performing an erasure encoding of the multiple container objects; and

storing results of the erasure encoding.

7. The computer-implemented method of claim 1 , further comprising:

dividing a second data object into SD 1 first-level data pieces, wherein the second data object is subject to multi-level redundant encoded distributed storage; and

concatenating each specific one of the SD 1 first-level data pieces of the second data object to a corresponding first-level container object on a corresponding first-level storage entity.

8. The computer-implemented method of claim 1 , further comprising:

dividing the data object subject to multi-level redundant encoded distributed storage into SD 1 sets of first-level data pieces;

storing each specific one of the SD 1 sets of first-level data pieces in a corresponding first-level container object on a corresponding first-level storage entity; and

on each specific one of the SD 1 plus RL 1 first-level storage entities:

dividing a locally-stored first-level container object comprising a set of first-level data pieces into SD 2 local subsets of first-level data pieces; and

storing each specific one of the SD 2 local subsets of first-level data pieces in a corresponding second-level container object on a corresponding second-level storage entity of the specific first-level storage entity.

9. The computer-implemented method of claim 1 , further comprising:

setting a value (K) to a natural number greater than or equal to zero and less than or equal to RL 1 .

10. The computer-implemented method of claim 9 , further comprising:

retrieving the data object subject to multi-level redundant encoded distributed storage from SD 1 of the first-level storage entities.

11. The computer-implemented method of claim 10 , further comprising:

retrieving SD 1 minus K data pieces of the data object from SD 1 minus K first-level container objects on SD 1 minus K first-level storage entities;

retrieving K redundant encodings of K data pieces of the data object from K first-level container objects on K first-level storage entities;

decoding K data pieces of the data object using the K redundant encodings and the SD 1 minus K retrieved data pieces; and

concatenating the SD 1 minus K retrieved data pieces and the K decoded data pieces of the data object.

12. The computer-implemented method of claim 9 , further comprising:

replacing a failed first-level storage entity storing a first-level redundantly-encoded container object, wherein replacing the failed first-level storage entity further comprises:

retrieving SD 1 minus K first-level container objects containing non-encoded data from SD 1 minus K first-level storage entities; and

retrieving K redundantly-encoded first-level container objects from K first-level storage entities.

13. The computer-implemented method of claim 12 , further comprising:

creating a first-level redundantly-encoded container object by performing an encoding operation on the SD 1 minus K retrieved first-level container objects; and

storing the first-level redundantly-encoded container object on an additional first-level storage entity.

14. The computer-implemented method of claim 12 , further comprising:

decoding an additional first-level container object containing non-encoded data, using the SD 1 minus K retrieved first-level container objects containing non-encoded data and the K retrieved redundantly-encoded first-level container objects; and

storing the additional first-level container object containing non-encoded data on an additional first-level storage entity.

15. The computer-implemented method of claim 1 , further comprising:

setting SD 1 to 2; and

setting SD 2 to 3.

16. The computer-implemented method of claim 15 , further comprising:

retrieving a data object subject to multi-level redundant encoded distributed storage from two of the first-level storage entities.

17. The computer-implemented method of claim 16 , further comprising:

retrieving a first data piece of the data object from a first first-level container object on a first first-level storage entity;

retrieving a second data piece of the data object from a second first-level container object on a second first-level storage entity; and

concatenating the first and the second retrieved data pieces of the data object.

18. The computer-implemented method of claim 16 , further comprising:

retrieving a first data piece of the data object from a first first-level container object on a first first-level storage entity;

retrieving a redundant encoding of a first data piece and a second data piece of the data object from a second first-level container object on a second first-level storage entity;

decoding the second data piece of the data object using the redundant encoding and the first retrieved data piece; and

concatenating the first and the second data pieces of the data object.

19. A storage system, comprising:

a processor; and

a storage manager stored on a memory and executable by the processor, the storage manager configured to:

set a level-one spreading divisor (SD 1 ) to a first positive natural number;

set a level-two spreading divisor (SD 2 ) to a second positive natural number;

divide a data object into SD 1 first-level data pieces, wherein the data object is subject to multi-level redundant encoded distributed storage;

store each specific one of the SD 1 first-level data pieces in a corresponding first-level container object on a corresponding first-level storage entity;

store a redundant encoding of the corresponding first-level container objects in additional first-level container objects of level-one redundancy level (RL 1 ) on additional first-level storage entities of RL 1 , thereby resulting in SD 1 plus RL 1 first-level container objects stored on SD 1 plus RL 1 first-level storage entities, wherein the data object is retrievable from any SD 1 of the SD 1 plus RL 1 first-level container objects; and

on each specific one of the SD 1 plus RL 1 first-level storage entities:

divide a locally-stored first-level container object into SD 2 local second-level data pieces;

store each specific one of the SD 2 local second-level data pieces in a corresponding second-level container object on a corresponding second-level storage entity of the specific first-level storage entity, wherein each specific one of the first-level storage entities further comprises SD 2 plus second-level storage entities of level-two redundancy level (RL 2 ); and

store a redundant encoding of the corresponding second-level container objects in RL 2 additional second-level container objects on RL 2 additional second-level storage entities of the specific first-level storage entity, thereby resulting in SD 2 plus RL 2 second-level container objects stored on SD 2 plus RL 2 second-level storage entities of the specific first-level storage entity, wherein the locally-stored first-level container object is retrievable from any SD 2 of the SD 2 plus RL 2 second-level container objects;

wherein the data object is retrievable in a circumstance in which any specific one of the SD 1 plus RL 1 first-level storage entities is not available, and any specific one of the SD 2 plus RL 2 second-level storage entities of each available first-level storage entity is not available.

20. An apparatus, comprising:

a processor; and

a storage manager stored on a memory and executable by the processor, the storage manager comprising:

means for setting a level-one spreading divisor (SD 1 ) to a first positive natural number;

means for setting a level-two spreading divisor (SD 2 ) to a second positive natural number;

means for dividing a data object into SD 1 first-level data pieces, wherein the data object is subject to multi-level redundant encoded distributed storage;

means for storing each specific one of the SD 1 first-level data pieces in a corresponding first-level container object on a corresponding first-level storage entity;

means for storing a redundant encoding of the corresponding first-level container objects in additional first-level container objects of level-one redundancy level (RL 1 ) on additional first-level storage entities of RL 1 , thereby resulting in SD 1 plus RL 1 first-level container objects stored on SD 1 plus RL 1 first-level storage entities, wherein the data object is retrievable from any SD 1 of the SD 1 plus RL 1 first-level container objects; and

on each specific one of the SD 1 plus RL 1 first-level storage entities:

means for dividing a locally-stored first-level container object into SD 2 local second-level data pieces;

means for storing each specific one of the SD 2 local second-level data pieces in a corresponding second-level container object on a corresponding second-level storage entity of the specific first-level storage entity, wherein each specific one of the first-level storage entities further comprises SD 2 plus second-level storage entities of level-two redundancy level (RL 2 ); and

means for storing a redundant encoding of the corresponding second-level container objects in RL 2 additional second-level container objects on RL 2 additional second-level storage entities of the specific first-level storage entity, thereby resulting in SD 2 plus RL 2 second-level container objects stored on SD 2 plus RL 2 second-level storage entities of the specific first-level storage entity, wherein the locally-stored first-level container object is retrievable from any SD 2 of the SD 2 plus RL 2 second-level container objects;

wherein the data object is retrievable in a circumstance in which any specific one of the SD 1 plus RL 1 first-level storage entities is not available, and any specific one of the SD 2 plus RL 2 second-level storage entities of each available first-level storage entity is not available.