Multipass programming in buffers implemented in non-volatile data storage systems

• US 9,043,517 B1
• Filed: 09/24/2013
• Issued: 05/26/2015
• Est. Priority Date: 07/25/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Sprouse, Steven, Li, Yan
• Primary Examiner(s): RHU, KRIS M
• Application Number:
  US14/035,876
• Time in Patent Office: 609 Days
• Field of Search: None
• US Class Current: 710/62
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7202 Allocation control and policies

Abstract

The various implementations described herein include systems, methods and/or devices used to enable multipass programming in buffers implemented in non-volatile data storage systems (e.g., using one or more flash memory devices). In one aspect, a portion of memory (e.g., a page in a block of a flash memory device) may be programmed many (e.g., 1000) times before an erase is required. Some embodiments include systems, methods and/or devices to integrate Bloom filter functionality in a non-volatile data storage system, where a portion of memory storing one or more bits of a Bloom filter array may be programmed many (e.g., 1000) times before the contents of the portion of memory need to be moved to an unused location in the memory.

Claims

1. A data processing method, comprising:

at a non-volatile data storage system;

receiving from a 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 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; and

wherein setting a respective bit position of the k bit positions in the Bloom filter comprises;

accessing usage information for a storage medium portion of the non-volatile storage medium that includes the respective bit position in the Bloom filter;

determining whether the usage information for the storage medium portion meets predefined multipass programming criteria;

in accordance with a determination that the usage information for the storage medium portion meets the predefined multipass programming criteria, setting the respective bit position in the Bloom filter in the storage medium portion; and

in accordance with a determination that the usage information for the storage medium portion does not meet the predefined multipass programming criteria, identifying a respective unused portion of the non-volatile storage medium, copying Bloom filter information in the storage medium portion to the identified portion of the non-volatile storage medium, and setting the respective bit position in the Bloom filter.

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, further comprising:

in accordance with a determination that the usage information for the storage medium portion does not meet the predefined multipass programming criteria, scheduling erasure of the storage medium portion of the non-volatile storage medium.

5. The method of claim 4, wherein the scheduling erasure of the storage medium portion is performed after setting the respective bit position in the Bloom filter.

6. The method of claim 1, wherein the determining whether the usage information for the storage medium portion meets predefined multipass programming criteria comprises:

determining whether the usage information indicates the storage medium portion of the non-volatile data storage system has been programmed no more than m times, where m is an integer of at least 1000;

in accordance with a determination that the storage medium portion of the non-volatile data storage system has been programmed no more than m times, the usage information for the storage medium portion meets the predefined multipass programming criteria; and

in accordance with a determination that the storage medium portion of the non-volatile data storage system has been programmed more than m times, the usage information for the storage medium portion does not meet the predefined multipass programming criteria.

7. The method of claim 1, wherein setting the respective set of k bit positions in the storage medium includes out of order word line programming.

8. The method of claim 1, further comprising:

receiving an element for testing with respect to the Bloom filter;

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

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

reading the 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 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 set are not set.

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 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 a 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; and

wherein setting a respective bit position of the k bit positions in the Bloom filter comprises;

accessing usage information for a storage medium portion of the non-volatile storage medium that includes the respective bit position in the Bloom filter;

determining whether the usage information for the storage medium portion meets predefined multipass programming criteria;

in accordance with a determination that the usage information for the storage medium portion meets the predefined multipass programming criteria, setting the respective bit position in the Bloom filter in the storage medium portion; and

in accordance with a determination that the usage information for the storage medium portion does not meet the predefined multipass programming criteria, identifying a respective unused portion of the non-volatile storage medium, copying Bloom filter information in the storage medium portion to the identified portion of the non-volatile storage medium, and setting the respective bit position in the Bloom filter.

13. The system of claim 12, 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.

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 respective set of k bit positions in the Bloom filter is generated using the k parallel processors.

15. 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:

schedule erasure of the storage medium portion of the non-volatile storage medium, in accordance with a determination that the usage information for the storage medium portion does not meet the predefined multipass programming criteria.

16. The system of claim 15, wherein the instructions for scheduling erasure of the storage medium portion comprise instructions for scheduling erasure of the storage medium portion after setting the respective bit position in the Bloom filter.

17. The system of claim 12, wherein the one or more programs include instructions that, when executed by the one or more processors, cause the non-volatile data storage system to determine whether the usage information for the storage medium portion meets predefined multipass programming criteria, by:

determining whether the usage information indicates the storage medium portion of the non-volatile data storage system has been programmed no more than m times, where m is an integer of at least 1000;

in accordance with a determination that the storage medium portion of the non-volatile data storage system has been programmed no more than m times, the usage information for the storage medium portion meets the predefined multipass programming criteria; and

in accordance with a determination that the storage medium portion of the non-volatile data storage system has been programmed more than m times, the usage information for the storage medium portion does not meet the predefined multipass programming criteria.

18. The system of claim 12, wherein the instructions for setting the respective set of k bit positions in the storage medium include instructions for out of order word line programming.

19. 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 an element for testing with respect to the Bloom filter;

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

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

reading the 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 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 set are not set.

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 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 a 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; and

wherein setting a respective bit position of the k bit positions in the Bloom filter comprises;

accessing usage information for a storage medium portion of the non-volatile storage medium that includes the respective bit position in the Bloom filter;

determining whether the usage information for the storage medium portion meets predefined multipass programming criteria;

in accordance with a determination that the usage information for the storage medium portion meets the predefined multipass programming criteria, setting the respective bit position in the Bloom filter in the storage medium portion; and

in accordance with a determination that the usage information for the storage medium portion does not meet the predefined multipass programming criteria, identifying a respective unused portion of the non-volatile storage medium, copying Bloom filter information in the storage medium portion to the identified portion of the non-volatile storage medium, and setting the respective bit position in the Bloom filter.

24. The non-transitory computer readable storage medium of claim 23, 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.

25. 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:

schedule erasure of the storage medium portion of the non-volatile storage medium, in accordance with a determination that the usage information for the storage medium portion does not meet the predefined multipass programming criteria.

26. The non-transitory computer readable storage medium of claim 25, wherein the instructions for scheduling erasure of the storage medium portion comprise instructions for scheduling erasure of the storage medium portion after setting the respective bit position in the Bloom filter.

27. The non-transitory computer readable storage medium of claim 23, wherein the one or more programs include instructions that, when executed by the one or more processors, cause the non-volatile data storage system to determine whether the usage information for the storage medium portion meets predefined multipass programming criteria, by:

determining whether the usage information indicates the storage medium portion of the non-volatile data storage system has been programmed no more than m times, where m is an integer of at least 1000;

in accordance with a determination that the storage medium portion of the non-volatile data storage system has been programmed no more than m times, the usage information for the storage medium portion meets the predefined multipass programming criteria; and

in accordance with a determination that the storage medium portion of the non-volatile data storage system has been programmed more than m times, the usage information for the storage medium portion does not meet the predefined multipass programming criteria.

28. The non-transitory computer readable storage medium of claim 23, wherein the instructions for setting the respective set of k bit positions in the storage medium include instructions for out of order word line programming.

29. 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 an element for testing with respect to the Bloom filter;

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

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

reading the 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 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 set are not set.

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