Any and all applications, if any, for which a foreign or domestic priority claim is identified in the Application Data Sheet of the present application are hereby incorporated by reference in their entireties under 37 CFR 1.57.

COPYRIGHT NOTICE

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document and/or the patent disclosure as it appears in the United States Patent and Trademark Office patent file and/or records, but otherwise reserves all copyrights whatsoever.

BACKGROUND

Businesses recognize the commercial value of their data and seek reliable, cost-effective ways to protect the information stored on their computer networks while minimizing impact on productivity. A company might back up critical computing systems such as databases, file servers, web servers, virtual machines, and so on as part of a daily, weekly, or monthly maintenance schedule. The company may similarly protect computing systems used by its employees, such as those used by an accounting department, marketing department, engineering department, and so forth. Given the rapidly expanding volume of data under management, companies also continue to seek innovative techniques for managing data growth, for example by migrating data to lower-cost storage over time, reducing redundant data, pruning lower priority data, etc. Enterprises also increasingly view their stored data as a valuable asset and look for solutions that leverage their data. For instance, data analysis capabilities, information management, improved data presentation and access features, and the like, are in increasing demand.

In response to these challenges, one technique developed by storage system providers is data deduplication. Deduplication typically involves eliminating or reducing the amount of redundant data stored and communicated within a storage system, improving storage utilization. For example, data can be divided into units of a chosen granularity (e.g., files or data blocks). As new data enters the system, the data units can be checked to see if they already exist in the storage system. If the data unit already exists, instead of storing and/or communicating a duplicate copy, the storage system stores and/or communicates a reference to the existing data unit.

As the volume of data blocks in secondary storage expands rapidly, so do the costs associated with storing, maintaining, and accessing that data on secondary storage devices. Enterprises are looking for enhancements in scalability and performance in the deduplication processes. A deduplication database typically performs large amount of I/O operations. Reducing the I/O operations greatly improves scale and performance of the overall system.

Current deduplication databases use reference counting mechanisms for tracking the number of references that exist in primary storage to the deduplicated data blocks stored in secondary storage. For each data block that checks into the deduplication database, the corresponding entry in the deduplication database (that tracks the signatures and locations of the deduplicated blocks) is updated with a new reference count. This creates a substantial number of I/O operations which slow the deduplication processes down significantly. A new approach described herein involves eliminating the tracking of reference counts from the deduplication database. Without needing to update the deduplication database in every instance that a duplicated data block “checks in” or pruned, the I/O operations performed on the deduplication database and engine are significantly decreased. The techniques described herein provide a solution which does not use a reference count in the deduplication database and thereby improves the efficiency of back up operations.

A deduplicated storage system is provided according to certain embodiments that uses one or more mechanisms to remove records that have been or will be erased from the secondary copies without the use of reference counting mechanisms.

SUMMARY

Deduplication can improve storage utilization, system traffic (e.g., over a networked storage system), or both. Deduplication techniques designed to reduce the demands on storage systems during storage operations such as backup and/or replication operations can be found in the following U.S. patent applications, each of which is incorporated by reference in its entirety. One or more embodiments of the present disclosure may be used with systems and methods disclosed therein:U.S. Patent Application Publication No. 2014/0201171, entitled “High Availability Distributed Deduplicated Storage System,” filed Jan. 10, 2014;U.S. Pat. No. 8,578,109, entitled “Systems and Methods for Retaining and Using Block Signatures in Data Protection Operations,” filed Dec. 30, 2010;U.S. Pat. No. 8,732,133, entitled “Extensible Data Deduplication System and Method,” filed Mar. 16, 2010; andU.S. Pat. No. 9,753,955, entitled “Fast Deduplication Data Verification,” filed Sep. 16, 2014.

The deduplication database may include a primary table and a secondary table. The primary table may include a record for each unique data block stored in a storage pool. The secondary table may identify a list of backup job identifiers and signatures associated with each backup job identifier. The deduplicated storage system may provide the deduplication database with the backup job identifier associated with a time that the backup job occurred. The deduplication database may use the backup job identifier to identify backup job identifiers listed in the secondary table that are associated with a backup job that occurred after the backup job associated with the provided backup job identifier.

While some deduplication databases may use reference counting mechanisms for tracking the number that each deduplicated data blocks is referenced in a backup, the approach described herein eliminates the need to use reference counts in a deduplication database.

However, by not tracking reference counts in the deduplication database, pruning entries from the primary table when a corresponding data blocks is removed/aged from secondary storage may become challenging. A deduplicated storage system is provided according to certain embodiments that uses one or more mechanisms to update the deduplication database and remove records corresponding to data blocks that have been or will be erased from the secondary copies, without keeping track of the number of references that exist to that data block. Some embodiments described herein use a secondary table (for tracking archive file contents) and a bitmap for marking which primary records of the primary table are present in the secondary table.

During a pruning operation, a secondary table may be used to evaluate whether the primary table includes any de-referenced data blocks (i.e., data blocks without any references in any backup files). To reduce I/O operations during this process, a bitmap may be used to mark whether each record in the primary table has been de-referenced. For example, when a data block is de-referenced its primary identifier will no longer be listed in any of the entries of the secondary table. In an embodiment, each primary identifier in the primary table is queried in the secondary table. If the primary identifier is present in the secondary table, the corresponding bit in the bitmap is modified to reflect that. In another embodiment, once the marking of the bitmap (“the marking phase”) is completed, the deduplication system will traverse the primary table and use the bitmap to identify the corresponding records from the primary table that may be moved to a “zero-reference” table. In other embodiments, the system will then traverse the “zero-reference” table and remove the corresponding primary data blocks from secondary storage devices.

