Persistent data structures

• US 10,817,421 B2
• Filed: 03/12/2014
• Issued: 10/27/2020
• Est. Priority Date: 12/13/2010
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Talagala, Nisha, Sundararaman, Swaminathan, Flynn, David
• Primary Examiner(s): Partridge, William B
• Assistant Examiner(s): Loonan, Eric T
• Application Number:
  US14/207,002
• Publication Number:
  US 20140195564A1
• Time in Patent Office: 2,421 Days
• CPC Class Codes: G06F 11/141 for bus or memory accesses
• CPC Class Codes: G06F 11/2015 Redundant power supplies power supply failure G06F1/30
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 2212/202 Non-volatile memory

Abstract

Apparatuses, systems, methods, and computer program products are disclosed for a persistent data structure. A method includes associating a logical identifier with a data structure. A method includes writing data of a data structure to a first region of a volatile memory module. A volatile memory module may be configured to ensure that data is preserved in response to a trigger. A method includes copying data of a data structure from a volatile memory module to a non-volatile storage medium such that the data of the data structure remains associated with a logical identifier.

Claims

1. A method comprising:

writing data of a persistent data structure from a host to an auto-commit memory, wherein;

the host is a computing device comprising a bus,

the auto-commit memory is a hardware device with a single connection to the bus,

the persistent data structure is associated with a logical identifier,

the auto-commit memory comprises a controller, a non-volatile storage medium, and a plurality of auto-commit memory buffers that receive the data, and

the auto-commit memory buffers are uniformly sized regions of a volatile memory module;

arming the auto-commit memory buffers that received the data of the persistent data structure by storing metadata in the auto-commit memory buffers such that the metadata specifies addresses of the non-volatile storage medium for storing the data of the persistent data structure, and such that individual auto-commit memory buffers store their own per-buffer portions of the metadata specifying where to store their own per-buffer portions of the data;

destaging a portion of the data of the persistent data structure from the auto-commit memory buffers that received the data to addresses specified by the metadata such that the data of the persistent data structure remains associated with the logical identifier; and

in response to a trigger, using the controller to store remaining data of the persistent data structure from the auto-commit memory buffers to the addresses specified by the metadata, wherein storing the data is internal to the hardware device without communicating via the single connection.

2. The method of claim 1, further comprising alternating between writing data of the persistent data structure to a first auto-commit memory buffer and a second auto-commit memory buffer while destaging data of the persistent data structure to the non-volatile storage medium from the other of the first auto-commit memory buffer and the second auto-commit memory buffer.

3. The method of claim 1, further comprising enforcing one or more rules for the persistent data structure.

4. The method of claim 3, wherein:

the persistent data structure comprises a log data structure;

the one or more rules define the log data structure as sequential and append-only; and

enforcing the one or more rules comprises preventing writes to the log data structure other than append operations.

5. The method of claim 1, further comprising tracking which data of the persistent data structure resides in the auto-commit memory buffers and which data of the persistent data structure resides in the non-volatile storage medium.

6. The method of claim 5, further comprising providing access to the data of the persistent data structure residing in the auto-commit memory buffers and the data of the persistent data structure stored in the non-volatile storage medium using the logical identifier.

7. The method of claim 1, further comprising limiting a rate at which data of the persistent data structure is written to the auto-commit memory buffers such that the rate is at or below a rate at which data of the persistent data structure is destaged to the non-volatile storage medium.

8. The method of claim 1, further comprising increasing a transfer rate in response to an increase in an input rate, wherein:

the input rate comprises a rate at which data of the persistent data structure is written to the auto-commit memory buffers; and

the transfer rate comprises a rate at which data of the persistent data structure is destaged to the non-volatile storage medium.

9. The method of claim 8, wherein the transfer rate is increased by increasing a quantity of data destaged to the non-volatile storage medium per transfer operation in response to the input rate being below a threshold, the transfer rate increased by increasing a number of parallel processes destaging data in response to the input rate being above the threshold.

10. The method of claim 1, wherein destaging data of the persistent data structure from the auto-commit memory buffers to the non-volatile storage medium is in response to one or more of:

an amount of data of the persistent data structure written to the auto-commit memory buffers satisfying a threshold;

an elapsed time period;

a notification provided by a monitoring device associated with the auto-commit memory buffers; and

a request from a client.

