Incremental garbage collection of data in a secondary storage

A computer storage medium that stores instructions, which when executed by a computer, causes the computer to perform a 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.

A system, comprising:

• a storage device to store a number of blocks of data in a memory space;
• and
• a garbage collection logic to locate the blocks of data that are both referenced by at least one other block stored within a set of one or more storage trees, and within a range at a tail of the memory space, the range representing an address range to be cleaned within an allocated segment of the memory space, wherein the memory space is implemented in a hierarchical architecture having one or more storage trees, each representing a snapshot taken at a point in time of target data being processed, each storage tree having a plurality of nodes, and each node representing a block of data of an active snapshot associated with each storage tree, each of the active snapshots including user-generated data stored from a file system taken at a different time, wherein locating the 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, and
• wherein said garbage collection logic is configured to copy the located blocks of data to an unallocated segment of the memory space and mark the range to be cleaned as unallocated so that at least a portion of the address space within the range is reclaimed.