Peer-to-Peer Redundant File Server System and Methods

• US 20090271412A1
• Filed: 04/28/2009
• Published: 10/29/2009
• Est. Priority Date: 04/29/2008
• Status: Active Grant

• Current Assignee: Overland Storage Incorporated (Silicon Valley Technology Partners LLC)
• Original Assignee: MaxiScale, Inc. (Silicon Valley Technology Partners LLC)
• Inventors: Nguyen, Don, Sartirana, Bruno, Ramsdell, Thomas Reynold, Steele, Peter Wallace, Tran, Kyle Dinh, Lin, I. Chung Joseph, Li, Samuel Sui-Lun, Diller, Nathanael John, Hua, Ernest Ying Sue, Lacapra, Francesco
• Granted Patent: US 8,296,398 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/178 Techniques for file synchronisation in file systems
• CPC Class Codes: G06F 16/1834 implemented based on peer-to-peer networks, e.g. gnutella p2p communication protocols H04L67/104
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• 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

Peer-to-peer redundant file server system and methods include clients that determine a target storage provider to contact for a particular storage transaction based on a pathname provided by the filesystem and a predetermined scheme such as a hash function applied to a portion of the pathname. Servers use the same scheme to determine where to store relevant file information so that the clients can locate the file information. The target storage provider may store the file itself and/or may store metadata that identifies one or more other storage providers where the file is stored. A file may be replicated in multiple storage providers, and the metadata may include a list of storage providers from which the clients can select (e.g., randomly) in order to access the file.

Claims

1. A file storage system, for handling a standard file system request including a path name, the system comprising:

a plurality of storage providers;

a client, in communication with the storage providers, that accepts the file system request and generates, for fulfillment, a corresponding reformatted request to a selected one of the storage providers, the selected one of the storage providers being initially selected by the client on the basis of a hashing algorithm applied to at least a portion of the path name, so that the client serves as an interface between the standard file system request and the storage providers.

2. A file storage system according to claim 1, wherein each storage provider is a virtual server, the virtual server including a plurality of peer-to-peer computer processes forming a set of peer nodes.

3. A file storage system according to claim 2, wherein a specified request directed to a specified virtual server is delivered to all peer nodes of the virtual server but the set is configured so that only a single one of the peer nodes responds to the specified request.

4. A file storage system according to claim 2, wherein each one of the peer nodes is implemented as a distinct physical storage medium coupled to a distinct microprocessor.

5. A file storage system according to claim 4, further comprising a plurality of physical storage servers, each physical storage server including a plurality of physical storage media and a microprocessor, wherein each virtual server is configured with a distinct storage server being associated with each peer node of the set.

6. A method for locating a given file in a file storage system having one or more storage providers, the given file associated with a file pathname including a sequence of directory names and a file name, the method comprising:

a. applying, in a computer process, a hashing algorithm to a chosen one of the directory names to obtain an index number, wherein the hashing algorithm has the property that different index numbers may be obtained for different directory names;

b. identifying a selected storage provider associated with the obtained index number; and

c. contacting the selected storage provider number in order to obtain information maintained by the selected storage provider regarding the location of the given file within the file storage system, whereby the given file may be located whether the given file is stored by the selected storage provider and/or by one or more other storage providers.

7. A method for locating a given file according to claim 6, wherein each storage provider is a virtual server, the virtual server including a plurality of peer-to-peer computer processes forming a set of peer nodes.

8. A method for locating a given file according to claim 6, wherein the chosen directory name is a parent directory for the file name.

9. A method for locating a given file according to claim 6, wherein the hashing algorithm obtains index numbers from zero up to, but not including, a number that is an integer power of a chosen base integer, such that the number is greater than or equal to the number of file servers in the file storage system, and the number divided by the base integer is less than the number of file servers in the file storage system.

10. A method for locating a given file according to claim 9, wherein the chosen base integer is two.

11. A method according to claim 6, further comprising:

changing the location of the given file within the file storage system; and

updating the information maintained by the selected storage provider to reflect the changed location.

12. A method according to claim 6, wherein multiple instantiations of the given file are stored in the file storage system, and wherein the information maintained by the selected storage provider identifies the locations of the instantiations.

13. A method according to claim 6, wherein identifying the selected storage provider associated with the obtained index number comprises using the obtained index number to index a table of storage providers.

14. A method of providing access by a client to a file in a storage system, the file associated with a file pathname, the method comprising:

a. storing an instantiation of the file in each of a plurality of storage providers;

b. storing metadata for the file in a target storage provider selected based at least in part on the pathname using a predetermined mapping scheme, the metadata including at least a list of the storage providers;

c. sending a request by the client to the target storage provider;

d. providing the list of the storage providers by the target storage provider to the client in response to the request;

e. selecting one of the listed storage providers by the client using a predetermined selection scheme; and

f. communicating with the selected storage provider by the client in order to access the file instantiation stored in the selected storage provider.

15. A method according to claim 14, wherein the predetermined mapping scheme includes a hash algorithm applied to a portion of the pathname.

16. A method according to claim 14, wherein the predetermined selection scheme includes random selection from among the listed storage providers.

