INDEX SEARCHING USING A BLOOM FILTER

• US 20130218900A1
• Filed: 02/08/2013
• Published: 08/22/2013
• Est. Priority Date: 03/10/2010
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Xie, Ying
• Granted Patent: US 8,756,238 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/328 Management therefor

Abstract

A system for index searching comprises a first index, a second index, a processor, and a memory. The processor is configured to determine, using a Bloom filter for the second index of fingerprints, whether the Bloom filter indicates that an entry corresponding to a segment has been previously stored in the second index. The processor is further configured to, in the event that the Bloom filter indicates that an entry corresponding to the segment has been previously stored in the second index, retrieve a second index entry associated with the segment that has been previously stored. The memory is coupled to the processor and configured to provide the processor with instructions.

Claims

1. A system for index searching, comprising:

a memory buffer index of fingerprints;

a second index of fingerprints;

a processor configured to;

determine whether an entry corresponding to a segment has been previously stored in the memory buffer index;

in the event that the entry corresponding to the segment has been previously stored in the memory buffer index, indicate a location of the segment is indicated based on the entry; and

in the event that the entry corresponding to the segment has not been previously stored in the memory buffer index, determine, using a Bloom filter for the second index of fingerprints, whether the Bloom filter indicates that an entry corresponding to a segment has been previously stored in the second index.

2. A system as in claim 1, wherein the processor is further configured to receive a request to retrieve the segment.

3. A system as in claim 1, wherein the processor is further configured to, in the event that the Bloom filter indicates that the entry corresponding to the segment has been previously stored in the second index, determine, using the second index, whether a second entry corresponding to the segment has been previously stored in the second index.

4. A system as in claim 3, wherein the processor is further configured to, in the event that it is determined, using the second index, that the second entry corresponding to the segment has been previously stored in the second index, indicate the location of the segment is indicated based on the second entry.

5. A system as in claim 3, wherein the processor is further configured to, in the event that it is determined, using the second index, that the second entry corresponding to the segment has not been previously stored in the second index, determine whether a third entry corresponding to the segment has been previously stored in a third index.

6. A system as in claim 5, wherein the processor is further configured to, in the event that the third entry corresponding to the segment has been previously stored in the third index, indicate the location of the segment is indicated based in the third entry.

7. A system as in claim 1, wherein the processor is further configured to, in the event that the Bloom filter indicates that the entry corresponding to the segment has not been previously stored in the second index, determine whether a third entry corresponding to the segment has been previously stored in a third index.

8. A system as in claim 7, wherein the processor is further configured to, in the event that the third entry corresponding to the segment has been previously stored in the third index, indicate the location of the segment is indicated based in the third entry.

9. A system as in claim 7, wherein the second index is transferred or merge sorted into the third index

10. A system as in claim 7, wherein the third index includes a fingerprint associated with a stored segment.

11. A system as in claim 7, wherein the third index is larger than the second index.

12. A system as in claim 1, wherein the second index is larger than the memory buffer index.

13. A system as in claim 1, wherein the memory buffer index includes a fingerprint associated with a stored segment.

14. A system as in claim 1, wherein the memory buffer index is transferred or merge sorted into the second index.

15. A system as in claim 1, wherein the second index includes a fingerprint associated with a stored segment.

16. A method for index searching, comprising:

determining whether an entry corresponding to a segment has been previously stored in the memory buffer index;

in the event that the entry corresponding to the segment has been previously stored in the memory buffer index, indicating a location of the segment is indicated based on the entry; and

in the event that the entry corresponding to the segment has not been previously stored in the memory buffer index, determining, using a Bloom filter for the second index of fingerprints, whether the Bloom filter indicates that an entry corresponding to a segment has been previously stored in the second index.

17. A method as in claim 16, further comprising in the event that the Bloom filter indicates that the entry corresponding to the segment has been previously stored in the second index, determining, using the second index, whether a second entry corresponding to the segment has been previously stored in the second index.

18. A method as in claim 17, further comprising in the event that it is determined, using the second index, that the second entry corresponding to the segment has been previously stored in the second index, indicating the location of the segment is indicated based on the second entry.

19. A method as in claim 17, further comprising in the event that it is determined, using the second index, that the second entry corresponding to the segment has not been previously stored in the second index, determining whether a third entry corresponding to the segment has been is previously stored in a third index.

20. A computer program product for index searching, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

determining whether an entry corresponding to a segment has been previously stored in the memory buffer index;

in the event that the entry corresponding to the segment has been previously stored in the memory buffer index, indicating a location of the segment is indicated based on the entry; and

in the event that the entry corresponding to the segment has not been previously stored in the memory buffer index, determining, using a Bloom filter for the second index of fingerprints, whether the Bloom filter indicates that an entry corresponding to a segment has been previously stored in the second index.