11. The method of claim 1, wherein the persistent data structure comprises at least one of a log, a queue, a stack, a tree, a linked-list, a hash, an array, a heap, and a graph data structure.

12. The method of claim 1, further comprising one or more of:

opening the persistent data structure in response to an open request from a client;

writing the data of the persistent data structure to the one or more auto-commit memory buffers in response to a write request from a client;

destaging data of the persistent data structure from the auto-commit memory buffers to the non-volatile storage medium in response to a synchronize request from a client;

closing the persistent data structure in response to a close request from a client; and

mapping the auto-commit memory buffers into virtual memory of a client in response to a map request from a client.

13. The method of claim 1, wherein:

the logical identifier comprises a filename of a file system; and

the persistent data structure is accessible as a file of the file system.

14. The method of claim 1, wherein:

the volatile memory module comprises a byte addressable write-in-place memory device; and

the non-volatile storage medium comprises a block addressable storage device.

15. The method of claim 1, wherein an isolation zone of the auto-commit memory comprises the controller, the non-volatile storage medium, the one or more auto-commit memory buffers, and a secondary power source configured to power the controller and the auto-commit memory buffers despite failure of the host.

16. An apparatus comprising:

a write module configured to append data to a persistent transaction log by writing the data from a host to an auto-commit memory, wherein;

the host is a computing device comprising a bus,

the auto-commit memory is a hardware device with a single connection to the bus,

the auto-commit memory comprises a controller, a non-volatile memory medium, and a plurality of auto-commit memory buffers that receive the data, and

the auto-commit memory buffers are uniformly sized regions of a volatile memory module;

a storage management module configured to arm the auto-commit memory buffers that received the data of the persistent transaction log by storing metadata in the auto-commit memory buffers such that the metadata specifies addresses of the non-volatile memory medium for storing the data of the persistent transaction log, and such that individual auto-commit memory buffers store their own per-buffer portions of the metadata specifying where to store their own per-buffer portions of the data;

an enforcement module configured to enforce one or more rules preventing the data from being overwritten in the persistent transaction log; and

a commit module configured to use the controller, in response to a trigger, to store data of the persistent transaction log from the auto-commit memory buffers to the one or more addresses specified by the metadata, wherein storing the data is internal to the hardware device without communicating via the single connection,

wherein the write module, the storage management module, the enforcement module, and the commit module comprise one or more of logic hardware and executable code, the executable code stored on a non-transitory computer readable medium.

17. The apparatus of claim 16, further comprising a destage module configured to write the appended data from a first auto-commit memory buffer to the non-volatile memory medium at a rate such that the appended data does not overrun the first auto-commit memory buffer, the destage module comprising one or more of logic hardware and executable code, the executable code stored on a non-transitory computer readable medium.

18. The apparatus of claim 17, wherein:

the write module is configured to alternate between two or more auto-commit memory buffers for storing appended data; and

the destage module is configured to write appended data to the non-volatile memory medium from an auto-commit memory buffer to which data is not currently being written.

19. An apparatus comprising:

means for satisfying one or more client requests for a persistent data structure, wherein;

satisfying the one or more client requests comprises writing data of a persistent data structure from a host to an auto-commit memory,

the host is a computing device comprising a bus,

the auto-commit memory is a hardware device with a single connection to the bus;

the auto-commit memory comprises a controller, a non-volatile memory medium, and a plurality of auto-commit memory buffers that receive the data;

the auto-commit memory buffers are uniformly sized regions of a volatile memory module;

the auto-commit memory buffers are individually armed by storing metadata in the auto-commit memory buffers such that the metadata specifies addresses of the non-volatile memory medium for storing data of the persistent data structure, and such that individual auto-commit memory buffers store their own per-buffer portions of the metadata specifying where to store their own per-buffer portions of the data; and

the persistent data structure comprises data stored in the auto-commit memory buffers and data stored in the non-volatile memory medium;

means for using the controller, in response to a trigger, to commit the data of the persistent data structure stored in the auto-commit memory buffers to the addresses specified by the metadata, wherein committing the data is internal to the hardware device without communicating via the single connection; and

means for providing access to the persistent data structure from the non-volatile memory medium after a restart event using a logical identifier associated with the persistent data structure.

20. The apparatus of claim 19, further comprising means for enforcing an append-only rule for the persistent data structure such that data of the persistent data structure is not overwritten.