Method and system for synchronizing storage system data

A method and system are provided for comparing data stored in a first storage system with corresponding data stored in a second storage system. In one implementation, the first system generates a random value associated with a respective data block P, and transmits to the second system an identifier associated with the data block P, and the random value. The second system generates a first digest representing a data block B, uses the first digest to encode the random value, producing a first encoded value, and transmits the first encoded value to the first system. The first system generates a second digest representing the data block P, uses the second digest to encode the random value, producing a second encoded value, and compares the first and second encoded values. If the two encoded values are equal, the data block B is a duplicate of the data block P. If the two encoded values are not the same, the data blocks are different. Additionally, a method is provided for synchronizing data stored on a second system to data stored on a first system. In one implementation, a data block P stored on a first system is compared to a data block B stored on a second system, as described above. If the two data blocks are different, the first system transmits a copy of the data block P, and the second system stores the copied data block P.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates generally to a system and method for storing data, and more particularly, to a method and system for comparing data stored on a first storage system to corresponding data stored on a second storage system.

2. Description of the Related Art

In many computing environments, large amounts of data are written to and retrieved from storage devices connected to one or more computers. As more data is stored on and accessed from storage devices, it becomes increasingly difficult to reproduce data if the storage devices fail. One way of protecting data is by backing up the data to backup media (e.g., tapes or disks). The backup media may then be stored in a safe location.

Other techniques for backing up data require comparing a block of data stored on a backup storage device to a corresponding data block on a primary storage device. If, for example, asynchronous mirroring is used to generate a backup copy of data—e.g., a cache is used to temporarily store data written to the primary device before writing to the backup, or mirroring, device—an interruption in the communication between the cache and the mirroring device can cause data to be lost and the backup copy to become corrupted. Generally, in such case, it is necessary to synchronize the mirroring device with the primary device, i.e., ensure that each sector of data on the backup device is identical to the corresponding sector on the primary device, before storing additional data.

One method for reconciling data on the backup storage device with the data stored on the primary storage device is to compare each block of data on the backup device with the corresponding block of data on the primary device. This requires either transferring each data block from the backup device to the primary device or transferring each data block from the primary device to the backup device. In some cases this may be an adequate solution. However, this approach typically requires a large bandwidth over the communications link between the two devices. This method can also be unacceptably slow. If the backup device is located at a remote location, these problems may be exacerbated. If a large amount of data is involved, it is often necessary to utilize a high-speed communication link between the primary device and the remote site where the backup device is located. Because high speed communication links are typically expensive, this solution is often undesirable.

This approach additionally poses security risks. Whenever a block of data is transmitted over the communication link, a third party may have an opportunity to intercept the data. The third party may intercept the data for espionage purposes, sabotage purposes, etc.

Techniques have been developed to reduce both the bandwidth requirements and the time needed to synchronize data between primary and backup storage devices. One approach is to identify and flag blocks of data on the backup device that are inconsistent with the corresponding data blocks on the primary device, and copy from the primary device to the backup device only the flagged data blocks. In accordance with one such technique, the backup device uses a known function to generate, for a respective data block, a first digest that represents the contents of the data block, and transmits the first digest to the primary device. The primary device retrieves a corresponding block of data and uses the same function to generate a second digest. The primary device then compares the first digest to the second digest. If the digests match, then the data blocks stored in the corresponding storage locations are assumed to be duplicates of one another. If the digests are not the same, then the data blocks stored in the corresponding storage locations are different. If the data blocks are different, the data block from the primary device is transmitted over the communication link to the backup device.

To be practical, a digest should be substantially smaller in size than the data block. Ideally, each digest is uniquely associated with the respective data block from which it is derived. Any one of a wide variety of functions can be used to generate a digest. Cryptographically strong hash functions are often used for this purpose. Another well-known function is the cyclic redundancy check (CRC). A digest-generating function is referred to herein as a D-G function.

A D-G function which generates a unique digest for each data block is said to be “collision-free.” In practice, it is sometimes acceptable to implement a D-G function that is substantially, but less than 100%, collision free.

Although this technique significantly reduces the amount of data that must be transmitted in order to synchronize two storage volumes, it does not entirely resolve the security problem. If the D-G function employed in the process is reversible, a third party may intercept the digest and derive the data block from the digest. Even if the D-G function is irreversible, a party familiar with the synchronization operation may intercept the digest, alter data in one or more of the storage systems, and in a subsequent synchronization operation retransmit the intercepted digest at the appropriate moment, thereby concealing the altered data.

