Systems and methods for replicating data in cluster environments

• US 8,478,718 B1
• Filed: 11/16/2010
• Issued: 07/02/2013
• Est. Priority Date: 11/16/2010
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Ranade, Dilip
• Primary Examiner(s): Nguyen, Cindy
• Application Number:
  US12/947,017
• Time in Patent Office: 959 Days
• Field of Search: 707/610, 707/616, 707/619, 707/625
• US Class Current: 707/610
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 11/2097 maintaining the standby controller/processing unit updated initialisation or re-synchronisation thereof G06F11/1658 and subgroups
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 67/025 for remote control or remote monitoring of applications
• CPC Class Codes: H04L 67/1095 Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes

Abstract

A method for replicating data in cluster environments may include (1) identifying a cluster of nodes configured to replicate common storage of the cluster, (2) identifying a first write operation issued by a first node to the common storage, (3) identifying a second write operation issued by a second node to the common storage after the first write operation, (4) identifying a completion time of the first write operation, (5) identifying a start time of the second write operation, (6) identifying a maximum potential skew between the first system clock and the second system clock, (7) determining that the first and second write operations are mutually independent by determining that the start time of the second write operation precedes the completion time of the first write operation by a span greater than the maximum potential skew, and then (8) replicating the first and second write operations in parallel.

Claims

1. A computer-implemented method for replicating data in cluster environments, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

identifying a cluster of nodes configured to replicate a common storage of the cluster;

identifying a first write operation issued by a first node in the cluster of nodes to the common storage;

identifying a second write operation issued by a second node in the cluster of nodes to the common storage, the second write operation issued after the first write operation;

identifying a completion time of the first write operation as recorded by a first system clock of the first node;

identifying a start time of the second write operation as recorded by a second system clock of the second node;

identifying a maximum potential skew between the first system clock and the second system clock;

determining that the first write operation and the second write operation are mutually independent by determining that the start time of the second write operation precedes the completion time of the first write operation by a span greater than the maximum potential skew;

replicating the first write operation and the second write operation in parallel based on the determination that the first write operation and the second write operation are mutually independent.

2. The computer-implemented method of claim 1, further comprising synchronizing the first system clock and the second system clock.

3. The computer-implemented method of claim 1, wherein the cluster of nodes is configured to replicate the common storage by providing continuous data protection for the common storage.

4. The computer-implemented method of claim 1, further comprising:

identifying a third write operation issued by a third node in the cluster of nodes to the common storage;

identifying a fourth write operation issued by a fourth node in the cluster of nodes to the common storage, the fourth write operation issued after the third write operation;

identifying a completion time of the third write operation as recorded by a third system clock of the third node;

identifying a start time of the fourth write operation as recorded by a fourth system clock of the fourth node;

identifying an additional maximum potential skew between the third system clock and the fourth system clock;

determining that the fourth write operation is dependent on the third write operation based in part by determining that the start time of the fourth write operation does not precede the completion time of the third write operation by a span greater than the additional maximum potential skew;

replicating the third write operation and the fourth write operation serially based on the determination that the fourth write operation depends on the third write operation.

5. The computer-implemented method of claim 1, wherein identifying the maximum potential skew comprises:

transmitting a first message from the first node to the second node, the first message including a first timestamp based on the time as identified by the first system clock that the first node transmitted the first message;

generating a second timestamp based on the time as identified by the second system clock that the second node received the first message;

transmitting a second message from the second node to the first node, the second message including a third timestamp based on the time as identified by the second system clock that the second node transmitted the second message;

generating a fourth timestamp based on the time as identified by the first system clock that the first node received the second message;

calculating the maximum potential skew based on the first timestamp, the second timestamp, the third timestamp, and the fourth timestamp.

6. The computer-implemented method of claim 1, further comprising determining that the maximum potential skew exceeds a predetermined threshold.

7. The computer-implemented method of claim 6, further comprising switching to an alternate dependency protocol until the first system clock and the second system clock are resynchronized.

8. The computer-implemented method of claim 6, further comprising suspending write operations from the first node and the second node until the first system clock and the second system clock are resynchronized.

9. The computer-implemented method of claim 6, wherein determining that the maximum potential skew exceeds a predetermined threshold comprises extrapolating the maximum potential skew based on an estimated rate of change of a skew between the first system clock and the second system clock.

