Additive library for data structures in a flash memory

• US 10,146,438 B1
• Filed: 06/29/2016
• Issued: 12/04/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: Shilane, Philip N., Wallace, Grant R.
• Primary Examiner(s): Chappell, Daniel C
• Application Number:
  US15/196,283
• Time in Patent Office: 888 Days
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0655 Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G11C 16/10 Programming or data input circuits
• CPC Class Codes: G11C 16/102 External programming circuits, e.g. EPROM programmers; In-circuit programming or reprogramming; EPROM emulators

Abstract

Systems and methods for managing data structures in a flash memory. A library is provided that supports read requests and write requests. The library allows reads and writes to be implemented without requiring the client to understand how the data structure is implemented in the flash memory.

Claims

1. A method for writing data to a data structure implemented in a flash memory, the method comprising:

receiving a write request from a client at the flash memory, wherein the flash memory includes a controller and a library that includes a plurality of calls that are performed by the controller, wherein the controller is configured to perform the write request and wherein the library allows the client to specify a particular call of the plurality of calls directly to the library of the flash memory such that the client determines how the write request is performed in the flash memory, wherein the write request is to write an update to a data structure stored in the flash memory in accordance with the particular call, wherein the write request includes an update and a location and wherein the library supports write requests and read requests;

translating the location to identify a page in the data structure and to identify a location in the page that corresponds to the location in the write request; and

overwriting the location in the page with the update when an overwrite operation can be performed, wherein the update is written to an in-memory table or to a new location in the flash memory when the overwrite operation cannot be performed.

2. The method of claim 1, wherein the library does not require the client to understand that the data structure is implemented in the flash memory.

3. The method of claim 1, wherein the location in the write request includes an offset into the data structure.

4. The method of claim 1, wherein overwriting the location includes only changing 0s to 1s in the location in the page.

5. The method of claim 1, further comprising writing the update to the in-memory table when the overwrite operation cannot be performed, wherein the update in the in-memory table is associated with the page and with the location in the page.

6. The method of claim 5, further comprising writing updates stored in the in-memory table to the data structure in flash memory.

7. The method of claim 6, wherein the updates stored in the in-memory table are written to the data structure periodically or when instructed, or when the in-memory table is full or fuller than a threshold level.

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

9. The method of claim 1, further comprising writing the update or a page that reflects the update to a new page in flash memory when the overwrite operation cannot be performed.

10. A method for reading data from a data structure implemented in a flash memory, the method comprising:

receiving a read request from a client at a library of the flash memory for data stored in a data structure, wherein the read request includes a location in the data structure and wherein the library supports write requests and read requests, wherein the library flash memory includes a controller, wherein the controller is configured to perform the read request and wherein the library allows the client to specify a particular call of the plurality of calls directly to the library of the flash memory such that the client determines how the particular call is performed in the flash memory;

translating the location to identify a page in the data structure and to identify a location in the page that corresponds to the location in the read request;

reading the data from the data structure at the location in the page;

applying updates to the data that are stored in an in-memory table, wherein the updates stored in the in-memory table correspond to writes to the requested data that were stored in the in-memory table instead of being written to the flash memory; and

returning the updated data to the client.

11. The method of claim 10, wherein the in-memory table is associated with the data structure and wherein writes to the data structure that cannot be performed by an overwrite operation are stored in the in-memory table and wherein the data structure is one of a linked list, a Bloom filter, a hash table, a locking structure, a graph, or a tree.

12. The method of claim 10, wherein the library does not require the client to understand that the data structure is implemented in the flash memory.

13. The method of claim 10, wherein the location in the read request includes an offset into the data structure.

14. The method of claim 10, further comprising receiving a write request from the client.

15. The method of claim 14, further comprising implementing the write request as an overwrite operation when only sets are required or writing an update included in the write request to the in-memory table.

16. A library configured to provide calls for a client that allows the client to write and read to a data structure stored in flash memory without understanding that the data structure is stored in the flash memory, the library comprising computer executable instructions that, where executed, perform a method for interacting with the data structure in response to a request from the client, the method comprising:

receiving the request at the library, the library included in the flash memory, wherein the flash memory includes a controller, wherein the library includes a plurality of calls that can be performed by the controller, wherein the controller is configured to perform the request and wherein the library allows the client to specify a particular call directly to the library of the flash memory such that the client determines how the request is performed in the flash memory;

when the request is a read request for data;

identifying a page in the data structure stored in the flash memory from information included in the read request;

reading the requested data from the identified page;

applying updates to the requested data, if any, from an in-memory table, wherein the updates correspond to writes to the requested data that were stored in the in-memory table instead of being written to the flash memory and

returning the updated data to the client; and

when the request is a write request that includes an update to the data structure;

identifying a page in the data structure from information included in the write request;

overwriting data in the page with the update when the update only requires bits to be set in the page with an overwrite operation; and

writing the update to the in-memory table when the overwrite operation requires bits to be unset.

17. The library of claim 16, wherein the overwrite operation includes a logical OR operation for at least the bits being set by the update or a compare and swap operation.

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

19. The library of claim 16, further comprising translating an offset in the read request or in the write request to identify the page in the data structure.

20. The library of claim 16, further comprising writing updates in the in-memory table to the data structure by reading at least the pages associated with the updates, applying the updates to the pages and writing the pages associated with the updates to new locations in the flash memory.

21. The library of claim 20, further comprising marking the old pages for erasure.