Bloom filters in a flash memory

• US 10,089,025 B1
• Filed: 06/29/2016
• Issued: 10/02/2018
• Est. Priority Date: 06/29/2016
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Wallace, Grant R., Shilane, Philip N.
• Primary Examiner(s): Chappell, Daniel C
• Application Number:
  US15/196,196
• Time in Patent Office: 825 Days
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G11C 16/08 Address circuits; Decoders; Word-line control circuits
• CPC Class Codes: G11C 16/10 Programming or data input circuits
• CPC Class Codes: G11C 16/16 for erasing blocks, e.g. arrays, words, groups
• CPC Class Codes: G11C 16/26 Sensing or reading circuits; Data output circuits
• CPC Class Codes: G11C 16/344 Arrangements for verifying correct erasure or for detecting overerased cells
• CPC Class Codes: G11C 16/3445 Circuits or methods to verify correct erasure of nonvolatile memory cells
• CPC Class Codes: G11C 16/3459 Circuits or methods to verify correct programming of nonvolatile memory cells

Abstract

Systems and methods for managing content in a flash memory. A data structure such as a Bloom filter is implemented in flash memory such that updates to the data can be performed by overwriting pages in the memory.

Claims

1. A method for implementing a Bloom filter in a flash memory, the method comprising:

establishing a Bloom filter in the flash memory, wherein the Bloom filter includes a plurality of pages and wherein all bits in the Bloom filter are initially unset, wherein the flash memory includes a controller and an external interface that allows calls to be made to the flash memory and allows a client to specify how the calls are performed in the flash memory by the controller;

storing elements into the Bloom filter such that some of the bits in the Bloom filter are set and such that some of the bits in the Bloom filter are unset;

identifying bits to be set in the Bloom filter for the element; and

overwriting pages associated with the identified bits in order to set the identified bits, wherein overwriting the pages is performed by the controller in the flash memory as specified by a call from the client to the external interface when determining that the overwrite only sets bits in the pages, wherein overwriting is not performed when determining that the overwrite requires unsetting bits in the pages.

2. The method of claim 1, further comprising performing a logical OR when overwriting the pages, wherein contents of the pages are logically ORed with pages that include 0s except at locations corresponding to the identified bits, which are 1s.

3. The method of claim 2, further comprising reading the pages into memory, setting the identified bits in the pages in the memory and performing a logical OR between the updated pages in memory and the pages in the Bloom filter in the flash memory.

4. The method of claim 1, further comprising issuing a logical OR call to the flash memory to overwrite the pages and insert the element into the Bloom filter.

5. The method of claim 1, further comprising locking the pages before overwriting the pages.

6. The method of claim 1, further comprising batching multiple insertions of elements in memory and inserting the elements during a single update to the Bloom filter.

7. The method of claim 6, wherein the insertions are stored in buckets and wherein full buckets are applied to the Bloom filter.

8. A method for updating a Bloom filter stored in a flash memory wherein the flash memory includes a controller and an external interface that allows calls to be made to the flash memory, the method comprising:

storing updates to the Bloom filter in an in-memory record that is separate from the flash memory, where the record includes a plurality of buckets and wherein each update identifies a location in the Bloom filter; and

when one of the buckets is full, applying the updates in the full bucket to the Bloom filter by overwriting a page in the Bloom filter corresponding to the full bucket, wherein overwriting a page sets bits in the page of the Bloom filter corresponding to the locations identified in the full bucket,

wherein the page in the Bloom filter is only overwritten when the updates cause one or more bits in the page to be set, wherein the page in the Bloom filter is not overwritten when the updates cause would cause one or more of the bits in the page to be unset, and

wherein the updates to the flash memory are applied by the controller in accordance with a call to the external interface, wherein the external interface allows a client to specify how the call is performed by the controller in the flash memory.

9. The method of claim 8, wherein each bucket includes a fixed number of offset entries.

10. The method of claim 9, wherein each bucket corresponds to a page of the Bloom filter and wherein each offset entry in the bucket corresponds to a bit in the page.

11. The method of claim 9, wherein applying the updates further comprises sending a request to the flash memory, wherein the flash memory overwrites the page in accordance with the request.

12. The method of claim 11, wherein the flash memory overwrites the page by:

reading the page in the Bloom filter;

determining whether the request only requires bits in the page to be set; and

overwriting the page with the updates when only sets are required, wherein a set changes a 0 to a 1.

13. The method of claim 11, further comprising overwriting the page by performing a logical OR with the page.

14. The method of claim 11, further comprising locking the page while the page is overwritten with the updates.

15. The method of claim 8, further comprising batching lookups into the Bloom filter by arranging lookup requests based on offsets such that the lookups are performed in groups based on the Bloom filter page the group references in the Bloom filter.

16. A method for managing elements in a set, wherein membership in the set is determined using a Bloom filter implemented in a flash memory, wherein the flash memory includes a controller and an external interface that allows calls to be made to the flash memory, the method comprising:

inserting an element into the set by;

performing one or more functions on a key associated with the element to identify locations in the Bloom filter to be set, wherein each function identifies at least one location;

adding each location to be set to a record in memory, wherein the memory is separate from the flash memory, wherein the record includes a plurality of buckets and each bucket corresponds to a page in the Bloom filter, wherein the locations are added to the buckets as offsets into pages; and

when a bucket is full or at a predetermined time, updating the Bloom filter based on the bucket, wherein the page of the Bloom filter corresponding to the bucket includes set bits and unset bits, wherein the page of the Bloom filter corresponding to the bucket is updated by overwriting the page such that locations in the page identified in the bucket are set and as long as only bits in the page are set when overwriting the page,

wherein the updates to the flash memory are applied by the controller in accordance with a call to the external interface, wherein the external interface allows a client to specify how the call is performed by the controller in the flash memory.

17. The method of claim 16, further comprising updating the Bloom filter by issuing a call to the flash memory, the call including one of a logical OR call or a swap and compare call.

18. The method of claim 16, wherein the flash memory includes a controller configured to overwrite the page with the updates by setting bits at the location by performing a logical OR between the page and a page that includes 0s except at the locations being set.

19. The method of claim 18, wherein the flash memory includes a controller configured to overwrite the page with the updates by reading the pages into memory, setting the identified bits in the pages in the memory and performing a logical OR between the updated pages in memory and the pages in the Bloom filter in the flash memory.

20. The method of claim 16, further comprising locking the page during the update process that overwrites the page in the Bloom filter with the updates from the bucket.

21. The method of claim 16, wherein the Bloom filter includes a plurality of pages whose size depends on how the flash memory writes to the memory, wherein one or more pages can be overwritten at the same time using updates from one or more corresponding buckets.

22. The method of claim 16, further comprising overwriting the page by comparing the page with the updates, wherein the updates are included in a page that includes all zeros except for locations corresponding to the offsets, and overwriting the page when only sets are required to insert the updates into the page.