Data encryption for a segment-based single instance file storage system

Various embodiments of a system and method for backing up a plurality of copies of a file are described. A first copy of the file may be owned by a first user, and a second copy of the file may be owned by a second user. The file is split into a plurality of segments, and each segment is encrypted with a respective segment key. Each encrypted segment is transmitted to and stored on a server computer system. De-duplication techniques are used to ensure that only a single instance of each encrypted segment is stored. The segment keys used to encrypt the file segments are also stored on the server computer system in an encrypted form. De-duplication techniques may be utilized so that only a single instance of the encrypted segment keys is stored.

BACKGROUND OF THE INVENTION

Field of the Invention

This invention relates to the field of computer data storage. More particularly, the invention relates to a system and method using de-duplication and encryption techniques to store files for a plurality of users in a file storage pool on a server computer system.

Description of the Related Art

Computer systems generally store information as files organized by a file system. Each file may be stored on a storage device, such as a disk drive, optical drive, or tape drive. It is often necessary to back up files by copying them to another storage device. For example, backup operations may be performed to guard against hardware failure or data loss, to provide a snapshot of files at a particular point in time, or to replicate files for other purposes.

In a networked computing environment, a plurality of client computer systems may each back up files to a backup server computer system. It is possible that an identical file is stored on multiple client computer systems. For example, two or more client computer systems may each store a copy of a file, where the data in each copy is identical. For example, client computer systems that execute the same operating system or the same software applications often have many identical files.

De-duplication techniques can be utilized so that only a single copy of each file is stored on the backup server computer system. For example, for each client computer system that has a copy of a particular file, the backup server computer system may store respective file metadata representing that copy. The portions of file metadata associated with each respective copy of the file may all reference a single instance of the file data (the actual contents of the file). In this way, the backup system can avoid the need to store multiple copies of identical files on the backup server computer system. A storage system which uses de-duplication to store and reference a single instance of data in order to avoid storing multiple copies of identical data is generally referred to as a single instance storage system.

It is sometimes desirable to store the files on the backup server computer system in encrypted form, e.g., to prevent unauthorized use of the files. An encryption algorithm typically uses a key (e.g., information such as a series of bits) to transform the file data into an encoded form. Thus, for example, each client computer may have its own key which is used to encrypt its files before transmitting them to the backup server computer system so that the files received from each client computer are unreadable by any user or application who does not possess the client computer's particular key.

However, since the process of encrypting a file involves transforming the file data into an encoded form that depends upon the encryption key that is used, different copies of an identical file encrypted by different client computers will produce different encrypted data since the encryption keys for the client computers are different from each other. This is a problem for single instance storage systems because even though the original file data is identical, the resulting encrypted data produced by the different client computers is not identical.

SUMMARY

Various embodiments of a system and method for backing up a plurality of copies of a file to a server computer system are described herein. For example, a first copy of the file may be owned by or associated with a first user, and a second copy of the file may be owned by or associated with a second user. According to some embodiments of the method, the file may be split into a plurality of segments, and each segment may be encrypted with a respective segment key. In some embodiments the respective segment key used to encrypt each segment may be derived based on the unencrypted contents of the segment. Each encrypted segment may be transmitted to a server computer system for storage on the server computer system.

The method may further comprise storing information corresponding to the first copy of the file on the server computer system. The information corresponding to the first copy of the file may include information specifying each stored encrypted segment of the plurality of encrypted segments, and may also include a first encrypted aggregation of the segment keys for the plurality of encrypted segments. The first encrypted aggregation may be encrypted with a private key of the first user.

The method may further comprise storing information corresponding to the second copy of the file on the server computer system. The information corresponding to the second copy of the file may include information specifying each stored encrypted segment of the plurality of encrypted segments, and may also include a second encrypted aggregation of the segment keys for the plurality of encrypted segments. The second encrypted aggregation may be encrypted with a private key of the second user.

In an alternative embodiment of the method, the plurality of encrypted segments may be stored on the server computer system, and a single encrypted aggregation of the segment keys for the plurality of encrypted segments may be stored on the server computer system. The encrypted aggregation of the segment keys may be encrypted with a key K, where the key K is derived from the unencrypted aggregation of the segment keys. In this embodiment, the method may comprise storing information corresponding to the first copy of the file on the server computer system, where the information corresponding to the first copy of the file includes: 1) information specifying each stored encrypted segment of the plurality of encrypted segments; 2) information specifying the stored encrypted aggregation of the segment keys for the plurality of encrypted segments; and 3) a first encrypted version of the key K encrypted with a private key of the first user. The method may further comprise storing information corresponding to the second copy of the file on the server computer system, where the information corresponding to the second copy of the file includes: 1) information specifying each stored encrypted segment of the plurality of encrypted segments; 2) information specifying the stored encrypted aggregation of the segment keys for the plurality of encrypted segments; and 3) a second encrypted version of the key K encrypted with a private key of the second user.

DETAILED DESCRIPTION

