Storage system capacity usage estimation

A non-transitory computer-readable medium having stored thereon instructions that, when executed by one or more processors, cause the one or more processors to:

• maintain an index of objects in a storage system to store data for the one or more hardware processors, the storage system to deduplicate data stored therein, each object in the index of objects having at least a corresponding shallow reference count indicating a number of parent objects that hold a reference to the object;
• maintain at least one tree milli-index and at least one node milli-index, each having entries corresponding to a subset of objects stored in the index of objects in the storage system each of the entries having sampled object signature values and deep reference count values for corresponding objects of the subset of objects in the index in the storage system, the deep reference values indicating a number of logical occurrences of associated objects within a tree of objects corresponding to the index of objects;
• and
• determine a capacity utilization of the storage system based on analysis utilizing the deep reference values from the at least one tree milli-index or the at least one node milli-index.

A method comprising:

• maintaining an index of objects in a storage system to store data for the one or more hardware processors, the storage system to deduplicate data stored therein, each object in the index of objects having at least a corresponding shallow reference count indicating a number of parent objects that hold a reference to the object;
• maintaining at least one tree milli-index and at least one node milli-index, each having entries corresponding to a subset of objects stored in the index of objects in the storage system each of the entries having sampled object signature values and deep reference count values for corresponding objects of the subset of objects in the index in the storage system, the deep reference values indicating a number of logical occurrences of associated objects within a tree of objects corresponding to the index of objects;
• and
• determining a capacity utilization of the storage system based on analysis utilizing the deep reference values from the at least one tree milli-index or the at least one node milli-index.