Object storage system for an unreliable storage medium

• US 10,725,884 B2
• Filed: 12/13/2017
• Issued: 07/28/2020
• Est. Priority Date: 12/27/2010
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: De Schrijver, Frederik, Slootmaekers, Romain Raymond Agnes, Stougie, Bastiaan, Damad, Joost Yervante, De Wispelaere, Wim, Van Eetvelde, Wouter, De Vylder, Bart
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US15/841,116
• Publication Number:
  US 20180101462A1
• Time in Patent Office: 958 Days
• Field of Search: 707652
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

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.

Claims

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.