The present invention relates to a system and a method for replicating data, in particular to data stored on non-volatile storage media. Every storage media is subjected to eventual temporal or permanent failure - With removable media there is a risk of loss or

misplacement, typically stationary media such as hard disks are subject to wear and tear over time. Typically users try to mitigate the risk of losing data by periodically copying the data from one storage medium to another. Ideally both media are not subject to the same risk, i.e. they are kept at separate places to ensure that they are not impacted by the same event such as fire, flooding etc. Computer systems and software for computer systems aid the user in keeping backups of his data, e.g. by means of an archiving or backup software that periodically either reminds the user to backup his data on a separate medium or performs such a backup automatically based on preset parameters. In case of a failure of the primary media the user either replaces the primary medium with one of the backup media, i.e. the selected backup medium becomes the new primary medium. As an alternative, a new empty primary media is supplied and the data is copied or restored from one of the backup media.

In case not only data integrity but also data availability matters, there are techniques known such as RAID systems, that continually mirror data from one storage medium to at least one other. E.g. RAID-1 defines implements such a mirror process which ensures that upon failure of the primary medium the data can be retrieved from a synchronized copy on a second medium without interruption of the service.

For professional services, high availability clusters are known utilizing for example

Distributed Replicated Block Devices (DRBD) for a distributed storage system. DRBD essentially defines RAID-1 type capabilities over a network, thus provides for spatial redundant storage. In more detail, DRBD provides for logical block devices acting as a proxy for the physical local block devices in each storage node. Data written to the logical block device on the primary node is transferred to a physical block device in the primary node and subsequently copied to the secondary node. In case of a storage media failure at the primary node, the secondary node is promoted to become the new primary node. However, this transition results in inconsistencies between the data stored in the primary and secondary not and thus requires a subsequent verification of the integrity of the file system stacked on top of DRBD or the deployment of a journaling file system such as EXT4.

Generally, systems deploying DRBD require a network connection between each storage systems hat exhibits high and constant data throughput typically only found in managed local area networks. DRDB operates synchronously and fails to perform well in wide area networks with varying data throughput. In particular if the network bandwidth temporarily drops below the bandwidth required for a synchronous replication, an application running on to of DRBD will see increasingly higher Input/Output latencies and/or hangs or stalls.

It is therefore the object of the present invention to provide a system and a method for replicating data that is tolerant to unreliable network links and that provides anytime data consistency.

This object is solved by the subject matter of the independent claims. Preferred

embodiments are defined by the dependent claims.

The present invention is related to a system for replicating data comprising a first computing device having a first storage means, a second storage means and volatile memory. The inventive system further comprises a second computing device having a third and a forth storage means, said third storage means being communicatively coupled to the second storage means. In a preferred embodiment of the invention the first computing device has means for receiving write requests, each request containing payload data, means for writing said payload data of each write request to the volatile memory and appending said each payload data to the second storage means, means for acknowledging said write request prior to writing the payload data to the second storage means.

Moreover, the second computing device has means for detecting new data in the third storage means and means for applying said new data to the forth storage means.

According to an embodiment, appending each payload data to the second storage means includes appending each payload data to the second storage means in a different order than it was received. According to an embodiment, appending each payload data to the second storage means includes appending each payload data to the second storage means in ascending block number order.

Brief description of the figures:

Figure 1 illustrates a system for replicating data according to prior art. Prior Art systems comprise a primary host (100) having multiple storage means (101 , 1 02) such as block level devices that are exposed as a device file (103) that is exposed for read and write access by applications. In order to provide data redundancy, a secondary host (1 10) also having multiple storage means (1 1 1 , 1 1 2) mapped to a device file (1 1 3) is synchronized (1 20) with the device file (1 03) of the primary host.

Figure 2 illustrates a block diagram of an exemplary embodiment of a system for replicating data according to the present invention.

Figure 3 illustrates a flow chart of an exemplary embodiment for processing data on the primary computing device.

Figures 4 and 5 illustrate flow charts of an exemplary embodiment for processing data on the secondary computing device.

Detailed description of the invention:

According to an embodiment of the invention a first computing device (200) and a second computing device (210) are communicatively coupled, each computing device having local physical non-volatile storage (201 , 21 2) that is suited for storing block level data. The physical non-volatile storage, such a single hard disk or a bunch of hard disk logically linked with each other is exposed to the outside using a pseudo device. The pseudo device refers to an arbitrary device node, such as /dev/mydata as shown in Figure 2.

The first computing device receives one or more write requests (214, 301 ), each write request may contain meta data such as an op code, a timestamp, a length indication and payload data - said may for example correspond to a full or a portion of a data block to be stored on a block level device.

The inventive concept includes recording all changes made to a block device (201 ) in a transaction log file (202). Any write request is treated like a transaction which changes the contents of the block device (201 ). This is a similar concept to some database systems known in the art, but there exists no separate "commit" operation: any write request is acting like a commit.

As shown in Fig.3 the first computing device upon receiving (301 ) one or more write requests buffers (302) the write requests in a volatile memory such as a RAM acting as a temporary memory buffer (203). This memory buffers serves multiples purposes: It keeps track of the order of write operations. Additionally, it keeps track of the positions in the underlying block level device. In particular, it detects when the same block is overwritten multiple times. Finally, the memory buffers servers the purpose of serving concurrent reads during pending write operations.

