Skip to content
EN

Том III. Внутренние механизмы

Уровень: для понимающих архитектуру; мост между «как пользоваться» и «как настраивать и отлаживать». Цель тома: вы объясняете поведение libmdbx через её устройство: B+tree и mmap, MVCC, конвейер коммита, GC, геометрию, вложенные транзакции, файл блокировок и восстановление.

Глава 13. Архитектура хранения: B+tree и mmap

13.1. B+tree: ветви, листья, overflow

Данные libmdbx хранит в B+tree — сбалансированном дереве, где все значения лежат в листьях, а внутренние узлы (branch) содержат только разделители-ключи и указатели на дочерние страницы.

          [branch: M]
        /             \
 [branch: B]          [branch: V]
   /    \                /    \
[a..b] [c..m]        [n..r] [s..z]     <- листья: пары ключ→значение

Свойства:

  • поиск — спуск от корня к листу, O(log N);
  • все листья одного уровня связаны — обход диапазона идёт по соседям;
  • при переполнении листа — split (деление пополам), рекурсивно вверх, включая новый корень;
  • при опустошении ниже порога — rebalance/merge с соседом (порог merge_threshold).

Значения, не помещающиеся в лист (больше примерно половины страницы), уходят на overflow-страницы: контигуальный прогон P_LARGE-страниц; в листе остаётся указатель {pgno, npages}.

13.2. Почему B+tree, а не B-tree или LSM

  • B-tree — данные и в листьях, и в ветвях: поиск может остановиться на любом уровне, но обход требует перехода вверх/вниз. B+tree с данными только в листьях даёт предсказуемый спуск и линейный обход.
  • LSM (LevelDB/RocksDB) оптимизирован на запись (append-only + фоновое сжатие), но чтение страдает от многоуровневых просмотров. B+tree даёт честный O(log N) на чтение и запись без фоновых процессов.

13.3. Страница — единица хранения и I/O

Размер страницы — 256…65536 байт (по умолчанию 4096), выбирается при создании базы и далее неизменен. Типы:

Тип Назначение
branch Внутренний узел: разделители и указатели
leaf Лист: пары ключ→значение
large / overflow Контигуальный прогон больших значений
meta Одна из трёх мета-страниц (снапшот состояния базы)
dupfix / subpage Плотная упаковка мультизначений

Каждая страница несёт метку транзакции (txnid), создавшей её текущую версию — это основа CoW и MVCC.

С базой можно связать пользовательский канарейник (MDBX_canary, 32 байта — четыре uint64_t: x, y, z, v; поле v всегда равно номеру транзакции): mdbx_canary_put(txn, &canary) записывает его в мету, mdbx_canary_get(txn, &canary) читает. Обновлённые значения видны другим процессам только после коммита. Это не данные таблиц, а произвольная метка приложения (например, версия схемы), переживающая открытия базы и доступная даже при монтировании только для чтения.

13.4. mmap: виртуальная память как окно в файл

Файл отображается в адресное пространство целиком. Чтение — разыменование указателя; страницу подтянет ядро (page cache). Отдельного буферного кэша в библиотеке нет.

Следствия:

  • чтение без копирования (вы получаете адрес прямо в mmap);
  • страничный кэш ОС управляет резидентностью;
  • объём базы ограничен адресным пространством (на 32-бит — реально ~1–3 ГБ);
  • при БД ≫ ОЗУ растут накладные на PTE в ядре.

Для области mmap применяется madvise(MADV_NOHUGEPAGE) (отказ от THP) — огромные страницы мешают точной оценке резидентности.

Фрагмент из examples/c++/18-tree-height.c++ — оценка дерева через mdbx_env_stat_ex(): высота, страницы leaf/branch/overflow и число записей; значение больше размера страницы создаёт overflow-страницы:

    {
      auto txn = env.start_write();
      auto table = txn.open_map(nullptr);
      for (int i = 0; i < 5000; ++i)
        txn.insert(table, mdbx::slice("k" + std::to_string(i)), mdbx::slice("v"));
      // Значение больше размера страницы (4096) уходит на overflow-страницы.
      const std::string big(64 * 1024, 'x');
      txn.insert(table, mdbx::slice("big"), mdbx::slice(big));
      txn.commit();
    }

    const auto stat = env.get_stat(); // mdbx_env_stat_ex()
    std::cout << "stat: depth=" << stat.ms_depth << " leaf=" << stat.ms_leaf_pages
              << " branch=" << stat.ms_branch_pages << " overflow=" << stat.ms_overflow_pages
              << " entries=" << stat.ms_entries << "\n";

Полный код: 18-tree-height.c++ · C-версия.

13.5. Инвариант достижимости

Каждая не-мета страница до указателя first_unallocated достижима ровно один раз: либо принадлежит какому-то дереву (обычной, главной или GC-таблице), либо перечислена в записи GC. На этом инварианте строится аудит целостности и инструмент проверки базы (mdbx_chk).

Примеры к главе: examples/c++/18-tree-height.c++ · C-версия.

13.6. Резюме главы 13

  • B+tree: данные в листьях, ветви — разделители; split/merge поддерживают баланс.
  • Большие значения — overflow-прогоны страниц.
  • mmap вместо буферного кэша: чтение без копирования, плата — адресное пространство/PTE.
  • Инвариант достижимости — фундамент целостности.

13.7. Упражнения

  1. Объясните, почему mdbx_get на 64-бит практически не зависит от объёма базы.
  2. Что меняется для читателя, если дерево выросло с высоты 3 до высоты 5?

13.8. Чек-лист главы 13

  • [ ] Могу объяснить, почему все значения лежат в листьях B+tree, а в ветвях — только разделители, и что это даёт для поиска и обхода диапазонов.
  • [ ] Знаю, куда уходит значение, не помещающееся в лист (overflow-прогон), и что остаётся в листе вместо него.
  • [ ] Понимаю, почему libmdbx не заводит собственный буферный кэш, и какие следствия это имеет (чтение без копирования, резидентность управляется ядром, рост PTE при БД ≫ ОЗУ).
  • [ ] Могу назвать ограничение объёма базы адресным пространством и его следствие на 32-битных платформах.
  • [ ] Знаю назначение канарейки (MDBX_canary) и что поле v всегда равно номеру транзакции.
  • [ ] Умею сформулировать инвариант достижимости и объяснить, что на нём построено (аудит целостности, mdbx_chk).

Глава 14. MVCC и снапшоты

14.1. Версионность страниц, снапшот читателя

Каждая страница помечена номером транзакции, создавшей её текущую версию. Читатель при старте фиксирует снапшот — состояние базы на момент начала транзакции. Всё, что он видит после, — непротиворечивая картина этого момента, независимо от последующих коммитов.

14.2. Тройка мета-страниц и двухфазный коммит

В базе всегда три мета-страницы (NUM_METAS = 3). Это позволяет держать два валидных снапшота («свежий» и «steady» — с гарантированно сброшенными на диск данными) и один хвостовой слот для перезаписи.

Обновление меты — двухфазное: сначала инвалидируется половина (запись номера транзакции с обнулением второй), затем заполняются поля и валидируется вторая половина. Читатель видит либо старую цельную мету, либо новую — никогда «полуобновлённую».

14.3. Конечный автомат тройки

Состояние каждой меты кодируется независимо; полная таблица переходов покрывает 216 (6³) комбинаций и исчерпывающе проверяется внутренней валидацией. Это защита от «невозможных» состояний после сбоев.

14.4. Таблица читателей (RLT)

Читатель регистрирует номер снапшота в таблице читателей (в файле блокировок). Слот содержит: номер снапшота, pid/tid владельца, и поля, описывающие, сколько страниц читатель «пинит».

Старейший активный снапшот — детент — вычисляется сканированием RLT (lock-free, с кэшированием). Детент — водораздел переиспользования страниц (глава 16).

14.5. Wait-free чтение и safe64

На операциях чтения читатель не берёт блокировок — он просто ходит по mmap. Единственное «записывающее» действие — регистрация слота при старте транзакции.

64-битные поля (номера транзакций в RLT и мете) читаются через специальный атомарный протокол safe64: значения пишутся «сначала младшее слово, затем старшее», чтение повторяется при обнаружении «обрывка». Это защита от разорванных 64-битных чтений на слабых моделях памяти.

14.6. Писатель: глобальный мьютекс, front txnid, грязный список

В любой момент времени одна write-транзакция (глобальный мьютекс писателя в файле блокировок). При старте писатель получает предварительный номер (front txnid = txnid + 1): новые и CoW-копии страниц метятся им и не видны читателям до коммита. Изменённые страницы скапливаются в грязном списке (DPL).

Фрагмент из examples/c++/19-readers-lag.c++ — читатель удерживает снапшот; коммиты писателя увеличивают его «отставание» (lag), а mdbx_reader_list показывает слоты читателей с txnid и lag:

    // Коммиты после создания снапшота увеличивают lag читателя.
    for (int i = 3; i < 8; ++i) {
      auto txn = env.start_write();
      auto wtable = txn.open_map(nullptr);
      txn.insert(wtable, mdbx::slice("k" + std::to_string(i)), mdbx::slice("v"));
      txn.commit();
    }

    // Перечислить читателей: слот читателя имеет lag > 0.
    struct visitor {
      int operator()(const mdbx::env::reader_info &ri, int) {
        std::cout << "reader slot: pid=" << ri.pid << " tid=" << ri.thread << " txnid=" << ri.transaction_id
                  << " lag=" << ri.transaction_lag << "\n";
        return mdbx::continue_loop;
      }
    } v;
    env.enumerate_readers(v);

Полный код: 19-readers-lag.c++.

Примеры к главе: examples/c++/19-readers-lag.c++.

14.7. Резюме главы 14

  • MVCC: страница помечена txnid; читатель видит свой снапшот.
  • Тройка мет с двухфазным обновлением и конечным автоматом 216 состояний.
  • RLT и детент — основа безопасности переиспользования.
  • Wait-free чтение; safe64 против разорванных чтений.
  • Один писатель; front txnid скрывает незакоммиченное.

14.8. Упражнения

  1. Зачем нужны именно три мета-страницы, а не две?
  2. Что произойдёт, если писатель упадёт в середине двухфазного обновления меты?

14.9. Чек-лист главы 14

  • [ ] Объясняю, почему читатель видит непротиворечивую картину независимо от последующих коммитов (снапшот + метка txnid на страницах).
  • [ ] Знаю, зачем нужны именно три мета-страницы и какие два валидных снапшота они держат.
  • [ ] Могу описать двухфазное обновление меты и объяснить, почему читатель никогда не видит «полуобновлённую» мету.
  • [ ] Понимаю, как детент вычисляется сканированием RLT и почему он — водораздел переиспользования страниц.
  • [ ] Знаю, что чтение wait-free и не берёт блокировок, и зачем нужен протокол safe64.
  • [ ] Могу объяснить, почему незакоммиченные страницы писателя не видны читателям (front txnid, грязный список).

