Patent ID: 9646067
Date: 2017-05-09
CPC Classifications: G06F

Claim:
1. A computerized method of maintaining running information of ingestion and deletion of file system data for a deduplicated data store in which to determine an expected outcome of a garbage collection operation on the deduplicated data store without performing the garbage collection operation, the method comprising: maintaining, by a computer device, a temporal graph, the temporal graph including nodes, the nodes including hash references to objects; updating, by the computer device, an accumulated difference count when a node is added to the temporal graph, the accumulated difference count including a number of hash differences between a parent node and its children nodes in the temporal graph; updating, by the computer device, a divested difference count when a node is removed from the temporal graph, the divested difference count including a number of hash differences referenced by the removed node but not referenced by either a parent node of the removed node or any child nodes of the removed node; and determining, by the computer device, an expected amount of data being reclaimable during a garbage collection operation based on both of the accumulated difference count and the divested difference count, thereby estimating an expected outcome of the garbage collection operation without performing the garbage collection operation, wherein determining the expected amount of data being reclaimable during the garbage collection includes determining an amount of data storage used by the deduplicated data store but not referenced by an object.