Local hash value generation in non-volatile data storage systems
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification