Deduplication system without reference counting
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 using or tracking reference counting values. Some embodiments described herein use a secondary table (for tracking archive file contents) and a bitmap to mark which primary records are present in the secondary table. In another embodiment, once the marking phase is completed, the deduplication system uses the marked-up bitmap to identify the corresponding records from the primary table that can be moved to another table for storing “zero-reference” data blocks. In other embodiments, the system will then traverse the “zero-reference” table and remove those primary data blocks from secondary storage devices.
1. An information management system configured to update a deduplication database, the information management system comprising:
a secondary storage subsystem comprising computer hardware configured to: identify a request to update a primary table within a deduplication database (DDB), wherein the primary table comprises a plurality of records containing information about deduplicated data blocks stored in a plurality of secondary storage devices, and
wherein, each of the plurality of records in the primary table comprises at least
a primary record identifier,
a unique signature for a corresponding data block,
and a location of the corresponding data block within one of the secondary storage devices;
retrieve one or more bitmaps associated with the deduplication database, wherein each bit in the one or more bitmaps is representative of whether the corresponding data block is referenced in a secondary table, wherein the secondary table comprises one or more job records, wherein each job record includes at least one or more job identifiers and at least one or more data block identifiers, and at least one or more primary record identifiers associated with the one or more job identifiers;
access a first primary record in the primary table;
access a first bit in in the one or more bitmaps, wherein the first bit in the one or more bitmaps corresponds to the first primary record;
determine that the first bit indicates that the first primary record is not referenced in the secondary table; and
move the first primary record from the primary table to a zero-reference table, wherein the zero-reference table comprises of primary records of data blocks that may be removed from secondary storage devices.
2. The information management system of claim 1 , wherein the secondary storage subsystem is further configured to:
retrieve the zero-reference table;
determine location of a secondary storage device where a first zero-reference data block associated with the first primary record in the zero-reference table is stored; and
remove from the secondary storage device, the first zero-reference data block.
3. The information management system of claim 1 , wherein each primary record in the zero-reference table further includes a job identification associated with the request to update the primary table.
4. The information management system of claim 1 , wherein the deduplication database is a database partition.
5. The information management system of claim 1 , wherein the first bit is not set.
6. The information management system of claim 1 , wherein the secondary storage subsystem is further configured to traverse all records in the primary table.
7. The information management system of claim 1 , wherein the request to update the primary table is initiated by a media agent implemented on same computing device where the deduplication database is stored.
8. The information management system of claim 1 , wherein the request to update the primary table is performed as part of a pruning operation.
9. The information management system of claim 1 , wherein the one or more bitmaps are stored in memory of a DDB media agent where the deduplication database is stored at.
10. An information management system configured to update a deduplication database, the information management system comprising:
a secondary storage subsystem comprising computer hardware configured to: identify a request to update a primary table within a deduplication database (DDB), wherein the primary table comprises a plurality of records containing information about deduplicated data blocks stored in a plurality of secondary storage devices, and
wherein, each of the plurality of records in the primary table comprises at least
a primary record identifier,
a unique signature for a corresponding data block, and
a location of the corresponding data block within one of the secondary storage devices;
retrieve one or more bitmaps associated with the deduplication database, wherein each bit in the one or more bitmaps is representative of whether the corresponding data block is referenced in a secondary table, wherein the secondary table comprises one or more job records, wherein each job record includes at least one or more job identifiers and at least one or more data block identifiers, and at least one or more primary record identifiers associated with the one or more job identifiers;
traverse at least one of the one or more bitmaps to locate a first value indicating that a corresponding primary record in the primary table can be removed from the primary table;
access the primary table; and
move the corresponding primary record from the primary table to a zero-reference table, wherein the zero-reference table comprises of primary records of data blocks that may be removed from secondary storage devices.
11. A computer-implemented method for updating a deduplication database, the method comprising:
identifying a request to update a primary table within a deduplication database (DDB), wherein the primary table comprises a plurality of records containing information about deduplicated data blocks stored in a plurality of secondary storage devices, and
wherein, each of the plurality of records in the primary table comprises
at least a primary record identifier,
a unique signature for a corresponding data block, and
a location of the corresponding data block within one of the secondary storage devices;
retrieving one or more bitmaps associated with the deduplication database, wherein each bit in the one or more bitmaps is representative of whether the corresponding data block is referenced in a secondary table, wherein the secondary table comprises one or more job records, wherein each job record includes at least one or more job identifiers and at least one or more data block identifiers, and at least one or more primary record identifiers associated with the one or more job identifiers;
accessing a first primary record in the primary table;
accessing a first bit in in the one or more bitmaps, wherein the first bit in the one or more bitmaps corresponds to the first primary record;
determining that the first bit indicates that the first primary record is not referenced in the secondary table; and
moving the first primary record from the primary table to a zero-reference table, wherein the zero-reference table comprises of primary records of data blocks that may be removed from secondary storage devices.
12. The method of claim 11 , the method further comprising:
retrieving the zero-reference table;
determining a location of a secondary storage device where a first zero-reference data block associated with the first primary record in the zero-reference table is stored; and
removing from the secondary storage device, the first zero-reference data block.
13. The method of claim 11 , wherein each primary record in the zero-reference table further includes a job identification associated with the request to update the primary table.
14. The method of claim 11 , wherein the deduplication database is a database partition.
15. The method of claim 11 , wherein the first bit is not set.
16. The method of claim 11 , the method further comprising traversing all records in the primary table.
17. The method of claim 11 , wherein the request to update the primary table is initiated by a media agent implemented on same computing device where the deduplication database is stored.
18. The method of claim 11 , wherein the request to update the primary table is performed as part of a pruning operation.
19. The method of claim 11 , wherein the one or more bitmaps are stored in memory of a DDB media agent where the deduplication database is stored at.
20. The method of claim 11 , wherein the deduplicated data blocks referenced in the DDB are stored in multiple single instance files (SFiles).