Bloom filters in a flash memory
First Claim
Patent Images
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.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
22 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
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. - View Dependent Claims (17, 18, 19, 20, 21, 22)
Specification