System and method for a distributed object store

• US 7,778,984 B2
• Filed: 11/19/2004
• Issued: 08/17/2010
• 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
• Primary Examiner(s): Le; Debbie
• Assistant Examiner(s): Corbo; Griselle
• Application Number:
  US10/993,536
• Publication Number:
  US 20060168154A1
• Time in Patent Office: 2,097 Days
• Field of Search: 707/204, 707/610, 707/613, 707/661, 707/665, 707/666, 707/689, 707/696
• US Class Current: 707/696
• 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 method in a distributed computer system capable of redundantly storing a plurality of data objects, the method for detecting an index failure and repairing the index, the method comprising:

storing a replicated data object on a computer storage medium;

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

a data node that has at least one object which is indexed by the first system node detecting that the first system node has failed;

a membership and routing layer detecting a failed node;

receiving notification of a changed configuration;

the membership and routing layer sending notification of the changed configuration to at least one live data node;

detecting a change in an availability of an index node for data objects stored by the live data node;

determining that a time period for propagation delay has expired and, upon determining the time period has expired, initiating data repair procedures;

upon determining the time period has expired, determining a new index node for each data object without a live index node;

a data node having at least one object indexed by the first system node determining, by using membership information of operable nodes in the new configuration, a second system node for rebuilding of the index for the replicated data object;

computing a responsible index node for maintaining index information for the replicated data object using the membership information;

sending an indexing request to the second system node for at least one object without a live index node;

rebuilding the index for the replicated data object; and

storing the rebuilt index in computer storage media corresponding to memory of a second system node.

2. The method of claim 1 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.

3. The method of claim 1 further comprising receiving notification of a configuration of operable system nodes.

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

5. The method of claim 1 further comprising instantiating a state machine for indicating the state of rebuilding the index of the replicated data object, the state machine maintaining information indicating whether a required number of copies of the replicated data object have been indexed.

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

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

8. The method of claim 1 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.

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

10. The method of claim 1 further comprising sending a request to a subset of system nodes having copies of a data object to send replicas of the data object to other selected system nodes.