Lossless recovery for computer systems with map assisted state transfer

• US 20050289169A1
• Filed: 10/29/2004
• Published: 12/29/2005
• Est. Priority Date: 06/29/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bolosky, William J., Adya, Atul, Lorch, Jacob R., Chaiken, Ronnie I.
• Granted Patent: US 7,472,129 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/203 using migration

Abstract

An architecture and implementation for losslessly restarting subsystems in a distributed file system is described. By partitioning functionality and logging appropriately across the kernel and user-level boundaries on a client, the user-level subsystem may be made losslessly restartable. A particular use of transactions achieves efficiency while retaining simplicity. Practical mechanisms for supporting state-based recovery in replicated state machines and like replica are described. In particular, a map assisted state transfer may include receiving one or more state updates, marshaling one or more active data-structures into a marshaled shadow, applying the received state updates to the marshaled shadow and re-instantiating the active data-structures by unmarshaling the marshaled shadow. While active data-structures may include invariance relationships, the marshaled shadow may be structured to support independence from invariance relationships between the shadows of the active data-structures, as well as efficient incremental state update application and unmarshaling to re-instantiate the active data-structures.

Claims

1. A computer-implemented method for map assisted state transfer, comprising:

receiving at least one state update;

marshaling at least one active data-structure into a marshaled shadow;

destroying said at least one active data-structure;

applying said at least one state update to the marshaled shadow; and

re-instantiating said at least one active data-structure by unmarshaling the marshaled shadow.

2. The method of claim 1, wherein the marshaled shadow comprises a shadow map.

3. The method of claim 2, wherein:

said at least one active data-structure comprises a plurality of programmatic objects arranged in an object-graph;

the marshaled shadow further comprises a plurality of shadowed objects corresponding to the plurality of programmatic objects; and

the shadow map facilitates placement of shadowed objects in the marshaled shadow independent of a need for class-specific object-graph navigation.

4. The method of claim 3, wherein facilitating placement of shadowed objects in the marshaled shadow comprises maintaining a map of keys to shadowed objects.

5. The method of claim 4, wherein each shadowed object comprises a marshaled object.

6. The method of claim 5, wherein:

each state update comprises at least one key and, for each of said at least one key, a marshaled replacement object; and

applying each state update to the marshaled shadow comprises, for each of said at least one key;

finding a matching key in the shadow map; and

replacing the associated shadowed object with the marshaled replacement object of the state update.

7. The method of claim 5, wherein:

at least one of said at least one state update comprises at least one key independent of a marshaled replacement object; and

applying said at least one said state update comprises, for each of said at least one key;

finding a matching key in the shadow map; and

deleting the associated shadowed object.

8. The method of claim 5, wherein:

each state update comprises at least one key and, for each of said at least one key, a marshaled replacement object; and

applying each state update to the marshaled shadow comprises, for each of said at least one key;

failing to find a matching key in the shadow map; and

adding the marshaled replacement object of the state update to the marshaled shadow.

9. The method of claim 1, wherein the marshaled shadow comprises data stored in volatile storage.

10. The method of claim 1, wherein the marshaled shadow comprises data stored in non-volatile storage.

11. The method of claim 1, wherein the marshaled shadow comprises data stored in a plurality of relational database tables.

12. The method of claim 11, wherein:

said at least one active data-structure comprises a plurality of programmatic objects each associated with at least one of a plurality of object classes;

each object class has a corresponding relational database table; and

each programmatic object is marshaled into the relational database table corresponding to said at least one of the plurality of object classes associated with the programmatic object.

13. The method of claim 12, wherein applying said at least one state update to the marshaled shadow comprises updating the relational database table corresponding to said at least one of the plurality of object classes associated with the programmatic object.

14. The method of claim 1, wherein:

said at least one active data-structure comprises a plurality of programmatic objects having an invariance relationship; and

the marshaled shadow comprises a plurality of shadowed objects free of invariance relationships.

15. The method of claim 1, wherein:

each active data-structure is a programmatic object associated with a plurality of methods comprising;

a marshal method; and