Глава 15. Copy-on-Write и конвейер коммита

15.1. Жизненный цикл страницы при записи

Состояние страницы определяется сравнением её метки mp->txnid с номером транзакции:

Состояние Условие Смысл
frozen txnid < txn->txnid Старая версия, видима читателям; менять нельзя — только копировать
spilled txnid == txn->txnid Уже записана на диск текущим писателем
shadowed txnid > txn->txnid Есть более новая версия; эта — устаревшая
modifiable txnid == front txnid Новая версия текущего писателя; можно менять на месте

Механизм touch (CoW): если страница «заморожена» — выделяем новую (из GC или хвоста файла), копируем содержимое, метим front txnid, кладём в грязный список; старую освобождаем. Родитель, указывавший на старую, тоже становится «изменяемым» — CoW распространяется вверх к корню. Курсоры, ссылавшиеся на старую версию, переводятся на новую.

15.2. Грязный список (DPL)

В пределах одной транзакции страница попадает в грязный список один раз, сколько бы раз её ни меняли — это ключевой фактор сдерживания WAF (write amplification factor — коэффициент усиления записи; подробно в томе IV, глава 21).

15.3. Спилл

Если объём грязных страниц превышает лимит (dp_limit, по умолчанию ≈ 1/42 ОЗУ), включается спилл: часть страниц выгружается на диск заранее. Страницы, на которые ссылаются курсоры, спиллу не подлежат; порядок выбора управляется опциями-знаменателями (минимум/максимум доли).

Нюанс: если спиллнутая страница затем снова изменяется — она будет записана повторно (дополнительная амплификация). Это компромисс «память vs WAF».

15.4. Loose-страницы и refund

  • Loose-страницы — небольшой кэш освобождённых в текущей транзакции грязных страниц (лимит loose_limit, по умолчанию 64) для быстрого переиспользования без обращения к GC.
  • Refund — возврат освобождённых хвостовых страниц в неразмеченное пространство (а не в GC); снижает WAF и даёт онлайн-сжатие.

15.5. Конвейер коммита

  1. Закрыть/проверить курсоры.
  2. GC-обработка: освобождённые страницы складываются в записи GC-дерева.
  3. Refund: хвостовые освобождения возвращаются в неразмеченное пространство.
  4. Спилл: при переполнении грязного списка — выгрузка заранее.
  5. Аудит (в режимах повышенной проверки): сверка сумм страниц.
  6. Двухфазное обновление меты + синхронизация по режиму долговечности.
  7. Снять блокировку писателя, обновить кэш детента, вычистить мёртвых читателей.

Каждая стадия измерима через mdbx_txn_commit_ex() → MDBX_commit_latency (preparation/gc_wallclock/audit/write/sync/ending/whole).

Фрагмент из examples/c++/20-commit-latency.c++ — сбор MDBX_commit_latency по стадиям через commit_get_latency() для серии коммитов и усреднение:

    for (int i = 0; i < commits; ++i) {
      auto txn = env.start_write();
      auto table = txn.open_map(nullptr);
      txn.insert(table, mdbx::slice("k" + std::to_string(i)), mdbx::slice("v"));
      const auto lat = txn.commit_get_latency(); // возвращает MDBX_commit_latency
      prep += lat.preparation;
      gc += lat.gc_wallclock;
      audit += lat.audit;
      write += lat.write;
      sync += lat.sync;
      ending += lat.ending;
      whole += lat.whole;
    }

    std::cout << "avg latency (us): preparation=" << (prep / commits) << " gc=" << (gc / commits)
              << " audit=" << (audit / commits) << " write=" << (write / commits) << " sync=" << (sync / commits)
              << " ending=" << (ending / commits) << " whole=" << (whole / commits) << "\n";

Полный код: 20-commit-latency.c++.

Примеры к главе: examples/c++/20-commit-latency.c++.

15.6. Резюме главы 15

  • CoW: frozen → копия → modifiable; путь к корню переписывается целиком.
  • DPL дедуплицирует страницы внутри транзакции — главный рычаг WAF.
  • Спилл — компромисс память/WAF; loose и refund снижают запись.
  • Конвейер коммита: GC → refund → спилл → аудит → мета → sync → разблокировка.

15.7. Упражнения

  1. Почему изменение одного байта в листе переписывает весь путь до корня?
  2. Как mdbx_txn_commit_ex поможет увидеть, что «застряло» — спилл или sync?

15.8. Чек-лист главы 15

  • [ ] Умею по метке mp->txnid определить состояние страницы (frozen/spilled/shadowed/modifiable) и что с ней можно делать.
  • [ ] Объясняю, почему CoW переписывает путь до корня и как курсоры переводятся на новые версии страниц.
  • [ ] Знаю, что страница попадает в грязный список один раз за транзакцию, и почему это сдерживает WAF.
  • [ ] Могу описать, когда включается спилл (dp_limit ≈ 1/42 ОЗУ), какие страницы он не трогает и чем плох повторный спилл.
  • [ ] Различаю loose-страницы (быстрое переиспользование, loose_limit = 64) и refund (возврат хвостовых страниц в неразмеченное пространство).
  • [ ] Воспроизвожу порядок конвейера коммита и знаю, какие его стадии видны в MDBX_commit_latency.

Глава 16. GC — сборщик мусора внутри БД

16.1. Почему нет free-list

У libmdbx нет классического списка свободных страниц. Освобождённые страницы учитываются персистентно, внутри файла данных, в специальном GC-дереве (отдельная таблица, корень — в мете).