Various embodiments of a system and method for backing up files to or storing files on a server computer system are described herein. The server computer system may receive files from a plurality of client computers, e.g., where the plurality of client computers are associated with or used by a plurality of users. The server computer system may store the files in a storage pool on behalf of the users. The system and method may operate to store the files in the storage pool in an encrypted form, while still maintaining single instance storage properties such that if different users each have their own copy of a particular file, the server computer system only stores a single instance of the data of the particular file, e.g., as opposed to storing multiple copies. More particularly, the files stored on the server computer system may be split into a plurality of segments, where each segment is encrypted, and where only a single instance of each segment is stored.

FIG. 1Aillustrates one embodiment of the system. The system includes a plurality of client computer systems7. Although three client computer systems7A-7C are shown in this example, in other embodiments there may be any number of client computer systems7. Each client computer system7may include one or more storage devices on which one or more files are stored. Each file may be associated with or owned by a particular user44. In some embodiments each user44may be a particular person. In other embodiments a user44may be an entity other than a person. For example, in some embodiments a user44may be a company or organization. In other embodiments a user44may be a particular software application. In general, a user may be any entity on whose behalf the server computer system10is configured to backup files, or any entity with which the server computer system10is configured to associate stored files.

In the example ofFIG. 1A, each client computer7is associated with a particular user44. For example, the client computer7A may be used by a user44A, the client computer7B may be used by a user44B, and the client computer7C may be used by a user44C. In other embodiments there may not be a one-to-one correspondence between client computers7and users44. For example, in some embodiments a particular user44may use multiple client computers7, and different ones of the user's files may be stored on different client computers7. In other embodiments a particular client computer7may be shared by multiple users44such that the particular client computer7stores files for different users44.

The system also includes a server computer system10. Backup client software180executing on the client computers system7may communicate with backup server software190executing on the server computer system10to transmit the files associated with or owned by the users44to the server computer system10for storage in a storage pool50. For example, in some embodiments the server computer system10may be a backup server computer system configured to backup the files on behalf of the users44, e.g., to protect the files against hardware failure or data loss, to save a snapshot of the files at a particular point in time, and/or to replicate the files for other purposes. The storage pool50is a storage area or database implemented using storage space of one or more storage devices included in or coupled to the server computer system10.

The backup client software180on the client computer systems7may be configured to split the files into segments before transmitting them to the server computer system10. The backup client software180may also encrypt the segments before transmitting them to the server computer system10. Thus, a particular file may be transmitted from one or more client computer systems7to the server computer system10by transmitting the encrypted segments of the particular file.

Suppose now that two different users44A and44B each own an identical copy of a particular file, e.g., where one copy is stored on a client computer7A used by the user44A, and the other copy is stored on a client computer7B used by the user44B. (The copies are said to be identical if the data contents of each copy are the same, although the file metadata or file system attributes of the two copies, such as their respective creation times, their pathnames, etc., may differ.) The two copies of the file may be backed up to the server computer system10in such a way that data segments of the file are stored in an encrypted form, and also such that only a single copy of each encrypted data segment is stored in the storage pool50on the server computer system10.

For example, suppose that the copy of the file on the client computer7A is first backed up to the server computer system10. The backup client software180executing on the client computer7A may split the file into a plurality of segments and encrypt each segment. The backup client software180may communicate with the backup server software190executing on the server computer system10to determine whether the encrypted segments are already stored on the server computer system10. Any encrypted segments not yet stored on the server computer system10may be transmitted to the server computer system10for storage.

In addition the backup client software180may also transmit to the server computer system10decryption information useable to decrypt the encrypted segments of the file. The decryption information may include information encrypted with a private key of the user44A, e.g., such that the private key of the user44A is necessary in order to use the decryption information to decrypt the encrypted segments of the file. The private key of the user44A is an encryption key which is kept private by the user44A and is not known by other users44or other software programs not controlled or authorized by the user44A. Thus, other users44or other software programs not controlled by the user44A may not be able to use the decryption information to decrypt the encrypted segments of the file since they do not have the private key of the user44A.

It is noted that the private key of the user44A may be a key used by either a symmetrical encryption scheme or an asymmetrical encryption scheme. The term “private key” is often used in the context of an asymmetrical encryption scheme. An asymmetrical encryption scheme uses a pair of keys: a private key and a public key. The public key is primarily used to encrypt data and is typically publicly known. The public key cannot be used to decrypt the data that was encrypted using the public key. The private key is used to decrypt the data encrypted with the corresponding public key and is known to just one party. Thus, in some embodiments the private key of the user44A may be the private key in a public/private key pair used in an asymmetrical encryption scheme, e.g., where the private key is known only by the user44A. In other embodiments the private key of the user44A may be a key used in a symmetrical encryption scheme, where the same key is used to both encrypt data and decrypt the encrypted data, and again where the private key is known only by the user44A.