an unmarshal method;

marshaling each programmatic object into the marshaled shadow comprises invoking the marshal method of the programmatic object; and

re-instantiating each programmatic object comprises invoking the unmarshal method of the programmatic object.

16. The method of claim 1, wherein each state update comprises an incremental state update.

17. The method of claim 1, further comprising determining that a map assisted state transfer is required.

18. The method of claim 17, wherein determining that a map assisted state transfer is required comprises receiving a map assisted state transfer trigger message.

19. The method of claim 17, wherein determining that a map assisted state transfer is required comprises restarting after a failure has occurred.

20. The method of claim 17, wherein determining that a map assisted state transfer is required comprises determining that said at least one active data-structure lags a replica.

21. The method of claim 17, further comprising sending a map assisted state transfer trigger message.

22. A computerized system capable of map assisted state transfer, comprising:

a first component maintaining a state, the first component configured to, at least, send at least one state update message comprising at least one incremental change to the state;

a second component maintaining a replica of the state in at least one active data-structure, the second component configured to, at least;

receive said at least one state update message;

marshal said at least one active data-structure into a marshaled shadow;

destroy said at least one active data-structure;

apply said at least one incremental change to the marshaled shadow;

re-instantiate said at least one active data-structure by unmarshaling the marshaled shadow.

23. The system of claim 22, wherein the first component and the second component participate in a replicated state machine.

24. The system of claim 22, wherein the first component and the second component participate in a Windows File System (WinFS).

25. The system of claim 22, wherein the marshaled shadow comprises:

a plurality of programmatic objects arranged in an object-graph; and

a shadow map that facilitates placement of the plurality of programmatic objects in the marshaled shadow independent of a need for class-specific object-graph navigation.

26. The system of claim 22, wherein:

said at least one active data-structure comprises a plurality of programmatic objects having an invariance relationship; and

the marshaled shadow comprises a plurality of shadowed objects free of invariance relationships.

27. The system of claim 22, wherein:

each active data-structure is a programmatic object associated with a plurality of methods comprising;

a marshal method; and

an unmarshal method;

marshaling each programmatic object into the marshaled shadow comprises invoking the marshal method of the programmatic object; and

re-instantiating each programmatic object comprises invoking the unmarshal method of the programmatic object.

28. The system of claim 22, wherein the second component is further configured to, at least, determine that a map assisted state transfer is required.

29. The system of claim 22, wherein the first component is further at least configured to send at least one replica operational message comprising at least one replica operation.

30. A computer-readable medium having thereon a data structure comprising a marshaled shadow of a plurality of active data-structures having at least one invariance relationship, the marshaled shadow structured to support, at least:

independence from invariance relationships between shadows of the plurality of active data-structures;

application of at least one incremental state update to one or more of the shadows of the plurality of active data-structures; and

re-instantiation of the plurality of active data-structures by unmarshaling the marshaled shadow.

31. The medium of claim 30, wherein the marshaled shadow comprises:

a plurality of programmatic objects arranged in an object-graph; and

a shadow map structured to facilitate, at least, placement of programmatic objects into the marshaled shadow independent of a need for class-specific object-graph navigation.

32. The medium of claim 30, wherein:

each active data-structure is a programmatic object associated with a plurality of methods comprising;

a marshal method; and

an unmarshal method;

marshaling each programmatic object into the marshaled shadow comprises invoking the marshal method of the programmatic object; and

re-instantiating each programmatic object comprises invoking the unmarshal method of the programmatic object.

33. The medium of claim 30, wherein the marshaled shadow comprises data stored in volatile storage.

34. The method of claim 30, wherein the marshaled shadow comprises data stored in non-volatile storage.

35. The method of claim 30, wherein the marshaled shadow comprises data stored in a plurality of relational database tables.

36. The method of claim 35, wherein:

the plurality of active data-structures comprise a plurality of programmatic objects each associated with at least one of a plurality of object classes;

each object class has a corresponding relational database table; and

each programmatic object is marshaled into the relational database table corresponding to said at least one of the plurality of object classes associated with the programmatic object.