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

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.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to replication in general and, more particularly, to a method and apparatus for consistency interval replication snapshots in a distributed storage environment.

2. Description of the Related Art

Modern distributed shared storage environments may include multiple storage objects connected via one or more interconnection networks. The interconnection networks provide the infrastructure to connect the various elements of a distributed shared storage environment. Within the storage environment, file system abstractions may be built on top of multiple storage objects. These storage objects may be physical disks or storage aggregations, like logical volumes that distribute data across multiple storage devices. As the number of logical volumes and file system abstractions grows, the complexity of the entire storage environment grows dramatically.

Storage systems frequently use data redundancy mechanisms to ensure data integrity, consistency, and availability. Other uses for data redundancy may include backing up data, distributed load sharing, disaster recovery, or point-in-time analysis and reporting. One approach to data redundancy is to copy or replicate data from a primary storage system to a second or replicated storage system. In other words, a storage system may duplicate data written to the primary copy of a data block to redundant or replicated copies of that data block in other, secondary storage systems. In some designs this copying is done synchronously when the data I/O is preformed. In other designs this replication may be performed asynchronously with the second storage system's data state lagging the primary storage state by a time interval that can be anywhere from fractions of a second to many hours, depending on the design objectives and technologies used.

Under some failure conditions, volumes that contain redundant data may require consistency recovery. For example, a host may crash during a write to a volume, or a component in the interconnect infrastructure may fail. This may leave the volume in an inconsistent state. For example, if the volume is mirrored to protect against data loss due to a single disk failure, and stores two or more complete copies of the data, a system crash during a write may leave data copies in different states and with different contents. In such situations, a consistency recovery operation may need to be performed to resynchronize the data contents and state of mirrored storage devices. One well-known synchronization method involves copying the entire contents of one data copy to another, such that all copies of data in a redundant volume have the same data contents. This process can take a very long time in even modestly sized storage configurations. To reduce the impact of consistency recovery, another well-known consistency recovery method involves maintaining a bitmap of in-progress I/Os, sometimes called “scoreboarding” or “dirty region mapping.” Every bit in this bitmap represents a region of one or more blocks of the volume. A bit in this map is set, or “dirtied”, when an I/O to the volume is issued and cleared after the I/O has completed.

SUMMARY

One goal of replication is to achieve a consistent copy of data being generated by independent streams of writes from nodes in a clustered/distributed environment. One problem that may occur is that two writes to the same block from different nodes may arrive at a replication storage target in a different order from the order in which they were written to primary storage. In consistency interval replication, as described herein, nodes send writes to the replication target freely, but the nodes may be configured to suspend writes from time to time in such a way as to achieve a point at which the data on the replication target is consistent. The replication target can then generate a snapshot or checkpoint of the data and then continue to receive writes again until the next consistency point. Consistency interval replication may involve an interval coordinator to manage the consistency points. The time between two consistency points may be considered a consistency interval. In order to obtain points in time where the replicated data is consistent, consistency interval markers may be used. Consistency interval markers may ensure that when all data writes from source nodes are completed before a consistency interval snapshot or checkpoint is generated, and thus may ensure that the data in the checkpoint is consistent. Consistency interval marker based replication may involve an interval coordinator managing the starting and stopping of individual consistency intervals and thus the timing of consistency checkpoints or snapshots.

The transition between two consistency intervals may include a two-phase process. For example, when the interval coordinator determines that an interval transition should occur (i.e. the time limit for an interval has been reached), the coordinator may first send a message informing the nodes that the current interval is ending and requesting a list of data blocks modified during that interval. In the second phase of the interval transition, the interval coordinator may analyze the list of modified blocks from each node to determine a list of conflict blocks. Conflict blocks may be data blocks written to by two different nodes during the same consistency interval. This list of conflict blocks may be delivered to each node so that the nodes may suspend writes to the conflict blocks. Once the conflicts have been resolved, the replication target may generate a snapshot or checkpoint of the data written during the ending interval and nodes may resume writes to the conflict blocks for the new interval.

When resolving write conflicts for blocks, the interval coordinator may first determine if the write conflicts for a particular block are completed or whether a completed write conflicts with a suspended in-progress write. If the conflict involves an in-progress write, the interval coordinator may request that the node sending the in-progress write, complete that write and send it to the replication target with a special indication or tag informing the replication target that the data from the in-progress write should overwrite any earlier writes (during the same consistency interval) to the same block. Thus, the later data from the in-progress write may take precedence over earlier writes to the same block—thus obviating the need to resolve any conflict between two earlier, completed writes for the same block.

If two (or more) completed writes conflict on the same block and there is no in-progress write for the block, the interval coordinator may request the latest version of the data for the conflict block from the shared storage. For instance, in one embodiment, the interval coordinator may request one of the nodes in the distributed environment to read the data for the conflict block from primary storage and forward it to the replication target with a tag similar to that used with the in-progress write, described above. Thus, a write conflict may be resolved by a node re-sending the latest version of the data for the conflict block—ensuring that the correct (i.e. latest) version of the data is included in a checkpoint or snapshot generated at the end of the consistency interval.

DETAILED DESCRIPTION OF EMBODIMENTS

Consistency Interval Marker Based Replication

Consistency interval marker based replication, as described herein, may be implemented on distributed or clustered computing environments, such as the one illustrated inFIG. 1. As shown inFIG. 1, a set of source nodes, such as nodes110,112and114may write data to one or more primary storage devices, such as primary storage130and may also replicate the data writes to a replication target, such as replication target140. The system illustrated inFIG. 1may implement consistency interval marker based replication, as described herein. Consistency interval marker based replication may, in some embodiments, involve a two-phase distributed algorithm to obtain consistent snapshots, which also may be referred to as consistency points, or global snapshots, of data across the nodes in the distributed environment. Such consistent snapshots of data may facilitate various data copy and replication image services in the distributed environment. For example, consistency interval replication may provide periodic consistency checkpoints for crash recovery. A consistency interval may be defined as the time between two consecutive consistency points. In general, a consistency interval may begin just after one consistency point and end just before the next. Similarly, a consistency point includes data written during the previous consistency interval.

While consistency interval marker based replication is described herein mainly in reference to write requests from applications, file systems, volume managers and similar processes to storage devices, in general, consistency interval marker based replication may be utilized to provide consistent points or snapshots for any type of data stream. For example, consistency interval replication may provide consistency checkpoints or snapshots across collections of logs, across collections of storage objects, or across sets of message streams in the distributed or clustered environment. Please note that the terms “I/O” and “write” are both used interchangeably herein to refer to data written by a source node to the replication target during consistency interval marker based replication. Please further note that the term “application” is used to refer to any processes executing on source nodes and replicating data to a replication target. Thus, “application”, as used herein may refer to a volume manager, file system, database application, storage replicator, or an end-user application, as well as any other processes replicating data.

When implementing consistency interval marker based replication, data written to primary storage130may also be replicated to replication target140. Each actual data write from a node, such as from node110, may include an identifier of the current consistency interval. An interval coordinator, such as interval coordinator120may determine and distribute IDs for each consistency interval and may also determine the length of each interval and manage the transitions between intervals. Consistency intervals may be of various lengths and the length of each interval may be determined in any of numerous methods, according to various embodiments. For example, in one embodiment, all consistency intervals may be same length of time, say 5 seconds. In other embodiments however, consistency interval length may be based upon the amount of data replicated or the number of write requests during that consistency interval. In yet other embodiments, consistency intervals may be determined by an application which is generating data changes (e.g. a database application) and sets interval markers according to this application's view of data consistency (e.g. on transaction commits, or other consistency events recognized by such applications as appropriate recovery and restart points). Replication may be generally asynchronous in that the storage subsystem may complete the I/O to the application before it is replicated. This differs from the writes to base or primary storage, which generally don't complete to the application that submitted the I/O until it is completed on the base storage.