16.2. Формат записи GC

  • Ключ записи — номер транзакции, освободившей страницы.
  • Значение — список номеров страниц (сжато, диапазонами).
  • Одна запись физически ограничена (~1000 номеров при 4 КБ странице).

Формат GC заморожен и не менялся с v11.3 — важная гарантия совместимости.

16.3. Детент: безопасность переиспользования

Страницы из записи GC с ключом T можно переиспользовать только когда T ≤ детент — старейший активный снапшот. Выше детента записи «заморожены» до завершения соответствующего читателя.

Детент вычисляется сканированием RLT (без блокировок, с кэшированием результата).

16.4. FIFO vs LIFO

Политика Механизм Эффект
FIFO (по умолчанию) Берутся страницы из самой старой подходящей записи Список живёт дольше, остывает на диске
LIFO (MDBX_LIFORECLAIM) Самые свежие освобождения первыми Минимально короткий круг циркуляции; страницы ещё «тёплые»; на системах с write-back кэшем — рост производительности записи в разы

Нюанс: MDBX_LIFORECLAIM почти не даёт эффекта с SAFE_NOSYNC/UTTERLY_NOSYNC — там длину цикла определяет частота env_sync(). Для поиска плотных последовательностей используются векторные (SIMD) ядра: SSE2/AVX2/AVX512/NEON.

16.5. BigFoot

Одна запись GC вмещает ~1000 номеров страниц (~4 МБ при 4 КБ). Если транзакция освобождает больше (например, заменяя огромное значение), записи оформляются цепочкой на последовательных txnid — режим BigFoot. Читатели обязаны быть новее всей цепочки. Цена — больше записей, выше GC-дерево.

BigFoot включён по умолчанию на 64-битных сборках (MDBX_ENABLE_BIGFOOT); полностью совместим с форматом базы.

16.6. Рекурсивность обновления GC

GC — тоже CoW-дерево: изменение GC требует выделения страниц, что влияет на список страниц, попадающий в GC. Поэтому перед обновлением формируется оперативный запас свободных страниц: нехватка → нерациональный рост БД, избыток → оверхед.

16.7. rp_augment_limit и gc_time_limit

Поиск плотных последовательностей (для больших значений) может быть дорогим при фрагментации. Два ограничителя стоимости:

  • rp_augment_limit — предел накопления списков при поиске; превышение → дешевле дописать новые страницы в хвост файла;
  • gc_time_limit — тайм-лимит (в 1/65536 секунды) на поиск в течение пишущей транзакции.

Правило: уменьшайте rp_augment_limit только вместе с gc_time_limit; слишком малый rp_augment не лечит рост GC, а усугубляет его ради скорости вставки длинных записей.

Фрагмент из examples/c++/22-gc-limits.c++ — установка и чтение лимитов GC: rp_augment_limit (запас страниц для рекламации) и gc_time_limit (1/65536 секунды на поиск последовательностей):

    env.set_extra_option(opt::rp_augment_limit, 128 * 1024);
    // gc_time_limit задаётся в 1/65536 долях секунды (16.16 fixed point):
    // 2500 ≈ 38 мс на поиск последовательностей страниц в GC внутри транзакции.
    env.set_extra_option(opt::gc_time_limit, 2500);

    // Нагрузка с длинными значениями: заставляет GC работать активнее.
    {
      auto txn = env.start_write();
      auto table = txn.open_map(nullptr);
      for (int i = 0; i < 2000; ++i) {
        const auto key = "k" + std::to_string(i);
        const std::string value(4096 + (i % 7) * 512, 'v');
        txn.insert(table, mdbx::slice(key), mdbx::slice(value));
      }
      txn.commit();
      auto del = env.start_write();
      auto dtable = del.open_map(nullptr);
      for (int i = 0; i < 2000; i += 2)
        del.erase(dtable, mdbx::slice("k" + std::to_string(i)));
      del.commit();
    }

    std::cout << "rp_augment_limit = " << env.extra_option(opt::rp_augment_limit) << "\n";
    std::cout << "gc_time_limit = " << env.extra_option(opt::gc_time_limit) << "\n";

Полный код: 22-gc-limits.c++.

16.8. Ранняя очистка GC (2025) и не-отложенная очистка (devel)

  • Ранняя очистка (2025): переработанные записи GC начинают обрабатываться раньше.
  • Не-отложенная очистка (devel, 0.14.x): переработанные записи GC удаляются сразу после чтения, а не при фиксации; накладные расходы становятся пропорциональны объёму операций. Это же открыло путь к явной дефрагментации без копирования (0.14.2+).

Примеры к главе: examples/c++/21-gc-observe.c++; examples/c++/22-gc-limits.c++.

16.9. Резюме главы 16

  • GC — дерево записей «txnid → список страниц» внутри файла (не free-list).
  • Переиспользование только новее детента.
  • FIFO по умолчанию; MDBX_LIFORECLAIM — LIFO.
  • BigFoot — цепочки для больших освобождений.
  • rp_augment_limit/gc_time_limit — контроль стоимости поиска.

16.10. Упражнения

  1. Объясните, почему долгий читатель «замораживает» переработку, используя понятие детента.
  2. Когда LIFO даст выигрыш, а когда нет?

