## Content Sharing Graphs for Deduplication-Enabled Storage Systems  
**[PERSON], [PERSON] * and [PERSON]**  
IBM Research at Almaden, 650 Harry Road, San Jose, CA 95120, USA;  
E-Mails: [EMAIL_ADDRESS] (M.L. ); [EMAIL_ADDRESS] (P.S.) \({}^{\star}\) Author to whom correspondence should be addressed; E-Mail: [EMAIL_ADDRESS];  
Tel. : +1-408-927-2943; Fax: +1-408-927-3497. _Received: 30 December 2011; in revised form: 28 March 2012 / Accepted: 29 March 2012 / Published: 10 April 2012_  
**Abstract:** Deduplication in storage systems has gained momentum recently for its capability in reducing data footprint. However, deduplication introduces challenges to storage management as storage objects (e.g., files) are no longer independent from each other due to content sharing between these storage objects. In this paper, we present a graph-based framework to address the challenges of storage management due to deduplication. Specifically, we model content sharing among storage objects by content sharing graphs (CSG), and apply graph-based algorithms to two real-world storage management use cases for deduplication-enabled storage systems. First, a quasi-linear algorithm was developed to partition deduplication domains with a minimal amount of deduplication loss (_i.e._, data replicated across partitioned domains) in commercial deduplication-enabled storage systems, whereas in general the partitioning problem is NP-complete. For a real-world trace of 3 TB data with 978 GB of removable duplicates, the proposed algorithm can partition the data into 15 balanced partitions with only 54 GB of deduplication loss, that is, a 5% deduplication loss. Second, a quick and accurate method to query the deduplicated size for a subset of objects in deduplicated storage systems was developed. For the same trace of 3 TB data, the optimized graph-based algorithm can complete the query in 2.6 s, which is less than 1% of that of the traditional algorithm based on the deduplication metadata. **Keywords:** deduplication; storage systems; graph models; graph partitioning; k-core; subset query Introduction  
Motivated by the current data explosion, data reduction methods like deduplication and compression have become popular features increasingly supported in primary storage systems. The two techniques have interesting but contrasting properties--compression has a \"local\" scope (file, block, object) while deduplication has a global one. Although data reduction methods can save storage space for storage systems, they introduce new technical challenges to storage management, which is especially true for deduplication. Compression does not present great challenges to storage management as storage objects are not correlated with each other after data compression. However, for deduplication, storage objects (e.g., files) share data content among them in deduplication-enabled storage systems. Storage management tasks can no longer consider storage objects as independent. Traditionally, storage management systems assume there is no data sharing between storage objects, and therefore individual storage objects can be managed independently without affecting others. However, when storage objects share content with each other, they cannot be managed independently because management decisions on one file may affect another file. For example, in a traditional tiering storage system, individual old files can be migrated to a \"colder\" tier (e.g., from disks to tapes) without affecting other files. However, in a deduplicated tiering storage system, old files may share content with other files that are not necessarily old, so the migration of a candidate file needs to consider other files that share content with the candidate file, which can complicate the storage management tasks. State-of-the-art deduplication-enabled storage systems [1; 2; 3; 4; 5; 6] have not exploited the sharing among deduplicated set of files for the file management tasks.