Methods and Apparatus for Distributed Data Storage

• US 20120185437A1
• Filed: 11/15/2011
• Published: 07/19/2012
• Est. Priority Date: 09/16/2008
• Status: Active Grant

• Current Assignee: File System Labs LLC
• Original Assignee: File System Labs LLC
• Inventors: Pavlov, Elan, Lachman, Ronald, Ness, Stephen, Critchlow, Roger, Swartz, Robert, Murphy, Timothy S.
• Granted Patent: US 9,098,519 B2
• Time in Patent Office: Days
• 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 16/134 Distributed indices
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 16/1827 Management specifically adapted to NAS management of storage area networks [SAN] G06F3/067
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding

Abstract

A distributed heterogeneous or homogeneous file storage system divides logical responsibility for data from actual control of the data by using separate file and storage managers. Each file manager provides access to stored files and stores metadata associated with each of the files for which it is responsible. A file manager control component allocates responsibilities among file managers, assigns management responsibilities for individual files, and maintains a record of which files are assigned to each manager. Each storage manager is responsible for managing storage of files on data storage devices and maintains a record of the location of each stored file. A storage manager control component allocates responsibilities among storage managers, assigns responsibilities for individual files, and maintains a record of which files and storage devices are assigned to each manager. A client provides user access, initiates actions within the system, and implements a redundant data recovery and reconstruction scheme.

Claims

1. A dynamically scalable redundant distributed storage system, the storage system having a plurality of components, the components comprising:

a plurality of file managers, each file manager having responsibility for providing access to a group of stored files or data blocks and being configured to store metadata associated with each of the files and data blocks for which it is responsible, the metadata including a unique file identifier for each file or data block;

a file manager control component adapted for allocating individual responsibilities among each of the plurality of file managers, the file manager control component being configured to assign file management responsibilities for individual files and data blocks to individual file managers and to maintain a record of which files and data blocks are assigned to each file manager;

a plurality of storage managers, each storage manager having responsibility for managing the storage of files and data blocks on one or more data storage devices for which it is responsible and being configured to maintain a record of the location of each stored file and data block on the data storage devices;

a storage manager control component adapted for allocating individual responsibilities among each of the plurality of storage managers, the storage manager control component being configured to assign file storage responsibilities for individual files among individual storage managers and to maintain a record of which files and data storage devices are assigned to each storage manager; and

at least one client adapted to provide user access to the storage system, the client being configured to initiate actions within the storage system by means of the file manager control component and the storage manager control component, the client further comprising a processor configured to implement a redundant data recovery and reconstruction scheme.

2. The distributed storage system of claim 1, wherein the file manager controller and the storage manager controller are implemented using distributed hash tables.

3. The distributed storage system of claim 2, wherein the distributed hash tables are implemented as lists.

4. The distributed storage system of claim 3, wherein the file manager distributed hash table is implemented as a list, the list comprising an entry for each file manager, each entry comprising a range of unique file identifier values assigned to the files or data blocks for which the file manager is responsible.

5. The distributed storage system of claim 1, wherein the physical devices comprising or hosting the components comprising the storage system are not homogeneous.

6. The distributed storage system of claim 1, wherein at least some of the components of the system are implemented in software using functional programming.

7. The distributed storage system of claim 1, wherein the redundant data recovery and reconstruction scheme employs error correction code methods.

8. The distributed storage system of claim 7, wherein the error correction code methods employ matrix-based erasure codes.

9. The distributed storage system of claim 1, wherein the redundant data recovery and reconstruction scheme employs file replication methods.

10. The distributed storage system of claim 1, wherein a single component may be replaced by a plurality of components.

11. The distributed storage system of claim 1, wherein additional components may be added to the system dynamically while the system is in use.

12. The distributed storage system of claim 1, wherein a component that has failed and then been repaired may be reutilized by the storage system.

13. The distributed storage system of claim 1, wherein a file manager acts as a client.

14. The distributed storage system of claim 1, wherein the system is asynchronous, having no system clock.

15. The distributed storage system of claim 1, wherein the file manager control component and storage manager control component are further configured to perform load balancing.

16. The distributed storage system of claim 1, wherein the level of redundancy required by the redundant data recovery and reconstruction scheme for each file or data block may be assigned individually to each file or data block.

17. The distributed storage system of claim 1, wherein the level of redundancy required by the redundant data recovery and reconstruction scheme may take the form of predetermined minimum and maximum redundancy levels.

18. A dynamically scalable redundant distributed storage system, the storage system having a plurality of components, the components comprising:

a plurality of file managers, each file manager having responsibility for providing access to a group of stored files or data blocks and being configured to store metadata associated with each of the files and data blocks for which it is responsible, the metadata including discovery metadata comprising a unique key for each file or data block;

a file manager distributed hash table adapted for allocating individual responsibilities among each of the plurality of file managers, the file manager distributed hash table being configured to assign file management responsibilities for individual files and data blocks to individual file managers and to maintain a record of which files and data blocks are assigned to each file manager;

a plurality of storage managers, each storage manager having responsibility for managing the storage of files and data blocks on one or more data storage elements for which it is responsible and being configured to maintain a record of the location of each stored file and data block on the data storage elements;

a storage manager distributed hash table adapted for allocating individual responsibilities among each of the plurality of storage managers, the storage manager distributed hash table being configured to assign file storage responsibilities for individual files among individual storage managers and to maintain a record of which files and data storage elements are assigned to each storage manager; and

at least one client adapted to provide user access to the storage system, the client being configured to initiate actions within the storage system by accessing the file manager distributed hash table and the storage manager distributed hash table, the client further comprising a processor configured to implement a redundant data recovery and reconstruction scheme.

19. The distributed storage system of claim 18, wherein the discovery metadata further comprises a predetermined desired redundancy level and type of data recovery and reconstruction scheme designation for each file or data block.

