Bloom filters in a flash memory
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.
1. A method for managing a life of a flash memory, the method comprising:
establishing a data structure in the flash memory, wherein the data structure includes a plurality of bits that are initially unset;
performing a transaction in the flash memory by:
overwriting bits included in the data structure and associated with the transaction in the plurality of bits when the transaction only requires unset bits to be set in an overwrite operation; and
storing the transaction in a memory with other transactions until the other transactions and the transaction can be performed in a batch overwrite operation when the transaction cannot be performed by the overwrite operation, wherein storing the transaction with the other transactions in the memory delays erasure of a portion of the flash memory.
2. The method of claim 1 , wherein the data structure includes at least one of a Bloom filter, a linked list, a hash table, a tree, a graph, or a locking data structure.
3. The method of claim 1 , further limiting a number or erasures of the flash memory by storing the transaction in the memory.
4. The method of claim 1 , further comprising performing the batch overwrite operation such that an erasure is not required for each insertion of data into the data structure.
5. The method of claim 1 , wherein the memory is configured to store a record, the record including a plurality of entries, and each entry corresponding to a portion of the data structure.
6. The method of claim 5 , further comprising, when one of the entries in the record is sufficiently full, overwriting the portion of the data structure corresponding the sufficiently full record.
7. The method of claim 1 , further comprising making a call to the flash memory to perform the overwriting, wherein the call allows a client to specify a method for performing the overwriting.
8. The method of claim 5 , wherein each entry in the record corresponds to a page in the flash memory, wherein the page is a size of the flash memory that is configured to be erased during a single erasure operation.
9. The method of claim 8 , wherein erasing a page allows multiple entries to be erased with fewer accesses to increase the life of the flash memory.
10. The method of claim 5 , further comprising clearing the entry in the record.
11. The method of claim 5 , further comprising managing the record to minimize a number of erasures performed in the flash memory.
12. A non-transitory computer readable medium comprising computer executable instructions for performing a method to manage a life of a flash memory, the instructions comprising:
establishing a data structure in the flash memory, wherein the data structure includes a plurality of bits that are initially unset;
performing a transaction in the flash memory by:
overwriting bits included in the data structure and associated with the transaction in the plurality of bits when the transaction only requires unset bits to be set in an overwrite operation; and
storing the transaction in a memory with other transactions until the other transactions and the transaction can be performed in a batch overwrite operation when the transaction cannot be performed by the overwrite operation, wherein storing the transaction with the other transactions in the memory delays erasure of a portion of the flash memory.
13. The non-transitory computer readable medium of claim 12 , wherein the data structure includes at least one of a Bloom filter, a linked list, a hash table, a tree, a graph, or a locking data structure.
14. The non-transitory computer readable medium of claim 12 , the instructions further comprising limiting a number or erasures of the flash memory by storing the transaction in the memory.
15. The non-transitory computer readable medium of claim 12 , the instructions further comprising performing the batch overwrite operation such that an erasure is not required for each insertion of data into the data structure.
16. The non-transitory computer readable medium of claim 12 , wherein the memory is configured to store a record, the record including a plurality of entries, and each entry corresponding to a portion of the data structure, the instructions further comprising, when one of the entries in the record is sufficiently full, overwriting the portion of the data structure corresponding the sufficiently full record.
17. The non-transitory computer readable medium of claim 16 , wherein each entry in the record corresponds to a page in the flash memory, wherein the page is a size of the flash memory that is configured to be erased during a single erasure operation.
18. The non-transitory computer readable medium of claim 17 , wherein erasing a page allows multiple entries in the flash memory to be erased with fewer accesses to increase the life of the flash memory.
19. The non-transitory computer readable medium of claim 16 , further comprising clearing the entry in the record.
20. The non-transitory computer readable medium of claim 16 , further comprising managing the record to minimize a number of erasures performed in the flash memory.