SUMMARY OF THE INVENTION

Accordingly, there is a need for comparing data stored in a first storage system with corresponding data stored in a second storage system without transferring the data from one storage system to the other. There is additionally a need for comparing data stored in a first storage system with corresponding data stored in a second storage system without transmitting the actual data across the communication link between the two systems.

The present method and system provide for comparing data stored in a first storage system with corresponding data stored in a second storage system. In accordance with one implementation of the invention, the first storage system retrieves a data block P, and generates a random value associated with the data block P. The first system transmits to the second system an identifier associated with the data block P, and the random value. The second system retrieves a data block B that corresponds to the data block P (based upon the associated identifier), and generates a first digest that represents the data block B. The second system then uses the first digest to encode the random value, producing a first encoded value. The second system then transmits the first encoded value to the first system. The first system, in a similar manner, generates a second digest that represents the data block P, and uses the second digest to encode the random value to produce a second encoded value. The first system then compares the first encoded value to the second encoded value. If the first and second encoded values are equivalent, the data block B is a duplicate of the data block P. If the first encoded value is not the same as the second encoded value, the data block B is different from the data block P.

There is a further need for synchronizing data stored on a first storage system with data stored on a second storage system while minimizing the quantity of data transferred from one storage system to the other.

The present method and system provide for synchronizing data stored on a second storage system to data stored on a first storage system. In accordance with one implementation of the invention, the steps outlined above are carried out to compare a data block P stored on a first storage system with a data block B stored on a second storage system. If the data block B is different from the data block P, the first system transmits a copy of the data block P, and the second system stores the copy of the data block P received from the first system.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 1illustrates a system for backing up data in accordance with one aspect of the invention. Primary storage system130and backup storage system140are connected to network120. Network120may be implemented as one or more of a number of different types of networks, such as, for example, an intranet, a local area network (LAN), a wide area network (WAN), an internet, Fibre Channel-based storage area network (SAN) or Ethernet. Alternatively, network120may be implemented as a combination of different types of networks. Any number of computers (three of which,110,111and112are shown inFIG. 1) may be connected to primary system130and backup system140over network120.

Primary storage system130may be implemented by any storage mechanism that stores data and is capable of being backed up in accordance with the present invention. In the implementation shown inFIG. 1, primary storage system130comprises controller220, memory230, interface210and storage devices240-1and240-2. Controller220orchestrates the operations of primary storage system130, including processing input/output (I/O) requests from network120, and sending I/O commands to storage devices240. In one implementation, controller220is implemented by a software application. In an alternative implementation, controller220is implemented by a combination of software and digital or analog circuitry.

Communications between controller220and network120are conducted in accordance with IP or Fibre Channel protocols. Accordingly, controller220receives from network120data processing requests formatted according to IP or Fibre Channel protocols.

Memory230is used by controller220to manage the flow of data to and from, and the location of data on, storage devices240. For example, controller220may store various tables indicating the locations and types of various items of data stored in storage devices240.

Interface210provides a communication gateway through which data may be transmitted between primary storage system130and network120. Interface210may be implemented using a number of different mechanisms, such as one or more SCSI cards, enterprise systems connection cards, fiber channel interfaces, modems, network interfaces, or a network hub.

Storage devices240may be implemented by any type of storage device that allows block-level storage access. In one implementation, storage devices240are disk drives. A disk drive typically includes one or more disks having a medium upon which information may be written. Each disk includes a number of physical tracks, each of which, in turn, is divided into one or more physical blocks. Accordingly, in this implementation, an address identifying the location of a data block on a disk drive may specify a disk, a physical track and a physical block. Storage devices240are connected to controller220, in accordance with this implementation, by Fibre Channel interfaces, SCSI connections, or a combination thereof.

Communications between controller220and storage devices240are conducted in accordance with SCSI protocols. Accordingly, controller220transmits data processing commands to, and receives data from, storage devices240, in accordance with SCSI protocols.

One implementation by which primary system130allocates disk space for storing data is described below as an example. It should be noted, however, that this implementation is for illustrative purposes only and that other techniques for allocating disk space may be used.

