Transactional key-value store

Patent metadata

Field	Value
Publication number	US-11288252-B2
Application number	US-202017079802-A
Country	US
Kind code	B2
Filing date	Oct 26, 2020
Priority date	Jan 29, 2015
Publication date	Mar 29, 2022
Grant date	Mar 29, 2022

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 log 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 method comprising:
generating a plurality of log files comprising log entries corresponding to transactions performed on data in volatile data pages organized into tables and stored in a volatile random access memory distributed across a plurality of interconnected nodes;
mapping the log entries into buckets corresponding to the tables;
partitioning the log entries in the buckets based on ranges of keys associated with the volatile data pages;
copying the partitioned log entries to corresponding batch buffers;
sorting the partitioned log entries in the batch buffers according to key ranges to generate corresponding files of sorted log entries;
generate new non-volatile data pages according to the files of sorted log entries; and
updating existing non-volatile data pages stored in a non-volatile random access memory distributed across the plurality of nodes with the new non-volatile data pages.

2. The method of claim 1 , wherein the ranges of keys are associated with open or more of the plurality of interconnected nodes determined to frequently access volatile data pages or non-volatile data pages associated with the ranges of keys.

3. The method of claim 1 , wherein updating the existing non-volatile data pages comprises updating pointers in the existing non-volatile data pages with addresses of the new non-volatile data pages.

4. The method of claim 1 , wherein, once the transactions are committed, the plurality of log files are stored in a private log buffer specific to a processing core.

5. The method of claim 1 , wherein a first set of the buckets are associated with a table of customer information and a second set of the buckets are associated with a database for financial transactions.

6. The method of claim 1 , further comprising:
determining that a first bucket of the buckets is full;
sorting and partitioning a set of log entries in the first bucket; and
initiating a reducing process of the set of log entries in the first bucket.

7. The method of claim 6 , wherein the sorting and partitioning is based on boundary keys associated with the first bucket.

8. The method of claim 1 , further comprising:
reserving space in a buffer; and
copying a first bucket into the reserved space in the buffer.

9. The method of claim 8 , wherein the space is reserved in the buffer by atomically modifying a state of the buffer, and wherein the state is modified a second time upon copying the first bucket to the reserved space in the buffer.

10. The method of claim 8 , wherein the first bucket is copied into the reserved space in the buffer using a single write operation.

11. The method of claim 1 , wherein the log entries comprise information regarding an original transaction request and an original input key.

12. The method of claim 1 , further comprising:
generating a single file of the sorted log entries.

13. 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:
generate a plurality of log files comprising log entries corresponding to transactions performed on data in volatile data pages organized into tables and stored in a volatile random access memory;
map the log entries into buckets corresponding to the tables;
partition the log entries in the buckets based on ranges of keys associated with the volatile data pages;
copy the partitioned log entries to corresponding batch buffers;
sort the partitioned log entries in the batch buffers according to key ranges to generate corresponding files of sorted log entries;
generate new non-volatile data pages according to the files of sorted log entries; and
update existing non-volatile data pages stored in a non-volatile random access memory distributed across the plurality of nodes with the new non-volatile data pages.

14. The system of claim 13 , wherein the volatile random access memory is distributed across a plurality of interconnected nodes, and wherein the ranges of keys are associated with one or more of the plurality of interconnected nodes determined to frequently access volatile data pages or non-volatile data pages associated with the ranges of keys.

15. The system of claim 13 , wherein updating the existing non-volatile data pages comprises updating pointers in the existing non-volatile data pages with addresses of the new non-volatile data pages.

16. The system of claim 13 , wherein the processors are further caused to:
determine that a first bucket of the buckets is full;
sort and partition a set of log entries in the first bucket; and
initiate a reducing process of the set of log entries in the first bucket.

17. 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:
generate a plurality of log files comprising log entries corresponding to transactions performed on data in data pages organized into tables and stored in a random access memory distributed across a plurality of interconnected nodes;
map the log entries into buckets corresponding to the tables;
partition the log entries in the buckets based on ranges of keys associated with the data pages;
copy the partitioned log entries to corresponding batch buffers;
sort the partitioned log entries in the batch buffers according to key ranges to generate corresponding files of sorted log entries;
generate new data pages according to the files of sorted log entries; and
update existing data pages stored in a random access memory distributed across the plurality of nodes with the new data pages.

18. The non-transitory computer readable storage medium of claim 17 , wherein the ranges of keys are associated with open or more of the plurality of interconnected nodes determined to frequently access volatile data pages or non-volatile data pages associated with the ranges of keys.

19. The non-transitory computer readable storage medium of claim 17 , wherein updating the existing data pages comprises updating pointers in the existing data pages with addresses of the new data pages.

20. The non-transitory computer readable storage medium of claim 17 , wherein the processors are further caused to:
determine that a first bucket of the buckets is full;
sort and partition a set of log entries in the first bucket; and
initiate a reducing process of the set of log entries in the first bucket.

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Kimura Hideaki

Classifications

• G06F16/2315 Primary

  Optimistic concurrency control · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title

• G06F16/2336 Primary

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

• G06F11/1451

  by selection of backup contents · CPC title

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title