Generating and optimizing summary index levels in a deduplication storage system
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20)
-
Specification