As noted above, interval coordinator120may manage the transitions between consistency intervals. For example, interval coordinator120may determine when the current interval should end and the next begin. Interval coordinator120may ensure that the data replicated during an interval is consistent, i.e. that that no write replicated during that interval depends upon a write that has not yet been replicated by the end of that interval. At the start of each consistency interval the interval coordinator may send a message to all source nodes in the distributed environment informing them of the new interval and possibly including an interval identifier to be included in writes from each node to the replication target. When sending a message, the consistency interval coordinator may utilize any suitable method of communication. In general, the term “message”, as used herein refers to the communication of information via any suitable method and/or transport. At the end of each interval the interval coordinator may also send a message to all nodes informing them that the interval is over. In some embodiments, a single interval transition message may be used to signal the transition between two consistency intervals. The individual nodes may, in some embodiments, be configured to suspend the completion of writes during the transition period between intervals. Suspending write completions may allow all in-progress writes from source nodes to complete and thus may allow the data to be consistent when the replication target checkpoints or saves a snapshot for the consistency interval. Thus, when transitioning between intervals, the interval coordinator may signal each node that the current interval has ended and, in response, each node may begin including the new interval's ID with each write to replication target140.

After sending an interval end message to each node, the interval coordinator may wait for an acknowledgment from each node before proceeding. This may allow for discovery of a crashed node. For example, if a node fails to respond or acknowledge a message from the interval coordinator, the interval coordinator may determine that the node has failed (or crashed) and may initiate recovery procedures for that node, as described below. After interval coordinator120has received an acknowledgment from every node, it may then send an interval start message informing nodes to complete held writes and to begin using the new interval's identifier in writes to replication target140.

When switching between intervals, each node may also be configured to send a consistency interval marker message to the replication target. For example, each node may send a message indicating that it has finished sending all writes for the current consistency interval. In other embodiments, each node may add a consistency interval marker or other indication of the interval transition into the first write message of a new interval. In yet other embodiments, each node may be configured to include sequence numbers with every write during an interval and such sequence numbers may roll over or reset at interval transitions. Thus, in some embodiments, the combination of a new interval ID and a sequence number rollover may indicate to the replication target a consistency interval marker for a particular node. When including sequence numbers with writes, each node may maintain its own sequencing and thus the sequence number may be considered node-specific. In yet other embodiments, the nodes may only be configured to include the new interval's ID with writes to the replication target and the replication target may consider the first write from a node that includes the new interval's identifier to be a consistency interval marker in the I/O stream.

Alternatively, in other embodiments, each node may send a consistency interval marker message to the interval coordinator rather than to the replication target. The interval coordinator may then send a single consistency interval marker message to the replication target after receiving individual consistency interval marker messages from the source nodes. Thus, in some embodiments, the replication target does not have to keep track of which nodes have sent consistency interval markers, but instead may rely upon the interval coordinator to send a single consistency interval marker message informing the replication target that all activity for the current interval is complete and that a checkpoint or snapshot for this interval may be saved/written.

In some embodiments, the replication target may save or store the writes received from nodes during a consistency interval in a log or other data structure separate from the main storage volume(s) for the replicated data. In some embodiments, writes from nodes may be stored in a persistent log for recovery purposes. Once the consistency interval is over and the nodes have indicated that all their data has been sent, the replication target may read the saved writes to create a snapshot or checkpoint of the data on replication storage volumes, sometimes called secondary storage. When checkpointing data for a consistency interval, the replication target may store only the changes to data made during the consistency interval, rather than make a complete copy or snapshot all the data. Thus, in some embodiments, a single consistency checkpoint may only include changes to the data made since a previous consistency checkpoint.

In other embodiments, however, a replication target may not log or spool the writes as they are received, but instead may store the data from writes to the replicated storage volumes immediately upon receipt from a node. Writing data immediately to replicated storage volumes may save time when processing the end of a consistency interval. However, it may be necessary to save complete snapshots of the data at each consistency point, rather than merely storing the data changes between two consistency points.

After receiving consistency point messages from every source node in the distributed or clustered environment, replication target140may notify interval coordinator120of that fact, according to some embodiments. In response, interval coordinator120may send an interval start message to the source nodes indicating the start of the new interval.

In some embodiments, each node may register with the interval coordinator or the replication target before sending writes. For example, node110may register with interval coordinator120and in response interval coordinator120may send node110the current interval identifier. In some embodiments, new nodes may join the replication process at any time, while, in other embodiments, new nodes may only be able to join at the start of a new consistency interval.

Block Conflict Resolution

Consistency interval marker based replication, as described herein, may be implemented for systems in which the data written by nodes110,112and114is read-shared, but not write-shared, according to some embodiments. That is, no two nodes may be able to write to the same storage block of data at the same time. When implementing consistency interval marker based replication in a write-shared environment, however, block conflict resolution may be utilized to ensure consistent data at consistency interval transitions. For example, when two nodes write to the same block of data during the same consistency interval, the system may use block conflict resolution to ensure the consistency of the data for that block within the consistency interval. When implementing block conflict resolution, interval coordinator120may track data blocks being written to by the nodes. Interval coordinator120may identify a block conflict when two nodes write to the same data block during the same consistency interval. When resolving such block conflicts, the interval coordinator may send a list of blocks with conflicts to each node. For example, if node110and node112each write to a particular data block, the interval coordinator may send an indication or identifier of the data block, such as the logical or physical storage address of the data block, to all nodes during the interval transition. Alternatively, in other embodiments, interval coordinator120may send an indication or identifier of the write requests, such as node specific sequence numbers, to the nodes that caused a block conflict. In response, the source nodes may be configured to suspend all writes to the conflict blocks until the conflicts can be resolved. Additionally, the interval coordinator may be configured to resolve conflicts by determining or “proving” the ordering of the writes to the conflict blocks. For example, in one embodiment, the particular writes from one node may be determined to be earlier than conflicting writes from another node, thus “proving” that the writes do not actual conflict so long as the ordering between those writes is maintained and communicated properly to the replication target.

In order to determine a list of conflict blocks, interval coordinator120may query every node to obtain a list of blocks written to by that node. Alternatively, each node may periodically send such a list of modified blocks to the interval coordinator during each interval. For example, each node may send a list of modified blocks at regular intervals, such as according to some fraction of the overall interval time length. For instance, in one embodiment, a node may be configured to send a list of modified blocks 5 times during an interval. In other embodiments, a node may be configured to send a list of modified blocks during idle time between write requests. Alternatively, in yet other embodiments, a node may be configured to send a list of modified blocks after a certain number of writes or after a predetermined number of blocks have been modified. Interval coordinator120may be configured to compare the blocks modified by each node to determine a list of conflict nodes that were written to be more than one node during the current interval, according to some embodiments. When informing the nodes of any block conflicts, interval coordinator120may include a list of conflict blocks in the interval end message, or in a specific block conflict message. Additionally, in some embodiments, interval coordinator120may be configured to initially send a preliminary list of block conflicts and subsequently send a final or updated list of block conflicts.

As noted above, source nodes, such as nodes110,112, and114, may send lists of modified blocks to the interval coordinator from time to time during a consistency interval. Rather than sending a message after every write, nodes may collect a list of modified blocks and send a single message including a list or batch of modified blocks. Nodes may include ranges of modified blocks rather than individually list contiguous blocks. As described above, the period used for sending list of modified block may be some fraction of the interval period itself. Alternatively, each node may send its list of modified blocks whenever that list exceeds some predetermined number of modified blocks. In general, each node may only include a modified block on a single list to the interval coordinator. Thus, even if a block is modified multiple times during the same consistency interval, it may only be included in only one list message to the interval coordinator, according to certain embodiments. Each time interval coordinator120receives a list of modified blocks from a node, interval coordinator120may merge the latest list with earlier lists. In general, interval coordinator120may be configured to maintain a single list of modified blocks for each node and to merge newly received lists of modified blocks into this single list, according to one embodiment. Additionally, interval coordinator120may maintain multiple such lists, one for each node. A node may also send a list identifying each individual modified block or, alternatively, may send ranges of modified blocks to save time, effort, and bandwidth. In general, any suitable method for identifying multiple data blocks may be used to send a modified block list from a node to the interval coordinator, according to various embodiments.

