"ENSURE: empty page must be defined as empty type" when adding and removing from collections simultaneously

[oleksii-datsiuk]

LiteDB 5.0.17, Windows 11, .NET6

I have DB with 2 collections. 3 threads are working with this DB in parallel. The first thread adds documents to the first collection. The second thread adds documents to the second collection. The third thread removes all documents from one of these collections.

In such a scenario, I get "ENSURE: empty page must be defined as empty type" error.

I debugged it for version 5.0.17 and have found 2 different reasons for this problem. I see that it is also reproducible in 5.0.20, and seems that reproducible even much more often.

Here I share my observations.

---

Problems are related with the header page. This page does not belong to any specific collection and could be accessible (read and written) from different transactions.

To reproduce the problem we need to work with more than 1 collection. If we modify single collection from multiple transactions, the problem is not reproducible, because collection is locked by the first transaction that modifies this collection. This lock prevents access to the collection pages as well as to the header page.

But if we work with multiple collections, these locks don't help to synchronize access to the header page. To solve this problem LiteDB has lock on _header variable. But this lock is used not in all places where header page is accessed (and even modified). And here comes the first source of the problem.

The problem generally is related to _header.FreeEmptyPageList property. This property references first free page which could be retrieved to be used. In the linked-list fashion it has reference on the next free page, and so on. When we take page form this list, we need to set _header.FreeEmptyPageList to reference to the next free page.

So problem happens in TransactionService.PersistDirtyPages(). Here we modify header twice, but lock is taken only in one place. The problem is that following 2 lines are not in the lock:

page.Item.NextPageID = _header.FreeEmptyPageList;
_header.FreeEmptyPageList = _transPages.FirstDeletedPageID;

PersistDirtyPages is called on Commit and on Safepoint. In case of commit, we execute the 2 lines above. They are actually adding new page to the free page list. And this code comes into race conditions with Snapshot.NewPage(), where we take free page to be used for index or data. What happens here, is following (due to the lack of synchronization):

1. PersistDirtyPages wants to add some page to the list of empty page. So it calls page.Item.NextPageID = _header.FreeEmptyPageList to make this page reference the current free page list head.
2. Right after that Snapshot.NewPage() takes page from the free list (it is needed for some Insert operation) and calls this: _header.FreeEmptyPageList = free.NextPageID. Essentially it removes "free" page from the free page list.
3. After that, PersistDirtyPages() executes next line: _header.FreeEmptyPageList = _transPages.FirstDeletedPageID. It adds pages released by transaction to the free page list. Last page in this list has NextPageID set to the previously available free list head page (see step 1). So in fact it returns page back to the free page list (because last of the newly added free pages now references this page as NextPageID, and ignores changes made in step 2).
4. Finally all free pages that are going after this conflicting page will be lost, because Snapshot.NewPage() executes: free.NextPageID = uint.MaxValue.

As a result we have the same page to be used for index/data and to be present in the free page list. Code that acquired this page (step 2) sets its type to Index, Data, or maybe something else. But when some time later some other branch of execution wants to acquire this page from the free page list, it turns out, that it has type Index or Data, and so we get "ENSURE: empty page must be defined as empty type".

Theoretically, we could solve this problem by locking these 2 lines by _header. But it seems to be even more safe to lock whole block of PersistDirtyPages code that has access to _header, to make all access to the _header atomic. I have found that this was already done in code earlier, but was removed with the commit 3acd003 (commit message was "Remove debug log and fix transaction log"). It was part of the implementation of a new transaction approach. Probably there were some reasons to do this exact change, but maybe that "reason" should be solved in some other way, because for me it looks like this lock is really needed.

But when we come to the second source of the problem, I will show that this lock should be moved even higher in the call hierarchy - to the Commit function itself.

---

There is also second source of this ENSURE error. It is related to the fact that header page is not part of any transaction and snapshot, while index and data pages are.

When one transaction adds page to the _header.FreeEmptyPageList on commit, all transactions immediately see this page and may try to acquire it when they need new index or data page. However problem is that in WAL index we may have different versions of each page. And each transaction may have its own Snapshot of the pages belonging to some collection. And each snapshot has _readVersion field, which specifies maximum version of the page in WAL index which could be used. When Snapshot.ReadPage() calls _walIndex.GetPageIndex(), it passes its _readVersion value, and so it can get only version of the page that is not newer than _readVersion. And this older version of the page may have type "Index" or "Data", and not "Empty".

So in other words: in transaction-independent header page we see that page is already free (it is assigned to _header.FreeEmptyPageList), but transaction only sees old version of the page which doesn't have "Empty" type. That's why acquiring this page causes "ENSURE: empty page must be defined as empty type".

To solve this problem we just need to take latest version of the page if we are acquiring new page, and not take into account Snapshot._readVersion.

---

It turned out, that during Commit operation TransactionService.PersistDirtyPages() should be executed as atomic operation together with _walIndex.ConfirmTransaction(). This will ensure that page that is added to _header.FreeEmptyPageList (by PersistDirtyPages) will get new version added to WalIndex. So that next operation which wants to acquires free page will both see this page in _header.FreeEmptyPageList and see its last version in WalIndex. Otherwise race conditions sometimes cause Snapshot.NewPage() to not see new version of the page in the WAL index even after this page is added to free page list.

Also, all changes to the header page which are done in TransactionService.PersistDirtyPages() are done only in the situation when commit is perfromed and when _transPages.HeaderChanged.

According to all this, it makes most sense to remove all header locks from TransactionService.PersistDirtyPages() and add header lock to the whole if-body of the Commit function (inside if (_mode == LockMode.Write || _transPages.HeaderChanged)).

---

I attach sample program to reproduce the problem. Also I will create PR with all the fixes described here.

It is still possible that there will be even more problems in the latest version which didn't exist in 5.0.17 which I was debugging.
Program5.zip

[mbdavid]

Hi @oleksii-datsiuk, firstly I would like to thank you so much for your observations and such detailed analysis about LiteDB. In the last few weeks I managed to organize a small team and we are revisiting and correcting the main problems. And this, certainly, is one of the most important bugs that LiteDB has: corrupting in environments and situations that I cannot simulate.
I planned LiteDB 5 to support multiple writing transactions, but only 1 per collection. The header is a very specific page and different from the others because it has a single instance in memory (although it is also stored in the log). I confess that it was a risky option, but I believed it was possible and made sense, since all data (except the header) has its own unique pages and does not communicate with each other. Today, when I think about it again, I believe that a good write lock system per database (without preventing anyone from reading) would be enough for the general use of LiteDB.
I saw that you created a pull request and I will look into it and get back to you.

Thanks for the effort