Extendible repeated data detection method

Abstract

The invention discloses an extendible repeated data detection method, belongs to the technical field of computer storage, and solves the problem that in the existing repeated data detecting method, the storage capacity cannot be efficiently extended, so as to meet the requirements of the current situation that the storage demand increases and repeatedly deleted systems need upgrading and updating. The extendible repeated data detection method comprises the following steps: partitioning processing, fingerprint extraction, retrieving of Bloom filters, retrieving of fingerprint subset table, judgment of unfulfilled Bloom filters, new fingerprint marking, judgment of Bloom filter quantity, and extending of Bloom filter array. In the invention, the Bloom filter array is used to retrieve the fingerprint data, so as to quickly locate the retrieval range, improve the retrieval efficiency and realize detection on the repeated data; the extendible repeated data detection method is high in expansibility and querying performance, can support element location and control the misjudgment rate, and further can effectively reduce the memory overhead. The Bloom filter array is composed of a series of isomorphic Bloom filters, so that once the misjudgment rate epsilon' and the pre-established retrieving fingerprint total quantity nmax are provided, the quantity of the required Bloom filters and the number of the hush functions can be worked out.

Description

technical field [0001] The invention belongs to the technical field of computer storage, and in particular relates to an expandable repeated data detection method. Background technique [0002] In 1998, Jim Gray concluded in his speech when he was awarded the Computer Turing Award that "the information industry has grown exponentially in the past 100 years", and proposed a new empirical law based on "Moore's Law" that "in the future, every 18 months the world will increase Storage capacity is the sum of all storage capacity ever created". Since 2007, IDC and EMC have cooperated to release information storage market research reports for five consecutive years. The estimated data shows that the total amount of digital information created and copied worldwide has increased from 161EB (exabytes) in 2006 to 1.8ZB (zettabytes) in 2011. ), the total amount of global digital information exceeded the available storage capacity for the first time in 2007, and the difference between t...

AI Technical Summary

Problems solved by technology

[0029] The present invention provides an expandable duplicate data detection method, which solves the problem that the storage capacity cannot be expanded efficiently in the existing duplicate data detection method, so as to adapt to the continuous expansion of storage requirements, and the deduplication system is facing the status quo of continuous upgrading.

Images