Local hash value generation in non-volatile data storage systems

• US 9,524,235 B1
• Filed: 09/24/2013
• Issued: 12/20/2016
• Est. Priority Date: 07/25/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Sprouse, Steven
• Primary Examiner(s): Bradley, Matthew
• Application Number:
  US14/035,869
• Time in Patent Office: 1,183 Days
• Field of Search: 711/103
• US Class Current: 1/1
• CPC Class Codes: G06F 13/12 using hardware independent of the central processor, e.g. channel or peripheral processor
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• 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 enable local hash value generation in a non-volatile data storage system (e.g., using a flash memory device). In one aspect, rather than having Bloom filter logic in a host, Bloom filter functionality is integrated in the non-volatile data storage system. In some implementations, at a non-volatile data storage system, the method includes receiving from a host a plurality of requests that specify respective elements. The method further includes, for each respective element specified by the received requests, (1) generating a respective set of k bit positions in a Bloom filter, using k distinct hash functions, where k is an integer greater than 2, and (2) setting the respective set of k bit positions in the Bloom filter, which is stored in a non-volatile storage medium of the non-volatile data storage system.

Claims

1. A data processing method, comprising:

at a memory controller in a non-volatile data storage system;

receiving from a computer system, external to the non-volatile data storage system, a plurality of requests that specify respective elements to be stored in the non-volatile data storage system;

for each respective element received from the computer system specified by the received requests;

generating a respective set of k bit positions in a Bloom filter, using k distinct hash functions, where k is an integer greater than 2; and

setting the respective set of k bit positions in the Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system;

receiving from the computer system a first element for testing with respect to the Bloom filter; and

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

processing the first element with the k distinct hash functions to generate a first set of k bit positions;

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

returning a first result in accordance with a determination that all the k bit positions in the Bloom filter from the first set are set; and

returning a second result in accordance with a determination that one or more of the k bit positions in the Bloom filter from the first set are not set.

2. The method of claim 1, including generating the respective 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 generating the respective 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 non-volatile storage medium comprises one or more flash memory devices.

5. The method of claim 1, wherein the respective elements specified by the plurality of requests comprise a plurality of objects.

6. The method of claim 1, wherein the respective elements specified by the plurality of requests comprise n-bit fingerprints of a plurality of objects, where n is at least 64.

7. 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 a memory controller in the non-volatile data storage system to;

receive from a computer system, external to the non-volatile data storage system, a plurality of requests that specify respective elements to be stored in the non-volatile data storage system;

for each respective element received from the computer system specified by the received requests;

generate a respective set of k bit positions in the Bloom filter, using k distinct hash functions, where k is an integer greater than 2; and

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

receive from the computer system a first element for testing with respect to the Bloom filter; and

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

processing the first element with the k distinct hash functions to generate a first set of k bit positions;

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

returning a first result in accordance with a determination that all the k bit positions in the Bloom filter from the first set are set; and

returning a second result in accordance with a determination that one or more of the k bit positions in the Bloom filter from the first set are not set.

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

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

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

11. The system of claim 7, wherein the respective elements specified by the plurality of requests comprise a plurality of objects.

12. The system of claim 7, wherein the respective elements specified by the plurality of requests comprise n-bit fingerprints of a plurality of objects, where n is at least 64.

13. 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 a memory controller in the non-volatile data storage system to:

receive from a computer system, external to the non-volatile data storage system, a plurality of requests that specify respective elements to be stored in the non-volatile data storage system;

for each respective element received from the computer system specified by the received requests;

generate a respective set of k bit positions in the Bloom filter, using k distinct hash functions, where k is an integer greater than 2; and

set the respective set of k bit positions in the Bloom filter, wherein the Bloom filter is stored in a non-volatile storage medium of the non-volatile data storage system;

receive from the computer system a first element for testing with respect to the Bloom filter; and

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

processing the first element with the k distinct hash functions to generate a first set of k bit positions;

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

returning a first result in accordance with a determination that all the k bit positions in the Bloom filter from the first set are set; and

returning a second result in accordance with a determination that one or more of the k bit positions in the Bloom filter from the first set are not set.

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

15. The non-transitory computer readable storage medium of claim 13, wherein the one or more processors of the non-volatile data storage system comprise k parallel processors, and the respective set of k bit positions in the Bloom filter is generated using the k parallel processors.

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

17. The non-transitory computer readable storage medium of claim 13, wherein the respective elements specified by the plurality of requests comprise a plurality of objects.

18. The non-transitory computer readable storage medium of claim 13, wherein the respective elements specified by the plurality of requests comprise n-bit fingerprints of a plurality of objects, where n is at least 64.