Hierarchical, distributed object storage system

• US 8,433,849 B2
• Filed: 12/23/2011
• Issued: 04/30/2013
• Est. Priority Date: 12/27/2010
• Status: Expired due to Fees

• Current Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Amplidata N.V. (Western Digital Corporation)
• Inventors: De Schrijver, Frederik, Slootmaekers, Romain Raymond Agnes, Stougie, Bastiaan, De Spiegeleer, Kristof Mark Guy, De Wispelaere, Wim, Van Eetvelde, Wouter
• Primary Examiner(s): Dudek, Jr., Edward
• Assistant Examiner(s): BIRKHIMER, CHRISTOPHER D
• Application Number:
  US13/336,558
• Publication Number:
  US 20120166726A1
• Time in Patent Office: 494 Days
• Field of Search: None
• US Class Current: 711/114
• 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 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

The invention concerns a distributed object storage system (1) that comprises a spreading module (410) which makes a selection of a number of storage elements (300) being larger or equal to a desired spreading width by means of a spreading policy that comprises rules for selecting storage elements (300) in function of a first hierarchy level identifier (70.1) and/or a second hierarchy level identifier (70.2).

Claims

1. A distributed object storage system comprising:

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

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

supplemented with

a maximal concurrent failures tolerance, corresponding to the 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;

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

decoding data, enabling said data object to be decoded from any combination of said redundant sub blocks of which the number corresponds to 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 storage nodes when storing or retrieving said data object, and comprising;

an encoding module operable to disassemble said data object into said predetermined number of redundant sub blocks;

a spreading module operable to store said predetermined number of said redundant sub blocks on a number of said storage elements that is larger or equal to said desired spreading width;

a clustering module operable 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

a decoding module operable to assemble said data object from any combination of said redundant sub blocks of which the number corresponds to said predetermined multiple of said minimal spreading requirement;

each of said plurality of redundant storage elements comprising a unique storage element identifier, said storage element identifier comprising;

a first hierarchy level identifier, which provides an identifier for the storage node comprising said storage element identified by said storage element identifier; and

a second hierarchy level identifier, which provides an identifier for a predetermined selection of a plurality of storage nodes comprising said storage element identified by said storage element identifier; and

said spreading module causing a selection of said number of said storage elements to be larger or equal to said desired spreading width by a spreading policy that comprises rules for selecting storage elements as a function of at least one of said first hierarchy level identifier and said second hierarchy level identifier.

2. The distributed object storage system according to claim 1, wherein said storage element identifier further comprises at least one of a third level hierarchy identifier and further level hierarchy identifiers, which provide an identifier for a predetermined selection of a plurality of said second hierarchy level identifiers or further previous hierarchy level identifiers respectively, and

said spreading policy further comprising rules for selecting said storage elements as a function of at least one of said third hierarchy level identifier and said further hierarchy level identifiers.

3. The distributed object storage system according to claim 1, said spreading policy further comprising rules for whitelisting or blacklisting a plurality of storage elements as a function of one or more of said hierarchy level identifiers included in their corresponding storage element identifier.

4. The distributed object storage system according to claim 1, wherein said spreading module is operable to differentiate the selection of said number of storage elements according to one or more of their respective hierarchy level identifiers as a function of said spreading policy.

5. The distributed object storage system according to claim 1, said spreading module being operable to store said predetermined number of said redundant sub blocks on a number of said storage elements that is larger or equal to said desired spreading width in two distinct phases:

in a first phase the required share of sub blocks is stored on a first number of fast storage elements which corresponds to a safety threshold, said safety threshold being larger than or equal to said minimal spreading requirement; and

in a subsequent second phase the required share of said sub blocks is stored on a second number of remaining unresponsive storage elements so that the total number of storage elements reaches said number being larger or equal to said desired spreading width.

6. The distributed object storage system according to claim 5, wherein said spreading module is operable to perform said subsequent second phase of said storage operation during a configurable, predetermined time period.

7. The distributed object storage system according to claim 5 wherein said spreading module is operable:

in said first phase to store said predetermined number of said redundant sub blocks entirely on said first number of said storage elements; and

in said second phase to move said required share of said sub blocks to said second number of remaining storage elements.

8. The distributed object storage system according to claim 5, wherein said spreading module is operable to temporarily ignore unresponsive storage elements.

9. The distributed object storage system according to claim 8, wherein said spreading module is operable to gradually increase a period of ignorance for said storage elements that remain unresponsive repeatedly.

10. The distributed object storage system according to claim 1, wherein said clustering module is operable to retrieve more sub blocks from the most responsive storage elements.

11. The distributed object storage system according to claim 10, wherein said clustering module is operable to transform a retrieval request for said data object, into a plurality of parallel iterative processes, one for each of said storage element storing sub blocks of said data object, said iterative process retrieving iteratively a predetermined share of said sub blocks stored on said respective storage element until the amount of sub blocks jointly retrieved by said parallel iterative processes is larger than or equal to said predetermined multiple of said minimal spreading requirement.

12. The distributed object storage system according to claim 1, wherein said spreading module is operable to retrieve more sub blocks from the most responsive storage elements.

13. The distributed object storage system according to claim 12, wherein said spreading module is operable to transform a storage request for said data object, into a plurality of parallel iterative processes, one for each of said storage element where sub blocks of said data object need to be stored, said iterative process storing iteratively a predetermined share of said sub blocks to be stored on said respective storage element until the amount of sub blocks jointly stored by said parallel iterative processes is larger than or equal to said predetermined multiple of said minimal spreading requirement.

14. The distributed object storage system according to claim 5, wherein unresponsive storage elements that remain unresponsive for a time period that exceeds a predetermined sleep time period threshold or storage elements that store data objects with a frequency of retrieval below a predetermined sleep frequency threshold are powered down.