Methods and systems to avoid false negative results in bloom filters implemented in non-volatile data storage systems

• US 9,384,126 B1
• Filed: 09/24/2013
• Issued: 07/05/2016
• Est. Priority Date: 07/25/2013
• Status: Expired due to Fees

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Inventors: Sprouse, Steven, Li, Yan
• Primary Examiner(s): Bradley, Matthew
• Application Number:
  US14/035,883
• Time in Patent Office: 1,015 Days
• Field of Search: 711/103
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 13/12 using hardware independent of the central processor, e.g. channel or peripheral processor
• CPC Class Codes: G06F 2212/702 Conservative garbage collection
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The various implementations described herein include systems, methods and/or devices used to avoid false negative results in Bloom filters implemented in non-volatile data storage systems. In one aspect, if an element is added to a Bloom filter using k hash functions, instead of requiring all k bits to be set before returning a positive result (e.g., indicating that the element is most likely present in the Bloom filter), the embodiments described herein return a positive result when at least k minus x (k−x) bit positions are set in the Bloom filter, where x is an integer greater than zero and less than k. In some embodiments, additional measures to avoid false negatives include performing a read check immediately after setting the k bits in the Bloom filter and/or using a conservative reading threshold voltage.

Claims

1. A data processing method, comprising:

at a non-volatile data storage system;

receiving from a host a first element for testing with respect to a Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system;

testing whether the first element is present in the Bloom filter, by;

processing the first element with k distinct hash functions to generate a first set of k bit positions in the Bloom filter, where k is an integer greater than 2;

reading the first set of k bit positions from the Bloom filter;

returning a first result in accordance with a determination that at least k minus x (k−

x) bit positions in the Bloom filter from the first set are set, where x is an integer greater than zero and less than k; and

returning a second result in accordance with a determination that y or more of the k bit positions in the Bloom filter from the first set are not set, where y is equal to x plus one (x+1).

2. The method of claim 1, including processing the first element with k distinct hash functions to generate the first set of k bit positions in the Bloom filter using one or more processors of the non-volatile data storage system.

3. The method of claim 1, including processing the first element with k distinct hash functions to generate the first set of k bit positions in the Bloom filter using k parallel processors of the non-volatile data storage system.

4. The method of claim 1, wherein the first element comprises an object.

5. The method of claim 1, wherein the first element comprises an n-bit fingerprint of an object, where n is at least 64.

6. The method of claim 1, further comprising:

at the non-volatile data storage system;

receiving from the host a plurality of requests that specify respective elements; and

for each respective element specified by the received requests;

generating a respective set of k bit positions in the Bloom filter, using the k distinct hash functions; and

setting the respective set of k bit positions in the Bloom filter.

7. The method of claim 6, further comprising:

after setting the respective set of k bit positions in the Bloom filter, performing a read check on the respective set of k bit positions in the Bloom filter to produce a read check result; and

in accordance with a determination that the read check result fails to meet predefined success criteria, performing a remedial action for the respective set of k bit positions in the Bloom filter.

8. The method of claim 1, wherein reading the first set of k bit positions from the Bloom filter comprises reading the first set of k bit positions from the Bloom filter using a reading threshold voltage that is less than a default reading threshold voltage for reading data from the non-volatile storage medium of the non-volatile data storage system.

9. The method of claim 1, wherein the non-volatile storage medium comprises one or more flash memory devices.

10. The method of claim 1, wherein the non-volatile data storage system is distinct from the host.

11. The method of claim 1, wherein the non-volatile data storage system is embedded in the host.

12. A non-volatile data storage system, comprising:

a non-volatile storage medium storing a Bloom filter;

one or more processors; and

memory storing one or more programs, which when executed by the one or more processors cause the non-volatile data storage system to;

receive from a host a first element for testing with respect to a Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system;

test whether the first element is present in the Bloom filter, by;

processing the first element with k distinct hash functions to generate a first set of k bit positions in the Bloom filter, where k is an integer greater than 2;

reading the first set of k bit positions from the Bloom filter;

returning a first result in accordance with a determination that at least k minus x (k−

x) bit positions in the Bloom filter from the first set are set, where x is an integer greater than zero and less than k; and