The backup client software180executing on the client computer system7B may subsequently backup the copy of the file owned by the user44B in a similar manner. For example the backup client software180executing on the client computer system7B may split the file into a plurality of segments and encrypt each segment so as to produce identical encrypted segments as those produced by the backup client software180executing on the client computer system7A. In this case, the backup client software180executing on the client computer7B may determine from the server computer system10that all of the encrypted segments are already stored on the server computer system10, and thus, the backup client software180executing on the client computer system7B may not transmit any of the encrypted segments to the server computer system10.

The backup client software180executing on the client computer system7B may transmit to the server computer system10decryption information useable to decrypt the encrypted segments of the file. In this case, however, the decryption information transmitted by the backup client software180executing on the client computer system7B may include information encrypted with the private key of the user44B instead of the user44A. Thus, other users44or other software programs not authorized by the user44B may not be able to use the decryption information transmitted by the backup client software180executing on the client computer system7B to decrypt the encrypted segments of the file since they do not have the private key of the user44B.

In response to the information received from the client computer systems7A and7B when the respective copies of the file are backed up, backup server software190executing on the server computer system10may store information in a storage pool50which represents the respective copies of the file. For example,FIG. 1Billustrates an example of the storage pool50according to one embodiment. In this example, the storage pool50includes a segment storage area or database58in which the backup server software has stored the encrypted segments of the file, e.g., the encrypted segments32A-32E in this example.

The backup server software has also stored file information68A corresponding to the user44A's copy of the file and file information68B corresponding to the user44B's copy of the file. The file information68for a given copy of a file is also referred to herein as “metadata”. The metadata68corresponding to each respective copy of the file may indicate which user owns the respective copy of the file. For example, the metadata68A may specify the user44A as the user who owns the particular copy of the file to which the metadata68A corresponds. In another embodiment the backup server software may, for example, store the metadata68A in a respective file information storage area or database corresponding to the user44A in order to indicate that the user44A owns the respective copy of the file.

Both the metadata68A and68B in this example include reference information306which specifies or references the encrypted segments32A-32E, e.g., in order to identify which encrypted segments contain the data for the file. The reference information306may specify or reference the encrypted segments of the file either directly or indirectly in any of various ways. For example, in some embodiments each encrypted segment may have a corresponding name or ID, or other information that uniquely identifies the encrypted segment, and the reference information306may directly specify the IDs of the encrypted segments of the file. In other embodiments the reference information306or metadata68may indirectly specify the encrypted segments of the file by directly specifying one or more objects, where the objects then directly specify the encrypted segments of the file. Also, there may be multiple levels of indirection in some embodiments. For example, in some embodiments the reference information306may directly specify a first one or more objects, where the first one or more objects then specify a second one or more objects, and where the second one or more objects then specify the encrypted segments of the file (or where the second one or more objects then specify a third one or more objects that specify the encrypted segments of the file, etc.)

The metadata68A includes decryption information79A, e.g., the decryption information received from the client computer system7A. As noted above, the decryption information79A includes information encrypted with the private key of the user44A. Similarly, the metadata68B includes decryption information79B, e.g., the decryption information received from the client computer system7B, which includes information encrypted with the private key of the user44B. Thus, the decryption information79A may be used to decrypt the encrypted segments of the file, but only if the private key of the user44A is known. This may prevent users other than the user44A (or software programs which do not execute with authorization of the user44A) from decrypting the encrypted segments of the file using the decryption information79A. Similarly, the decryption information79B may be used to decrypt the encrypted segments of the file, but only if the private key of the user44B is known.

In some embodiments the respective metadata68for a respective copy of the file may also specify various other attributes of the copy of the file, e.g., file system attributes specifying properties of the copy of the file on the respective client computer7from which the copy of the file originated, such as the file's pathname, creation time, last modification time, etc.

Thus, for each copy of a file backed up to or stored on the server computer system10from a respective client computer7, the server computer system10may store respective metadata68for the copy of the file in the storage pool50. If different client computer systems7each backup respective copies of the same file then only a single instance of the encrypted file segments containing the file's data are stored in the storage pool50, and the metadata entries corresponding to the various copies of the file all reference the same encrypted file segments.

Referring now toFIG. 2, a detailed embodiment of an algorithm for backing up a particular file20A owned by or associated with a user44A is illustrated. The file20A may originally be stored on a particular client computer system7A. The algorithm may be implemented by software, e.g., backup client software180, executing on the client computer system7A.

As indicated by arrow1A, the backup client software180may split the file20A into a plurality of segments22. In this example, the file20A is split into five segments22A-22E. In some embodiments each segment may be a fixed size, such as 128 kb or another fixed size of N bytes. Thus, for example, the segment22A may include the first N bytes of the file20A's data, the segment22B may include the next N bytes of the file20A's data, and so on. In other embodiments the segments22may be created in any of various other ways. Also, in some alternative embodiments the segments22may vary in size. For example, in some embodiments the backup client software180may analyze the file data to identify where each segment of the file should begin and end.

In some embodiments the file may be split into segments22by creating one or more data structures representing each segment22. For example, in some embodiments the portion of the file data corresponding to each segment22may be copied into a respective data structure. In other embodiments, splitting the file may comprise creating information indicating where each segment22begins and ends, but the file data may not necessarily be copied into other data structures.

