Distributed object storage system comprising performance optimizations

• US 8,738,582 B2
• Filed: 12/23/2011
• Issued: 05/27/2014
• Est. Priority Date: 12/27/2010
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Amplidata N.V. (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:
  US13/976,061
• Publication Number:
  US 20130275381A1
• Time in Patent Office: 886 Days
• Field of Search: 707/652, 707/693, 707/699, 711/114, 714/6.2
• US Class Current: 707/652
• 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 distributed object storage system includes several performance optimizations with respect to storing very small data objects, very large data objects and CRC calculations.

Claims

1. A distributed object storage system which, according to a first storage and retrieval option, comprising:

a plurality of redundant storage elements, configured to store and retrieve a data object comprising a data object identifier in form of a predetermined number of redundant sub blocks comprising said data object identifier, said predetermined number of redundant sub blocks corresponding to a predetermined multiple of a desired spreading width, said predetermined multiple of the desired spreading width consisting of the sum of;

(a) a minimal spreading requirement, corresponding to a minimal number of storage elements that must store sub blocks of said data object and are not allowed to fail; and

(b) a maximal concurrent failures tolerance, corresponding to a number of storage elements that must store sub blocks of said data object and are allowed to fail concurrently;

each one of said redundant sub blocks comprising;

(a) encoded data of equal size of the data object divided by a factor equal to said predetermined multiple of said minimal spreading requirement; and

(b) decoding data, enabling said data object to be decoded from any combination of a minimum number of said redundant sub blocks, the minimum number corresponding to said predetermined multiple of said minimal spreading requirement;

a plurality of storage nodes each comprising a share of said plurality of redundant storage elements; and

at least one controller node, operably connected to or comprised within said plurality of storage nodes when storing or retrieving said data object, comprising;

(a) an encoding module configured to disassemble said data object into said predetermined number of redundant sub blocks;

(b) a spreading module configured to store said predetermined number of said redundant sub blocks on a number of said storage elements being larger or equal to said desired spreading width;

(c) a clustering module configured to retrieve at least said predetermined multiple of said minimal spreading requirement of said redundant sub blocks from a plurality of said storage elements; and

(d) a decoding module configured to assemble said data object from any combination of a minimum number of said redundant sub blocks, the minimum number corresponding to said predetermined multiple of said minimal spreading requirement;

wherein, according to a second storage and retrieval option of said distributed object storage system;

(a) said plurality of redundant storage elements, are further configured to store and retrieve said data object comprising a data object identifier in form of a predetermined plurality of replication copies of said data object comprising said data object identifier, said predetermined plurality corresponding to said desired spreading width, each one of said replication copies comprising an exact copy of said data object;

(b) said encoding module is further configured to replicate said data object into said predetermined plurality of said replication copies;

(c) said spreading module is further configured to store said predetermined plurality of said replication copies on a corresponding plurality of said storage elements;

(d) said clustering module is further configured to retrieve at least one of said predetermined plurality of said replication copies from said corresponding plurality of said storage elements; and

(e) said decoding module is further configured to provide said data object from any one of said replication copies; and

wherein said distributed object storage system is operated according to said first storage and retrieval option if the size of said data object is equal to or larger than a predetermined lower data object size threshold, and is operated according to said second storage and retrieval option if the size of said data object is smaller than said predetermined lower data object size threshold.

2. The distributed object storage system according to claim 1, wherein said predetermined lower data object size threshold is 2 Megabytes or lower.

3. The distributed object storage system according to claim 1, wherein each of said plurality of redundant storage elements comprises a distributed key value store in which said replication copies are stored.

4. The distributed object storage system according to claim 3, wherein said distributed key value store further comprises metadata of data objects stored on said storage element, said metadata comprising:

said data object identifier;

a list of identifiers of the storage elements on which sub blocks or replication copies of said data object are stored; and

an identifier indicating a type of storage and retrieval option that was used to store said data object.

5. The distributed object storage system according to claim 1, wherein, according to a third storage and retrieval option of said distributed object storage system:

said encoding module is further configured during a storage operation to split said data object into a plurality of sequential data objects, each sequential data object having an associated sequential data object identifier that comprises said data object identifier and a data object offset identifier corresponding to the respective sequential data object, each of said sequential data objects subsequently being stored according to said first storage and retrieval option;

said decoding module is further configured during a retrieval operation to concatenate said plurality of sequential data objects in a correct order by means of said data object offset identifiers such that the concatenated sequential data objects form said data object, each of said sequential data objects previously being retrieved according to said first storage and retrieval option;

said distributed object storage system is operated according to said third storage and retrieval option if the size of said data object is larger than a predetermined upper data object size threshold.

6. The distributed object storage system according to claim 5, wherein said predetermined upper data object size threshold is equal to or larger than 32 Megabytes.

7. The distributed object storage system according to claim 5, wherein, according to said third storage and retrieval option of said distributed object storage system:

during a storage operation, a plurality of said sequential data objects are stored in parallel according to said first storage and retrieval option; and

during a retrieval operation, a plurality of said sequential data objects are retrieved in parallel according to said first storage and retrieval option.

8. The distributed object storage system according to claim 5, wherein, according to said third storage and retrieval option of said distributed object storage system, the distributed object storage system is configured to store and/or retrieve a specific selection of said sequential data objects by means of said data object offset identifiers.

9. The distributed object storage system according to claim 1, wherein, according to said first storage and retrieval option of said distributed object storage system:

said encoding module is further configured to generate a predetermined number of Cyclic Redundancy Checks (CRCs) of said redundant sub blocks, when disassembling said data object into said predetermined number of redundant sub blocks;

said spreading module is further configured to store said predetermined number of CRCs together with their corresponding redundant sub blocks on said plurality of redundant storage elements;

wherein

said encoding module is configured to calculate each redundant sub block by means of a predetermined combination of XOR operations on intermediate data blocks;

said encoding module is further configured to generate a CRC for each of said intermediate data blocks; and

said encoding module is further configured to calculate said predetermined number of CRCs of said redundant sub blocks by applying said predetermined combination of XOR operations to the respective CRCs of said intermediate data blocks.

10. The distributed object storage system according to claim 9, wherein, according to said first storage and retrieval option of said distributed object storage system:

said clustering module is further configured to retrieve said respective CRCs of said redundant sub blocks; and

said decoding module is further configured to assemble said data object from intermediate data blocks which are generated from said redundant sub blocks by means of a predetermined combination of XOR operations; and

said decoding module is further configured to calculate the CRCs of said intermediate data blocks by applying said predetermined combination of XOR operations to the respective CRCs of said redundant sub blocks.

11. The distributed object storage system according to claim 9, wherein, according to said first storage and retrieval option of said distributed object storage system:

said decoding module is further configured to form said data object from a concatenation of a plurality of said intermediate data blocks; and

said decoding module is further configured to calculate a CRC of said data object from the CRCs of the respective intermediate data blocks.

12. The distributed object storage system according to claim 5, wherein, according to said third storage and retrieval option of said distributed object storage system, said decoding module is further configured, during a retrieval operation, to calculate a CRC of said data object from CRCs of the respective sequential data objects.

13. A method for storage and retrieval of a data object on a distributed object storage system, the data object having a size, the method comprising:

if the size of the data object is greater than or equal to a predetermined lower data object size threshold;

disassembling the data object into a predetermined number of redundant sub blocks, the predetermined number of redundant sub blocks corresponding to a predetermined multiple of a desired spreading width, the predetermined multiple of the desired spreading width consisting of the sum of;

(a) a minimal spreading requirement corresponding to a minimal number of storage elements that must store sub blocks of the data object and are not allowed to fail, and (b) a maximal concurrent failures tolerance corresponding to a number of storage elements that must store sub blocks of the data object and are allowed to fail concurrently;

each one of the redundant sub blocks comprising;

(a) encoded data of equal size of the data object divided by a factor equal to the predetermined multiple of the minimal spreading requirement; and

(b) decoding data, enabling the data object to be decoded from any combination of a particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement;

storing the predetermined number of redundant sub blocks on a number of redundant storage elements, the number of redundant storage elements being greater than or equal to the desired spreading width;

retrieving any combination of the particular number of the redundant sub blocks from the number of storage elements; and

assembling the data object from the retrieved redundant sub blocks;

otherwise, if the size of the data object is less than the predetermined lower data object size threshold;

replicating the data object into a predetermined number of replication copies corresponding to the desired spreading width, each one of the replication copies comprising an exact copy of the data object;

storing the predetermined number of replication copies on a corresponding plurality of storage elements;

retrieving any of the replication copies from the corresponding plurality of the storage elements; and

providing the data object from the replication copy.

14. The method recited in claim 13, further comprising:

if the size of the data object is greater than or equal to a predetermined upper data object size threshold;

splitting the data object into a plurality of sequential data objects, each sequential data object having an associated sequential data object identifier that comprises the data object identifier and a data object offset identifier corresponding to the respective sequential data object;

for each sequential data object;

disassembling the sequential data object into a predetermined number of redundant sub blocks, the predetermined number of redundant sub blocks corresponding to a predetermined multiple of a desired spreading width, the predetermined multiple of the desired spreading width consisting of the sum of;

(a) a minimal spreading requirement corresponding to a minimal number of storage elements that must store sub blocks of the sequential data object and are not allowed to fail, and (b) a maximal concurrent failures tolerance corresponding to a number of storage elements that must store sub blocks of the sequential data object and are allowed to fail concurrently;

each one of the redundant sub blocks comprising;

(a) encoded data of equal size of the sequential data object divided by a factor equal to the predetermined multiple of the minimal spreading requirement; and

(b) decoding data, enabling the sequential data object to be decoded from any combination of a particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement;

storing the predetermined number of redundant sub blocks on a number of redundant storage elements, the number of redundant storage elements being greater than or equal to the desired spreading width;

retrieving any combination of the particular number of the redundant sub blocks from the number of storage elements; and

assembling the sequential data object from the retrieved redundant sub blocks; and

concatenating the plurality of sequential data objects in a correct order by means of the data object offset identifiers such that the concatenated sequential data objects form the data object.

15. The method recited in claim 14, wherein the steps of storing the predetermined number of redundant sub blocks for each sequential data object are performed in parallel.

16. The method recited in claim 14, wherein the steps of retrieving any combination of the particular number of the redundant sub blocks for each sequential data object are performed in parallel.

17. The method recited in claim 13, wherein

disassembling the data object into the predetermined number of redundant sub blocks comprises:

calculating each redundant sub block by means of a predetermined combination of XOR operations on intermediate data blocks;

generating a CRC for each of the intermediate data blocks;

calculating a predetermined number of CRCs of the redundant sub blocks by applying the predetermined combination of XOR operations to the respective CRCs of the intermediate data blocks; and

storing the predetermined number of redundant sub blocks comprises storing the predetermined number of CRCs together with their corresponding redundant sub blocks on the plurality of redundant storage elements.

18. The method recited in claim 17, wherein

retrieving any combination of the particular number of the redundant sub blocks comprises retrieving the respective CRCs of the redundant sub blocks;

and

assembling the data object from the retrieved redundant sub blocks comprises;

assembling the data object from intermediate data blocks which are generated from the redundant sub blocks by means of the predetermined combination of XOR operations; and

calculating the CRCs of the intermediate data blocks by applying the predetermined combination of XOR operations to the respective CRCs of the redundant sub blocks.

19. The method recited in claim 17, wherein assembling the data object from the retrieved redundant sub blocks comprises:

forming the data object from a concatenation of a plurality of the intermediate data blocks; and

calculating a CRC of the data object from the CRCs of the respective intermediate data blocks.

20. A computer device for storage and retrieval of a data object on a distributed object storage system, the computer device comprising:

a processor; and

memory having stored thereon instructions that when processed by the processor cause a method for storage and retrieval of a data object on a distributed object storage system to be performed, the method comprising;

if a size of the data object is greater than or equal to a predetermined lower data object size threshold;

disassembling the data object into a predetermined number of redundant sub blocks, the predetermined number of redundant sub blocks corresponding to a predetermined multiple of a desired spreading width, the predetermined multiple of the desired spreading width consisting of the sum of;

(a) a minimal spreading requirement corresponding to a minimal number of storage elements that must store sub blocks of the data object and are not allowed to fail, and (b) a maximal concurrent failures tolerance corresponding to a number of storage elements that must store sub blocks of the data object and are allowed to fail concurrently;

each one of the redundant sub blocks comprising;

(a) encoded data of equal size of the data object divided by a factor equal to the predetermined multiple of the minimal spreading requirement; and

(b) decoding data, enabling the data object to be decoded from any combination of a particular number of the redundant sub blocks, the particular number corresponding to the predetermined multiple of the minimal spreading requirement;

storing the predetermined number of redundant sub blocks on a number of redundant storage elements, the number of redundant storage elements being greater than or equal to the desired spreading width;

retrieving any combination of the particular number of the redundant sub blocks from the number of storage elements; and

assembling the data object from the retrieved redundant sub blocks;

otherwise, if the size of the data object is less than the predetermined lower data object size threshold;

replicating the data object into a predetermined number of replication copies corresponding to the desired spreading width, each one of the replication copies comprising an exact copy of the data object;

storing the predetermined number of replication copies on a corresponding plurality of storage elements;

retrieving any of the replication copies from the corresponding plurality of the storage elements; and

providing the data object from the replication copy.