System and method for improved garbage collection operations in a deduplicated store by tracking temporal relationships among copies
View Patent ↗Systems and methods are disclosed for performing garbage collection to identify content segments no longer referenced in a deduplicating storage system in which redundant mark operations in a mark-and-sweep technique are avoided. An organized arrangement of hash structures is created for each data object, wherein each structure includes a hash signature for a corresponding content segment and is associated with a reference to the corresponding content segment, and the logical organization of the arrangement represents the logical organization of the content segments as they are represented within the data object. Additionally, for each data object, temporal states are maintained over time. Garbage collection iterates over the temporal structures and, for each temporal structure, marks the garbage collection state for the associated content segments for only the content segments that have changed relative to an immediately prior temporal state of the data object.
1. A method of performing garbage collection to identify content segments no longer referenced in a deduplicating storage system in which redundant mark operations in a mark-and-sweep technique are avoided, the method comprising:
organizing unique content of each data object as a plurality of content segments in the deduplicating storage system;
for each data object, creating an organized arrangement of hash structures, wherein each structure, for a subset of the hash structures, includes a hash signature for a corresponding content segment and is associated with a reference to the corresponding content segment, wherein the logical organization of the arrangement represents the logical organization of the content segments as they are represented within the data object, and wherein another subset of the hash structures includes a hierarchy of hash signatures of said hash signatures for corresponding content segments so that the organized arrangement may be traversed to determine if content is represented by said organized arrangement of hash structures;
for each data object, maintaining an organized arrangement of temporal structures to represent a corresponding data object over time, wherein each structure is associated with a temporal state of the data object and wherein the logical arrangement of structures is indicative of the changing temporal states of the data object, and wherein each temporal state is associated with the hash structures representing the content of the data object that has changed relative to an immediately prior temporal state of the data object;
in response to a garbage collection operation, for each content segment in the deduplicating storage system, clearing its corresponding garbage collection state;
in response to the garbage collection operation, iterating over the temporal structures and, for each temporal structure, marking the garbage collection state for the associated content segments for only the content segments that have changed relative to an immediately prior temporal state of the data object; and
after the iteration step on those content segments, returning any content segments to a free pool of storage that has a cleared garbage collection state.
2. The method of claim 1 , further comprising iterating over the temporal structures using a depth first search.
3. The method of claim 1 , further comprising repeating the method at periodic intervals.
4. The method of claim 1 , further comprising performing the method subsequent to the addition of a new temporal state of a data object.
5. The method of claim 1 , further comprising performing the method subsequent to the removal of a temporal state of a data object.
6. The method of claim 1 , further comprising maintaining a global reference list of all content segments that have been allocated in the deduplicated storage system.