As indicated by arrow2A, the backup client software may generate a respective content-based key30for each of the segments22. The content-based key30for each segment22is an encryption key that will be used to encrypt the segment22, where the key is derived from the contents (data) of the segment22. For example, the content-based key30A is derived using the data of the segment22A, the content-based key30B is derived using the data of the segment22B, etc. In various embodiments the content-based keys30may include any information useable by an encryption algorithm to encrypt the segments22. In a typical embodiment, a content-based key30may be a series of bits, such as a 64-bit key, or a 128-bit key, etc.

In various embodiments any desired algorithm operable to generate the content-based keys30based on the data of the respective segments22may be used. For example, the content-based key30for a particular segment22may be generated by using the data of the segment22to perform one or more mathematical functions or calculations. The key generation algorithm is an algorithm that will generate the same content-based key30every time for a given segment22as long as the data for the segment22remains the same.

As indicated by the arrow3A, the backup client software may encrypt each segment22using the respective content-based key30for the segment22, i.e., using the key derived from the data of the respective segment22. For example, the segment22A may be encrypted using the content-based key30A, the segment22B may be encrypted using the content-based key30B, etc. Thus, each segment22is encrypted into a respective encrypted segment32, as illustrated inFIG. 2.

As indicated by the arrow4A, the backup client software may also aggregate the content-based keys30to produce an aggregation36. The aggregation36is information that includes each of the content-based keys30. In various embodiments the aggregation may be produced using any of various techniques, and the aggregation may be structured in any of various ways or may be represented using any type of data structure. In some embodiments the aggregation may be produced by concatenating the content-based keys30, e.g., by appending the bits of the respective keys30to produce a single series of bits that includes all the bits of the individual keys30. In other embodiments the backup client software may produce an aggregation of the content-based keys30in any of various ways other than concatenation.

As indicated by the arrow5A, the backup client software may then encrypt the aggregation36using the private key of the user44A to produce an encrypted aggregation38A. Other users44or other software programs not controlled by or authorized by the user44A may not be able to decrypt the encrypted aggregation38A since they do not have the private key of the user44A.

As indicated by the arrows6A and7A, the backup client software180executing on the client computer system7A may communicate with backup server software190executing on the server computer system10to transmit the encrypted segments32and the encrypted aggregation38A to the server computer system10. The backup client software180may also transmit other file attributes regarding the file20A to the server computer system10, e.g., file system attributes of the file20A, such as its pathname, creation time, last modification time, etc.

The backup server software190executing on the server computer system10may store the information received from the client computer system7A in the storage pool50.FIG. 3illustrates an example of the storage pool50after the information has been stored according to one embodiment. The storage pool50may include a segment storage area or database58in which the encrypted segments32A-32E have been stored. The storage pool50may also include metadata representing files owned by the user44A which have been backed up to the server computer system10. In some embodiments the metadata for the user44A's files may be stored in a separate storage area or database allocated to the user44A. In other embodiments the metadata for the user44A's files may be stored together with metadata for other users' files, and each portion of metadata may simply identify the respective user44to which the metadata corresponds.

As shown inFIG. 3, the backup server software190has stored metadata68A corresponding to the file20A in the storage pool50. The metadata68A includes reference information306which specifies or references the encrypted segments32A-32E which include the data for the file20A (in encrypted form). The metadata68A also includes the encrypted aggregation38A which is encrypted with the private key of the user44A and includes the content-based keys that were used to encrypt the segments of the file. The metadata68A may also include other information, such as file attributes304for the file20A received from the client computer system7A (e.g., file pathname, last modification time, etc.).

In this example, other file metadata68B and68C representing other files20B and20C owned by the user44A has also been stored. (The details of the metadata68B and68C is not shown.) Other encrypted segments32F-32L referenced by the metadata68B and68C have also been stored in the segment storage area58. For example, the metadata68B and68C and the encrypted segments32F-32L may have previously been stored when the files20B and20C were previously backed up from the client computer7A to the server computer system10.

Suppose now that another user44B of another client computer system7B has a file20D which is an identical copy of the file20A. (The file attributes of the file20D, such as the pathname, creation time, etc., may be different than those of the file20A, but the actual data contents of the two files are the same.) Backup client software180executing on the client computer system7B may perform the algorithm described above with reference toFIG. 2to backup the file20D to the server computer system10. The file20D may be split into the same file segments22A-22E as were produced on the client computer system7A. The same content-based keys30A-30E may be generated from the file segments22A-22E, and the same encrypted file segments32A-32E may be produced from the file segments22A-22E using the content-based keys30A-30E.

The backup client software executing on the client computer system7B may also produce the same aggregation36including the content-based keys30A-30E. However, instead of encrypting the aggregation36with the private key of the user44A, the backup client software180executing on the client computer system7B may encrypt the aggregation36with a private key of the user44B, which results in an encrypted aggregation38B which is different than the encrypted aggregation38A.

