Granted Patent B2

US 7,209,973 · App. 09/918,032 · Granted Apr 24, 2007

Abstract

Claims (150)

1. A system for distributed file storage comprising:

a plurality of servers providing, to a plurality of clients, file access services for accessing files stored on the plurality of servers; and

a dynamic list of neighbor servers maintained by each server, wherein the neighbor servers are grouped as a subset of the plurality of servers, switching at least one server of the plurality of servers into a neighbor group of servers based on network distance,

wherein each file is stored in the form of a plurality of N pieces on N servers, the N pieces being generated from the file,

wherein the list is used to obtain information for reconstructing files stored on the neighbor servers, such that any K out of the N pieces can be used to reconstruct any file,

wherein a server belonging to more than one group acts as a boundary server, and

wherein boundary servers are used to transfer pieces of the file to servers of groups other than a group to which a client has connected.

2. The system of claim 1 , wherein the servers use a peer-to-peer network for communication with each other.

3. The system of claim 1 , wherein the files are stored using a peer-to-peer network.

4. The system of claim 1 , wherein at least one of the servers is a logical server that includes a plurality of physical servers connected via a network.

5. The system of claim 1 , wherein each server belongs to a group defined by its corresponding list,

wherein a server that belongs to multiple groups maintains corresponding multiple lists for each group to which it belongs, and

wherein, upon receiving a request for a file, the server distributes the request to each of the multiple groups.

6. The system of claim 1 , wherein none of the pieces is unique.

7. The system of claim 1 , wherein the servers are organized into a plurality of groups such that server-to-server response time between any two servers of the same group does not exceed a predetermined limit, and

wherein, when a new server is connected to one of the groups, the new server uses information of the boundary servers to connect to a group so as to have optimal server-to-server response time to its neighbors within its group.

8. The system of claim 7 , wherein, when one server is disconnected from the system, the remaining servers use information of the boundary servers to reconfigure their groups so as to have optimal server-to-server response times to their neighbors within their groups.

9. A method for distributed file storage comprising:

dividing a plurality of servers into a plurality of groups, with each server belonging to at least one group;

on each server, maintaining a dynamic list of neighbor servers belonging to the same group, wherein each group is a subset of the plurality of servers; switching at least one server of the plurality of servers into a neighbor group of servers based on network distance;

supporting file access services on each of the servers;

transforming a file into a plurality of N pieces that are derived from the file, such that any K out of the N pieces can be used to reconstruct any file; and

storing each of the pieces on N servers selected from the list,

wherein a server belonging to more than one group acts as a boundary server, and

wherein boundary servers are used to transfer pieces of the file to servers of groups other than a group to which a client has connected.

10. The method of claim 9 , further comprising using a peer-to-peer network for communication between the servers.

11. The method of claim 9 , further comprising using a peer-to-peer network for storing the file.

12. The method of claim 9 , further comprising maintaining functional equivalence among the servers.

13. The method of claim 9 , further comprising verifying availability of the neighbor servers.

14. The method of claim 9 , further comprising:

polling the servers on the dynamic list of the neighbor servers and measuring a network distance for each server;

keeping each available server on the dynamic list in the same group;

removing unavailable servers from the dynamic list of the same group; and

switching at least one server of the plurality of servers into a neighbor group of servers if the measured network distance is lower than a predetermined threshold.

15. The method of claim 14 , wherein better network connectivity is determined based on the network distance.

16. The method of claim 14 , further comprising:

polling the dynamic list;

connecting a client to a server on the dynamic list;

switching the client to a different server on the dynamic list that has a smaller workload or lower network distance relative to the client; and

delivering to the client a file requested by the client that is stored on the servers.

17. The method of claim 14 , further comprising:

polling the dynamic list;

connecting a client to a server on the dynamic list;

switching the client to a different server on the dynamic list that has a lower network distance from a perspective of the client; and

delivering to the client a file requested by the client that is stored on the servers.

18. The method of claim 9 , wherein the list is a static list of servers.

19. The method of claim 9 , further comprising:

maintaining multiple lists for a server that belongs to multiple groups; and,

upon receiving a request for a file, distributing the request to servers selected from the multiple groups.

20. The method of claim 9 , wherein, when one server is disconnected from the system, the remaining servers use information of the boundary servers to reconfigure their groups so as to have optimal server-to-server response times to their neighbors within their groups.

