Distributed object storage system

• US 8,386,840 B2
• Filed: 10/28/2011
• Issued: 02/26/2013
• 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: Stougie, Bastiaan, De Schrijver, Frederik, Slootmaekers, Romain Raymond Agnes, De Spiegeleer, Kristof Mark Guy, Van Eetvelde, Wouter, Damad, Joost Yervante, De Wispelaere, Wim
• Primary Examiner(s): MASKULINSKI, MICHAEL C
• Application Number:
  US13/283,650
• Publication Number:
  US 20120166487A1
• Time in Patent Office: 487 Days
• Field of Search: 714/6.2
• US Class Current: 714/6.2
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems

Abstract

The invention concerns a distributed object storage system (1) comprising a maintenance agent (740) instructing an encoding module (400) to disassemble a repair data object into a specific number of repair sub blocks, this specific number being equal to or greater than said number of missing sub blocks and less then the predetermined number of sub blocks during a regular storage operation.

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, wherein said desired spreading width consists of 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; and

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, such that said data object can 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, 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 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,

a monitoring agent, operably connected to said storage nodes when monitoring said data object, and operable to;

provide a repair data object identifier of a repair data object, wherein said repair data object identifier corresponds to said data object identifier and said repair data object corresponds to said data object when said data object is not correctly stored in said distributed object storage system; and

subsequently create a repair task comprising said repair object identifier,

and wherein;

the distributed object storage system further comprises a maintenance agent operably connected to said controller node when repairing said repair data object, and operable to perform the following steps when executing said repair task;

said maintenance agent determining said repair data object identifier comprised within said repair task;

said maintenance agent instructing said clustering module to retrieve said predetermined number of sub blocks comprising said repair data object identifier, said clustering module subsequently retrieving a number of collected sub blocks equal to or greater then said predetermined multiple of said minimal spreading requirement;

said maintenance agent determining a number of missing sub blocks which corresponds to the number of sub blocks said clustering module is not able to collect;

said maintenance agent instructing said decoding module to assemble said repair data object from said number of collected sub blocks;

said maintenance agent instructing said encoding module to disassemble said repair data object into a specific number of repair sub blocks, said specific number being equal to or greater than said number of missing sub blocks and less then said predetermined number of sub blocks; and

said maintenance agent instructing said spreading module to store said number of repair sub blocks, said spreading module subsequently storing said number of repair sub blocks, such that said repair sub blocks and said collected sub blocks are stored on a number of said storage elements that is larger or equal to said desired spreading width.

2. A distributed object storage system according to claim 1, wherein said specific number is equal to said number of missing sub blocks augmented by a safety margin.

3. A distributed object storage system according to claim 2, wherein said safety margin is equal to zero.

4. A distributed object storage system according to claim 3, wherein said controller node is operable to consult said metadata storage to determine on which storage elements said sub blocks of said data object can be retrieved, and said consultation is a consultation of said central metadata storage.

5. A distributed object storage system according to claim 1, wherein said distributed object storage system further comprises a metadata storage, said encoding module and/or said spreading module adding to said metadata storage and wherein metadata for said data object stored comprises:

said data object identifier;

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

an identifier for the type of encoding that was used to disassemble said data object.

6. A distributed object storage system according to claim 5, wherein said controller node comprises a central metadata storage.

7. A distributed object storage system according to claim 6, wherein said spreading module is operable to add to said central metadata storage said metadata for each data object stored by said controller node.

8. A distributed object storage system according to claim 6, wherein said plurality of storage nodes each comprise a local metadata storage, said spreading module adding to said respective local metadata storage, and said metadata for each data object being stored in said corresponding storage node.

9. A distributed object storage system according to claim 8, wherein said metadata further comprises a version number that is incremented every time said data object is stored by said spreading module.

10. A distributed object storage system according to claim 9, wherein said controller node retrieves said metadata from said local metadata storages and adds the metadata for each data object comprising the highest version number to said central metadata storage.

11. A distributed object storage system according to claim 9, wherein said controller node is operable to consult said metadata storage to determine on which storage elements said sub blocks of said data object can be retrieved, and said consultation is a federated search of one or more of said local metadata storages, and wherein during said federated search said controller node retrieves said metadata of said local metadata storages that are consulted and adds said metadata for each data object comprising the highest version number to said central metadata storage.

12. A distributed object storage system according to claim 8, wherein said controller node is operable to consult said metadata storage to determine on which storage elements said sub blocks of said data object can be retrieved, and said consultation is a federated search of one or more of said local metadata storages.

13. A distributed object storage system according to claim 5, wherein said controller node is operable to consult said metadata storage to determine on which storage elements said sub blocks of said data object can be retrieved.

