Patent ID: 8806154

Claim:
A method for scalable indexing of a storage pool formed from multiple storage units in which backup information is recorded, comprising: forming a virtual volume in which the combined storage capacity of the storage pool is represented by a set of chunks have a pre-selected data size with the chunks being assigned to be either storage chunks or reference chunks; storing in a set of reference chunks metadata information to index the storage chunks and track usage of storage chunks, wherein storage chunks are allocated on demand and are referable more than once to reduce redundant storage for identical content; adjusting the total number of chunks and a chunk allocation in response to a change in the size of the available physical storage to include a sufficient number of reference chunks to index all of the storage chunks; wherein the reference chunks are updatable to store indexing information for redirect on write snapshots of the virtual volume; and wherein the set of reference chunks stores: a reference count map maintained as a set of contiguous storage pool chunks, the reference count map referencing all the storage chunks in a virtual volume including usage information on storage chunks used more than once including a usage count of each storage chunk, the usage count tracking free and allocated storage chunks and the number of times a storage chunk is referenced; and a reference count of chunks referred to by any redirect on write snapshots of the virtual volume.