16.11. Чек-лист главы 16

  • [ ] Могу объяснить, почему в libmdbx нет free-list и где персистентно учитываются освобождённые страницы.
  • [ ] Описываю формат записи GC: ключ — txnid освободителя, значение — список страниц диапазонами; формат заморожен с v11.3.
  • [ ] Объясняю условие переиспользования через детент и что происходит с записями GC выше детента.
  • [ ] Знаю разницу FIFO и LIFO и когда MDBX_LIFORECLAIM даёт выигрыш, а когда нет.
  • [ ] Понимаю механизм BigFoot: цепочки записей на последовательных txnid и требование к читателям быть новее всей цепочки.
  • [ ] Могу объяснить, почему обновление GC рекурсивно (GC — тоже CoW-дерево) и зачем нужен оперативный запас страниц.
  • [ ] Знаю назначение rp_augment_limit и gc_time_limit и правило их совместного уменьшения.

Глава 17. Рост, сжатие и дефрагментация БД

17.1. Почему БД растёт

  • Долгие читатели замораживают детент → GC не переиспользует страницы → писатель берёт новые из хвоста файла. Даже цикл put→del «распухает».
  • MDBX_SAFE_NOSYNC — постоянный квази-долгий читатель (последний steady-коммит).
  • Фрагментация и нехватка контигуальных последовательностей для больших значений.
  • Забытые читатели (крэш потока, неправильный TLS).

17.2. Геометрия: growth_step, upper, shrink_threshold

Файл растёт автоматически, кратными growth_step, до upper. Усечение возможно только до последней используемой страницы; одна занятая страница у конца может блокировать сжатие неопределённо долго. Сжатие требует гистерезиса (шаг сжатия > шага роста), иначе файл «дышит».

17.3. MDBX_MAP_FULL и разрешающие механизмы

Когда GC пуст/заморожен и файл упёрся в upper, срабатывают, по возможности: новый steady-point (сдвиг детента) → HSR-колбэк (HSR — Handle-Slow-Readers, механизм вытеснения застрявших читателей; подробно в томе V, гл. 29) → выселение припаркованных читателей → и лишь затем MDBX_MAP_FULL.

Фрагмент из examples/c++/23-map-full.c++ — воспроизведение MDBX_MAP_FULL (в примере жёсткая геометрия ограничивает файл 512 КБ) и разрешение через увеличение size_upper:

    size_t inserted = 0;
    try {
      auto txn = env.start_write();
      auto table = txn.open_map(nullptr);
      for (;;) {
        const auto key = "k" + std::to_string(inserted);
        const std::string value(1024, 'x');
        txn.insert(table, mdbx::slice(key), mdbx::slice(value));
        ++inserted;
      }
    } catch (const mdbx::db_full &ex) {
      std::cout << "MDBX_MAP_FULL after " << inserted << " inserts\n";
    }

    // Увеличиваем верхнюю границу — и продолжаем с того же места.
    mdbx::env::geometry bigger;
    bigger.size_upper = 8 * 1024 * 1024;
    try {
      env.set_geometry(bigger);
    } catch (const mdbx::db_unable_extend &) {
      // На 32-битной Windows адресный диапазон сразу за отображением может
      // оказаться занят: переоткрываем ту же БД с увеличенной геометрией.
      mdbx::env::geometry reopened = geo;
      reopened.size_upper = bigger.size_upper;
      env.close();
      env = mdbx::env_managed(path,
          mdbx::env_managed::create_parameters().set_geometry(reopened),
          mdbx::env::operate_parameters());
    }

Увеличение upper на живой БД требует переотображения: на большинстве платформ оно выполняется на месте, но на 32-битной Windows рядом с текущим отображением может не оказаться свободного диапазона адресов — тогда возникает MDBX_UNABLE_EXTEND_MAPSIZE, а переносимый путь — закрыть и переоткрыть БД с увеличенной геометрией (новое отображение создаётся сразу с нужным upper).

Полный код: 23-map-full.c++.

17.4. Авто-компактификация (implicit shrink)

При каждом коммите освобождённые хвостовые страницы возвращаются в неразмеченное пространство (refund). Когда свободный хвост превышает shrink_threshold (+ небольшой запас), коммит дополнительно: сбрасывает «лишний» диапазон через madvise(MADV_DONTNEED/REMOVE) и усекает файл.

Ограничения: не работает, пока долгие читатели удерживают хвост или файл используют несколько процессов; при SAFE_NOSYNC ограничено частотой steady-point'ов.

17.5. Явная дефрагментация

mdbx_env_defrag() / утилита mdbx_defrag (0.14.2+) — аккуратная перестановка страниц к началу файла циклами; каждый цикл — отдельная коммитнутая транзакция. Параметры: defrag_atleast/ defrag_enough (минимальное/достаточное сокращение), time_atleast/time_limit (1/65536 с), acceptable_backlash, preferred_batch. Код результата — MDBX_defrag_enough_threshold.

Гарантированное уменьшение файла — также mdbx_copy -c (компактифицированная копия) или dump+load (-a).

17.6. Оценка ёмкости

Деление размера файла на размер элемента переоценивает реальную ёмкость: страничная гранулярность, путь к корню, GC и гистерезис добавляют накладные. Оценивайте по худшему случаю заморозки переиспользования.

Примеры к главе: examples/c++/23-map-full.c++; examples/c++/24-defrag.c++.

17.7. Резюме главы 17

  • Рост = не переиспользуемые страницы (читатели/SAFE_NOSYNC/фрагментация).
  • upper — жёсткий предел; MAP_FULL разрешается steady/HSR/выселением.
  • Implicit shrink — бесплатная компактификация в составе коммитов.
  • Явная дефрагментация циклами; гарантированное сжатие — copy -c / dump+load.

