Efficient write-back for journal truncation

1. A method, comprising:

maintaining a journal in a memory of a computing system including a plurality of records, wherein each record indicates a transaction associated with one or more pages in an ordered data structure;

maintaining a dirty list in the memory including an entry for each page indicated by a record in the journal, wherein each entry in the dirty list includes a respective first log sequence number (LSN) associated with a least recent record of the plurality of records that indicates the page and a respective second LSN associated with a most recent record of the plurality of records that indicates the page;

determining to truncate the journal, the truncation comprising removing one or more of the plurality of records from the memory;

identifying, based at least in part on the dirty list, one or more records, of the plurality of records, from the journal to write back to a disk, by:

obtaining a maximum LSN value for the journal truncation;

checking entries in the dirty list, starting from a least recent entry in the dirty list; and

determining whether the respective first LSN of the entry associated with the least recent record of the plurality of records that indicates the page is equal to or less than the maximum LSN value; and

writing back the one or more records to the disk.

2. The method of claim 1 , wherein maintaining the dirty list comprises:

adding a record to the journal, wherein the record indicates a first page and a third LSN;

determining whether the dirty list includes an entry for the first page;

when the dirty list includes an entry for the first page, updating the respective second LSN in the entry to the LSN; and

when the dirty list does not include an entry for the first page, adding an entry to the dirty list including the third LSN as a respective first LSN indicating the least recent record of the plurality of records that indicates the first page and the third LSN as a respective second LSN indicating the most recent record of the plurality of records that indicates the first page.

3. The method of claim 1 , wherein each entry in the dirty list is associated with a first pointer to a previous entry in the dirty list and a second pointer to a next entry in the dirty list.

4. The method of claim 1 , further comprising:

when the respective first LSN of the entry is larger than the maximum LSN value:

refraining from writing back the respective record associated with the respective first LSN; and

stopping checking the entries in the dirty list.

5. The method of claim 1 , further comprising:

when the entry is for a hot page:

skipping the entry; and

checking a next entry in the dirty list.

6. The method of claim 1 , further comprising:

when the first LSN of the entry is equal to or smaller than the maximum LSN value:

writing back the respective record, associated with the first LSN, to the disk;

removing the entry from the dirty list; and

checking a next entry in the dirty list.

7. The method of claim 6 , further comprising:

truncating the respective record, associated with the first LSN, from the journal.

8. The method of claim 1 , further comprising:

determining to write back the one or more identified records and to refrain from truncating the one or more identified records from the journal when the one or more identified records are associated with at least one hot page.

9. The method of claim 1 , wherein the ordered data structure comprises a copy-on-write (COW) B+ tree, and wherein the journal comprises a write-ahead log (WAL) for the COW B+ tree.

10. A system comprising:

one or more processors; and

non-transitory computer-readable medium comprising instructions that, when executed by one or more processors of a computing system, cause the computing system to perform operations comprising:

maintaining a journal in the memory including a plurality of records, wherein each record indicates a transaction associated with one or more pages in an ordered data structure;

maintaining a dirty list in the memory including an entry for each page indicated by a record in the journal, wherein each entry in the dirty list includes a respective first log sequence number (LSN) associated with a least recent record of the plurality of records that indicates the page and a respective second LSN associated with a most recent record of the plurality of records that indicates the page;

determining to truncate the journal, the truncation comprising removing one or more of the plurality of records from the memory;

identifying, based at least in parton the dirty list, one or more records, of the plurality of records, from the journal to write back to a disk, by:

obtaining a maximum LSN value for the journal truncation;

checking entries in the dirty list, starting from a least recent entry in the dirty list; and

determining whether the respective first LSN of the entry associated with the least recent record of the plurality of records that indicates the page is equal to or less than the maximum LSN value; and

write-writing back the one or more records to the disk.

11. The system of claim 10 , wherein maintaining the dirty list comprises:

adding a record to the journal, wherein the record indicates a first page and a third LSN;

determining whether the dirty list includes an entry for the first page;

when the dirty list includes an entry for the first page, updating the respective second LSN in the entry to the LSN; and

when the dirty list does not include an entry for the first page, adding an entry to the dirty list including the third LSN as a respective first LSN indicating the least recent record of the plurality of records that indicates the first page and the third LSN as a respective second LSN indicating the most recent record of the plurality of records that indicates the first page.

12. The system of claim 10 , wherein each entry in the dirty list is associated with a first pointer to a previous entry in the dirty list and a second pointer to a next entry in the dirty list.

13. The system of claim 10 , the operations further comprising:

when the respective first LSN of the entry is larger than the maximum LSN value:

refraining from writing back the respective record associated with the respective first LSN; and

stop checking the entries in the dirty list.

14. The system of claim 10 , the operations further comprising:

when the entry is for a hot page:

skipping the entry; and

checking a next entry in the dirty list.

15. The system of claim 10 , the operations further comprising:

when the first LSN of the entry is equal to or smaller than the maximum LSN value:

writing back the respective record, associated with the first LSN, to the disk;

removing the entry from the dirty list; and

checking a next entry in the dirty list.

16. The system of claim 15 , the operations further comprising:

truncating the respective record, associated with the first LSN, from the journal.

17. The system of claim 10 , the operations further comprising:

determining to write back the one or more identified records and to refrain from truncating the one or more identified records from the journal when the one or more identified records are associated with at least one hot page.

18. A non-transitory computer-readable medium comprising instructions that, when executed by one or more processors of a computing system, cause the computing system to perform operations comprising:

maintaining a journal in a memory of the computing system including a plurality of records, wherein each record indicates a transaction associated with one or more pages in an ordered data structure;

maintaining a dirty list in the memory including an entry for each page indicated by a record in the journal, wherein each entry in the dirty list includes a respective first log sequence number (LSN) associated with a least recent record of the plurality of records that indicates the page and a respective second LSN associated with a most recent record of the plurality of records that indicates the page;

determining to truncate the journal, the truncation comprising removing one or more of the plurality of records from the memory;

identifying, based at least in part on the dirty list, one or more records, of the plurality of records, from the journal to write back to a disk, by:

obtaining a maximum LSN value for the journal truncation;

checking entries in the dirty list, starting from a least recent entry in the dirty list; and

determining whether the respective first LSN of the entry associated with the least recent record of the plurality of records that indicates the page is equal to or less than the maximum LSN value; and

writing back the one or more records to the disk.

19. The non-transitory computer readable medium of claim 18 , wherein maintaining the dirty list comprises:

adding a record to the journal, wherein the record indicates a first page and a third LSN;

determining whether the dirty list includes an entry for the first page;

when the dirty list includes an entry for the first page, updating the respective second LSN in the entry to the LSN; and

when the dirty list does not include an entry for the first page, adding an entry to the dirty list including the third LSN as a respective first LSN indicating the least recent record of the plurality of records that indicates the first page and the third LSN as a respective second LSN indicating the most recent record of the plurality of records that indicates the first page.

20. The non-transitory computer readable medium of claim 18 , wherein each entry in the dirty list is associated with a first pointer to a previous entry in the dirty list and a second pointer to a next entry in the dirty list.