Primary system130may dynamically allocate disk space according to a technique that assigns disk space to a virtual disk drive as needed. The dynamic allocation technique functions on a drive level. In such instances, disk drives that are managed by primary system130are defined as virtual drives. The virtual drive system allows an algorithm to manage a “virtual” disk drive having assigned to it an amount of virtual storage that is larger than the amount of physical storage actually available on a single disk drive. Accordingly, large disk drives can virtually exist on a system without requiring an initial investment of an entire storage subsystem. Additional storage may then be added as it is required without committing these resources prematurely. Alternatively, a virtual disk drive may have assigned to it an amount of virtual storage that is smaller than the amount of available physical storage.

According to this implementation, when primary system130initially defines a virtual storage device, or when additional storage is assigned to the virtual storage device, the disk space on the storage devices is divided into segments. Each segment has associated with it segment descriptors, which are stored in a free list table in memory. Generally, a segment descriptor contains information defining the segment it represents; for example, the segment descriptor may define a home storage device location, physical starting sector of the segment, sector count within the segment, and segment number.FIG. 2Aillustrates schematically the contents of a segment descriptor32. Fields32-1through32-5contain data indicating, respectively, on which storage device the segment is located, the segment's starting physical address, the segment's size, a segment identifier, and other information which may be useful for identifying and processing the segment.

Referring toFIG. 2B, as segments are needed to store data, the next available segment descriptor, e.g., segment descriptor32, is identified from the free segment list50, the data is stored in the segment, and the segment descriptor32is assigned to a new table called a segment map66. The segment map66maintains information representing how each segment defines the virtual storage device. More specifically, the segment map provides the logical sector to physical sector mapping of a virtual storage device. After the free segment descriptor32is moved or stored in the appropriate area of the segment map66, which in this example is slot2(70), the descriptor is no longer a free segment but is now an allocated segment. A detailed description of this method for dynamically allocating disk space can be found in U.S. patent application Ser. No. 10/052,208, entitled “Dynamic Allocation of Computer Memory,” filed Jan. 17, 2002, which is incorporated herein by reference in its entirety.

Backup storage system140may be implemented by any system capable of storing data generated for the purpose of backing up data stored on primary storage system130. In the implementation shown inFIG. 1, backup storage system140is implemented by a system similar to that of primary system130. Accordingly, backup system140comprises controller265, interface260, memory270, and storage devices280-1and280-2. However, in other implementations, backup storage system140is configured in a different manner than primary storage system130.

In one implementation, controller265of backup system140and controller220of primary system130both utilize the dynamic disk space allocation technique described above. Accordingly, when a respective block of data is stored on primary system130, controller220of primary system130generates a segment descriptor containing an identifier for the data block. A copy of the respective data block is transmitted to backup system140for purposes of backing up the data, and controller265of backup system140separately generates a segment descriptor for the copied data block. In accordance with this implementation, although the physical location of the respective data block on primary system130may be different from the physical location of the copied data block on backup system140, primary system130and backup system140use the same segment identifier information for the two respective data blocks. In this way, primary system130and backup system140can identify and find a given block of data on primary system130and the corresponding data block stored on backup system140.

In accordance with one aspect of the invention, primary system130determines whether a first block of data stored on primary system130and a corresponding, second block of data stored on backup system140are duplicates of one another. To accomplish this, primary system130generates a random value R, and transmits the random value and an identifier associated with the first data block to backup system140. Backup system140receives the random value R and the identifier, uses the identifier to retrieve the second block of data, and uses a selected D-G function to generate a digest DBrepresenting the second block of data. Backup system140then uses the digest DBto encode the random value R, producing an encoded value VB. Backup system140transmits the encoded value VBto primary system130. Primary system130similarly uses the D-G function to derive a digest DPfrom the first block of data, and then uses the digest DPto encode the random value R, generating an encoded value VP. Primary system130compares the encoded value VB(received from backup system140) to the encoded value VPto determine whether the two blocks of data are consistent. If the encoded value VBis equal to the encoded value VP, then the two data blocks are duplicates of one another. If VBis not equal to VP, then the two data blocks are different. Primary storage system130may further utilize this technique to compare multiple blocks of data with a plurality of corresponding data blocks stored on primary storage system130. It should be noted that, when used herein, any statement that two data blocks are “duplicates” of one another (or that they are “equivalent”, or “the same”) signifies that the two data blocks are assumed to be the same, within a negligible probability of collision.