In general, interval coordinator120may send the list of block conflicts to all nodes in the distributed or clustered environment. In some embodiments, the interval coordinator may send such a list of block conflicts after sending an interval end message, but prior to sending the interval start message. In response to receiving a list of conflict blocks, each node may be configured to suspend any new writes for data blocks on the conflict list until the conflicts have been resolved and a new interval has begun. Additionally, in response to receiving a list of conflict blocks, each node may respond with an updated list of blocks modified after receiving the initial interval end message. For example, some writes may be in process when a node receives an interval end message from interval coordinator120and thus the blocks modified by those writes may not have been included in any list of modified blocks previously sent to the interval coordinator. In some embodiments, interval coordinator120may then use the updated or final lists of modified blocks from each node to determine a final list of conflict blocks and may distribute the final list of conflict blocks to the every node.

Interval coordinator120may resolve conflicts to data blocks in various ways. In general, interval coordinator120may consider two different types of write conflicts. Firstly, two or more writes may modify the same block during the same consistency interval. The replication target may receive two writes to the same data block by two different nodes in a different order than the order in which those writes were originally completed on the primary data storage. In other words, there may exist an ordering ambiguity between the two writes. For example, node110may write a particular data block and node112may subsequently overwrite node110's write with another write to that same data block. However, it may be possible, due to network congestion or other issues, that when the writes to that data block are sent to replication target140they arrive out of order. Thus, while node112may have actually written to the data block last, its write may arrive first to replication target140. Without recognizing and resolving such block conflicts a checkpoint or snapshot for the current interval may include the wrong version of data for blocks written to be more than one node, in some embodiments. Thus, any recovery made using such a snapshot may result in data corruption.

In general, replication target140and interval coordinator120may have no way of knowing the proper order of multiple writes to a single data block, and thus no way of resolving the ordering ambiguity. In order to ensure that the consistency checkpoint or snapshot generated at the end of the current consistency interval has a correct (i.e. consistent) version of the data, the data block may be read from primary storage130and sent to replication target140, in certain embodiment. In some embodiments, interval coordinator120may request that a particular node read the data for a conflict block from primary storage130and forward it to replication target140. In other embodiments, however, interval coordinator120may be configured to directly read the data from primary storage130and forward it to replication target140.

In some embodiments, writes conflicts may be resolved by determining the correct ordering of conflicting writes to a data block using specific knowledge of the data being written. For example, in one embodiment, the replicated data may be for a shared database and replication target140may be able to inspect the contents of each conflicting write and determine from the individual contents of each write their correct ordering. For instance, in one embodiment, each write to the database may include a timestamp or a global sequence number that may allow replication target140to determine the correct ordering of writes. In other embodiments, however, replication target140and interval coordinator120may not be able to determine the correct ordering of conflicting writes to the same data block and thus may read, or cause to be read, data for the conflict block from primary storage130to ensure that the replicated data is consistent with the primary data at the time of the consistency interval transition, and thus, when a consistency checkpoint or snapshot is generated.

One benefit to having source nodes, such as nodes110,112, and114, suspend writes and/or write completions during consistency interval transitions is that it allows data for a conflict block to be read from primary storage130before any of the nodes overwrite that block during the next interval, according to some embodiments. Thus, if source nodes are allowed to continuing writing data during consistency interval transitions, one of the nodes may overwrite a conflict block, thus preventing interval coordinator120and/or replication target140from resolving that conflict by obtaining the latest version of data for that block from primary storage130.

Alternatively, as noted above, there may also be conflict between one or more completed writes to a data block and an in-progress or uncompleted write to the same data block. For example, when the current interval ended, a node may have suspended a write to a conflict block. In such a case, interval coordinator120may request, via a message or any other form of communication, that the node holding the suspended in-progress write completion that write including a special indication that the write completion is resolving a conflict and that the write should overwrite early writes to the conflict block and therefore be included in any checkpoint or snapshot generated for the just ended interval. By requesting completion of the in-progress write, interval coordinator120may eliminate the need to determine the order of other, previously completed, writes to the same block, and may also avoid a read operation to get the last written version of the data.

If interval coordinator120and/or replication target140cannot resolve a conflict block, such as in the event that one of the nodes has crashed or running very slowly or if the block cannot be read from primary storage130, the current interval may be considered invalid and combined with the next interval to make one, larger interval, as will be discussed in more detail below.

After resolving all block conflicts, interval coordinator120may send a message to all nodes informing them that the current interval is closed and that all writes and write completions may be resumed, in some embodiments. The interval coordinator may also send a completion message to the replication target regarding the successful resolution of all block conflicts. In response, the replication target may generate a consistency checkpoint or snapshot of the data, thereby creating a consistency point in the replicated data corresponding to the end of the consistency interval. Alternatively, in other embodiments, each source node may be configured to send consistency interval markers to the replication target after completing all processing, including conflict resolution processing, for the current interval. Thus, the replication target may generate a consistency point or snapshot in response to receiving consistency interval markers from every node, according to some embodiments.

In some embodiments, interval coordinator120may send a single message that serves multiple purposes to nodes. For example, in one embodiment, the interval coordinator may send a custom message to each node that includes: a final list of block conflicts, permission to resume writes for non-conflict blocks, a list of blocks the node should forward from primary storage to the replication target, and a list of in-progress writes that the node should complete to resolve block conflicts. In response to such a message, each node may be configured to resume writes to non-conflict blocks, send the requested nodes to the replication target, complete the designated in-progress writes, and send a consistency interval marker message to the replication target (and/or the interval coordinator), according to some embodiments. As noted above, when the replication target (and/or interval coordinator) receives a consistency interval marker message from every node, processing for the current interval may be considered complete and a checkpoint or snapshot of the data may be generated. Thus, in some embodiments, the interval coordinator may send individual messages for each step of the block resolution process, while, in other embodiments, the interval coordinator may send a single message to each node containing all the information that node needs in order to complete interval transition processing and block conflict resolution.

In some embodiments, the nodes may be configured to start sending data for a new consistency interval before all block conflicts for the current interval have been resolved. Thus, the replication target may receive writes for a new interval while also receiving conflict resolving writes for the current interval. Accordingly, replication target140may, in some embodiments, be configured to maintain separate write logs, not only for each node but also for each active interval. Once all block conflicts for the current ending interval have been resolved and the consistency checkpoint generated, replication target140may be configured to delete or otherwise clean up the write logs for the current interval, in one embodiment.

While the above description of block conflict resolution generally refers to either the interval coordinator or the replication target resolving write conflicts on blocks, in some embodiments, a separate shared-write coordinator or block coordinator may resolve such conflicts. For example, in some embodiments, a shared-write coordinator, such as shared-write coordinator150may be configured to resolve write conflicts. Interval coordinator120may forward a list of conflict blocks to shared-write coordinator150during the interval transition and rely upon shared-write coordinator150to resolve the conflicts. Shared-write coordinator150may perform the same functions to resolve write conflicts described above regarding interval coordinator120. Additionally, both interval coordinator120and shared-write coordinator150may reside on a single device or may be part of replication target140, according to various embodiments. Also, in some embodiments, the number and length of intervals used by the interval coordinator and the shared-write coordinator may not be the same. For instance, there may be more shared-write intervals as long as consistency intervals correspond to a shared write coordination interval.

Thus, in some embodiments, replication target140may perform all the functionality of a replication target, an interval coordinator and a shared-write coordinator. In another embodiment, however, interval coordinator120may perform all functionality of both an interval coordinator and a shared-write coordinator separately from replication target140. Furthermore, interval coordinator120and/or shared-write coordinator150may reside on virtually any node in the distributed or clustered environment, such as on any of nodes110,112and/or node114, as well as on replication target140, or may also reside on a separate, dedicated device or devices.

When implementing consistency interval marker based replication in a write shared situation, interval coordinator120may, during a consistency interval transition and before resolving block conflicts, request that all nodes suspend writes to the blocks in conflict. Thus, in some embodiments, each node may temporarily suspend all writes to all blocks and then, after receiving a list of conflict blocks (whether provisional or final), resume writes to block that are not on the block conflict list. However, source nodes may be configured to include such writes to non-conflict blocks as part of the next, new consistency interval, rather than the currently ending interval. Additionally, in some embodiments, when writes cross the consistency interval boundary, some writes may be assigned to one interval and others may be assigned to a next interval. As noted above, nodes may include the interval ID along with writes, allowing the replication target to distinguish between writes for different consistency intervals during a consistency interval transition. In some embodiments, Nodes may suspend writes to conflict blocks until receiving a message from interval coordinator120confirming that all conflicts have been resolved.

