Durable multiversion B+-tree
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.
1. A method of comprising:
writing, by a processor to a memory space, a root page of a tree, wherein the root page comprises one or more downlinks directly pointing to one or more pages, and the root page is configured to store a first plurality of pivot keys;
writing, by the processor to the memory space, a plurality of internal pages of the tree, wherein each internal page comprises one or more downlinks directly pointing to one or more pages, and the plurality of internal pages are configured to store a second plurality of pivot keys;
writing, by the processor to the memory space, a plurality of leaf pages of the tree, wherein the plurality of leaf pages 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 page 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 pages;
writing, by the processor, at least one modification to the one or more pages 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 pages,
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 page; and
writing, by the processor, an instruction to the main memory to set a dirty bit of the modified page.
4. The method of claim 3 further comprises:
delaying, by the processor, writing the modified page to the disk;
receiving, by the processor, a request to read the modified page; and
sending, by the processor, a read request to the main memory to read the modified page after setting the dirty bit.
5. The method of claim 3 , wherein prior to writing a page to the main memory or the disk, the processor writes information corresponding to the page 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 pages to the main memory and the disk, wherein the pages comprise a root page, one or more internal pages, and one or more leaf pages;
write one or more pivot keys to the root page, wherein the root page comprises one or more downlinks directly pointing to one or more pages; and
write one or more pivot keys to the one or more internal pages, wherein each of the one or more internal pages comprises one or more downlinks directly pointing to one or more pages;
write a first checkpoint, comprising copies of the plurality of pages as respective blocks, to the disk;
during the write of the first checkpoint, write a modification to one or more of the pages;
write at least one modification to the one or more pages after writing the first checkpoint; and
write a second checkpoint, comprising copies of new and modified pages as respective blocks, to the disk;
wherein the second checkpoint comprises pointers to a plurality of blocks of the first checkpoint corresponding to unmodified pages,
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 page;
write an instruction to set a dirty bit of the modified page;
receive a request to read the modified page; and
send a read request to main memory to read the modified page.
14. The system of claim 13 , wherein the modified page is not written to the disk between setting the dirty bit and reading the modified page.
15. One or more non-transitory computer readable media comprising instructions that, when executed by one or more processors, cause:
write a root page of a tree to a memory space, wherein the root page comprises one or more downlinks directly pointing to one or more pages, and the root page is configured to store a first plurality of pivot keys;
write a plurality of internal pages of the tree to the memory space, wherein each internal page comprises one or more downlinks directly pointing to one or more pages, and the plurality of internal pages are configured to store a second plurality of pivot keys; and
write a plurality of leaf pages of the tree to the memory space, wherein the plurality of leaf pages are configured to store a plurality of rows;
write a first checkpoint representing a first state of the tree, comprising a copy of each page as a respective block, to a disk; and
during the write of the first checkpoint, write a modification to one or more of the pages;
write at least one modification to the one or more pages 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 pages,
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 page; and
write an instruction to the main memory to set a dirty bit of the modified page.
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 page to the disk; and
receive a request to read the modified page; and
send a read request to the main memory to read the modified page after setting the dirty bit.
18. The non-transitory computer readable media of claim 16 , wherein prior to writing a page to the main memory or the disk, the one or more processors are configured to execute instructions to write information corresponding to the page 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.