The procedure outlined above is referred to as the “reverse challenge-response” method for comparing data. The random value R sent by primary system130constitutes a “challenge.” The encoded value VBsent from backup system140to primary system130represents the “response.”

FIG. 3Ais a flowchart describing a method for verifying the consistency of two blocks of data using the reverse challenge-response technique, in accordance with one implementation of the invention. At step375, controller220of primary system130retrieves a selected block of data for verification from one or more of storage devices240. In this example, a selected block of data stored in primary storage system130is referred to as a “data block P.” Similarly, a selected block of data stored in backup storage system140is referred to as a “data block B.” In one implementation in which primary system130utilizes the dynamic disk space allocation technique described above, a “block” of data may comprise a segment identified in a segment descriptor, or a portion thereof. In other implementations, a block of data may be defined differently.

At step377, controller220of primary system130generates a random value R. In the implementation illustrated inFIG. 3A, the random value R is a random number. The random number may be generated using any well-known random number generator. In one implementation, a random number function supported by C runtime library is employed. Another implementation uses a random number function supported by Java API. In other implementations, a cryptographically strong random number generating algorithm may be employed. Still other implementations employ non-numerical values for R.

To organize the information generated for various blocks of data, controller220of primary system130may maintain a table such as that shown inFIG. 4. Table420contains two columns430and435. Column430identifies a respective block of data stored on primary system130. Column435contains a random value for each respective data block. Each row in table420constitutes a record associated with a respective block of data. Referring to row462-1, for example, the data block identified by identifier Q-74is associated with random value R−1. It should be noted that the identifiers shown inFIG. 4(e.g., Q-74) are for illustrative purposes. Other implementations may use different forms of identifying information for various blocks of data.

In accordance to one implementation in which the dynamic disk space allocation technique described above is used, a respective data block is identified in database420by its segment identifier and, if necessary, additional information indicating a block within the segment. In accordance with this implementation, because a segment identifier identifies a logical unit of data rather than a physical address, both primary system130and backup system140are capable of utilizing the segment identifier information to locate the appropriate block of data. Referring toFIG. 4, for example, the label Q-74may identify a logical unit of data which is stored on primary system130as well as on backup system140. In accordance with the dynamic allocation technique, the physical location of the segment in primary system130is dynamically determined by controller220; likewise, the physical location of the segment in backup system140is dynamically determined by controller265. The same identifier may be used by both storage systems to keep track of the respective data blocks.

At step379, controller220of primary system130transmits the random value R and an identifier of an associated data block P to backup system140. In one implementation, primary system130sends segment identifier information associated with a data block P, and an associated random value.

In one implementation, primary system130transmits data pertaining to a single data block P using a data packet such as that shown inFIG. 5. Referring toFIG. 5, data packet590contains two fields592–593. Field592carries data identifying a data block P. In this example, field592contains an identifier for the data block Q-74. Field593contains the random value R−1 associated with data block Q-74. It should be noted that although for purposes of illustration, two fields are shown inFIG. 5, packet590may comprise any number of fields. In an alternative implementation, primary system130may transmit to backup system140data for multiple data blocks in the form of a table.

At step381, controller265of backup system140applies a D-G function to a data block B that corresponds to the data block P, to generate a digest DBthat represents the data block B. The D-G function may be any operation that generates a digest having a sufficiently high probability of detecting differences between two blocks of data. In accordance with one implementation, the D-G function is known to both the primary and backup storage systems prior to commencing the data synchronization process.

Referring toFIG. 5, controller265of backup system140receives data packet590, and retrieves the data block B identified as Q-74. Controller265then applies the known D-G function to the data block B to produce the digest DB. To organize data received from primary system130, controller265of backup system140may maintain a table similar to table420shown inFIG. 4.

In one implementation, the D-G function is a hash function. A hash function performs a transformation on an input and returns a number having a fixed length—a hash value. Properties of a hash function as used in the present invention include the ability to (1) take a variable-sized input and generate a fixed-size output, (2) compute the hash value relatively easily and quickly for any input value, and (3) be substantially (or “strongly”) collision-free. Examples of hash functions satisfying these criteria include, but are not limited to, the message digest 5 (MD5) algorithm and the secure hash (SHA-1) algorithm.