21. A method of accessing files in a distributed file storage system comprising:

dividing a plurality of the servers into a plurality of groups, wherein each server belongs to at least one group, and wherein each group is a subset of the plurality of servers;

supporting file access services on each of the servers for accessing a file stored on the servers;

at each server, maintaining a dynamic list of neighbor servers that belong to the same group; switching at least one server of the plurality of servers into a neighbor group of servers based on network distance;

generating a plurality of N pieces from the file; and

distributing the plurality of N pieces to the neighbor servers in the same group in order to achieve a desired fault tolerance level, wherein the fault tolerance level is defined by how many servers (K) out of the total number of N servers on which the N file pieces are stored, can fail, such that any K out of the N pieces can be used to reconstruct any file,

wherein a server belonging to more than one group acts as a boundary server, and

wherein boundary servers are used to transfer pieces of the file to servers of groups other than a group to which a client has connected.

22. The method of claim 21 , further comprising using a peer-to-peer network for communication between the servers.

23. The method of claim 21 , further comprising maintaining functional equivalence of the servers for purposes of storing the file.

24. The method of claim 21 , further comprising verifying availability of the neighbor servers.

25. The method of claim 21 , further comprising:

polling the list of neighboring group servers and measuring a relative network distance for each client-server pair;

connecting a client to any of the servers on the list using the measured metric;

switching the client to a server on the list that has a lower relative network distance and a smaller workload to improve a level of service; and

delivering, to the client, the file requested by the client.

26. The method of claim 21 , further comprising:

polling servers on the list that belong to the same group;

connecting a client to any of the servers on the list that belong to the same group;

switching the client to a server on the list that has a smaller workload; and

delivering, to the client, the file that is requested by the client.

27. The method of claim 26 , further comprising:

identifying a name of the file in namespace;

sending a request for the file from the client to the server to which the client is connected;

sending a request for the file from the server to which the client is connected to a neighbor server;

distributing the request to other servers if the server to which the client is connected cannot provide the file pieces information;

checking for file pieces in a local cache of each server that received the request;

sending the pieces to the server to which the client is connected;

transferring the pieces to the client; and

assembling the file on the client.

28. The method of claim 26 , further comprising sending all the pieces from the neighbor servers to the server to which the client is connected simultaneously.

29. The method of claim 21 , wherein the list is a static list of servers.

30. The method of claim 21 , wherein none of the pieces is unique.

31. A method of naming files in a distributed file storage system comprising:

dividing a plurality of servers into a plurality of groups such that each server belongs to at least one group, wherein each group is a subset of the plurality of servers;

supporting file access services on each of the servers for accessing files stored on the servers; at each server, maintaining a dynamic list of neighbors server that belong to the same group; switching at least one server of the plurality of servers into a neighbor group of servers based on network distance;

giving file names for the uniformly and independent of location of the files on the servers;

storing the files on N of the servers using the names, wherein each file is transformed into a plurality of pieces that are generated from the file, such that any K out of the N pieces can be used to reconstruct any file,

wherein a server belonging to more than one group acts as a boundary server, and

wherein boundary servers are used to transfer pieces of the file to servers of groups other than a group to which a client has connected; and

accessing the files using the file access services from any of servers.

32. The method of claim 31 , further comprising using a peer-to-peer network for communication between the servers.

33. The method of claim 31 , further comprising maintaining functional equivalence of the servers.

34. The method of claim 31 , further comprising verifying availability of the neighbor servers.

35. The method of claim 31 , further comprising:

on each server, maintaining a dynamic list of the neighbor servers in the same group;

polling servers on the dynamic list;

connecting a client to any of the servers on the dynamic list;

switching the client to a server on the dynamic list that has lower network distance to improve level of service; and

delivering to the client a file requested by the client that is stored on the servers.

36. The method of claim 31 , further comprising:

on each server, maintaining a dynamic list of the neighbor servers;

polling servers on the dynamic list that belong to the same group;

connecting a client to any of the servers on the dynamic list;

switching the client to a server on the dynamic list that has a smaller workload; and

delivering to the client a file requested by the client that is stored on the servers.

37. The method of claim 31 , further comprising:

maintaining a uniform name space as a tree with a common root and a logical path to each stored file as part of the distributed file storage system; and

maintaining data files and directory files to be stored in the distributed file storage system.

