Durable multiversion b+-tree

Abstract

Embodiments of the systems and methods disclosed include a durable multiversion modification of B+-tree with full transaction semantics. In-memory and persistent page images are managed without a buffer manager. Instead, a non-leaf page downlink directly points either to in-memory or on-disk pages. In turn, the reduced amount of fetches per page access improves scalability on multi-core hardware platforms. Embodiments include structurally consistent copy-on-write checkpoints that enable using row-level write-ahead logs. In combination with in-memory undo log for multiversion concurrency control, the amount of persistent storage operations is significantly reduced.

I claim: 
     
         1 . A method of comprising:
 writing, by a processor to a memory space, a root fha of a tree, wherein the root node comprises one or more downlinks directly pointing to one or more nodes, and the root node is configured to store a first plurality of pivot keys;   writing, by the processor to the memory space, a plurality of internal nodes of the tree, wherein each internal node comprises one or more downlinks directly pointing to one or more nodes, and the plurality of internal nodes are configured to store a second plurality of pivot keys;   writing, by the processor to the memory space, a plurality of leaf nodes of the tree, wherein the plurality of leaf nodes are configured to store a plurality of rows;   writing, by the processor, a first checkpoint representing a first state of the tree, comprising a copy of each node as a respective block, to a disk;   during writing of the first checkpoint, writing, by the processor, a modification to one or more of the nodes;   writing, by the processor, at least one modification to the one or more nodes after writing the first checkpoint; and   writing, by the processor, a second checkpoint, of a second state of the tree, to the disk;   wherein the second checkpoint comprises pointers to a plurality of blocks of the first checkpoint corresponding to unmodified nodes,   wherein the first checkpoint remains unmodified until the second checkpoint is completed.   
     
     
         2 . The method of  claim 1 , wherein after the second checkpoint is completed, the modified blocks of the first checkpoint are treated as free space. 
     
     
         3 . The method of  claim 1  further comprising:
 writing, by the processor, an instruction to main memory to generate a modified node; and 
 writing, by the processor, an instruction to the main memory to set a dirty bit of the modified node. 
 
     
     
         4 . The method of  claim 3  further comprises:
 delaying, by the processor, writing the modified node to the disk; 
 receiving, by the processor, a request to read the modified node; and 
 sending, by the processor, a read request to the main memory to read the modified node after setting the dirty bit. 
 
     
     
         5 . The method of  claim 3 , wherein prior to writing a node to the main memory or the disk, the processor writes information corresponding to the node to a write-ahead log (WAL) record. 
     
     
         6 . The method of  claim 5 , wherein each WAL record is idempotent. 
     
     
         7 . The method of  claim 6 , wherein the WAL comprises one or more WAL records that correspond to the tree and one or more additional trees. 
     
     
         8 . The method of  claim 6  further comprising:
 initiating, by the processor, a database recovery process; 
 reading, by the processor, a last completed checkpoint from the disk; 
 writing, by the processor, the last completed checkpoint to the main memory and the disk; and 
 writing, by the processor, WAL records to recover a last state. 
 
     
     
         9 . The method of  claim 5  further comprising:
 after a crash, restoring the second checkpoint; and 
 replaying a plurality of records of the WAL. 
 
     
     
         10 . The method of  claim 1 , wherein the downlinks comprise physical addresses to a main memory and the disk. 
     
     
         11 . A system comprising:
 one or more processors;   a main memory coupled to the one or more processors;   a disk coupled to the one or more processors;   the one or more processors are configured to:   write a plurality of nodes to the main memory and the disk, wherein the nodes comprise a root node, one or more internal nodes, and one or more leaf nodes;   write one or more pivot keys to the root node, wherein the root node comprises one or more downlinks directly pointing to one or more nodes; and   write one or more pivot keys to the one or more internal nodes, wherein each of the one or more internal nodes comprises one or more downlinks directly pointing to one or more nodes;   write a first checkpoint, comprising copies of the plurality of nodes as respective blocks, to the disk;   during the write of the first checkpoint, write a modification to one or more of the nodes;   write at least one modification to the one or more nodes after writing the first checkpoint; and   write a second checkpoint, comprising copies of new and modified nodes as respective blocks, to the disk;   wherein the second checkpoint comprises pointers to a plurality of blocks of the first checkpoint corresponding to unmodified nodes,   wherein the first checkpoint remains unmodified until the second checkpoint is completed.   
     
     
         12 . The system of  claim 11 , wherein the downlinks comprise physical addresses to the main memory and the disk. 
     
     
         13 . The system of  claim 11 , wherein the one or more processors are further configured to:
 write an instruction to main memory to generate a modified node;   write an instruction to set a dirty bit of the modified node;   receive a request to read the modified node; and   send a read request to main memory to read the modified node.   
     
     
         14 . The system of  claim 13 , wherein the modified node is not written to the disk between setting the dirty bit and reading the modified node. 
     
     
         15 . One or more non-transitory computer readable media comprising instructions that, when executed by one or more processors, cause:
 write a root node of a tree to a memory space, wherein the root node comprises one or more downlinks directly pointing to one or more nodes, and the root node is configured to store a first plurality of pivot keys;   write a plurality of internal nodes of the tree to the memory space, wherein each internal node comprises one or more downlinks directly pointing to one or more nodes, and the plurality of internal nodes are configured to store a second plurality of pivot keys; and   write a plurality of leaf nodes of the tree to the memory space, wherein the plurality of leaf nodes are configured to store a plurality of rows;   write a first checkpoint representing a first state of the tree, comprising a copy of each node as a respective block, to a disk; and   during the write of the first checkpoint, write a modification to one or more of the nodes;   write at least one modification to the one or more nodes to the first checkpoint; and   write a second checkpoint, of a second state of the tree, to the disk;   wherein the second checkpoint comprises pointers to a plurality of blocks of the first checkpoint corresponding to unmodified nodes,   wherein the first checkpoint remains unmodified until the second checkpoint is completed.   
     
     
         16 . The non-transitory computer readable media of  claim 15  further comprising instructions that, when executed by the one or more processors:
 write an instruction to main memory to generate a modified node; and 
 write an instruction to the main memory to set a dirty bit of the modified node. 
 
     
     
         17 . The non-transitory computer readable media of  claim 16  further comprising instructions that, when executed by the one or more processors:
 delay the write of the modified node to the disk; and 
 receive a request to read the modified node; and 
 send a read request to the main memory to read the modified node after setting the dirty bit. 
 
     
     
         18 . The non-transitory computer readable media of  claim 16 , wherein prior to writing a node to the main memory or the disk, the one or more processors are configured to execute instructions to write information corresponding to the node to a write-ahead log (WAL) record. 
     
     
         19 . The non-transitory computer readable media of  claim 18 , wherein each WAL record is idempotent. 
     
     
         20 . The non-transitory computer readable media of  claim 19 , wherein the WAL comprises one or more WAL records that correspond to the tree and one or more additional trees.