In some embodiments the backup client software180on the client computer system7B may first communicate with the backup server software to determine whether the encrypted segments32A-32E are already stored in the storage pool50before transmitting the encrypted segments32to the server computer system10. If a given encrypted segment32is already stored in the storage pool50then the encrypted segment32may not be transmitted to the server computer system10. Thus, in this example, since all of the encrypted segments32A-32E were previously stored in the storage pool50when the file20A was backed up from the client computer system7A, the encrypted segments32A-32E may not be transmitted. (The backup client software180on the client computer system7A may also check first to determine whether the encrypted segments32A-32E need to be transmitted to the server computer system10when backing up the file20A.) The backup client software180on the client computer system7B may still transmit the encrypted aggregation38B and the file attributes of the file20B to the server computer system10.

In response, the server computer system10may store metadata68D for the file20D in association with the user44B, as illustrated inFIG. 4. The reference information306of the metadata68D references the same encrypted segments32A-32E previously stored in the segment storage area58when the file20A was backed up from the client computer system7A. The metadata68D also includes the encrypted aggregation38B which is encrypted with the private key of the user44B and the file attributes304of the file20D received from the client computer system7B.

Thus, the system may be configured to perform de-duplication on the basis of file segments so that there is only a single instance of each unique file segment. In some systems, splitting files into multiple segments and backing the files up on the basis of their individual segments may increase the storage efficiency of the storage pool50since different files may not be exactly identical but may contain some segments in common with each other. Furthermore, each file segment may be stored in an encrypted form to protect against unauthorized access to the files.

Referring again to arrow3A ofFIG. 2where the segments22are encrypted, it is noted that the content-based keys30may be used in any desired encryption algorithm in order to produce the encrypted segments32. In some embodiments the content-based keys30may be used in a symmetrical encryption scheme where the same content-based key used to encrypt each respective segment will later be used to decrypt the respective segment. In other embodiments the content-based keys30may be used in an asymmetrical encryption scheme. For example, the backup client software180may generate a public/private key pair for each segment based on the content of the segment. For each segment, the public key of the key pair generated for the segment may be used to encrypt the segment and may then be discarded. The private keys for all of the key pairs for the segments may be included in the aggregation36.

FIG. 5is a flowchart diagram illustrating one embodiment of a method for restoring a file from the server computer system10to a client computer system7. For example, the backup client software180executing on the client computer7A may perform the method to restore the file20A.

As indicated in471, the backup client software180executing on the client computer7A may communicate with the backup server software to receive the metadata68A and the encrypted segments32A-32E for the file20A from the server computer system10. The metadata68A may include the encrypted aggregation38A.

As indicated in473, the backup client software180may decrypt the encrypted aggregation38A using the private key of the user44A to produce the unencrypted aggregation36. The content-based keys that were used to generate the encrypted segments32A-32E may then be retrieved from the aggregation36. For example, if the aggregation was produced by concatenating the content-based keys for the respective file segments then the backup client software180may split the concatenation36to obtain the individual content-based keys30A-30E.

As indicated in475, the backup client software180may decrypt the encrypted segments32using their respective content-based keys30to produce the original file segments22.

As indicated in477, the backup client software180may then assemble the file from the decrypted segments22, e.g., by appending the data from each segment into a single file having data identical to the original file20A.

Thus, the method enables the backup client software180executing on behalf of the user44A to restore the file20A using the private key of the user44A. However, other users44or unauthorized software do not possess the private key of the user44A, and thus may not be able to restore and access the file20A using the metadata68A stored on the server computer system10. Similarly, the backup client software executing on behalf of the user44B, can restore the file20D using the private key of the user44B, but other users44and unauthorized software do not possess the private key of the user44B.

As described above, since the keys used to encrypt the segments for a file are derived from the content of the segments themselves, the backup client software180for each user having a copy of the file will produce identical encrypted segments, which enables de-duplication of the encrypted segments on the server computer system10. Since the segment keys produced for all the users are the same, the aggregation36of the segments keys may also be the same. However, in the embodiments described above, the aggregation36is encrypted with the private key of each user44, which results in different encrypted aggregations38. For example, the aggregation36created by the client computer7A is encrypted with the private key of the user44A to produce the encrypted aggregation38A, and the aggregation36created by the client computer7B is encrypted with the private key of the user44B to produce a different encrypted aggregation38B. Thus, although the underlying segment keys are the same, the segment keys are effectively duplicated on the server computer system10for each copy of the file.

Further embodiments of the method may eliminate this duplication of the segment keys on the server computer system10. For example,FIG. 6illustrates an alternative embodiment of a method for backing up the file20A owned by the user44A.

As indicated by arrows1B and2B, the backup client software180B executing on the client computer7A may split the file20A into a plurality of segments22A-22E and generate a respective content-based key30for each of the segments22, similarly as described above. As indicated by the arrow3B, the backup client software180may encrypt each respective segment22using the respective content-based key30for the respective segment22, to produce the same encrypted segments32A-32E as previously described above.

