Reason for excluding append pages from regular and reserve free lists during page allocation.

[Shravyabhat]

We use TuplDB in production and frequently encounter DatabaseFullException due to high write traffic.
To mitigate this, we have implemented throttlers that reject write requests once memory utilization reaches a defined threshold.
For instance, in a t3.small EC2 instance, throttlers are configured to trigger when utilization nears the set limit.

These throttlers rely on the stats method from the Tupl Database class, which is called asynchronously to determine the current memory state and manage request flow accordingly.

This stats method has the below issue.

Issue Observed in TuplDB

Append List Usage in AllocPage :

• The AllocPage method does not utilize the append list for both the regular and reserve free lists.
• Question: Is there a specific reason for excluding the append pages in the AllocPage method despite their inclusion in the database statistics?

This causes the stats method to over report the number of free pages causing our throttler’s measurement of utilization to be lower than the actual usage. Therefore, the throttler will let requests go through even when actual usage is close to max DB size.

[broneill]

I'm wondering why you're observing DatabaseFullException, and by what means space is being freed. I can think of couple reasons why the exception is being thrown, when the PageManager is used:

1. The backing file is opened with a MappedPageArray with a small page count
2. An explicit capacity limit has been set

How is space being freed? Just natural updates/deletes of records or is eviction being used?

[Shravyabhat]

Yes, an explicit capacity limit is set, and space is freed through both natural updates/deletes and eviction.

However, the key concern remains unresolved:

Why are Append Pages not used in the AllocPage method for the Regular and Reserve Free Lists?

Despite not being utilized for allocation, these Append Free Pages are still included in the stats method, leading to an overestimation of available free pages. This misrepresentation causes the throttler to underestimate actual memory usage, allowing more write requests to go through even when the database is close to its capacity limit.

[broneill]

Some notes regarding the three types of free lists:

1. The regular free list is the "safe" default to use, which ensures that pages which appended to the end are never used again until after a checkpoint. This is an essential feature of the copy-on-write design.
2. The recycle free list permits appended pages to be unappended because pages which are added to it are known to not be referenced by any data structure stored by the last checkpoint.
3. The reserve list is only used during a file compaction operation, which is optional and only invoked manually. If the compaction aborts, these pages are moved back into the regular free list.

The free pages number reported by the stats object is a simple measure of the maximum potential free space, but not all of it is available until after a checkpoint or the completion of compaction.

You might benefit from an enhanced stats object which reports more numbers.

[Shravyabhat]

To clarify, by "enhanced stats object which reports more numbers," do you mean:

1. More free pages reporting the maximum potential free space.
2. Or reporting the immediate usable stats which would not include the append list which are not readily usable until after checkpoint.

[broneill]

A stats object which reports the number for the immediately available pages would help in your case. The existing freePages number would remain the same.

[Shravyabhat]

Thank you for the clarifications!

But, this raises another question:

Would it be feasible to implement either of the following approaches to improve space availability?

1. Immediate Commit – Instead of batch committing, can pages be moved from append list to remove list as soon as they get added into the append list by triggering the commit there.

2. More Frequent Checkpoints – Would increasing the checkpoint frequency help in making free pages available sooner? Or would this cause data inconsistency?

[broneill]

Only with more frequent checkpoints can the free space become available sooner.

Are you running TuplDB as a pure cache or do you need persistence? If you configure it without a file, then checkpoints go away and freed pages are always immediately available.

[Shravyabhat]

We do need persistence.

So, currently we plan to go ahead with the implementation of a enhanced stats method which will provide the actual free pages value and not the max potential.

[broneill]

If you're making any changes to the code, be sure to create a PR or provide a link to your fork, since it's the easiest way to be compliant with the software license.