Data replication in a distributed system

• US 20070299955A1
• Filed: 06/27/2006
• Published: 12/27/2007
• Est. Priority Date: 06/27/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: MacCormick, John P., Roomp, Kristof, Thekkath, Chandramohan A., Zhou, Lidong, Jager, Marcus J., Hoffman, William R.
• Granted Patent: US 7,636,868 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
• 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

A global state management service manages replication in a distributed system. A distributed system can have several replica groups. The global state management service manages state associated with each replica group. Data replication is implemented without implementing an instance of a state machine on each device in a replica group. A replica group comprises a primary device and at least one secondary device. Each device in a replica group contains a replica of data of interest. The global state management service manages the allocation of primary and secondary devices. In the absence of a failure in either a primary device or a secondary device, read and write operations are performed without consulting the global state management service. When a failure is detected, the global state management service manages failover.

Claims

1. A system for replicating data in a distributed system, the system comprising:

a plurality of devices comprising;

a primary device for storing a replica of the data; and

at least one secondary device, wherein;

each one of the at least one secondary device is for storing a respective replica of the data; and

absent a detection of a failure in one of the primary device and a secondary device, read operations and write operations are performed without consulting a global state management service; and

the global state management service for;

designating one of the plurality of devices in the distributed system as the primary device;

designating from the plurality of devices the at least one secondary device; and

if a failure is detected in the primary device, reallocating one of the at least one secondary device as a primary device.

2. A system in accordance with claim 1, the global state management service further for detecting the failure.

3. A system in accordance with claim 1, wherein the global state management service comprises a device other than the primary device and the at least one secondary device.

4. A system in accordance with claim 1, the global state management service further for instructing the reallocated primary device to assume processing for the failed primary device.

5. A system in accordance with claim 4, wherein the replica data of the reallocated primary device replaces the data of the failed primary device.

6. A system in accordance with claim 4, the global state management service further for managing the plurality of devices such that the reallocated primary device assumes processing for the failed primary device without intervention of a user of the system.

7. A system in accordance with claim 1, wherein:

if a failure is detected in a secondary device, the global state management service grants permission, for a predetermined amount of time, to the primary device to perform at least one of a write operation and a read operation.

8. A system in accordance with claim 7, wherein:

prior to expiration of the predetermined amount of time and upon receiving a request to renew the permission, the global state management service renews the permission.

9. A system in accordance with claim 8, wherein:

if a failure is detected in the primary device and subsequent expiration of the predetermined amount of time, the global management service reallocates one of the at least one secondary device as a primary device.

10. A system in accordance with claim 1, wherein the primary device performs a write operation in a single round of message exchange comprising:

providing, by the primary device, a write request to at least one live secondary device, wherein a live secondary device is a secondary device in which a failure has not been detected; and

receiving, by the primary device, a reply from each live secondary device.

11. A method for replicating data in a distributed system comprising a global state management service, a primary device, and at least one secondary device, the method comprising:

if no indication has been received that one of the primary device and a secondary device has failed, managing, by the primary device, read and write operations between the primary device and the at least one secondary device, wherein;

a write operation is performed in a single round of message exchange comprising;

providing, by the primary device, a write request to at least one live secondary device, wherein a live secondary device is a secondary device in which a failure has not been detected; and

receiving, by the primary device, a reply from each live secondary device; and

if an indication has been received that one of a primary device and a secondary device has failed, managing by the global state management service one of recovery and reallocation of the failed device.

12. A method in accordance with claim 11, further comprising:

if a failure is detected in the primary device, reallocating one of the at least one secondary device as a reallocated primary device.

13. A method for replicating data in a distributed system comprising a global state management service, a primary device, and at least one secondary device, the method comprising:

maintaining, by at least one of the global state management service and the primary device, a state of the primary device and the at least one secondary device;

managing, by at least one of the global state management service and the primary device, a transition between states of the primary device and the at least one secondary device; and

updating, by at least one of the global state management service and the primary device, a state of the primary device and the at least one secondary device, wherein absent a detection of a failure in one of the primary device and a secondary device, update operations are performed without interacting with the global state management service.

14. A method in accordance with claim 13, further comprising maintaining a portion of information pertaining to the state of the primary device and the at least one secondary device in the primary device and the at least one secondary device.

15. A method in accordance with claim 14, further comprising:

maintaining a normal state of the primary device and the at least one secondary device, wherein the normal state is indicative of the primary device and the at least one secondary device being operational;

while in the normal state, if a device fails, transitioning to a state indicative of a device being non-operational; and

while in the normal state, if one of a read from a device and a write to a device occurs, remaining in the normal state.

16. A method in accordance with claim 15, further comprising:

while in the state indicative of a device being non-operational, if the non-operational device becomes operational attempting to reconcile the non-operational device that is operational into the distributed system;

if the attempt to reconcile is successful, transitioning to the normal state;

if the attempt to reconcile is unsuccessful, remaining in the maintaining state indicative of a device being non-operational;

while in the state indicative of a device being non-operational, if a read from a device occurs, remaining in the state indicative of a device being non-operational;

while in the state indicative of a device being non-operational, if a write to the primary device occurs, transitioning to a state indicative of a device being stale, wherein a stale device comprises a non-operational device that has not been updated by a write operation.

17. A method in accordance with claim 13, further comprising, when the primary device and the at least one secondary device are non-operational, transitioning to a halt state indicative of neither the primary device nor the at least one secondary device being able to provide information.

18. A method in accordance with claim 13, further comprising:

if a failure is detected in a secondary device, granting permission, for a predetermined amount of time, by the global state management service to the primary device to perform at least one of a write operation and a read operation; and

prior to expiration of the predetermined amount of time and upon receiving a request to renew the permission, renewing, by the global state management service, the permission.

19. A method in accordance with claim 18, further comprising:

if a failure is detected in the primary device and subsequent expiration of the predetermined amount of time, reallocating, by the global management service, one of the at least one secondary device as a primary device.

20. A method in accordance with claim 13, further comprising:

performing a write operation in a single round of message exchange comprising;

providing, by the primary device, a write request to at least one live secondary device, wherein a live secondary device is a secondary device in which a failure has not been detected; and

receiving, by the primary device, a reply from each live secondary device.