When implementing consistency interval marker based replication, as described herein, replication target140may store received writes in one or more logs, according to some embodiments. In one embodiment, replication target140may maintain a separate write log for each node, while in other embodiments, replication target140may maintain only a single log file, but may include a node identifier when storing the writes. Thus, in general, replication target140may be configured to store (and access) each received write on a node-specific basis. Alternatively, in one embodiment, only interval identities and node-specific interval completions may be logged.

Additionally, recovery information, such as in-progress writes “scoreboards”, synchronous write logs, or other types of recover information, may be maintained for the data being replicated. Thus, in the event of a node (either a source node, the interval coordinator or a shared write consistency coordinator) crashing, the recovery information may be used to reconstruct a consistent data image for replication. For example, when maintaining an in-progress writes scoreboard using a bitmap, individual bits representing ranges or regions of data storage are marked (e.g. set to 1) when the corresponding region is modified/written to. A bit may be cleared when writes to the corresponding region have been completed and/or logged successfully. In the event of a node crashing, the recovery information may be used to determine those regions of the data that must be rebuilt or made consistent for the replicated backup. While in some embodiments, replication target140may maintain both node-specific write logs and recovery information, in other embodiments, either the write logs, the recovery information or both may be maintained by the source nodes or by one or more other processes/entities in the distributed environment. In general, any method or manner of persisting a particular write may be used as long as information that the particular blocks were modified can be retained (or at least recovered) between the times blocks are written to the primary storage until all replication processing is complete.

Target Controlled Consistency Interval Replication

In some embodiments, a replication target, such as replication target140, may perform some or all of the same functions as an interval coordinator. Thus, the replication target may send out interval start and end messages as well as track and resolve block conflicts. When utilizing target controlled consistency interval replication, source nodes, such as nodes110,112and114, may initially register themselves with replication target140and replication target140may respond by sending each node the current interval ID, according to some embodiments. As the nodes send writes, replication target140may store a copy of each write in a node-specific log and may also maintain a list of blocks modified by each node. Thus, when implementing target controlled consistency interval replication, the replication target may stream, or store, the received writes into logically separate logs and may also retain copies of the blocks written in memory, again logically separated by source (i.e. node).

Additionally, replication target140may maintain a list of block conflicts needing resolution. When an interval ends, replication target140may not have to request lists of modified blocks from the nodes as it may already have this information from the individual writes, according to some embodiments. The resolution of individual block conflicts may be performed as described above when using a separate consistency interval coordinator, in some embodiments.

At the end of a consistency interval, replication target140may, in some embodiments, send a message to all nodes signaling the end of the current interval. In one embodiment, each node may send a specific acknowledgment message to replication target140in response to the interval end message, while, in other embodiments, nodes may not send a specific acknowledgement message but instead may merely begin including the new interval's ID in writes to the replication target as an acknowledgement of the interval transition. However, if a node has no new write operations to send to the replication target, a specific interval end message may be required in some embodiments.

After a consistency interval has ended, replication target140may not immediately generate a consistency checkpoint or snapshot, according to some embodiments. Instead, in some embodiments, the replication target may hold the accumulated writes for one or more additional intervals to ensure that any writes arriving late (i.e. after the end of the interval) may also be included in the generated checkpoint or snapshot. Thus, in some embodiments, replication target140may include node-specific write logs for more than one interval. For example, replication target140may, in one embodiment, be configured to wait two consistency interval lengths before generating a checkpoint for a consistency interval. Thus, while receiving writes during consistency interval3, replication target140may, in some embodiments, be holding the received writes for intervals1and2. Once interval three has ended, the replication target may then generate a checkpoint or snapshot of the data from interval1, according to one embodiment. In some embodiments, replication target140may not perform any conflict resolution processing until after waiting sufficient time to ensure the receipt of any late arriving writes. In other embodiments, however, replication target140may analyze and perform conflict resolution immediately after an interval as ended and perform additional conflict resolution if required by late arriving writes.

Another method, according to some embodiments, to help ensure that all writes for a consistency interval have been received before generating a checkpoint or snapshot, may be to have the source nodes include a node-specific sequence number with each write sent to the replication target. Thus, in some embodiments, replication target140may be configured to determine that one or more writes have not been received, based on the sequence numbers, and request the resending of those writes. Alternatively, in other embodiments, each node may be configured to send a list of IDs for the writes associated with a consistency interval, thus allowing the replication target to verify that it has received all the writes sent by the node. In one embodiment, each node may include node-specific sequence numbers and may also include the sequence number of the last write sent in an acknowledgement to an interval transition message from replication target140. In general, consistency interval marker based replication, with or without block conflict resolution, may include the ability for a replication target to determine whether not it has received all the writes sent from source nodes during a consistency interval before generating a consistency checkpoint or snapshot for that interval.

When including block conflict resolution in target controlled consistency interval replication, replication target140may compare the writes it has received from all source nodes to determine whether there are any block conflicts, i.e. two nodes writing to the same block during the same consistency interval. In some embodiments, the replication target may be able to determine the correct ordering of writes to a single block. For example, in one embodiment, replication target140may have specific knowledge of the structure and/or nature of the data being written, such as for a custom database application, and thus may be able to use the content of writes to determine their proper ordering. For instance, as described above, the replication target may be able to use sequence numbers, transaction IDs or other characteristics of the data being written to determine the correct ordering of the writes and thus, the final (i.e. correct) state of the block at the end of the consistency interval.

Additionally, in some embodiments, the source node may include node-specific timestamps in each write sent to replication target140and replication target140may be able to determine the proper ordering of multiple writes to a single block based upon those timestamps. However, since individual clocks used for timestamps from different nodes may be skewed with respect to each other, replication target140may only be able to determine the correct order for writes sent sufficiently apart in time to overcome skew and drift between the source nodes' individual clocks, according to one embodiment. Thus, even if nodes include timestamp information with each write, replication target140may not be able to always determine the proper ordering of writes sent close together in time.

If replication target140cannot determine the proper ordering of multiple writes to a single block, replication target140may be configured to request that one of the nodes, such as node110, read the block from primary storage130and forward it to replication target140, as described above regarding interval coordinator120. As noted above, the data read from the primary storage130may not be valid if any node has overwritten the relevant block during a later consistency interval. Replication target140may, in one embodiment, be configured to search node-specific write logs for later intervals when determining whether or not a conflict block was overwritten in a later interval. Thus, in some embodiments, the nodes may be configured to suspend writes to conflict blocks until all conflicts have been resolved, as discussed above.

Combining Consistency Intervals

If a conflict block was overwritten during a later interval before the conflict was resolved, the current consistency interval may be declared invalid and combined with one or more later intervals, according to one embodiment. For example, replication target140may use a 1 second consistency interval length, and may have generated a consistency checkpoint for a consistency interval ending at time 2:15:59. If, in this example, the consistency interval ending at 2:15:30 includes two writes to the same block for which the proper ordering cannot be determined, replication target140may search the write logs for the consistency interval ending at 2:15:31 for writes to the same conflict block. If, the consistency interval ending at 2:15:31 includes only a single write to the conflict block, or alternatively, two or more writes for which the ordering can be determined, that data may be used for the conflict block and the two consistency intervals (ending at 2:15:30 and 2:15:31, respectively) may be combined into single, two second consistency interval, according to some embodiments. Thus, replication target140, in this example, may not store a consistency checkpoint for the consistency interval ending at 2:15:30, in one embodiment.

