A method, including partitioning a dataset into a first number of data units, and selecting, based on a sampling ratio, a second number of the data units. A hash value is calculated for each of the selected data units, and a first histogram is computed indicating a first duplication count for each of the calculated hash values. Based on respective frequencies of the calculated hash values, a second histogram is computed indicating an observed frequency for each of the first duplication counts in the first histogram, and based on the sampling ratio and the second histogram, a target function is derived. A third histogram that minimizes the target function is derived, the third histogram including, for the first number of the storage units, second duplication counts and a respective predicted frequency for each of the second duplication counts. Finally, a deduplication ratio is determined based on the third histogram.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is related to U.S. Patent Applications titled “Low Memory Sampling Based Estimation of Distinct Elements and Deduplication” and “Gauging Accuracy of Sampling-Based Distinct Element Estimation” filed on even date with the present application, and which are incorporated herein by reference.

FIELD OF THE INVENTION

The present invention relates generally to data deduplication, and specifically to implementing a method of estimating a deduplication ratio based on a random sample of data retrieved from a dataset.

BACKGROUND

In datasets typically stored on storage systems, data deduplication is a technique for eliminating duplicate copies of repeating data, thereby improving storage utilization. Additionally, in data network environments, data deduplication can be applied to network data transfers in order to reduce the amount of data to be transmitted over the network. In a data deduplication process, unique chunks of data (i.e., byte patterns) are identified and stored during a process of analysis. As the analysis continues, other chunks are compared to the stored copy and whenever a match occurs, the redundant chunk is replaced with a small reference that points to the stored chunk. Given that the same byte pattern may occur dozens, hundreds, or even thousands of times (the match frequency is dependent on the chunk size), the amount of data that must be stored or transferred can be greatly reduced.

The potential savings that deduplication can yield are profound. For example, in workloads that have inherent repetitions (e.g., backup scenarios), deduplication can reduce required storage with ratios ranging between 1:2 and 1:50.

SUMMARY

There is provided, in accordance with an embodiment of the present invention a method, including partitioning a dataset into a first number of logical data units, selecting, based on a sampling ratio, a second number of the logical data units, the second number of the logical data units including a random sample of the first number of logical data units, calculating a hash value for each of the selected logical data units, computing a first histogram indicating a first duplication count for each of the calculated hash values, computing, based on respective frequencies of the calculated hash values, a second histogram indicating an observed frequency for each of the first duplication counts in the first histogram, deriving, based on the sampling ratio and the second histogram, a target function, deriving a third histogram that minimizes the target function, the third histogram including, for the first number of the storage units, second duplication counts and a respective predicted frequency for each of the second duplication counts, and determining, based on the third histogram, a deduplication ratio.

There is also provided, in accordance with an embodiment of the present invention an apparatus, including a storage device configured to store a dataset, and a processor configured to partition a dataset into a first number of logical data units, to select, based on a sampling ratio, a second number of the logical data units, the second number of the logical data units including a random sample of the first number of logical data units, to calculate a hash value for each of the selected logical data units, to compute a first histogram indicating a first duplication count for each of the calculated hash values, to compute, based on respective frequencies of the calculated hash values, a second histogram indicating an observed frequency for each of the first duplication counts in the first histogram, to derive, based on the sampling ratio and the second histogram, a target function, to derive a third histogram that minimizes the target function, the third histogram including, for the first number of the storage units, second duplication counts and a respective predicted frequency for each of the second duplication counts, and to determine, based on the third histogram, a deduplication ratio.

