Cluster and Single-Node Analysis of Long-Term ...

1 13 Cluster and Single-Node Analysis of Long-TermDeduplication Pa ernsZHEN JASON SUN,National University of Defense TechnologyGEOFF KUENNING,Harvey Mudd CollegeSONAM MANDAL,Stony Brook UniversityPHILIP SHILANE,Dell EMCVASILY TARASOV,IBM ResearchNONG XIAO,National University of Defense TechnologyEREZ ZADOK,Stony Brook UniversityDeduplication has become essential in disk-based backup systems, but there have been few Long-Term studiesof backup workloads. Most past studies either were of a small static snapshot or covered only a short periodthat was not representative of how a backup system evolves over time. For this article, we rst collected 21months of data from a shared user le system; 33 users and over 4,000 snapshots are covered. We then analyzedthe data set, examining a variety of essential characteristics across two dimensions: Single-Node deduplicationand Cluster deduplication .

2 For Single-Node deduplication Analysis , our primary focus was individual-user apparently similar roles and behavior among all of our users, we found signi cant di erences in theirdeduplication ratios . Moreover, the data that some users share with others had a much higher deduplicationratio than average. For Cluster deduplication Analysis , we implemented seven published data -routing algorithmsand created a detailed comparison of their performance with respect to deduplication ratio, load distribution,and communication overhead. We found that per- le routing achieves a higher deduplication ratio thanrouting by super-chunk (multiple consecutive chunks), but it also leads to high data skew (imbalance of spaceusage across nodes). We also found that large chunking sizes are better for Cluster deduplication , as theysigni cantly reduce data -routing overhead, while their negative impact on deduplication ratios is small andacceptable.

3 We draw interesting conclusions from both Single-Node and Cluster deduplication Analysis , andmake recommendations for future deduplication systems Reference format:Zhen Jason Sun, Geo Kuenning, Sonam Mandal, Philip Shilane, Vasily Tarasov, Nong Xiao, and Erez Cluster and Single-Node Analysis of Long-Term deduplication Trans. Storage14, 2,Article 13 (May 2018), INTRODUCTIONThe explosive growth of data in recent years [38] has made deduplication an important researcharea. deduplication systems split data into identi able pieces ( chunks ) and then use hashes toidentify and eliminate redundant chunks. This approach has proven highly e ective in saving space,especially in backup storage [44].Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without feeprovided that copies are not made or distributed for pro t or commercial advantage and that copies bear this notice and thefull citation on the rst page.

4 Copyrights for components of this work owned by others than the author(s) must be with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requiresprior speci c permission and/or a fee. Request permissions from 2018 Copyright held by the owner/author(s). Publication rights licensed to Association for Computing $$ Transactions on Storage, Vol. 14, No. 2, Article 13. Publication date: May Transactions on Storage 2018 Many researchers have analyzed data sets from various environments, such as disk and tapebackups [14,39], primary storage [6,18,25,30], archival systems [17], and HPC centers [29]. Byunderstanding such data sets characteristics, we can design more e cient storage systems [10,11,35]. However, data sets may vary signi cantly across di erent environments ( , whole- lechunking e ciencies range between 20% and 87% compared to sub- le chunking [6,29,39]).

5 As aresult, conclusions drawn from only a few data sets cannot be used to guide the design of a practicaland e cient deduplication system. Thus, new, large-scale studies using di erent types of data setsand investigating new metrics are data redundancies in backups [15] make deduplication an integral part of backup space savings of deduplication made the transition from tape-based to disk-based backupsystems possible [44]. However, our understanding of these systems real-life performance is stillpoor, because there are few Long-Term studies of large backup data sets: most prior studies drawconclusions based on the entire data set, whereas we show that studying per-user trends is valuableand produces surprising many backup storage systems, data sizes are growing rapidly, and although deduplication canreduce the space consumption by a factor of 10 or more, Single-Node storage systems still graduallyfail to meet capacity and throughput needs.

6 Cluster deduplication is an appealing approach toaddress these challenges by distributing the load and aggregating throughput from multiple algorithms are a key component of Cluster deduplication ; selecting the best destinationnode for data assignment has a direct impact on the overall (and per-node) deduplication ratio, loadbalance, and routing overheads. Many data -routing algorithms have been proposed with variousgoals, such as design simplicity or maximizing the deduplication there are signi cant di erences in the characteristics of data sets from various environ-ments, the performance of a particular algorithm may vary signi cantly depending on the dataset. We have classi ed data -routing algorithms and implemented seven published algorithms thatadopt di erent strategies.

7 We provide a detailed comparative Analysis of the performance of eachalgorithm using key metrics and also draw interesting this article, we rst introduce the data set that we have been collecting and have releasedpublicly, and the tools we developed. Our data set,Homes, has a longer duration than previouslypublished studies, which is important for investigating realistic, Long-Term trends: 21 months ofdaily snapshots taken over a period. One of our goals was to nd out whether previouslypublished ndings still hold with our much longer data then present an Analysis of Single-Node deduplication based on this data set, with sometimesexpected and sometimes unexpected results. For example, we found that because of the size of thechunk index itself, smaller chunk sizes are not always better at saving space, as others discovered aswell [30,39].

8 We also found that whole- le chunking identi es signi cantly fewer duplicates thansub- le chunking, because larger les tend to dominate space usage and have a small deduplicationratio (de ned as the logical storage space divided by the physical storage space after deduplication );this was also reported before [30].In addition, we studied the data set from the users point of view. Given that our users werelargely similar in their background, behavior, and job function, we expected their storage footprintsand deduplication patterns to be similar too. Yet that was not the case. We found, investigated, andexplained three surprising new results:(1)The deduplication ratios of each user s own data set varied signi cantly, and their sensitivityto chunking size was also di erent.

9 This suggests that even similar users behave quitedi erently; this should be taken into account in future deduplication (2) deduplication ratios across users ranged widely. Yet, in combination with other information,the deduplication ratio can help us group users together to improve the e ectiveness ofclustered deduplication systems.(3)The data that users share with each other had a higher deduplication ratio than average, andthe duplicate data shared by di erent user pairs tended to be fairly similar. This knowledgecan bene t the caching and prefetching components of deduplication , we studied theHomesdataset by using Cluster deduplication techniques. We introduce ve important parameters that allow us to classify many Cluster deduplication algorithms. Weimplemented seven published algorithms that cover several combinations of these parameters,and simulated their behavior accurately using our extensive data set.

10 We plan to release theimplementations of these algorithms in the future, so that others can run or modify the parametersand thresholds of each algorithm easily. We analyzed the behavior of these seven algorithms interms of Cluster deduplication ratios , load distributions, and communication overheads. We havecome to three conclusions:(1)Using whole le as the routing unit leads to a better deduplication ratio at the cost of poorload balance. In addition, communication overheads increase, because most les inHomesare small.(2)Physical and logical load distribution are not always consistent. Here, thephysical loadmeans the data that is stored in each node after deduplication ; and thelogical loadmeansthe data that is assigned to each node before deduplication . The physical load shows thereal space consumption, while the logical load includes the meta- data size (mainly the lerecipe) and the number of I/O requests.