After the one ore more write request have been buffered, the first computing device starts appending (303) the data to a sequentially organized log file accessible from or attached to the first computing device. This log entry contains vital information such as the logical block number in the underlying block level device, the length of the data, a timestamp, some header magic in order to detect corruption, the log entry number, of course the data itself and optional information like a checksum or compression information. Preferably, the timestamp takes into account the asynchronous communication in a distributed system as described herein. Therefore it is preferred to use a Lamport clock model, in particular the physical Lamport clock model which tries to remain as near as possible to the system clock (i.e. in a Linux-based environment counting in units of seconds since the Unix epoch, with nanosecond resolution. The physical Lamport clock works rather simple: any message send through the network is augmented with a Lamport timestamp telling when the message was sent according to the local Lamport clock of the sender. Whenever that message is received by some receiver, it checks whether the time ordering relation would be violated: whenever the Lamport timestamp in the message would claim that the sender had sent it after it arrived at the receiver (according to drifts in their respective local clocks), something must be wrong. In this case the Lamport clock of the receiver is advanced shortly after the sender Lamport timestamp, such that the time ordering relation is no longer violated. As a consequence, any local Lamport clock may precede the corresponding local system clock. In order to avoid accumulation of deltas between the Lamport and the system clock, the Lamport clock will run slower after that, possibly until it reaches the system clock again, if no other message arrives which sets it forward again. After having reached the system clock, the Lamport clock will continue with "normal" speed. After the data was successfully appended to the log file, the first computing device promptly signals (307) completion of the received write request(s) to the applications that had issued the requests and starts writing (305) the data to the local storage (201 ). Even if the system is powered-off at this time, the information is not lost as it is present in the log file and can be reconstructed from there. Notice that the order of log records present in the transaction log defines a total order among the write requests, which is compatible to the partial order of write requests issued on the block level device (201 ).

Once this write operation has successfully completed (306), the buffer space used in the volatile memory is freed. According to an embodiment of the invention, the first computing device may append the data of the write requests to the log file (202) in different order than it was originally received. In particular, it may order the request in ascending or descending order with respect to the block numbers obtained from the metadata or payload data in each write request. This will reduce the average seek distance of magnetic disks in general. Also, if a write request refers to a block number that has been received previously but not yet completed appending to the log file, the first computing device may process only the last write request for a particular block number and disregard the previous one, for example by freeing the buffer for said previous write request. In case the primary host crashes during writeback, it sufficies to replay the log entries from some point in the past until the end of the transaction log file. It does not harm if some log entries are replayed twice or even more often: since the replay is in the original total order, any temporary inconsistency is healed by replaying the log file.

According to an embodiment illustrated by Fig. 4 the second computing device detects new data to be written, fetches (401 ) the delta of the remote log file on the first computing device and appends (402) this data to a local copy of the log file accessible by the second computing device. It should be noted that the step of detecting new data can be performed by several variants:

According to an aspect of the invention, the second computing devices open a connection oriented network connection (such as a TCP connection) to the first computing device over which either the second computing device pulls for new data from the first computing device or the first computing devices pushes new data to the second computing device through this connection. According to a different aspect of the invention the two log files (202, 21 1 ) may be provided by a shared file system, allowing both the first and the second computing device to access the same file - in this case, appropriate file pointers must be used to determine the respective read/write positions within the file. According to yet a different aspect of the invention, the two log files may be synced by an external syncing tool, such as rsync available in the Linux-based computing operating systems.

According to an embodiment illustrated by Fig. 5 the second computing devices detects new data to be written, fetches (501 ) the delta of the local copy of the log file, starts write back (502) to a local non volatile storage.

It should be noted, that each process defined by the process steps in each of Figure 3, 4 and 5 may be performed in parallel, for example the first computing device may continue writing the payload of new write requests to the local log file while the second computing device is still busy accessing log file information for the previous requests.

According to an embodiment there may be more than one secondary computing devices, each having local storage and the ability to perform the steps previously disclosed for the second computing device.

The previous disclosure assumes normal operating conditions, in particular at least a working network connection between the first and second computing device and sufficient memory for storing all necessary data. The inventive concept shall, however, also cover the following particular cases:

If there is no more space left for writing write requests to the log file (step 303 fails) the first computing devices attempts to free memory by rotating the log file, i.e. moving the log file to a storage with sufficient free space. If this attempt is unsuccessful or provides only temporary relief, the first computing device switches to a "by-pass mode" in which the first computing device refrains from writing to log files and starts writing data directly to the local storage.

If the transfer of the log file from the first computing device to the second computing device results in an incomplete log file at the second computing device, i.e. caused by a faulty network connection, the secondary computing device will attempt a fast full sync based on the last known to be good data in the local log file.

In case of a so-called split-brain condition, i.e. when the checksums of the log files do not match because of a faulty operation at the first computing device, the system requires manual intervention by setting the appropriate computing device to become the new primary computing device, followed by a full sync of the newly appointed secondary computing devices. Finally it should be noted that the previous disclosed method steps and features of the computing devices are optimized for the use in an wide-area network environment, meaning that the second computing device is placed at least 50 km apart from the first computing device.