Hybrid transaction/intent log for data replication

[0001] The present invention relates generally to the art of synchronising copies of data in real time between dispersed computer systems. The technique is applicable whether the computers are dispersed over large distances, replicating over short local networks, or even to a single computer utilising a RAID-1 subsystem.

[0002] In the field of reliable computing, one particular need is to keep a duplicate or backup copy (called a replica) of a particular data set in such a way that the replica is always an exact (or just slightly out of date) copy of the primary data set. In a synchronous replication environment, the replica is always exact; in an asynchronous one, the replica may be out of date with respect to the primary by at most a pre-determined amount.

[0003] FIG. 1 illustrates a replication set up having a primary 101, with its associated data set on permanent storage 102, which is connected to a network 103. Network 103 is routed onto the internet 104 which ultimately connects to a different network 105. The replica 106 also having a storage device 107 for receiving a replica of the data set and being connected to network 105. Thus, a write to the data set on the primary storage 102 may be encapsulated into a network datagram and sent over networks 103, 104 and 105 where it is received at the replica, unencapsulated and sent down to the replica data set on storage 107. This operation is functionally equivalent to direct replication 108 from the primary data set on 102 to the secondary data set on 107.

[0004] When a communications failure occurs between the primary and its replica, the primary continues processing the data set but the replica is frozen until it can re-establish communications with the primary. When communications are re-established, the replica must be brought up to date again (preferably without too much impact to the primary). Since the data set being processed may be much greater than the data actually changed while the primary and replica lost contact, it is advantageous to transmit to the replica only the said changes necessary to bring it up to date with respect to the primary. There are two methods usually used for keeping track of the changes between a primary and its replica.

[0005] i. Transaction Logging

