System and method for block conflict resolution within consistency interval marker based replication

• US 7,467,265 B1
• Filed: 09/20/2005
• Issued: 12/16/2008
• Est. Priority Date: 06/30/2005
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: Kiselev, Oleg, Colgrove, John A., Karr, Ronald S., Tawri, Deepak, Krishnamurthy, Raghu, Baird, Robert, Kekre, Anand A.
• Primary Examiner(s): Bragdon; Reginald G
• Assistant Examiner(s): Gu; Shawn X
• Application Number:
  US11/231,185
• Time in Patent Office: 1,183 Days
• Field of Search: None
• US Class Current: 711/161
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0815 Cache consistency protocols

Abstract

One goal of consistency interval replication is to achieve a consistent copy of data generated by independent streams of writes from nodes in a clustered/distributed environment. Two writes to the same block from different nodes may arrive at a replication target in a different order from the order in which they were written to primary storage. A consistency interval coordinator may analyze a list of blocks modified during a consistency interval to determine conflict blocks written to by two different nodes during the same consistency interval. Conflict resolution may involve a node reading data for a conflict block from primary storage and forwarding it to the replication target or a node completing a suspended in-progress write for the conflict block. Once the conflicts have been resolved, the replication target may checkpoint the data modified during the interval and nodes may resume writes to the conflict blocks for the new interval.

Claims

1. A method, comprising:

a plurality of nodes in a distributed computing environment sending replicated write requests to a replication target device, wherein each of the replicated write requests specifies a data location for storing data associated with the replicated write request;

wherein two or more conflicting write requests from different ones of the nodes each specifies a same data location;

in response to detecting the two or more conflicting write requests, a consistency interval coordinator sending a message to one of the plurality of nodes, wherein the message indicates said same data location; and

in response to receiving the message from the consistency interval coordinator, the node to which the message is sent sending data for said same data location to the replication target device, wherein the data for said same data location resolves an ordering ambiguity between the two or more conflicting write requests.

2. The method of claim 1, further comprising the replication target device generating a checkpoint of data associated with the replicated write requests, wherein the checkpoint includes the data for said same data location.

3. The method of claim 1, further comprising the node to which the message is sent reading the data for said same data location from a storage system separate from the replication target device in response to receiving the message from the consistency interval coordinator and prior to said sending data for said same data location.

4. The method of claim 1, wherein the message from the consistency interval coordinator includes an indication of a suspended replicated write request specifying said same data location, wherein said sending data for said same data location comprises the node to which the message is sent sending the suspended replicated write request to the replication target device.

5. The method of claim 1, wherein each replicated write request includes an indication of a first consistency interval.

6. The method of claim 5, further comprising the consistency interval coordinator sending a message to each of the plurality of nodes indicating the end of the first consistency interval.

7. The method of claim 5, wherein the data for said same data location is associated with a second consistency interval, and wherein said generating a checkpoint of data further comprises data for the second consistency interval.

8. The method of claim 1, further comprising each of the plurality of nodes sending a message to the consistency interval coordinator indicating one or more data locations modified by one or more replicated write requests sent by the respective node to the replication target device.

9. The method of claim 8, further comprising the consistency interval coordinator analyzing the respective one or more data locations modified by each respective one of the plurality of nodes to detect the two conflicting write requests.

10. A system, comprising:

a plurality of computing devices configured to implement;

a plurality of nodes in a distributed computing environment;

a replication target device coupled to the plurality of nodes; and

a consistency interval coordinator coupled to the plurality of nodes and the replication target device;

wherein each of the plurality of nodes is configured to send replicated write requests to the replication target device, wherein each of the replicated write requests specifies a data location for storing data associated with the replicated write request;

wherein two or more conflicting write requests from different ones of the nodes each specifies a same data location;

wherein in response to detecting the two or more conflicting write requests, the consistency interval coordinator is configured to send a message to one of the nodes, wherein the message indicates said same data location; and

wherein in response to receiving a message from the consistency interval coordinator the node to which the message is sent is further configured to send data for said same data location to the replication target device, wherein the data for said same data location resolves an ordering ambiguity between the two or more conflicting write requests.

11. The system of claim 10, wherein the replication target device is further configured to generate a checkpoint of data associated with the replicated write requests, wherein the checkpoint includes the data for said same data location.

12. The system of claim 10, wherein each of the plurality of nodes is further configured to read the data for said same data location from a storage system separate from the replication target device in response to receiving the message from the consistency interval coordinator.