returning a second result in accordance with a determination that y or more of the k bit positions in the Bloom filter from the first set are not set, where y is equal to x plus one (x+1).

13. The system of claim 12, wherein the first set of k bit positions in the Bloom filter is generated using the one or more processors of the non-volatile data storage system.

14. The system of claim 12, wherein the one or more processors of the non-volatile data storage system comprise k parallel processors, and the first set of k bit positions in the Bloom filter is generated using the k parallel processors.

15. The system of claim 12, wherein the first element comprises an object.

16. The system of claim 12, wherein the first element comprises an n-bit fingerprint of an object, where n is at least 64.

17. The system of claim 12, wherein the one or more programs further include instructions that, when executed by the one or more processors, cause the non-volatile data storage system to:

receive from the host a plurality of requests that specify respective elements; and

for each respective element specified by the received requests;

generate a respective set of k bit positions in the Bloom filter, using the k distinct hash functions; and

set the respective set of k bit positions in the Bloom filter.

18. The system of claim 17, wherein the one or more programs further include instructions that, when executed by the one or more processors, cause the non-volatile data storage system to:

perform, after setting the respective set of k bit positions in the Bloom filter, a read check on the respective set of k bit positions in the Bloom filter to produce a read check result; and

perform, in accordance with a determination that the read check result fails to meet predefined success criteria, a remedial action for the respective set of k bit positions in the Bloom filter.

19. The system of claim 12, wherein reading the first set of k bit positions from the Bloom filter comprises reading the first set of k bit positions from the Bloom filter using a reading threshold voltage that is less than a default reading threshold voltage for reading data from the non-volatile storage medium of the non-volatile data storage system.

20. The system of claim 12, wherein the non-volatile storage medium comprises one or more flash memory devices.

21. The system of claim 12, wherein the non-volatile data storage system is distinct from the host.

22. The system of claim 12, wherein the non-volatile data storage system is embedded in the host.

23. A non-transitory computer readable storage medium storing one or more programs configured for execution by one or more processors of a non-volatile data storage system, the one or more programs comprising instructions for causing the non-volatile data storage system to:

receive from a host a first element for testing with respect to a Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system;

test whether the first element is present in the Bloom filter, by;

processing the first element with k distinct hash functions to generate a first set of k bit positions in the Bloom filter, where k is an integer greater than 2;

reading the first set of k bit positions from the Bloom filter;

returning a first result in accordance with a determination that at least k minus x (k−

x) bit positions in the Bloom filter from the first set are set, where x is an integer greater than zero and less than k; and

returning a second result in accordance with a determination that y or more of the k bit positions in the Bloom filter from the first set are not set, where y is equal to x plus one (x+1).

24. The non-transitory computer readable storage medium of claim 23, wherein the first set of k bit positions in the Bloom filter is generated using the one or more processors of the non-volatile data storage system.

25. The non-transitory computer readable storage medium of claim 23, wherein the first element comprises an object.

26. The non-transitory computer readable storage medium of claim 23, wherein the first element comprises an n-bit fingerprint of an object, where n is at least 64.

27. The non-transitory computer readable storage medium of claim 23, wherein the one or more programs further include instructions that, when executed by the one or more processors, cause the non-volatile data storage system to:

receive from the host a plurality of requests that specify respective elements; and

for each respective element specified by the received requests;

generate a respective set of k bit positions in the Bloom filter, using the k distinct hash functions; and

set the respective set of k bit positions in the Bloom filter.

28. The non-transitory computer readable storage medium of claim 27, wherein the one or more programs further include instructions that, when executed by the one or more processors, cause the non-volatile data storage system to:

perform, after setting the respective set of k bit positions in the Bloom filter, a read check on the respective set of k bit positions in the Bloom filter to produce a read check result; and

perform, in accordance with a determination that the read check result fails to meet predefined success criteria, a remedial action for the respective set of k bit positions in the Bloom filter.

29. The non-transitory computer readable storage medium of claim 23, wherein reading the first set of k bit positions from the Bloom filter comprises reading the first set of k bit positions from the Bloom filter using a reading threshold voltage that is less than a default reading threshold voltage for reading data from the non-volatile storage medium of the non-volatile data storage system.

30. The non-transitory computer readable storage medium of claim 23, wherein the non-volatile storage medium comprises one or more flash memory devices.