17.8. Упражнения

  1. Почему «в базе 10 ГБ, значит 10 ГБ данных» — ошибка оценки?
  2. Опишите сценарий, где авто-компактификация не сработает.

17.9. Чек-лист главы 17

  • [ ] Называю причины роста БД: долгие читатели, MDBX_SAFE_NOSYNC, фрагментация, забытые читатели.
  • [ ] Понимаю, почему усечение возможно только до последней используемой страницы и зачем нужен гистерезис шага сжатия.
  • [ ] Воспроизвожу цепочку разрешения MDBX_MAP_FULL: steady-point → HSR-колбэк → выселение припаркованных читателей → ошибка.
  • [ ] Знаю ограничения авто-компактификации (implicit shrink) и когда она не сработает.
  • [ ] Могу описать явную дефрагментацию циклами и гарантированные пути уменьшения файла (mdbx_copy -c, dump+load).
  • [ ] Объясняю, почему деление размера файла на размер элемента переоценивает реальную ёмкость.

Глава 18. Вложенные транзакции

18.1. Зачем нужны

Вложенная транзакция — дочерняя write-транзакция внутри родительской, позволяющая группировать изменения с возможностью частичного отката.

18.2. Реализация

Дочерняя транзакция работает на том же номере транзакции и front txnid. Она наследует у родителя: пространство страниц и грязный список (с тенью родительского), retired-списки (списки уже освобождённых, но ещё удерживаемых от переиспользования страниц — см. 19.4), буферы GC, дескрипторы таблиц и курсоры (через механизм «спаренных» курсоров).

18.3. Commit (join) vs Abort (undo)

  • Коммит: грязные страницы дочерней сливаются в родительский список; счётчики GC переносятся. Если дочерняя «чистая» — быстрый путь без слияния.
  • Abort: все изменения отбрасываются; утилизированные страницы «рас-утилизируются»; хендлы и курсоры восстанавливаются.

Фрагмент из examples/c++/25-nested-txn.c++ — вложенная транзакция: start_nested() + abort() откатывает её изменения (undo); симметричный commit() вливает их в родителя (join):

    // Вложенная транзакция с откатом (undo).
    {
      auto nested = txn.start_nested();
      auto ntable = nested.open_map(nullptr);
      nested.insert(ntable, mdbx::slice("k2"), mdbx::slice("v2"));
      nested.abort(); // откат вложенной
    }
    std::cout << "parent sees k1 after nested abort: " << txn.get(table, mdbx::slice("k1")).as_string() << "\n";
    try {
      (void)txn.get(table, mdbx::slice("k2"));
      std::cerr << "FAIL: k2 survived nested abort\n";
      return EXIT_FAILURE;
    } catch (const mdbx::not_found &) {
      std::cout << "k2 rolled back by nested abort: absent\n";
    }

Полный код: 25-nested-txn.c++.

18.4. Судьба таблиц

  • Таблица, созданная во вложенной: при commit остаётся, при abort исчезает.
  • Таблица, удалённая во вложенной: при commit удаляется, при abort «оживает».

18.5. Анти-паттерн: вложенная транзакция в каждой функции

Вызывать mdbx_txn_begin(parent, ...) в каждой маленькой функции — анти-паттерн: теряется смысл группировки, растут накладные. Вкладывайте осознанно, по границам логических операций.

18.6. Workaround нехватки места

Вложенные транзакции — известный workaround для сценариев нехватки места (можно частично откатиться, не теряя предыдущие изменения).

Нюанс: вложенные транзакции не сочетаются с MDBX_WRITEMAP.

Примеры к главе: examples/c++/25-nested-txn.c++.

18.7. Резюме главы 18

  • Вложенная транзакция = дочерняя write-транзакция с частичным откатом.
  • Commit — слияние в родителя; Abort — полный откат.
  • Судьба созданных/удалённых таблиц следует правилам CoW.
  • Не вкладывайте «на каждую функцию»; не сочетайте с WRITEMAP.

18.8. Упражнения

  1. Напишите пример «группа обновлений с откатом последнего шага» через вложенную транзакцию.
  2. Проверьте судьбу таблицы, созданной и удалённой во вложенной транзакции при abort.

18.9. Чек-лист главы 18

  • [ ] Объясняю, что дочерняя транзакция работает на том же номере транзакции, и что она наследует у родителя.
  • [ ] Различаю commit (join): слияние грязных страниц в родителя, и abort (undo): полный откат и «рас-утилизация» страниц.
  • [ ] Знаю судьбу таблиц, созданных и удалённых во вложенной транзакции, при commit и при abort.
  • [ ] Умею показать частичный откат через start_nested() + abort().
  • [ ] Могу обосновать, почему вложенная транзакция «в каждой функции» — анти-паттерн.
  • [ ] Знаю, что вложенные транзакции — workaround нехватки места, и что они не сочетаются с MDBX_WRITEMAP.

Глава 19. Файл блокировок и межпроцессная синхронизация

19.1. Зачем отдельный файл

Рядом с файлом данных живёт файл блокировок (.lck): глобальный мьютекс писателя, таблица читателей (RLT), статистика, кэши старейшего снапшота. Он нужен для координации между процессами.