If, using the same example from above, the consistency interval ending at 2:15:31 also included multiple writes to the conflict block and the ordering of those writes cannot be determined, replication target140may search yet later consistency intervals for the contents of the conflict block. If say, the consistency interval for 2:15:32 does not include any writes to the conflict block, the replication target may, in some embodiments, request that a node, such as node110, read the contents of the block from primary storage130, which would represent the correct contents of the block at the end of the 2:15:31 interval (since no node has overwritten it since). Replication target140may, in some embodiments, then use that data to resolve the conflict for the block in question and combine the two consistency intervals ending at 2:15:30 and 2:15:31 into a single, 2 second, interval, as described above. Please note, that in both of the above cases, the state of the replicated data may not be consistent at 2:15:30, but may be consistent at both 2:15:29 and 2:15:31. In another example, one node may be slower to respond to an interval completion message than two other nodes that may respond more quickly. Thus, any conflicts between the two quicker nodes may already be resolved by the time the first node does respond to the interval completion message. When the first node does respond, it may or may not have additional conflicts with the other two nodes. If the first node does not conflict with any writes from the other two nodes, no further conflict resolution is required.

In general, consistency interval marker based replication may be seen as a means for coordinating across virtually any collection of data sources which need to be copied or replicated for various copy services, or that need to be asynchronously processed for various other services. Additionally, consistency interval marker based replication may be implemented for any collection of systems that share one or more data volumes and replicates to other, secondary volumes, according to various embodiments. The data sources for consistency interval marker based replication may represent any level of the typical I/O stack. For instance, volume managers, file systems, databases storage replicators (in hardware or software), and end-user applications are a few types of data sources for which consistency interval marker based replication may be utilized. When implementing consistency interval marker based replication, various asynchronous copy services may be performed in a generally I/O efficient and scalable manner in clustered and/or distributed environments including multi-host environments. Such asynchronous copy services may include, but are not limited to asynchronous mirroring, replication, snapshots, finely grained in-time backups for continuous data protection, among others.

Please note that the networked computing environment illustrated inFIG. 1represents only one possible environment in which consistency interval marker based replication, with or without block conflict resolution, may be implemented. For example, network100, as illustrated inFIG. 1, may comprise any of various network technologies according to various embodiments. Network100may be a local area network, wide area network, intranet network, Internet network, or many other types of network. Network100may be designed to be continuously available (although network outages may occur), or may be intermittent (e.g. a modem connection made between a computer system in a user's home and a computer system in a user's workplace).

Network100may utilize any of a number of different physical networking technologies including, but not limited to, Fiber Channel, Ethernet, Fast-Ethernet, Gigabit-Ethernet, Myrinet, Infiniband, VAX CI, or ServerNet, or others. Network100may be configured according to a number of different network topologies including, but not limited to, star, ring, token-ring, token-bus, scatternet, dual-ring, mesh, etc. Network100may also be configured to utilize a combination of different networking technologies and/or topologies. Additionally, Network100may comprise shared storage or shared memory for communicating between different computer systems or between processes within the same computer system, according to various embodiments.

In some embodiments, Network100may be the interconnect network for any of various distributed shared storage environments, including, but not limited to, network file system (NFS), common Internet file system (CIFS), storage area network (SAN), network attached storage (NAS), storage-network aggregation, multi-site block storage, object-based storage devices (OBSDs), or other asymmetric, out-of-band, or shared storage models. Furthermore, the network environment illustrated inFIG. 1, may represent any of various types of distributed or clustered networking environments, according to various embodiments. For example, in one embodiment, consistency interval marker based replication may be implemented in a distributed environment, such as a multi-node system in which blocks of data on a storage volumes are virtualized across various nodes in the distributed environment, or in a clustered environment, such as a multi-node system in which all volume data is distributed uniformly across all nodes sharing the volumes.

Similarly, nodes110,112and114may, in different embodiments, represent any of a number of different types of applications and/or processes at various levels in an I/O stack, such as volume managers, file systems, databases storage replicators (in hardware or software), and end-user applications, among others. Additionally, primary storage130and replication target140may represent any of various sorts of single node or multi-node storage devices and/or storage systems including, but not limited to, disk drives, disk arrays, storage controllers, array controllers, tape drives, optical drives, tape libraries, RAID systems, and/or object based storage devices (OBSD).

Various aspects of consistency interval marker based replication and block conflict resolution will be described in more detail below.

FIG. 2is a block diagram illustrating the relationship between source nodes110,112and114, replication target140, and the replicated data, according to one embodiment. As described above, multiple source nodes, such as node one110, node two112, and node three114, may send write requests to replication target140asynchronously from the I/O stream to primary storage130. In some embodiments, the message used to send a write to replication target140may include a current interval identifier. For example, node one110may send write message200to replication target140and may include interval identifier210in the message. Thus, in the embodiment and example illustrated byFIG. 2, node one may send writes during consistency interval3. While, simple, numeric interval identifiers are used herein by way of example to identify consistency intervals, in other embodiments, more complex interval IDs, such as ones including date/time information, replication target information, or even universally unique global identifiers, may be also used.

As described previously, replication target140may maintain multiple node-specific write logs to store the writes from nodes during consistency interval. Thus, as illustrated inFIG. 2according to one embodiment, replication target140may maintain three separate write logs, node one write log220, node two write log230, and node three write log240, to store write I/Os from node one110, node two112, and node three114, respectively. Additionally, in other embodiments, replication target140may also maintain different sets of node-specific write logs for different consistency intervals, as noted above. For example, replication target140may, in one embodiment, be configured to hold the writes for a previously ended consistency interval while collecting writes for a later consistency interval. Thus, whileFIG. 2illustrates node-specific write logs for only one (the current) consistency interval, replication target140may also maintain node-specific write logs for other, previously ended, consistency intervals.

WhileFIG. 2shows three independent node-specific write logs, in some embodiments, replication target140may store the writes from nodes in different ways. For example, in one embodiment, replication target140may store writes from all nodes in a single log configured to separately maintain the node-specific writes. For example, entries for a single, multi-node write log may include a node identifier or may include some other way to determine which writes were sent from which nodes, according to some embodiments. In some embodiments, node-specific write logs220,230, and240may be stored on disk, while in other embodiments they may be kept only in memory. Although, when maintaining such write logs in memory, replication target140and/or nodes110,112, and114may be configured to maintain recovery information, such as an in-progress writes scoreboard style bitmap, or synchronous write logs for use in case of a system error or crash. In other embodiments however, writes from nodes110,112, and114may be maintained both on disk and in memory. In general, replication target140may be configured to store writes from nodes in any fashion suitable of storing the write data while allowing access the data on a node-specific basis.

After a current consistency interval ends, such as interval3inFIG. 2, replication target140may generate a consistency checkpoint or snapshot, or otherwise save the data from writes during the interval to a replication store, such as checkpoint store250.FIG. 2illustrates checkpoint store250including two consistency points already saved, interval1consistency point260and interval2consistency point270. In one embodiment, a consistency snapshot of the entire data (not just the data written in the current consistency interval) may be generated. In other embodiments however, only those changes to data made during the current interval may be stored in checkpoint store250or other replicated data store.

WhileFIG. 2illustrates three nodes, three node-specific write logs and three intervals, other embodiments may include many more such nodes, logs and intervals. Logs may also be combined, so that one log includes entries from several nodes or for several purposes. Furthermore, saving consistency points in a checkpoint store on replication target140is only one of many possible methods for storing replicated data. In other embodiments, consistency point data may be stored on devices separate from replication target140, or even forwarded to completely separate replication system.

FIG. 3is a block diagram illustrating, according to one embodiment, the logical flow of communication between a node, an interval coordinator, and a replication target while implementing consistency interval marker based replication. The logical communication flow illustrated inFIG. 3represents an example exchange among interval coordinator120, node110, and replication target140during a consistency interval transition (i.e. the ending of one interval and the start of another). Thus, as described above, node110may send writes, each including the ID of the current interval, to replication target140and replication target140may, in some embodiments, send acknowledgments back to node110, as illustrated by arrows320and325.

