GARBAGE COLLECTION SYSTEM AND PROCESS
A garbage collection process for a data deduplication storage system is disclosed. In one implementation, a method is disclosed to perform garbage collection that works effectively across a scale-out cluster and across very large amounts of data. The method includes compacting data in an object store in the scale-out cluster by examining data in a reference map of data blocks in the object store to determine which of the locations within a back-end object in an object store are referenced, and which locations are no longer referenced by a process. The back-end object in an Object Store are altered to remove block data from locations which are no longer referenced, and a hash-to-location table is updated to remove the entries for the removed block data.
1 . A method to perform garbage collection to compact data in a memory of one or more multiple network capable servers comprising:
storing one or more backend objects in an object store;
creating data in a reference map of the of the object store to indicate which locations within the one or more back-end objects in the object store are currently referenced by an object-key-to-location table, and which locations within the one or more back-end objects are no longer referenced;
altering the one or more back-end objects in the object store to remove block data from the locations within the one or more back-end objects which are no longer referenced; and
updating a hash-to-location table to remove entries in the table corresponding to block data that have been removed.
2 . The method as recited in claim 1 , further comprising referencing the locations within the back-end object in the object store using the hash-to location table.
3 . The method as recited in claim 1 , further comprising identifying which locations within the back-end object in an object store are currently referenced, and which locations are no longer referenced by running a trace process that determines which locations within the back-end object contain data that is still currently referenced.
4 . The method as recited in claim 3 wherein the trace process includes:
creating a partial reference map for each block shard, to record the references found;
iterating within each key shard through the object-key-to-location table for objects managed by the key shard and recording a reference in the partial reference map for each block location that appears in the object-key-to-location table; and
sending the partial reference map to a corresponding block shard server.
5 . The method as recited in claim 1 , further comprising:
deleting the reference map after it has been used to update the hash-to-location table to remove all entries in the table that correspond to block data that have been removed from the object store.
6 . The method as recited in claim 4 further comprising,
collecting with the block shard server the reference maps from every key shard, and
removing with the block shard server blocks that are no longer referenced.
7 . A system to perform garbage collection to compact data, the system comprising:
an object store storing a backend object;
one or more multiple network capable servers including a memory;
a reference map created in the memory to indicate which locations within a back-end object stored in the object store are currently referenced, and which locations within the back-end object stored in the object store are no longer referenced;
circuitry to alter the back-end object stored in the object store to remove block data from the locations within the back-end object stored in the object store which are no longer referenced; and
circuitry to remove entries within a hash-to-location table identifying locations of block data within the back-end object that have been removed.
8 . The system as recited in claim 7 , further comprising:
circuitry to delete the reference map after removal of all entries in the hash-to-location table corresponding to block data that have been removed.
9 . The system as recited in claim 7 , further comprising:
circuitry to run a trace process that identifies which locations within the back-end object contain data that is still currently referenced, and which locations are no longer referenced.
10 . The system as recited in claim 9 , wherein the circuitry to run the trace process includes:
circuitry to create a partial reference map for each block shard, to record the references found;
circuitry to iterate with a key shard through the object-key-to-location table for objects managed by the key shard and recording a reference in the partial reference map for each block location that appears in the object-key-to-location table; and
circuitry to send the partial reference map to a corresponding block shard server.
11 . An apparatus, comprising:
at least one non-transitory medium for execution by a processor in a server, the at least one non-transitory medium includes at least:
one or more instructions for creating data in a reference map of the memory to indicate which locations within a back-end object in an object store are currently referenced, and which locations are no longer referenced;
one or more instructions for altering the back-end object in the object store to remove block data from the locations which are no longer referenced; and
one or more instructions for updating a hash-to-location table identifying locations of block data within the back-end object to remove entries in the table identifying locations of block data that have been removed.
12 . The apparatus as recited in claim 11 , wherein the at least one non-transitory medium includes at least:
instructions for referencing the locations within the back-end object in the object store using the hash-to location table.
13 . The apparatus as recited in claim 12 , wherein the at least one non-transitory medium includes at least:
instructions for identifying which locations within the back-end object in an object store are currently referenced, and which locations are no longer referenced by running trace process instructions to determine which locations within the back-end object contain data that is still currently referenced.
14 . The apparatus as recited in claim 12 , wherein the trace process instructions includes:
instructions for creating a partial reference map for each block shard, to record the references found;
instructions for iterating with a key shard through the object-key-to-location table for objects managed by the key shard and recording a reference in the partial reference map for each block location that appears in the object-key-to-location table; and
instructions for sending the partial reference map to a corresponding block shard server.
15 . The apparatus as recited in claim 11 , wherein the at least one non-transitory medium includes at least:
instructions for deleting the reference map in response to updating the hash-to-location table to remove all entries in the table corresponding to block data that have been removed.