Bloom filters in a flash memory

• US 10,353,607 B2
• Filed: 09/28/2018
• Issued: 07/16/2019
• 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:
  US16/146,584
• Publication Number:
  US 20190034100A1
• Time in Patent Office: 291 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;

storing a record in memory, wherein the memory is separate from the flash memory, the record including a plurality of entries, each entry corresponding to a portion of the Bloom filter;

when one of the plurality of entries in the record is full, identifying bits to be set in the Bloom filter from the full entry;

overwriting the portion of the Bloom filter corresponding to the full entry in the record in order to set the identified bits.

2. The method of claim 1, further comprising, when one of the plurality of entries in the record is full, identifying all bits in all of the plurality of entries in the record to be set in the Bloom filter and overwriting the portion of the Bloom filter corresponding to all entries in the record.

3. The method of claim 1, further comprising performing garbage collection using the Bloom filter.

4. The method of claim 1, further comprising performing deduplication of data using the Bloom filter.

5. The method of claim 1, further comprising making a call to the flash memory to perform the overwriting, wherein the call is specified by a client such that the client controls how the overwriting is performed.

6. The method of claim 5, wherein the call includes one of a logical OR or a Compare and Swap overwrite operation.

7. The method of claim 1, wherein each entry in the record corresponds to a page in the flash memory.

8. 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;

storing a record in memory that is separate from the flash memory, wherein the record is configured to store updates to the Bloom filter in a plurality of entries, each entry corresponding to a portion of the Bloom filter;

identifying bits in the record to be set in the Bloom filter from the plurality of entries in a batch update;

overwriting the portion of the Bloom filter corresponding to identified bits in the record during a batch update in order to set the identified bits in the Bloom filter.

9. The method of claim 8, wherein the identified bits include at least bits in an entry in the record that is full, further comprising, overwriting the portion of the Bloom filter corresponding to all entries in the record.

10. The method of claim 9, further comprising clearing the identified bits from the record.

11. The method of claim 8, further comprising performing garbage collection using the Bloom filter or a deduplication operation using the Bloom filter.

12. The method of claim 8, further comprising sorting pluralities of entries in the record.

13. The method of claim 8, wherein the plurality of entries each include an offset and each entry includes a bucket that is associated with a portion of the Bloom filter.

14. The method of claim 8, further comprising, when a new element is to be inserted into the Bloom filter, determining bits to set in the Bloom filter and recording those bits in the record.

15. The method of claim 8, further comprising making a call to the flash memory to perform the overwriting, wherein the call is specified by a client such that the client controls how the overwriting is performed.

16. The method of claim 15, wherein the call includes one of a logical OR or a Compare and Swap overwrite operation.

17. The method of claim 8, wherein each entry in the record corresponds to a page in the flash memory.

18. A method for implementing a data structure in a flash memory, the method comprising:

establishing a data structure in the flash memory, wherein the data structure includes a plurality of pages of the flash memory and wherein all bits in the data structure are initially unset;

storing a record in memory that is separate from the flash memory, wherein the record is configured to store updates to the data structure in a plurality of entries, each entry corresponding to a portion of the data structure;

identifying bits in the record to be set in the data structure from the plurality of entries in a batch update;

overwriting the portion of the data structure corresponding to identified bits in the record during a batch update in order to set the identified bits in the Bloom filter.

19. The method of claim 18, wherein the data structure is one of a Bloom filter, a linked list, a hash table, a locking data structure, a tree, or a graph.

20. The method of claim 18, wherein the portion of the data structure corresponds to a page of the flash memory.