## 3 Use Cases of Graphs
### Size Calculation for Deduplicated File Sets  
Motivation  
Administrators of modern large-scale storage systems are interested to know the space consumption of a subset of files, where the subset of interest is defined by administrators. For example, \"what applications and users use the most of space\", \"how much space do pdf files consume\", _etc._ Since the subset of files are defined at the query time, the size of the user-defined subset has to be computed on the fly from the metadata. We denote such queries as _on-demand size_ queries. The on-demand nature of such queries poses a significant challenge to traditional metadata management systems and methods. As proposed by [PERSON] _et al_. [10] and [PERSON] _et al_. [11], a new set of metadata structures and related methods are required to efficiently answer _on-demand_ queries (including _on-demand size_ queries) for a large-scale storage system. The output of such queries is a subset of files that meet the query criteria.  
Deduplication in storage systems further complicates the problem because the size of a subset of files is not simply the sum of the sizes of all files in the subset, _i.e._, even after we get the list of files that meet the query criteria, we cannot have a sum of the selected file sizes as these files may share content with each other. In this paper, we focus our discussion on how to calculate the accurate size of such a deduplicated set of files after we get the list of files from file subset queries.  
The state-of-the-art practice is to query the deduplication metadata containing the signatures of either file of sub-file chunks, which is not scalable with the storage system size. To compute the size of a deduplicated subset of files, it is inevitable to deduplicate the subset of files by scanning all related file chunks and querying the deduplication metadata accordingly. We propose a relatively small metadata layer that is extracted from the raw deduplication metadata, to help efficiently answer _on-demand size_ queries in a deduplicated storage system.  
The _DCSG_ graph is a good candidate for such an efficient metadata layer for two reasons. First, the _DCSG_ graph accurately models the sharing between files for either a full set of files or for a subset of  
Figure 11: Partitioning cost as function of the number of equal sizes partitions, for WL2 workload using CHAIN and STAR topology.  
files. Second, the _DCSG_ graph has the potential to reduce its memory footprint by aggregating adjacent shared chunks. Experimental results show that aggregating adjacent shared chunks can effectively reduce the memory footprint of the _DCSG_ graph.  
In the following discussion, we first describe how the state-of-the-art practice answers _on-demand size_ queries using only the raw deduplication metadata in a database. We name this approach the \"naive\" algorithm. We then describe a straightforward algorithm based on _DCSG_ graphs, which we name the \"graph\" algorithm, and a refined, scalable algorithm by aggregating adjacent shared chunks, which we name the \"optimized graph\" algorithm or _GraphOpt_. Finally we present the experimental results of comparing these three algorithms with the data sets described in Section 3.1.