10. The computer-implemented method of claim 1, further comprising:

identifying an additional node configured to join the cluster of nodes;

synchronizing a system clock of the additional node with the cluster before allowing the additional node to join the cluster.

11. A system for replicating data in cluster environments, the system comprising:

an identification module programmed to;

identify a cluster of nodes configured to replicate a common storage of the cluster;

identify a first write operation issued by a first node in the cluster of nodes to the common storage;

identify a second write operation issued by a second node in the cluster of nodes to the common storage, the second write operation issued after the first write operation;

identify a completion time of the first write operation as recorded by a first system clock of the first node;

identify a start time of the second write operation as recorded by a second system clock of the second node;

a skew module programmed to identify a maximum potential skew between the first system clock and the second system clock;

a determination module programmed to determine that the first write operation and the second write operation are mutually independent by determining that the start time of the second write operation precedes the completion time of the first write operation by a span greater than the maximum potential skew;

a replication module programmed to replicate the first write operation and the second write operation in parallel based on the determination that the first write operation and the second write operation are mutually independent;

at least one processor configured to execute the identification module, the skew module, the determination module, and the replication module.

12. The system of claim 11, wherein the skew module is further programmed to synchronize the first system clock and the second system clock.

13. The system of claim 11, wherein the cluster of nodes is configured to replicate the common storage by providing continuous data protection for the common storage.

14. The system of claim 11, wherein:

the identification module is further programmed to;

identify a third write operation issued by a third node in the cluster of nodes to the common storage;

identify a fourth write operation issued by a fourth node in the cluster of nodes to the common storage, the fourth write operation issued after the third write operation;

identify a completion time of the third write operation as recorded by a third system clock of the third node;

identify a start time of the fourth write operation as recorded by a fourth system clock of the fourth node;

the skew module is further programmed to identify an additional maximum potential skew between the third system clock and the fourth system clock;

the determination module is further programmed to determine that the fourth write operation is dependent on the third write operation based in part by determining that the start time of the fourth write operation does not precede the completion time of the third write operation by a span greater than the additional maximum potential skew;

the replication module is further programmed to replicate the third write operation and the fourth write operation serially based on the determination that the fourth write operation depends on the third write operation.

15. The system of claim 11, wherein the skew module is programmed to identify the maximum potential skew by:

transmitting a first message from the first node to the second node, the first message including a first timestamp based on the time as identified by the first system clock that the first node transmitted the first message;

generating a second timestamp based on the time as identified by the second system clock that the second node received the first message;

transmitting a second message from the second node to the first node, the second message including a third timestamp based on the time as identified by the second system clock that the second node transmitted the second message;

generating a fourth timestamp based on the time as identified by the first system clock that the first node received the second message;

calculating the maximum potential skew based on the first timestamp, the second timestamp, the third timestamp, and the fourth timestamp.

16. The system of claim 11, wherein the skew module is further programmed to determine that the maximum potential skew exceeds a predetermined threshold.

17. The system of claim 16, wherein the skew module is further programmed to switch to an alternate dependency protocol until the first system clock and the second system clock are resynchronized.

18. The system of claim 16, wherein the skew module is further programmed to suspend write operations from the first node and the second node until the first system clock and the second system clock are resynchronized.

19. The system of claim 16, wherein the skew module is programmed to determine that the maximum potential skew exceeds a predetermined threshold by extrapolating the maximum potential skew based on an estimated rate of change of a skew between the first system clock and the second system clock.

20. A non-transitory computer-readable-storage medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

identify a cluster of nodes configured to replicate a common storage of the cluster;

identify a first write operation issued by a first node in the cluster of nodes to the common storage;

identify a second write operation issued by a second node in the cluster of nodes to the common storage, the second write operation issued after the first write operation;

identify a completion time of the first write operation as recorded by a first system clock of the first node;

identify a start time of the second write operation as recorded by a second system clock of the second node;

identify a maximum potential skew between the first system clock and the second system clock;

determine that the first write operation and the second write operation are mutually independent by determining that the start time of the second write operation precedes the completion time of the first write operation by a span greater than the maximum potential skew;

replicate the first write operation and the second write operation in parallel based on the determination that the first write operation and the second write operation are mutually independent.