Additionally, in some embodiments, node110may maintain or update a recovery map or log indicating blocks or regions of blocks that have been changed. For example, a dirty region bitmap, in which each bit represents a range of data blocks, may be maintained, either for each node, or for all nodes together, according to different embodiments. Alternatively, in other embodiments, a sequential, synchronous, log of all writes may be maintained during the current interval and flushed once a consistency checkpoint or snapshot has been generated for the internal by replication target140. In general, the term “recovery map” is used herein to refer to any sort of data structure used to store or maintain recovery information regarding the writes sent by the source nodes to the replication target, including, but not limited to, dirty region tracking, synchronous data logs, metadata logs, data change objects, etc. Likewise, the term “log” is used herein to refer to any sort of data structure used to store or maintain a record of operations, such as the data being written, the time, nodes, and/or block numbers involved, in a manner that allows retrieval of individual operations as discrete items which can be ordered in a sequence using a unique identification key associated with each item, including, but not limited to, logs, databases, etc.

Thus, in some embodiments, node110may also update a recovery map after sending a write to replication target140. For instance, node110may set (to 1) bits in dirty region bitmap corresponding to the blocks being written. After receiving acknowledgement from replication target140, node110may then clear those bits (to 0). In one embodiment, a single, combined, recovery map may be maintained for all data written by all nodes. In other embodiments, however, a separate recovery map may be maintained for each node. Maintaining a separate recovery map for each node may allow an interval coordinator, such as interval coordinator120, to perform recovery processes for a crashed node based on the contents of that node's recovery map. Please note that while in some embodiments, each node may interact with and update its own recovery map, in other embodiments, a single recovery process may maintain all the nodes' individual maps based upon information supplied by the nodes.

In certain embodiments, each node may maintain two such recovery maps, one for the currently active consistency interval, and one for the immediately previous consistency interval. Since, in some embodiments, nodes may be sending writes for a new consistency interval while the previous (just ended) interval is still being processed, such as for block conflict resolution. For example, in one embodiment, block conflicts may still be being resolved while nodes are already sending writes (to non-conflict blocks) for the next interval. Thus, when using two recovery maps, a node may use one as an active map for recording changes made during the current interval and may use the other as a replay map for the previous interval. A node may swap the two maps (i.e. make the active map the replay map and clear out the replay map to make it the active map) at interval transitions. Some embodiments may keep maps for more than one previous interval, allowing more flexibility in conflict resolution at the expense of greater memory consumption. As the workings and use of recovery maps, and recovery information in general, are well understood in the art, they will not be discussed in detail herein.

At some point interval coordinator120may determine that it is time to end a current interval and thus may send a consistency interval end message to node110, as represented by arrow300inFIG. 1. As discussed above, there are multiple ways that interval120may determine when to end a consistency interval. In response to the consistency interval end message, node110may send an acknowledgement message back to interval coordinator120, as indicated by arrow305. Also, as noted above, node110may also suspend completion of writes in response to receiving the interval end message, according to some embodiments. When suspending completion of writes during an interval transition, node110may, in some embodiments, continue to send writes to replication target140, but may not acknowledge the completion of those writes to any application that performed the write originally. Thus, if the node crashes during the interval transition, the application cannot assume that the writes were completed and thus may have no expectations regarding the state of the relevant data, according to some embodiments.

After receiving acknowledgment messages from all nodes in the system, interval coordinator120may send another message to all the nodes. In some embodiments, interval coordinator120may send a message including the ID of the new interval that is starting, as indicated by arrow310A. In other embodiments, however, interval coordinator120may include the new interval ID in the interval end message and, after receiving acknowledgements from all nodes, interval coordinator120may send a message signaling the nodes to resume suspended write completions. When resuming suspended write completions, node110may notify the application that originally performed a write that was suspended of the successful completion of that write, according to certain embodiments.

After node110has sent all writes for the current interval (that is, the interval just ending), node110may, in some embodiments, send a consistency point or a consistency interval marker message to replication target140. Node110may inform replication target110that it has finished sending writes for an ending interval in a number of ways. In some embodiments, node110may send a specific consistency interval marker message. In other embodiments, however, node110may include a consistency point indicator in the first write of the new interval. After receiving consistency interval markers from all nodes in the system, replication target140may send a message, such as a interval transition message, to interval coordinator120indicating that all writes for the ending interval have been sent by the nodes, as indicated by arrow315.

In some embodiments, interval coordinator120may wait until receiving an interval transition message from replication target140indicating that all nodes have sent their respective consistency interval markers before sending a consistency interval ID message to the nodes, as indicated by arrow310B. Thus, in some embodiments, interval coordinator120may send the new interval ID to node110at the end of the current interval, such as in a consistency interval end message, while, in other embodiments, interval coordinator120may wait until after receiving acknowledgements of the interval transition before sending the new interval ID. In yet other embodiments, interval coordinator120may wait until all nodes have sent all writes for the ending interval, indicated by replication target140receiving consistency interval markers from all nodes, before sending the new interval ID.

Additionally, in some embodiments, the interval ID message may also indicate that nodes may resume writes and/or write completions, while, in other embodiments, interval coordinator120may send a separate message instructing nodes to resume writes and/or write completions. After the interval transition and after node110has received the new interval ID from interval coordinator120, node110may then send writes including the new interval ID to replication target140, as indicated by arrow340. The process may continue with node110sending writes to replication target140and replication target140acknowledging those writes until interval coordinator120ends the new interval with another interval end message.

Please note that the communication flow logically illustrated inFIG. 3regards consistency interval replication for a system in which multiple nodes are read-sharing one or more data volumes, but in which the data is not write-shared. Thus, no two nodes may be able write to the same block of data at the same time. In other words, the communication flow logically illustrated inFIG. 3does not include any provision for block conflict resolution, as that will be described in more detail below regardingFIGS. 5-9.

FIG. 4is a flowchart illustrating one embodiment of a method for consistency interval maker based replication, as described herein. As described above, multiple nodes, such as applications, file systems, or volume managers, etc., may send writes to a replication target including the current interval ID with each write, as illustrated by block400. For instance, in one embodiment, nodes110,112and114may each send writes to replication target140and may include the current interval ID with each write. As noted above, replication target140may store each write in a node-specific log or may, alternatively store all writes from all nodes in a single log or data structure allowing node-specific access, according to various embodiments.

An interval coordinator, such as interval coordinator120, may signal the end of the current interval, as illustrated by block410. For example, interval coordinator120may determine the end of the current interval according to a length of time for the interval, while other methods for determining the length of an interval may be used in different embodiments. Interval coordinator120may send a message to each node informing the node that the current interval is ending. In response, each node may complete all in-progress writes for the ending interval and suspend completions for any new writes, as illustrated by block420. For example, each node may proceed to send writes for the new consistency interval to replication target140, but may not send a completion or acknowledgement to an application or process originally performing the write, as noted above. When sending new writes to replication target140after suspending write completions, each node may include the new interval ID with each write in order to allow replication target140to differentiate between writes for the previous (now ending) interval and the new interval. Additionally, each node may send an acknowledgement message to interval coordinator120, as indicated by block430, letting the coordinator know that the node received the end of interval message and has suspended write completions.

After receiving an acknowledgement from every node, interval coordinator120may, in some embodiments, send another message to each node signaling that write completions may be resumed, as indicated by block440. In response, the nodes may complete any previously uncompleted writes by sending acknowledgments or completion messages to applications or processes originally performing the writes, as indicated by block450. After all data for the previous (ending) interval has been delivered to replication target140, each node may send a consistency interval marker or consistency point message to replication target140, as indicated by block460, and described above. Once replication target140has received consistency points from every node, replication target140may inform the interval coordinator that interval processing is completed.

Additionally, replication target140may generate a consistency checkpoint or snapshot for the ended interval, or alternatively, may delay generating a checkpoint or snapshot for a time sufficient to ensure that any writes delayed, due to network congestion for example, may arrive, according to some embodiments. As discussed above, replication target140may delay generating a consistency checkpoint or snapshot for an additional number of consistency intervals, in one embodiment. However, source nodes may continue sending writes to the replication target and may include the new interval ID with each write, as illustrated by block470.

While the discussions above in reference toFIGS. 2-4described consistency interval marker based replication in reference to non-write-shared storage environments, and thus, did not discuss block conflict resolution, the following discussions regardingFIGS. 5-9will discuss consistency interval marker based replication in write-shared environment and thus will describe block conflict resolution in detail.