14. A distributed object storage system according to claim 5, wherein said distributed object storage system further comprises a garbage collection agent operably connected to said storage nodes when performing a garbage collection operation, and operable to perform the following steps during a garbage collection operation:

retrieving the object identifier of at least one of said sub blocks stored on said storage element;

verifying whether said data object corresponding to said retrieved object identifier corresponds to a data object stored in said distributed object storage system; and

removing said sub blocks for which said verification indicates that said corresponding data object is not stored in said distributed object storage system.

15. A distributed object storage system according to claim 14, wherein said verification indicates that said corresponding data object is not stored in said distributed object storage system if said object identifier is not present in said metadata storage.

16. A distributed object storage system according to claim 1, wherein said monitoring agent is operable to monitor availability of said data object by:

instructing said clustering module to retrieve said predetermined number of said redundant sub blocks; and

providing said repair data object identifier if at least one of said redundant sub blocks cannot be retrieved.

17. A distributed object storage system according to claim 1, wherein said monitoring agent is operable to monitor availability of said data object by:

checking the status of said storage elements; and

providing said repair data object identifier if at least one of said redundant sub blocks is stored on a storage element of which the status indicates it is unavailable.

18. A distributed object storage system according to claim 1, wherein said monitoring agent is operable to monitor availability of said data object by:

checking the status of said storage elements;

storing the status of said storage elements in a central infrastructure database comprising infrastructure metadata, said infrastructure metadata comprising;

an identifier of each said storage element; and

the status of each said storage element (300),

providing said repair data object identifier if at least one of said redundant sub blocks is stored on a storage element that the infrastructure metadata indicates is unavailable.

19. A distributed object storage system according to claim 18, wherein said maintenance agent, when instructing said clustering module to retrieve said predetermined number of sub blocks comprising said repair data object identifier, is operable to further instruct said clustering module to consult said central infrastructure database, said clustering module subsequently retrieving a number of stored sub blocks equal to or greater then said predetermined multiple of said minimal spreading requirement exclusively from said storage elements for which the status in said infrastructure metadata indicates availability.

20. A distributed object storage system according to claim 18 wherein said monitoring agent is operable to provide said repair data object identifier if at least one of said redundant sub blocks is stored on a storage element of which the infrastructure metadata indicates it is unavailable by combining both the metadata of said data object and the infrastructure metadata of said storage elements.

21. A distributed object storage system according to any of the preceding claims, wherein

said encoding module is further operable to generate a predetermined number of checksums of said redundant sub blocks when disassembling said data object into said predetermined number of redundant sub blocks;

said spreading module is further operable to store said predetermined number of checksums together with their corresponding redundant sub blocks on said storage elements; and

said monitoring agent is operable to monitor availability of said data object by;

checking said checksums; and

providing said repair data object identifier if at least one of said redundant sub blocks is stored on a storage element together with an invalid checksum.

22. A distributed object storage method implemented on a distributed object storage system, said 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, wherein said desired spreading width consists of 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; and

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, such that said data object can 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, 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 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,

a monitoring agent, operably connected to said storage nodes when monitoring said data object, and operable to;

provide a repair data object identifier of a repair data object, wherein said repair data object identifier corresponds to said data object identifier and said repair data object corresponds to said data object when said data object is not correctly stored in said distributed object storage system; and

subsequently create a repair task comprising said repair object identifier, and

a maintenance agent operably connected to said controller node when repairing said repair data object, and operable to perform the following steps when executing said repair task,

said distributed object storage method comprising the steps of;

(a) said maintenance agent determining said repair data object identifier comprised within said repair task;

(b) said maintenance agent instructing said clustering module to retrieve said predetermined number of sub blocks comprising said repair data object identifier, said clustering module subsequently retrieving a number of collected sub blocks equal to or greater then said predetermined multiple of said minimal spreading requirement;

(c) said maintenance agent determining a number of missing sub blocks which corresponds to the number of sub blocks said clustering module is not able to collect;

(d) said maintenance agent instructing said decoding module to assemble said repair data object from said number of collected sub blocks;

(e) said maintenance agent instructing said encoding module to disassemble said repair data object into a specific number of repair sub blocks, said specific number being equal to or greater than said number of missing sub blocks and less then said predetermined number of sub blocks; and

said maintenance agent instructing said spreading module to store said number of repair sub blocks, said spreading module subsequently storing said number of repair sub blocks, such that said repair sub blocks and said collected sub blocks are stored on a number of said storage elements that is larger or equal to said desired spreading width.

23. A distributed object storage method according to claim 22, wherein said specific number is equal to said number of missing sub blocks augmented by a safety margin.

24. A distributed object storage method according to claim 23, wherein said safety margin is equal to zero.

25. A distributed object storage method according to claim 24, further comprising the step of said controller node consulting said metadata storage to determine on which storage elements said sub blocks of said data object can be retrieved, said consultation being a consultation of said central metadata storage.

