Generating and optimizing summary index levels in a deduplication storage system

• US 9,983,822 B1
• Filed: 10/31/2016
• Issued: 05/29/2018
• Est. Priority Date: 05/02/2016
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Karr, Ronald, Miller, Ethan L., Sandvig, Cary A., Wang, Feng, Zhang, Wei
• Primary Examiner(s): Chan, Tracy
• Application Number:
  US15/339,673
• Time in Patent Office: 575 Days
• Field of Search: 711154
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

The method generates a first deduplication map (DDM) level of a DDM pyramid. The DDM pyramid identifies locations of data stored in the persistent storage resource of the deduplication system. The method further determines a first false positive rate target for a first index summary (IS) level of an index pyramid based on a memory footprint for the first IS level and an aggregate false positive rate target for the index pyramid. The first IS level accelerates lookup into the first DDM level. The first false positive rate target indicates a rate that a hit for a value found in the first IS level is not found in the first DDM level. The method also generates the first IS level with a first false positive rate based on the determined first false positive rate target.

Claims

1. A deduplication system, comprising:

a persistent storage resource;

a volatile memory; and

a processing device, operatively coupled to the persistent storage resource and the volatile memory, to;

generate a first deduplication map (DDM) level of a DDM pyramid, wherein the DDM pyramid identifies locations of data stored in the persistent storage resource of the deduplication system;

determine a first false positive rate target for a first index summary (IS) level of an index pyramid based on a memory footprint for the first IS level and an aggregate false positive rate target for the index pyramid, wherein the first IS level accelerates lookup into the first DDM level, wherein the first false positive rate target indicates a target percentage of queries into the first IS level for a value located in the first DDM level that incorrectly yields a hit; and

generate the first IS level with a first false positive rate based on the determined first false positive rate target, wherein the first false positive rate is different than a second false positive rate associated with a second IS level.

2. The deduplication system of claim 1, the processing device further to:

generate a second deduplication map (DDM) level of the DDM pyramid;

determine a second false positive rate target for the second IS level of the index pyramid based on a memory footprint of the second IS level and the aggregate false positive rate target for the index pyramid; and

generate the second IS level with the second false positive rate based on the determined second false positive rate target.

3. The deduplication system of claim 1, wherein the first DDM level of the DDM pyramid comprises first data that is evenly distributed.

4. The deduplication system of claim 1, wherein the first IS level accelerates lookup into the first DDM level by indicating a part of the value located in the first DDM level by providing an indication of location of the value in the first DDM level.

5. The deduplication system of claim 1, wherein to generate the first IS level with the first false positive rate based on the determined first false positive rate target, the processing device to:

determine a bit size for entries of the first IS level to achieve the first false positive rate target; and

generate the first IS level with the determined bit size.

6. The deduplication system of claim 1, wherein to determine the first false positive rate target for the first index summary (IS) level of the index pyramid based on the memory footprint for the first IS level and the aggregate false positive rate target for the index pyramid, the processing device to:

estimate a size of the first IS level based on the first DDM level;

determine a location to store the first IS level is in the volatile memory or outside the volatile memory; and

determine the aggregate false positive rate target for the index pyramid, wherein the aggregate false positive rate target for the index pyramid indicates a target percentage for an aggregate of false positive rates for a plurality of IS levels of the index summary, wherein the plurality of IS levels of the index summary comprises the first IS level and a second IS level; and

determine the first false positive rate target for the first IS level based on the estimated size of the first IS level, the determined location to store the first IS level, and the determined aggregate false positive rate target.

7. The deduplication system of claim 1, wherein the persistent storage resource is flash memory.

8. The deduplication system of claim 1, wherein the first index summary level is a Bloom filter.

9. A method comprising:

generating a first deduplication map (DDM) level of a DDM pyramid;

determining, by a processing device, a first false positive rate target for a first index summary (IS) level of an index pyramid based on a memory footprint for the first IS level and an aggregate false positive rate target for the index pyramid, wherein the first IS level accelerates lookup into the first DDM level, wherein the first false positive rate target indicates a target percentage of queries into the first IS level for a value located in the first DDM level that incorrectly yields a hit; and