As indicated by the arrow4B, the backup client software may also concatenate the content-based keys30to produce a concatenation36, e.g., by appending the bits of the respective keys30to produce a single series of bits that includes all the bits of the individual keys30. In other embodiments the backup client software may produce an aggregation of the content-based keys30in any of various ways other than concatenation. An aggregation of the content-based keys30may include any information which includes the content-based keys30.

The backup client software180may also aggregate the content-based keys30to produce the same aggregation36as described above. However, instead of encrypting the aggregation36with the private key of the user44A, the backup client software180instead generates a content-based key “K”34from the aggregation36, as indicated by the arrow5B. For example, in some embodiments the key “K” may be derived using the bits of the aggregation36, e.g., using the same algorithm or a similar algorithm as the one used to derive the content-based keys30from the segments22.

As indicated by the arrow6B, the backup client software180may then encrypt the aggregation36using the derived key “K”34, which results in the encrypted aggregation38.

As indicated by the arrow7B, the backup client software180may also encrypt the key “K”34with the private key of the user44A, which results in the encrypted key “K”39A. Thus, other users44or other software programs not controlled by or authorized by the user44A may not be able to decrypt the encrypted key “K”39A since they do not have the private key of the user44A.

As indicated by the arrows8B,9B, and10B, the backup client software180executing on the client computer system7A may communicate with backup server software executing on the server computer system10to transmit the encrypted segments32, the encrypted aggregation38, and the encrypted key “K”39A to the server computer system10. The backup client software may also transmit other file attributes regarding the file20A to the server computer system10, e.g., file system attributes of the file20A, such as its pathname, creation time, last modification time, etc.

The backup client software180executing on the client computer7B may backup the identical file20D in a similar manner. Since the aggregation36produced on the client computer7B is the same as the aggregation36produced on the client computer7A, the key “K” derived from the aggregation36will be the same in both cases. Thus, the encrypted aggregation38will also be the same in both cases since the same key “K” is used on both the client computer7A and the client computer7B to create the encrypted aggregation38. However, in this case the key “K” derived from the aggregation36is encrypted with the private key of the user44B to produce an encrypted key39B.

The backup server software executing on the server computer system10may store the information received from the client computer system7A and the client computer system7B in the storage pool50.FIG. 7illustrates an example of the storage pool50after the information has been stored according to one embodiment. The storage pool50may include a segment storage area or database58in which the encrypted segments32A-32E have been stored, similarly as described above. In this example, the storage pool50also includes a segment key storage area or database63in which the encrypted aggregation38has been stored. The reference information306in the metadata68A for the file20A and the reference information306in the metadata68D for the file20D both reference the same instances of the encrypted segments32A-32E, and also reference the same encrypted aggregation38.

The metadata68A for the file20A includes the encrypted key “K”39A, i.e., the version of the key “K” encrypted with the private key of the user44A. Similarly, the metadata68D for the file20D includes the encrypted key “K”39B, i.e., the version of the key “K” encrypted with the private key of the user44B.

Thus, in this embodiment a single encrypted instance of the segment keys is stored and referenced for each copy of the file, which enables duplication of the segment keys to be avoided. The key “K” is needed to decrypt the encrypted aggregation38, and the private key of the user44A or44B is needed to obtain the key “K” since the key “K” is encrypted.

FIG. 7Billustrates an alternative embodiment of the storage pool50after the server computer system10has stored the information received from the client computer system7A and the client computer system7B. The storage pool50again includes a segment storage area or database58in which the encrypted segments32A-32E have been stored. The storage pool50also includes a segment key storage area or database63in which the encrypted aggregation38has been stored. However, in this example the encrypted aggregation38has been stored within an object85. The reference information306in both the metadata68A and the metadata68D reference the same object85, and the object85references the same instances of the encrypted segments32A-32E. This embodiment eliminates the duplicate references to all of the encrypted segments in the metadata68A and the metadata68D, which may further aid in the de-duplication of data performed by the server computer system10. The encrypted segments are referenced only once by the object85. It is noted that in other embodiments there may be more than one level of indirection. For example, in other embodiments the object85may reference another object, which then references the encrypted segments32A-32E. Also, objects may reference each other recursively which may allow for increased levels of de-duplication and allow the storage pool50to scale well as it becomes very large.

FIG. 8is a flowchart diagram illustrating one embodiment of a method for restoring a file from the server computer system10to a client computer system7, where the file has been backed up according to the method illustrated inFIG. 6. For example, the backup client software executing on the client computer7A may perform the method to restore the file20A.

As indicated in501, the backup client software180executing on the client computer7A may communicate with the backup server software190to receive the metadata68A, the encrypted segments32A-32E, and the encrypted aggregation38from the server computer system10. The metadata68A may include the encrypted key “K”39A.

As indicated in503, the backup client software180may decrypt the encrypted key “K”39A included in the metadata68A using the private key of the user44A to produce the key “K”34.

