System and method for a distributed object store

• US 20060168154A1
• Filed: 11/19/2004
• Published: 07/27/2006
• Est. Priority Date: 11/19/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Zheng, Lin, Shiding, Chen, Yu, Chen, Wei, Lian, Qiao, Teodosiu, Dan, Jin, Chao
• Granted Patent: US 7,778,984 B2
• Time in Patent Office: Days
• US Class Current: 709/220
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• 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]
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

An improved system and method for flexible object placement and soft-state indexing of objects in a distributed object store is provided. A distributed object store may be provided by a large number of system nodes operably coupled to a network. A system node provided may include an access module for communicating with a client, an index module for building an index of a replicated data object, a data module for storing a data object on a computer readable medium, and a membership and routing module for detecting the configuration of operable nodes in the distributed system. Upon failure of an index node, the failure may be detected at other nodes, including those nodes that store the replicas of the object. These nodes may then send new index rebuilding requests to a different node that may rebuild the index for servicing any access request to the object.

Claims

1. A distributed computer system for storing data objects, comprising:

a first index node for holding an index of a replicated data object, the index having information of the location of each replica of the replicated data object in the distributed computer system;

a data node for storing the replicated data object and for initiating rebuilding of the index for the replicated data object on a second index node when the first index node fails, the data node determining when the first index node fails from a configuration of operable index nodes and data nodes; and

a network operably coupled to the first index node and operably coupled to the data node for communicating a message including the configuration of operable index nodes and data nodes in the distributed computer system.

2. The system of claim 1 further comprising a membership and routing module for sending the message including the configuration of operable index nodes and data nodes in the distributed computer system.

3. The system of claim 1 further comprising an access module operably coupled to the first index node and the data node for communicating with a client.

4. The system of claim 1 further comprising a client operably coupled to the network for communicating with the first index node and the data node.

5. The system of claim 4 wherein the client includes an application having a copy of the replicated data object and having a desired replication degree for the data object.

6. The system of claim 4 wherein the client includes a policy for specifying replication and placement of the replicated data object in the distributed computer system.

7. A computer-readable medium having computer-executable components comprising the system of claim 1.

15. A computer readable medium having computer-executable components comprising the system of claim 1.

8. A distributed computing system, comprising:

an index module for building an index of a replicated data object on a first system node;

a data module for storing the replicated data object on a computer storage medium and for initiating rebuilding of the index for the replicated data object on a second system node when the first system node fails, the data module determining when the first system node fails from a configuration of operable system nodes; and

a membership and routing module for detecting the configuration of operable system nodes in the distributed computer system and communicating the configuration of operable system nodes to the data module.

9. The system of claim 8 further comprising a client for communicating with the index module and the data module, the client including an executable application.

10. The system of claim 8 further comprising an application having a copy of the replicated data object and having a desired replication degree for the data object.

11. The system of claim 8 further comprising a policy for specifying replication and placement of the replicated data object in the distributed computer system.

12. The system of claim 8 further comprising an access module for communicating with a client.

13. The system of claim 8 further comprising a network operably coupling the index module and the data module.

14. The system of claim 8 further comprising an index having information of the location of each replica of the replicated data object in the distributed computer system.

16. A method in a distributed computer system for storing data objects, comprising the steps of:

storing a replicated data object on a computer storage medium;

building an index of a replicated data object in volatile memory of a first system node;

detecting that the first system node has failed;

determining a second system node for rebuilding of the index for the replicated data object; and

rebuilding of the index for the replicated data object in volatile memory of a second system node.

17. The method of claim 16 further comprising sending an indexing request from a system node storing a replicated data object to the first system node, the indexing request including the location of the replicated data object.

18. The method of claim 16 further comprising receiving notification of a configuration of operable system nodes.

19. The method of claim 16 further comprising sending an indexing request to the second system node, the indexing request including the location of the replicated data object.

20. The method of claim 16 further comprising instantiating a state machine for indicating the state of rebuilding the index of the replicated data object.

21. The method of claim 16 further comprising receiving notification of expiration of a timer indicating that fewer than the desired number of replicas are indexed.

22. The method of claim 16 further comprising determining the number of replicas needed for the replicated data object.

23. The method of claim 16 further comprising determining that all replicas needed for the replicated data object have been created upon receiving a number of notifications greater than or equal to the desired replication degree for the data object.