The MD5 algorithm generates a 16-byte (128-bit) hash value. It is designed to run on 32-bit computers. MD5 is substantially collision-free. Using MD5, hash values may be typically generated at high speed. The SHA-1 algorithm generates a 20-byte (160-bit) hash value. The maximum input length of a data block to the SHA-1 algorithm is 264bits (˜1.8×1019bits). The design of SHA-1 is similar to that of MD5, but because its output is larger, it is slightly slower than MD5, although it is more collision-free.

At step383, controller265of backup system140uses digest DBto encode the random number R, generating an encoded value VB. The encoding technique should be chosen carefully to minimize the probability of collisions. Accordingly, in one implementation, a hash function is used to encode the random number R. It is preferable to employ an encoding technique that is irreversible, to reduce the possibility that transmitted information may be intercepted. However, in other implementations, a reversible encoding technique may be used. In accordance with the example discussed above, controller265of backup system140uses the digest DBderived from the data block identified as Q-74to encode the random number R−1, generating an encoded value VB−1.

At step385, controller265of backup system140transmits the encoded value VB, and an identifier of the associated data block B to primary system130. In one implementation, backup system140transmits the encoded value VBand data identifying the associated data block B using a data packet similar to that shown inFIG. 5. In accordance with the example provided above, backup system140transmits a data packet conveying the identifier for data block Q-74in one field, and the associated encoded value VB−1 in a separate field.

Primary system130receives the data packet and extracts the encoded value VBand the identifier. Primary system130reads the identifier and associates the encoded value VBwith the corresponding data block P.

At this point, primary system130proceeds to derive a second encoded value by the same method used by backup system140. Thus, at step387, controller220of primary system130applies the D-G function (known to both the primary and backup systems) to the data block P to generate a digest DP. In an implementation in which a hash function is used to generate digests, the digest DPgenerated by primary system130is of the same length as the digest DBgenerated by backup system140.

At step389, controller220of primary system130uses the digest DPto encode the random value R associated with the data block P, producing an encoded value VP. Controller220of primary system130utilizes the same encoding technique used by backup system140to generate encoded value VB. In an implementation in which a hash value is used by backup system140to generate the encoded value VB, the same hash function is utilized by primary system130to produce the encoded value VP. Following the example discussed above, controller220of primary system130uses the digest DPto encode the random number R−1, generating the encoded value VP−1.

To organize the information associated with various blocks of data, primary system130may maintain a table such as that shown inFIG. 6. Table620contains three columns630,635and640. Column630identifies a respective block of data stored on primary system130. Column635contains an encoded value VBreceived from backup system140that is associated with a respective data block. Column640stores an encoded value VPgenerated by primary system130. Each row in table620constitutes a record associated with a respective block of data. Referring to row662-1, for example, the data block identified as Q-74is associated with encoded values VB−1 and VP−1.

At step391, controller220of primary system130compares the encoded value VBreceived from backup system140with the associated encoded value VP. If it is determined, at block395, that the encoded value VPequals encoded value VB, then data block P and data block B are duplicates of one another (step396). If VPis not equal to VB, then data block P and data block B are different (step397).

FIG. 3Bis a flowchart illustrating a method for verifying the consistency of two data blocks using the reverse challenge-response method, in accordance with an alternative implementation of the invention. Referring toFIG. 3B, at step310, primary system130retrieves a data block P. At step315, primary system130applies a D-G function to the data block P, generating a digest DP. In one implementation, primary system130uses a hash function to generate the digest DP. At step320, primary system130generates a random number RP.

At step325, primary system130uses the digest DPto encode the random number RP, producing an encoded value VE. At step330, primary system130transmits the encoded value VEand an identifier for the data block P to backup system140.

At step335, backup system140applies the known D-G function to a data block B that corresponds to the data block P, generating a digest DB. At step340, backup system140uses the digest DBto decode the encoded value VE, producing a decoded number RB, and transmits the decoded number RBto primary system130(step345).

At step350, primary system130compares the decoded number RBto the random number RPto determine whether the data block B is a duplicate of the data block P. Referring to block360, if RPis equivalent to RB, then the two data blocks are duplicates of one another (block365). If RPand RBare not the same, the two data blocks are different (block370).

In accordance with another aspect of the invention, primary system130transmits to backup system140a copy of a data block P that is inconsistent with the corresponding data block B.FIG. 7is a flowchart depicting a method for synchronizing data in accordance with this aspect of the invention. This is accomplished by ascertaining values VPand VBfor one or more corresponding blocks of data as described above with reference toFIG. 3A. Referring to block803, if the encoded value VPis equal to encoded value VB, then the process ends. If multiple data blocks are being examined, primary system130may at this point proceed to another data block.

