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;
generate redundant data elements by:
in response to determining that the size of the data item is less than a first predetermined threshold:
generating replicas of the data item 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 the data item into data blocks based on the spreading parameter; and
processing the data blocks with an erasure coding algorithm;
in response to determining that the size of the data item is greater than or equal to the second predetermined threshold:
dividing the data item into a plurality of sections of predetermined length;
dividing each section into data blocks based on the spreading parameter; and
processing the data blocks with an erasure coding algorithm; and
store the redundant data elements among the plurality of storage elements.
2. The distributed storage system of claim 1 , wherein the control circuitry is further configured, 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.
3. The distributed storage system of claim 2 , 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.
4. 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.
5. 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 prior to storing the redundant data elements among the plurality of storage elements.
6. The distributed storage system of claim 5 , 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.
7. 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.
8. 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.
9. The distributed storage system of claim 8 , 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.
10. 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 is a multiple of the spreading parameter.
11. The distributed storage system of claim 10 , wherein the communication network is a wireless communication network.
12. The distributed storage system of claim 10 , 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.
13. The distributed storage system of claim 1 , wherein the plurality of storage elements includes partitions in a single storage device.
14. The distributed storage system of claim 13 , wherein the single storage device includes a solid-state drive.
15. 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;
generating redundant data elements by:
in response to determining that the size of the data item is less than a first predetermined threshold:
generating replicas of the data item 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 the data item into data blocks based on the spreading parameter; and
processing the data blocks with an erasure coding algorithm;
in response to determining that the size of the data item is greater than or equal to the second predetermined threshold:
dividing the data item into a plurality of sections of predetermined length;
dividing each section into data blocks based on the spreading parameter; and
processing the data blocks with an erasure coding algorithm; and
storing, by the control circuitry, the redundant data elements among a plurality of storage elements.
16. The method of claim 15 , 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.
17. The method of claim 15 , 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.
18. A distributed storage system, comprising:
means for receiving a data item from a device that requests storage of the data item;
means for generating redundant data elements by:
in response to a size of the data item being less than a first predetermined threshold:
generating replicas of the data item 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:
dividing the data item into data blocks based on the spreading parameter; and
processing the data blocks with an erasure coding algorithm;
in response to the size of the data item being greater than or equal to the second predetermined threshold:
dividing the data item into a plurality of sections of predetermined length;
dividing each section into data blocks based on the spreading parameter; and
processing the data blocks with an erasure coding algorithm; and
means for storing the redundant data elements in a plurality of storage elements.
19. The distributed storage system of claim 18 , further comprising means for 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.
20. The distributed storage system of claim 18 , 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.