KEY-VALUE STORE ON PERSISTENT MEMORY

• US 20200133800A1
• Filed: 10/26/2018
• Published: 04/30/2020
• Est. Priority Date: 10/26/2018
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Varadan, Srikant, Barszczak, Tomasz, Luo, Hao
• Granted Patent: US 11,360,863 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/1441 Resetting or repowering
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/2064 while ensuring consistency
• CPC Class Codes: G06F 11/2069 Management of state, configuration or failover
• CPC Class Codes: G06F 11/2092 Techniques of failing over between control units
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A technique for reducing recovery time in a computing apparatus includes: storing data in a key-value store residing in a persistent memory, the key-value store including a plurality of persistent nodes including key-value pairs, the key-value pairs of the persistent nodes being unsorted; caching selected persistent nodes in a volatile memory, the key-value pairs of the cached nodes being sorted, the caching including instantiating a dual pointer for each cached node, the dual pointer including a volatile pointer to a child node of the cached node and a persistent pointer to the child node of the corresponding persistent node in the key-value store; and rebuilding the cache of selected nodes upon demand using the dual pointers in the event of recovery.

Claims

1. A method for use in a computing apparatus, the method comprising:

storing data in a key-value store residing in a persistent memory, the key-value store including a plurality of persistent nodes including key-value pairs, the key-value pairs of the persistent nodes being unsorted;

caching selected persistent nodes in a volatile memory, the key-value pairs of the cached nodes being sorted, the caching including instantiating a dual pointer for each cached node, the dual pointer including a volatile pointer to a child node of the cached node and a persistent pointer to the child node of the corresponding persistent node in the key-value store; and

rebuilding the cache of selected nodes upon demand using the dual pointers in the event of recovery.

2. The method of claim 1, further comprising retrieving the data in the persistent memory from a backend storage.

3. The method of claim 1, further comprising rebuilding the volatile pointers on demand from persistent pointers based on the first access to a particular persistent node in the key-value store.

4. The method of claim 1, wherein the recovery is after a failover or other failure.

5. The method of claim 1, wherein the cache comprises a second key-value store.

6. The method of claim 1, wherein the key-value store comprises a B+ tree.

7. The method of claim 6, wherein the cached nodes comprise any internal tree nodes in the B+ tree accessed on a path from a tree root to the accessed key since the last recovery.

8. The method of claim 1, wherein the recovery is a user-space process restart or a system reboot.

9. A computing apparatus, comprising:

a processor;

a volatile memory;

a persistent memory; and

a non-transitory, machine-readable storage medium storing instructions that, when executed by the processor, perform a method comprising;

storing data in a key-value store residing in the persistent memory, the key-value store including a plurality of persistent nodes including key-value pairs, the key-value pairs of the persistent nodes being unsorted;

caching selected persistent nodes in the volatile memory, the key-value pairs of the cached nodes being sorted, the caching including instantiating a dual pointer for each cached node, the dual pointer including a volatile pointer to a child node of the cached node and a persistent pointer to the child node of the corresponding persistent node in the key-value store; and

rebuilding the cache of selected nodes upon demand using the dual pointers in the event of recovery.

10. The computing apparatus of claim 9, further comprising a backend storage whose data the persistent memory buffers.

11. The computing apparatus of claim 10, wherein the backend storage comprises a redundant array of independent disks.

12. The computing apparatus of claim 9, wherein the volatile memory comprises dynamic random access memory.

13. The computing apparatus of claim 9, wherein the persistent memory comprises non-volatile, dual in-line memory modules.

14. The computing apparatus of claim 9, wherein the key-value store residing in the persistent memory is implemented in a B+ tree.

15. A storage system, comprising:

backend storage;

an active controller that, in operation, controls the writing of data to and the reading of data from the backend storage, the active controller including;

a persistent memory that, in operation, is populated using data from the backend storage;

a key-value store residing in the persistent memory during operation and comprising a plurality of persistent nodes, each persistent node including a set of unsorted key-value pairs;

a volatile memory;

a cache of selected persistent nodes residing in the volatile memory during operation, the key-value pairs of the cached nodes being sorted; and

a dual pointer for each cached node, the dual pointer including a volatile pointer to a child node of the cached node and a persistent pointer to the child node of the corresponding persistent node in the key-value store;

a bridge; and

a passive controller assuming control from the active controller upon failover from the active controller, and to which the transactions of the active controller are mirrored over the bridge.

16. The storage system of claim 15, wherein the backend storage comprises a redundant array of independent disks.

17. The storage system of claim 15, wherein the volatile memory comprises dynamic random access memory.

18. The storage system of claim 15, wherein the persistent memory comprises non-volatile, dual in-line memory modules.

19. The storage system of claim 15 wherein the key-value store residing in the persistent memory is Implemented in a B+ tree.

20. The storage system of claim 15, wherein the passive controller comprises:

a second persistent memory that, in operation, is populated using data from the backend storage as mirrored from the active controller;

a mirrored key-value store residing in the second persistent memory during operation and comprised of a plurality of mirrored persistent nodes, each mirrored persistent node including a set of mirrored, unsorted key-value pairs;

a second volatile memory;

a mirrored cache of selected mirrored persistent nodes residing in the second volatile memory while the computing apparatus is in use, the mirrored key-value pairs of the mirrored cached nodes being sorted; and

a mirrored dual pointer for each mirrored cached node, the mirrored dual pointer including a mirrored volatile pointer to a mirrored child node of the mirrored cached node and a mirrored persistent pointer to the mirrored child node of the corresponding mirrored persistent node in the mirrored key-value store;