38. The method of claim 37 , further comprising;

maintaining the directory files as executable files with their own executable code and data; and

providing translation from a logical path inside the uniform name space to a unique file identifier using the directory files.

39. A system for organizing distributed file storage comprising:

N functionally equivalent servers each providing file access services, for a plurality of clients, to files stored on the servers, such that when a file is divided into N pieces stored on the N servers, any K out of the N servers can be used to reconstruct the file; and

each file being transformed into the N pieces that are generated from the file and stored on the N servers, at each server, maintaining a dynamic list of neighbors server that belong to the same group; switching at least one server of the plurality of servers into a neighbor group of server based on network distance,

wherein information for reconstructing the files is obtained from the servers,

wherein the servers are organized into groups, each group being a subset of the plurality of N servers, and wherein a server belonging to more than one group acts as a boundary server, and

wherein boundary servers are used to transfer pieces of the file to servers of groups other than a group to which a client has connected.

40. The system of claim 39 , further comprising a dynamic list of neighbor servers maintained by each server,

wherein the neighbor servers are a subset of the plurality of servers, and

wherein the dynamic list is used to obtain the information for reconstructing the files.

41. The system of claim 39 , further comprising a static list of neighbor servers maintained by each server,

wherein the neighbor servers are a subset of the plurality of servers, and

wherein the static list is used to obtain the information for reconstructing the files.

42. A computer program product for distributed file storage, the computer program product comprising a computer useable medium having computer program logic recorded thereon for controlling a processor, the computer program logic comprising:

computer program code means for organizing a plurality of servers into a plurality of groups, with each server belonging to at least one group;

on each server, computer program code means for maintaining a dynamic list of neighbor servers belonging to the same group; switching at least one server of the plurality of servers into a neighbor group of servers based on network distance;

computer program code means for supporting file access services on each of the servers;

computer program code means for transforming a file into a plurality of pieces that are derived from the file, such that any K out of the N pieces can be used to reconstruct any file; and

computer program code means for storing each of the pieces on N servers selected from the lists,

wherein a server belonging to more than one group acts as a boundary server, and

wherein boundary servers are used to transfer pieces of the file to servers of groups other than a group to which a client has connected.

43. A method of accessing files in a distributed file storage system comprising:

organizing a plurality of the servers into dynamically reconfigurable groups, wherein each server belongs to at least one group that is reconfigurable based on minimum network distance, wherein each group is a subset of the plurality of servers; at each server, maintaining a dynamic list of neighbors server that belong to the same group; switching at least one server of the plurality of servers into a neighbor group of servers based on network distance;

supporting file access services on each of the servers for accessing a file distributed among the servers;

generating a plurality of N pieces from the file; and

distributing the plurality of N pieces to N of the neighbor servers in the same group in order to achieve a desired fault tolerance level based on how many servers (K) out of the plurality of servers are available, such that any K out of the N pieces can be used to reconstruct any file,

wherein a server belonging to more than one group acts as a boundary server, and

wherein boundary servers are used to transfer pieces of the file to servers of groups other than a group to which a client has connected.

44. A system for distributed file storage comprising:

a plurality of servers providing, to a plurality of clients, file access services for accessing files stored on the plurality of servers;

wherein the servers are organized into a plurality of groups such that server-to-server response time between any two servers of the same group does not exceed a predetermined limit;

wherein a server belonging to more than one group acts as a boundary server;

wherein, when a new server is connected to one of the groups, the new server uses information of the boundary servers to connect to a group so as to have optimal server-to-server response time to its neighbors within its group;

wherein, when one server is disconnected from the system, the remaining servers use information of the boundary servers to reconfigure their groups so as to have optimal server-to-server response times to their neighbors within their groups; and

a dynamic list of neighbor servers of each server's group maintained by each server, wherein the neighbor servers are a subset of the plurality of servers, switching at least one server of the plurality of servers into a neighbor group of servers based on network distance;

wherein each file is stored in the form of a plurality of N pieces, the pieces being generated from the file and stored on N servers of the plurality of servers,

wherein boundary servers are used to transfer pieces of the file to servers of groups other than a group to which a client has connected,

wherein the list is used to obtain information for reconstructing files stored on the neighbor servers, and

wherein any client can use any of the plurality of servers to access any of its files stored on the system.

Assignments (10)