FIG. 5is a block diagram illustrating, according to one embodiment, a first phase of block conflict resolution, as described herein. For instance, node one110and node two112may each have sent writes for two blocks to replication target140during the current interval. Node110may have sent writes for blocks1and2, while node112may have sent writes for blocks2and3. Replication target140may store the received writes in node-specific write logs, such as node one write log550and node two write log560. Thus, as illustrated byFIG. 5, node one write log may include blocks1and2from node one110and node two write log560may include blocks2and3from node two112. As noted above, the exact manner and data structure in which replication target140maintains the writes received from nodes110and112may vary from embodiment to embodiment.

Additionally, in some embodiments, nodes one (110) and two (112) may periodically send interval coordinator120lists of modified blocks that indicate the blocks modified by each respective node. Thus, node110may send a list of modified blocks including blocks1and2as indicated by dirty block list500and node112may send a list of modified blocks including blocks2and3, as indicated by dirty block list510. In response to receiving the lists of modified blocks from nodes110and112, interval coordinator120may maintain node-specific lists of modified (or dirty) blocks. Thus, the dirty block list530from node one may include blocks1and2, while the dirty block list540from node two may include blocks2and3.

Additionally, interval coordinator120may maintain a preliminary block conflict list520and may update preliminary block conflict list520whenever it receives a list of modified blocks from a node. For example, interval coordinator may compare the node one dirty block list530and node two dirty block list540and determine that block2was written to be both node one and node two. Thus, interval coordinator120may generate or update preliminary block conflict list520to include block2, according to the embodiment illustrated byFIG. 5. As described above, interval coordinator120may send preliminary block conflict list520to each node after sending an interval end message and may determine a final block conflict list after receiving final modified block lists from every node, as will be described below regardingFIG. 6.

FIG. 6is a block diagram illustrating a second phase of block conflict resolution as described herein and according to one embodiment. After determining preliminary block conflict list520, as described above regardingFIG. 5, interval coordinator120may send preliminary block conflict list520to every node, such as nodes110and112. In response to receiving a preliminary block conflict list from interval coordinator120, nodes110and112may suspend writes or completions of writes, including in-progress writes. Thus, node110may suspend an in-progress write to block3, as indicated by in-progress block list600. Additionally, node112may suspend an in-progress write to block8, even though block8may not be a conflict block.

Since receiving an interval end message from interval coordinator120, nodes110and112may have completed additional writes for the ending interval. For example, node110may have completed in-progress writes to blocks4and5, and node112may have completed writes to blocks6and7. Additionally, node110may have started a write for block3, as indicated by in-progress block list600, and node112may have started a write for block8, as indicated by in-progress block list610, as noted above. Please note that in-progress block lists600and610are illustrated inFIG. 6for discussion and explanation purposes only. Nodes taking part in consistency interval maker based replication with block conflict resolution, as described herein, may not actually maintain such a list of in-progress writes, or may maintain such a list in a different form or format.

Nodes110and112may also send a final list of modified blocks to interval coordinator120, according to some embodiments. For instance, node110may send a final modified block list including blocks4and5and node112may send a final modified block list including blocks6and7. Thus, interval coordinator120may update its node-specific modified block lists, as indicated by node one dirty block list530and node two dirty block list540. In response to receiving final modified block lists from nodes, interval coordinator120may generate and distribute to the nodes a final block conflict list, such as final block conflict list620.

Additionally, as described above, interval coordinator120may include conflict-resolving instructions to each node when sending final block conflict list620. Alternatively, interval coordinator120may send such conflict-resolving instructions in separate, individual message to each node, according to certain embodiments.

Regardless of whether interval coordinator120sends conflict-resolving instructions along with final block conflict list620or separately, the nodes may, in one embodiment, send additional writes to replication target140to resolve the block conflicts, according to the conflict-resolving instruction from interval coordinator120. For example, interval coordinator120may request that node110complete the in-progress write of block3, thereby resolving the conflict of block3. Please note that since the in-progress write of block3from node110occurs after the completion of the write to block3from node112, interval coordinator120may determine that the data for block3from node110is the final (in terms of the current consistency interval) data for block3. Similarly, interval coordinator120may request that node112read the data for block2and forward it to replication target140. Please note that interval coordinator could also have requested that node110read and forward data for block2, however, in some embodiments, interval coordinator120may distribute conflict-resolving instructions across multiple nodes in order to limit the amount of time and network bandwidth used by each node during conflict resolution, and to take advantage of possible data caching on the individual nodes or data access hardware.

Interval coordinator120may send such conflict resolving instructions to nodes in various forms, according to different embodiments. For example, in one embodiment, interval coordinator120may simply include a list of blocks that a node is to read and send to replication target140.

When sending conflict resolving writes to replication target140, in response to receiving conflict-resolving instructions from interval coordinator120, a node may mark or flag the writes as conflict-resolving so that replication target140may know to overwrite any previously received data for the relevant blocks with the data from the conflict-resolving writes. For example, a particular tag or flag may be included with a conflict-resolving write in one embodiment. In other embodiments, however, replication target140may assume that any writes including a consistency interval's ID received after that interval has ended to be conflict-resolving writes. Alternatively, in yet other embodiments, interval coordinator120may send replication target140a message indicating which blocks will be overwritten by conflict-resolving writes and thus replication140may be able to determine which writes from nodes are conflict-resolving writes, such as to handle the case where an earlier (non-resolving) write is received later than a conflict resolving write for an interval (which can happen if nodes process and deliver data to the target with different delays).

FIG. 7is a block diagram illustrating the logical communication flow between a node, an interval coordinator, and a replication target while implementing consistency interval replication with block conflict resolution, according to one embodiment. Similarly toFIG. 3, described above,FIG. 7shows the communication between node110, interval coordinator120and replication target140for an interval transition including block conflict resolution, as described herein and according to some embodiments. Thus,FIG. 7(likeFIGS. 5 and 6) illustrates consistency interval marker based replication in an environment that includes write-shared data storage in which multiple nodes may write to the same data block, thus replication target140may receive multiple writes from different nodes to the same data block. As described above, node110may send writes to replication target140including the current interval ID with each write and replication target140may response with acknowledgement messages, as illustrated by arrows700and705.

Unlike consistency interval marker based replication without block conflict resolution, consistency interval marker based replication with block conflict resolution involves nodes, such as node110, periodically sending interval coordinator120lists of the blocks modified by the writes sent from the nodes, as indicated by arrow710. Thus, periodically throughout a consistency interval, node110may send a message to interval coordinator120including a list of those blocks being modified by the writes from node110. Node110may only include in such a list blocks that have been modified since the last time node110sent such a list to interval coordinator120. However, in some embodiments, nodes may not send lists of modified blocks periodically, but instead may send a complete list of modified blocks to interval coordinator120in response to a consistency interval end message from interval coordinator120. Interval coordinator120may also maintain node-specific lists of modified blocks for use in block conflict resolution, such as dirty block lists530and540, described above regardingFIGS. 5 and 6.

As described above, consistency interval120may send an interval end message to node110at the end of the current interval, as shown by arrow715. In response to the interval end message, node110may send interval coordinator120an updated list of modified blocks, as illustrated by arrow720. As noted above, node110may send a list of only those blocks modified since the last time node110sent such a list to interval coordinator120(during the current consistency interval). Interval coordinator120may analyze the lists of modified blocks from all nodes to identify block conflicts where two nodes sent writes for the same data block. Interval coordinator120may send a preliminary list of block conflicts to each node as indicated by arrow725. In some embodiments, this list may be preliminary because some nodes may not have completed all writes for the ending interval. In response to receiving a preliminary list of block conflicts, node110may suspend all writes to any conflict block but may, in some embodiments, send writes for non-conflict blocks in the new interval, as indicated by arrow730. While not illustrated inFIG. 7, replication target140may acknowledge writes for non-conflict blocks as described above regarding arrow705.

Additionally, after receiving a preliminary list of block conflicts from interval coordinator120, node110may send a final list of modified blocks to interval coordinator120, as indicated by arrow740. For example, node110may send a list of blocks modified since the last list of modified blocks was sent to interval coordinator120. In another embodiment, node110may respond to a preliminary list of block conflicts with a complete list of all blocks modified during the current interval. After receiving the final lists of modified blocks from all nodes, interval coordinator may, as described above, send a final list of block conflicts to each node, as indicated by arrow745. In some embodiments, interval coordinator120may send identical messages to all nodes with a list that includes all block conflicts.

