the present invention is a system and method for performing deduplication on previously archived backup images such that a file system may be deduplicated even after its data objects have been backed up or written to media . using the present invention , previously archived backup images may be streamlined to remove multiple instances of backed up files . as a result , backup images may be reduced in size , reducing the amount of space taken up by large amounts of archive media needed . leftover archive media that have been purged of data redundancies may be recycled or re - used for future backups . the present invention may deduplicate any backup image , without regard to the format or manner of the backup image &# 39 ; s creation . a person having ordinary skill in the art will appreciate that the terms “ backup ” and “ archive ” refer to two complementary storage concepts . in some contexts , backup refers to scheduled , automated , incremental short - term data object storage , whereas archive refers to manual , long - term data object storage . as a result , backup files and archive files may be distinguishable by their metadata , header information , or file extensions . however , as used herein , backup and archive are interchangeable since the present invention is able to perform deduplication on either backup files or archive files . the alternate use of the terms “ backup ” or “ archive ” is not meant to limit the invention in any way . a person skilled in the art will appreciate that there are many software applications , commands or methods to backup or archive data , such as dump , tar , open tape format , scsi , ndmp , pax , vbb , cpio , etc . each method has a different format and schema . additionally , each software application that performs or manages the backup session may originate from a different vendor . as a result , there may be vendor - specific formats for each of the different backup methods . because an organization may use a number of different backup or archive utilities from different vendors , or may use a single backup utility to perform different backup , it is not uncommon for the organization to store legacy backup images in different formats and / or created by different backup software . it should be appreciated that the present invention can be implemented in numerous ways , including as a process , an apparatus , a system , a device , a method , or a computer readable medium such as a computer readable storage medium comprising computer program instructions , a software module containing computer program instructions or a computer network wherein computer program instructions are sent over optical or electronic communication links . applications may take the form of software executing on a general purpose computer or be hardwired or hard coded in hardware . in this specification , these implementations , or any other form that the invention may take , may be referred to as techniques . in general , the order of the steps of disclosed processes may be altered within the scope of the invention . in this disclosure , the system components of the present invention are discussed first , followed by a description of the methods performed by the system components , according to an embodiment of the present invention . one will appreciate that the examples below are merely illustrative , and are not meant to limit the scope of the invention in any way . fig1 illustrates various hardware and software modules that may make up the present invention . the various methods performed by these modules are discussed further below . as shown , 101 is a backup image . one having ordinary skill in the art will appreciate that a backup image is a collection of all of the data objects backed up from a file system , and may include the complete contents ( data and system files ) of an entire drive , disk or file system , or may contain selected data objects from the file system . after a utility performs a backup or archive , the end result of an individual backup session is a backup image . in fig1 , backup image 101 is comprised of a plurality of data objects , including data files , system files , and file directories . each data object 105 may be associated with metadata 103 , which may form part of a header file for the data object 105 or may be encoded into a header block for data object 105 . the metadata 103 may contain information about the data object 105 , identifying the type of data object it is , the data it may contain , the format of that data , whether the data object is linked to any related data objects , or other information about the data object . the metadata 103 associated with the data object 105 may contain information identifying the format or method used to backup data object 105 . apart from or in addition to the metadata 103 for each data object 105 , backup image 101 may itself have metadata that identifies its format or method of creation . in addition , metadata for either the data objects or the backup image may also help differentiate which part of the backup image 101 is actual data content , and which part is merely information about that data . the present invention includes an “ image adapter ” or “ image decoder .” this image adapter 131 may be used to read or “ decode ” backup image 101 . as used herein , “ decode ” means differentiating which part of the backup image 101 or data object 105 is actual data , and which part is merely metadata 103 or merely information about that data . decoding also determines the format of the backed up data , as well as the original path information for the data as it originally existed on the file system before backup . the decoding process will be discussed in further detail below . as depicted in fig1 , in an embodiment , the present invention provides a bridge between the backup image 101 and a deduplication engine 151 through the use of the image adapter 131 . the deduplication engine 151 is software or hardware responsible for accepting streams of data from image adapter 131 and identifying multiple instances of data objects from that stream of data . the deduplication engine 151 will only permit a single instance of a data object for storage . as such , deduplication engine 151 may be associated with either disk storage 171 or tape storage 191 . after backup image 101 has been passed through the image adapter 131 and the deduplication engine 151 , the resulting deduplicated image stored on tape 191 or disk 171 will be much smaller , since multiple instances of files 105 will have been removed . image adapter 131 may be connected to or associated with a catalog 141 , which is a database or associative data array that stores information generated by the image adapter 131 and / or the deduplication engine 151 . in an embodiment , the catalog 141 may also be associated with or may accept information from the deduplication engine 151 . this information is separate from the backup files stored on tape 191 or disk 171 , but may be additional metadata about these backed up files . for example , after a backup image 101 has been decoded by the image adapter 131 , the data objects 105 may be streamed to the deduplication engine 151 , but the metadata 103 associated with those data files 105 may be kept separate . the metadata 103 may contain information about the original file system that was backed up and stored as backup image 101 . other information generated by the image adapter 131 or the deduplication engine 151 may be hash values for identifying the streamed data objects 105 . all of these various types of information , metadata or other data may be stored in catalog 141 . as will be discussed further below , the information stored in catalog 141 may be useful when data objects are recovered from disk 171 or tape 191 . a person having ordinary skill in the art will appreciate that fig1 is merely exemplary , and not meant to be limiting in any way . for example , in an embodiment , each of the software modules depicted in fig1 may be implemented by a hardware device . in an embodiment , image adapter 131 and deduplication engine 151 may be contained in a single software application or hardware device . also , in an embodiment , the reference 101 may be a backup tape repository having multiple backup images , rather than a single backup image as was discussed previously . in such a case , if reference 101 is a tape repository , then it may contain backup image 105 that is associated with its own metadata 103 . in other words , the present invention contemplates multiple backup images written to media with a single metadata file for the entire collection of backup images , or multiple backup images written to media with metadata files for each of the data objects contained in the multiple backup images . other variations are possible to illustrate the scalability and extensibility of the present invention . the method performed by the image adapter 131 is now described , according to an embodiment of the present invention . a person having ordinary skill in the art will appreciate that there are many ways that the image adapter 131 can perform its task of decoding backup images for the deduplication engine 151 . as noted previously , the image adapter 131 decodes backup images to identify the format of the backup image 101 , as well as which part of the data objects 105 that comprise backup image 101 is actual data content , and which part is metadata 103 for that data content . each data object 105 may be associated with metadata 103 that contains information about the data object , such as file permissions , file stat ( creation , modification , etc . ), and / or inode or other file identifier (“ fid ”) information , etc . the metadata may reveal how the data object 105 was compressed or converted to form part of the backup image 101 , the other related data objects that comprise the backup image 101 , and / or the backup utility used to create the backup image 101 . alternatively , the backup image itself may contain metadata that reveals this type of information . as such , decoding may involve reading the metadata for the backup image 101 , reading the metadata 103 for each of the data objects 105 , and / or reading a stream of the data objects 105 and metadata 103 . the image adapter 131 is designed to read both the metadata 103 for the data objects 105 contained in backup image 101 as well as the metadata specifically for the backup image 101 to determine the format of the backup image . in some cases , neither metadata 103 nor the backup image &# 39 ; s metadata may reveal this information , or the image adapter 131 may be encountering a new backup format . in this circumstance , a system administrator may tell the image adapter 131 the format of the backup image . this may occur whenever the image adapter 131 fails to identify the format of the backup image . in an embodiment , the image adapter 131 may be updated remotely or directly with new backup image format information so that image adapter 131 may automatically recognize backup image formats without system administrator intervention . one will appreciate that once the image adapter 131 “ learns ” to recognize the format of a certain type of backup image , the image adapter 131 may automatically recognize this format the next time it encounters the same format of backup image . for example , one skilled in the art will appreciate that a backup image may be preceded by a header file or a header block that contains metadata with information on the data objects included in the archive . the backup image may also have a file extension that identifies its file type , as well as the utility or command used to create the backup image . either the header file metadata or the file extension may be useful in determining which part of the archive file should be streamed to the deduplication engine 151 . the following examples illustrate some of the methods that may be performed by the image adapter 131 in order to prepare data objects from a backup image for streaming to the deduplication engine 151 . the image adapter 131 may decode a backup image 101 by identifying the backup image 101 &# 39 ; s file type . the file type may be recognized by reading the file extension for a file , in this case the backup image 101 . for example , the backup image 101 may be created using “ cpio .” one having skill in the art will appreciate that “ cpio ” is a type of binary file format and one of many ways to archive or backup data objects . “ cpio ” also refers to the software utility used to create a cpio file or backup image . a backup image created using a cpio utility or other equivalent cpio tool may have a “. cpio ” file extension . the cpio utility may be used to create a cpio backup image out of stream of data objects , and may also be used to extract files from a cpio backup image to partially or completely recover an archived file system . one skilled in the art will recognize that a cpio backup image may also be referred to as a cpio archive file or simply , as a cpio file . the image adapter 131 aspect of the present invention provides some of the functionality of a cpio tool in addition to the other features described . in an embodiment , a cpio backup image may be streamed to the image adapter 131 . the image adapter 131 reads the cpio backup image , and automatically determines that this image was created using the cpio utility . the image adapter 131 may be instructed to recognize the “. cpio ” file extension . once it has identified that this backup image was created using the cpio utility , it can extract the data content and send it to the deduplication engine 151 . therefore , it is a feature of the present invention to provide for automatic recognition of certain archive file or backup image types based upon the file extension of these archive files . once the image adapter 131 identifies the file type of the archive file or backup image , it may automatically extract the data files stored in the archive file or backup image and stream it to the deduplication engine 151 . the use of a file extension to recognize the format of a backup image 101 or the format of the data objects 105 that comprise the backup image 101 is one way the image adapter 131 may decode the backup image 101 . one will appreciate that while a file extension may identify file format , the image adapter 131 may not uncover any vendor - specific format characteristics for a backup image . as such , the image adapter 131 may perform other methods in order to fully decode a backup image 101 for streaming data objects to the deduplication 151 . in circumstances where the format of a backup image may not be revealed by referring to its file extension , it may be more practical for the image adapter 131 to read the metadata for backup image 101 , or the metadata 103 contained in header files for each data object 105 that comprise backup image 101 . in most cases , every backup or archive utility used to create backup image 101 will also associate metadata with each data object that comprises the archive file . this metadata 103 is typically written to a header block for each data object 105 , and may include not only the identifying information for the associated data object , but may also reveal the format used to backup the data object 105 . one skilled in the art will appreciate that while some backup images may include a file extension that reveals backup image format ( as discussed above ), it may be more convenient to refer to the backup image metadata or data object metadata 103 for this information . for example , while a cpio backup image may have the “. cpio ” file extension , the metadata for that backup image will also reveal that it was created using the cpio utility . “ tar ” is another common format and software utility used to create backup images . when tar is used , it creates a collection of data objects to form a single tar file , also known as a tar archive , tape archive or tar backup image . the data object content is unaltered , but each data object may be associated with a header block containing metadata that details the data object name , path address , owner name , size , last modification time , format and other information for the data object . the header block for data objects in a tar file is typically written in ascii format , which may be read by the image decoder 131 . therefore , in an example where the backup image 101 is a tar file comprised of data objects 105 and metadata 103 associated with each data object 105 , the image adapter 131 may read the metadata 103 for each data object 105 , extract each data object 105 , then stream the data object 105 to the deduplication engine 151 . without the image adapter 131 , the deduplication engine 151 is unable to read the backup image 101 and extract the data objects 105 . further , without the deduplication engine 151 , the present invention is unable to deduplicate backup image 101 , and identify which data objects 105 in backup image 101 are multiple instances . one will appreciate that while backup utilities such as tar and cpio may be used to create tar files and cpio files respectively , other backup utilities are also capable of creating tar and cpio files . as such , it is important to recognize the file format of a backup image 101 no matter what software utility was used to create the backup image 101 . for example , “ pax ” is a utility used to backup data objects which provides similar , if not all of the functionality provided by the tar and cpio archive utilities . the pax utility may save archive files or backup images in a number of different formats , including tar , cpio , or ustar . therefore , while the file extension may reveal the format of a backup image , it may be more useful for the image adapter 131 to read the backup image 101 &# 39 ; s metadata or data object 105 &# 39 ; s metadata 103 to determine whether another utility has added additional format attributes . the pax utility archives files as component files , and directories may be archived as component directories . the archive file , or backup image , is therefore comprised of these component files and component directories . similar to the tar format , the component files and component directories may each be associated with metadata or header information . this information may detail the file or directory name , type , size , path information or other extended attributes for the backed up file . when a image adapter 131 encounters a backup image created using the pax utility , it will differentiate header information metadata from the actual data , and will stream the actual data to the deduplication engine 151 . as such , the image adapter 131 may decode various backup image formats . another common file utility used to perform file system backup is “ dump .” one skilled in the art will appreciate that “ dump ” differs from tar or cpio in that it is mode based and organizes backed up data object such that directories precede files . despite these differences , the image adapter 131 is capable of reading the metadata for the backup image 101 or the metadata 103 for the backed up data objects 105 contained in backup image 101 to determine if backup image 101 was created using the dump utility . a backup image 101 created using the dump utility may contain one or two bitmaps describing which modes were in use when the dump utility was performing a backup , as well as which modes were written to the backup media . in addition , each backed up data object 105 in backup image 101 may include metadata 103 stored as header information . this header information may include the file type , size , permissions , group , owner and other information for the backed up data object 105 . either the bitmap metadata for the backup image or the header information metadata 103 for each data object 105 may be read by the image adapter 131 to determine which data should be streamed to the deduplication engine 151 for deduplication . once the image adapter 131 identifies that the backup image 101 was created using the dump utility , the image adapter 131 will be able to read the metadata 103 for each backed up data object 105 , then stream the data content from each data object 105 to the deduplication engine 151 for single instance storage . as the above examples show , the image adapter 131 is capable of receiving and identifying any number of different backup image formats , either by decoding the metadata 103 contained in header information for each data object 105 that forms part of the backup image 101 , the metadata for the backup image 101 itself , or the file extension for the backup image 101 . using the image adapter 131 , backup images may be placed in a form that can be read by the deduplication engine 151 . the deduplication engine 151 provides the function of reducing space on archive media by storing only single instances of each data object . however , without the decoding function provided by the image adapter 131 , the deduplication engine 151 would be unable to read the backup image , because it is unable to distinguish between data content and metadata and it is not equipped to handle different backup image formats . once the image adapter 131 has determined the format of the backup image 101 and / or the data objects 105 that comprise the backup image 101 , the deduplication engine 151 may perform its function of detecting multiple instances of data . one skilled in the art will appreciate that the deduplication engine 151 may receive the data content of the data object 105 without any metadata 103 for that data object 105 , before performing the deduplication . there are many methods for determining whether there are multiple instances of data . for example , u . s . pat . nos . 6 , 704 , 720 and 6 , 810 , 398 , which are incorporated in full herein , disclose methods that may be performed by the deduplication engine 131 . specifically , an embodiment of the present invention provides that the deduplication engine 151 receives data streamed from the image adapter 131 , and analyzes the data for multiple instances before storing a single instance of each data object in associated disk storage 171 or tape storage 191 . deduplication may be performed through the use of hash functions and hash ids . by assigning hash ids to the data objects streamed from the image adapter 131 , the deduplication engine 151 is able to identify whether a data object has been streamed and stored before . in an embodiment , the image adapter 131 may assign hash ids to data objects prior to transmission to the deduplication engine 151 . a person having ordinary skill in the art will recognize that in a general fashion , deduplication may involve associating two different hash ids : a composite hash id , and an atomic hash id . this provides at least two ways to check for multiple instances for a data object . a composite hash id may be assigned to an entire data object . in most storage systems , data objects are divided up into even - sized “ chunks ” or blocks of data . for example , a data block may be 128 bytes in size , and a data object may occupy or take up multiple data blocks on a storage medium . in deduplication , a data block may also be assigned a hash id , known as an atomic hash id . an atomic hash id is more granular than a composite hash id , which , as previously mentioned , is assigned to the entire data object . during deduplication , the deduplication engine 151 will assign a composite hash id to the data object streamed from the image adapter 131 , and will also assign an atomic hash id for each data block streamed from the image adapter 131 . the deduplication engine 151 knows to only assign a composite or atomic hash id once . if a second instance of a data object is streamed to the deduplication engine 151 , the deduplication engine 151 will try to assign the same hash id to that data object . if this happens , the deduplication engine 151 will realize that this composite hash id has already been assigned , and that therefore , the data object is a second instance of a data object already stored . similarly , if certain data content has already been assigned a hash id , such as an atomic hash id for specific data content in a data block , the deduplication engine 151 will recognize if certain content has already been stored . assigning and comparing composite and atomic hash ids to data objects and data blocks streamed from the image adapter 131 provides one method of deduplication for the present invention . one skilled in the art will appreciate that other methods are possible as well without departing from the scope of the present invention . an important purpose of backup and archival of data is the ability to restore this data in the event of a disaster . this is known as restoration or recovery . aspects of the present invention permit restoration of data objects stored by the deduplication engine 151 . restoration may require use of the catalog 141 associated with the image adapter 131 . as noted previously , the catalog 141 is a database of information generated by the image adapter 131 and / or the deduplication engine 151 . for example , during decoding , the image adapter 131 may extract the metadata 103 associated with a data object 105 from the backup image 101 . this metadata 103 will contain the original path information for the data object 105 . in other words , the metadata 103 will identify exactly where on the file system data object 105 was located before it was backed up to backup image 101 . since only the data object 105 is streamed to the deduplication engine 151 , if this path information metadata is not retained , then the backup and recovery application may not be able to re - create the backed up file system . as such , it is important to store this information in a database such as catalog 141 . in an embodiment , the information stored in catalog 141 may be limited to only the information necessary to perform a restore , and as such , additional metadata not necessary for restoration may be left out of the catalog 141 database in order to keep its memory footprint small . one will also appreciate that once the data object 105 is streamed to the deduplication engine 151 , it may be stored as a single instance in either disk 171 or tape 191 . if the backup image 101 , and therefore the original file system , contained multiple instances of a data object , the location and / or number of these instances may be lost . the only information generated by the deduplication engine 151 is the composite and atomic hash ids for those data objects . in order to keep track of the number of instances of a backed up data object 105 that existed in the backup image 101 or the original file system , it is important that the hash ids and number of instances is stored with the other metadata for those data objects . as such , the catalog 141 will contain hash id information and path or other mapping information for each of the data objects deduplicated by the deduplication engine 151 and stored by the deduplication engine 151 . restoration may therefore be performed using the hash id and path information for the deduplicated data objects . if a file system needs to be restored , the recovery application may refer to the database in catalog 141 to identify not only the structure and location of each backed up data object , but also where multiple instances of certain data objects were located . as such , the present invention not only provides deduplication features to previously archived backup images , but also enables restoration of those backup images without any loss of data or file system structure . as a further benefit , because archived backup images have been deduplicated using the present invention , restoration may be made more efficient , since only a single instance of a data object is stored , reducing the number of archive media to recover . since the quantity of archive media is reduced , it may require less time to navigate and recover the backed up file system . a person having ordinary skill in the art will appreciate that there may be other benefits of the present invention as well . for example , the present invention may also increase backup and deduplication efficiency by providing “ synthetic full ” or “ consolidated backup ” functionality . a person having ordinary skill in the art will appreciate that a synthetic full backup is a type of backup whereby the backup server combines the most recent full backup and associated series of incremental backups to generate a backup image that is no different than if a full backup had been performed . if an organization already performs periodic full backups , with incremental backups in - between each full backup , it may be advantageous to combine the incremental backups with the previous full backup , rather than perform a full backup . synthetic full backups may be less time consuming than a full backup , but may retain all of the data that would have been stored in a full backup session . the present invention enables the image adapter 131 in conjunction with the deduplication engine 151 to perform synthetic full backups . as a result , the backup system benefits from a more efficient process than full backup , as well as the decreased use of memory resources from the deduplication process . in an embodiment , the image adapter may be able to calculate whether or not a backup image is from an incremental backup or a full backup by reading the time when a image was created , as well as the size of the image . once the image adapter 131 has identified which backup image resulted from an incremental backup , and which one resulted from a full backup , the image adapter 131 may organize the backup images temporally so that only the latest versions of the data objects that comprise the backup image are streamed to the deduplication engine . in this fashion , while the original archive media may contain both full and incremental backup images , the image adapter 131 may perform consolidation operations such that only a synthetic full backup image is deduplicated by the deduplication engine 151 . as a result , if a full backup image is missing from an archive , or was never created , the present invention can create a synthetic full backup image , while still providing deduplication on the archived files . in an embodiment , the image adapter 131 may also be able to identify which full backup images and which incremental backup images have already been streamed to the deduplication engine 151 for deduplication . rather than store both the full and incremental backup images in disk 171 or tape 191 , the image adapter 131 may create a synthetic full backup image from these previous backup images , thereby streamlining archive media even after the backup images have been deduplicated by the present invention . one will appreciate that in the description above and throughout , numerous specific details are set forth in order to provide a thorough understanding of the present invention . it will be evident , however , to one of ordinary skill in the art , that the present invention may be practiced without these specific details . in other instances , well - known structures and devices are shown in block diagram form to facilitate explanation . the description of the preferred embodiments is not intended to limit the scope of the claims appended hereto .