Patent ID: 8028009

Claim:
A computer-implemented method for garbage collection in a storage device, the method comprising: locating blocks of data in a memory space that are both referenced by at least one other block of data and within a range representing an address range within an allocated segment of the memory space, wherein the data is stored in a set of one or more storage trees, each representing active snapshots of user-generated data captured at different points in time, wherein each storage tree includes a plurality of nodes, each representing a block of data of an active snapshot associated with each storage tree, wherein locating blocks of data comprises pruning walking of the storage trees to determine active blocks of data within the range, including determining, based on accessing in one of the storage trees, a parent node having at least one descendent node that none of parent node's descendent nodes are associated with blocks of data within the range, skipping the walking of the parent node's descendent nodes if none of them is associated with blocks of data within the range, retrieving a block of data associated with a current node, upon determining that a minimum address value among addresses of child nodes is within the range to be cleaned, designating, as the current node, one of the child nodes of the current node that is an interior node, upon determining that at least one child node is an interior node, designating, as the current node, a parent node of the current node whose child nodes are unprocessed, and marking the range as unallocated when the blocks of data that are active and within the range are copied to a head of the memory space so that at least a portion of the address space within the range to be cleaned is reclaimed; copying the blocks of data that are referenced by at least one other block of data and within the range to an unallocated segment of the memory space; and marking the range at the tail of the memory space as unallocated such that at least a portion of an address space within the range is reclaimed.