diff options
| author | George Hazan <ghazan@miranda.im> | 2018-08-25 12:49:45 +0300 |
|---|---|---|
| committer | George Hazan <ghazan@miranda.im> | 2018-08-25 12:49:45 +0300 |
| commit | c2216a4278bbbc3fb01e6bfb25ddaf8ad48c4e1e (patch) | |
| tree | 7415b5b5a140cdf291a259b0b5da6cc61cc60d70 /libs/libmdbx/src | |
| parent | 94fb75230352ce8729e9b0ace42e81c6d494a6fd (diff) | |
merge with recent libmdbx
Diffstat (limited to 'libs/libmdbx/src')
| -rw-r--r-- | libs/libmdbx/src/README-RU.md | 708 | ||||
| -rw-r--r-- | libs/libmdbx/src/README.md | 714 | ||||
| -rw-r--r-- | libs/libmdbx/src/TODO.md | 89 | ||||
| -rw-r--r-- | libs/libmdbx/src/mdbx.h | 8 | ||||
| -rw-r--r-- | libs/libmdbx/src/packages/rpm/CMakeLists.txt (renamed from libs/libmdbx/src/CMakeLists.txt) | 0 | ||||
| -rw-r--r-- | libs/libmdbx/src/packages/rpm/build.sh (renamed from libs/libmdbx/src/build.sh) | 0 | ||||
| -rw-r--r-- | libs/libmdbx/src/packages/rpm/package.sh (renamed from libs/libmdbx/src/package.sh) | 0 | ||||
| -rw-r--r-- | libs/libmdbx/src/src/bits.h | 10 | ||||
| -rw-r--r-- | libs/libmdbx/src/src/mdbx.c | 477 | ||||
| -rw-r--r-- | libs/libmdbx/src/src/tools/mdbx_chk.c | 12 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/config.cc | 99 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/config.h | 26 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/gc.sh | 35 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/hill.cc | 2 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/keygen.cc | 8 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/log.h | 9 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/main.cc | 65 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/osal-windows.cc | 8 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/test.cc | 5 | ||||
| -rw-r--r-- | libs/libmdbx/src/test/utils.cc | 2 |
20 files changed, 1284 insertions, 993 deletions
diff --git a/libs/libmdbx/src/README-RU.md b/libs/libmdbx/src/README-RU.md index f4ae5e8f14..5dd062c1a6 100644 --- a/libs/libmdbx/src/README-RU.md +++ b/libs/libmdbx/src/README-RU.md @@ -12,31 +12,31 @@ and [by Yandex](https://translate.yandex.ru/translate?url=https%3A%2F%2Fgithub.c ### Project Status - -**Сейчас MDBX _активно перерабатывается_** и к середине 2018 -ожидается большое изменение как API, так и формата базы данных. -К сожалению, обновление приведет к потере совместимости с -предыдущими версиями. - -Цель этой революции - обеспечение более четкого надежного -API и добавление новых функции, а также наделение базы данных -новыми свойствами. - -В настоящее время MDBX предназначена для Linux, а также -поддерживает Windows (начиная с Windows Server 2008) в качестве -дополнительной платформы. Поддержка других ОС может быть -обеспечена на коммерческой основе. Однако такие -усовершенствования (т. е. pull-requests) могут быть приняты в -мейнстрим только в том случае, если будет доступен -соответствующий публичный и бесплатный сервис непрерывной -интеграции (aka Continuous Integration). +**Сейчас MDBX _активно перерабатывается_** и к середине 2018 ожидается +большое изменение как API, так и формата базы данных. К сожалению, +обновление приведет к потере совместимости с предыдущими версиями. + +Цель этой революции - обеспечение более четкого надежного API и +добавление новых функции, а также наделение базы данных новыми +свойствами. + +В настоящее время MDBX предназначена для Linux, а также поддерживает +Windows (начиная с Windows Server 2008) в качестве дополнительной +платформы. Поддержка других ОС может быть обеспечена на коммерческой +основе. Однако такие усовершенствования (т. е. pull-requests) могут быть +приняты в мейнстрим только в том случае, если будет доступен +соответствующий публичный и бесплатный сервис непрерывной интеграции +(aka Continuous Integration). ## Содержание - - [Обзор](#Обзор) - [Сравнение с другими СУБД](#Сравнение-с-другими-СУБД) - [История & Acknowledgments](#История) - [Основные свойства](#Основные-свойства) +- [Доработки и усовершенствования относительно LMDB](#Доработки-и-усовершенствования-относительно-lmdb) +- [Недостатки и Компромиссы](#Недостатки-и-Компромиссы) + - [Проблема долгих чтений](#Проблема-долгих-чтений) + - [Сохранность данных в режиме асинхронной фиксации](#Сохранность-данных-в-режиме-асинхронной-фиксации) - [Сравнение производительности](#Сравнение-производительности) - [Интегральная производительность](#Интегральная-производительность) - [Масштабируемость чтения](#Масштабируемость-чтения) @@ -44,21 +44,18 @@ API и добавление новых функции, а также надел - [Отложенная фиксация](#Отложенная-фиксация) - [Асинхронная фиксация](#Асинхронная-фиксация) - [Потребление ресурсов](#Потребление-ресурсов) -- [Недостатки и Компромиссы](#Недостатки-и-Компромиссы) - - [Проблема долгих чтений](#Проблема-долгих-чтений) - - [Сохранность данных в режиме асинхронной фиксации](#Сохранность-данных-в-режиме-асинхронной-фиксации) -- [Доработки и усовершенствования относительно LMDB](#Доработки-и-усовершенствования-относительно-lmdb) ## Обзор - _libmdbx_ - это встраиваемый key-value движок хранения со специфическим набором свойств и возможностей, ориентированный на создание уникальных -легковесных решений с предельной производительностью под Linux и Windows. +легковесных решений с предельной производительностью под Linux и +Windows. _libmdbx_ позволяет множеству процессов совместно читать и обновлять -несколько key-value таблиц с соблюдением [ACID](https://ru.wikipedia.org/wiki/ACID), -при минимальных накладных расходах и амортизационной стоимости любых операций Olog(N). +несколько key-value таблиц с соблюдением +[ACID](https://ru.wikipedia.org/wiki/ACID), при минимальных накладных +расходах и амортизационной стоимости любых операций Olog(N). _libmdbx_ обеспечивает [serializability](https://en.wikipedia.org/wiki/Serializability) @@ -72,20 +69,26 @@ _libmdbx_ позволяет выполнять операции чтения с параллельно на каждом ядре CPU, без использования атомарных операций и/или примитивов синхронизации. -_libmdbx_ не использует [LSM](https://en.wikipedia.org/wiki/Log-structured_merge-tree), а основан на [B+Tree](https://en.wikipedia.org/wiki/B%2B_tree) с [отображением](https://en.wikipedia.org/wiki/Memory-mapped_file) всех данных в память, -при этом текущая версия не использует [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging). -Это предопределяет многие свойства, в том числе удачные и противопоказанные сценарии использования. +_libmdbx_ не использует +[LSM](https://en.wikipedia.org/wiki/Log-structured_merge-tree), а +основан на [B+Tree](https://en.wikipedia.org/wiki/B%2B_tree) с +[отображением](https://en.wikipedia.org/wiki/Memory-mapped_file) всех +данных в память, при этом текущая версия не использует +[WAL](https://en.wikipedia.org/wiki/Write-ahead_logging). Это +предопределяет многие свойства, в том числе удачные и противопоказанные +сценарии использования. -### Сравнение с другими СУБД -Ввиду того, что в _libmdbx_ сейчас происходит революция, я посчитал лучшим решением -ограничится здесь ссылкой на [главу Comparison with other databases](https://github.com/coreos/bbolt#comparison-with-other-databases) в описании _BoltDB_. +### Сравнение с другими СУБД +Ввиду того, что в _libmdbx_ сейчас происходит революция, я посчитал +лучшим решением ограничится здесь ссылкой на [главу Comparison with +other databases](https://github.com/coreos/bbolt#comparison-with-other-databases) +в описании _BoltDB_. ### История - -_libmdbx_ является результатом переработки и развития "Lightning Memory-Mapped Database", -известной под аббревиатурой +_libmdbx_ является результатом переработки и развития "Lightning +Memory-Mapped Database", известной под аббревиатурой [LMDB](https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database). Изначально доработка производилась в составе проекта [ReOpenLDAP](https://github.com/leo-yuriev/ReOpenLDAP). Примерно за год @@ -102,226 +105,223 @@ Technologies](https://www.ptsecurity.ru). #### Acknowledgments +Howard Chu (Symas Corporation) - the author of LMDB, from which +originated the MDBX in 2015. -Howard Chu (Symas Corporation) - the author of LMDB, -from which originated the MDBX in 2015. - -Martin Hedenfalk <martin@bzero.se> - the author of `btree.c` code, -which was used for begin development of LMDB. +Martin Hedenfalk <martin@bzero.se> - the author of `btree.c` code, which +was used for begin development of LMDB. Основные свойства ================= -_libmdbx_ наследует все ключевые возможности и особенности -своего прародителя [LMDB](https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database), -но с устранением ряда описываемых далее проблем и архитектурных недочетов. - -1. Данные хранятся в упорядоченном отображении (ordered map), ключи всегда - отсортированы, поддерживается выборка диапазонов (range lookups). - -2. Данные отображается в память каждого работающего с БД процесса. - К данным и ключам обеспечивается прямой доступ в памяти без необходимости их - копирования. - -3. Транзакции согласно - [ACID](https://ru.wikipedia.org/wiki/ACID), посредством - [MVCC](https://ru.wikipedia.org/wiki/MVCC) и - [COW](https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BF%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%B8_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B8). - Изменения строго последовательны и не блокируются чтением, - конфликты между транзакциями невозможны. - При этом гарантируется чтение только зафиксированных данных, см [relaxing serializability](https://en.wikipedia.org/wiki/Serializability). - -4. Чтение и поиск [без блокировок](https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B1%D0%BB%D0%BE%D0%BA%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B0%D1%8F_%D1%81%D0%B8%D0%BD%D1%85%D1%80%D0%BE%D0%BD%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F), - без [атомарных операций](https://ru.wikipedia.org/wiki/%D0%90%D1%82%D0%BE%D0%BC%D0%B0%D1%80%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D1%8F). - Читатели не блокируются операциями записи и не конкурируют - между собой, чтение масштабируется линейно по ядрам CPU. +_libmdbx_ наследует все ключевые возможности и особенности своего +прародителя +[LMDB](https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database), +но с устранением ряда описываемых далее проблем и архитектурных +недочетов. + +1. Данные хранятся в упорядоченном отображении (ordered map), ключи +всегда отсортированы, поддерживается выборка диапазонов (range lookups). + +2. Данные отображается в память каждого работающего с БД процесса. К +данным и ключам обеспечивается прямой доступ в памяти без необходимости +их копирования. + +3. Транзакции согласно [ACID](https://ru.wikipedia.org/wiki/ACID), +посредством [MVCC](https://ru.wikipedia.org/wiki/MVCC) и +[COW](https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BF%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BF%D1%80%D0%B8_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D0%B8). +Изменения строго последовательны и не блокируются чтением, конфликты +между транзакциями невозможны. При этом гарантируется чтение только +зафиксированных данных, см [relaxing +serializability](https://en.wikipedia.org/wiki/Serializability). + +4. Чтение и поиск [без +блокировок](https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B1%D0%BB%D0%BE%D0%BA%D0%B8%D1%80%D1%83%D1%8E%D1%89%D0%B0%D1%8F_%D1%81%D0%B8%D0%BD%D1%85%D1%80%D0%BE%D0%BD%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F), +без [атомарных +операций](https://ru.wikipedia.org/wiki/%D0%90%D1%82%D0%BE%D0%BC%D0%B0%D1%80%D0%BD%D0%B0%D1%8F_%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D1%8F). +Читатели не блокируются операциями записи и не конкурируют между собой, +чтение масштабируется линейно по ядрам CPU. > Для точности следует отметить, что "подключение к БД" (старт первой > читающей транзакции в потоке) и "отключение от БД" (закрытие БД или > завершение потока) требуют краткосрочного захвата блокировки для > регистрации/дерегистрации текущего потока в "таблице читателей". -5. Эффективное хранение дубликатов (ключей с несколькими - значениями), без дублирования ключей, с сортировкой значений, в - том числе целочисленных (для вторичных индексов). +5. Эффективное хранение дубликатов (ключей с несколькими значениями), +без дублирования ключей, с сортировкой значений, в том числе +целочисленных (для вторичных индексов). -6. Эффективная поддержка коротких ключей фиксированной длины, в том числе целочисленных. +6. Эффективная поддержка коротких ключей фиксированной длины, в том +числе целочисленных. 7. Амортизационная стоимость любой операции Olog(N), - [WAF](https://en.wikipedia.org/wiki/Write_amplification) (Write - Amplification Factor) и RAF (Read Amplification Factor) также Olog(N). +[WAF](https://en.wikipedia.org/wiki/Write_amplification) (Write +Amplification Factor) и RAF (Read Amplification Factor) также Olog(N). -8. Нет [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) и журнала - транзакций, после сбоев не требуется восстановление. Не требуется компактификация - или какое-либо периодическое обслуживание. Поддерживается резервное копирование - "по горячему", на работающей БД без приостановки изменения данных. +8. Нет [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) и +журнала транзакций, после сбоев не требуется восстановление. Не +требуется компактификация или какое-либо периодическое обслуживание. +Поддерживается резервное копирование "по горячему", на работающей БД без +приостановки изменения данных. -9. Отсутствует какое-либо внутреннее управление памятью или кэшированием. Всё - необходимое штатно выполняет ядро ОС! +9. Отсутствует какое-либо внутреннее управление памятью или +кэшированием. Всё необходимое штатно выполняет ядро ОС. -Сравнение производительности -============================ - -Все представленные ниже данные получены многократным прогоном тестов на -ноутбуке Lenovo Carbon-2, i7-4600U 2.1 ГГц, 8 Гб ОЗУ, с SSD-диском -SAMSUNG MZNTD512HAGL-000L1 (DXT23L0Q) 512 Гб. - -Исходный код бенчмарка [_IOArena_](https://github.com/pmwkaa/ioarena) и -сценарии тестирования [доступны на -github](https://github.com/pmwkaa/ioarena/tree/HL%2B%2B2015). - --------------------------------------------------------------------------------- - -### Интегральная производительность - -Показана соотнесенная сумма ключевых показателей производительности в трёх -бенчмарках: - - - Чтение/Поиск на машине с 4-мя процессорами; - - - Транзакции с [CRUD](https://ru.wikipedia.org/wiki/CRUD)-операциями - (вставка, чтение, обновление, удаление) в режиме **синхронной фиксации** - данных (fdatasync при завершении каждой транзакции или аналог); - - - Транзакции с [CRUD](https://ru.wikipedia.org/wiki/CRUD)-операциями - (вставка, чтение, обновление, удаление) в режиме **отложенной фиксации** - данных (отложенная запись посредством файловой систем или аналог); - -*Бенчмарк в режиме асинхронной записи не включен по двум причинам:* +Доработки и усовершенствования относительно LMDB +================================================ - 1. Такое сравнение не совсем правомочно, его следует делать с движками - ориентированными на хранение данных в памяти ([Tarantool](https://tarantool.io/), [Redis](https://redis.io/)). +1. Утилита `mdbx_chk` для проверки целостности структуры БД. - 2. Превосходство libmdbx становится еще более подавляющим, что мешает - восприятию информации. +2. Автоматическое динамическое управление размером БД согласно +параметрам задаваемым функцией `mdbx_env_set_geometry()`, включая шаг +приращения и порог уменьшения размера БД, а также выбор размера +страницы. Соответственно, это позволяет снизить фрагментированность +файла БД на диске и освободить место, в том числе в **Windows**. - +3. Автоматическая без-затратная компактификация БД путем возврата +освобождающихся страниц в область нераспределенного резерва в конце +файла данных. При этом уменьшается количество страниц находящихся в +памяти и участвующих в в обмене с диском. --------------------------------------------------------------------------------- +4. Поддержка ключей и значений нулевой длины, включая сортированные +дубликаты. -### Масштабируемость чтения +5. Возможность связать с каждой завершаемой транзакцией до 3 +дополнительных маркеров посредством `mdbx_canary_put()`, и прочитать их +в транзакции чтения посредством `mdbx_canary_get()`. -Для каждого движка показана суммарная производительность при -одновременном выполнении запросов чтения/поиска в 1-2-4-8 потоков на -машине с 4-мя физическими процессорами. +6. Возможность посредством `mdbx_replace()` обновить или удалить запись +с получением предыдущего значения данных, а также адресно изменить +конкретное multi-значение. - +7. Режим `LIFO RECLAIM`. --------------------------------------------------------------------------------- + Для повторного использования выбираются не самые старые, а + самые новые страницы из доступных. За счет этого цикл + использования страниц всегда имеет минимальную длину и не + зависит от общего числа выделенных страниц. -### Синхронная фиксация + В результате механизмы кэширования и обратной записи работают с + максимально возможной эффективностью. В случае использования + контроллера дисков или системы хранения с + [BBWC](https://en.wikipedia.org/wiki/BBWC) возможно + многократное увеличение производительности по записи + (обновлению данных). - - Линейная шкала слева и темные прямоугольники соответствуют количеству - транзакций в секунду, усредненному за всё время теста. +8. Генерация последовательностей посредством `mdbx_dbi_sequence()`. - - Логарифмическая шкала справа и желтые интервальные отрезки - соответствуют времени выполнения транзакций. При этом каждый отрезок - показывает минимальное и максимальное время, затраченное на выполнение - транзакций, а крестиком отмечено среднеквадратичное значение. +9. Обработчик `OOM-KICK`. -Выполняется **10.000 транзакций в режиме синхронной фиксации данных** на -диске. При этом требуется гарантия, что при аварийном выключении питания -(или другом подобном сбое) все данные будут консистентны и полностью -соответствовать последней завершенной транзакции. В _libmdbx_ в этом -режиме при фиксации каждой транзакции выполняется системный вызов -[fdatasync](https://linux.die.net/man/2/fdatasync). + Посредством `mdbx_env_set_oomfunc()` может быть установлен + внешний обработчик (callback), который будет вызван при + исчерпании свободных страниц по причине долгой операцией чтения + на фоне интенсивного изменения данных. + Обработчику будет передан PID и pthread_id виновника. + В свою очередь обработчик может предпринять одно из действий: -В каждой транзакции выполняется комбинированная CRUD-операция (две -вставки, одно чтение, одно обновление, одно удаление). Бенчмарк стартует -на пустой базе, а при завершении, в результате выполняемых действий, в -базе насчитывается 10.000 небольших key-value записей. + * нейтрализовать виновника (отправить сигнал kill #9), если + долгое чтение выполняется сторонним процессом; - + * отменить или перезапустить проблемную операцию чтения, если + операция выполняется одним из потоков текущего процесса; --------------------------------------------------------------------------------- + * подождать некоторое время, в расчете на то, что проблемная операция + чтения будет штатно завершена; -### Отложенная фиксация + * прервать текущую операцию изменения данных с возвратом кода + ошибки. - - Линейная шкала слева и темные прямоугольники соответствуют количеству - транзакций в секунду, усредненному за всё время теста. +10. Возможность открыть БД в эксклюзивном режиме посредством флага +`MDBX_EXCLUSIVE`. - - Логарифмическая шкала справа и желтые интервальные отрезки - соответствуют времени выполнения транзакций. При этом каждый отрезок - показывает минимальное и максимальное время, затраченное на выполнение - транзакций, а крестиком отмечено среднеквадратичное значение. +11. Возможность получить отставание текущей транзакции чтения от +последней версии данных в БД посредством `mdbx_txn_straggler()`. -Выполняется **100.000 транзакций в режиме отложенной фиксации данных** -на диске. При этом требуется гарантия, что при аварийном выключении -питания (или другом подобном сбое) все данные будут консистентны на -момент завершения одной из транзакций, но допускается потеря изменений -из некоторого количества последних транзакций, что для многих движков -предполагает включение -[WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) (write-ahead -logging) либо журнала транзакций, который в свою очередь опирается на -гарантию упорядоченности данных в журналируемой файловой системе. -_libmdbx_ при этом не ведет WAL, а передает весь контроль файловой -системе и ядру ОС. +12. Возможность явно запросить обновление существующей записи, без +создания новой посредством флажка `MDBX_CURRENT` для `mdbx_put()`. -В каждой транзакции выполняется комбинированная CRUD-операция (две -вставки, одно чтение, одно обновление, одно удаление). Бенчмарк стартует -на пустой базе, а при завершении, в результате выполняемых действий, в -базе насчитывается 100.000 небольших key-value записей. +13. Исправленный вариант `mdbx_cursor_count()`, возвращающий корректное +количество дубликатов для всех типов таблиц и любого положения курсора. - +14. Возможность получить посредством `mdbx_env_info()` дополнительную +информацию, включая номер самой старой версии БД (снимка данных), +который используется одним из читателей. --------------------------------------------------------------------------------- +15. Функция `mdbx_del()` не игнорирует дополнительный (уточняющий) +аргумент `data` для таблиц без дубликатов (без флажка `MDBX_DUPSORT`), а +при его ненулевом значении всегда использует его для сверки с удаляемой +записью. -### Асинхронная фиксация +16. Возможность открыть dbi-таблицу, одновременно с установкой +компараторов для ключей и данных, посредством `mdbx_dbi_open_ex()`. - - Линейная шкала слева и темные прямоугольники соответствуют количеству - транзакций в секунду, усредненному за всё время теста. +17. Возможность посредством `mdbx_is_dirty()` определить находятся ли +некоторый ключ или данные в "грязной" странице БД. Таким образом, +избегая лишнего копирования данных перед выполнением модифицирующих +операций (значения, размещенные в "грязных" страницах, могут быть +перезаписаны при изменениях, иначе они будут неизменны). - - Логарифмическая шкала справа и желтые интервальные отрезки - соответствуют времени выполнения транзакций. При этом каждый отрезок - показывает минимальное и максимальное время, затраченное на выполнение - транзакций, а крестиком отмечено среднеквадратичное значение. +18. Корректное обновление текущей записи, в том числе сортированного +дубликата, при использовании режима `MDBX_CURRENT` в +`mdbx_cursor_put()`. -Выполняется **1.000.000 транзакций в режиме асинхронной фиксации -данных** на диске. При этом требуется гарантия, что при аварийном -выключении питания (или другом подобном сбое) все данные будут -консистентны на момент завершения одной из транзакций, но допускается -потеря изменений из значительного количества последних транзакций. Во -всех движках при этом включался режим предполагающий минимальную -нагрузку на диск по записи, и соответственно минимальную гарантию -сохранности данных. В _libmdbx_ при этом используется режим асинхронной -записи измененных страниц на диск посредством ядра ОС и системного -вызова [msync(MS_ASYNC)](https://linux.die.net/man/2/msync). +19. Возможность узнать есть ли за текущей позицией курсора строка данных +посредством `mdbx_cursor_eof()`. -В каждой транзакции выполняется комбинированная CRUD-операция (две -вставки, одно чтение, одно обновление, одно удаление). Бенчмарк стартует -на пустой базе, а при завершении, в результате выполняемых действий, в -базе насчитывается 10.000 небольших key-value записей. +20. Дополнительный код ошибки `MDBX_EMULTIVAL`, который возвращается из +`mdbx_put()` и `mdbx_replace()` при попытке выполнить неоднозначное +обновление или удаления одного из нескольких значений с одним ключом. - +21. Возможность посредством `mdbx_get_ex()` получить значение по +заданному ключу, одновременно с количеством дубликатов. --------------------------------------------------------------------------------- +22. Наличие функций `mdbx_cursor_on_first()` и `mdbx_cursor_on_last()`, +которые позволяют быстро выяснить стоит ли курсор на первой/последней +позиции. -### Потребление ресурсов +23. Возможность автоматического формирования контрольных точек (сброса +данных на диск) при накоплении заданного объёма изменений, +устанавливаемого функцией `mdbx_env_set_syncbytes()`. -Показана соотнесенная сумма использованных ресурсов в ходе бенчмарка в -режиме отложенной фиксации: +24. Управление отладкой и получение отладочных сообщений посредством +`mdbx_setup_debug()`. - - суммарное количество операций ввода-вывода (IOPS), как записи, так и - чтения. +25. Функция `mdbx_env_pgwalk()` для обхода всех страниц БД. - - суммарное затраченное время процессора, как в режиме пользовательских процессов, - так и в режиме ядра ОС. +26. Три мета-страницы вместо двух, что позволяет гарантированно +консистентно обновлять слабые контрольные точки фиксации без риска +повредить крайнюю сильную точку фиксации. - - использованное место на диске при завершении теста, после закрытия БД из тестирующего процесса, - но без ожидания всех внутренних операций обслуживания (компактификации LSM и т.п.). +27. Гарантия сохранности БД в режиме `WRITEMAP+MAPSYNC`. + > В текущей версии _libmdbx_ вам предоставляется выбор между безопасным + > режимом (по умолчанию) асинхронной фиксации, и режимом `UTTERLY_NOSYNC` + > когда при системной аварии есть шанс полного разрушения БД как в LMDB. + > Для подробностей смотрите раздел + > [Сохранность данных в режиме асинхронной фиксации](#Сохранность-данных-в-режиме-асинхронной-фиксации). -Движок _ForestDB_ был исключен при оформлении результатов, так как -относительно конкурентов многократно превысил потребление каждого из -ресурсов (потратил процессорное время на генерацию IOPS для заполнения -диска), что не позволяло наглядно сравнить показатели остальных движков -на одной диаграмме. +28. Возможность закрыть БД в "грязном" состоянии (без сброса данных и +формирования сильной точки фиксации) посредством `mdbx_env_close_ex()`. -Все данные собирались посредством системного вызова -[getrusage()](http://man7.org/linux/man-pages/man2/getrusage.2.html) и -сканированием директорий с данными. +29. При завершении читающих транзакций, открытые в них DBI-хендлы не +закрываются и не теряются при завершении таких транзакций посредством +`mdbx_txn_abort()` или `mdbx_txn_reset()`. Что позволяет избавится от ряда +сложно обнаруживаемых ошибок. - +30. Все курсоры, как в транзакциях только для чтения, так и в пишущих, +могут быть переиспользованы посредством `mdbx_cursor_renew()` и ДОЛЖНЫ +ОСВОБОЖДАТЬСЯ ЯВНО. + > + > ## _ВАЖНО_, Обратите внимание! + > + > Это единственное изменение в API, которое значимо меняет + > семантику управления курсорами и может приводить к утечкам + > памяти. Следует отметить, что это изменение вынужденно. + > Так устраняется неоднозначность с массой тяжких последствий: + > + > - обращение к уже освобожденной памяти; + > - попытки повторного освобождения памяти; + > - повреждение памяти и ошибки сегментации. -------------------------------------------------------------------------------- @@ -382,7 +382,6 @@ _libmdbx_ при этом не ведет WAL, а передает весь ко #### Проблема долгих чтений - *Следует отметить*, что проблема "сборки мусора" так или иначе существует во всех СУБД (Vacuum в PostgreSQL). Однако в случае _libmdbx_ и LMDB она проявляется более остро, прежде всего из-за высокой @@ -448,19 +447,17 @@ _libmdbx_ при этом не ведет WAL, а передает весь ко за счет эффективной работы [BBWC](https://en.wikipedia.org/wiki/BBWC) при включении `LIFO RECLAIM` в _libmdbx_. - #### Сохранность данных в режиме асинхронной фиксации - При работе в режиме `WRITEMAP+MAPSYNC` запись измененных страниц выполняется ядром ОС, что имеет ряд преимуществ. Так например, при крахе приложения, ядро ОС сохранит все изменения. Однако, при аварийном отключении питания или сбое в ядре ОС, на диске -может быть сохранена только часть измененных страниц БД. При этом с большой -вероятностью может оказаться, что будут сохранены мета-страницы со -ссылками на страницы с новыми версиями данных, но не сами новые данные. -В этом случае БД будет безвозвратна разрушена, даже если до аварии -производилась полная синхронизация данных (посредством +может быть сохранена только часть измененных страниц БД. При этом с +большой вероятностью может оказаться, что будут сохранены мета-страницы +со ссылками на страницы с новыми версиями данных, но не сами новые +данные. В этом случае БД будет безвозвратна разрушена, даже если до +аварии производилась полная синхронизация данных (посредством `mdbx_env_sync()`). В _libmdbx_ эта проблема устранена путем полной переработки @@ -488,186 +485,194 @@ _libmdbx_ при этом не ведет WAL, а передает весь ко * При открытии БД выполняется автоматический откат к последней сильной фиксации. Этим обеспечивается гарантия сохранности БД. -Такая гарантия надежности не дается бесплатно. Для -сохранности данных, страницы, формирующие крайний снимок с -сильной фиксацией, не должны повторно использоваться -(перезаписываться) до формирования следующей сильной точки -фиксации. Таким образом, крайняя точка фиксации создает -описанный выше эффект "долгого чтения". Разница же здесь в том, -что при исчерпании свободных страниц ситуация будет -автоматически исправлена, посредством записи изменений на диск -и формирования новой сильной точки фиксации. +Такая гарантия надежности не дается бесплатно. Для сохранности данных, +страницы, формирующие крайний снимок с сильной фиксацией, не должны +повторно использоваться (перезаписываться) до формирования следующей +сильной точки фиксации. Таким образом, крайняя точка фиксации создает +описанный выше эффект "долгого чтения". Разница же здесь в том, что при +исчерпании свободных страниц ситуация будет автоматически исправлена, +посредством записи изменений на диск и формирования новой сильной точки +фиксации. Таким образом, в режиме безопасной асинхронной фиксации _libmdbx_ будет -всегда использовать новые страницы до исчерпания места в БД или до явного -формирования сильной точки фиксации посредством `mdbx_env_sync()`. -При этом суммарный трафик записи на диск будет примерно такой же, -как если бы отдельно фиксировалась каждая транзакция. +всегда использовать новые страницы до исчерпания места в БД или до +явного формирования сильной точки фиксации посредством +`mdbx_env_sync()`. При этом суммарный трафик записи на диск будет +примерно такой же, как если бы отдельно фиксировалась каждая транзакция. В текущей версии _libmdbx_ вам предоставляется выбор между безопасным -режимом (по умолчанию) асинхронной фиксации, и режимом `UTTERLY_NOSYNC` когда -при системной аварии есть шанс полного разрушения БД как в LMDB. +режимом (по умолчанию) асинхронной фиксации, и режимом `UTTERLY_NOSYNC` +когда при системной аварии есть шанс полного разрушения БД как в LMDB. -В последующих версиях _libmdbx_ будут предусмотрены средства -для асинхронной записи данных на диск с автоматическим -формированием сильных точек фиксации. +В последующих версиях _libmdbx_ будут предусмотрены средства для +асинхронной записи данных на диск с автоматическим формированием сильных +точек фиксации. -------------------------------------------------------------------------------- -Доработки и усовершенствования относительно LMDB -================================================ +Сравнение производительности +============================ -1. Режим `LIFO RECLAIM`. +Все представленные ниже данные получены многократным прогоном тестов на +ноутбуке Lenovo Carbon-2, i7-4600U 2.1 ГГц, 8 Гб ОЗУ, с SSD-диском +SAMSUNG MZNTD512HAGL-000L1 (DXT23L0Q) 512 Гб. - Для повторного использования выбираются не самые старые, а - самые новые страницы из доступных. За счет этого цикл - использования страниц всегда имеет минимальную длину и не - зависит от общего числа выделенных страниц. +Исходный код бенчмарка [_IOArena_](https://github.com/pmwkaa/ioarena) и +сценарии тестирования [доступны на +github](https://github.com/pmwkaa/ioarena/tree/HL%2B%2B2015). - В результате механизмы кэширования и обратной записи работают с - максимально возможной эффективностью. В случае использования - контроллера дисков или системы хранения с - [BBWC](https://en.wikipedia.org/wiki/BBWC) возможно - многократное увеличение производительности по записи - (обновлению данных). +-------------------------------------------------------------------------------- -2. Обработчик `OOM-KICK`. +### Интегральная производительность - Посредством `mdbx_env_set_oomfunc()` может быть установлен - внешний обработчик (callback), который будет вызван при - исчерпании свободных страниц из-за долгой операцией чтения. - Обработчику будет передан PID и pthread_id виновника. - В свою очередь обработчик может предпринять одно из действий: +Показана соотнесенная сумма ключевых показателей производительности в трёх +бенчмарках: - * нейтрализовать виновника (отправить сигнал kill #9), если - долгое чтение выполняется сторонним процессом; + - Чтение/Поиск на машине с 4-мя процессорами; - * отменить или перезапустить проблемную операцию чтения, если - операция выполняется одним из потоков текущего процесса; + - Транзакции с [CRUD](https://ru.wikipedia.org/wiki/CRUD)-операциями + (вставка, чтение, обновление, удаление) в режиме **синхронной фиксации** + данных (fdatasync при завершении каждой транзакции или аналог); - * подождать некоторое время, в расчете на то, что проблемная операция - чтения будет штатно завершена; + - Транзакции с [CRUD](https://ru.wikipedia.org/wiki/CRUD)-операциями + (вставка, чтение, обновление, удаление) в режиме **отложенной фиксации** + данных (отложенная запись посредством файловой систем или аналог); - * прервать текущую операцию изменения данных с возвратом кода - ошибки. +*Бенчмарк в режиме асинхронной записи не включен по двум причинам:* -3. Гарантия сохранности БД в режиме `WRITEMAP+MAPSYNC`. - > В текущей версии _libmdbx_ вам предоставляется выбор между безопасным - > режимом (по умолчанию) асинхронной фиксации, и режимом `UTTERLY_NOSYNC` - > когда при системной аварии есть шанс полного разрушения БД как в LMDB. - > Для подробностей смотрите раздел - > [Сохранность данных в режиме асинхронной фиксации](#Сохранность-данных-в-режиме-асинхронной-фиксации). + 1. Такое сравнение не совсем правомочно, его следует делать с движками + ориентированными на хранение данных в памяти ([Tarantool](https://tarantool.io/), [Redis](https://redis.io/)). -4. Возможность автоматического формирования контрольных точек -(сброса данных на диск) при накоплении заданного объёма изменений, -устанавливаемого функцией `mdbx_env_set_syncbytes()`. + 2. Превосходство libmdbx становится еще более подавляющим, что мешает + восприятию информации. -5. Возможность получить отставание текущей транзакции чтения от -последней версии данных в БД посредством `mdbx_txn_straggler()`. + -6. Утилита mdbx_chk для проверки БД и функция `mdbx_env_pgwalk()` для -обхода всех страниц БД. +-------------------------------------------------------------------------------- -7. Управление отладкой и получение отладочных сообщений посредством -`mdbx_setup_debug()`. +### Масштабируемость чтения -8. Возможность связать с каждой завершаемой транзакцией до 3 -дополнительных маркеров посредством `mdbx_canary_put()`, и прочитать их -в транзакции чтения посредством `mdbx_canary_get()`. +Для каждого движка показана суммарная производительность при +одновременном выполнении запросов чтения/поиска в 1-2-4-8 потоков на +машине с 4-мя физическими процессорами. -9. Возможность узнать есть ли за текущей позицией курсора строка данных -посредством `mdbx_cursor_eof()`. + -10. Возможность явно запросить обновление существующей записи, без -создания новой посредством флажка `MDBX_CURRENT` для `mdbx_put()`. +-------------------------------------------------------------------------------- -11. Возможность посредством `mdbx_replace()` обновить или удалить запись -с получением предыдущего значения данных, а также адресно изменить -конкретное multi-значение. +### Синхронная фиксация -12. Поддержка ключей и значений нулевой длины, включая сортированные -дубликаты. + - Линейная шкала слева и темные прямоугольники соответствуют количеству + транзакций в секунду, усредненному за всё время теста. -13. Исправленный вариант `mdbx_cursor_count()`, возвращающий корректное -количество дубликатов для всех типов таблиц и любого положения курсора. + - Логарифмическая шкала справа и желтые интервальные отрезки + соответствуют времени выполнения транзакций. При этом каждый отрезок + показывает минимальное и максимальное время, затраченное на выполнение + транзакций, а крестиком отмечено среднеквадратичное значение. -14. Возможность открыть БД в эксклюзивном режиме посредством флага -`MDBX_EXCLUSIVE`, например в целях её проверки. +Выполняется **10.000 транзакций в режиме синхронной фиксации данных** на +диске. При этом требуется гарантия, что при аварийном выключении питания +(или другом подобном сбое) все данные будут консистентны и полностью +соответствовать последней завершенной транзакции. В _libmdbx_ в этом +режиме при фиксации каждой транзакции выполняется системный вызов +[fdatasync](https://linux.die.net/man/2/fdatasync). -15. Возможность закрыть БД в "грязном" состоянии (без сброса данных и -формирования сильной точки фиксации) посредством `mdbx_env_close_ex()`. +В каждой транзакции выполняется комбинированная CRUD-операция (две +вставки, одно чтение, одно обновление, одно удаление). Бенчмарк стартует +на пустой базе, а при завершении, в результате выполняемых действий, в +базе насчитывается 10.000 небольших key-value записей. -16. Возможность получить посредством `mdbx_env_info()` дополнительную -информацию, включая номер самой старой версии БД (снимка данных), -который используется одним из читателей. + -17. Функция `mdbx_del()` не игнорирует дополнительный (уточняющий) -аргумент `data` для таблиц без дубликатов (без флажка `MDBX_DUPSORT`), а -при его ненулевом значении всегда использует его для сверки с удаляемой -записью. +-------------------------------------------------------------------------------- -18. Возможность открыть dbi-таблицу, одновременно с установкой -компараторов для ключей и данных, посредством `mdbx_dbi_open_ex()`. +### Отложенная фиксация -19. Возможность посредством `mdbx_is_dirty()` определить находятся ли -некоторый ключ или данные в "грязной" странице БД. Таким образом, -избегая лишнего копирования данных перед выполнением модифицирующих -операций (значения, размещенные в "грязных" страницах, могут быть -перезаписаны при изменениях, иначе они будут неизменны). + - Линейная шкала слева и темные прямоугольники соответствуют количеству + транзакций в секунду, усредненному за всё время теста. -20. Корректное обновление текущей записи, в том числе сортированного -дубликата, при использовании режима `MDBX_CURRENT` в -`mdbx_cursor_put()`. + - Логарифмическая шкала справа и желтые интервальные отрезки + соответствуют времени выполнения транзакций. При этом каждый отрезок + показывает минимальное и максимальное время, затраченное на выполнение + транзакций, а крестиком отмечено среднеквадратичное значение. -21. Все курсоры, как в транзакциях только для чтения, так и в пишущих, -могут быть переиспользованы посредством `mdbx_cursor_renew()` и ДОЛЖНЫ -ОСВОБОЖДАТЬСЯ ЯВНО. - > - > ## _ВАЖНО_, Обратите внимание! - > - > Это единственное изменение в API, которое значимо меняет - > семантику управления курсорами и может приводить к утечкам - > памяти. Следует отметить, что это изменение вынужденно. - > Так устраняется неоднозначность с массой тяжких последствий: - > - > - обращение к уже освобожденной памяти; - > - попытки повторного освобождения памяти; - > - повреждение памяти и ошибки сегментации. +Выполняется **100.000 транзакций в режиме отложенной фиксации данных** +на диске. При этом требуется гарантия, что при аварийном выключении +питания (или другом подобном сбое) все данные будут консистентны на +момент завершения одной из транзакций, но допускается потеря изменений +из некоторого количества последних транзакций, что для многих движков +предполагает включение +[WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) (write-ahead +logging) либо журнала транзакций, который в свою очередь опирается на +гарантию упорядоченности данных в журналируемой файловой системе. +_libmdbx_ при этом не ведет WAL, а передает весь контроль файловой +системе и ядру ОС. -22. Дополнительный код ошибки `MDBX_EMULTIVAL`, который возвращается из -`mdbx_put()` и `mdbx_replace()` при попытке выполнить неоднозначное -обновление или удаления одного из нескольких значений с одним ключом. +В каждой транзакции выполняется комбинированная CRUD-операция (две +вставки, одно чтение, одно обновление, одно удаление). Бенчмарк стартует +на пустой базе, а при завершении, в результате выполняемых действий, в +базе насчитывается 100.000 небольших key-value записей. -23. Возможность посредством `mdbx_get_ex()` получить значение по -заданному ключу, одновременно с количеством дубликатов. + -24. Наличие функций `mdbx_cursor_on_first()` и `mdbx_cursor_on_last()`, -которые позволяют быстро выяснить стоит ли курсор на первой/последней -позиции. +-------------------------------------------------------------------------------- -25. При завершении читающих транзакций, открытые в них DBI-хендлы не -закрываются и не теряются при завершении таких транзакций посредством -`mdbx_txn_abort()` или `mdbx_txn_reset()`. Что позволяет избавится от ряда -сложно обнаруживаемых ошибок. +### Асинхронная фиксация -26. Генерация последовательностей посредством `mdbx_dbi_sequence()`. + - Линейная шкала слева и темные прямоугольники соответствуют количеству + транзакций в секунду, усредненному за всё время теста. -27. Расширенное динамическое управление размером БД, включая выбор -размера страницы посредством `mdbx_env_set_geometry()`, -в том числе в **Windows** + - Логарифмическая шкала справа и желтые интервальные отрезки + соответствуют времени выполнения транзакций. При этом каждый отрезок + показывает минимальное и максимальное время, затраченное на выполнение + транзакций, а крестиком отмечено среднеквадратичное значение. -28. Три мета-страницы вместо двух, что позволяет гарантированно -консистентно обновлять слабые контрольные точки фиксации без риска -повредить крайнюю сильную точку фиксации. +Выполняется **1.000.000 транзакций в режиме асинхронной фиксации +данных** на диске. При этом требуется гарантия, что при аварийном +выключении питания (или другом подобном сбое) все данные будут +консистентны на момент завершения одной из транзакций, но допускается +потеря изменений из значительного количества последних транзакций. Во +всех движках при этом включался режим предполагающий минимальную +нагрузку на диск по записи, и соответственно минимальную гарантию +сохранности данных. В _libmdbx_ при этом используется режим асинхронной +записи измененных страниц на диск посредством ядра ОС и системного +вызова [msync(MS_ASYNC)](https://linux.die.net/man/2/msync). + +В каждой транзакции выполняется комбинированная CRUD-операция (две +вставки, одно чтение, одно обновление, одно удаление). Бенчмарк стартует +на пустой базе, а при завершении, в результате выполняемых действий, в +базе насчитывается 10.000 небольших key-value записей. + + + +-------------------------------------------------------------------------------- + +### Потребление ресурсов + +Показана соотнесенная сумма использованных ресурсов в ходе бенчмарка в +режиме отложенной фиксации: -29. В _libmdbx_ реализован автоматический возврат освобождающихся -страниц в область нераспределенного резерва в конце файла данных. При -этом уменьшается количество страниц загруженных в память и участвующих в -цикле обновления данных и записи на диск. Фактически _libmdbx_ выполняет -постоянную компактификацию данных, но не затрачивая на это -дополнительных ресурсов, а только освобождая их. При освобождении места -в БД и установке соответствующих параметров геометрии базы данных, также будет -уменьшаться размер файла на диске, в том числе в **Windows**. + - суммарное количество операций ввода-вывода (IOPS), как записи, так и + чтения. + + - суммарное затраченное время процессора, как в режиме пользовательских + процессов, так и в режиме ядра ОС. + + - использованное место на диске при завершении теста, после закрытия БД + из тестирующего процесса, но без ожидания всех внутренних операций + обслуживания (компактификации LSM и т.п.). + +Движок _ForestDB_ был исключен при оформлении результатов, так как +относительно конкурентов многократно превысил потребление каждого из +ресурсов (потратил процессорное время на генерацию IOPS для заполнения +диска), что не позволяло наглядно сравнить показатели остальных движков +на одной диаграмме. + +Все данные собирались посредством системного вызова +[getrusage()](http://man7.org/linux/man-pages/man2/getrusage.2.html) и +сканированием директорий с данными. + + -------------------------------------------------------------------------------- @@ -685,16 +690,3 @@ Idx Name Size VMA LMA File off Algn CONTENTS, ALLOC, LOAD, READONLY, CODE ``` - -``` -$ gcc -v -Using built-in specs. -COLLECT_GCC=gcc -COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/7/lto-wrapper -OFFLOAD_TARGET_NAMES=nvptx-none -OFFLOAD_TARGET_DEFAULT=1 -Target: x86_64-linux-gnu -Configured with: ../src/configure -v --with-pkgversion='Ubuntu 7.2.0-8ubuntu3' --with-bugurl=file:///usr/share/doc/gcc-7/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++ --prefix=/usr --with-gcc-major-version-only --program-suffix=-7 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-libmpx --enable-plugin --enable-default-pie --with-system-zlib --with-target-system-zlib --enable-objc-gc=auto --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu -Thread model: posix -gcc version 7.2.0 (Ubuntu 7.2.0-8ubuntu3) -``` diff --git a/libs/libmdbx/src/README.md b/libs/libmdbx/src/README.md index 92b6542fa7..7c07de316e 100644 --- a/libs/libmdbx/src/README.md +++ b/libs/libmdbx/src/README.md @@ -9,9 +9,21 @@ libmdbx ## Project Status for now - - The stable versions ([_stable/0.0_](https://github.com/leo-yuriev/libmdbx/tree/stable/0.0) and [_stable/0.1_](https://github.com/leo-yuriev/libmdbx/tree/stable/0.1) branches) of _MDBX_ are frozen, i.e. no new features or API changes, but only bug fixes. - - The next version ([_devel_](https://github.com/leo-yuriev/libmdbx/tree/devel) branch) **is under active non-public development**, i.e. current API and set of features are extreme volatile. - - The immediate goal of development is formation of the stable API and the stable internal database format, which allows realise all PLANNED FEATURES: + - The stable versions + ([_stable/0.0_](https://github.com/leo-yuriev/libmdbx/tree/stable/0.0) + and + [_stable/0.1_](https://github.com/leo-yuriev/libmdbx/tree/stable/0.1) + branches) of _MDBX_ are frozen, i.e. no new features or API changes, but + only bug fixes. + + - The next version + ([_devel_](https://github.com/leo-yuriev/libmdbx/tree/devel) branch) + **is under active non-public development**, i.e. current API and set of + features are extreme volatile. + + - The immediate goal of development is formation of the stable API and + the stable internal database format, which allows realise all PLANNED + FEATURES: 1. Integrity check by [Merkle tree](https://en.wikipedia.org/wiki/Merkle_tree); 2. Support for [raw block devices](https://en.wikipedia.org/wiki/Raw_device); 3. Separate place (HDD) for large data items; @@ -24,19 +36,21 @@ Don't miss [Java Native Interface](https://github.com/castortech/mdbxjni) by [Ca ----- -Nowadays MDBX intended for Linux, and support Windows (since -Windows Server 2008) as a complementary platform. Support for -other OS could be implemented on commercial basis. However such -enhancements (i.e. pull requests) could be accepted in -mainstream only when corresponding public and free Continuous -Integration service will be available. +Nowadays MDBX intended for Linux, and support Windows (since Windows +Server 2008) as a complementary platform. Support for other OS could be +implemented on commercial basis. However such enhancements (i.e. pull +requests) could be accepted in mainstream only when corresponding public +and free Continuous Integration service will be available. ## Contents - - [Overview](#overview) - [Comparison with other DBs](#comparison-with-other-dbs) - [History & Acknowledgments](#history) - [Main features](#main-features) +- [Improvements over LMDB](#improvements-over-lmdb) +- [Gotchas](#gotchas) + - [Long-time read transactions problem](#long-time-read-transactions-problem) + - [Data safety in async-write-mode](#data-safety-in-async-write-mode) - [Performance comparison](#performance-comparison) - [Integral performance](#integral-performance) - [Read scalability](#read-scalability) @@ -44,52 +58,58 @@ Integration service will be available. - [Lazy-write mode](#lazy-write-mode) - [Async-write mode](#async-write-mode) - [Cost comparison](#cost-comparison) -- [Gotchas](#gotchas) - - [Long-time read transactions problem](#long-time-read-transactions-problem) - - [Data safety in async-write-mode](#data-safety-in-async-write-mode) -- [Improvements over LMDB](#improvements-over-lmdb) ## Overview +_libmdbx_ is an embedded lightweight key-value database engine oriented +for performance under Linux and Windows. -_libmdbx_ is an embedded lightweight key-value database engine oriented for performance under Linux and Windows. - -_libmdbx_ allows multiple processes to read and update several key-value tables concurrently, -while being [ACID](https://en.wikipedia.org/wiki/ACID)-compliant, with minimal overhead and operation cost of Olog(N). +_libmdbx_ allows multiple processes to read and update several key-value +tables concurrently, while being +[ACID](https://en.wikipedia.org/wiki/ACID)-compliant, with minimal +overhead and operation cost of Olog(N). _libmdbx_ provides -[serializability](https://en.wikipedia.org/wiki/Serializability) and consistency of data after crash. -Read-write transactions don't block read-only transactions and are -[serialized](https://en.wikipedia.org/wiki/Serializability) by [mutex](https://en.wikipedia.org/wiki/Mutual_exclusion). - -_libmdbx_ [wait-free](https://en.wikipedia.org/wiki/Non-blocking_algorithm#Wait-freedom) provides parallel read transactions -without atomic operations or synchronization primitives. - -_libmdbx_ uses [B+Trees](https://en.wikipedia.org/wiki/B%2B_tree) and [mmap](https://en.wikipedia.org/wiki/Memory-mapped_file), -doesn't use [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging). This might have caveats for some workloads. +[serializability](https://en.wikipedia.org/wiki/Serializability) and +consistency of data after crash. Read-write transactions don't block +read-only transactions and are +[serialized](https://en.wikipedia.org/wiki/Serializability) by +[mutex](https://en.wikipedia.org/wiki/Mutual_exclusion). + +_libmdbx_ +[wait-free](https://en.wikipedia.org/wiki/Non-blocking_algorithm#Wait-freedom) +provides parallel read transactions without atomic operations or +synchronization primitives. + +_libmdbx_ uses [B+Trees](https://en.wikipedia.org/wiki/B%2B_tree) and +[mmap](https://en.wikipedia.org/wiki/Memory-mapped_file), doesn't use +[WAL](https://en.wikipedia.org/wiki/Write-ahead_logging). This might +have caveats for some workloads. ### Comparison with other DBs - -Because _libmdbx_ is currently overhauled, I think it's better to just link -[chapter of Comparison with other databases](https://github.com/coreos/bbolt#comparison-with-other-databases) here. +Because _libmdbx_ is currently overhauled, I think it's better to just +link [chapter of Comparison with other +databases](https://github.com/coreos/bbolt#comparison-with-other-databases) +here. ### History - -The _libmdbx_ design is based on [Lightning Memory-Mapped Database](https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database). -Initial development was going in [ReOpenLDAP](https://github.com/leo-yuriev/ReOpenLDAP) project, about a year later it -received separate development effort and in autumn 2015 was isolated to separate project, which was -[presented at Highload++ 2015 conference](http://www.highload.ru/2015/abstracts/1831.html). - -Since early 2017 _libmdbx_ is used in [Fast Positive Tables](https://github.com/leo-yuriev/libfpta), +The _libmdbx_ design is based on [Lightning Memory-Mapped +Database](https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database). +Initial development was going in +[ReOpenLDAP](https://github.com/leo-yuriev/ReOpenLDAP) project, about a +year later it received separate development effort and in autumn 2015 +was isolated to separate project, which was [presented at Highload++ +2015 conference](http://www.highload.ru/2015/abstracts/1831.html). + +Since early 2017 _libmdbx_ is used in [Fast PositiveTables](https://github.com/leo-yuriev/libfpta), by [Positive Technologies](https://www.ptsecurity.com). #### Acknowledgments +Howard Chu (Symas Corporation) - the author of LMDB, from which +originated the MDBX in 2015. -Howard Chu (Symas Corporation) - the author of LMDB, -from which originated the MDBX in 2015. - -Martin Hedenfalk <martin@bzero.se> - the author of `btree.c` code, -which was used for begin development of LMDB. +Martin Hedenfalk <martin@bzero.se> - the author of `btree.c` code, which +was used for begin development of LMDB. Main features @@ -98,365 +118,468 @@ Main features _libmdbx_ inherits all keys features and characteristics from [LMDB](https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database): -1. Data is stored in ordered map, keys are always sorted, range lookups are supported. - -2. Data is [mmaped](https://en.wikipedia.org/wiki/Memory-mapped_file) to memory of each worker DB process, read transactions are zero-copy. - -3. Transactions are [ACID](https://en.wikipedia.org/wiki/ACID)-compliant, thanks to - [MVCC](https://en.wikipedia.org/wiki/Multiversion_concurrency_control) and [CoW](https://en.wikipedia.org/wiki/Copy-on-write). - Writes are strongly serialized and aren't blocked by reads, transactions can't conflict with each other. - Reads are guaranteed to get only commited data - ([relaxing serializability](https://en.wikipedia.org/wiki/Serializability#Relaxing_serializability)). - -4. Reads and queries are [non-blocking](https://en.wikipedia.org/wiki/Non-blocking_algorithm), - don't use [atomic operations](https://en.wikipedia.org/wiki/Linearizability#High-level_atomic_operations). - Readers don't block each other and aren't blocked by writers. Read performance scales linearly with CPU core count. - > Though "connect to DB" (start of first read transaction in thread) and "disconnect from DB" (shutdown or thread - > termination) requires to acquire a lock to register/unregister current thread from "readers table" - -5. Keys with multiple values are stored efficiently without key duplication, sorted by value, including integers - (reasonable for secondary indexes). - -6. Efficient operation on short fixed length keys, including integer ones. - -7. [WAF](https://en.wikipedia.org/wiki/Write_amplification) (Write Amplification Factor) и RAF (Read Amplification Factor) - are Olog(N). - -8. No [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) and transaction journal. - In case of a crash no recovery needed. No need for regular maintenance. Backups can be made on the fly on working DB - without freezing writers. +1. Data is stored in ordered map, keys are always sorted, range lookups +are supported. + +2. Data is [mmaped](https://en.wikipedia.org/wiki/Memory-mapped_file) to +memory of each worker DB process, read transactions are zero-copy. + +3. Transactions are +[ACID](https://en.wikipedia.org/wiki/ACID)-compliant, thanks to +[MVCC](https://en.wikipedia.org/wiki/Multiversion_concurrency_control) +and [CoW](https://en.wikipedia.org/wiki/Copy-on-write). Writes are +strongly serialized and aren't blocked by reads, transactions can't +conflict with each other. Reads are guaranteed to get only commited data +([relaxing serializability](https://en.wikipedia.org/wiki/Serializability#Relaxing_serializability)). + +4. Reads and queries are +[non-blocking](https://en.wikipedia.org/wiki/Non-blocking_algorithm), +don't use [atomic +operations](https://en.wikipedia.org/wiki/Linearizability#High-level_atomic_operations). +Readers don't block each other and aren't blocked by writers. Read +performance scales linearly with CPU core count. + > Though "connect to DB" (start of first read transaction in thread) and + > "disconnect from DB" (shutdown or thread termination) requires to + > acquire a lock to register/unregister current thread from "readers + > table" + +5. Keys with multiple values are stored efficiently without key +duplication, sorted by value, including integers (reasonable for +secondary indexes). + +6. Efficient operation on short fixed length keys, including integer +ones. + +7. [WAF](https://en.wikipedia.org/wiki/Write_amplification) (Write +Amplification Factor) и RAF (Read Amplification Factor) are Olog(N). + +8. No [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) and +transaction journal. In case of a crash no recovery needed. No need for +regular maintenance. Backups can be made on the fly on working DB + without freezing writers. 9. No custom memory management, all done with standard OS syscalls. +-------------------------------------------------------------------------------- -Performance comparison -===================== +Improvements over LMDB +====================== -All benchmarks were done by [IOArena](https://github.com/pmwkaa/ioarena) -and multiple [scripts](https://github.com/pmwkaa/ioarena/tree/HL%2B%2B2015) -runs on Lenovo Carbon-2 laptop, i7-4600U 2.1 GHz, 8 Gb RAM, -SSD SAMSUNG MZNTD512HAGL-000L1 (DXT23L0Q) 512 Gb. +1. `mdbx_chk` tool for DB integrity check. --------------------------------------------------------------------------------- +2. Automatic dynamic DB size management according to the parameters +specified by `mdbx_env_set_geometry()` function. Including including +growth step and truncation threshold, as well as the choice of page +size. -### Integral performance +3. Automatic returning of freed pages into unallocated space at the end +of database file with optionally automatic shrinking it. This reduces +amount of pages resides in RAM and circulated in disk I/O. In fact +_libmdbx_ constantly performs DB compactification, without spending +additional resources for that. -Here showed sum of performance metrics in 3 benchmarks: +4. Support for keys and values of zero length, including sorted +duplicates. - - Read/Search on 4 CPU cores machine; +5. Ability to assign up to 3 markers to commiting transaction with +`mdbx_canary_put()` and then get them in read transaction by +`mdbx_canary_get()`. - - Transactions with [CRUD](https://en.wikipedia.org/wiki/CRUD) operations - in sync-write mode (fdatasync is called after each transaction); +6. Ability to update or delete record and get previous value via +`mdbx_replace()` Also can update specific multi-value. - - Transactions with [CRUD](https://en.wikipedia.org/wiki/CRUD) operations - in lazy-write mode (moment to sync data to persistent storage is decided by OS). +7. `LIFO RECLAIM` mode: -*Reasons why asynchronous mode isn't benchmarked here:* + The newest pages are picked for reuse instead of the oldest. This allows + to minimize reclaim loop and make it execution time independent of total + page count. - 1. It doesn't make sense as it has to be done with DB engines, oriented for keeping data in memory e.g. - [Tarantool](https://tarantool.io/), [Redis](https://redis.io/)), etc. + This results in OS kernel cache mechanisms working with maximum + efficiency. In case of using disk controllers or storages with + [BBWC](https://en.wikipedia.org/wiki/Disk_buffer#Write_acceleration) + this may greatly improve write performance. - 2. Performance gap is too high to compare in any meaningful way. +8. Sequence generation via `mdbx_dbi_sequence()`. - +9. `OOM-KICK` callback. --------------------------------------------------------------------------------- + `mdbx_env_set_oomfunc()` allows to set a callback, which will be called + in the event of DB space exhausting during long-time read transaction in + parallel with extensive updating. Callback will be invoked with PID and + pthread_id of offending thread as parameters. Callback can do any of + these things to remedy the problem: -### Read Scalability + * wait for read transaction to finish normally; -Summary performance with concurrent read/search queries in 1-2-4-8 threads on 4 CPU cores machine. + * kill the offending process (signal 9), if separate process is doing + long-time read; - + * abort or restart offending read transaction if it's running in sibling + thread; --------------------------------------------------------------------------------- + * abort current write transaction with returning error code. -### Sync-write mode +10. Ability to open DB in exclusive mode with `MDBX_EXCLUSIVE` flag. - - Linear scale on left and dark rectangles mean arithmetic mean transactions per second; +11. Ability to get how far current read-only snapshot is from latest +version of the DB by `mdbx_txn_straggler()`. - - Logarithmic scale on right is in seconds and yellow intervals mean execution time of transactions. - Each interval shows minimal and maximum execution time, cross marks standard deviation. +12. Ability to explicitly request update of present record without +creating new record. Implemented as `MDBX_CURRENT` flag for +`mdbx_put()`. -**10,000 transactions in sync-write mode**. In case of a crash all data is consistent and state is right after last successful transaction. [fdatasync](https://linux.die.net/man/2/fdatasync) syscall is used after each write transaction in this mode. +13. Fixed `mdbx_cursor_count()`, which returns correct count of +duplicated for all table types and any cursor position. -In the benchmark each transaction contains combined CRUD operations (2 inserts, 1 read, 1 update, 1 delete). -Benchmark starts on empty database and after full run the database contains 10,000 small key-value records. +14. `mdbx_env_info()` to getting additional info, including number of +the oldest snapshot of DB, which is used by one of the readers. - +15. `mdbx_del()` doesn't ignore additional argument (specifier) `data` +for tables without duplicates (without flag `MDBX_DUPSORT`), if `data` +is not null then always uses it to verify record, which is being +deleted. --------------------------------------------------------------------------------- +16. Ability to open dbi-table with simultaneous setup of comparators for +keys and values, via `mdbx_dbi_open_ex()`. -### Lazy-write mode +17. `mdbx_is_dirty()`to find out if key or value is on dirty page, that +useful to avoid copy-out before updates. - - Linear scale on left and dark rectangles mean arithmetic mean of thousands transactions per second; +18. Correct update of current record in `MDBX_CURRENT` mode of +`mdbx_cursor_put()`, including sorted duplicated. - - Logarithmic scale on right in seconds and yellow intervals mean execution time of transactions. Each interval shows minimal and maximum execution time, cross marks standard deviation. +19. Check if there is a row with data after current cursor position via +`mdbx_cursor_eof()`. -**100,000 transactions in lazy-write mode**. -In case of a crash all data is consistent and state is right after one of last transactions, but transactions after it -will be lost. Other DB engines use [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) or transaction journal for that, -which in turn depends on order of operations in journaled filesystem. _libmdbx_ doesn't use WAL and hands I/O operations -to filesystem and OS kernel (mmap). +20. Additional error code `MDBX_EMULTIVAL`, which is returned by +`mdbx_put()` and `mdbx_replace()` in case is ambiguous update or delete. -In the benchmark each transaction contains combined CRUD operations (2 inserts, 1 read, 1 update, 1 delete). -Benchmark starts on empty database and after full run the database contains 100,000 small key-value records. +21. Ability to get value by key and duplicates count by `mdbx_get_ex()`. +22. Functions `mdbx_cursor_on_first()` and `mdbx_cursor_on_last()`, +which allows to know if cursor is currently on first or last position +respectively. - +23. Automatic creation of synchronization points (flush changes to +persistent storage) when changes reach set threshold (threshold can be +set by `mdbx_env_set_syncbytes()`). --------------------------------------------------------------------------------- +24. Control over debugging and receiving of debugging messages via +`mdbx_setup_debug()`. -### Async-write mode +25. Function `mdbx_env_pgwalk()` for page-walking all pages in DB. - - Linear scale on left and dark rectangles mean arithmetic mean of thousands transactions per second; +26. Three meta-pages instead of two, this allows to guarantee +consistently update weak sync-points without risking to corrupt last +steady sync-point. - - Logarithmic scale on right in seconds and yellow intervals mean execution time of transactions. Each interval shows minimal and maximum execution time, cross marks standard deviation. +27. Guarantee of DB integrity in `WRITEMAP+MAPSYNC` mode: + > Current _libmdbx_ gives a choice of safe async-write mode (default) + > and `UTTERLY_NOSYNC` mode which may result in full + > DB corruption during system crash as with LMDB. For details see + > [Data safety in async-write mode](#data-safety-in-async-write-mode). -**1,000,000 transactions in async-write mode**. In case of a crash all data will be consistent and state will be right after one of last transactions, but lost transaction count is much higher than in lazy-write mode. All DB engines in this mode do as little writes as possible on persistent storage. _libmdbx_ uses [msync(MS_ASYNC)](https://linux.die.net/man/2/msync) in this mode. +28. Ability to close DB in "dirty" state (without data flush and +creation of steady synchronization point) via `mdbx_env_close_ex()`. -In the benchmark each transaction contains combined CRUD operations (2 inserts, 1 read, 1 update, 1 delete). -Benchmark starts on empty database and after full run the database contains 10,000 small key-value records. +29. If read transaction is aborted via `mdbx_txn_abort()` or +`mdbx_txn_reset()` then DBI-handles, which were opened in it, aren't +closed or deleted. This allows to avoid several types of hard-to-debug +errors. - +30. All cursors in all read and write transactions can be reused by +`mdbx_cursor_renew()` and MUST be freed explicitly. + > ## Caution, please pay attention! + > + > This is the only change of API, which changes semantics of cursor management + > and can lead to memory leaks on misuse. This is a needed change as it eliminates ambiguity + > which helps to avoid such errors as: + > - use-after-free; + > - double-free; + > - memory corruption and segfaults. -------------------------------------------------------------------------------- -### Cost comparison - -Summary of used resources during lazy-write mode benchmarks: +## Gotchas - - Read and write IOPS; +1. At one moment there can be only one writer. But this allows to +serialize writes and eliminate any possibility of conflict or logical +errors during transaction rollback. + +2. No [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) means +relatively big [WAF](https://en.wikipedia.org/wiki/Write_amplification) +(Write Amplification Factor). Because of this syncing data to disk might +be quite resource intensive and be main performance bottleneck during +intensive write workload. + > As compromise _libmdbx_ allows several modes of lazy and/or periodic + > syncing, including `MAPASYNC` mode, which modificate data in memory and + > asynchronously syncs data to disk, moment to sync is picked by OS. + > + > Although this should be used with care, synchronous transactions in a DB + > with transaction journal will require 2 IOPS minimum (probably 3-4 in + > practice) because of filesystem overhead, overhead depends on + > filesystem, not on record count or record size. In _libmdbx_ IOPS count + > will grow logarithmically depending on record count in DB (height of B+ + > tree) and will require at least 2 IOPS per transaction too. + +3. [CoW](https://en.wikipedia.org/wiki/Copy-on-write) for +[MVCC](https://en.wikipedia.org/wiki/Multiversion_concurrency_control) +is done on memory page level with +[B+trees](https://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE). +Therefore altering data requires to copy about Olog(N) memory pages, +which uses [memory bandwidth](https://en.wikipedia.org/wiki/Memory_bandwidth) and is main +performance bottleneck in `MAPASYNC` mode. + > This is unavoidable, but isn't that bad. Syncing data to disk requires + > much more similar operations which will be done by OS, therefore this is + > noticeable only if data sync to persistent storage is fully disabled. + > _libmdbx_ allows to safely save data to persistent storage with minimal + > performance overhead. If there is no need to save data to persistent + > storage then it's much more preferable to use `std::map`. + + +4. LMDB has a problem of long-time readers which degrades performance +and bloats DB. + > _libmdbx_ addresses that, details below. - - Sum of user CPU time and sys CPU time; +5. _LMDB_ is susceptible to DB corruption in `WRITEMAP+MAPASYNC` mode. +_libmdbx_ in `WRITEMAP+MAPASYNC` guarantees DB integrity and consistency +of data. + > Additionally there is an alternative: `UTTERLY_NOSYNC` mode. + > Details below. - - Used space on persistent storage after the test and closed DB, but not waiting for the end of all internal - housekeeping operations (LSM compactification, etc). -_ForestDB_ is excluded because benchmark showed it's resource consumption for each resource (CPU, IOPS) much higher than other engines which prevents to meaningfully compare it with them. +#### Long-time read transactions problem +Garbage collection problem exists in all databases one way or another +(e.g. VACUUM in PostgreSQL). But in _libmdbx_ and LMDB it's even more +important because of high performance and deliberate simplification of +internals with emphasis on performance. -All benchmark data is gathered by [getrusage()](http://man7.org/linux/man-pages/man2/getrusage.2.html) syscall and by -scanning data directory. +* Altering data during long read operation may exhaust available space +on persistent storage. - +* If available space is exhausted then any attempt to update data +results in `MAP_FULL` error until long read operation ends. --------------------------------------------------------------------------------- +* Main examples of long readers is hot backup and debugging of client +application which actively uses read transactions. -## Gotchas +* In _LMDB_ this results in degraded performance of all operations of +syncing data to persistent storage. -1. At one moment there can be only one writer. But this allows to serialize writes and eliminate any possibility - of conflict or logical errors during transaction rollback. - -2. No [WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) means relatively - big [WAF](https://en.wikipedia.org/wiki/Write_amplification) (Write Amplification Factor). - Because of this syncing data to disk might be quite resource intensive and be main performance bottleneck - during intensive write workload. - > As compromise _libmdbx_ allows several modes of lazy and/or periodic syncing, including `MAPASYNC` mode, which modificate - > data in memory and asynchronously syncs data to disk, moment to sync is picked by OS. - > - > Although this should be used with care, synchronous transactions in a DB with transaction journal will require 2 IOPS - > minimum (probably 3-4 in practice) because of filesystem overhead, overhead depends on filesystem, not on record - > count or record size. In _libmdbx_ IOPS count will grow logarithmically depending on record count in DB (height of B+ tree) - > and will require at least 2 IOPS per transaction too. - -3. [CoW](https://en.wikipedia.org/wiki/Copy-on-write) - for [MVCC](https://en.wikipedia.org/wiki/Multiversion_concurrency_control) is done on memory page level with [B+ - trees](https://ru.wikipedia.org/wiki/B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE). - Therefore altering data requires to copy about Olog(N) memory pages, which uses [memory bandwidth](https://en.wikipedia.org/wiki/Memory_bandwidth) and is main performance bottleneck in `MAPASYNC` mode. - > This is unavoidable, but isn't that bad. Syncing data to disk requires much more similar operations which will - > be done by OS, therefore this is noticeable only if data sync to persistent storage is fully disabled. - > _libmdbx_ allows to safely save data to persistent storage with minimal performance overhead. If there is no need - > to save data to persistent storage then it's much more preferable to use `std::map`. - - -4. LMDB has a problem of long-time readers which degrades performance and bloats DB - > _libmdbx_ addresses that, details below. +* _libmdbx_ has a mechanism which aborts such operations and `LIFO RECLAIM` +mode which addresses performance degradation. + +Read operations operate only over snapshot of DB which is consistent on +the moment when read transaction started. This snapshot doesn't change +throughout the transaction but this leads to inability to reclaim the +pages until read transaction ends. + +In _LMDB_ this leads to a problem that memory pages, allocated for +operations during long read, will be used for operations and won't be +reclaimed until DB process terminates. In _LMDB_ they are used in +[FIFO](https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics)) +manner, which causes increased page count and less chance of cache hit +during I/O. In other words: one long-time reader can impact performance +of all database until it'll be reopened. + +_libmdbx_ addresses the problem, details below. Illustrations to this +problem can be found in the +[presentation](http://www.slideshare.net/leoyuriev/lmdb). There is also +example of performance increase thanks to +[BBWC](https://en.wikipedia.org/wiki/Disk_buffer#Write_acceleration) +when `LIFO RECLAIM` enabled in _libmdbx_. -5. _LMDB_ is susceptible to DB corruption in `WRITEMAP+MAPASYNC` mode. - _libmdbx_ in `WRITEMAP+MAPASYNC` guarantees DB integrity and consistency of data. - > Additionally there is an alternative: `UTTERLY_NOSYNC` mode. Details below. +#### Data safety in async-write mode +In `WRITEMAP+MAPSYNC` mode dirty pages are written to persistent storage +by kernel. This means that in case of application crash OS kernel will +write all dirty data to disk and nothing will be lost. But in case of +hardware malfunction or OS kernel fatal error only some dirty data might +be synced to disk, and there is high probability that pages with +metadata saved, will point to non-saved, hence non-existent, data pages. +In such situation, DB is completely corrupted and can't be repaired even +if there was full sync before the crash via `mdbx_env_sync(). +_libmdbx_ addresses this by fully reimplementing write path of data: -#### Long-time read transactions problem +* In `WRITEMAP+MAPSYNC` mode meta-data pages aren't updated in place, +instead their shadow copies are used and their updates are synced after +data is flushed to disk. -Garbage collection problem exists in all databases one way or another (e.g. VACUUM in PostgreSQL). -But in _libmdbx_ and LMDB it's even more important because of high performance and deliberate -simplification of internals with emphasis on performance. +* During transaction commit _libmdbx_ marks synchronization points as +steady or weak depending on how much synchronization needed between RAM +and persistent storage, e.g. in `WRITEMAP+MAPSYNC` commited transactions +are marked as weak, but during explicit data synchronization - as +steady. -* Altering data during long read operation may exhaust available space on persistent storage. +* _libmdbx_ maintains three separate meta-pages instead of two. This +allows to commit transaction with steady or weak synchronization point +without losing two previous synchronization points (one of them can be +steady, and second - weak). This allows to order weak and steady +synchronization points in any order without losing consistency in case +of system crash. -* If available space is exhausted then any attempt to update data - results in `MAP_FULL` error until long read operation ends. +* During DB open _libmdbx_ rollbacks to the last steady synchronization +point, this guarantees database integrity. -* Main examples of long readers is hot backup - and debugging of client application which actively uses read transactions. +For data safety pages which form database snapshot with steady +synchronization point must not be updated until next steady +synchronization point. So last steady synchronization point creates +"long-time read" effect. The only difference that in case of memory +exhaustion the problem will be immediately addressed by flushing changes +to persistent storage and forming new steady synchronization point. -* In _LMDB_ this results in degraded performance of all operations - of syncing data to persistent storage. +So in async-write mode _libmdbx_ will always use new pages until memory +is exhausted or `mdbx_env_sync()` is invoked. Total disk usage will be +almost the same as in sync-write mode. -* _libmdbx_ has a mechanism which aborts such operations and `LIFO RECLAIM` - mode which addresses performance degradation. +Current _libmdbx_ gives a choice of safe async-write mode (default) and +`UTTERLY_NOSYNC` mode which may result in full DB corruption during +system crash as with LMDB. -Read operations operate only over snapshot of DB which is consistent on the moment when read transaction started. -This snapshot doesn't change throughout the transaction but this leads to inability to reclaim the pages until -read transaction ends. +Next version of _libmdbx_ will create steady synchronization points +automatically in async-write mode. -In _LMDB_ this leads to a problem that memory pages, allocated for operations during long read, will be used for operations -and won't be reclaimed until DB process terminates. In _LMDB_ they are used in -[FIFO](https://en.wikipedia.org/wiki/FIFO_(computing_and_electronics)) manner, which causes increased page count -and less chance of cache hit during I/O. In other words: one long-time reader can impact performance of all database -until it'll be reopened. +-------------------------------------------------------------------------------- -_libmdbx_ addresses the problem, details below. Illustrations to this problem can be found in the -[presentation](http://www.slideshare.net/leoyuriev/lmdb). There is also example of performance increase thanks to -[BBWC](https://en.wikipedia.org/wiki/Disk_buffer#Write_acceleration) when `LIFO RECLAIM` enabled in _libmdbx_. +Performance comparison +====================== -#### Data safety in async-write mode +All benchmarks were done by [IOArena](https://github.com/pmwkaa/ioarena) +and multiple [scripts](https://github.com/pmwkaa/ioarena/tree/HL%2B%2B2015) +runs on Lenovo Carbon-2 laptop, i7-4600U 2.1 GHz, 8 Gb RAM, +SSD SAMSUNG MZNTD512HAGL-000L1 (DXT23L0Q) 512 Gb. -In `WRITEMAP+MAPSYNC` mode dirty pages are written to persistent storage by kernel. This means that in case of application -crash OS kernel will write all dirty data to disk and nothing will be lost. But in case of hardware malfunction or OS kernel -fatal error only some dirty data might be synced to disk, and there is high probability that pages with metadata saved, -will point to non-saved, hence non-existent, data pages. In such situation, DB is completely corrupted and can't be -repaired even if there was full sync before the crash via `mdbx_env_sync(). +-------------------------------------------------------------------------------- -_libmdbx_ addresses this by fully reimplementing write path of data: +### Integral performance -* In `WRITEMAP+MAPSYNC` mode meta-data pages aren't updated in place, instead their shadow copies are used and their updates - are synced after data is flushed to disk. +Here showed sum of performance metrics in 3 benchmarks: -* During transaction commit _libmdbx_ marks synchronization points as steady or weak depending on how much synchronization - needed between RAM and persistent storage, e.g. in `WRITEMAP+MAPSYNC` commited transactions are marked as weak, - but during explicit data synchronization - as steady. + - Read/Search on 4 CPU cores machine; -* _libmdbx_ maintains three separate meta-pages instead of two. This allows to commit transaction with steady or -weak synchronization point without losing two previous synchronization points (one of them can be steady, and second - weak). -This allows to order weak and steady synchronization points in any order without losing consistency in case of system crash. + - Transactions with [CRUD](https://en.wikipedia.org/wiki/CRUD) + operations in sync-write mode (fdatasync is called after each + transaction); -* During DB open _libmdbx_ rollbacks to the last steady synchronization point, this guarantees database integrity. + - Transactions with [CRUD](https://en.wikipedia.org/wiki/CRUD) + operations in lazy-write mode (moment to sync data to persistent storage + is decided by OS). -For data safety pages which form database snapshot with steady synchronization point must not be updated until next steady -synchronization point. So last steady synchronization point creates "long-time read" effect. The only difference that in case -of memory exhaustion the problem will be immediately addressed by flushing changes to persistent storage and forming new steady -synchronization point. +*Reasons why asynchronous mode isn't benchmarked here:* -So in async-write mode _libmdbx_ will always use new pages until memory is exhausted or `mdbx_env_sync()` is invoked. Total -disk usage will be almost the same as in sync-write mode. + 1. It doesn't make sense as it has to be done with DB engines, oriented + for keeping data in memory e.g. [Tarantool](https://tarantool.io/), + [Redis](https://redis.io/)), etc. -Current _libmdbx_ gives a choice of safe async-write mode (default) and `UTTERLY_NOSYNC` mode which may result in full DB -corruption during system crash as with LMDB. + 2. Performance gap is too high to compare in any meaningful way. -Next version of _libmdbx_ will create steady synchronization points automatically in async-write mode. + -------------------------------------------------------------------------------- -Improvements over LMDB -================================================ - -1. `LIFO RECLAIM` mode: - - The newest pages are picked for reuse instead of the oldest. - This allows to minimize reclaim loop and make it execution time independent of total page count. - - This results in OS kernel cache mechanisms working with maximum efficiency. - In case of using disk controllers or storages with - [BBWC](https://en.wikipedia.org/wiki/Disk_buffer#Write_acceleration) this may greatly improve - write performance. +### Read Scalability -2. `OOM-KICK` callback. +Summary performance with concurrent read/search queries in 1-2-4-8 +threads on 4 CPU cores machine. - `mdbx_env_set_oomfunc()` allows to set a callback, which will be called - in the event of memory exhausting during long-time read transaction. - Callback will be invoked with PID and pthread_id of offending thread as parameters. - Callback can do any of these things to remedy the problem: + - * wait for read transaction to finish normally; +-------------------------------------------------------------------------------- - * kill the offending process (signal 9), if separate process is doing long-time read; +### Sync-write mode - * abort or restart offending read transaction if it's running in sibling thread; + - Linear scale on left and dark rectangles mean arithmetic mean + transactions per second; - * abort current write transaction with returning error code. + - Logarithmic scale on right is in seconds and yellow intervals mean + execution time of transactions. Each interval shows minimal and maximum + execution time, cross marks standard deviation. -3. Guarantee of DB integrity in `WRITEMAP+MAPSYNC` mode: - > Current _libmdbx_ gives a choice of safe async-write mode (default) - > and `UTTERLY_NOSYNC` mode which may result in full - > DB corruption during system crash as with LMDB. For details see - > [Data safety in async-write mode](#data-safety-in-async-write-mode). +**10,000 transactions in sync-write mode**. In case of a crash all data +is consistent and state is right after last successful transaction. +[fdatasync](https://linux.die.net/man/2/fdatasync) syscall is used after +each write transaction in this mode. -4. Automatic creation of synchronization points (flush changes to persistent storage) - when changes reach set threshold (threshold can be set by `mdbx_env_set_syncbytes()`). +In the benchmark each transaction contains combined CRUD operations (2 +inserts, 1 read, 1 update, 1 delete). Benchmark starts on empty database +and after full run the database contains 10,000 small key-value records. -5. Ability to get how far current read-only snapshot is from latest version of the DB by `mdbx_txn_straggler()`. + -6. `mdbx_chk` tool for DB checking and `mdbx_env_pgwalk()` for page-walking all pages in DB. +-------------------------------------------------------------------------------- -7. Control over debugging and receiving of debugging messages via `mdbx_setup_debug()`. +### Lazy-write mode -8. Ability to assign up to 3 markers to commiting transaction with `mdbx_canary_put()` and then get them in read transaction - by `mdbx_canary_get()`. + - Linear scale on left and dark rectangles mean arithmetic mean of + thousands transactions per second; -9. Check if there is a row with data after current cursor position via `mdbx_cursor_eof()`. + - Logarithmic scale on right in seconds and yellow intervals mean + execution time of transactions. Each interval shows minimal and maximum + execution time, cross marks standard deviation. -10. Ability to explicitly request update of present record without creating new record. Implemented as `MDBX_CURRENT` flag - for `mdbx_put()`. +**100,000 transactions in lazy-write mode**. In case of a crash all data +is consistent and state is right after one of last transactions, but +transactions after it will be lost. Other DB engines use +[WAL](https://en.wikipedia.org/wiki/Write-ahead_logging) or transaction +journal for that, which in turn depends on order of operations in +journaled filesystem. _libmdbx_ doesn't use WAL and hands I/O operations +to filesystem and OS kernel (mmap). -11. Ability to update or delete record and get previous value via `mdbx_replace()` Also can update specific multi-value. +In the benchmark each transaction contains combined CRUD operations (2 +inserts, 1 read, 1 update, 1 delete). Benchmark starts on empty database +and after full run the database contains 100,000 small key-value +records. -12. Support for keys and values of zero length, including sorted duplicates. -13. Fixed `mdbx_cursor_count()`, which returns correct count of duplicated for all table types and any cursor position. + -14. Ability to open DB in exclusive mode with `MDBX_EXCLUSIVE` flag, e.g. for integrity check. +-------------------------------------------------------------------------------- -15. Ability to close DB in "dirty" state (without data flush and creation of steady synchronization point) - via `mdbx_env_close_ex()`. +### Async-write mode -16. Ability to get additional info, including number of the oldest snapshot of DB, which is used by one of the readers. - Implemented via `mdbx_env_info()`. + - Linear scale on left and dark rectangles mean arithmetic mean of + thousands transactions per second; -17. `mdbx_del()` doesn't ignore additional argument (specifier) `data` - for tables without duplicates (without flag `MDBX_DUPSORT`), if `data` is not zero then always uses it to verify - record, which is being deleted. + - Logarithmic scale on right in seconds and yellow intervals mean + execution time of transactions. Each interval shows minimal and maximum + execution time, cross marks standard deviation. -18. Ability to open dbi-table with simultaneous setup of comparators for keys and values, via `mdbx_dbi_open_ex()`. +**1,000,000 transactions in async-write mode**. In case of a crash all +data will be consistent and state will be right after one of last +transactions, but lost transaction count is much higher than in +lazy-write mode. All DB engines in this mode do as little writes as +possible on persistent storage. _libmdbx_ uses +[msync(MS_ASYNC)](https://linux.die.net/man/2/msync) in this mode. -19. Ability to find out if key or value is in dirty page. This may be useful to make a decision to avoid - excessive CoW before updates. Implemented via `mdbx_is_dirty()`. +In the benchmark each transaction contains combined CRUD operations (2 +inserts, 1 read, 1 update, 1 delete). Benchmark starts on empty database +and after full run the database contains 10,000 small key-value records. -20. Correct update of current record in `MDBX_CURRENT` mode of `mdbx_cursor_put()`, including sorted duplicated. + -21. All cursors in all read and write transactions can be reused by `mdbx_cursor_renew()` and MUST be freed explicitly. - > ## Caution, please pay attention! - > - > This is the only change of API, which changes semantics of cursor management - > and can lead to memory leaks on misuse. This is a needed change as it eliminates ambiguity - > which helps to avoid such errors as: - > - use-after-free; - > - double-free; - > - memory corruption and segfaults. +-------------------------------------------------------------------------------- -22. Additional error code `MDBX_EMULTIVAL`, which is returned by `mdbx_put()` and - `mdbx_replace()` in case is ambiguous update or delete. +### Cost comparison -23. Ability to get value by key and duplicates count by `mdbx_get_ex()`. +Summary of used resources during lazy-write mode benchmarks: -24. Functions `mdbx_cursor_on_first() and mdbx_cursor_on_last(), which allows to know if cursor is currently on first or - last position respectively. + - Read and write IOPS; -25. If read transaction is aborted via `mdbx_txn_abort()` or `mdbx_txn_reset()` then DBI-handles, which were opened in it, - aren't closed or deleted. This allows to avoid several types of hard-to-debug errors. + - Sum of user CPU time and sys CPU time; -26. Sequence generation via `mdbx_dbi_sequence()`. + - Used space on persistent storage after the test and closed DB, but not + waiting for the end of all internal housekeeping operations (LSM + compactification, etc). -27. Advanced dynamic control over DB size, including ability to choose page size via `mdbx_env_set_geometry()`, - including on Windows. +_ForestDB_ is excluded because benchmark showed it's resource +consumption for each resource (CPU, IOPS) much higher than other engines +which prevents to meaningfully compare it with them. -28. Three meta-pages instead of two, this allows to guarantee consistently update weak sync-points without risking to - corrupt last steady sync-point. +All benchmark data is gathered by +[getrusage()](http://man7.org/linux/man-pages/man2/getrusage.2.html) +syscall and by scanning data directory. -29. Automatic reclaim of freed pages to specific reserved space at the end of database file. This lowers amount of pages, - loaded to memory, used in update/flush loop. In fact _libmdbx_ constantly performs compactification of data, - but doesn't use additional resources for that. Space reclaim of DB and setup of database geometry parameters also decreases - size of the database on disk, including on Windows. + -------------------------------------------------------------------------------- @@ -474,16 +597,3 @@ Idx Name Size VMA LMA File off Algn CONTENTS, ALLOC, LOAD, READONLY, CODE ``` - -``` -$ gcc -v -Using built-in specs. -COLLECT_GCC=gcc -COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/7/lto-wrapper -OFFLOAD_TARGET_NAMES=nvptx-none -OFFLOAD_TARGET_DEFAULT=1 -Target: x86_64-linux-gnu -Configured with: ../src/configure -v --with-pkgversion='Ubuntu 7.2.0-8ubuntu3' --with-bugurl=file:///usr/share/doc/gcc-7/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++ --prefix=/usr --with-gcc-major-version-only --program-suffix=-7 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-libmpx --enable-plugin --enable-default-pie --with-system-zlib --with-target-system-zlib --enable-objc-gc=auto --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu -Thread model: posix -gcc version 7.2.0 (Ubuntu 7.2.0-8ubuntu3) -``` diff --git a/libs/libmdbx/src/TODO.md b/libs/libmdbx/src/TODO.md deleted file mode 100644 index 810b18dc4a..0000000000 --- a/libs/libmdbx/src/TODO.md +++ /dev/null @@ -1,89 +0,0 @@ -Допеределки -=========== -- [ ] Перевод mdbx-tools на С++ и сборка для Windows. -- [ ] Переход на CMake, замена заглушек mdbx_version и mdbx_build. -- [ ] Актуализация README.md -- [ ] Переход на C++11, добавление #pramga detect_mismatch(). -- [ ] Убрать MDB_DEBUG (всегда: логирование важный ситуаций и ошибок, опционально: включение ассертов и трассировка). -- [ ] Заменить mdbx_debug на mdbx_trace, и почистить... -- [ ] Заметить максимум assert() на mdbx_assert(env, ...). - -Качество и CI -============= -- [ ] Добавить в CI linux сборки для 32-битных таргетов. - -Доработки API -============= -- [ ] Поправить/Добавить описание нового API. -- [ ] Добавить возможность "подбора" режима для mdbx_env_open(). -- [ ] Переименовать в API: env->db, db->tbl. - -Тесты -===== -- [ ] Тестирование поддержки lockless-режима. -- [x] Додумать имя и размещение тестовой БД по-умолчанию. -- [ ] Реализовать cleanup в тесте. -- [ ] usage для теста. -- [ ] Логирование в файл, плюс более полный progress bar. -- [ ] Опция игнорирования (пропуска части теста) при переполнении БД. -- [ ] Базовый бенчмарк. - -Развитие -======== -- [ ] Отслеживание времени жизни DBI-хендлов. -- [ ] Отрефакторить mdbx_freelist_save(). -- [ ] Хранить "свободный хвост" не связанный с freeDB в META. -- [x] Возврат выделенных страниц в unallocated tail-pool. -- [ ] Валидатор страниц БД по номеру транзакции: - ~0 при переработке и номер транзакции при выделении, - проверять что этот номер больше головы реклайминга и не-больше текущей транзакции. -- [ ] Размещение overflow-pages в отдельном mmap/файле с собственной геометрией. -- [ ] Зафиксировать формат БД. -- [ ] Валидатор страниц по CRC32, плюс контроль номер транзакии под модулю 2^32. -- [ ] Валидатор страниц по t1ha c контролем снимков/версий БД на основе Merkle Tree. -- [ ] Возможность хранения ключей внутри data (libfptu). -- [ ] Асинхронная фиксация (https://github.com/leo-yuriev/libmdbx/issues/5). -- [ ] (Пере)Выделять память под IDL-списки с учетом реального кол-ва страниц, т.е. max(MDB_IDL_UM_MAX/MDB_IDL_UM_MAX, npages). - ------------------------------------------------------------------------ - -Сделано -======= -- [x] разделение errno и GetLastError(). -- [x] CI посредством AppVeyor. -- [x] тест конкурентного доступа. -- [x] тест основного функционала (заменить текущий треш). -- [x] uint32/uint64 в структурах. -- [x] Завершить переименование. -- [x] Макросы версионности, сделать как в fpta (cmake?). -- [x] Попробовать убрать yield (или что там с местом?). -- [x] trinity для copy/compaction. -- [x] trinity для mdbx_chk и mdbx_stat. -- [x] проверки с mdbx_meta_eq. -- [x] Не проверять режим при открытии в readonly. -- [x] Поправить выбор tail в mdbx_chk. -- [x] Там-же проверять позицию реклайминга. -- [x] поправить проблему открытия после READ-ONLY. -- [x] static-assertы на размер/выравнивание lck, meta и т.п. -- [x] Зачистить size_t. -- [x] Добавить локи вокруг dbi. -- [x] Привести в порядок volatile. -- [x] контроль meta.mapsize. -- [x] переработка формата: заголовки страниц, meta, clk... -- [x] зачистка Doxygen и бесполезных комментариев. -- [x] Добавить поле типа контрольной суммы. -- [x] Добавить поле/флаг размера pgno_t. -- [x] Поменять сигнатуры. -- [x] Добавить мета-страницы в coredump, проверить lck. -- [x] Сделать список для txnid_t, кода sizeof(txnid_t) > sizeof(pgno_t) и вернуть размер pgno_t. -- [x] Избавиться от умножения на размер страницы (заменить на сдвиг). -- [x] Устранение всех предупреждений (в том числе под Windows). -- [x] Добавить 'mti_reader_finished_flag'. -- [x] Погасить все level4-warnings от MSVC, включить /WX. -- [x] Проверка посредством Coverity с гашением всех дефектов. -- [x] Полная матрица Windows-сборок (2013/2015/2017). -- [x] Дать возможность задавать размер страницы при создании БД. -- [x] Изменение mapsize через API с блокировкой и увеличением txn. -- [x] Контроль размера страницы полного размера и кол-ва страниц при создании и обновлении. -- [x] Инкрементальный mmap. -- [x] Инкрементальное приращение размера (колбэк стратегии?). diff --git a/libs/libmdbx/src/mdbx.h b/libs/libmdbx/src/mdbx.h index 35faed8488..57efd875cf 100644 --- a/libs/libmdbx/src/mdbx.h +++ b/libs/libmdbx/src/mdbx.h @@ -924,7 +924,6 @@ LIBMDBX_API int mdbx_env_set_maxdbs(MDBX_env *env, MDBX_dbi dbs); * * Returns The maximum size of a key we can write. */ LIBMDBX_API int mdbx_env_get_maxkeysize(MDBX_env *env); -LIBMDBX_API int mdbx_get_maxkeysize(size_t pagesize); /* Set application information associated with the MDBX_env. * @@ -1697,6 +1696,13 @@ LIBMDBX_API int mdbx_is_dirty(const MDBX_txn *txn, const void *ptr); LIBMDBX_API int mdbx_dbi_sequence(MDBX_txn *txn, MDBX_dbi dbi, uint64_t *result, uint64_t increment); +LIBMDBX_API int mdbx_limits_pgsize_min(void); +LIBMDBX_API int mdbx_limits_pgsize_max(void); +LIBMDBX_API intptr_t mdbx_limits_dbsize_min(intptr_t pagesize); +LIBMDBX_API intptr_t mdbx_limits_dbsize_max(intptr_t pagesize); +LIBMDBX_API intptr_t mdbx_limits_keysize_max(intptr_t pagesize); +LIBMDBX_API intptr_t mdbx_limits_txnsize_max(intptr_t pagesize); + /*----------------------------------------------------------------------------*/ /* attribute support functions for Nexenta */ typedef uint_fast64_t mdbx_attr_t; diff --git a/libs/libmdbx/src/CMakeLists.txt b/libs/libmdbx/src/packages/rpm/CMakeLists.txt index b664075556..b664075556 100644 --- a/libs/libmdbx/src/CMakeLists.txt +++ b/libs/libmdbx/src/packages/rpm/CMakeLists.txt diff --git a/libs/libmdbx/src/build.sh b/libs/libmdbx/src/packages/rpm/build.sh index 5170882265..5170882265 100644 --- a/libs/libmdbx/src/build.sh +++ b/libs/libmdbx/src/packages/rpm/build.sh diff --git a/libs/libmdbx/src/package.sh b/libs/libmdbx/src/packages/rpm/package.sh index d7f9ab297a..d7f9ab297a 100644 --- a/libs/libmdbx/src/package.sh +++ b/libs/libmdbx/src/packages/rpm/package.sh diff --git a/libs/libmdbx/src/src/bits.h b/libs/libmdbx/src/src/bits.h index fca28e25e5..559435b49d 100644 --- a/libs/libmdbx/src/src/bits.h +++ b/libs/libmdbx/src/src/bits.h @@ -508,13 +508,7 @@ typedef MDBX_ID2 *MDBX_ID2L; /* PNL sizes - likely should be even bigger * limiting factors: sizeof(pgno_t), thread stack size */ -#define MDBX_PNL_LOGN 16 /* DB_SIZE is 2^16, UM_SIZE is 2^17 */ -#define MDBX_PNL_DB_SIZE (1 << MDBX_PNL_LOGN) -#define MDBX_PNL_UM_SIZE (1 << (MDBX_PNL_LOGN + 1)) - -#define MDBX_PNL_DB_MAX (MDBX_PNL_DB_SIZE - 1) -#define MDBX_PNL_UM_MAX (MDBX_PNL_UM_SIZE - 1) -#define MDBX_PNL_MAX (MAX_PAGENO / 4) +#define MDBX_LIST_MAX ((1 << 24) - 1) #define MDBX_PNL_SIZEOF(pl) (((pl)[0] + 1) * sizeof(pgno_t)) #define MDBX_PNL_IS_ZERO(pl) ((pl)[0] == 0) @@ -758,7 +752,7 @@ struct MDBX_env { MDBX_page *me_dpages; /* list of malloc'd blocks for re-use */ /* PNL of pages that became unused in a write txn */ MDBX_PNL me_free_pgs; - /* ID2L of pages written during a write txn. Length MDBX_PNL_UM_SIZE. */ + /* ID2L of pages written during a write txn. Length MDBX_LIST_MAX. */ MDBX_ID2L me_dirtylist; /* Number of freelist items that can fit in a single overflow page */ unsigned me_maxgc_ov1page; diff --git a/libs/libmdbx/src/src/mdbx.c b/libs/libmdbx/src/src/mdbx.c index f5b864595d..cafaefc19c 100644 --- a/libs/libmdbx/src/src/mdbx.c +++ b/libs/libmdbx/src/src/mdbx.c @@ -1,4 +1,4 @@ -/* +/* * Copyright 2015-2018 Leonid Yuriev <leo@yuriev.ru> * and other libmdbx authors: please see AUTHORS file. * All rights reserved. @@ -501,7 +501,7 @@ __cold void mdbx_rthc_remove(const mdbx_thread_key_t key) { * Allocates memory for an PNL of the given size. * Returns PNL on success, NULL on failure. */ static MDBX_PNL mdbx_pnl_alloc(size_t size) { - assert(size <= MDBX_PNL_MAX); + assert(size <= MDBX_LIST_MAX); MDBX_PNL pl = malloc((size + 2) * sizeof(pgno_t)); if (likely(pl)) { *pl++ = (pgno_t)size; @@ -544,7 +544,7 @@ static __inline void mdbx_pnl_xappend(MDBX_PNL pl, pgno_t id) { static bool mdbx_pnl_check(MDBX_PNL pl, bool allocated) { if (pl) { if (allocated) { - assert(pl[0] <= MDBX_PNL_MAX && pl[0] <= pl[-1]); + assert(pl[0] <= MDBX_LIST_MAX && pl[0] <= pl[-1]); } for (const pgno_t *ptr = pl + pl[0]; --ptr > pl;) { assert(MDBX_PNL_ORDERED(ptr[0], ptr[1])); @@ -678,12 +678,12 @@ static unsigned __hot mdbx_pnl_search(MDBX_PNL pnl, pgno_t id) { * [in,out] ppl Address of the PNL to shrink. */ static void mdbx_pnl_shrink(MDBX_PNL *ppl) { MDBX_PNL pl = *ppl - 1; - if (unlikely(*pl > MDBX_PNL_UM_MAX)) { - /* shrink to MDBX_PNL_UM_MAX */ - pl = realloc(pl, (MDBX_PNL_UM_MAX + 2) * sizeof(pgno_t)); + if (unlikely(*pl > MDBX_LIST_MAX)) { + /* shrink to MDBX_LIST_MAX */ + pl = realloc(pl, (MDBX_LIST_MAX + 2) * sizeof(pgno_t)); if (likely(pl)) { - *pl++ = MDBX_PNL_UM_MAX; - *ppl = pl; + *pl = MDBX_LIST_MAX; + *ppl = pl + 1; } } } @@ -692,29 +692,18 @@ static void mdbx_pnl_shrink(MDBX_PNL *ppl) { * Return the PNL to the size growed by given number. * [in,out] ppl Address of the PNL to grow. */ static int __must_check_result mdbx_pnl_grow(MDBX_PNL *ppl, size_t num) { - MDBX_PNL idn = *ppl - 1; - assert(idn[0] <= MDBX_PNL_MAX && idn[0] <= idn[-1]); - assert(num <= MDBX_PNL_MAX); - num += *idn; - if (unlikely(num > MDBX_PNL_MAX)) + MDBX_PNL pl = *ppl - 1; + assert(pl[1] <= MDBX_LIST_MAX && pl[1] <= pl[0]); + assert(num <= MDBX_LIST_MAX); + num += pl[0]; + if (unlikely(num > MDBX_LIST_MAX)) return MDBX_TXN_FULL; /* grow it */ - idn = realloc(idn, (num + 2) * sizeof(pgno_t)); - if (unlikely(!idn)) - return MDBX_ENOMEM; - *idn++ += (pgno_t)num; - *ppl = idn; - return MDBX_SUCCESS; -} - -static int __must_check_result mdbx_txl_grow(MDBX_TXL *ptr, size_t num) { - MDBX_TXL list = *ptr - 1; - /* grow it */ - list = realloc(list, ((size_t)*list + num + 2) * sizeof(txnid_t)); - if (unlikely(!list)) + pl = realloc(pl, (num + 2) * sizeof(pgno_t)); + if (unlikely(!pl)) return MDBX_ENOMEM; - *list++ += num; - *ptr = list; + *pl = (pgno_t)num; + *ppl = pl + 1; return MDBX_SUCCESS; } @@ -723,20 +712,20 @@ static int __must_check_result mdbx_txl_grow(MDBX_TXL *ptr, size_t num) { * [in] num Number of elements to make room for. * Returns 0 on success, MDBX_ENOMEM on failure. */ static int __must_check_result mdbx_pnl_need(MDBX_PNL *ppl, size_t num) { - MDBX_PNL pl = *ppl; - assert(pl[0] <= MDBX_PNL_MAX && pl[0] <= pl[-1]); - assert(num <= MDBX_PNL_MAX); - num += pl[0]; - if (unlikely(num > pl[-1])) { - if (unlikely(num > MDBX_PNL_MAX)) + MDBX_PNL pl = *ppl - 1; + assert(pl[1] <= MDBX_LIST_MAX && pl[1] <= pl[0]); + assert(num <= MDBX_LIST_MAX); + num += pl[1]; + if (unlikely(num > pl[0])) { + if (unlikely(num > MDBX_LIST_MAX)) return MDBX_TXN_FULL; num = (num + num / 4 + (256 + 2)) & ~255u; - num = (num < MDBX_PNL_MAX + 2) ? num : MDBX_PNL_MAX + 2; - pl = realloc(pl - 1, num * sizeof(pgno_t)); + num = (num < MDBX_LIST_MAX + 2) ? num : MDBX_LIST_MAX + 2; + pl = realloc(pl, num * sizeof(pgno_t)); if (unlikely(!pl)) return MDBX_ENOMEM; - *pl++ = (pgno_t)num - 2; - *ppl = pl; + *pl = (pgno_t)num - 2; + *ppl = pl + 1; } return MDBX_SUCCESS; } @@ -749,7 +738,7 @@ static int __must_check_result mdbx_pnl_append(MDBX_PNL *ppl, pgno_t id) { MDBX_PNL pl = *ppl; /* Too big? */ if (unlikely(pl[0] >= pl[-1])) { - int rc = mdbx_pnl_grow(ppl, MDBX_PNL_UM_MAX); + int rc = mdbx_pnl_grow(ppl, MDBX_LIST_MAX); if (unlikely(rc != MDBX_SUCCESS)) return rc; pl = *ppl; @@ -759,20 +748,6 @@ static int __must_check_result mdbx_pnl_append(MDBX_PNL *ppl, pgno_t id) { return MDBX_SUCCESS; } -static int __must_check_result mdbx_txl_append(MDBX_TXL *ptr, txnid_t id) { - MDBX_TXL list = *ptr; - /* Too big? */ - if (unlikely(list[0] >= list[-1])) { - int rc = mdbx_txl_grow(ptr, (size_t)list[0]); - if (unlikely(rc != MDBX_SUCCESS)) - return rc; - list = *ptr; - } - list[0]++; - list[list[0]] = id; - return MDBX_SUCCESS; -} - /* Append an PNL onto an PNL. * [in,out] ppl Address of the PNL to append to. * [in] app The PNL to append. @@ -792,21 +767,6 @@ static int __must_check_result mdbx_pnl_append_list(MDBX_PNL *ppl, return MDBX_SUCCESS; } -static int __must_check_result mdbx_txl_append_list(MDBX_TXL *ptr, - MDBX_TXL append) { - MDBX_TXL list = *ptr; - /* Too big? */ - if (unlikely(list[0] + append[0] >= list[-1])) { - int rc = mdbx_txl_grow(ptr, (size_t)append[0]); - if (unlikely(rc != MDBX_SUCCESS)) - return rc; - list = *ptr; - } - memcpy(&list[list[0] + 1], &append[1], (size_t)append[0] * sizeof(txnid_t)); - list[0] += append[0]; - return MDBX_SUCCESS; -} - /* Append an ID range onto an PNL. * [in,out] ppl Address of the PNL to append to. * [in] id The lowest ID to append. @@ -817,7 +777,7 @@ static int __must_check_result mdbx_pnl_append_range(MDBX_PNL *ppl, pgno_t id, pgno_t *pnl = *ppl, len = pnl[0]; /* Too big? */ if (unlikely(len + n > pnl[-1])) { - int rc = mdbx_pnl_grow(ppl, n | MDBX_PNL_UM_MAX); + int rc = mdbx_pnl_grow(ppl, n | MDBX_LIST_MAX); if (unlikely(rc != MDBX_SUCCESS)) return rc; pnl = *ppl; @@ -849,6 +809,57 @@ static void __hot mdbx_pnl_xmerge(MDBX_PNL pnl, MDBX_PNL merge) { assert(mdbx_pnl_check(pnl, true)); } +static int __must_check_result mdbx_txl_grow(MDBX_TXL *ptr, size_t num) { + MDBX_TXL list = *ptr - 1; + /* grow it */ + list = realloc(list, ((size_t)*list + num + 2) * sizeof(txnid_t)); + if (unlikely(!list)) + return MDBX_ENOMEM; + *list += num; + *ptr = list + 1; + return MDBX_SUCCESS; +} + +static int mdbx_txl_cmp(const void *pa, const void *pb) { + const txnid_t a = *(MDBX_TXL)pa; + const txnid_t b = *(MDBX_TXL)pb; + return mdbx_cmp2int(b, a); +} + +static void mdbx_txl_sort(MDBX_TXL ptr) { + /* LY: temporary */ + qsort(ptr + 1, (size_t)ptr[0], sizeof(*ptr), mdbx_txl_cmp); +} + +static int __must_check_result mdbx_txl_append(MDBX_TXL *ptr, txnid_t id) { + MDBX_TXL list = *ptr; + /* Too big? */ + if (unlikely(list[0] >= list[-1])) { + int rc = mdbx_txl_grow(ptr, (size_t)list[0]); + if (unlikely(rc != MDBX_SUCCESS)) + return rc; + list = *ptr; + } + list[0]++; + list[list[0]] = id; + return MDBX_SUCCESS; +} + +static int __must_check_result mdbx_txl_append_list(MDBX_TXL *ptr, + MDBX_TXL append) { + MDBX_TXL list = *ptr; + /* Too big? */ + if (unlikely(list[0] + append[0] >= list[-1])) { + int rc = mdbx_txl_grow(ptr, (size_t)append[0]); + if (unlikely(rc != MDBX_SUCCESS)) + return rc; + list = *ptr; + } + memcpy(&list[list[0] + 1], &append[1], (size_t)append[0] * sizeof(txnid_t)); + list[0] += append[0]; + return MDBX_SUCCESS; +} + /* Search for an ID in an ID2L. * [in] pnl The ID2L to search. * [in] id The ID to search for. @@ -900,10 +911,10 @@ static int __must_check_result mdbx_mid2l_insert(MDBX_ID2L pnl, MDBX_ID2 *id) { if (unlikely(x < 1)) return /* internal error */ MDBX_PROBLEM; - if (x <= pnl[0].mid && pnl[x].mid == id->mid) + if (unlikely(pnl[x].mid == id->mid && x <= pnl[0].mid)) return /* duplicate */ MDBX_PROBLEM; - if (unlikely(pnl[0].mid >= MDBX_PNL_UM_MAX)) + if (unlikely(pnl[0].mid >= MDBX_LIST_MAX)) return /* too big */ MDBX_TXN_FULL; /* insert id */ @@ -928,7 +939,7 @@ static int __must_check_result mdbx_mid2l_append(MDBX_ID2L pnl, MDBX_ID2 *id) { #endif /* Too big? */ - if (unlikely(pnl[0].mid >= MDBX_PNL_UM_MAX)) + if (unlikely(pnl[0].mid >= MDBX_LIST_MAX)) return /* too big */ MDBX_TXN_FULL; pnl[0].mid++; @@ -1698,7 +1709,7 @@ static int mdbx_page_spill(MDBX_cursor *m0, MDBX_val *key, MDBX_val *data) { return MDBX_SUCCESS; if (!txn->mt_spill_pages) { - txn->mt_spill_pages = mdbx_pnl_alloc(MDBX_PNL_UM_MAX); + txn->mt_spill_pages = mdbx_pnl_alloc(MDBX_LIST_MAX); if (unlikely(!txn->mt_spill_pages)) return MDBX_ENOMEM; } else { @@ -1723,8 +1734,8 @@ static int mdbx_page_spill(MDBX_cursor *m0, MDBX_val *key, MDBX_val *data) { * of those pages will need to be used again. So now we spill only 1/8th * of the dirty pages. Testing revealed this to be a good tradeoff, * better than 1/2, 1/4, or 1/10. */ - if (need < MDBX_PNL_UM_MAX / 8) - need = MDBX_PNL_UM_MAX / 8; + if (need < MDBX_LIST_MAX / 8) + need = MDBX_LIST_MAX / 8; /* Save the page IDs of all the pages we're flushing */ /* flush from the tail forward, this saves a lot of shifting later on. */ @@ -2406,7 +2417,7 @@ static int mdbx_page_alloc(MDBX_cursor *mc, unsigned num, MDBX_page **mp, } /* Don't try to coalesce too much. */ - if (repg_len > MDBX_PNL_UM_SIZE / 2) + if (unlikely(repg_len > MDBX_LIST_MAX / 2)) break; if (flags & MDBX_COALESCE) { if (repg_len /* current size */ >= env->me_maxgc_ov1page || @@ -2709,7 +2720,7 @@ static int mdbx_page_touch(MDBX_cursor *mc) { } mdbx_debug("clone db %d page %" PRIaPGNO, DDBI(mc), mp->mp_pgno); - mdbx_cassert(mc, dl[0].mid < MDBX_PNL_UM_MAX); + mdbx_cassert(mc, dl[0].mid < MDBX_LIST_MAX); /* No - copy it */ np = mdbx_page_malloc(txn, 1); if (unlikely(!np)) { @@ -3078,7 +3089,7 @@ static int mdbx_txn_renew0(MDBX_txn *txn, unsigned flags) { txn->mt_child = NULL; txn->mt_loose_pages = NULL; txn->mt_loose_count = 0; - txn->mt_dirtyroom = MDBX_PNL_UM_MAX; + txn->mt_dirtyroom = MDBX_LIST_MAX; txn->mt_rw_dirtylist = env->me_dirtylist; txn->mt_rw_dirtylist[0].mid = 0; txn->mt_befree_pages = env->me_free_pgs; @@ -3231,9 +3242,9 @@ int mdbx_txn_begin(MDBX_env *env, MDBX_txn *parent, unsigned flags, unsigned i; txn->mt_cursors = (MDBX_cursor **)(txn->mt_dbs + env->me_maxdbs); txn->mt_dbiseqs = parent->mt_dbiseqs; - txn->mt_rw_dirtylist = malloc(sizeof(MDBX_ID2) * MDBX_PNL_UM_SIZE); + txn->mt_rw_dirtylist = malloc(sizeof(MDBX_ID2) * (MDBX_LIST_MAX + 1)); if (!txn->mt_rw_dirtylist || - !(txn->mt_befree_pages = mdbx_pnl_alloc(MDBX_PNL_UM_MAX))) { + !(txn->mt_befree_pages = mdbx_pnl_alloc(MDBX_LIST_MAX))) { free(txn->mt_rw_dirtylist); free(txn); return MDBX_ENOMEM; @@ -3528,7 +3539,7 @@ static int mdbx_update_gc(MDBX_txn *txn) { /* env->me_reclaimed_pglist[] can grow and shrink during this call. * env->me_last_reclaimed and txn->mt_befree_pages[] can only grow. * Page numbers cannot disappear from txn->mt_befree_pages[]. */ - MDBX_env *env = txn->mt_env; + MDBX_env *const env = txn->mt_env; const bool lifo = (env->me_flags & MDBX_LIFORECLAIM) != 0; MDBX_cursor mc; @@ -3545,17 +3556,18 @@ static int mdbx_update_gc(MDBX_txn *txn) { retry: mdbx_trace(" >> restart"); mdbx_tassert(txn, mdbx_pnl_check(env->me_reclaimed_pglist, true)); + unsigned placed = 0, cleaned_gc_slot = 0, reused_gc_slots = 0, + filled_gc_slot = ~0u; + txnid_t cleaned_gc_id = 0, head_gc_id = env->me_last_reclaimed + ? env->me_last_reclaimed + : ~(txnid_t)0; + if (unlikely(/* paranoia */ ++loop > 42)) { mdbx_error("too more loops %u, bailout", loop); rc = MDBX_PROBLEM; goto bailout; } - unsigned placed = 0, cleaned_gc_slot = 0, reused_gc_slot = 0, - filled_gc_slot = ~0u; - txnid_t cleaned_gc_id = 0, - head_gc_id = lifo ? *env->me_oldest : env->me_last_reclaimed; - while (1) { /* Come back here after each Put() in case befree-list changed */ MDBX_val key, data; @@ -3573,7 +3585,6 @@ retry: goto bailout; cleaned_gc_id = head_gc_id = *(txnid_t *)key.iov_base; mdbx_tassert(txn, cleaned_gc_id < *env->me_oldest); - placed = 0; mdbx_tassert(txn, cleaned_gc_id <= env->me_last_reclaimed); mc.mc_flags |= C_RECLAIMING; mdbx_trace("%s.cleanup-reclaimed-id %" PRIaTXN, dbg_prefix_mode, @@ -3582,31 +3593,37 @@ retry: mc.mc_flags ^= C_RECLAIMING; if (unlikely(rc != MDBX_SUCCESS)) goto bailout; + placed = 0; } - } else if (txn->mt_lifo_reclaimed) { + } else if (txn->mt_lifo_reclaimed && + cleaned_gc_slot < txn->mt_lifo_reclaimed[0]) { /* LY: cleanup reclaimed records. */ - while (cleaned_gc_slot < txn->mt_lifo_reclaimed[0]) { + do { cleaned_gc_id = txn->mt_lifo_reclaimed[++cleaned_gc_slot]; + assert(cleaned_gc_slot > 0 && cleaned_gc_id < *env->me_oldest); head_gc_id = (head_gc_id > cleaned_gc_id) ? cleaned_gc_id : head_gc_id; key.iov_base = &cleaned_gc_id; key.iov_len = sizeof(cleaned_gc_id); rc = mdbx_cursor_get(&mc, &key, NULL, MDBX_SET); - if (likely(rc != MDBX_NOTFOUND)) { - if (unlikely(rc != MDBX_SUCCESS)) - goto bailout; - rc = mdbx_prep_backlog(txn, &mc); - if (unlikely(rc != MDBX_SUCCESS)) - goto bailout; - mdbx_tassert(txn, cleaned_gc_id < *env->me_oldest); - mc.mc_flags |= C_RECLAIMING; - mdbx_trace("%s.cleanup-reclaimed-id [%u]%" PRIaTXN, dbg_prefix_mode, - cleaned_gc_slot, cleaned_gc_id); - rc = mdbx_cursor_del(&mc, 0); - mc.mc_flags ^= C_RECLAIMING; - if (unlikely(rc != MDBX_SUCCESS)) - goto bailout; - } - } + if (rc == MDBX_NOTFOUND) + continue; + if (unlikely(rc != MDBX_SUCCESS)) + goto bailout; + rc = mdbx_prep_backlog(txn, &mc); + if (unlikely(rc != MDBX_SUCCESS)) + goto bailout; + mdbx_tassert(txn, cleaned_gc_id < *env->me_oldest); + mc.mc_flags |= C_RECLAIMING; + mdbx_trace("%s.cleanup-reclaimed-id [%u]%" PRIaTXN, dbg_prefix_mode, + cleaned_gc_slot, cleaned_gc_id); + rc = mdbx_cursor_del(&mc, 0); + mc.mc_flags ^= C_RECLAIMING; + if (unlikely(rc != MDBX_SUCCESS)) + goto bailout; + } while (cleaned_gc_slot < txn->mt_lifo_reclaimed[0]); + mdbx_txl_sort(txn->mt_lifo_reclaimed); + assert(txn->mt_lifo_reclaimed[0] == 0 || + txn->mt_lifo_reclaimed[txn->mt_lifo_reclaimed[0]] == head_gc_id); } // handle loose pages - put ones into the reclaimed- or befree-list @@ -3737,21 +3754,30 @@ retry: // handle reclaimed and loost pages - merge and store both into gc mdbx_tassert(txn, mdbx_pnl_check(env->me_reclaimed_pglist, true)); mdbx_tassert(txn, txn->mt_loose_count == 0); + + mdbx_trace(" >> reserving"); const unsigned amount = env->me_reclaimed_pglist ? env->me_reclaimed_pglist[0] : 0; const unsigned left = amount - placed; - mdbx_trace("%s: amount %u, placed %d, left %d", dbg_prefix_mode, amount, placed, (int)left); if (0 >= (int)left) break; - mdbx_trace(" >> reserving"); txnid_t reservation_gc_id; - const unsigned lifo_gc_slots = - txn->mt_lifo_reclaimed ? (unsigned)txn->mt_lifo_reclaimed[0] : 0; if (lifo) { - if (reused_gc_slot >= lifo_gc_slots) { + assert(txn->mt_lifo_reclaimed != NULL); + if (unlikely(!txn->mt_lifo_reclaimed)) { + txn->mt_lifo_reclaimed = mdbx_txl_alloc(); + if (unlikely(!txn->mt_lifo_reclaimed)) { + rc = MDBX_ENOMEM; + goto bailout; + } + } + + if (head_gc_id > 1 && txn->mt_lifo_reclaimed[0] < INT16_MAX && + left > ((unsigned)txn->mt_lifo_reclaimed[0] - reused_gc_slots) * + env->me_maxgc_ov1page) { /* LY: need just a txn-id for save page list. */ rc = mdbx_page_alloc(&mc, 0, NULL, MDBX_ALLOC_GC | MDBX_ALLOC_KICK); if (likely(rc == MDBX_SUCCESS)) @@ -3761,58 +3787,101 @@ retry: /* LY: other troubles... */ goto bailout; - if (unlikely(!txn->mt_lifo_reclaimed)) { - txn->mt_lifo_reclaimed = mdbx_txl_alloc(); - if (unlikely(!txn->mt_lifo_reclaimed)) { - rc = MDBX_ENOMEM; - goto bailout; - } - } /* LY: freedb is empty, will look any free txn-id in high2low order. */ - rc = mdbx_txl_append(&txn->mt_lifo_reclaimed, --head_gc_id); - if (unlikely(rc != MDBX_SUCCESS)) - goto bailout; - cleaned_gc_slot += 1 /* mark GC cleanup is not needed. */; - - mdbx_trace("%s: append @%" PRIaTXN - " to lifo-reclaimed, cleaned-gc-slot = %u", - dbg_prefix_mode, head_gc_id, cleaned_gc_slot); - } - mdbx_tassert(txn, txn->mt_lifo_reclaimed != NULL); - reservation_gc_id = txn->mt_lifo_reclaimed[++reused_gc_slot]; + do { + --head_gc_id; + assert(txn->mt_lifo_reclaimed[txn->mt_lifo_reclaimed[0]] > + head_gc_id); + rc = mdbx_txl_append(&txn->mt_lifo_reclaimed, head_gc_id); + if (unlikely(rc != MDBX_SUCCESS)) + goto bailout; + cleaned_gc_slot += 1 /* mark GC cleanup is not needed. */; + + mdbx_trace("%s: append @%" PRIaTXN + " to lifo-reclaimed, cleaned-gc-slot = %u", + dbg_prefix_mode, head_gc_id, cleaned_gc_slot); + } while (head_gc_id > 1 && txn->mt_lifo_reclaimed[0] < INT16_MAX && + left > + ((unsigned)txn->mt_lifo_reclaimed[0] - reused_gc_slots) * + env->me_maxgc_ov1page); + } + + if ((unsigned)txn->mt_lifo_reclaimed[0] <= reused_gc_slots) { + mdbx_notice("** restart: reserve depleted (reused_gc_slot %u >= " + "lifo_reclaimed %u" PRIaTXN, + reused_gc_slots, (unsigned)txn->mt_lifo_reclaimed[0]); + goto retry; + } + const unsigned i = (unsigned)txn->mt_lifo_reclaimed[0] - reused_gc_slots; + assert(i > 0 && i <= txn->mt_lifo_reclaimed[0]); + reservation_gc_id = txn->mt_lifo_reclaimed[i]; mdbx_trace("%s: take @%" PRIaTXN " from lifo-reclaimed[%u]", - dbg_prefix_mode, reservation_gc_id, reused_gc_slot); - head_gc_id = - (head_gc_id > reservation_gc_id) ? reservation_gc_id : head_gc_id; + dbg_prefix_mode, reservation_gc_id, i); } else { mdbx_tassert(txn, txn->mt_lifo_reclaimed == NULL); - reused_gc_slot++ /* just count reserved records */; reservation_gc_id = head_gc_id--; mdbx_trace("%s: take @%" PRIaTXN " from head-gc-id", dbg_prefix_mode, reservation_gc_id); } - mdbx_trace("%s: head_gc_id %" PRIaTXN - ", reused_gc_slot %u, lifo_gc_slots %u, reservation-id " + ++reused_gc_slots; + assert(txn->mt_lifo_reclaimed == NULL || + txn->mt_lifo_reclaimed[0] <= INT16_MAX); + unsigned chunk = left; + if (unlikely(chunk > env->me_maxgc_ov1page)) { + const unsigned avail_gs_slots = + lifo ? (unsigned)txn->mt_lifo_reclaimed[0] - reused_gc_slots + : (head_gc_id < INT16_MAX) ? (unsigned)head_gc_id : INT16_MAX; + if (avail_gs_slots > 1) { + if (chunk < env->me_maxgc_ov1page * 2) + chunk /= 2; + else { + const unsigned threshold = env->me_maxgc_ov1page * avail_gs_slots; + if (left < threshold) + chunk = env->me_maxgc_ov1page; + else { + const unsigned tail = left - threshold + env->me_maxgc_ov1page + 1; + unsigned span = 1; + unsigned avail = (unsigned)((pgno2bytes(env, span) - PAGEHDRSZ) / + sizeof(pgno_t)) /*- 1 + span */; + if (tail > avail) { + for (unsigned i = env->me_reclaimed_pglist[0] - span; i > 0; + --i) { + if (MDBX_PNL_ASCENDING + ? (env->me_reclaimed_pglist[i] + span) + : (env->me_reclaimed_pglist[i] - span) == + env->me_reclaimed_pglist[i + span]) { + span += 1; + avail = (unsigned)((pgno2bytes(env, span) - PAGEHDRSZ) / + sizeof(pgno_t)) - + 1 + span; + if (avail >= tail) + break; + } + } + } + + chunk = (avail >= tail) + ? tail - span + : (avail_gs_slots > 3 && reused_gc_slots < 42) + ? avail - span + : tail; + } + } + } + } + assert(chunk > 0); + + mdbx_trace("%s: head_gc_id %" PRIaTXN ", reused_gc_slot %u, reservation-id " "%" PRIaTXN, - dbg_prefix_mode, head_gc_id, reused_gc_slot, lifo_gc_slots, - reservation_gc_id); - - const bool no_slots_more = - head_gc_id < 2 && (!lifo || reused_gc_slot >= lifo_gc_slots); - const unsigned chunk = - (left < env->me_maxgc_ov1page || no_slots_more) - ? left - : (left < env->me_maxgc_ov1page * 2) - ? /* the half to each of the last two chunks */ left / 2 - : env->me_maxgc_ov1page; - - mdbx_trace("%s: chunk %u, no_slots_more %s, gc-per-ovpage %u", - dbg_prefix_mode, chunk, no_slots_more ? "yes" : "no", + dbg_prefix_mode, head_gc_id, reused_gc_slots, reservation_gc_id); + + mdbx_trace("%s: chunk %u, gc-per-ovpage %u", dbg_prefix_mode, chunk, env->me_maxgc_ov1page); mdbx_tassert(txn, reservation_gc_id < *env->me_oldest); - if (unlikely(reservation_gc_id < 1)) { + if (unlikely(reservation_gc_id < 1 || + reservation_gc_id >= *env->me_oldest)) { /* LY: not any txn in the past of freedb. */ rc = MDBX_PROBLEM; goto bailout; @@ -3841,7 +3910,9 @@ retry: mdbx_trace(" >> filling"); /* Fill in the reserved records */ - filled_gc_slot = reused_gc_slot; + filled_gc_slot = txn->mt_lifo_reclaimed + ? (unsigned)txn->mt_lifo_reclaimed[0] - reused_gc_slots + : reused_gc_slots; rc = MDBX_SUCCESS; mdbx_tassert(txn, mdbx_pnl_check(env->me_reclaimed_pglist, true)); if (env->me_reclaimed_pglist && env->me_reclaimed_pglist[0]) { @@ -3867,8 +3938,7 @@ retry: if (txn->mt_lifo_reclaimed == nullptr) { mdbx_tassert(txn, lifo == 0); fill_gc_id = *(txnid_t *)key.iov_base; - if (filled_gc_slot-- /* just countdown reserved records */ == 0 || - fill_gc_id > env->me_last_reclaimed) { + if (filled_gc_slot-- == 0 || fill_gc_id > env->me_last_reclaimed) { mdbx_notice( "** restart: reserve depleted (filled_slot %u, fill_id %" PRIaTXN " > last_reclaimed %" PRIaTXN, @@ -3877,15 +3947,15 @@ retry: } } else { mdbx_tassert(txn, lifo != 0); - if (filled_gc_slot == 0) { - mdbx_notice("** restart: reserve depleted (filled_slot == 0)"); + if (++filled_gc_slot > (unsigned)txn->mt_lifo_reclaimed[0]) { + mdbx_notice("** restart: reserve depleted (filled_gc_slot %u > " + "lifo_reclaimed %u" PRIaTXN, + filled_gc_slot, (unsigned)txn->mt_lifo_reclaimed[0]); goto retry; } - mdbx_tassert(txn, filled_gc_slot > 0 && - filled_gc_slot <= txn->mt_lifo_reclaimed[0]); - fill_gc_id = txn->mt_lifo_reclaimed[filled_gc_slot--]; + fill_gc_id = txn->mt_lifo_reclaimed[filled_gc_slot]; mdbx_trace("%s.seek-reservaton @%" PRIaTXN " at lifo_reclaimed[%u]", - dbg_prefix_mode, fill_gc_id, (unsigned)filled_gc_slot); + dbg_prefix_mode, fill_gc_id, filled_gc_slot); key.iov_base = &fill_gc_id; key.iov_len = sizeof(fill_gc_id); rc = mdbx_cursor_get(&mc, &key, &data, MDBX_SET); @@ -3941,17 +4011,17 @@ retry: } mdbx_tassert(txn, rc == MDBX_SUCCESS); - if (txn->mt_lifo_reclaimed) { - mdbx_tassert(txn, cleaned_gc_slot == txn->mt_lifo_reclaimed[0]); - if (unlikely(filled_gc_slot != 0)) { - mdbx_notice("** restart: reserve excess (filled-slot %u > 0)", - filled_gc_slot); - goto retry; - } + if (unlikely( + filled_gc_slot != + (txn->mt_lifo_reclaimed ? (unsigned)txn->mt_lifo_reclaimed[0] : 0))) { + mdbx_notice("** restart: reserve excess (filled-slot %u)", filled_gc_slot); + goto retry; } bailout: if (txn->mt_lifo_reclaimed) { + mdbx_tassert(txn, rc != MDBX_SUCCESS || + cleaned_gc_slot == txn->mt_lifo_reclaimed[0]); txn->mt_lifo_reclaimed[0] = 0; if (txn != env->me_txn0) { mdbx_txl_free(txn->mt_lifo_reclaimed); @@ -4243,7 +4313,7 @@ int mdbx_txn_commit(MDBX_txn *txn) { } } } else { /* Simplify the above for single-ancestor case */ - len = MDBX_PNL_UM_MAX - txn->mt_dirtyroom; + len = MDBX_LIST_MAX - txn->mt_dirtyroom; } /* Merge our dirty list with parent's */ y = src[0].mid; @@ -4935,18 +5005,6 @@ int __cold mdbx_env_get_maxkeysize(MDBX_env *env) { #define mdbx_maxgc_ov1page(pagesize) \ (((pagesize)-PAGEHDRSZ) / sizeof(pgno_t) - 1) -int mdbx_get_maxkeysize(size_t pagesize) { - if (pagesize == 0) - pagesize = mdbx_syspagesize(); - - intptr_t nodemax = mdbx_nodemax(pagesize); - if (nodemax < 0) - return -MDBX_EINVAL; - - intptr_t maxkey = mdbx_maxkey(nodemax); - return (maxkey > 0 && maxkey < INT_MAX) ? (int)maxkey : -MDBX_EINVAL; -} - static void __cold mdbx_setup_pagesize(MDBX_env *env, const size_t pagesize) { STATIC_ASSERT(SSIZE_MAX > MAX_MAPSIZE); STATIC_ASSERT(MIN_PAGESIZE > sizeof(MDBX_page)); @@ -4956,9 +5014,9 @@ static void __cold mdbx_setup_pagesize(MDBX_env *env, const size_t pagesize) { env->me_psize = (unsigned)pagesize; STATIC_ASSERT(mdbx_maxgc_ov1page(MIN_PAGESIZE) > 42); - STATIC_ASSERT(mdbx_maxgc_ov1page(MAX_PAGESIZE) < MDBX_PNL_DB_MAX); + STATIC_ASSERT(mdbx_maxgc_ov1page(MAX_PAGESIZE) < MDBX_LIST_MAX); const intptr_t maxgc_ov1page = (pagesize - PAGEHDRSZ) / sizeof(pgno_t) - 1; - mdbx_ensure(env, maxgc_ov1page > 42 && maxgc_ov1page < MDBX_PNL_DB_MAX); + mdbx_ensure(env, maxgc_ov1page > 42 && maxgc_ov1page < MDBX_LIST_MAX); env->me_maxgc_ov1page = (unsigned)maxgc_ov1page; STATIC_ASSERT(mdbx_nodemax(MIN_PAGESIZE) > 42); @@ -5871,8 +5929,8 @@ int __cold mdbx_env_open(MDBX_env *env, const char *path, unsigned flags, flags &= ~(MDBX_WRITEMAP | MDBX_MAPASYNC | MDBX_NOSYNC | MDBX_NOMETASYNC | MDBX_COALESCE | MDBX_LIFORECLAIM | MDBX_NOMEMINIT); } else { - if (!((env->me_free_pgs = mdbx_pnl_alloc(MDBX_PNL_UM_MAX)) && - (env->me_dirtylist = calloc(MDBX_PNL_UM_SIZE, sizeof(MDBX_ID2))))) + if (!((env->me_free_pgs = mdbx_pnl_alloc(MDBX_LIST_MAX)) && + (env->me_dirtylist = calloc(MDBX_LIST_MAX + 1, sizeof(MDBX_ID2))))) rc = MDBX_ENOMEM; } @@ -7893,7 +7951,8 @@ int mdbx_cursor_put(MDBX_cursor *mc, MDBX_val *key, MDBX_val *data, ovpages = omp->mp_pages; /* Is the ov page large enough? */ - if (ovpages >= dpages) { + if (ovpages == + /* LY: add configuragle theshold to keep reserve space */ dpages) { if (!(omp->mp_flags & P_DIRTY) && (level || (env->me_flags & MDBX_WRITEMAP))) { rc = mdbx_page_unspill(mc->mc_txn, omp, &omp); @@ -12325,6 +12384,58 @@ int mdbx_dbi_sequence(MDBX_txn *txn, MDBX_dbi dbi, uint64_t *result, } /*----------------------------------------------------------------------------*/ + +__cold intptr_t mdbx_limits_keysize_max(intptr_t pagesize) { + if (pagesize < 1) + pagesize = (intptr_t)mdbx_syspagesize(); + else if (unlikely(pagesize < (intptr_t)MIN_PAGESIZE || + pagesize > (intptr_t)MAX_PAGESIZE || + !mdbx_is_power2((size_t)pagesize))) + return -MDBX_EINVAL; + + return mdbx_maxkey(mdbx_nodemax(pagesize)); +} + +__cold int mdbx_limits_pgsize_min(void) { return MIN_PAGESIZE; } + +__cold int mdbx_limits_pgsize_max(void) { return MAX_PAGESIZE; } + +__cold intptr_t mdbx_limits_dbsize_min(intptr_t pagesize) { + if (pagesize < 1) + pagesize = (intptr_t)mdbx_syspagesize(); + else if (unlikely(pagesize < (intptr_t)MIN_PAGESIZE || + pagesize > (intptr_t)MAX_PAGESIZE || + !mdbx_is_power2((size_t)pagesize))) + return -MDBX_EINVAL; + + return MIN_PAGENO * pagesize; +} + +__cold intptr_t mdbx_limits_dbsize_max(intptr_t pagesize) { + if (pagesize < 1) + pagesize = (intptr_t)mdbx_syspagesize(); + else if (unlikely(pagesize < (intptr_t)MIN_PAGESIZE || + pagesize > (intptr_t)MAX_PAGESIZE || + !mdbx_is_power2((size_t)pagesize))) + return -MDBX_EINVAL; + + const uint64_t limit = MAX_PAGENO * (uint64_t)pagesize; + return (limit < (intptr_t)MAX_MAPSIZE) ? (intptr_t)limit + : (intptr_t)MAX_PAGESIZE; +} + +__cold intptr_t mdbx_limits_txnsize_max(intptr_t pagesize) { + if (pagesize < 1) + pagesize = (intptr_t)mdbx_syspagesize(); + else if (unlikely(pagesize < (intptr_t)MIN_PAGESIZE || + pagesize > (intptr_t)MAX_PAGESIZE || + !mdbx_is_power2((size_t)pagesize))) + return -MDBX_EINVAL; + + return pagesize * (MDBX_LIST_MAX - 1); +} + +/*----------------------------------------------------------------------------*/ /* attribute support functions for Nexenta */ static __inline int mdbx_attr_peek(MDBX_val *data, mdbx_attr_t *attrptr) { diff --git a/libs/libmdbx/src/src/tools/mdbx_chk.c b/libs/libmdbx/src/src/tools/mdbx_chk.c index 772102ccb6..8fec23e3a8 100644 --- a/libs/libmdbx/src/src/tools/mdbx_chk.c +++ b/libs/libmdbx/src/src/tools/mdbx_chk.c @@ -340,12 +340,16 @@ static int handle_freedb(const uint64_t record_number, const MDBX_val *key, data->iov_len); else { const pgno_t number = *iptr++; - if (number < 1 || number > MDBX_PNL_MAX) + if (number < 1 || number > MDBX_LIST_MAX) problem_add("entry", record_number, "wrong idl length", "%" PRIiPTR "", number); - else if ((number + 1) * sizeof(pgno_t) != data->iov_len) - problem_add("entry", record_number, "mismatch idl length", - "%" PRIuSIZE " != %" PRIuSIZE "", + else if ((number + 1) * sizeof(pgno_t) > data->iov_len) + problem_add("entry", record_number, "trimmed idl", + "%" PRIuSIZE " > %" PRIuSIZE " (corruption)", + (number + 1) * sizeof(pgno_t), data->iov_len); + else if ((number + 1) * sizeof(pgno_t) < data->iov_len) + problem_add("entry", record_number, "extra idl space", + "%" PRIuSIZE " < %" PRIuSIZE " (minor, not a trouble)", (number + 1) * sizeof(pgno_t), data->iov_len); else { freedb_pages += number; diff --git a/libs/libmdbx/src/test/config.cc b/libs/libmdbx/src/test/config.cc index cbff68ce4e..c17c0d71e0 100644 --- a/libs/libmdbx/src/test/config.cc +++ b/libs/libmdbx/src/test/config.cc @@ -43,6 +43,11 @@ bool parse_option(int argc, char *const argv[], int &narg, const char *option, if (narg + 1 < argc && strncmp("--", argv[narg + 1], 2) != 0) { *value = argv[narg + 1]; + if (strcmp(*value, "default") == 0) { + if (!default_value) + failure("Option '--%s' doen't accept default value\n", option); + *value = default_value; + } ++narg; return true; } @@ -57,9 +62,15 @@ bool parse_option(int argc, char *const argv[], int &narg, const char *option, bool parse_option(int argc, char *const argv[], int &narg, const char *option, std::string &value, bool allow_empty) { + return parse_option(argc, argv, narg, option, value, allow_empty, + allow_empty ? "" : nullptr); +} + +bool parse_option(int argc, char *const argv[], int &narg, const char *option, + std::string &value, bool allow_empty, + const char *default_value) { const char *value_cstr; - if (!parse_option(argc, argv, narg, option, &value_cstr, - allow_empty ? "" : nullptr)) + if (!parse_option(argc, argv, narg, option, &value_cstr, default_value)) return false; if (!allow_empty && strlen(value_cstr) == 0) @@ -75,7 +86,7 @@ bool parse_option(int argc, char *const argv[], int &narg, const char *option, if (!parse_option(argc, argv, narg, option, &list)) return false; - mask = 0; + unsigned clear = 0; while (*list) { if (*list == ',' || *list == ' ' || *list == '\t') { ++list; @@ -83,14 +94,21 @@ bool parse_option(int argc, char *const argv[], int &narg, const char *option, } const char *const comma = strchr(list, ','); + const bool strikethrough = *list == '-' || *list == '~'; + if (strikethrough || *list == '+') + ++list; + else + mask = clear; const size_t len = (comma) ? comma - list : strlen(list); const option_verb *scan = verbs; + while (true) { if (!scan->verb) failure("Unknown verb '%.*s', for option '==%s'\n", (int)len, list, option); if (strlen(scan->verb) == len && strncmp(list, scan->verb, len) == 0) { - mask |= scan->mask; + mask = strikethrough ? mask & ~scan->mask : mask | scan->mask; + clear = strikethrough ? clear & ~scan->mask : clear | scan->mask; list += len; break; } @@ -103,15 +121,36 @@ bool parse_option(int argc, char *const argv[], int &narg, const char *option, bool parse_option(int argc, char *const argv[], int &narg, const char *option, uint64_t &value, const scale_mode scale, - const uint64_t minval, const uint64_t maxval) { + const uint64_t minval, const uint64_t maxval, + const uint64_t default_value) { const char *value_cstr; if (!parse_option(argc, argv, narg, option, &value_cstr)) return false; + if (default_value && strcmp(value_cstr, "default") == 0) { + value = default_value; + return true; + } + + if (strcmp(value_cstr, "min") == 0 || strcmp(value_cstr, "minimal") == 0) { + value = minval; + return true; + } + + if (strcmp(value_cstr, "max") == 0 || strcmp(value_cstr, "maximal") == 0) { + value = maxval; + return true; + } + char *suffix = nullptr; errno = 0; - unsigned long raw = strtoul(value_cstr, &suffix, 0); + unsigned long long raw = strtoull(value_cstr, &suffix, 0); + if ((suffix && *suffix) || errno) { + suffix = nullptr; + errno = 0; + raw = strtoull(value_cstr, &suffix, 10); + } if (errno) failure("Option '--%s' expects a numeric value (%s)\n", option, test_strerror(errno)); @@ -167,28 +206,58 @@ bool parse_option(int argc, char *const argv[], int &narg, const char *option, bool parse_option(int argc, char *const argv[], int &narg, const char *option, unsigned &value, const scale_mode scale, - const unsigned minval, const unsigned maxval) { + const unsigned minval, const unsigned maxval, + const unsigned default_value) { uint64_t huge; - if (!parse_option(argc, argv, narg, option, huge, scale, minval, maxval)) + if (!parse_option(argc, argv, narg, option, huge, scale, minval, maxval, + default_value)) return false; value = (unsigned)huge; return true; } bool parse_option(int argc, char *const argv[], int &narg, const char *option, - uint8_t &value, const uint8_t minval, const uint8_t maxval) { + uint8_t &value, const uint8_t minval, const uint8_t maxval, + const uint8_t default_value) { uint64_t huge; - if (!parse_option(argc, argv, narg, option, huge, no_scale, minval, maxval)) + if (!parse_option(argc, argv, narg, option, huge, no_scale, minval, maxval, + default_value)) return false; value = (uint8_t)huge; return true; } bool parse_option(int argc, char *const argv[], int &narg, const char *option, + int64_t &value, const int64_t minval, const int64_t maxval, + const int64_t default_value) { + uint64_t proxy = (uint64_t)value; + if (parse_option(argc, argv, narg, option, proxy, config::binary, + (uint64_t)minval, (uint64_t)maxval, + (uint64_t)default_value)) { + value = (int64_t)proxy; + return true; + } + return false; +} + +bool parse_option(int argc, char *const argv[], int &narg, const char *option, + int32_t &value, const int32_t minval, const int32_t maxval, + const int32_t default_value) { + uint64_t proxy = (uint64_t)value; + if (parse_option(argc, argv, narg, option, proxy, config::binary, + (uint64_t)minval, (uint64_t)maxval, + (uint64_t)default_value)) { + value = (int32_t)proxy; + return true; + } + return false; +} + +bool parse_option(int argc, char *const argv[], int &narg, const char *option, bool &value) { - const char *value_cstr = NULL; + const char *value_cstr = nullptr; if (!parse_option(argc, argv, narg, option, &value_cstr, "yes")) { const char *current = argv[narg]; if (strncmp(current, "--no-", 5) == 0 && strcmp(current + 5, option) == 0) { @@ -288,8 +357,12 @@ void dump(const char *title) { : i->params.pathname_log.c_str()); } - log_info("database: %s, size %" PRIu64 "\n", i->params.pathname_db.c_str(), - i->params.size); + log_info("database: %s, size %" PRIuPTR "[%" PRIiPTR "..%" PRIiPTR + ", %i %i, %i]\n", + i->params.pathname_db.c_str(), i->params.size_now, + i->params.size_lower, i->params.size_upper, + i->params.shrink_threshold, i->params.growth_step, + i->params.pagesize); dump_verbs("mode", i->params.mode_flags, mode_bits); dump_verbs("table", i->params.table_flags, table_bits); diff --git a/libs/libmdbx/src/test/config.h b/libs/libmdbx/src/test/config.h index 86f37fbed8..e8dc87577d 100644 --- a/libs/libmdbx/src/test/config.h +++ b/libs/libmdbx/src/test/config.h @@ -63,6 +63,10 @@ bool parse_option(int argc, char *const argv[], int &narg, const char *option, std::string &value, bool allow_empty = false); bool parse_option(int argc, char *const argv[], int &narg, const char *option, + std::string &value, bool allow_empty, + const char *default_value); + +bool parse_option(int argc, char *const argv[], int &narg, const char *option, bool &value); struct option_verb { @@ -75,16 +79,25 @@ bool parse_option(int argc, char *const argv[], int &narg, const char *option, bool parse_option(int argc, char *const argv[], int &narg, const char *option, uint64_t &value, const scale_mode scale, - const uint64_t minval = 0, const uint64_t maxval = INT64_MAX); + const uint64_t minval = 0, const uint64_t maxval = INT64_MAX, + const uint64_t default_value = 0); bool parse_option(int argc, char *const argv[], int &narg, const char *option, unsigned &value, const scale_mode scale, - const unsigned minval = 0, const unsigned maxval = INT32_MAX); + const unsigned minval = 0, const unsigned maxval = INT32_MAX, + const unsigned default_value = 0); bool parse_option(int argc, char *const argv[], int &narg, const char *option, uint8_t &value, const uint8_t minval = 0, - const uint8_t maxval = 255); + const uint8_t maxval = 255, const uint8_t default_value = 0); +bool parse_option(int argc, char *const argv[], int &narg, const char *option, + int64_t &value, const int64_t minval, const int64_t maxval, + const int64_t default_value = -1); + +bool parse_option(int argc, char *const argv[], int &narg, const char *option, + int32_t &value, const int32_t minval, const int32_t maxval, + const int32_t default_value = -1); //----------------------------------------------------------------------------- #pragma pack(push, 1) @@ -203,7 +216,12 @@ struct actor_params_pod { unsigned mode_flags; unsigned table_flags; - uint64_t size; + intptr_t size_lower; + intptr_t size_now; + intptr_t size_upper; + int shrink_threshold; + int growth_step; + int pagesize; unsigned test_duration; unsigned test_nops; diff --git a/libs/libmdbx/src/test/gc.sh b/libs/libmdbx/src/test/gc.sh new file mode 100644 index 0000000000..84f31a50e7 --- /dev/null +++ b/libs/libmdbx/src/test/gc.sh @@ -0,0 +1,35 @@ +#!/bin/bash +set -euo pipefail +TESTDB_PREFIX=${1:-/dev/shm/mdbx-gc-test} + +function rep9 { printf "%*s" $1 '' | tr ' ' '9'; } +function join { local IFS="$1"; shift; echo "$*"; } +function bit2option { local -n arr=$1; (( ($2&(1<<$3)) != 0 )) && echo -n '+' || echo -n '-'; echo "${arr[$3]}"; } + +options=(writemap coalesce lifo) + +function bits2list { + local -n arr=$1 + local i + local list=() + for ((i=0; i<${#arr[@]}; ++i)) do + list[$i]=$(bit2option $1 $2 $i) + done + join , "${list[@]}" +} + +for nops in {7..1}; do + for ((wbatch=nops; wbatch > 0; --wbatch)); do + for ((bits=2**${#options[@]}; --bits >= 0; )); do + echo "=================================== $(date)" + rm -f ${TESTDB_PREFIX}* + echo --nops=$( rep9 $nops ) --batch.write=$( rep9 $wbatch ) --mode=$(bits2list options $bits) + ./mdbx_test --pathname=${TESTDB_PREFIX} --pagesize=min --size=8G --keylen.min=1 --keylen.max=250 --datalen.min=1 --datalen.max=1500 \ + --nops=$( rep9 $nops ) --batch.write=$( rep9 $wbatch ) --mode=$(bits2list options $bits) \ + --keygen.seed=$(date +%N) --hill | bzip2 -c > ${TESTDB_PREFIX}.log.bz2 + ./mdbx_chk -nvv ${TESTDB_PREFIX} | tee ${TESTDB_PREFIX}-chk.log + done + done +done + +echo "=== ALL DONE ====================== $(date)" diff --git a/libs/libmdbx/src/test/hill.cc b/libs/libmdbx/src/test/hill.cc index c9115784d4..0d609b8692 100644 --- a/libs/libmdbx/src/test/hill.cc +++ b/libs/libmdbx/src/test/hill.cc @@ -156,8 +156,6 @@ bool testcase_hill::run() { a_serial); generate_pair(a_serial, a_key, a_data_0, 0); generate_pair(a_serial, a_key, a_data_1, age_shift); - if (a_serial == 808) - log_trace("!!!"); int rc = mdbx_replace(txn_guard.get(), dbi, &a_key->value, &a_data_1->value, &a_data_0->value, update_flags); if (unlikely(rc != MDBX_SUCCESS)) diff --git a/libs/libmdbx/src/test/keygen.cc b/libs/libmdbx/src/test/keygen.cc index 99b46f2976..1b18fa0033 100644 --- a/libs/libmdbx/src/test/keygen.cc +++ b/libs/libmdbx/src/test/keygen.cc @@ -122,16 +122,16 @@ void maker::setup(const config::actor_params_pod &actor, unsigned thread_number) { key_essentials.flags = actor.table_flags & (MDBX_INTEGERKEY | MDBX_REVERSEKEY); - assert(actor.keylen_min < UINT8_MAX); + assert(actor.keylen_min <= UINT8_MAX); key_essentials.minlen = (uint8_t)actor.keylen_min; - assert(actor.keylen_max < UINT16_MAX); + assert(actor.keylen_max <= UINT16_MAX); key_essentials.maxlen = (uint16_t)actor.keylen_max; value_essentials.flags = actor.table_flags & (MDBX_INTEGERDUP | MDBX_REVERSEDUP); - assert(actor.datalen_min < UINT8_MAX); + assert(actor.datalen_min <= UINT8_MAX); value_essentials.minlen = (uint8_t)actor.datalen_min; - assert(actor.datalen_max < UINT16_MAX); + assert(actor.datalen_max <= UINT16_MAX); value_essentials.maxlen = (uint16_t)actor.datalen_max; assert(thread_number < 2); diff --git a/libs/libmdbx/src/test/log.h b/libs/libmdbx/src/test/log.h index e97e954cea..3e9f9483ab 100644 --- a/libs/libmdbx/src/test/log.h +++ b/libs/libmdbx/src/test/log.h @@ -17,16 +17,7 @@ #include "base.h" void __noreturn usage(void); - -#ifdef __GNUC__ -#define __printf_args(format_index, first_arg) \ - __attribute__((format(printf, format_index, first_arg))) -#else -#define __printf_args(format_index, first_arg) -#endif - void __noreturn __printf_args(1, 2) failure(const char *fmt, ...); - void __noreturn failure_perror(const char *what, int errnum); const char *test_strerror(int errnum); diff --git a/libs/libmdbx/src/test/main.cc b/libs/libmdbx/src/test/main.cc index bc3198ed3a..1cac3506a3 100644 --- a/libs/libmdbx/src/test/main.cc +++ b/libs/libmdbx/src/test/main.cc @@ -1,4 +1,4 @@ -/* +/* * Copyright 2017-2018 Leonid Yuriev <leo@yuriev.ru> * and other libmdbx authors: please see AUTHORS file. * All rights reserved. @@ -35,7 +35,13 @@ void actor_params::set_defaults(const std::string &tmpdir) { mode_flags = MDBX_NOSUBDIR | MDBX_WRITEMAP | MDBX_MAPASYNC | MDBX_NORDAHEAD | MDBX_NOMEMINIT | MDBX_COALESCE | MDBX_LIFORECLAIM; table_flags = MDBX_DUPSORT; - size = 1024 * 1024 * 4; + + size_lower = -1; + size_now = 1024 * 1024 * 4; + size_upper = -1; + shrink_threshold = -1; + growth_step = -1; + pagesize = -1; keygen.seed = 1; keygen.keycase = kc_random; @@ -150,8 +156,34 @@ int main(int argc, char *const argv[]) { if (config::parse_option(argc, argv, narg, "table", params.table_flags, config::table_bits)) continue; - if (config::parse_option(argc, argv, narg, "size", params.size, - config::binary, 4096 * 4)) + + if (config::parse_option(argc, argv, narg, "pagesize", params.pagesize, + mdbx_limits_pgsize_min(), + mdbx_limits_pgsize_max())) + continue; + if (config::parse_option(argc, argv, narg, "size-lower", params.size_lower, + mdbx_limits_dbsize_min(params.pagesize), + mdbx_limits_dbsize_max(params.pagesize))) + continue; + if (config::parse_option(argc, argv, narg, "size", params.size_now, + mdbx_limits_dbsize_min(params.pagesize), + mdbx_limits_dbsize_max(params.pagesize))) + continue; + if (config::parse_option(argc, argv, narg, "size-upper", params.size_upper, + mdbx_limits_dbsize_min(params.pagesize), + mdbx_limits_dbsize_max(params.pagesize))) + continue; + if (config::parse_option( + argc, argv, narg, "shrink-threshold", params.shrink_threshold, 0, + (int)std::min((intptr_t)INT_MAX, + mdbx_limits_dbsize_max(params.pagesize) - + mdbx_limits_dbsize_min(params.pagesize)))) + continue; + if (config::parse_option( + argc, argv, narg, "growth-step", params.growth_step, 0, + (int)std::min((intptr_t)INT_MAX, + mdbx_limits_dbsize_max(params.pagesize) - + mdbx_limits_dbsize_min(params.pagesize)))) continue; if (config::parse_option(argc, argv, narg, "keygen.width", @@ -188,20 +220,33 @@ int main(int argc, char *const argv[]) { config::duration, 1)) continue; if (config::parse_option(argc, argv, narg, "keylen.min", params.keylen_min, - config::no_scale, 0, params.keylen_max)) + config::no_scale, 0, UINT8_MAX)) { + if (params.keylen_max < params.keylen_min) + params.keylen_max = params.keylen_min; continue; + } if (config::parse_option(argc, argv, narg, "keylen.max", params.keylen_max, - config::no_scale, params.keylen_min, - mdbx_get_maxkeysize(0))) + config::no_scale, 0, + std::min((unsigned)mdbx_limits_keysize_max(0), + (unsigned)UINT16_MAX))) { + if (params.keylen_min > params.keylen_max) + params.keylen_min = params.keylen_max; continue; + } if (config::parse_option(argc, argv, narg, "datalen.min", params.datalen_min, config::no_scale, 0, - params.datalen_max)) + UINT8_MAX)) { + if (params.datalen_max < params.datalen_min) + params.datalen_max = params.datalen_min; continue; + } if (config::parse_option(argc, argv, narg, "datalen.max", - params.datalen_max, config::no_scale, - params.datalen_min, MDBX_MAXDATASIZE)) + params.datalen_max, config::no_scale, 0, + std::min((int)UINT16_MAX, MDBX_MAXDATASIZE))) { + if (params.datalen_min > params.datalen_max) + params.datalen_min = params.datalen_max; continue; + } if (config::parse_option(argc, argv, narg, "batch.read", params.batch_read, config::no_scale, 1)) continue; diff --git a/libs/libmdbx/src/test/osal-windows.cc b/libs/libmdbx/src/test/osal-windows.cc index 109c835a96..b8cdb53513 100644 --- a/libs/libmdbx/src/test/osal-windows.cc +++ b/libs/libmdbx/src/test/osal-windows.cc @@ -53,7 +53,7 @@ void osal_wait4barrier(void) { } } -static HANDLE make_inharitable(HANDLE hHandle) { +static HANDLE make_inheritable(HANDLE hHandle) { assert(hHandle != NULL && hHandle != INVALID_HANDLE_VALUE); if (!DuplicateHandle(GetCurrentProcess(), hHandle, GetCurrentProcess(), &hHandle, 0, TRUE, @@ -71,7 +71,7 @@ void osal_setup(const std::vector<actor_config> &actors) { HANDLE hEvent = CreateEvent(NULL, TRUE, FALSE, NULL); if (!hEvent) failure_perror("CreateEvent()", GetLastError()); - hEvent = make_inharitable(hEvent); + hEvent = make_inheritable(hEvent); log_trace("osal_setup: event %" PRIuPTR " -> %p", i, hEvent); events[i] = hEvent; } @@ -79,12 +79,12 @@ void osal_setup(const std::vector<actor_config> &actors) { hBarrierSemaphore = CreateSemaphore(NULL, 0, (LONG)actors.size(), NULL); if (!hBarrierSemaphore) failure_perror("CreateSemaphore(BarrierSemaphore)", GetLastError()); - hBarrierSemaphore = make_inharitable(hBarrierSemaphore); + hBarrierSemaphore = make_inheritable(hBarrierSemaphore); hBarrierEvent = CreateEvent(NULL, TRUE, FALSE, NULL); if (!hBarrierEvent) failure_perror("CreateEvent(BarrierEvent)", GetLastError()); - hBarrierEvent = make_inharitable(hBarrierEvent); + hBarrierEvent = make_inheritable(hBarrierEvent); } void osal_broadcast(unsigned id) { diff --git a/libs/libmdbx/src/test/test.cc b/libs/libmdbx/src/test/test.cc index 3750af525f..80694827a6 100644 --- a/libs/libmdbx/src/test/test.cc +++ b/libs/libmdbx/src/test/test.cc @@ -149,7 +149,10 @@ void testcase::db_prepare() { if (unlikely(rc != MDBX_SUCCESS)) failure_perror("mdbx_env_set_oomfunc()", rc); - rc = mdbx_env_set_mapsize(env, (size_t)config.params.size); + rc = mdbx_env_set_geometry( + env, config.params.size_lower, config.params.size_now, + config.params.size_upper, config.params.growth_step, + config.params.shrink_threshold, config.params.pagesize); if (unlikely(rc != MDBX_SUCCESS)) failure_perror("mdbx_env_set_mapsize()", rc); diff --git a/libs/libmdbx/src/test/utils.cc b/libs/libmdbx/src/test/utils.cc index 0855c7eef3..53a750e314 100644 --- a/libs/libmdbx/src/test/utils.cc +++ b/libs/libmdbx/src/test/utils.cc @@ -93,7 +93,7 @@ bool hex2data(const char *hex_begin, const char *hex_end, void *ptr, //----------------------------------------------------------------------------- -/* TODO: replace my 'libmera' fomr t1ha. */ +/* TODO: replace my 'libmera' from t1ha. */ uint64_t entropy_ticks(void) { #if defined(EMSCRIPTEN) return (uint64_t)emscripten_get_now(); |