26. A distributed object storage method according to claim 22, wherein said distributed object storage system further comprises a metadata storage, said encoding module and/or said spreading module adding to said metadata storage and wherein metadata for said data object stored comprises:

said data object identifier;

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

an identifier for the type of encoding that was used to disassemble said data object.

27. A distributed object storage method according to claim 26, wherein said controller node comprises a central metadata storage.

28. A distributed object storage method according to claim 27, further comprising the step of said spreading module adding to said central metadata storage said metadata for each data object stored by said controller node.

29. A distributed object storage method according to claim 27, wherein said plurality of storage nodes each comprise a local metadata storage, and further comprising the steps of said spreading module adding to said respective local metadata storage, and storing said metadata for each data object in said corresponding storage node.

30. A distributed object storage method according to claim 29, further comprising the step of incrementing a version number every time said data object is stored by said spreading module.

31. A distributed object storage method according to claim 30, further comprising the step of said controller node retrieving said metadata from said local metadata storages and adding the metadata for each data object comprising the highest version number to said central metadata storage.

32. A distributed object storage method according to claim 30, further comprising the step of said controller node consulting said metadata storage to determine on which storage elements said sub blocks of said data object can be retrieved, said consultation being a federated search of one or more of said local metadata storages, and wherein during said federated search said controller node retrieves said metadata of said local metadata storages that are consulted and adds said metadata for each data object comprising the highest version number to said central metadata storage.

33. A distributed object storage method according to claim 29, further comprising the steps of said controller node consulting said metadata storage to determine on which storage elements said sub blocks of said data object can be retrieved, said consultation being a federated search of one or more of said local metadata storages.

34. A distributed object storage method according to claim 26, further comprising the step of said controller node consulting said metadata storage to determine on which storage elements said sub blocks of said data object can be retrieved.

35. A distributed object storage method according to claim 26, wherein said distributed object storage system further comprises a garbage collection agent operably connected to said storage nodes when performing a garbage collection operation, and said garbage collection agent performing the following steps during a garbage collection operation:

retrieving the object identifier of at least one of said sub blocks stored on said storage element;

verifying whether said data object corresponding to said retrieved object identifier corresponds to a data object stored in said distributed object storage system; and

removing said sub blocks for which said verification indicates that said corresponding data object is not stored in said distributed object storage system.

36. A distributed object storage method according to claim 35, wherein said verification indicates that said corresponding data object is not stored in said distributed object storage system if said object identifier is not present in said metadata storage.

37. A distributed object storage method according to claim 22, further comprising the step of said monitoring agent monitoring availability of said data object by:

instructing said clustering module to retrieve said predetermined number of said redundant sub blocks; and

providing said repair data object identifier if at least one of said redundant sub blocks cannot be retrieved.

38. A distributed object storage method according to claim 22, further comprising the step of said monitoring agent monitoring availability of said data object by:

checking the status of said storage elements; and

providing said repair data object identifier if at least one of said redundant sub blocks is stored on a storage element of which the status indicates it is unavailable.

39. A distributed object storage method according to claim 22, further comprising the step of said monitoring agent monitoring availability of said data object by:

checking the status of said storage elements;

storing the status of said storage elements in a central infrastructure database comprising infrastructure metadata, said infrastructure metadata comprising;

an identifier of each said storage element; and

the status of each said storage element (300),

providing said repair data object identifier if at least one of said redundant sub blocks is stored on a storage element that the infrastructure metadata indicates is unavailable.

40. A distributed object storage method according to claim 39, further comprising the step of said maintenance agent, when instructing said clustering module to retrieve said predetermined number of sub blocks comprising said repair data object identifier, further instructing said clustering module to consult said central infrastructure database, said clustering module subsequently retrieving a number of stored sub blocks equal to or greater then said predetermined multiple of said minimal spreading requirement exclusively from said storage elements for which the status in said infrastructure metadata indicates availability.

41. A distributed object storage method according to claim 39, further comprising the step of said monitoring agent providing said repair data object identifier if at least one of said redundant sub blocks is stored on a storage element of which the infrastructure metadata indicates it is unavailable by combining both the metadata of said data object and the infrastructure metadata of said storage elements.

42. A distributed object storage method according to claim 22, further comprising the steps of

said encoding module generating a predetermined number of checksums of said redundant sub blocks when disassembling said data object into said predetermined number of redundant sub blocks;

said spreading module storing said predetermined number of checksums together with their corresponding redundant sub blocks on said storage elements; and

said monitoring agent monitoring availability of said data object by;

checking said checksums; and

providing said repair data object identifier if at least one of said redundant sub blocks is stored on a storage element together with an invalid checksum.