There is further provided, in accordance with an embodiment of the present invention a computer program product, the computer program product including a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code including computer readable program code configured to partition a dataset into a first number of logical data units, computer readable program code configured to select, based on a sampling ratio, a second number of the logical data units, the second number of the logical data units including a random sample of the first number of logical data units, computer readable program code configured to calculate a hash value for each of the selected logical data units, computer readable program code configured to compute a first histogram indicating a first duplication count for each of the calculated hash values, computer readable program code configured to compute, based on respective frequencies of the calculated hash values, a second histogram indicating an observed frequency for each of the first duplication counts in the first histogram, computer readable program code configured to derive, based on the sampling ratio and the second histogram, a target function, computer readable program code configured to derive a third histogram that minimizes the target function, the third histogram including, for the first number of the storage units, second duplication counts and a respective predicted frequency for each of the second duplication counts, and computer readable program code configured to determine, based on the third histogram, a deduplication ratio.

DETAILED DESCRIPTION OF EMBODIMENTS

When implementing data deduplication, an entire dataset on a storage system is typically processed in order to realize the maximum saving potential of the deduplication. While the same process may be replicated in order to estimate the deduplication ratio of the dataset, processing the entire dataset can be a prohibitively expensive operation that requires large memory and computing resources. On the other hand, estimating deduplication savings by examining a sample of the data can be challenging, since data deduplication is a global property, and repetitions need to be identified over ranges that may span multiple terabytes of data in multiple locations.

Embodiments of the present invention provide methods and systems that provide a framework for the task of estimating a deduplication ratio based on a sample of the dataset. As described hereinbelow, a dataset is partitioned into a first number of logical data units, and, based on a sampling ratio, a second number of the logical data units are selected, the second number of the logical data units comprising a random sample of the first number of logical data units. A hash value is calculated for each of the selected logical data units, and a first histogram indicating a first duplication count for each of the calculated hash values is computed. Upon computing, based on respective frequencies of the calculated hash values, a second histogram indicating an observed frequency for each of the first duplication counts in the first histogram, a target function is derived based on the sampling ratio and the second histogram. A third histogram that minimizes the target function is computed, the third histogram comprising, for the first number of the storage units, second duplication counts and a respective predicted frequency for each of the second duplication counts, and the third histogram is used to determine a deduplication ratio.

In some embodiments, compression ratios of the second number of logical data units can be incorporated into the data duplication analysis, thereby enabling estimation of the combined compression and deduplication savings in systems that employ both technologies.

In operation, the target function measures a distance between a “sampling transformation” on potential third histograms and the second observed histogram. The goal is to find the third histogram that minimizes the distance. The third histogram having the minimum distance comprises an “optimal histogram”, and to derive, from this optimal histogram, an estimation of the deduplication potential in the dataset. Finding the optimal histogram can be performed using various standard optimization methods, depending also on the distance measure at hand.

Embodiments of the present invention provide a capability to forecast how much space can be saved from deduplicating a specific dataset. Motivations for forecasting the space savings include:Storage system sizing. When purchasing a storage system with deduplication, a sufficient amount of storage space needs to be purchased to store all of the data (i.e., after deduplication). This amount of storage space can vary greatly according to the deduplication ratio. Therefore, assuming an aggressive deduplication ratio (expecting too high savings from deduplication) can leave the system out of space at some point. On the other hand taking a very cautious approach (assuming poor deduplication benefits) to the deduplication ratio may result in excess capital expenditures which negates the purpose of using deduplication in the first place. Therefore, an accurate estimation of the space saving is paramount to the success of a deduplication system.Resource allocation and decisions. Performing deduplication comes at a cost of system resources. Central processing unit (CPU), memory and disk resources are typically used to carry out the deduplication process. These resources may be scarce in storage or other systems and therefore should be allocated carefully. Specifically, resources can be allocated to data with the best savings potential (i.e., as opposed wasting these resources on data that has no meaningful deduplication potential). In other words, embodiments of the present invention enable capital resources to be directed to storage systems that support deduplication only for storage systems whose data exhibits sufficient deduplication saving potential.Choice of algorithm. Different deduplication methods (e.g. chunking methods and chunk size) can at times produce different results. Knowing an optimal method for determining deduplication levels in advance can prove to be highly beneficial.

System Description