In other embodiments, however, interval coordinator120may send individual messages to each node with the final list of block conflicts that also includes specific instructions for that node to perform for conflict resolution. For example, as described above, interval coordinator120may request node110to read the data for a specific block and forward that data to replication target140. When sending such conflict resolving writes to replication target130as indicated by arrow750, node110may, in some embodiments, include an indication that the write is a conflict-resolving write and that the data in the conflict-resolving write should overwrite any other writes to the same block (within the ending consistency interval), as described above.

Interval coordinator120may also request that node110complete an in-progress write for a conflict node and in response, node110may send the write to replication target140, in some embodiments including an indication that this write is a conflict-resolving write. In response to receiving conflict-resolving writes from node110, replication target140may use the data from the conflict-resolving writes when generating a consistency checkpoint or snapshot for the ending consistency interval. Additionally, replication target140may, in some embodiments, send an acknowledgment message to node110indicating that replication target140received the conflict-resolving writes, as described above regarding arrow705.

After completing all conflict-resolving instructions from interval coordinator120, whether included with the final list of conflict blocks or sent in individual messages, node110may, in some embodiments, send a consistency point or consistency interval marker message to replication target140, as indicated by arrow760. As described previously, once replication target140has received consistency point messages from all nodes, replication target140may send an interval transition message, as indicated by arrow765, to interval coordinator120reporting that all nodes have finished all conflict-resolving processing and have sent their respective consistency point messages. Thus, interval coordinator120may determine that all processing for the ending interval may be complete, according to one embodiment.

FIG. 8is a flowchart illustrating, according to one embodiment, a method for consistency interval marker based replication with block conflict resolution, as described herein. As illustrated by block800, at the end of a consistency interval, interval coordinator120may signal the end of the interval, as described above and the nodes may suspend write completions, as indicated by block810and discussed above.

As illustrated by block820, each node may send a final list of blocks modified during the consistency interval. For example, in one embodiment, each node may send a single, complete, list of all blocks modified since the start of the consistency interval. In another embodiment, each node may periodically send lists of modified blocks and may only send, as a final modified block list, a list of those blocks changed since the last modified block list was sent to interval coordinator120.

Interval coordinator120may also analyze the received list of modified blocks for each node to determine whether there are any blocks in conflict, as illustrated by block830, as discussed above. If there are blocks in conflict, interval coordinator120may send a message to all nodes including the final list of conflict blocks, as indicated by block835, and, in response, the nodes may resume write completions for blocks that are not in conflict, as indicated by block840. Additionally, interval coordinator120may resolve the block conflicts, as illustrated by block850and as described in detail below regardingFIG. 9. If there were no conflicts, as indicated by the negative output of block830, the interval coordinator may simply send a message acknowledging receipt of the lists of modified blocks from each node, as indicated by block860and in response, the nodes may resume any suspended writes or write completions, as illustrated by block870.

As described above, interval coordinator120may send messages to certain nodes requesting the forwarding of data for conflict blocks to replication target140and may also request the completion of suspended in-progress writes to resolve a block conflict, according to some embodiments. After resolving all block conflicts, or if there were no block conflicts, the interval coordinator may signal the start of a new interval, as indicated by block880. For example, the interval coordinator may send a message to all nodes including the new interval's interval ID, in some embodiments. In other embodiments, however, the nodes may have already received the new interval ID, and may already be sending writes including that interval ID, and thus the interval coordinator may send a message informing all nodes that all conflicts for the ending interval are resolved, and thus the nodes may begin or resume sending writes for all blocks, including the previous conflict blocks, as described above. Additionally, in some embodiments, the nodes may, in response to receiving a message regarding the completion of interval transition processing from interval coordinator120, perform any node-specific processing, such as cleaning up recovery information stored for the completed consistency interval, as discussed previously.

FIG. 9is a flowchart illustrating one embodiment of a method for block conflict resolution as described herein. After receiving a final list of modified blocks from each of the nodes, as illustrated by block900, interval coordinator120may analyze the list of modified blocks to determine any block conflicts, as illustrated by block910, and described above. For example, the interval coordinator may go through the list from each node comparing it to the lists from every other node to determine blocks written to by more than one node. After determining a list of blocks with conflicts, interval coordinator120may send the list of block conflicts to each node, as indicated by block920. Interval coordinator120may then proceed to resolve the block conflicts. For each block conflict the interval coordinator may determine whether there is a suspended in-progress write for the block in conflict, as illustrated by block940. If there is an in-progress write for a conflict block, interval coordinator120may request that the node holding the in-progress write complete the in-progress write, thus allowing replication target140to overwrite any earlier writes for the block.

If there is not an in-progress write for a conflict block, interval coordinator120may request that a node read the data for the conflict block from primary storage130and forward that data to replication target140, as illustrated by block950. As noted above, interval coordinator120may also include with a final block conflict list message conflict-resolving instructions, such as for a node to read data for certain blocks and forward them to replication target140. As discussed above, a node may include an indication that the data in a conflict-resolving write for a block should overwrite any earlier data for that block (within the current interval). Additionally, interval coordinator120may also send instructions for a node to complete an in-progress write for a conflict block. Thus, in some embodiments, replication target120may receive conflict-resolving writes for conflict blocks for the currently ending interval.

While there are still block conflicts to be resolved, interval coordinator120may move on and determine how to resolve the next block conflict, as illustrated by blocks970and930. As interval coordinator120and the nodes finish resolving block conflicts for each node, interval coordinator120may, in some embodiments, send a message including the new consistency interval ID to the node, and in response the node may send a consistency point message to replication target140. After all block conflicts have been resolved, as described above, replication target140may generate a consistency checkpoint or snapshot of the data for the consistency interval, as illustrated by block980. However, as noted above, replication target140may only generate a consistency checkpoint or snapshot for the interval after receiving a consistency point from all the nodes, in some embodiments.

FIG. 10illustrates a computing system capable of implementing consistency interval marker based replication and block conflict resolution as described herein and according to various embodiments. Computer system1000may be any of various types of devices, including, but not limited to, a personal computer system, desktop computer, laptop or notebook computer, mainframe computer system, handheld computer, workstation, network computer, a consumer device such as a mobile phone, pager, or any type of networkable peripheral device such as storage devices, switches, modems, routers, etc, or in general any type of networkable computing device. Computer system1000may include at least one processor1040. Processor1040may couple across interconnect1050to memory1010and I/O interfaces1030. I/O interfaces1030may be any of various types of interfaces configured to couple with and communicate with other devices, according to various embodiments. In one embodiment I/O interfaces1030may represent a network interface configured to couple with and communicate over network100illustrated inFIG. 1, described above.

Memory1010is representative of various types of possible memory media, also referred to as “computer accessible media.” Hard disk storage, floppy disk storage, removable disk storage, flash memory and random access memory (RAM) are examples of memory media. The terms “memory” and “memory medium” may include an installation medium, e.g., a CD-ROM or floppy disk, a computer system memory such as DRAM, SRAM, EDO RAM, SDRAM, DDR SDRAM, Rambus RAM, etc., or a non-volatile memory such as a magnetic media, e.g., a hard drive or optical storage. The memory medium may include other types of memory as well, or combinations thereof.

In some embodiments, memory1010may include program instructions1015configured to implement consistency interval marker based replication in a clustered and/or distributed environment, as described above. In certain embodiments, program instructions1015may be configured to implement an interval coordinator, such as interval coordinator120, or a shared-write coordinator, such as shared-write coordinator150, both described above. In other embodiments, program instructions1015may be configured to implement a replication target, such as replication target140, also described above. In yet other embodiments, program instructions1015may be configured to implement a source node, such as nodes110,112, and114, also described above.

Although the embodiments above have been described in detail, numerous variations and modifications will become apparent once the above disclosure is fully appreciated. It is intended that the following claims be interpreted to embrace all such variations and modifications.