Efficient incremental journal truncation policy

1. A method for journal truncation, the method comprising:

maintaining a journal in a memory of a computing system including a plurality of records, wherein each record indicates a transaction in an ordered data structure;

maintaining a truncation queue in the memory including one or more entries, wherein each entry in the truncation queue includes a respective physical on-disk offset associated with a different record of the plurality of records;

determining to truncate the journal; and

truncating records, of the plurality of records, from the journal starting from a beginning record in the journal up to a record associated with the respective physical on-disk offset included in a least recent entry of the one or more entries in the truncation queue, wherein the truncating includes removing the records from the memory.

2. The method of claim 1 , wherein maintaining the truncation queue comprises:

when adding a batch of one or more records to the journal:

determining a physical on-disk offset between a first record, of the one or more records of the batch, having a highest log sequence number (LSN) and a second record associated with a most recent entry in the truncation queue; and

adding the respective physical on-disk offset associated with the first record to the truncation queue when the physical on-disk offset between the first record and the second record is equal to or greater than a portion size threshold; and

refraining from adding the respective physical on-disk offset associated with the first record to the truncation queue when the physical on-disk offset between the first record and the second record is smaller than the portion size threshold.

3. The method of claim 2 , wherein the portion size threshold is a divisor of a maximum size of the journal.

4. The method claim 2 , further comprising:

maintaining a current physical on-disk offset value corresponding to a physical on-disk offset between a last record in the journal and the second record associated with the most recent entry in the truncation queue; and

setting the current physical on-disk offset value to the respective physical on-disk offset associated with the first record when first record is added to the truncation queue.

5. The method of claim 4 , wherein determining the physical on-disk offset between the first record and the second record comprises:

determining a total physical on-disk offset of a first physical on-disk offset between the current physical on-disk offset value and the respective physical on-disk offset associated with the second record and a second physical on-disk offset between a third record and the respective physical on-disk offset associated with the first record, of the batch of one or more records, having a lowest LSN.

6. The method of claim 1 , wherein each entry in the truncation queue further includes a log sequence number (LSN) of a record associated with the entry.

7. 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.

8. A system comprising:

one or more processors; and

at least one memory, the one or more processors and the at least one memory configured to:

maintain a journal in the memory including a plurality of records, wherein each record indicates a transaction in an ordered data structure;

maintain a truncation queue in the memory including one or more entries,

wherein each entry in the truncation queue includes a respective physical on-disk offset associated with a different record of the plurality of records;

determine to truncate the journal; and

truncate records, of the plurality of records, from the journal starting from a beginning record in the journal up to a record associated with the respective physical on-disk offset included in a least recent entry of the one or more entries in the truncation queue, wherein the truncating includes removing the records from the memory.

9. The system of claim 8 , wherein the one or more processors and the at least one memory being configured to maintaining the truncation queue comprises the one or more processors and the at least one memory being configured to:

when adding a batch of one or more records to the journal:

determine a physical on-disk offset between a first record, of the one or more records of the batch, having a highest log sequence number (LSN) and a second record associated with a most recent entry in the truncation queue; and

add the respective physical on-disk offset associated with the first record to the truncation queue when the physical on-disk offset between the first record and the second record is equal to or greater than a portion size threshold; and

refrain from adding the respective physical on-disk offset associated with the first record to the truncation queue when the physical on-disk offset between the first record and the second record is smaller than the portion size threshold.

10. The system of claim 9 , wherein the portion size threshold is a divisor of a maximum size of the journal.

11. The system claim 9 , wherein the one or more processors and the at least one memory are further configured to:

maintain a current physical on-disk offset value corresponding to a physical on-disk offset between a last record in the journal and the second record associated with the most recent entry in the truncation queue; and

set the current physical on-disk offset value to the respective physical on-disk offset associated with the first record when first record is added to the truncation queue.

12. The system of claim 11 , wherein the one or more processors and the at least one memory being configured to determine the physical on-disk offset between the first record and the second record comprises the one or more processors and the at least one memory being configured to:

determine a total physical on-disk offset of a first physical on-disk offset between the current physical on-disk offset value and the respective physical on-disk offset associated with the second record and a second physical on-disk offset between a third record and the respective physical on-disk offset associated with the first record, of the batch of one or more records, having a lowest LSN.

13. The system of claim 8 , wherein each entry in the truncation queue further includes a log sequence number (LSN) of a record associated with the entry.

14. The system of claim 8 , 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.

15. 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 for journal truncation, the operations comprising:

maintaining a journal in a memory of the computing system including a plurality of records, wherein each record indicates a transaction in an ordered data structure;

maintaining a truncation queue in the memory including one or more entries, wherein each entry in the truncation queue includes a respective physical on-disk offset associated with a different record of the plurality of records;

determining to truncate the journal; and

truncating records, of the plurality of records, from the journal starting from a beginning record in the journal up to a record associated with the respective physical on-disk offset included in a least recent entry of the one or more entries in the truncation queue, wherein the truncating includes removing the records from the memory.

16. The non-transitory computer-readable medium of claim 15 , wherein maintaining the truncation queue comprises:

when adding a batch of one or more records to the journal:

determining a physical on-disk offset between a first record, of the one or more records of the batch, having a highest log sequence number (LSN) and a second record associated with a most recent entry in the truncation queue; and

adding the respective physical on-disk offset associated with the first record to the truncation queue when the physical on-disk offset between the first record and the second record is equal to or greater than a portion size threshold; and

refraining from adding the respective physical on-disk offset associated with the first record to the truncation queue when the physical on-disk offset between the first record and the second record is smaller than the portion size threshold.

17. The non-transitory computer-readable medium of claim 16 , wherein the portion size threshold is a divisor of a maximum size of the journal.

18. The non-transitory computer-readable medium claim 16 , the operations further comprising:

maintaining a current physical on-disk offset value corresponding to a physical on-disk offset between a last record in the journal and the second record associated with the most recent entry in the truncation queue; and

setting the current physical on-disk offset value to the respective physical on-disk offset associated with the first record when first record is added to the truncation queue.

19. The non-transitory computer-readable medium of claim 18 , wherein determining the physical on-disk offset between the first record and the second record comprises:

determining a total physical on-disk offset of a first physical on-disk offset between the current physical on-disk offset value and the respective physical on-disk offset associated with the second record and a second physical on-disk offset between a third record and the respective physical on-disk offset associated with the first record, of the batch of one or more records, having a lowest LSN.

20. The non-transitory computer-readable medium of claim 15 , wherein each entry in the truncation queue further includes a log sequence number (LSN) of a record associated with the entry.