Фрагмент из examples/c++/26-two-processes.c++ — межпроцессный доступ: процесс-писатель коммитит данные, процесс-читатель (потомок через fork()) открывает ту же БД и читает их:

    // Писатель: родительский процесс коммитит данные и закрывает окружение.
    {
      auto env = example::env_open(path);
      auto txn = env.start_write();
      auto table = txn.open_map(nullptr);
      txn.insert(table, mdbx::slice("k"), mdbx::slice("v1"));
      txn.commit();
      std::cout << "parent wrote: k=v1" << std::endl;
    }

    const pid_t pid = fork();
    if (pid < 0) {
      std::cerr << "fork failed\n";
      return EXIT_FAILURE;
    }

    if (pid == 0) {
      // Читатель: потомок открывает ту же БД и читает данные.
      auto env = example::env_open(path);
      auto txn = env.start_read();
      auto table = txn.open_map(nullptr);
      std::cout << "child reads: " << txn.get(table, mdbx::slice("k")).as_string() << std::endl;
      txn.abort();
      _exit(EXIT_SUCCESS);
    }

Полный код: 26-two-processes.c++.

19.2. Реализации блокировок

Опция сборки MDBX_LOCKING:

Flavour Примитивы Сигнатура LCK
POSIX2008 Надёжные мьютексы (Linux по умолчанию) 0x8017
POSIX2001 Общие мьютексы 0x8017
SYSV Семафоры (macOS по умолчанию) 0xF18D
WIN32FILES Windows (LockFileEx) 0xF10C
POSIX1988 (legacy) 0xFC29

Нюанс: почему у POSIX2001 и POSIX2008 одна сигнатура — это не опечатка. Оба флавора хранят в LCK межпроцессный примитив одного и того же типа — pthread_mutex_t, поэтому их on-disk формат совпадает байт-в-байт, и сигнатура у них общая. Различие — только в используемых возможностях API: надёжные (robust) мьютексы появились в POSIX.1-2008, режим 2001 работает с обычными process-shared мьютексами. Следствие: базу, открытую в одном из этих двух режимов, можно продолжить в другом — а с SYSV, WIN32FILES и POSIX1988 нельзя (у них другие сигнатуры, и LCK такого формата будет отвергнут).

При этом фактическая проверка совместимости при открытии использует не сырую сигнатуру, а производный хеш MDBX_LOCK_FORMAT — он смешивает сигнатуру флавора с sizeof(reader_slot_t) и офсетами ключевых полей структуры lck_t, так что приведённые константы — лишь «база», уникальная для формата примитива, а полный паспорт учитывает и раскладку остальных полей.

Формат LCK версионирован отдельно от формата данных: изменение структуры ломает только совместный доступ к уже открытой базе, не сам файл данных.

19.3. Почему LockFileEx на Windows, а не именованные мьютексы

Файловые блокировки (LockFileEx) выбраны осознанно: работают на сетевых дисках и защищают от некомпетентных действий. Цена — в наивных бенчмарках с множеством мелких транзакций libmdbx может отставать от LMDB (захват/освобождение файловой блокировки — сотни микросекунд).

19.4. Слот читателя (RLT)

txnid (atomic)          номер снапшота (INVALID_TXNID = свободен)
tid                     владелец; PARKED = UINT64_MAX, OUSTED = UINT64_MAX-1
pid                     процесс-владелец
snapshot_pages_used     first_unallocated на момент снапшота
snapshot_pages_retired  сколько страниц удерживает от переиспользования

Живость слотов проверяется средствами ОС (защита от повторного использования pid/tid). stale-слоты не сканируются поштучно — таблица целиком реинициализируется, когда LCK открывает единственный процесс.

19.5. Восстановление блокировок после сбоя процесса

После краха процесса ОС освобождает его блокировки; мёртвые слоты читателей очищаются механизмами живости и mdbx_reader_check().

19.6. Режим без файла блокировок

Возможен режим «один процесс, эксклюзивно» без .lck (опция сборки) — когда межпроцессный доступ не нужен.

Примеры к главе: examples/c++/26-two-processes.c++.

19.7. Резюме главы 19

  • LCK: мьютекс писателя + RLT + статистика; отдельно версионируется.
  • Реализации: POSIX/SysV/WIN32FILES; сигнатуры flavour'ов.
  • LockFileEx — выбор ради сетевых дисков; медленнее для мелких транзакций.
  • Слот RLT: txnid/tid/pid + пининг-поля; живость через ОС.
  • Возможен режим без LCK (один процесс).

19.8. Упражнения

  1. Почему удалять .lck при открытой базе — ошибка?
  2. Чем mdbx_reader_check отличается от «автоматической» очистки?

19.9. Чек-лист главы 19

  • [ ] Могу перечислить, что живёт в файле блокировок, и зачем он нужен при межпроцессном доступе.
  • [ ] Знаю, что формат LCK версионируется отдельно от формата данных, и что это значит для совместимости.
  • [ ] Объясняю, почему на Windows выбран LockFileEx, и чем за это платим в бенчмарках с мелкими транзакциями.
  • [ ] Описываю слот читателя RLT и поля, фиксирующие, сколько страниц читатель удерживает от переиспользования.
  • [ ] Понимаю, как проверяется живость слотов средствами ОС и что очищает мёртвые слоты после краха процесса (mdbx_reader_check()).
  • [ ] Знаю, когда возможен режим без файла блокировок (один процесс, эксклюзивно).

Глава 20. Долговечность и восстановление

20.1. Двухфазное обновление меты: weak vs steady

  • weak — данные в файле, но не гарантированно сброшены на постоянный носитель;
  • steady — данные сброшены на диск; снапшот переживает сбой системы.

20.2. Восстановление без WAL

WAL отсутствует намеренно. После сбоя при открытии выбирается последняя цельная и валидная мета (согласованная тройка, совпадение половин txnid, контрольная сумма). «Полузаписанные» транзакции, не успевшие опубликовать мету, просто не существуют.

