Patent ID: 7451168

Claim:
A method of garbage collecting in a storage device comprising: locating blocks of data stored in a contiguous circular log that are both referenced by at least one other block of data stored within a set of one or more storage trees and within a range at a tail of the log using pruned walking, the range representing an address range within an allocated segment of the log, each storage tree representing active snapshots of user-generated data stored from each one of a plurality of remote computer systems taken at different points in time and having a plurality of nodes, each node representing a block of data of an active snapshot associated with each storage tree, the plurality of nodes including leaf nodes representing data blocks of the user-generated data stored from each one of the plurality of remote computer systems and root and intermediate nodes representing data blocks of system-generated data created by the storage device, the system-generated data including pointers to reference other data blocks of the user-generated data to enable overlapping and sharing of the user-generated data between and among different snapshots of the plurality of snapshots, each block of data stored within the circular log in a sequential order, wrapping around to a beginning of the log once an end of the log is reached and the beginning of the log has been cleaned, so that the size of the contiguous log does not increase beyond its originally allocated size; copying the blocks of data that are referenced by one or more other blocks of data of other nodes and within the range to an unallocated segment of the log, wherein blocks of data that are not referenced by other blocks of data and within the range remain untouched, and marking the range at the tail of the log as unallocated so that at least a portion of an address space within the range is reclaimed.