If, however, the encoded value VPis not equal to the encoded value VB, then, at step805, controller220of primary system130transmits a copy of the data block P associated with the value VPto backup system140. At step809, controller265of backup system140stores the copy of the data block P, thus ensuring that the data in the two systems are synchronized. Referring toFIG. 6as an example, if the encoded value VP−1 and the encoded value VB−1 are not equal, then the data block Q-74on primary system130and the data block Q-74on backup system are different. In this case, controller220of primary system130transmits a copy of the contents of the data block P identified as Q-74, and backup system140stores the copied data block. In one implementation, backup system140overwrites the existing data block B identified as Q-74.

It should be noted that, although in the implementations described above, primary system130initiates the process of comparing two data blocks, by retrieving a data block P, generating a random number R, etc., in another implementation this role may be performed by backup storage system140. In accordance with this implementation, backup system140retrieves a data block B and generates a random value R, and transmits the random value R to primary system130. Primary system130retrieves a corresponding block P, generates a first digest, uses the first digest to encode the random value R, and transmits a first encoded value back to backup system140. Backup system140derives a second digest from the data block B, and uses the second digest to encode the random value R to produce a second encoded value. According to this implementation, backup system140compares the first encoded value to the second encoded value to determine if the data block B and the data block P are the same. If the first encoded value is equivalent to the second encoded value, the data block B is a duplicate of the data block P. If the first encoded value is not the same as the second encoded value, the data block B is different from the data block P. In accordance with this implementation, if the data blocks are different, backup system140may transmit a copy of the data block B to primary system130. After receiving a copy of the data block B from backup system140, primary system130stores the copied data block.

It should be further noted that, although in the implementations described above, digests are generated by hash functions, other D-G functions may be employed. For example, in an alternative implementation, the cyclic redundancy check (CRC) may be used to generate a digest.

SCSI Command

In accordance with another aspect of the invention, a primary storage system transmits to a backup storage system, in accordance with standard protocols, a message directing a backup storage system to perform a synchronization operation with respect to a specified block of data. Specifically, the primary system transmits a message conveying a random value and an identifier for a respective block of data. The message further represents a request that the backup storage system apply a known D-G function to the respective block of data to generate a digest, utilize the digest to encode the random value, and send back to the primary system an encoded value. Such a message is referred to as a “reverse challenge-response request.” In response to the request, the backup system applies the known D-G function to the respective block of data to generate a digest, utilizes the digest to encode the random value, and sends the resulting encoded value back to the primary system.

In accordance with one implementation, the reverse challenge-response request is implemented as a Small Computer System Interface (SCSI) command. SCSI is a standard for connecting computers to peripheral devices such as disk drives. The SCSI standard specifies the hardware and software interface between these devices at a level that minimizes dependencies on any specific hardware implementation. This is achieved by representing data stored on a storage device as a collection of logical blocks rather than in terms of the data's physical address. This abstraction allows the SCSI protocol to be used with a wide variety of devices.

The central item of hardware in a SCSI system is the SCSI bus, which must conform to the specification of the SCSI standard. A SCSI device refers to any device that is connected to the SCSI bus. Each SCSI device on the bus is assigned a SCSI ID that uniquely identifies the device during SCSI transactions.

The SCSI standard also establishes a set of protocols by which SCSI devices may communicate. When two SCSI devices communicate, one device acts as the initiator and the other as the target. The initiator begins a transaction by selecting a target device. The target responds to the selection and requests a command. The initiator then sends a SCSI command, and the target performs the action.

SCSI transactions comprise up to eight distinct phases: bus free, arbitration, selection, reselection, command, data, status and message.FIG. 8is a block diagram showing the relationship of the SCSI bus phases. The bus free phase815indicates that no SCSI devices are using the SCSI bus. During arbitration phase820, a SCSI device may gain control of the SCSI bus. All devices requesting to use the bus assert their SCSI ID by transmitting a signal onto the bus. The device having the highest ID wins the arbitration and becomes the initiator for the next SCSI transaction. During selection phase825, the initiator selects a target device. The optional reselection phase (not shown) allows a peripheral that is busy performing a lengthy data processing action to disconnect from and subsequently reconnect to the SCSI bus.

