KahaDB index compaction

KahaDB contains two components, he journal and the index. The journal stores all of the data (mesages, acks, metadata, etc) as commands in the journal and the index is used to keep track of where certain things are for quick look up (such as being able to iterate over messages by order or by id). The goal of this issue is to address compacting the index (stored as page files) when large. Journal compaction is a separate issue that will be addressed separately. Inded compaction will be done in two phases, truncation and defrag.

Index usage in KahaDB

The KahaDB index is stored using a PageFile, which is just a contiguous block of pages in a single file. The page file is essentially a big linked list on disk, and writes will be written to as many pages as needed and flushed to disk. Pages can also be cached in memory for fast access.

When updates are written to the index and there isn't enough space, new pages are allocated as necessary which grows the file. When deletes happen pages are just marked as free and reclaimed into a list of free pages. Writing updates to the index first looks to re-use pages that are marked as free and will only allocate new space if needed. Under normal use cases this leads to a pretty stable PageFile size as the amount of pages necessary get allocated.

The need for compaction

Sometimes the PageFile can grow quite large. The most common scenario for this is a large backlog on a destination. A large backlog will cause a lot of extra writes to the index to track all the messages which causes the page file to grow quite large. Once the backlog is gone the pages will be marked as free and reclaimed to be re-used, but the page file itself will never shrink. This can lead to a huge PageFile with a lot of empty space that just isn't necessary.

Compaction via truncation (#2233)

A simple way to help solve this problem is using a truncation compaction strategy. Truncation helps in this scenario by simply truncating the file and removing the excess free pages. This works well because all we need to do is remove the free pages from the tracking and then set the length of the file to the new size which is nearly instant time, so there is no noticeable performance impact.

While this strategy is very fast and easy to implement, the major and obvious limitation to this strategy is it only works if the free pages are at the end of the file. If the free pages are in the middle of the file his won't work so we can't shrink the file. This could happen, for example, if a new destination was created while there was a big backlog and it was written to the index. This means all the eventual free pages that would be reclaimed after the backlog is gone would be in the middle of the file so we could not truncate.

Compaction via defragmentation (Future plans)

The goal here is to address the shortcomings of truncation and there are a few ideas to explore. One way to reclaim space is to just re-write the entire page file and drop free pages but this would be pretty slow. Another idea is to implement defragmentation to move pages and reduce the empty space in the middle of the file so that truncation could work and there are a few ideas to try:

1. One option to explore is we re-write/move pages at the end of the file to early free pages. Eventually we will end up with enough free pages at the end of the file and we can truncate again. This is more complex because the page file forms lots of separate linked lists within the page file. We could convert the linked lists to a doubly linked lists so that when we move pages we can update the metadata of the page that points to the page so we don't break the list. This also means it would not be backwards compatible (you'd need to start with a fresh page file) because existing page files don't contain markers for the previous page in the list.
2. Another option would be to still move pages to earlier in the file, but add another index that's a virtual page file and a look up table that would likely be stored in a second small page file. It would just be a map that we could use to find the real location of a page based off the stored pageId if it was moved.
3. A third option worth exploring is to just rewrite stored destination metadata to earlier in the file and over time truncation would naturally work as backlogs are gone. The main cause of big files (if truncation is enabled) would be data that is permanent like destination data so moving it earlier int he page file could allow cleanup. Stored destination metadata just contains the "first" pages of each of its indexes in the linked list so you don't need to store previous pages (so no doubly linked list). One flaw is that this may not necessarily work as intended though if a destination has a lot of durable subscriptions and they get added later after a big backlog as that would add pages to the index that were not moved.

It's TBD which would work best.