Object storage system for an unreliable storage medium
A method and computer device for storage and retrieval of a data object on a storage medium. The method includes steps of disassembling the data object into a predetermined number of redundant sub blocks, storing the redundant sub blocks on the storage medium, retrieving at least a predetermined multiple of a minimal spreading requirement of the redundant sub blocks from the storage medium, and assembling the data object from any combination of a particular number of the redundant sub blocks, the particular number corresponding to a predetermined multiple of a minimal spreading requirement. The computer device includes modules for performing the steps.
1. A distributed storage system, comprising:
a plurality of storage elements; and
control circuitry configured to:
receive a data item, via a communication network, from a device that requests storage of the data item;
determine a size of the data item;
in response to determining that the size of the data item is less than a first predetermined threshold:
generate replicas of the data item as redundant data elements in accordance with a spreading parameter;
in response to determining that the size of the data item is greater than or equal to the first predetermined threshold and less than a second predetermined threshold:
divide the data item into data blocks based on the spreading parameter; and
append encoding information to each of the data blocks to generate redundant data elements;
in response to determining that the size of the data item is greater than or equal to the second predetermined threshold:
divide the data item into a plurality of sections of predetermined length;
divide each section into data blocks based on the spreading parameter; and
append encoding information to each of the data blocks of each section to generate redundant data elements; and
store the redundant data elements among the plurality of storage elements.
2. The distributed storage system of claim 1 , wherein the encoding information is generated by processing the data blocks with an erasure coding algorithm.
3. The distributed storage system of claim 1 , wherein the control circuitry is further configured to, in response to determining that the size of the data item is greater than or equal to the second predetermined threshold, append a unique identifier of the data item and an identifier offset to each of the plurality of sections to identify each of the plurality of sections as corresponding to the data item.
4. The distributed storage system of claim 3 , wherein the control circuitry is further configured to retrieve one of the plurality of sections that has a unique identifier and an identifier offset matching a unique identifier and an identifier offset included in a retrieval request from the device.
5. The distributed storage system of claim 1 , wherein the control circuitry is further configured to, in response to determining that the size of the data item is greater than or equal to the second predetermined threshold, pad a last section of the plurality of sections when a length of the last section is less than the predetermined length.
6. The distributed storage system of claim 1 , wherein the control circuitry is further configured to append a cyclic redundancy check (CRC) code to each of the redundant data elements.
7. The distributed storage system of claim 6 , wherein the control circuitry is further configured to generate the CRC code by:
dividing the data item into intermediate blocks; and
performing exclusive-OR operations on the intermediate blocks.
8. The distributed storage system of claim 1 , wherein:
the control circuitry is further configured to generate a distributed key for each of the plurality of storage elements;
the distributed key identifies redundant data elements stored in the plurality of storage elements; and
the distributed key is distributed among the plurality of storage elements.
9. The distributed storage system of claim 1 , wherein the control circuitry is further configured to retrieve at least one replica of the data item from the plurality of storage elements upon receipt of a retrieval request from the device.
10. The distributed storage system of claim 9 , wherein:
at least a portion of the plurality of storage elements are distributed in different geographical areas; and
the control circuitry is further configured to retrieve the at least one replica from a storage element geographically located closest to the device.
11. The distributed storage system of claim 1 , wherein:
the control circuitry is further configured to retrieve a minimum number of redundant data elements from at least a subset of the plurality of storage elements based on receipt of a retrieval request from the device; and
the minimum number corresponds to a minimum number of redundant data elements required for reconstruction of the data item and being a multiple of the spreading parameter.
12. The distributed storage system of claim 1 , wherein the communication network is a wireless communication network.
13. The distributed storage system of claim 1 , wherein:
the device is a wireless telephone, a computer or a personal digital assistant; and
the device executes an application to communicate with the distributed storage system.
14. The distributed storage system of claim 1 , wherein the plurality of storage elements includes partitions in a single storage device.
15. The distributed storage system of claim 14 , wherein the single storage device includes a solid state drive.
16. A method of storing a data item in a distributed storage system, comprising:
receiving, with control circuitry, the data item from a device via a communication network, the device requesting storage of the data item;
determining, with the control circuitry, a size of the data item;
in response to determining that the size of the data item is less than a first predetermined threshold:
generating, with the control circuitry, replicas of the data item as redundant data elements in accordance with a spreading parameter;
in response to determining that the size of the data item is greater than or equal to the first predetermined threshold and less than a second predetermined threshold:
dividing, by the control circuitry, the data item into data blocks based on the spreading parameter; and
appending, by the control circuitry, encoding information to each of the data blocks to generate redundant data elements;
in response to determining that the size of the data item is greater than or equal to the second predetermined threshold:
dividing, by the control circuitry, the data item into a plurality of sections of predetermined length;
dividing, by the control circuitry, each section into data blocks based on the spreading parameter; and
appending, by the control circuitry, encoding information to each of the data blocks of each section to generate redundant data elements; and
storing, by the control circuitry, the redundant data elements among a plurality of storage elements.
17. The method of claim 16 , further comprising generating a distributed key for each of the plurality of storage elements, the distributed key identifying redundant data elements stored in the plurality of storage elements, the distributed key being distributed among the plurality of storage elements.
18. The method of claim 16 , further comprising appending a unique identifier of the data item and an identifier offset to each of the plurality of sections to identify each of the plurality of sections as corresponding to the data item.
19. A distributed storage system, comprising:
means for receiving a data item, via a communication network, from a device that requests storage of the data item;
in response to the size of the data item being less than a first predetermined threshold, means for:
generating replicas of the data item as redundant data elements in accordance with a spreading parameter;
in response to the size of the data item being greater than or equal to the first predetermined threshold and less than a second predetermined threshold, means for:
dividing the data item into data blocks based on the spreading parameter; and
appending encoding information to each of the data blocks to generate redundant data elements;
in response to the size of the data item being greater than or equal to the second predetermined threshold, means for:
dividing the data item into a plurality of sections of predetermined length;
dividing each section into data blocks based on the spreading parameter; and
appending encoding information to each of the data blocks of each section to generate redundant data elements; and
means for storing a plurality of redundant data elements.
20. The distributed storage system of claim 19 , further comprising means for appending a unique identifier of the data item and an identifier offset to each of the plurality of sections to identify each of the plurality of sections as corresponding to the data item.