The last four phases (command, data, status and message) are referred to collectively as the information transfer phases, and are represented inFIG. 8by block840. During these phases, data can be transferred between the initiator and target devices. During the command phase, the target requests a command from the initiator, and in response, the initiator transfers a SCSI command to the target. A SCSI command is an instruction from an initiator to a target to perform an action, such as reading or writing a block of data. SCSI commands are contained in a data structure called a command descriptor block, which can be 6, 10 or 12 bytes in size. The first byte specifies the action requested, and the remaining bytes are parameters used for that action. The target can determine from the first command byte transmitted how many command bytes will follow.

During the data phase, data is transferred between the initiator and the target. To indicate that it is ready to transmit data to the initiator, the target transmits an input/output (I/O) signal indicating DATA IN. To indicate that it is ready to receive data, the target transmits a DATA OUT signal.

During the message phase, the target requests the transfer of a message. The SCSI standard specifies a number of possible messages that may be exchanged between SCSI devices. SCSI messages must conform to the structure specified by the SCSI standard and generally carry information about a SCSI transaction. The status phase occurs after completion of all commands and allows the target to transmit a status signal to the initiator. For example, the target may send status information indicating that an operation completed successfully, or that an error occurred. After a transaction is completed, the bus returns to the bus free phase815.

According to this implementation, a primary storage system, in the role of initiator, sends to a backup storage system, acting as target, a SCSI command representing a reverse challenge-response request. The SCSI command conveys a random value and an identifier for a respective block of data, and directs the backup storage system to apply a known D-G function to the respective block of data to generate a digest, utilize the digest to encode the random value, and send back to the primary system an encoded value. In response, the backup system applies the known D-G function to the respective block of data, generating a digest, utilizes the digest to encode the random value, and sends to the primary system the resulting encoded value.

FIG. 9is a flowchart showing a method for transmitting to a backup storage system a SCSI command representing a reverse challenge-response request. Referring to block923, controller220of primary system130first performs steps375–377depicted inFIG. 3A. Accordingly, controller220retrieves a data block P, and generates a random number R.

At step925, controller220of primary storage system130initiates a SCSI transaction with backup storage system140. Referring toFIG. 8, controller220arbitrates to use a SCSI bus in arbitration phase820and selects backup system140as the target device in selection phase825. In another implementation, controller220(of primary system130) selects controller265(of backup system140) as the target. Alternatively, controller220selects a storage device (e.g.,280-1) as the target.

Returning toFIG. 9, at step932, controller220of primary system130generates a SCSI command that represents a reverse challenge-response request. In accordance with this implementation, a customer-defined SCSI command is utilized. Accordingly, primary system130generates a command descriptor block (CDB) of 6, 10 or 12 bytes in size. The CDB includes an identifier of a respective data block P stored in primary system130and the random value R.

At step942, controller220of primary system130transmits the SCSI command over network120to backup system140. Referring toFIG. 8, primary system130transmits the SCSI command to backup system140during the command phase, which occurs during information transfer phases840.

At step950, controller265of backup system140receives the SCSI command and extracts the identifier for a respective data block P stored in primary system130, and the random value R. Referring to block952, the interaction between backup system140and primary system130then proceeds as described previously, starting at step381ofFIG. 3A. Accordingly, controller265of backup system140applies the known D-G function to a corresponding data block B to generate a digest DB, uses the digest DBto encode the random value R and produce an encoded value VB, and transmits the encoded value VBback to primary system140. In the same manner as described above, controller220of primary system130then generates a digest DPthat represents the data block P, and uses the digest DPto encode the random value R, generating an encoded value VP. Controller220of primary system130compares the encoded value VPwith the encoded value VBto determine whether the two data blocks are duplicates of one another.

It should be noted that, although in the implementations described above, primary system130initiates the process of synchronizing two data blocks, by transmitting a SCSI command, in accordance with another implementation this role may be performed by backup storage system140. In accordance with this implementation, backup system140generates and transmits to primary system130a command representing a reverse challenge-response request. The command conveys an random value and identifies a respective block of data. In response to the request, primary system130applies the known D-G function to a corresponding block of data to generate a digest, utilizes the digest to encode the random value, and sends the resulting encoded value back to backup system140. In the manner described above, backup system140derives a second digest from a corresponding data block, uses the second digest to encode the random value, generating a second encoded value, and compares the two encoded values to determine whether the two data blocks are duplicates of one another.