[0006] Every write made to the primary data set is recorded separately in an ordered log called the transaction log whose contents alone are sufficient to recreate the original write. The same write is also sent (if possible) to the replica. When the write completes on the replica, a signal is sent back to the primary and the primary then removes the log entry for the write from its transaction log (note, this removal of the log entry doesn't have to be done instantaneously). When contact with the replica is lost, the transaction log fills up because no completion signals are received. As soon as contact is restored, the transaction log can be replayed, in order, to the secondary (from oldest to youngest write); transactions may still be accepted while the replay is going on. The great advantage of using a transaction log is that while the log replay is in process, because it is sending every write in the correct order, the replica is always an exact (but out of date) copy of the primary. Thus, even if there is a failure during the log replay, the replica would still be usable as an (out of date) copy of the primary. The great disadvantage of a transaction log is that it must be a finite size. Further, since it records every transaction, three writes of a kilobyte each would occupy over three kilobytes in the transaction log since they must all be recorded in the correct order. Thus, a transaction log grows without bound when the primary is processing data but out of contact with the secondary. When a transaction log runs out of space, a condition called log overflow, the primary has no choice but to send its entire data set to the replica when contact is re-established. This may take a considerable amount of time and further, the replica is a corrupt copy of the primary until the resynchronisation is completed.

[0007] Obviously, the operator of the replication system must set the transaction log to a maximum finite size, so sizing the transaction log to avoid log overflow in most situations becomes an issue.

[0008] ii. Intent Logging

[0009] The concept of an intent log is predicated on the assumption that the dataset can be segmented into chunks (called clusters), which the replication system must also use as its basic unit of transmission. Often, the clusters correspond to indivisible quantities in the data set such as the file system block size, or the underlying disc sector size. When a write occurs on the primary, the number of clusters it covers is ascertained and these clusters are marked as dirty in a bitmap of clusters covering the entire data set (the intent log). When the write completion signal is sent back from the replica, the dirty bit is cleared from the intent log (this bit clearing doesn't have to be done instantaneously). If contact is lost with the replica, the intent log continues to keep a record of all the clusters dirtied. When contact is restored the log is replayed sending only the dirty clusters to the replica to update it. However, since the intent log contains no concept of ordering, the replica is corrupt until the replay is complete. The great advantage an intent log has is that it is a finite and known size and can never overflow. This property makes it particularly effective for geographically dispersed clusters, where the communications failures can be prolonged because of the distances and the sheer numbers of intermediate networks that must be traversed to copy data between the sites.

[0010] Note also that for a large outage an intent log replay is far more efficient than a transaction log since an intent log only replays a dirty cluster once but a transaction log may have to change the same cluster of data many times because it is mirroring exactly how the data changed in the primary volume.

[0011] The object of the present invention is to produce a replication log that can replay transactions in order like a transaction log but that also never overflows, like an intent log. The present invention achieves this object by using a log which behaves as a transaction log until the log overflow condition occurs, whereupon it converts this transaction log to an intent log, replaying the complete transaction log through the intent log so that all of the correct clusters are marked dirty. The log will operate as an intent log from that point until a log replay has been completed, whereupon, the empty log will begin as a transaction log again.

[0012] The utility of the present invention lies in the fact that the user of the present invention may tune the log size to the anticipated communication outage patterns in their replication enterprise. Thus, for most small communication outages the log is big enough to remain as a transaction log for the entire outage and thus retain all the benefits of such a log. For a prolonged communications outage, the log will switch to an intent log and thus the log overflow problem is avoided (although the replica will now be corrupt on log replay).

[0013] Those skilled in the art will notice that most quality replication solutions also guard against corruption problems that may occur in the replication system because of a failure of the primary (so that replication may begin seamlessly when the primary failure is corrected). Therefore, it is a further object of the present invention to preserve the utility of the log at all times during its conversion from transaction to intent. This object is achieved by identifying the amount of space taken up by the intent log bitmap and adding to this the amount of space taken up by compressed transactions. All of the transactions within this space are compressed: the data contained in them is eliminated and instead the numeric identifiers of the clusters they cover in the primary dataset is substituted (this data is much less than the original transaction data). At this point, the transactions are labelled with their order (for transaction logs that use implicit ordering within the log for this). This process opens up spaces within the log where the eliminated data would have been. Compressed transactions that lie within the space that will become the intent log bitmap are now copied to the excess space identified to contain them. Finally, the intent log bitmap is cleared and all transactions (starting with the compressed ones) are replayed to set the dirty clusters in the intent log. Each step in this process is a logical checkpoint: if the process is halted, it can be restarted from the beginning of the step with no adverse consequences. Once conversion to an intent log has begun, it must be completed before the dirty clusters can be sent to the replica as part of log replay.

[0014] Those skilled in the art will notice that if the conversion is done only after the transaction log becomes full, all writing to the data set must be suspended while the conversion to an intent log is in progress to preserve the integrity of the log. However, if the conversion were begun speculatively while some space remained in the transaction log, writing to the data set (and logging to the end of the transaction log) could continue as long as both the transaction log has space and the conversion routine is aware of the added transactions and processes them correctly. Thus, by correct choice of this conversion point, the processing of the data set may continue uninterrupted.

[0015] Those skilled in the art will appreciate that the compression method will still function even if the transaction header and body for an individual transaction entry are not contiguous in the log. In this case the intent log region would be set up so as to span mainly the bodies of the transactions.

[0022] The preferred embodiment is presented in terms of a network replicating system because that is where the present invention has the greatest utility. However, those skilled in the art will realise that nothing prevents the principles disclosed from being applied to a single computer system replicating data between two locally connected volumes.

[0023] A preferred embodiment for the invention consists of a RAID-1 device (in Linux this would be the md driver) and a Network Block Device (in linux this is nbd) whose job is to appear to the primary as a local device, but which in fact hands off all reads and writes to a block device physically located on the replica. Such a set up is illustrated in FIG. 2. User application 201 sends a write of data block number 2320 (illustrated as 209) down to a device connected to RAID-1 mirror 203. Mirror 203 logs the write in log 202 and after it receives a write completion signal from log 202, sends it down to local storage 204 and the nbd network transmitter 205. Transmitter 205 packages the data up for the network and sends it over one or more network paths 210 to receiver 206 which unpackages the data, sends it to daemon 207 which finally puts the data on replica storage 208. The write complete signal from committing the data to storage 208 is transmitted back to daemon 207 and then receiver 206 which transmits the signal back over the network to 205. 205 then sends a write completion signal to mirror 203. On receipt of completion signals from both local copy 204 and the remote copy 208, mirror 203 erases the log entry for the particular data block and sends a write completion signal to the user application 201.

[0024] When log 202 is functioning as an intent log, it simply writes a dirty bit corresponding to data block 209; when it is functioning as a transaction log, it records sequentially an entire copy of the data.

[0025] FIG. 3 illustrates the sequence of events for an asynchronous replication system. User Process 300 issues a write 301 to the replication system. The write 301 is first directed 302 to Log 313 (where it is recorded either as a dirty bit for an intent log or complete data for a transaction log). Write completion of the log 303 triggers the system 304 to issue the same data as both a write 306 to primary volume 316 and a write 305 to replica volume 315. A write completion signal 307 from the primary volume 316 causes a write completion signal 308 to be returned to the user process. The foregoing actually describes the case for an intent log; for a transaction log, the alternate write completion signal 314 is returned to the user immediately after the write completion 303 from the log 313 is returned. At this point, the user process believes the write transaction to be completed. The following is unnecessary to the user process, but may be done if the primary and replica are in good network contact: once write completion signals 309 and 310 from the primary 316 and replica 315 volumes respectively are processed, they trigger 311 the log entry to be erased 312. If this process cannot be completed because the primary and replica are out of contact, the log entry remains until a log replay occurs.

[0026] The present invention requires that the log 313 initially be a transaction log, but should log write 302 fill the log up to a pre-specified level (which may be completely full, or a fraction thereof), the conversion of the log to an intent log shall begin. A transaction entry in the log is illustrated in FIG. 4. The transaction entry 401 consists of a header 403 which is quite small (usually under 16 bytes) and a body 402 containing the data. Since data is usually written by the operating system in indivisible units of blocks which are at least 512 bytes long, many transaction headers 403 would fit inside a single transaction body 402. The header itself consists of a sequence number 404 identifying the correct ordering for the transaction, a set of flags 405 identifying the state of the transaction and data location information 406 identifying where data 402 should be placed in the replica volume to complete the transaction.

[0027] In FIG. 5, the actual transaction log 501 is divided into regions prior to conversion to an intent log. Region 502 bounded by 506 represents the actual space that would be taken up by the intent log. The size of this region in bytes is calculated by taking the number of clusters on the device and dividing it by 8 (one dirty bit per cluster). It is usually rounded up to the nearest device block to avoid synchronization complexities caused by sharing indivisible regions on the said device. Boundary 506 may occur inside a transaction body, but may not occur inside a transaction header. The next region 503, called the “conversion region” is the amount of space set aside for compressed transactions inside the intent log. First, the compressed transaction space requirement is calculated by counting the number of transactions inside region 502, multiplying by the transaction header size. Then, boundary 507 is set by counting up the space taken by the number of transaction bodies (excluding the headers) from region 502. When this equals the compressed transaction space requirement, the barrier 507 is assigned to the next block boundary that doesn't reside inside a transaction header. Boundary 508 marks the point at which conversion to an intent log will begin this quota of unfilled space in the transaction log is exceeded (note that a transaction log may not necessarily be contiguous, so the empty region 505 may be spread across the log rather than located neatly at the end. This only affects how the conversion point is found, not the algorithm for converting to an intent log). Field 509 right at the end of the log is a flag field identifying the log either as type TRANSACTION, type INTENT or type CONVERTING.

[0028] The conversion process then proceeds according to the following steps:

• • [0029] 1. Set the log type to CONVERTING.
  • [0030] 2. All transactions in the conversion region 503 are “compressed”. The process of compressing the transactions is simply to add the flag COMPRESSED to the transaction header. The presence of this flag indicates to any routine using the transaction log that it may no longer rely on the data 402 in the transaction entry, but must instead use the data location 406 of the transaction header to read the data from the primary volume instead.
  • [0031] 3. All transactions in the intent log region 502 are moved to the available space previously occupied by the data pieces of the transactions in the conversion region 503 in the following fashion
    • [0032] (a) Copy the next individual transaction header to the first available piece of space in the empty data areas of the conversion region 503, marking the transaction as COMPRESSED in the new header.
    • [0033] (b) Once the copy is complete, erase the header from the intent log by marking its flags as INVALID.
    • [0034] (c) Repeat until the intent log region 502 is empty.
  • [0035] 4. Completely clear the intent log region 502.
  • [0036] 5. Begin to move up the transaction log from boundary 506 to the end of the log reading the log headers and using data location information 406 to set the dirty bits in the intent log 502. Note: this sweep does not have to be done in transaction sequence 404 order.
  • [0037] 6. Once the sweep is complete, and any transactions that may have been placed into the empty region are converted, the log type is switched to INTENT and all writes now merely set the dirty bits in the appropriate region of the intent log.
  • [0038] 7. All of the transaction log excluding the intent log region 502 (and the flag 509) are cleaned out to contain no transactions in preparation for beginning life again as a transaction log when the intent log replay to the replica has completed.

[0039] Should the primary crash at any point while the log is of type TRANSACTION or INTENT, only actions that usually apply to those log types need be taken. However, if the crash occurs while the log is of type CONVERTING, the conversion must be completed. Since all of the actions in the list above are idempotent, the conversion may simply be restarted from step 2 in the list.

[0040] If the conversion to intent log has occurred (or conversion has begun) when the replica comes back into contact with the secondary, replay of the log must be done as an intent log. During the replay of the intent log, a moving point, called the synchronisation point is maintained. This point starts at the beginning of the intent log 502 and moves sequentially to its end. When it encounters clusters marked as dirty, the contents of these clusters are copied from the primary data set and sent to the secondary. This process is illustrated in FIG. 6 where the complete log is 601 (shown as 501 in FIG. 5). The synchronisation point is 605, with the intent log ending at 604 (which would be 506 in FIG. 5). The rest of the log is region 606 (in the previous FIG. 5, this is regions 503, 504, 505 and type flag 509). The region 602 before the synchronisation point 605 represents the region that has been synchronised with the replica. Any write to region 602 would be recorded in the cleaned transaction log (beginning from point 604) as an ordinary transaction and sent on to the replica. Any write to region 603 after the synchronisation point 605 would not be sent to the replica since it will be sent as soon as the synchronisation point sweeps over it; however, it would be recorded as a dirty cluster in the remaining intent log (if the cluster is not already dirty). Any completion signals from the replica for transactions in the transaction log will be handled in the usual fashion. Once the synchronisation point 605 has reached the end of the transaction log (604) then the replay is complete, the intent log regions 602 and 603 may be emptied and turned over for use by the transaction log. The conversion back to transaction log has now completed.