As indicated in505, the backup client software180may decrypt the encrypted aggregation38using the key “K”34to produce the unencrypted aggregation36of the content-based segment keys30A-30E. The backup client software180may then extract the individual content-based segment keys30A-30E from the aggregation36.

As indicated in507, the backup client software180may decrypt the encrypted segments32using their respective content-based keys30to produce the original file segments22.

As indicated in509, the backup client software180may then assemble the file from the decrypted segments22, e.g., by appending the data from each segment into a single file having data identical to the original file20A.

Thus, the method enables the backup client software executing on behalf of the user44A to restore the file20A using the private key of the user44A. However, other users44or unauthorized software do not possess the private key of the user44A, and thus may not be able to restore and access the file20A. Similarly, the backup client software executing on behalf of the user44B, can restore the file20D using the private key of the user44B, but other users44and unauthorized software do not possess the private key of the user44B.

As noted above, in some embodiments the backup client software180on a given client computer system7may first communicate with the backup server software190to determine whether the encrypted segments for a file are already stored in the storage pool50before transmitting the encrypted segments to the server computer system10. In various embodiments the system may use any of various techniques to determine whether the encrypted segments are already stored in the storage pool50. In some embodiments, for each of the encrypted segments32of the file, the backup client software may perform an algorithm based on the encrypted data of the encrypted segment32in order to compute an ID or fingerprint for the encrypted segment32. The ID or fingerprint may include information useable to identify the encrypted segment32. For example, in some embodiments a hash function may be applied to the encrypted data of the encrypted segment32in order to generate a hash value used as the encrypted segment ID. In other embodiments, any of various other kinds of algorithms may be performed to generate the encrypted segment IDs. In some embodiments the algorithm that is used may have the following properties: 1) For any two encrypted segments that have identical data, the algorithm will generate the same ID for the encrypted segment. 2) For any two encrypted segments that do not have identical data, the algorithm will generate different IDs for the encrypted segment.

Thus, the backup client software180may transmit the IDs for the encrypted segments32to the server computer system10. In response, the backup server software190on the server computer system10may use the IDs to check to see whether copies of the encrypted segments32are already stored in the storage pool50. For example, each encrypted segment in the storage pool50may be stored in association with its respective ID. The backup server software may then inform the backup client software180of which of the encrypted segments32(if any) are already stored in the storage pool50.

As noted above, in some embodiments the reference information306or metadata68may indirectly specify the encrypted segments of the file through one or more levels of objects. For example, in some embodiments the server computer system10may be configured to use a hierarchy of objects to represent stored files. Representing files using a hierarchy of objects may enable de-duplication techniques to be recursively applied at each level of the hierarchy. In various embodiments there may be any number of recursive levels of de-duplication, and any of various kinds of object hierarchies may be used to represent the files.

In some embodiments the hierarchy of objects may include path objects (POs), data objects (DOs), and segment objects (SOs). Each segment object (SO) includes metadata and content, where the SO is identified by a fingerprint based solely on the content, and the metadata consists of size, checksums, etc.

Each data object (DO) includes metadata and a sequence of tuples, where each tuple specifies metadata and the fingerprint of a DO or SO. The content of the DO (data object) corresponds to the concatenated content of the DOs and SOs in the sequence, and the fingerprint of the DO can be based on the sequence or on the concatenated content.

Each PO includes metadata (path, file attributes, etc.), DO fingerprint of file content, DO fingerprint of file ACL, and DO fingerprint of additional metadata of the file. The ACL is security information associated with the file on the file system.

Thus, these objects represent a hierarchy in which a path object references one or more data objects, where each data object references one or more segment objects and/or one or more other data objects, and where each segment object directly specifies or represents a file segment.

The content of each segment object (SO) may be encrypted using a key K1derived from the content. Thus, the content of the segment object is stored in encrypted form. The use of a content-derived key to encrypt the segment content may ensure that different data objects which have segments in common will reference the same segment objects, thus achieving deduplication at the segment level.

The sequence of tuples in each data object (DO) may also be encrypted using a key K2based on the sequence itself. Thus, the sequence of tuples in each data object is also stored in encrypted form. The use of a content-derived key to encrypt the sequence may ensure that different path objects (or other data objects) can reference a single de-duplicated instance of a data object.

Thus, recursive levels of de-duplication may be achieved. For example, multiple path objects (POs) may refer to the same de-duplicated data object (DO), and multiple DOs can refer to the same de-duplicated DO and/or the same de-duplicated SO.

It is noted that information in the path object may be encrypted with the private key of the user who owns the file represented by the path object. Thus, in some embodiments, the objects (POs, DOs, SOs) at each level in the object hierarchy are encrypted, and de-duplication is also achieved at the DO and SO level.

FIG. 9illustrates an example of a client computer system7according to one embodiment. It is noted thatFIG. 9is provided as an example, and in other embodiments a client computer system7may be implemented in various other ways. In some embodiments the client computer system7may comprise a computer such as a personal computer system (PC), workstation, portable computer (e.g., laptop or notebook), personal digital assistant (PDA), television system, or other computing device or combination of devices.