generating, by the processing device, the first IS level with a first false positive rate based on the determined first false positive rate target, wherein the first false positive rate is different than a second false positive rate associated with a second IS level.

10. The method of claim 9, further comprising:

generating a second deduplication map (DDM) level of the DDM pyramid;

determining a second false positive rate target for the second IS level of the index pyramid based on a memory footprint of the second IS level and the aggregate false positive rate target for the index pyramid; and

generating the second IS level with the second false positive rate based on the determined second false positive rate target.

11. The method of claim 9, wherein the first DDM level of the DDM pyramid comprises first data that is evenly distributed.

12. The method of claim 9, wherein the first IS level accelerates lookup into the first DDM level by indicating a part of a value located in the first DDM level or by providing an indication of location of the value in the first DDM level.

13. The method of claim 9, wherein generating the first IS level with the first false positive rate based on the determined first false positive rate target, the method further comprises:

determining a bit size for entries of the first IS level to achieve the first false positive rate target; and

generating the first IS level with the determined bit size.

14. The method of claim 9, wherein determining the first false positive rate target for the first index summary (IS) level of the index pyramid based on the memory footprint for the first IS level and the aggregate false positive rate target for the index pyramid, the method further comprising:

estimating a size of the first IS level based on the first DDM level;

determining a location to store the first IS level is in a volatile memory or outside the volatile memory; and

determining the aggregate false positive rate target for the index pyramid, wherein the aggregate false positive rate target for the index pyramid indicates a target percentage for an aggregate of false positive rates for a plurality of IS levels of the index summary, wherein the plurality of IS levels of the index summary comprises the first IS level and a second IS level; and

determining the first false positive rate target for the first IS level based on the estimated size of the first IS level, the determined location to store the first IS level, and the determined aggregate false positive rate target.

15. The method of claim 9, wherein the first index summary level is a Bloom filter.

16. A non-transitory computer-readable medium to store instructions that, when executed by a processing device, cause the processing device to:

generate, by the processing device, a first deduplication map (DDM) level of a DDM pyramid, wherein the DDM pyramid identifies locations of data stored in the persistent storage resource of the deduplication system;

determine a first false positive rate target for a first index summary (IS) level of an index pyramid based on a memory footprint for the first IS level and an aggregate false positive rate target for the index pyramid, wherein the first IS level accelerates lookup into the first DDM level, wherein the first false positive rate target indicates a target percentage of queries into the first IS level for a value located in the first DDM level that incorrectly yields a hit; and

generate the first IS level with a first false positive rate based on the determined first false positive rate target, wherein the first false positive rate is different than a second false positive rate associated with a second IS level.

17. The non-transitory computer-readable medium of claim 16, the processing device further to:

generate a second deduplication map (DDM) level of the DDM pyramid;

determine a the second false positive rate target for a the second IS level of the index pyramid based on a memory footprint of the second IS level and the aggregate false positive rate target for the index pyramid; and

generate the second IS level with a the second false rate based on the determined second false positive rate target, wherein the second false positive rate is different than the first false positive rate.

18. The non-transitory computer-readable medium of claim 16, wherein to generate the first IS level with the first false positive rate based on the determined first false positive rate target, the processing device to:

determine a bit size for entries of the first IS level to achieve the first false positive rate target; and

generate the first IS level with the determined bit size.

19. The non-transitory computer-readable medium of claim 16, wherein to determine the first false positive rate target for the first index summary (IS) level of the index pyramid based on the memory footprint for the first IS level and the aggregate false positive rate target for the index pyramid, the processing device to:

estimate a size of the first IS level based on the first DDM level;

determine a location to store the first IS level is in the volatile memory or outside the volatile memory; and

determine the aggregate false positive rate target for the index pyramid, wherein the aggregate false positive rate target for the index pyramid indicates a target percentage for an aggregate of false positive rates for a plurality of IS levels of the index summary, wherein the plurality of IS levels of the index summary comprises the first IS level and a second IS level; and

determine the first false positive rate target for the first IS level based on the estimated size of the first IS level, the determined location to store the first IS level, and the determined aggregate false positive rate target.

20. The non-transitory computer-readable medium of claim 16, wherein the first index summary level is a Bloom filter.