System and method for storing and accessing data using a plurality of probabilistic data structures

• US 8,290,972 B1
• Filed: 04/29/2009
• Issued: 10/16/2012
• Est. Priority Date: 04/29/2009
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Deshmukh, Vijay, Komatsu, Kiyoshi, Saraswat, Prashant
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): Gurmu, Muluemebet
• Application Number:
  US12/432,541
• Time in Patent Office: 1,266 Days
• Field of Search: 707/758
• US Class Current: 707/758
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

A system and method are described for storing and accessing data using a plurality of probabilistic data structures. In one embodiment, a plurality of probabilistic data structures are identified, each probabilistic data structure being associated with at least one other probabilistic data structure. The plurality of probabilistic data structures each correspond to a portion of a storage device storing a dataset. The dataset may include a plurality of values, such as a plurality of data blocks. A plurality of keys may be generated from the plurality of values, such as a plurality of fingerprints. Each key may be inserted into the probabilistic data structures which correspond to the portion of the storage device storing the value the key was generated from. The plurality of probabilistic data structures are stored in a memory and may be queried with an item to determine if the item exists in the plurality of probabilistic data structures.

Claims

1. A computer-implemented method for storing and accessing data using a plurality of probabilistic data structures, the method comprising:

identifying, by a processor, a dataset comprising a plurality of values stored on a storage device;

assembling, by a processor, a plurality of probabilistic data structures, each probabilistic data structure being associated with at least one other probabilistic data structure in the plurality of probabilistic data structures, wherein the plurality of probabilistic data structures are associated to form a tree structure comprising a plurality of ordered levels, each level being associated with at least one of the plurality of probabilistic data structures, wherein each probabilistic data structure corresponds to a portion of the storage device storing the dataset;

generating, by the processor, a plurality of keys corresponding to the plurality of values;

inserting, by the processor, each key of the plurality of keys into each probabilistic data structure that corresponds to the portion of the storage device storing the value the key was generated from;

storing, by the processor, the plurality of probabilistic data structures in memory; and

querying, by the processor, a first probabilistic data structure of the plurality of probabilistic data structures with an item to determine whether the item exists in the first probabilistic data structure, and if the item exists in the first probabilistic data structure, then querying, by the processor, a second probabilistic data structure of the plurality of probabilistic data structures with the item to determine whether the item exists in the second probabilistic data structure.

2. The method of claim 1, wherein the plurality of keys comprise of a plurality of fingerprints and the plurality of values comprise of a plurality of data blocks stored on the storage device.

3. The method of claim 1, wherein each probabilistic data structure comprises a Bloom filter.

4. The method of claim 1, further comprising:

associating, by the processor, each key and an offset identifying a location of the corresponding value on the storage device with the probabilistic data structure in a last ordered level of the plurality of ordered levels which corresponds to the portion of the storage device storing the value.

5. The method of claim 1, wherein a number of probabilistic data structures associated with each ordered level increases exponentially from level to level.

6. The method of claim 1, wherein each probabilistic data structure comprises a bit vector and at least one hash function.

7. The method of claim 6 wherein inserting each key of the plurality of keys into each probabilistic data structure of the plurality of probabilistic data structures further comprises inserting each key into each hash function of each probabilistic data structure.

8. The method of claim 6 wherein querying, by the processor, the plurality of probabilistic data structures with an item further comprises querying, by the processor, each hash function of each probabilistic data structure with the item.

9. The method of claim 6 wherein at least one hash function comprises a Message-Digest algorithm 5.

10. The method of claim 1, wherein the item comprises a fingerprint generated from a received data block.

11. The method of claim 1, wherein each probabilistic data structure is associated with a status describing a state of each probabilistic data structure.

12. The method of claim 11 further comprising:

receiving a request to remove a plurality of keys from the plurality of probabilistic data structures;

identifying a probabilistic data structure in the plurality of probabilistic data structures such that the probabilistic data structure only stores the plurality of keys; and

modifying the status of the probabilistic data structure to indicate that the plurality of keys have been removed from the probabilistic data structure.

26. The method of claim 1 wherein associated probabilistic data structures correspond to a portion of the storage device storing the same dataset.

27. The method of claim 1 wherein the portion of the storage device corresponding to the second probabilistic data structure is a subset of the portion of the storage device corresponding to the first probabilistic data structure.

13. A computer-implemented method for performing a deduplication operation using a plurality of probabilistic data structures to represent a fingerprint database, the method comprising:

identifying, by a processor, a plurality of probabilistic data structures representing a fingerprint database comprising of a plurality of fingerprints and a plurality of offsets, the plurality of offsets identifying a location of a plurality of data blocks from which the plurality of fingerprints were generated, each probabilistic data structure being associated with at least one other probabilistic data structure in the plurality of probabilistic data structures, wherein the plurality of probabilistic data structures are associated to form a tree structure comprising a plurality of ordered levels, each level being associated with at least one of the plurality of probabilistic data structures, wherein each probabilistic data structure corresponds to a portion of a storage device storing the plurality of data blocks;

generating, by the processor, a fingerprint of a received data block to be deduplicated;

querying, by the processor, a first probabilistic data structure of the plurality of probabilistic data structures with the generated fingerprint to determine if the generated fingerprint exists in the first probabilistic data structure, and if the item exists in the first probabilistic data structure, then querying, by the processor, a second probabilistic data structure of the plurality of probabilistic data structures with the generated fingerprint to determine whether the generated fingerprint exists in the second probabilistic data structure;

receiving, by the processor, an offset identifying a location of a stored data block from the plurality of probabilistic data structures, if the generated fingerprint exists in the plurality of probabilistic data structures;

retrieving, by the processor, the stored data block from the location identified by the offset;

comparing, by the processor, the stored data block with the received data block to determine if the received data block is a duplicate of the stored data block; and

deduplicating, by the processor, the received data block if the received data block is a duplicate of the stored data block.

14. The method of claim 13, wherein each probabilistic data structure comprises a Bloom filter.

15. The method of claim 13, wherein a number of probabilistic data structures associated with each ordered level increases exponentially from level to level.

16. The method of claim 13, wherein each probabilistic data structure comprises a bit vector and at least one hash function.

17. The method of claim 16 wherein querying, by the processor, the plurality of probabilistic data structures further comprises querying, by the processor, each hash function of each probabilistic data structure with the item.

18. A system for storing and accessing data using a plurality of probabilistic data structures, the system comprising:

a storage device operative to store a dataset comprising of a plurality of values;

a memory operative to store a plurality of probabilistic data structures, each probabilistic data structure being associated with at least one other probabilistic data structure in the plurality of probabilistic data structures, wherein the plurality of probabilistic data structures are associated to form a tree structure comprising a plurality of ordered levels, each level being associated with at least one of the plurality of probabilistic data structures, wherein each probabilistic data structure corresponds to a portion of the storage device storing the dataset; and

a processor operatively connected to the memory and operative to;

generate a plurality of keys corresponding to the plurality of values;

insert each key of the plurality of keys into each probabilistic data structure that corresponds to the portion of the storage device storing the value the key was generated from;

store the plurality of probabilistic data structures in the memory; and

query a first probabilistic data structure of the plurality of probabilistic data structures with an item to determine whether the item exists in the first probabilistic data structure, and if the item exists in the first probabilistic data structure, then query the second probabilistic data structure of the plurality of probabilistic data structures with the item to determine whether the item exists in the second probabilistic data structure.

19. The system of claim 18, wherein the plurality of keys comprise a plurality of fingerprints and the plurality of values corresponds to a plurality of data blocks.

20. The system of claim 18, wherein each probabilistic data structure comprises a Bloom filter.

21. The system of claim 18 wherein the processor is further operative to store each key and an offset identifying a location of the corresponding value on the storage device with the probabilistic data structure in a last ordered level of the plurality of ordered levels which corresponds to the portion of the storage device storing the value.

22. The system of claim 18, wherein each probabilistic data structure comprises a bit vector and at least one hash function.

23. The system of claim 22 wherein the processor is further operative to insert each key into each hash function of each probabilistic data structure.

24. The system of claim 22 wherein the processor is further operative to query each hash function of each probabilistic data structure with the item.

25. The system of claim 22, wherein the item comprises a fingerprint generated from a received data block.

28. A computer-implemented method for storing and accessing data using a plurality of probabilistic data structures, the method comprising:

identifying, by a processor, a dataset comprising a plurality of values stored on a storage device;

assembling, by a processor, a plurality of probabilistic data structures, each probabilistic data structure being associated with at least one other probabilistic data structure in the plurality of probabilistic data structures, wherein the plurality of probabilistic data structures are associated to form a tree structure comprising a plurality of ordered levels, each level being associated with at least one of the plurality of probabilistic data structures, wherein each probabilistic data structure corresponds to a portion of the storage device storing the dataset, wherein ordering of the probabilistic data structures corresponds to ordering of the values;

generating, by the processor, a plurality of keys corresponding to the plurality of values;

inserting, by the processor, each key of the plurality of keys into each probabilistic data structure that corresponds to the portion of the storage device storing the value the key was generated from;

storing, by the processor, the plurality of probabilistic data structures in memory; and

querying, by the processor, the plurality of probabilistic data structures with an item to determine whether the item exists in the first probabilistic data structure.

29. The method of claim 28 wherein the plurality of probabilistic data structures are stored in the memory in depth first order.