24. The method of claim 16 further comprising applying a policy to select the system nodes for storing replicas of the replicated data object.

25. The method of claim 16 further comprising instructing a subset of system nodes to send replicas to other selected system nodes.

26. A method in a distributed computer system for storing data objects, comprising the steps of:

receiving a request for storing a replicated data object on a computer storage medium of a system node;

applying a policy to select the system nodes for storing replicas of the replicated data object;

creating the replicas of the replicated object on the system nodes selected; and

sending an indexing request to an index node for building an index for the replicated data object.

27. The method of claim 26 further comprising determining the number of replicas desired for the replicated data object.

28. The method of claim 26 further comprising determining the index node for building the index for the replicated data object.

29. The method of claim 26 further comprising building the index for the replicated data object in volatile memory of the index node.

30. The method of claim 26 wherein creating the replicas of the replicated object on the system nodes selected comprises instructing a subset of system nodes to send replicas to the system nodes selected.

31. A computer readable medium having computer-executable instructions for performing the method of claim 26.

32. A method in a distributed computer system for storing data objects, comprising the steps of:

detecting a new computer storage medium added to the distributed computer system;

detecting new data objects on the new computer storage medium;

determining an index node for each new data object detected on the new computer storage medium; and

sending an indexing request to each index node determined for each new data object.

33. The method of claim 32 wherein detecting a new computer storage medium added to the distributed computer system comprises detecting a new system node added to the distributed computer system, the new system node including the new computer storage medium.

34. The method of claim 32 wherein detecting new data objects on the new computer storage medium comprises scanning the new computer storage medium to discover the new data objects.

35. The method of claim 32 further comprising initiating data repair to create the desired number of replicas for each new data object on selected nodes in the distributed computer system.

36. A computer readable medium having computer-executable instructions for performing the method of claim 32.

37. A method in a distributed computer system for storing data objects, comprising the steps of:

receiving notification to initiate data repair on a replicated data object;

determining the number of replicas needed to be created for the distributed computer system to have the number of desired replicas for the replicated data object;

applying a policy to select the system nodes for storing the needed replicas of the replicated data object; and

instructing a subset of system nodes to send replicas of the replicated data object to the system nodes selected for storing the needed replicas.

38. The method of claim 37 wherein receiving notification to initiate data repair on a replicated data object comprises receiving notification that the time period expired for a state machine of an index of the replicated data object to remain in a partial state.

39. The method of claim 37 wherein determining the number of replicas needed to be created for the distributed computer system to have the number of desired replicas for the replicated data object comprises subtracting the number of replicas indexed from the number of desired replicas for the replicated data object.

40. The method of claim 37 further comprising receiving a first request from one of the selected system nodes to build an index for the replicated data object.

41. The method of claim 40 wherein receiving a first request from one of the selected system nodes to build an index for the replicated data object comprises setting a timer to expire at the end of a time period during which a state machine for the index of the replicated data object remains in a partial state.

42. The method of claim 37 further comprising rebuilding an index for the replicated data object in volatile memory of an index node.

43. A computer readable medium having computer-executable instructions for performing the method of claim 37.

44. A method in a distributed computer system for checking out a data object, comprising the steps of:

receiving a request for checking out a replicated data object;

determining an index node having an index for the replicated object;

selecting a system node having a replica of the replicated data object;

routing the request to the selected system node for transferring a copy of the replicated data object to the requestor; and

transferring a copy of the replicated data object to the requestor.

45. A method in a distributed computer system for deleting a data object from a distributed object store, comprising the steps of:

receiving a request for deleting a replicated data object from a distributed object store;

determining an index node having an index for the replicated object;

selecting each system node having a replica of the replicated data object;

routing the deletion request to each selected system node for deleting the replicated data object stored thereon; and

deleting the replicated data object stored on each selected system node.

46. The method of claim 45 further comprising marking the index for the replicated data object to be deleted.

47. The method of claim 45 further comprising sending a deletion acknowledgement to the index node.

48. The method of claim 45 further comprising resending the deletion request to each selected system node for which a deletion acknowledgement was not received within a specified period of time.

49. The method of claim 45 further comprising sending the deletion request to each new system node added to the distributed computer system that contains a replica of the replicated data object to be deleted.