Database corruption by cross-merging LEAF and BRANCH pages (inherited from LMDB)

[erthink]

This bug discovered by long-running test, which add/update/delete key-value pairs with stochastically choosing the length of key and data.

Running such test with quantity of transaction in range from 100,000 to 1,000,000 fails with a probability of about 0.1 - 1%.

The investigation showed that the damage to the database structure is due to erroneous / invalid merging of different types of pages, i.e. mering LEAF into BRANCH or BRANCH into LEAF.

[erthink]

English version by Google.

Это одна из фатальных ошибок унаследованных из LMDB - существенное упущение в дизайне и алгоритмах, которое замаскированно плохим стилем кодирования.

Суть проблемы:

• высота дерева может увеличиваться даже при удалении данных (пояснение ниже).
• в коде пере-балансировке и слияния есть несколько ошибок/упущений, но увеличение высоты дерева приводит к разрушению БД из-за вот этого кодо-ребуса в LMDB.

Рост дерева возможен при существенном различии/разбросе длины ключей, так как:

• в каждой не-листовой странице дерева содержатся записи-указатели на дочерние страницы.
• каждая такая запись состоит из номера дочерней страницы и ключа, значение которого является наименьшим из всех дочерних записей.
• более того, в качестве оптимизации для экономии места, ключ первой записи дочерней страницы часто не хранится, так как совпадает с ключом в записи-указателе на родительской странице.

Соответственно, если при вставке/удалении на странице меняется значение ключа у первой записи, то это изменение должно быть вытолкнуто в родительскую страницу, и при необходимости рекурсивно до корня дерева.

Однако, при таком обновлении, новое значение ключа может быть существенно длиннее предыдущего. Из-за чего на родительской странице может не хватить места. В том числе, это может произойти при удалении.

Например, если было две записи {key="a", value="x"} и {key="bbb...bbb", value="y"} и мы удаляем первую, то в родительской странице короткий ключ "a" должен быть заменен на длинный "bbb...bbb".

Если на родительской странице не хватает места, то она должна быть разделена. В свою очередь, это потребует вставки в её родительскую страницу, и в ней тоже может не быть места, и так далее.

В результате, удаление может привести к увеличению высоты дерева страниц и LMDB уничтожит ваши данные.

[hyc]

Sounds like http://www.openldap.org/its/index.cgi/Software%20Bugs?id=8258

[erthink]

Yes @hyc , this is the same bug/issue, but it newer has been fixed (corresponding ITS-patch is applied a time ago).

Briefly, independent of merge-or-move strategy it is possible that a tree will be higher after the deletion than the before.

[erthink]

Testcase is simple (typo is fixed for now):

• let S is a sequence of 3-byte long numbers (e.g 0...2^24-1).
• insert a lot of "even" items with short keys of form "Sa".
• insert a lot of "odd" items with long keys of form "Sb+any-long-string-upto-maxkeylength".
• remove an "even" items.

[hyc]

By "odd" and "even" do you mean the long and short keys are interleaved? Otherwise I don't see how this can trigger the issue.

Does the its8258 test program succeed or crash for you? It runs fine here.

[erthink]

Yes, certainly.
It seems obvious .

[hyc]

Unable to reproduce any failure...

mtest7.c.txt

[erthink]

I tried the given mtest7 and then made some changes to fit the scenario I tried to describe above.

Unfortunately it don't reproduce the failure nor in the original LMDB, nor in the MDBX.
However, a longer stochastic test steadily reproduces the problem in the MDBX.
This test currently couldn't be run with LMDB, i.e. a lot of API-related changes are required.

On the other hand, it looks like I'm close to fixing the problem in MDBX.
With my current fixes, the database was never corrupted due relabalance itself, but in complex cases, the cursor position becomes invalid after deletion.
In other words, the page stack of the cursor becomes invalid after deletion, in some cases when the tree grows due to rebalancing.

I expect to complete the work within a week. After that, we can try to adapt the stochastic test for LMDB and check if there is this problem.

[erthink]

Fixed in the 'master' branch now.