13. The system of claim 10, wherein the message from the consistency interval coordinator includes an indication of a suspended replicated write request specifying said same data location, wherein in sending the data for said same data location, the node to which the message is sent is further configured to send the suspended replicated write request to the replication target device.

14. The system of claim 10, and wherein each replicated write request includes an indication of a first consistency interval.

15. The system of claim 14, wherein the consistency interval coordinator is configured to send a message to each of the plurality of nodes indicating the end of the first consistency interval.

16. The system of claim 10, wherein each of the plurality of nodes is further configured to send a message to the consistency interval coordinator indicating one or more data locations modified by one or more replicated write requests sent by the respective node to the replication target device.

17. The system of claim 16, wherein the consistency interval coordinator is further configured to analyze the one or more data locations modified by each respective one of the plurality of nodes to identify the two conflicting write requests.

18. The system of claim 17, wherein the consistency interval coordinator resides on the replication target device.

19. A device, comprising:

one or more processors; and

a memory coupled to the one or more processor, wherein the memory comprises program instructions executable by the one or more processors to implement a node in a networked computing environment, wherein the node is configured to;

send replicated write requests to a replication target device, wherein each of the replicated write requests specifies a data location for storing data associated with the replicated write request;

wherein a conflicting one of the write requests and a replicated write request sent to the replication target device from another node in the networked computing environment both specify a same data location;

receive a message from a consistency interval coordinator in response to detecting the conflicting write request, wherein the message indicates said same data location; and

in response to receiving the message send data for said same data location to the replication target device to resolve an ordering ambiguity between two or more conflicting write requests.

20. The device of claim 19, wherein the node to which the message is sent is further configured to read the data for the conflict location from a storage system separate from the replication target device in response to said receiving the message from the consistency interval coordinator.

21. The device of claim 19, wherein the message from the consistency interval coordinator includes an indication of a suspended replicated write request specifying said same data location, wherein in sending data for said same data location the node to which the message is sent is further configured to send the suspended replicated write request to the replication target device.

22. A device, comprising:

one or more processors; and

a memory coupled to the one or more processors, wherein the memory comprises program instructions executable by the one or more processors to implement a replication target in a networked computing environment, wherein the replication target is configured to;

receive replicated write requests from a plurality of nodes in the networked computing environment, wherein each of the replicated write requests specifies a data location for storing data associated with the replicated write request;

wherein two or more conflicting write requests from different ones of the nodes each specifies a same data location; and

receive data for said same data location from one of the plurality of nodes, wherein the data for said same data location is sent in response to receiving a message from a consistency interval coordinator in response to detecting the two or more conflicting write requests, and wherein the data for said same data location resolves an ordering ambiguity between the two or more conflicting write requests.

23. The device of claim 22, wherein the replication target is further configured to generate a checkpoint of data associated with the replicated write requests, wherein the checkpoint includes the data for said same data location.

24. A device, comprising:

one or more processors; and

a memory coupled to the one or more processor, wherein the memory comprises program instructions executable by the one or more processors to implement a consistency interval coordinator in a networked computing environment, wherein the consistency interval coordinator is configured to;

receive a message from each of a plurality of nodes in the networked computing environment, wherein each message indicates one or more data locations modified by one or more replicated write requests sent by the corresponding node to a replication target device;

identify, based upon the indicated modified data locations, two or more conflicting write requests from different ones of the plurality of nodes wherein each of the conflicting write requests specifies a same data location; and

send a message to one of the plurality of nodes indicating said same data location, wherein the message further instructs the node to which the message is sent to send data for said same data location to the replication target device, wherein the data for said same data location resolves an ordering ambiguity between the two or more conflicting write requests.

25. A computer accessible medium, comprising computer-executable program instructions to implement:

receiving a message from each of a plurality of nodes in the networked computing environment, wherein each message indicates one or more data locations modified by one or more replicated write requests sent by the corresponding node to a replication target device;

detecting, based upon the indicated modified data locations, two or more conflicting write requests from different ones of the plurality of nodes wherein each of the conflicting write requests specifies a same data location; and

in response to said detecting, sending a message to one of the plurality of nodes indicating said same data location, wherein the message instructs the node to which the message is sent to send data for said same data location to the replication target device, wherein the data for said same data location resolves an ordering ambiguity between the two or more conflicting write requests.