20. The distributed storage system of claim 18, wherein the file manager distributed hash table supports addition and removal of file managers, load balancing, and associating keys with responsible file managers.

21. The distributed storage system of claim 18, wherein the storage manager distributed hash table supports addition and removal of storage managers, load balancing, and associating keys with responsible storage managers.

22. The distributed storage system of claim 18, wherein each storage manager can be accessed to write, retrieve, and modify the data on any file or data block it is responsible for.

23. The distributed storage system of claim 18, wherein the storage managers can lock file or data blocks.

24. The distributed storage system of claim 18, wherein each file manager is associated with discovery metadata about the file manager and the file manager discovery metadata is stored in a file or data block in the distributed storage system.

25. The distributed storage system of claim 18, wherein the distributed hash tables are implemented as lists.

26. The distributed storage system of claim 25, wherein the file manager distributed hash table is implemented as a list, the list comprising an entry for each file manager, each entry comprising a range of unique key, value pairs assigned to the files or data blocks for which the file manager is responsible

27. The distributed storage system of claim 18, wherein the physical devices comprising or hosting the components comprising the storage system are not homogeneous.

28. The distributed storage system of claim 18, wherein at least some of the components of the system are implemented in software using functional programming.

29. The distributed storage system of claim 18, wherein the redundant data recovery and reconstruction scheme employs error correction code methods.

30. The distributed storage system of claim 18, wherein the redundant data recovery and reconstruction scheme employs file replication methods.

31. The distributed storage system of claim 18, wherein any single component may be replaced by a plurality of components.

32. The distributed storage system of claim 18, wherein additional components may be added to the system dynamically while the system is in use.

33. The distributed storage system of claim 18, wherein a component that has failed and then been repaired may be reutilized by the storage system.

34. The distributed storage system of claim 18, wherein a file manager acts as a client.

35. The distributed storage system of claim 18, wherein the system is asynchronous, having no system clock.

36. The distributed storage system of claim 18, wherein the level of redundancy required by the redundant data recovery and reconstruction scheme may take the form of predetermined minimum and maximum redundancy levels.

37. A method for ensuring restoration and integrity of data in computer-related applications using a dynamically scalable redundant distributed storage system, comprising the steps of:

dividing logical responsibility for files and data blocks from actual control of the files and data blocks by the steps of;

providing a plurality of file managers, each file manager having responsibility for providing access to a group of stored files or data blocks and being configured to store metadata associated with each of the files and data blocks for which it is responsible, the metadata including a unique file identifier for each file or data block;

allocating individual responsibilities among each of the plurality of file managers by assigning file management responsibilities for individual files and data blocks to individual file managers;

maintaining a record of which files and data blocks are assigned to each file manager;

providing a plurality of storage managers, each storage manager having responsibility for managing the storage of files and data blocks on one or more data storage devices for which it is responsible and being configured to maintain a record of the location of each stored file and data block on the data storage devices;

allocating individual responsibilities among each of the plurality of storage managers by assigning file storage responsibilities for individual files among individual storage managers; and

maintaining a record of which files and data storage devices are assigned to each storage manager;

implementing a redundant data recovery and reconstruction scheme;

assigning a unique file identifier to each file or data block;

storing, according to the redundant data recovery and reconstruction scheme, the metadata associated with each of the files and data blocks, including the unique file identifier for each file or data block;

storing, according to the redundant data recovery and reconstruction scheme, the files and data blocks on one or more data storage devices; and

recording the location on the data storage devices of each stored file and data block.

38. The method of claim 37, further comprising the step of providing user access to the storage system by means of a client that initiates actions within the storage system.

39. The method of claim 37, wherein the steps of allocating individual responsibilities among file managers and maintaining a record of which files and data blocks are assigned to each file manager are performed by a file manager control component.

40. The method of claim 39, wherein the file manager control component comprises a distributed hash table.

41. The method of claim 37, wherein the steps of allocating individual responsibilities among storage managers and maintaining a record of which files and data storage devices are assigned to each storage manager are performed by a storage manager control component.

42. The method of claim 39, wherein the storage manager control component comprises a distributed hash table.

43. The method of claim 37, wherein the redundant data recovery and reconstruction scheme employs error correction code methods.

44. The method of claim 37, wherein the redundant data recovery and reconstruction scheme employs replication of files and data blocks.

45. The method of claim 37, further comprising the step of reconstructing data by the steps of:

detecting loss or corruption of files or data blocks;

retrieving stored metadata for the files or data blocks;

using the retrieved metadata, locating, retrieving, and reconstructing the stored files and data blocks; and

reallocating responsibility for the reconstructed data.

46. The method of claim 37, further comprising the step of individually assigning, for each file or data block, the level of redundancy required by the redundant data recovery and reconstruction scheme.

47. The method of claim 37, further comprising the step of establishing minimum and maximum redundancy levels to be required by the redundant data recovery and reconstruction scheme.

48. A method for ensuring restoration and integrity of data in computer-related applications using a dynamically scalable redundant distributed storage system, comprising the steps of:

distributing data file storage across a plurality of data storage devices by the steps of;

breaking each data file into to shreds; and

distributing the shreds across multiple data storage devices;

reconstructing failed data storage devices by using redundancy or duplication to recover the stored data files on the failed data storage devices; and

restoring the recovered data files by distributing them across, and storing them on, free space on the remaining data storage devices.

49. A distributed storage system, comprising a storage system configured to rapidly reconstruct a failed storage element by distributing data storage across a number of storage elements and reconstructing data stored on the failed storage element by breaking each data file into shreds, distributing the shreds across multiple storage elements, using redundancy or duplication to recover the data from errors, and distributing the recovered data onto free space on the remaining system storage elements.