Systems and methods for set membership matching
AssigneeRed Hat, Inc.
InventorHuamin Chen
Life of this patent
Estimating the term…
Abstract
Various examples are directed to systems and methods for matching a test data block to a data block set. A computing device may receive the test data block. The computing device may determine that a first filter describing a first data block subset of the data block set indicates that the test data block is not in the first data block subset and determine that a second filter describing a second data block subset of the data block set indicates that the test data block is in the second data block subset. An average reference frequency of the second data block subset may be less than an average reference frequency of the first data block subset. The computing device may verify that the test data block is in the second data block subset and return an indication that the test data block is in the data block set.
Claims20
A method for deduplicating data blocks in a virtual machine environment, comprising:
- receiving, by a hypervisor executing at a computing device and from a virtual machine executing at the computing device, a write request comprising a logical name of a first data structure and a test data block, wherein the computing device comprises at least one processor and a data storage device in communication with the at least one processor, and wherein a data block set is stored at the data storage device;
- applying, by the hypervisor, a first set of hash functions to the test data block to generate a first set of test data block hash values;
- comparing, by the hypervisor, the first set of test data block hash values to a first filter bit vector describing a first data block subset of data blocks from a set of data blocks stored at the data storage device;
- determining, by the hypervisor, that the first set of test data block hash values do not match the first filter bit vector;
- applying, by the hypervisor, a second set of hash functions to the test data block to generate a second set of test data block hash values;
- comparing, by the hypervisor, the second set of test data block hash values to a second filter bit vector describing a second subset of data blocks from the set of data blocks stored at the data storage device, wherein an average reference frequency of the second subset of data blocks is less than an average reference frequency of the first data block subset;
- identifying, by the hypervisor and from the second subset of data blocks, a first equivalent data block having the same value as the test data block;
- and
- writing, by the hypervisor, an entry to a page table, the entry indicating a name of the test data block and an address of the first equivalent data block.
A computer system for deduplicating data blocks, comprising:
- at least one processor;
- a data storage device in communication with the at least one processor, wherein the data storage device comprises a data block set that comprises a plurality of data blocks and instructions that, when executed by the at least one processor, cause the at least one processor to:
- receive a write request comprising a test data block and a logical name describing at least the test data block;
- determine that a first Bloom filter describing a first data block subset of data blocks from the data block set stored at the data storage device returns a negative result for the test data block;
- determine that a second Bloom filter describing a second data block subset of data blocks from the data block set stored at the data storage device returns a positive result for the test data block, wherein an average reference frequency for the second data block subset is lower than an average reference frequency for the first data block subset;
- determine a location of an equivalent data block to the test data block at the data storage device;
- and
- write to the data storage device data associating the logical name with the location of the equivalent data block.
A method for matching a test data block to a data block set, comprising:
- receiving, by a computing device, a test data block;
- determining, by the computing device, that a first filter describing a first data block subset of the data block set indicates that the test data block is not in the first data block subset;
- determining, by the computing device, that a second filter describing a second data block subset of the data block set indicates that the test data block is in the second data block subset, wherein an average reference frequency of the second data block subset is less than an average reference frequency of the first data block subset;
- verifying, by the computing device, that the test data block is in the second data block subset;
- and
- returning, by the computing device, an indication that the test data block is in the data block set.
Dependencies are inferred from the claim text.