17. A method according to claim 14, wherein the predetermined selection scheme includes a user-configurable policy.

18. A method according to claim 14, wherein the target storage provider is one of the plurality of storage providers in which an instantiation of the file is stored.

19. A method according to claim 14, wherein the target storage provider is not one of the plurality of storage providers in which an instantiation of the file is stored.

20. A method according to claim 14, wherein the metadata further includes at least one of the pathname, a portion of the pathname, and a file version number.

21. A method according to claim 14, wherein an instantiation of the file is stored in each of a plurality of storage providers for redundancy.

22. A method according to claim 14, wherein an instantiation of the file is stored in each of a plurality of storage providers for distributing processing load across the plurality of storage providers.

23. A storage system comprising:

a client; and

a storage provider in communication the client over a communication network, the storage provider including a plurality of storage nodes, each storage node managed by a different storage server, wherein the plurality of storage nodes are associated with a multicast address and requests are transmitted to the storage provider using the multicast address.

24. A storage system comprising:

a client;

a storage provider in communication the client over a communication network, the storage provider including a plurality of storage nodes and a distributed queuing mechanism allowing tasks to be queued for processing by one or more of the storage nodes.

25. A storage system according to claim 24, wherein each storage node is managed by a different storage server.

26. A storage system according to claim 25, wherein the storage nodes are associated with a multicast address and tasks are queued using the multicast address.

27. A storage system according to claim 24, wherein one of the storage nodes is designated for processing queued tasks at any given time.

28. A storage system according to claim 24, wherein the storage nodes are assigned different roles for managing the processing of queued tasks, the roles including at least a primary that manages the processing of queued tasks by default and a secondary that manages the processing of queued tasks if the primary is unable to do so.

29. A storage system according to claim 28, wherein the roles are assigned using color designations.

30. A storage system comprising:

a client; and

a storage provider in communication the client over a communication network, the storage provider including a plurality of storage nodes, wherein one of the storage nodes is designated to act as a proxy for the plurality of nodes for managing storage of data among the plurality of storage nodes and interacting with the client on behalf of the other storage nodes.

31. A storage system according to claim 30, wherein each storage node is managed by a different storage server.

32. A storage system according to claim 31, wherein the storage nodes are associated with a multicast address and wherein the client communicates with the storage system using the multicast address.

33. A storage system according to claim 30, wherein the storage nodes are assigned different roles, the roles including at least a primary that acts as the proxy and a secondary that acts as the proxy if the primary is unable to do so.

34. A storage system according to claim 33, wherein the roles are assigned using color designations.

35. A storage system comprising a plurality of storage providers for distributed storage of files associated with a filesystem, wherein each storage provider maintains statistics regarding the files that it stores, and wherein the statistics are collected by a designated storage provider for processing.

36. A storage system according to claim 35, wherein the statistics include file access frequency.

37. A method of distributing processing load across a plurality of storage providers, the method comprising:

determining that multiple clients desire access to a file stored by a given storage provider;

replicating the file in at least one additional storage provider such each of storage providers, including the given storage provider, stores an instantiation of the file; and

allowing clients to access any of the instantiations of the file so as to distribute processing load across the storage providers.

38. A method according to claim 37, wherein allowing clients to access any of the instantiations of the file comprises:

providing a list of the storage providers to each of the clients; and

allowing each client to select one of the storage providers from which to access the file.

39. A method according to claim 37, wherein allowing clients to access any of the instantiations of the file comprises:

specifying a different one of the storage providers for each of the clients.

40. A method for maintaining peer set nodes of a computer file storage system, the method comprising:

identifying waiting nodes associated with a current peer set based on a node-selection algorithm, the node-selection algorithm producing, at a root node, in a first computer process, an updated list of the current peer set nodes; and

in a second computer process, conducting a dialog among the identified nodes, the dialog establishing a hierarchy and role distribution among the nodes.

41. A method according to claim 40, wherein identifying the waiting nodes associated with the current peer set of nodes comprises:

receiving, by a waiting node, from the root node, a message containing descriptors of waiting nodes associated with the current peer set.

42. A method according to claim 40, wherein conducting the dialog comprises:

sending invitations, by each of node-inviters, to be received by nodes-invitees, each invitation triggering a node-invitee to respond by sending an acknowledgment to a corresponding node-inviter,

receiving at least one acknowledgment by at least one node-inviter,

wherein a node-inviter and a node-invitee are waiting nodes identified as being associated with the current peer set.

43. A method according to claim 42, wherein the dialog indicator is positive if each of node-inviters received acknowledgments from each of node-invitees, and wherein the dialog indicator is negative otherwise.

44. A method according to claim 43, further comprising:

in a third computer process, allocating replacement nodes for the current peer set if the dialog success indicator is negative.

45. A method according to claim 42, wherein conducting the dialog further comprises:

passing messages received from the root node by each of node-inviters to each of node-invitees.

46. A method according to claim 42, wherein conducting the dialog further comprises:

passing a message by at least one of node-inviters to be received by the node-invitees, the message containing descriptors of waiting nodes associated with the current set and received by the at least one of node-inviters from the root node.