Incoherent flaw of Linux' unified page/buffer cache

[erthink]

Исходя из наблюдаемого в серии экспериментов, можно сделать вывод, что есть некий дефект «некогерентности» в unified page cache ядра Linux (как минимум в linux-image-4.19.0-18-amd64, 4.19.208-1), который проявляется в купе при взаимодействии с остальными компонентами (io-scheduler, virtual memory management, драйвер диска/контроллера).
Из-за этого некоторая часть страниц записанная одним процессом, становится видимой другому процессу с задержкой и неравномерно/неодновременно.
В результате, процесс-читатель БД следуя по ссылкам (meta-page => maindb-root => maindb_leaf => subdb-root => ...) иногда видит смесь страниц измененных в последней транзакции и устаревших данных.

1. Упрощенно есть два процесса W (писатель), R (читатель) и отображенный к ним обоим в память файл БД.
2. При фиксации транзакции, процесс W делает следующее (упрощенно):
   • через дескриптор записывает в файл БД все измененные страницы, включая новую корневую страницу b-tree;
   • вызывает fdatasync() если включен надежный режим;
   • обновляет одну из meta-страниц, указывая в ней номер новой корневой страницы БД и номер фиксируемой транзакции;
   • еще раз вызывает fdatasync() если включен надежный режим.
3. При старте читающей транзакции, процесс R делает следующее (упрощенно):
   • читает все три мета-страницы и выбирает "последнюю" (с максимальным номером транзакции);
   • считывает из мета-страницы всю информацию, включая номер корневой страницы БД;
   • проверят что ничего не поменялось и повторяет цикл если что-то не так;
   • продолжает транзакцию, предполагая что в памяти (через отображенный файл) ему видны актуальные данные записанные процессом W при фиксации транзакции.

Всё вышеописанное работает при условии «когерентного» unified page cache внутри ядра ОС. Суть в том, что во всех случаях ядру нет смысла иметь в памяти более одной копии каждой страницы отображенного файла БД. Поэтому, как только кто-то пишет в этот файл через файловый дескриптор, эти изменения сразу видны всем процессам отобразившим файл БД в память:

• если логическая страница файла БД уже загружена в память, то она обновляется inplace и уже после отправляется к io-scheduler для записи на носитель;
• иначе, если страница отсутствует в ОЗУ, то создается с помещением в неё записываемых данных, и уже затем попадает в очереди к io-sheduler;
• но каждый процесс всегда видит новые данные, сразу по завершению write()в писателе.

В наблюдаемых случаях, очень-очень похоже, что происходит следующее:

• используется NOSYNC-режимы без MDBX_WRITEMAP, т.е. данные пишутся через файловый дескриптор, но без последующего fdatasync();
• внутри ядра записанные данные не сразу попадают в "unified page cache", либо из-за направления в io-очередь одновременно существуют старые и новые версии закэшированных страниц;
• при некоторой небольшой паузе новые данные "доезжают" и проблема исчезает;
• в результате процесс-читатель видит обновленную мета-страницу, но читая корневую страницу БД иногда видит старые данные.

Был проведен эксперимент с включением режима MDBX_WRITEMAP. При этом данные изменяются непосредственно в памяти, соответствующие страницы при необходимости подгружаются в unified page cache, меняются в памяти, помечаются «грязными» и уже после могут быть направлены к очереди к io-планировщику. Это устранило проблему и подтвердило гипотезу, но по-хорошему ребуется перепроверка (многократно перепроверено и подтверждено).

Пока проблема была зафиксирована только на ядре 4.19 и ни разу не была замечена на ядрах 5.4, 5.8, 5.11 и 5.13. Поэтому, предположительно, соответствующий баг/недочет в ядре уже устранен в актуальных ядрах Linux. Многократно перепроверено и подтверждено на всех актуальных ядрах Linux, но проблема воспроизводится (в том числе собственными тестами libmdbx) только если на машине параллельно работает нагруженный SIEM.

[erthink]

A description in English may be provided later.
Briefly it is a temporary false corruption (MDBX_CORRUPTION error) due flaw of kernel 4.19 unified page/buffer cache.

[erthink]

Related to #67.

[erthink]

For now, just-in-case, had release a painless workaround for kernels < 5.4
However, for >= 5.4 kernels still unable to reproduce, but not sure there no this flaw.
I continue digging.

[erthink]

Reproduced on the 5.10 (linux-image-5.10.0-0.bpo.9-amd64/buster-backports,now 5.10.70-1~bpo10+1 amd64).
Continue digging.

[erthink]

Reproduced on the 5.15.15-2~bpo11+1 (debian).
Continue digging.

[erthink]

1. For now I am sure that the cause of the problem is an bug/flaw in the Linux' implementation unified page/buffer cache.
2. To ensure that problems are avoided before the final workaround is released, it is enough to use MDBX_WRITEMAP mode.
3. Unfortunately, so far only one reproduce scenario is known, which requires a highload to the OS kernel produced by a complex close-sourced commercial system. It should be noted that the problem is also reproduced in libmdbx's own tests, but only when ones work simultaneously with the mentioned specific highload.
4. The problem could not be reproduced quickly on the 5.4 and newer kernel. Therefore, I thought that there were no problems in kernels >= 5.4, which is why an emergency v0.11.5 was released with a temporary workaround. But 12 days ago I reproduces this problem on 5.15, so this released temporary workaround is futile.
5. Preliminaly implementation of a complete and final workaround is available now in the devel branch. However, I need more time to test it.

[erthink]

Good news:

1. There is full confidence that the problem is not the result of any errors or flaws in the libmdbx.
2. The devel branch now contain the complete workaround.
3. This workaround has been tested and is fully confident in its effectiveness and reliability, including on any OS and/or CPU.

Bad news:

1. Unfortunately, there is no complete certainty about the causes of the problem.
2. Most likely, the reason is an error in the implementation of the unified page/buffer cache inside the Linux kernel, but based on what is observed, it is impossible to exclude a defect in the cache and/or NUMA/MESI interaction of Intel processors.
3. Therefore the patch will remain active for all operating systems and CPU architectures until there is complete confidence in the causes of the problem, even though it may lead to some (insignificant) decrease in performance.

---

Some technical details:

• The problem appears only when the root page of internal MainDB or FreeDB/GC is updated immediately before the meta page is written.
• The delay of a single memcmp() for check the updated root page is enough to drown out the problem, i.e. only the inclusion of the one part of workaround cures the problem (unable to reproduce).