Method and system for writing data to and read data from persistent storage

• US 10,339,062 B2
• Filed: 04/28/2017
• Issued: 07/02/2019
• Est. Priority Date: 04/28/2017
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Wilde, Todd, Rajadnya, Samir, Ramachandran, Karthik, Nishimoto, Michael
• Primary Examiner(s): Portka, Gary J
• Application Number:
  US15/581,963
• Publication Number:
  US 20180314639A1
• Time in Patent Office: 795 Days
• Field of Search: 711102, 711103, 711206, 711207, 711221
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/282 Partitioned cache
• CPC Class Codes: G06F 2212/313 In storage device
• CPC Class Codes: G06F 2212/608 Details relating to cache mapping

Abstract

In general, embodiments of the technology relate to a method and system for storing and reading data from persistent storage. More specifically, embodiments of the technology relate to a method and system for storing data in persistent storage, where the data written to the persistent storage is not immediately accessible in the persistent storage (i.e., during the inaccessibility period). In such instances, embodiments of the technology provide a method and system to enable the storage system to service read requests for the data using a primary cache entry table (PCET) and an overflow table.

Claims

1. A method for managing data stored in a persistent storage, the method comprising:

receiving a write request comprising a logical address and a first datum;

storing a table entry corresponding to the logical address in a primary cache entry table;

updating a bitmap entry corresponding to the logical address;

storing the first datum in an external memory, wherein the external memory is operatively connected to the persistent storage;

transmitting a copy of the first datum to the persistent storage;

receiving a write request comprising a second logical address and second datum;

storing a second table entry corresponding to the second logical address in an overflow table;

updating a bitmap entry corresponding to the second logical address;

storing the second datum in the external memory; and

transmitting a copy of the second datum to the persistent storage.

2. The method of claim 1, wherein storing the second table entry in the overflow table comprises:

hashing the second logical address to obtain a hash value;

determining, using the hash value, that a location in the primary cache entry table is full;

identifying a location in the overflow table; and

based on the determination, storing the second table entry in the location in the overflow table.

3. The method of claim 2, wherein the table entry comprises a reference to the second table entry.

4. The method of claim 1, wherein storing the table entry in the primary cache entry table comprises:

hashing the logical address to obtain a hash value;

determining, using the hash value, that a location in the primary cache entry table is empty; and

based on the determination, storing the table entry in the location.

5. The method of claim 1, wherein the primary cache entry table is located on a field-programmable gate array (FPGA).

6. The method of claim 1, further comprising:

receiving, from a client, a read request comprising the logical address;

determining that an entry in the bitmap corresponding to the logical address is set;

based on the determination, identifying the table entry from the primary cache entry table;

obtaining, from the external storage, a second copy of the first datum from a location associated with the table entry; and

providing the second copy of the first datum to the client.

7. The method of claim 1, further comprising:

receiving, from a client, a read request comprising the logical address;

determining that an entry in the bitmap corresponding to the logical address is not set;

based on the determination, obtaining, from the persistent storage, a second copy of the first datum; and

providing the second copy of the first datum to the client.

8. The method of claim 1, further comprising:

selecting the table entry;

determining that the table entry has been present in the primary cache entry table for a time period that exceeds an unavailability period associated with the persistent storage;

based on the determination, marking the table entry as invalid.

9. The method of claim 8, further comprising:

after marking the table entry as invalid, replacing the table entry with a second table entry generated in response to a second write request.

10. The method of claim 1, further comprising:

selecting the table entry;

determining that the table entry has been present in the primary cache entry table for a time period that exceeds an unavailability period associated with the persistent storage;

based on the determination;

identifying a second table entry, wherein the table comprises a reference to the second table entry, and

replacing the table entry with the second table entry.

11. A storage module, comprising:

a field programmable gate array (FPGA) comprising internal memory;

an external memory operatively connected to the FPGA; and

a storage unit operatively connected to the FPGA and comprising persistent storage,

wherein the FPGA is configured to;

receive a write request comprising a logical address and a first datum;

store a table entry corresponding to the logical address in a primary cache entry table in the internal memory;

update, in a bitmap stored in the external memory, a bitmap entry corresponding to the logical address;

store the first datum in the external memory;

transmit a copy of the first datum to the persistent storage;

receive a write request comprising a second logical address and second datum;

store a second table entry corresponding to the second logical address in an overflow table;

update a bitmap entry corresponding to the second logical address;

store the second datum in the external memory; and

transmit a copy of the second datum to the persistent storage.

12. The storage module of claim 11, wherein storing the second table entry in the overflow table comprises:

hashing the second logical address to obtain a hash value;

determining, using the hash value, that a location in the primary cache entry table is full;

identifying a location in the overflow table; and

based on the determination, storing the second table entry in the location in the overflow table,

wherein the table entry comprises a reference to the second table entry.

13. The storage module of claim 11, wherein storing the table entry in the primary cache entry table comprises:

hashing the logical address to obtain a hash value;

determining, using the hash value, that a location in the primary cache entry table is empty; and

based on the determination, storing the table entry in the location.

14. The storage module of claim 11, wherein the FPGA is further configured to:

receive, from a client, a read request comprising the logical address;

determine that an entry in the bitmap corresponding to the logical address is set;

based on the determination, identify the table entry from the primary cache entry table;

obtain, from the external memory, a second copy of the first datum from a location associated with the table entry; and

provide the second copy of the first datum to the client.

15. The storage module of claim 11, wherein the FPGA is further configured to:

receive, from a client, a read request comprising the logical address;

determine that an entry in the bitmap corresponding to the logical address is not set;

based on the determination, obtain, from the persistent storage, a second copy of the first datum; and

provide the second copy of the first datum to the client.

16. The storage module of claim 11, wherein the FPGA is further configured to:

select the table entry;

determine that the table entry has been present in the primary cache entry table for a time period that exceeds an unavailability period associated with the persistent storage;

based on the determination, mark the table entry as invalid; and

after marking the table entry as invalid, replacing the table entry with a second table entry generated in response to a second write request.

17. The storage module of claim 11, wherein the FPGA is further configured to:

select the table entry;

determine that the table entry has been present in the primary cache entry table for a time period that exceeds an unavailability period associated with the persistent storage;

based on the determination;

identify a second table entry, wherein the table comprises a reference to the second table entry, and

replace the table entry with the second table entry.

18. The storage module of claim 11, wherein the persistent storage comprises phase change storage media.