FIG. 1is a block diagram that schematically illustrates a computer20configured to estimate a deduplication ratio for a dataset56stored on a storage system22in accordance with an embodiment of the present invention. Computer20comprises a processor24and a memory26, and storage system22comprises one or more storage devices28such as hard disk drives or solid-state disk drives. Computer20and storage system22communicate via a data network connection30.

In embodiments described herein, the dataset is partitioned into logical data units comprising super-chunks32, each of the super-chunks comprising multiple chunks34. For example, each super-chunk32may comprises a logical data unit having a length of one megabyte, and each chunk34may comprise a logical data unit having a length of 64 kilobytes. In this example, each super-chunk32comprises sixteen chunks34. While chunks34are typically fixed lengths, chunks34having variable lengths is considered to be within the spirit and scope of the present invention.

While the configuration inFIG. 1presents the logical data units comprising super-chunks32and chunks34, dataset56comprising any type of logical data units that can be analyzed for deduplication is considered to be within the spirit and scope of the present invention. Examples of logical data units that computer20can analyzed for deduplication include block logical data units, file system logical data units and object logical data units. It is understood that this logical composition (i.e., super-chunks32and chunks34) is for the sake of performing or estimating deduplication on this data and does not necessarily apply to the data in other circumstances.

Memory26stores a target function module36, an observed hash value duplication histogram38, an observed duplication frequency histogram40and a derived optimal duplication frequency histogram42. In embodiments described herein, each histogram36,38and39comprises (i.e., in a more general mathematical sense) a function mithat counts the number of observations that fall into each of the disjoint categories (known as bins). Therefore, if we let n be the total number of observations and k be the total number of bins, the histogram mimeets the following conditions:

In embodiments described herein, observed hash value duplication histogram38may also be referred to as a first histogram, observed duplication frequency histogram40may also be referred to as a second histogram and derived optimal duplication frequency histogram may also be referred to as a third histogram. As described hereinbelow:Processor24first retrieves a sample number of chunks34, calculates a hash value44for each of the chunks, and creates observed hash value duplication histogram38. In observed hash value duplication histogram38, each given hash value44has an associated number of observations46indicating a number of chunks34that have the given hash value.Processor24analyzes observed hash value duplication histogram38to create observed duplication frequency histogram40comprising duplication counts48and corresponding number of observations50. Each duplication count48indicates a number of duplications (i.e., observed frequency histogram40comprises observed frequencies of duplication counts48). For example, a given duplication count48stores “5” and its corresponding number of observations52stores “8” indicates that there are eight instances in the sample number of chunks34where a given chunk34is duplicated five times.Processor24executes target function module36to derive a target function comprising a transformation function.Processor24derives third histogram42comprising duplication counts52and a corresponding number of observations54. In embodiments of the present invention, derived duplication frequency histogram42comprises a duplication frequency histogram for all chunks34in dataset56that “best explains” observed frequency histogram40.

While embodiments herein use hash values44to identify duplicate chunks34, any other type of digital “fingerprint” that can identify the duplicate chunks is considered to be within the spirit and scope of the present invention. In some embodiments, each given hash value44may have a corresponding compression ratio (not shown) or an estimated compression ratio (not shown) for the chunk associated with the given hash value. Incorporating compression ratios or estimated compression ratios into identifying space savings realized from deduplication is described hereinbelow.

Memory26typically comprises high-speed volatile memory such as random access memory (RAM). While the example inFIG. 1shows histograms38,40and42stored entirely in memory26, other configurations are considered to be within the spirit and scope of the present invention. For example, histograms38,40and42can be stored on storage device (not shown) coupled to computer20, or the histograms can stored using a combination of memory26and the storage device.

Processor24typically comprises a general-purpose computer, which are programmed in software to carry out the functions described herein. The software may be downloaded to computer20in electronic form, over a network, for example, or it may be provided on non-transitory tangible media, such as optical, magnetic or electronic memory media. Alternatively, some or all of the functions of processor24may be carried out by dedicated or programmable digital hardware components, or using a combination of hardware and software elements.

