Transactional key-value store

Patent metadata

Field	Value
Publication number	US-10846279-B2
Application number	US-201515545389-A
Country	US
Kind code	B2
Filing date	Jan 29, 2015
Priority date	Jan 29, 2015
Publication date	Nov 24, 2020
Grant date	Nov 24, 2020

Abstract

Example implementations disclosed herein can be used to build, maintain, and access databases built database in multi-core computing systems with large VRAM and huge NVRAM. The database with optimistic concurrency control can be built on a transactional key-value data store that includes logically equivalent data pages stored in both VRAM and VRAM. Data records in volatile data pages in the VRAM represent the most recent version of the data. Data records in the NVRAM immutable and are organized in a stratified composite snapshot. A distributed log gleaner process is used to process entries corresponding to transactions on the volatile data pages and construct the snapshot. The log gleaner sorts the log entries by epoch, key range, and most recent use to partition the snapshot across multiple nodes.

First claim

What is claimed is:

1. A system comprising:
a plurality of processors;
a volatile random access memory coupled to at least one of the plurality of processors;
a non-volatile random access memory coupled to one or more of the plurality of processors, wherein the non-volatile random access memory comprises instructions, that when executed by one or more processors in the plurality of processors, cause the processors to:
access a key-value store comprising:
a plurality of keys; and
a plurality of dual pointers associated with corresponding keys in the plurality of keys, each dual pointer in the plurality of dual pointers comprising a volatile pointer associated with a volatile data page in a plurality of volatile data pages in the volatile random access memory or a non-volatile pointer associated with a non-volatile data page in a plurality of non-volatile data pages in the non-volatile random access memory;

execute a transaction comprising an input key based on the key-value store;
follow a volatile pointer of a dual pointer corresponding to the input key to access a volatile data page; and
if the volatile pointer is null, then follow a non-volatile pointer of the dual pointer to copy a corresponding non-volatile data page to a corresponding volatile data page associated with an address in the volatile random access memory.

2. The system of claim 1 , wherein the volatile data pages and the non-volatile data pages are fixed size data pages.

3. The system of claim 1 , wherein the instructions further cause the processors to:
generate a read-set comprising a first value associated with the input key in the corresponding volatile data page;
generate a pointer-set comprising the address of the corresponding volatile data page in the volatile random access memory;
generate a second value;
compare the first value in the read-set with a third value stored at the address before the second value is written to the address; and
based on the comparison aborting the transaction or writing the second value to corresponding volatile data page.

4. The system of claim 1 , wherein the plurality of processors, the volatile random access memory, and the non-volatile random access memory are distributed among a plurality of interconnected node boards.

5. The system of claim 4 , wherein the transaction is associated with a node board in the plurality of interconnected node boards, and the instructions further cause the processors to:
generate a write-set comprising changes in one or more volatile data pages in the plurality of volatile data pages corresponding to the transaction;
save the write-set and other write-sets associated with the node board in the plurality of interconnected node boards to a time-based log file; and
combine the time-based log file with other time-based log files associated with other node boards in the plurality of interconnected node boards to generate an updated snapshot of the plurality of non-volatile data pages.

6. The system of claim 5 , wherein the updated snapshot comprises multiple partitions stored in the non-volatile random access memory of multiple node boards.

7. A non-transitory computer readable storage medium comprising instructions, that when executed by one or more processors in a plurality of processors distributed among a plurality of interconnected nodes, cause the processors to:
instantiate a key-value store comprising:
a plurality of keys; and
a plurality of dual pointers associated with corresponding keys in the plurality of keys, each dual pointer in the plurality of dual pointers comprising:
a volatile pointer associated with a volatile data page in a plurality of volatile data pages stored in a volatile random access memory; and
a non-volatile pointer associated with a non-volatile data page in a plurality of non-volatile data pages stored in a non-volatile random access memory; and

execute multiple transactions on data stored in the plurality of volatile data pages based on corresponding input keys and the key-value store;
generate log entries corresponding to the multiple transactions;
generate a multi-version snapshot of the data stored in the plurality of volatile data pages in the plurality of non-volatile data pages based on the log entries;
follow a volatile pointer of a dual pointer corresponding to the input key to access a volatile data page; and
if the volatile pointer is null, then follow a non-volatile pointer of the dual pointer to copy a corresponding non-volatile data page to a corresponding volatile data page associated with an address in the volatile random access memory.

8. The non-transitory computer readable storage medium of claim 7 , wherein to generate the multi-version snapshot the instructions further cause the processors to generate partitions of the log entries based on time periods.

9. The non-transitory computer readable storage medium of claim 8 , wherein the multi-version snapshot comprises multiple snapshots of the data stored in the plurality of volatile data pages corresponding to the partitions and pointers that define connections among the multiple snapshots.

10. The non-transitory computer readable storage medium of claim 7 , wherein the multi-version snapshot is distributed across the plurality of nodes.

11. The non-transitory computer readable storage medium of claim 7 that when executed by one or more processors further cause the processors to:
generate a read-set comprising a first value associated with the input key in the corresponding volatile data page;
generate a pointer-set comprising the address of the corresponding volatile data page in the volatile random access memory;
generate a second value;
compare the first value in the read-set with a third value stored at the address before the second value is written to the address; and
based on the comparison aborting the transaction or writing the second value to corresponding volatile data page.

12. The non-transitory computer readable storage medium of claim 7 , wherein the volatile data pages and the non-volatile data pages are fixed size data pages.

13. The non-transitory computer readable storage medium of claim 7 that when executed by one or more processors further cause the processors to:
generate a write-set comprising changes in one or more volatile data pages in the plurality of volatile data pages corresponding to the transaction;
save the write-set and other write-sets associated with the node board in the plurality of interconnected node boards to a time-based log file; and
combine the time-based log file with other time-based log files associated with other node boards in the plurality of interconnected node boards to generate an updated snapshot of the plurality of non-volatile data pages.

14. The non-transitory computer readable storage medium of claim 13 , wherein the updated snapshot comprises multiple partitions stored in the non-volatile random access memory of multiple node boards.

15. A method comprising
accessing a key-value store, the key store comprising a plurality of keys and a plurality of dual pointers associated with corresponding keys in the plurality of keys, each dual pointer in the plurality of dual pointers comprising a volatile pointer associated with a volatile data page in a plurality of volatile data pages in the volatile random access memory or a non-volatile pointer associated with a non-volatile data page in a plurality of non-volatile data pages in the non-volatile random access memory;
executing a transaction comprising an input key based on the key-value store;
following a volatile pointer of a dual

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Kimura Hideaki

Classifications

• G06F16/2315 Primary

  Optimistic concurrency control · CPC title

• G06F16/2365

  Ensuring data consistency and integrity · CPC title

• G06F16/2336 Primary

  Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps · CPC title

• G06F3/0685

  Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays · CPC title

• G06F11/1451

  by selection of backup contents · CPC title