The client computer system7includes one or more processors120coupled to memory122. In some embodiments, the memory122may include one or more forms of random access memory (RAM) such as dynamic RAM (DRAM) or synchronous DRAM (SDRAM). However, in other embodiments, the memory122may include any other type of memory instead or in addition.

The memory122may store program instructions and/or data. In particular, the memory122may store backup client software180, which may be executed by the processor(s)120. The backup client software180may be operable to communicate with the backup server software190executing on the server computer system10in order to backup and restore files according to the methods described herein.

It is noted that the processor120is representative of any type of processor. For example, in one embodiment, the processor120may be compatible with the x86 architecture, while in another embodiment the processor120may be compatible with the SPARC™ family of processors. Also, in some embodiments the client computer system7may include multiple processors120.

The client computer system7also includes or is coupled to one or more storage devices125. Files that are backed up from the client computer system7may originally be stored on the storage device(s)125, e.g., in a file system. In various embodiments the storage devices125may include any of various kinds of storage devices operable to store data, such as optical storage devices, hard drives, tape drives, etc. As one example, the storage devices125may be implemented as one or more hard disks configured independently or as a disk storage system.

The client computer system7may also include one or more input devices126for receiving user input from a user of the client computer system7. The input device(s)126may include any of various types of input devices, such as keyboards, keypads, microphones, or pointing devices (e.g., a mouse or trackball). The client computer system7may also include one or more output devices128for displaying output to the user. The output device(s)128may include any of various types of output devices, such as LCD screens or monitors, CRT monitors, etc.

The client computer system7may also include network connection hardware129through which the client computer system7couples to a network enabling communication with the server computer system10. The network connection129may include any type of hardware for coupling the client computer system7to a network, e.g., depending on the type of network. In various embodiments, the client computer system7may be coupled to the server computer system10via any type of network or combination of networks. For example, the network may include any type or combination of local area network (LAN), a wide area network (WAN), an Intranet, the Internet, etc. Examples of local area networks include Ethernet networks, Fiber Distributed Data Interface (FDDI) networks, and token ring networks. Also, each computer may be coupled to the network using any type of wired or wireless connection medium. For example, wired mediums may include Ethernet, fiber channel, a modem connected to plain old telephone service (POTS), etc. Wireless connection mediums may include a satellite link, a modem link through a cellular service, a wireless link such as Wi-Fi™, a wireless connection using a wireless communication protocol such as IEEE 802.11 (wireless Ethernet), Bluetooth, etc.

FIG. 10illustrates an example of the server computer system10according to one embodiment. The server computer system10includes one or more processors120coupled to memory122. In some embodiments, the memory122may include one or more forms of random access memory (RAM) such as dynamic RAM (DRAM) or synchronous DRAM (SDRAM). However, in other embodiments, the memory122may include any other type of memory instead or in addition.

The memory122may store program instructions and/or data. In particular, the memory122may store backup server software190, which may be executed by the processor(s)120. The backup server software190may be operable to communicate with the backup client software180executing on the various client computer systems7in order to backup files from the client computer systems7and restore files to the client computer systems7according to the methods described herein. For example, the backup server software190may execute to perform operations described above, such as receiving and storing a plurality of encrypted segments of a file and storing metadata for the file in the storage pool50. The backup server software190may also execute to retrieve the encrypted segments and metadata for the file from the storage pool50and return them to the backup client software180executing on a particular client computer system7, e.g., in response to a request by the backup client software180to restore the file.

The backup server computer system10also includes or is coupled to one or more storage devices125on which the storage pool50is implemented. In various embodiments the storage devices125may include any of various kinds of storage devices operable to store data, such as disk drives, optical storage devices, tape drives, etc. As one example, the storage devices125may be implemented as one or more hard disks configured independently or as a disk storage system. As another example, the storage devices125may be implemented as one or more tape drives. In some embodiments the storage devices125may operate in a storage system or library device with which the server computer system10communicates via a communication bus or network.

The backup server computer system10may also include one or more input devices126, one or more output devices128, and network connection hardware129, similarly as described above with reference to the client computer system7.

It is noted that various embodiments may further include receiving, sending or storing instructions and/or data implemented in accordance with the foregoing description upon a computer-accessible storage medium. Generally speaking, a computer-accessible storage medium may include any storage media accessible by one or more computers (or processors) during use to provide instructions and/or data to the computer(s). For example, a computer-accessible storage medium may include storage media such as magnetic or optical media, e.g., one or more disks (fixed or removable), tape, CD-ROM, DVD-ROM, CD-R, CD-RW, DVD-R, DVD-RW, etc. Storage media may further include volatile or non-volatile memory media such as RAM (e.g. synchronous dynamic RAM (SDRAM), Rambus DRAM (RDRAM), static RAM (SRAM), etc.), ROM, Flash memory, non-volatile memory (e.g. Flash memory) accessible via a peripheral interface such as the Universal Serial Bus (USB) interface, etc. In some embodiments the computer(s) may access the storage media via a communication means such as a network and/or a wireless link.