These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks.

FIG. 2is a flow diagram that schematically illustrates a method for estimating a deduplication ratio in dataset56, in accordance with an embodiment of the present invention. In a definition step60, a chunk size, a super-chunk size and a sampling ratio are defined, and in an partition step62, processor24partitions dataset56into a number (also referred to herein as a first number of chunks34.

In a selection step64, processor24selects, using the sampling ratio, a sample number (also referred to herein as a second number) of random chunks34in dataset56. Using a simple example, if the chunk size is 1,000 bytes, the sampling ratio is 10%, and there are 100,000 chunks34in dataset56, then processor24selects a random sample of 10,000 chunks34.

In some embodiments (especially in hard disk based storage systems), processor24can reduce the time required to retrieve the selected random chunks34by retrieving super-chunks32from storage system22, each of the super-chunks comprising multiple chunks34. For example, if the super-chunk size is 10,000 bytes, then processor24can retrieve1,000random super-chunks32, and extract 10,000 chunks34from the retrieved super-chunks (i.e., extract ten chunks34from each super-chunk32).

In a calculation step66, processor24calculates a given hash value44for each chunk34, and in a first computation step68, the processor computes observed hash value duplication histogram38. Observed hash value duplication histogram38comprises hash values44calculated in step66and number of observations46indicating a respective number of duplications of data stored in chunks34.

In a second computation step70, processor24uses observed hash value duplication histogram38to compute observed duplication frequency histogram40. Duplication counts48and number of observations50in observed frequency histogram40comprises a histogram of how many chunks34are duplicated one time, how many chunks34are duplicated two times, how many chunks34are duplicated three times etc. In embodiments described herein, observed hash value duplication histogram38may incorporate factors such as length types (i.e., whether the logical data units have fixed or variable lengths), physical locations, virtual locations and timestamps. For example, if processor24calculates identical hash values44for two chunks (i.e., logical data units) that have different timestamps, the processor can store the two (i.e., identical) hash values to separate entries in observed has value duplication histogram38.

In a first derivation step72, processor24executes target function module36to define a target function based on the sampling ratio and observed duplication frequency histogram40, and in a second derivation step74, the processor derives an optimal duplication frequency histogram42that minimizes target function module36. When deriving histogram42, processor24can use calculations such as quadratic programming computations, maximum likelihood computations and linear programming computations. Calculations used by embodiments of the present invention to perform steps72-74are described hereinbelow.

Finally, in a determination step78, processor24determines a deduplication ratio based on the identified optimal histogram in a determination step78, and the method ends. In some embodiments, the deduplication ratio indicates a first space savings for implementing deduplication on the sample number of chunks34. In additional embodiments, processor24can estimate a compression ratio for each of the sample chunks, and can determine a second space savings based on the compression ratios and the deduplication ratio.

In further embodiments, processor24can (i.e., in step68) compute observed hash value duplication histogram38for a subset of the hash values calculated in step66. In other words, observed hash value duplication histogram38indicates duplication counts for a subset of the calculated hash values. In these further embodiments, processor24can compute derived duplication frequency histogram40and estimate the deduplication ratio based on hash value duplication histogram38that was computed for the subset of the hash values.

Target Function Definition

In embodiments of the present invention, a dataset is comprises collection of items. In reality, the data is a stream of bytes, that for the purposes of deduplication is broken into data chunks34(this could be fixed or variable sized chunks, e.g. of size 4K) and a given hash value44(i.e., a digital fingerprint) is computed for each chunk34. In some embodiments, the collection of these fingerprints is considered to be the items in the dataset, where duplication of two items means that the corresponding chunks had identical fingerprints. Each of the items may also hold a compression ratio (or estimated compression ratio) for the corresponding data chunk.

In operation, processor24takes a random sample of size m out of the entire dataset of size N, and computes a duplication frequency histogram y (i.e., observed duplication frequency

histogram40) on this sample. Processor24then defines the sampling transform T (i.e., via target function module36) between a duplication frequency histogram x′ (not shown) on a dataset of total size N to the expected duplication frequency histogram y′ (not shown) of a random sample of size m (randomly chosen out of the full sized N dataset).

The goal of the method is to find a legal duplication frequency histogram x′ such that the distance between T(x′) and the observed y is minimal. In embodiments described herein, this distance comprises the target function. The deduplication estimation of the dataset can then be computed according to the optimal x′ (i.e., derived duplication frequency histogram42).

More formally, given an observed duplication frequency histogram y, the goal is to find a legal duplication frequency histogram x′ for which

that minimizes the distance (i.e., the target function):
Dist(T(x′),y)  (3)The estimated number of distinct chunks in the entire dataset is then

C=∑i=1size⁡(x′)⁢xi′(4)and the estimated deduplication ratio is

Finding the optimal x can be done in various optimization methods, for example, using linear programming when the distance measure is an l1norm, using quadratic programming when the distance is measure is an l2norm or using a choice of optimization methods to find a maximum likelihood ratio.

There are several variations to be considered here that are specific to the case of data reduction and deduplication:In storage systems that are the main target of deduplication estimation, performing random sampling at a low granularity is taxing. Instead, one implementation is to sample “super-chunks”32that match the underlying page size of the storage system (this could be 256 KB, 1 MB depending on system). Each super-chunk32can then be broken into the smaller deduplication chunks34and considered part of the sample. While this does not constitute of a truly random sample, experiments have shown that this forms a fair estimation.Another implementation can sample super-chunks32, and then break them into smaller chunks34for a variety of chunk sizes and methods. For each chunking method the estimation process can be run separately, and this can give an indication of the best “chunking” method for the dataset at hand.In the case that compression is also implemented in the system (this is a popular and beneficial combination where typically compression is performed after deduplication), the algorithm in target function module36can be modified as follows: Hold a weighted duplication frequency histogram in which the ithbucket contains the number of element that had i duplications times CRi, where CRiis the average compression ratio of the elements (i.e., chunks34) with duplication i. In other words, the ithbucket represents the average number of chunks required to store all of the items that had reference count i (after they are compressed). Let CR be the average compression of the non deduplicated data—this can be efficiently estimated using sampling techniques known in the art. The optimization will now be the following:Find a weighted duplication frequency histogram x′ under the constraint that

∑i=1size⁡(x)⁢i*xi=N·CR(5)such that the distance between T(x′) and the observed weighted duplication frequency histogram y is minimal.The estimated number of chunks required to store the entire compressed and deduplicated dataset is then

C=∑i=1size⁡(x′)⁢xi′(6)and the estimated data reduction ratio is

R=CN.In a straightforward implementation, processor24generates the duplication frequency histogram directly from the sampled data. However, some deduplication techniques are limited in their duplication finding and elimination capabilities. For example, it may be the case that deduplication is only performed when the physical/virtual addresses (i.e., locations) involved are close or in the same range. Such considerations can be inserted in the creation of the duplication frequency histogram, so that it reflects what would happen when the actual deduplication algorithm runs.In another implementation, the sample used to form the observed y is taken on-line, by a bump in the wire that records hashes for p percent of the traffic. In such an implementation, duplications that occur at large time distances from each other can be treated differently, depending on the deduplication architecture at hand. In some embodiments, processor24can determine the time distances based on timestamps of the logical data units (e.g., super-chunks32and chunks34)

In embodiments where compression ratios are incorporated into the estimation, processor24can associate each of duplication count48in observed frequency distribution40with one or more of the logical data units, and then calculate, for each given deduplication count48, an average of the compression ratios of the logical data units associated with the given deduplication count, weight, for each of deduplication count48, the respective observed frequency (i.e., observations50) according to the respective average compression ratios, and weight the optimal duplication frequency histogram42based on the average of the compression ratios.