System and method for efficiently measuring physical space for an ad-hoc subset of files in protection storage filesystem with stream segmentation and data deduplication
In one example, a method for processing data includes receiving information that identifies an ad-hoc group of size ‘n’ of files F 1 . . . F n , each file F including a respective segment set S, and then sampling a representation of each unique segment in the segment set S to obtain a sampled unique segment count for each file F. A unique segment count is then obtained for each file F by applying a sampling ratio R to each sampled unique segment count, and an average segment size for each file F is determined. Next, a physical space measurement is generated for each file F based on the average segment size and the unique segment count, and then a total physical space measurement p is generated based on the individual physical space measurements for each file F.
1. A method, comprising:
measuring an amount of physical storage space used, or expected to be used, by a dataset that comprises an ad-hoc group of size ‘n’ of files F 1 . . . F n , wherein measuring the amount of physical storage space comprises:
receiving information that identifies the ad-hoc group of size ‘n’ of files F 1 . . . F n , each file F including a respective segment set S;
creating a bloom filter with bitmap B F for each of the files F, and sampling a representation of each unique segment in the segment set S by sampling a fingerprint of each unique segment in the segment set S, wherein each sampled fingerprint corresponds to a unique segment physical size, and adding the unique segment physical sizes to the corresponding bloom filter to obtain a sampled unique segment count for each file F;
compressing and caching each of the bloom filters, wherein the bloom filters are compressed such that the respective compressed sizes are proportional to the size of an associated file;
obtaining a unique segment count for each file F by applying a sampling ratio R to each sampled unique segment count;
determining an average segment size for each file F;
generating a physical space measurement for each file F based on the average segment size and the unique segment count; and
generating a total physical space measurement p based on the individual physical space measurements for each file F by combining the compressed and cached bloom filters.
2. The method as recited in claim 1 , wherein the sampling of unique segments is a non-random sampling process.
3. The method as recited in claim 2 , wherein the non-random sampling of unique segments is based on the content of the sampled segments.
4. The method as recited in claim 1 , wherein the average segment size for any file F is obtained independently of the unique segment count for that file F.
5. The method as recited in claim 1 , wherein the sampled representation of a data segment comprises a fingerprint.
6. The method as recited in claim 1 , wherein the sampling is performed with a sampling mask.
7. The method as recited in claim 1 , wherein the sampling is performed such that the unique segment count is not underestimated.
8. The method as recited in claim 1 , wherein each file F is in the form of segmented, deduplicated data.
9. The method as recited in claim 1 , wherein the sampling is a non-random sampling of unique segments based on the content of the sampled segments.
10. The method as recited in claim 1 , wherein the average segment size for any file F is obtained independently of the unique segment count for that file F.
11. The method as recited in claim 1 , wherein each file F is in the form of segmented, deduplicated data.
12. The method as recited in claim 1 , wherein each fingerprint associated with a file F is able to be tested with a sampling condition.
13. The method as recited in claim 1 , wherein a segment associated with a fingerprint is sampled only when the application of a sampling mask indicates that the last bits of the fingerprint match a specified sampling pattern.
14. A non-transitory storage medium having stored therein computer-executable instructions which, when executed by one or more hardware processors, performs the following operations:
measuring an amount of physical storage space used, or expected to be used, by a dataset that comprises an ad-hoc group of size ‘n’ of files F 1 . . . F n , wherein measuring the amount of physical storage space comprises:
receiving information that identifies the ad-hoc group of size ‘n’ of files F 1 . . . F n , each file F including a respective segment set S;
creating a bloom filter with bitmap B F for each of the files F, and sampling a representation of each unique segment in the segment set S by sampling a fingerprint of each unique segment in the segment set S, wherein each sampled fingerprint corresponds to a unique segment physical size, and adding the unique segment physical sizes to the corresponding bloom filter to obtain a sampled unique segment count for each file F;
compressing and caching each of the bloom filters, wherein the bloom filters are compressed such that the respective compressed sizes are proportional to the size of an associated file;
obtaining a unique segment count for each file F by applying a sampling ratio R to each sampled unique segment count;
determining an average segment size for each file F;
generating a physical space measurement for each file F based on the average segment size and the unique segment count; and
generating a total physical space measurement p based on the individual physical space measurements for each file F by combining the compressed and cached bloom filters.
15. The non-transitory storage medium as recited in claim 14 , wherein the sampling is a non-random sampling of unique segments based on the content of the sampled segments.
16. The non-transitory storage medium as recited in claim 14 , wherein the non-random sampling of unique segments is based on the content of the sampled segments.
17. The non-transitory storage medium as recited in claim 14 , wherein the average segment size for any file F is obtained independently of the unique segment count for that file F.
18. The non-transitory storage medium as recited in claim 14 , wherein each file F is in the form of segmented, deduplicated data.
19. The non-transitory storage medium as recited in claim 14 , wherein a segment associated with a fingerprint is sampled only when the application of a sampling mask indicates that the last bits of the fingerprint match a specified sampling pattern.