The MDBX_opt_split_reserve is available now.

[erthink]

The MDBX_opt_split_reserve feature now available in the master branch.

---

Поддержка опции MDBX_opt_split_reserve добавлена вместе с сопутствующей переделкой page_split(). Это результат поиска управляемого компромисса в сценариях массивных упорядоченных вставок.

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

Для поддержки вставки в таком режиме, в LMDB исходно были предложены опции-флажки MDB_APPEND и MDB_APPENDDUP. В libmdbx, кроме аналогичных опций MDBX_APPEND и MDBX_APPENDDUP, уже давно реализовано автоматическое использование такого подхода, в том числе при вставке ключей в обратном порядке (что обеспечивает ускорение работы индексов до двух раз).

Ещё раз повторю/перефразирую: Плотная укладка ключей в страницы означает минимум неиспользуемых зазоров, т.е. что место используется максимально эффективно. При этом обеспечивается минимальный размер БД, а поиск и чтение работают максимально быстро.
Однако, при плотной укладке ключей любая последующая вставка потребует расщепления страницы, ведь свободного места нет. В результате расщепления листовой страницы получится две заполненные примерно пополам, на добавленную половину придется добавлять ссылку в родительскую страницу, что также потребует её расщепления, и так далее до корня дерева включительно. Поэтому вставки в плотно заполненное дерево очень дороги, а если сделать по одной вставке в каждую листовую страницу, то размер БД буквально удвоится.

Во многих случаях автоматическая описанная плотная укладка ключей является достаточно хорошим вариантом, поэтому работает по-умолчанию. Но эффект последующего удвоения размера БД также нельзя игнорировать и нередко именно он является существенной проблемой. Например, вы импортировали терабайт отсортированных данных, но попытка добавления ещё всего-лишь 1% требует вдвое больше места.

В результате поиска решения появилась опция MDBX_opt_split_reserve и существенно переработана функция page_split():

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

2. При расщеплении страниц будет по-возможности формироваться заданный резерв свободного места:

   • при нулевом значении резерва не будет, соответственно при упорядоченных вставках будет выполнять максимально плотное заполнение страниц;
   • если же задать максимальное значение (50%), то это приведет к максимально равному заполнению половинок.

Таким образом, опцию MDBX_opt_split_reserve можно трактовать как ограничение снизу возможного перекоса при расщеплении страниц.

---

В ближайших планах:

• добавить в mdbx_load и mdbx_defrag опции командной строки для использования новых возможностей;
• добавить опциональный сбор статистики о получении/загрузки страниц;
• реализовать "удаление гроздями" для Erigon;
• провести некоторый рефакторинг page_split() и page_merge(), с тем чтобы преобразовать инвариантные фрагменты кода с массой условий в отдельные функции (т.е. уменьшить кол-во ветвлений и увеличить производительность).

После этого будет релиз 0.14.2. Тем не менее, указанные доработки будут либо изолированными от остального функционала, либо крайне консервативными/осторожными. Поэтому текущую ветку master можно считать релиз-кандидатом.

Обратная связь приветствуется!