mdbx_txn_checkpoint(txn, weakening_durability, &latency) — вариант коммита: фиксирует транзакцию и возвращает латенси по стадиям (MDBX_commit_latency), позволяя ослабить долговечность через weakening_durability. В заголовке помечено как «может измениться в будущих релизах» — используйте для диагностики, а не как стабильный API. Принудительное продвижение steady-точки выполняется mdbx_env_sync_ex(env, force=true, ...) (Том II, глава 10), а не checkpoint'ом.

20.3. Open for recovery

mdbx_env_open_for_recovery() открывает базу с выбором целевой мета-страницы (target_meta) под эксклюзивной блокировкой, чтобы разрешить «застрявшую» тройку. Recovery-проверки с 0.12.7+ не изменяют базу. Код MDBX_WANNA_RECOVERY возвращается при read-only открытии базы, требующей восстановления.

Внимание: в заголовке функция помечена как внутренний API утилиты mdbx_chk, «subject to change at any time» — в прикладном коде она не рекомендуется; штатный путь — read-write открытие или mdbx_chk.

Фрагмент из examples/c++/27-recovery.c++ — падение писателя (_exit без commit/abort) откатывается при повторном открытии (steady), а open_for_recovery() открывает конкретную meta-страницу:

    // Повторное открытие: незакоммиченные изменения откатились.
    {
      auto env = example::env_open(path);
      auto txn = env.start_read();
      auto table = txn.open_map(nullptr);
      const std::string value(txn.get(table, mdbx::slice("key")).as_string());
      std::cout << "crashed writer changes rolled back: key=" << value << ", newkey ";
      try {
        (void)txn.get(table, mdbx::slice("newkey"));
        std::cout << "present\n";
        return EXIT_FAILURE;
      } catch (const mdbx::not_found &) {
        std::cout << "absent\n";
      }
      txn.abort();
    }

    // Режим восстановления: открыть конкретную meta-страницу (0..2).
    {
      auto recovery = mdbx::env_managed::open_for_recovery(path.c_str(), 0 /* target_meta */, true);
      std::cout << "open_for_recovery: ok\n";
    }

Полный код: 27-recovery.c++.

20.4. boot_id: семантика и поведение в LXC

boot_id — идентификатор загрузки ОС, учитываемый при откате слабых мет. В LXC boot_id может отсутствовать/быть общим для контейнеров — контроль отката слабых мет учитывает это. Это важно при сбоях внутри контейнеров.

20.5. Некогерентность unified page cache

Известная проблема issue #269: некогерентность объединённого page cache между процессами. Защита — MDBX_FORCE_CHECK_MMAP_COHERENCY (опция сборки, дефолт 0); внесена в сериях 0.11.5–0.11.6; счётчик срабатываний виден в диагностике.

20.6. mdbx_chk: проверка целостности

mdbx_chk — глубокая валидация: меты/тройка, деревья, упорядоченность, инвариант достижимости, GC. Режимы: -w (read-write, откат к steady), -d (постраничный обход — без него нельзя найти lost/double-used страницы), -i (игнор ложных ошибок порядка при кастомных компараторах), -0/-1/-2 (конкретная мета), -vvvvv (гистограммы). Exit-код: 0 = чисто.

20.7. Что переживёт сбой питания — по режимам

Режим После сбоя
MDBX_SYNC_DURABLE Все закоммиченные данные на месте
MDBX_NOMETASYNC Потеря последних коммитов (мета отложенно)
MDBX_SAFE_NOSYNC Откат к последнему steady
MDBX_UTTERLY_NOSYNC Никаких гарантий; возможна порча

Примеры к главе: examples/c++/27-recovery.c++.

20.8. Резюме главы 20

  • Двухфазная мета: weak/steady; восстановление — выбор последней цельной меты.
  • Open-for-recovery с target_meta; с 0.12.7 проверки не изменяют базу.
  • boot_id важен в LXC; page-cache несоогласованность — #269 + FORCE_CHECK.
  • mdbx_chk — основной инструмент проверки; режимы см. выше.

20.9. Упражнения

  1. Опишите, что произойдёт с базой после kill -9 посреди коммита, в режиме DURABLE.
  2. Зачем mdbx_chk -d нужен для поиска lost-unused страниц?

20.10. Чек-лист главы 20

  • [ ] Различаю weak и steady снапшоты и знаю, какой из них переживает сбой системы.
  • [ ] Объясняю, как работает восстановление без WAL: выбор последней цельной и валидной меты; «полузаписанные» транзакции просто не существуют.
  • [ ] Знаю назначение mdbx_env_open_for_recovery() с target_meta и почему в прикладном коде она не рекомендуется.
  • [ ] Понимаю роль boot_id при откате слабых мет и его особенности в LXC.
  • [ ] Знаю о некогерентности unified page cache (#269) и защите MDBX_FORCE_CHECK_MMAP_COHERENCY.
  • [ ] Умею выбрать режимы mdbx_chk (-w, -d, -i, -0/-1/-2) под задачу и понимаю, зачем нужен -d.
  • [ ] Могу для каждого режима долговечности сказать, что переживёт сбой питания.

Итог тома

Вы понимаете внутреннее устройство libmdbx: от страницы и B+tree до меты, GC и восстановления. Теперь вы можете объяснять любое наблюдаемое поведение через архитектуру.

Что дальше: Том IV — производительность и оптимизация: WAF, выбор конфигурации под сценарий, микрооптимизации, get-cached, массовые операции, бенчмарки.