Patent ID: 7921086

Claim:
A method for providing deterministic space management in a deduplication context, the method comprising the steps of: maintaining, by a computer, a block subkey data structure in computer memory, the block subkey data structure comprising an entry for each of a plurality of blocks in a deduplication store, each entry comprising a subkey identifying that block and a refcount for that block, each subkey comprising a subset of bits of a corresponding full hash key identifying that block, and each refcount indicating a number of objects that reference that block, independent of a number of references to that block by any individual object; for each of a plurality of objects in the deduplication store, maintaining, by a computer, a corresponding object subkey data structure, each object subkey data structure comprising an identifying subkey for each block referenced by the corresponding object, and being stored in association with that object; receiving, by a computer, a space management query concerning a specific object set; responsive to the received query, creating, by a computer, an object set subkey data structure concerning the object set, the object set subkey data structure comprising an entry for each block referenced by at least one object in the object set, each entry comprising a subkey identifying that block and an object set refcount for that block, the object set refcount indicating a number of objects in the object set that reference that block, independent of a number of references to that block by any individual object in the set; and utilizing the object set subkey data structure to determine an answer to the received space management query, by a computer.