Комментарии 48
Отличная "мясистая" статья!
Несколько комментариев относительно упомянутого движка MDBX:
- Настоятельно советую мигрировать с LMDB на MDBX, пока не "бомбанули" ошибки LMDB. Кроме этого вы получите автокомпактификацию и изменяемый размер файла БД.
- MDBX появилась внутри ReOpenLDAP в ходе доработок для использования в инфраструктуре ПАО Мегафон, и произошла эта история в компании Петер-Сервис (ныне Nexign).
- Об MDBX скоро будет отдельная статья, как только я закончу основную работу над C++ биндингами.
- При необходимости хранить "табличные данные" с колонками и вторичными индексами рекомендую посмотреть на libfpta, а не мучиться с голым key-value.
Пользуясь случаем, хочу поинтересоваться, автоадаптация размеров хранилища не приводит к инвалидации разного рода сущностей, полученных ранее от движка. Вот получил я указатель на данные в MDB_val, какой-то кусок кода продолжает им пользоваться и тут бац и база поресайзилась. Как транзакции переживают этот момент? В этом свете, предполагает ли работа с MDBX обязательное копирование ранее полученных из неё данных?
Не Юра, но почти привык ;)
Данные лежание внутри БД (внутри mmap-файла) валидны пока вы находитесь в рамках транзакции. Соответственно, если упростить, то libmdbx не уменьшает размер файла меньше чем используется хотя-бы одним из читателей.
Кстати, две характерные ошибки при использовании LMDB/MDBX — это обращение к данным вне пределов транзакции, когда эти данные могут быть перезаписаны. Причем есть отдельный подвид таких ошибок внутри пишущих транзакций, когда данные могут располагаться в грязной страницы и меняться в ходе операций внутри текущей транзакции. Это достаточно частые "грабли" при организации различных индексов или отношений поверх MDBX, поэтому:
- в MDBX есть
mdbx_is_dirty(); - есть смысл посмотреть на libfpta, чтобы не ходить по этим граблям.
На всякий добавлю про бесплатную авто-компактификацию внтури MDBX, так как многие либо не доверяют этому механизму, либо даже считают его надувательством (ибо "не может быть").
Так вот, автокомпактификация основывается на простом "трюке":
- Внутри БД есть значение, отмечающее границу выделенных страниц от начала файла БД (сколько страниц находится в обороте, включая как данные, так и GC).
- При освобождении страниц внутри БД проверяется примыкают ли они к этой границе, и если примыкают, то граница сдвигается к началу. Эта очень дешево, почти бесплатно.
- Такими образом, libmdbx стремиться вытолкнуть максимум страниц в не-распределенный/неиспользуемый хвост файла БД, при необходимости больше "пережевав" GC.
В результате, реально используемый набор страниц БД стремится к уменьшению (что уменьшает объем используемой памяти и общее давление на подсистему управлением виртуальной памятью).
Как видите, это достаточно простой, надежный и эффективный механизм. Не понимаю, почему Howard Chu не реализовал подобное в LMDB исходно и даже сейчас (спустя почти три года, как автокомпактификация появилась в libmdbx).
Соответственно, динамическое изменение размера БД основывает на этой авто-компактификации, и (если сильно упростить) сводится к добавлению/отрезанию файла БД рациональными (не мелкими) кусками (ибо это относительно дорогая операция).
Ок, вы выталкиваете данные в конец файла, а как обрезаете его начало-то? Или не обрезаете и он растёт неограниченно?
Классная библиотека, особенно когда у тебя 1 writer.
Для генерации ключа мы использовали код из FoundationDb
В свое время я из интереса написал универсальный сериализатор ключей LRE когда работал с Berkeley DB, поскольку аналогичных библиотек в сети я не нашел. Сериализатор из FDB не позволяет сравнивать целые и флоаты, потому что использует для них разные представления.
Надо мне будет сделать бенчмарк, чтобы сравнить с fptu. Предположительно должно-быть где-то между "Raw structs" и "FlatBuffers (binary)".
Независимо от этого хотелось-бы узнать ваше мнение, так сказать при взгляде со стороны. Тем более если что-нибудь попробуете/пощупаете.
Кастомный компаратор все равно проиграет memcmp. Так что самое быстро решение — сериализовать составной ключ в строку, поддерживающую правильный порядок при лексикографическом сравнении.
На всякий — в MDBX есть примитивные функции формирования ключей, которые решают близкую задачу. Например, составной ключ из double и integer легко получить просто перевернув байты в BigEndian и записав последовательно. Причем при сборке с использованием LTO/IPO это будет максимально дешево (без накладных расходов).
И еще на всякий — в libfpta поддерживаются составные индексы (по нескольким колонкам), в которых всё необходимое делается автоматически (а в готовящемся С++ API еще и удобнее).
Пользуясь случаем, хотел спросить ещё следующее. В мобилках отсутствие места на диске является вполне себе заурядной ситуацией, особенно в контексте облачного приложения, которое и устанавливают, чтобы это место освободить. Насколько сложным вам видится поддержка работы хранилища в in memory режиме, без привязки к файлу. По идее поддержать mmap поверх анонимной памяти не должно быть сильно сложной задачей. Много ли внутри LMDB или сильно продвинувшейся вперед MDBX завязок на то, что под mmap обязательно лежит именно файл?
Прям заинтриговали готовящимся C++ API от души!
Плюсовое API для libmdbx будет без особых чудес, но с RAII и т.п. В свою очередь, у libfpta будет свое С++ API — и вот тут изменений и удобств будет существенно больше, но это два разных проекта (хотя и взаимосвязанных).
Насколько сложным вам видится поддержка работы хранилища в in memory режиме, без привязки к файлу.
Эта задача уже сейчас полностью решается под Linux/Android (и некоторых BSD-системах) путем размещения БД в tmpfs (/dev/shm).
Для других платформ (OSX/iOS, Windows) эта задача не является технически сложной, но требует доработки/расширения API и допиливания внутренних интерфейсов с риском внесения багов. Причем имплементить и тестировать это нужно так, чтобы работало везде. Поэтому варианта примерно три:
- вы можете сделать это разумно-костыльным способом своими силами в своем форке.
- вы можете итеративно по-хорошему реализовать такую фичу и оформить pull-request.
- вы можете как-то задонатить такую доработку, если она вам действительно нужна.
Моя же собственная мотивация по libmdbx — довести проект до максимальной готовности (зарелизить v1.0), что предполагает консервативный подход к добавлению новых features.
На всякий, "разумно-костыльно" — это значит (например) просто задефайнить часть используемых в libmdbx функций POSIX на собственные реализации, пересадив таким образом БД в ОЗУ. Причем если собрать с LTO (clang из яблочного SDK давно умеет), то вы еще и выиграете по производительности.
Такая пересадка БД в ОЗУ предполагает что все функции, работающие с файловой системой (кроме открытия-создания и закрытия БД), становятся пустотелыми заглушками.
Соответственно, при сборке с LTO компилятор выкинет всё что связано с дисковым обменом и подготовкой к нему.
Речь об эффекте от удаления мертвого кода, что на стоит путать (например) с удалением недостижимого кода.
Т.е. компилятор сможет выкинуть больше кода не из-за того что какие-то функции не вызываются (ибо они будут вызываться, это достижимый код), а потому-что эти функции не заканчиваются системными вызовами и не оказывают влияния на результат работы (являются мертвым кодом, включая все операции подготовки их аргументов).
Прям заинтриговали готовящимся C++ API от души!
С++ API для libmdbx доступно в ветке c++ на github и скоро (после обкатки и стабилизации) переедет в master. Некоторые ключевые моменты:
- приложено много усилий чтобы сделать многочисленные возможности MDBX само-документируемыми и удобными для использования (режимы работы БД, варианты ключей и значений, и т.д.);
- от C++11 до C++20 и всего три семантически функциональных класса: среда/БД, транзакция и курсор.
- одна библиотека и один заголовочный файл, большую часть которого занимаю классы slice и buffer;
- опорное
CAPI также было расширено: (де)регистрация тредов-читателей, предварительное создание экземпляров читающих транзакций и курсоров — в сумме позволяет получить гарантии lock-free для операций чтения.
Самое время посмотреть и высказать пожелания, может чего-то не достает. Code review также приветствуется, но отписывать конечно не сюда, а в телеграм или на github.
https://github.com/abdullin/foundationdb-1/blob/master/fdbclient/Tuple.cpp вот тут исходники Tuple. Доки здесь поищите, мы на C# переписали, там один маленький файл получился. Код не могу сходу найти.
На вопрос почему это использовали: код простой, быстрый и передаешь методу например так
Fdb.CreateKey(tableId, authorId,bookName)
и получаешь байты, которые уже отсортированы, т.е. если tableId1<tableId2 то каким бы authorId не был, все равно 2 строка будет позже чем первая.
Что касается того что int и double будут там разными байтами, мы по факту элемент ключа использовали как index column, поэтому если tableId — это int, то он был таким для всех таблиц.
При всех достоинствах LMDB (главным образом астрономическая скорость), существует много ограничений, особенно если сравнивать с её "медленным старшим братом" Berkeley DB. Вот некоторые из тех, с которыми я сталкивался:
- Длина ключа ограничена 511 байтами. Этот #define внутри библиотеки может быть переопределён, но его значение не может быть больше, чем 1/2 размера страницы
- Только пишущие транзакции могут быть вложенными. Родительские транзакции не могут выполнять никаких операций кроме mdb_txn_commit и mdb_txn_abort. Вложенные транзакции несовместимы с MDB_WRITEMAP
- Курсоры не имеют возможностей эффективного смещения, только последовательная перемотка записей или MDB_SET_RANGE
- База данных непрерывно растет
- Нет репликации
- Нет очередей
Всё совершенно верно, но я бы хотел дать пояснения (почему так) и показать что исправлено/улучшено у меня в MDBX (потомке LMDB).
Длина ключа ограничена 511 байтами. Этот #define внутри библиотеки может быть переопределён, но его значение не может быть больше, чем 1/2 размера страницы.
Хуже, не 1/2, а скорее 1/4 размера страницы. Причина в том, что в "простом" b+tree в branch-странице должно быть минимум 2 ключа и для возможности эффективного split+rebalance это правило должно выполняться после разделения страницы пополам. Соответственно 2*2 = 4.
Поддержка более длинных ключей требует существенного усложнения кода (сжатие префиксов, вынос ключей в отдельные страницы), но при этом всё равно сильно страдает производительность.
В MDBX указанное ограничение "из каробки" увеличено до максимального уровня (не нужно править #define и пересобирать). Кроме этого, также "из каробки" при создании БД возможен выбор размера страницы вплоть до 64К, т.е. в MDBX максимальный размер ключа примерно в 42 раза больше (21780 байт вместо 511).
Только пишущие транзакции могут быть вложенными.
Нет смысла делать вложенными читающие транзакции, они будут читать одно и тоже и ничего не могут менять. При необходимости такая вложенность может эмулироваться кодом-оберткой со счетчиком ссылок, но ценность и сценарии использования такой возможности (мне) не понятны.
Аналогично нет смысла вкладывать читающие транзакции в пишущие, и опять-таки это легко эмулировать в коде-обертке.
Родительские транзакции не могут выполнять никаких операций кроме mdb_txn_commit и mdb_txn_abort.
В MDBX/LMDB сознательно явно сериализуются все пишущие транзакции, это дает массу бонусов. Если же от этого отказаться, то начнется ад с блокировками и/или проблемы с изоляцией транзакций. Поэтому активной (с возможностью операций) может быть только одна (самая вложенная) транзакция, а изменения в родительских становятся возможными после завершения (commit или abort) всех дочерних.
Вложенные транзакции несовместимы с MDB_WRITEMAP.
Вложенные транзакции требуют формирования в памяти набора/кэша всех измененных станиц, причем смотреть на все данные через этот кэш. Это ровно тоже самое, что происходит без опции MDBX_WRITEMAP.
Со своей стороны, опция MDBX_WRITEMAP позволяет избавиться от накладных расходов на формирования образов страниц в памяти и их последующей записи через файловой API.
Если же реализовать вложенные транзакции в режиме MDBX_WRITEMAP, то при этом вернется назад существенная часть накладных расходов.
Поэтому предлагается выбрать между двумя вариантами: быстро (в режиме MDBX_WRITEMAP) и без вложенных транзакций, либо с дополнительными накладными расходами и вложенными транзакциями.
Курсоры не имеют возможностей эффективного смещения, только последовательная перемотка записей или MDB_SET_RANGE.
Сквозная нумерация конечно была-бы полезна (например для быстрой оценки range-запросов). Но Howard не стал её реализовывать (видимо) потому, что этого НЕ требовалось в его целевых сценариях (OpenLDAP), но требовало еще больше усложнить исходный код.
Со своей стороны, мне в MDBX в начале этого также не требовалось, а сейчас это проблематично добавить, ибо требуется переработка формата БД. А вот в MithrilDB я склоняюсь к решению реализовать эту фичу.
Тем не менее, в MDBX сейчас есть быстрая оценка range-выборок.
База данных непрерывно растет.
Да, это одна из проблем LMDB, которая полностью решена в MDBX — есть авто-компактификация и автоматической изменение размера БД "на лету", см. mdbx_env_set_geometry().
Нет репликации.
Полезная фича с точки зрения пользователя, но очень сомнительная с точки зрения движка хранения.
"Репликация" требует принятия ряда архитектурных решений и их последующее навязывание пользователю, в частности использование WAL.
Сам движок хранения при этом становится подглючивающим "швейцарским ножом" с "большими батарейками", примерно как Berkeley DB.
Я склоняюсь к варианту предоставления в MithrilDB доступа к части внутреннего API, так чтобы необходимый вариант репликации мог быть реализован рядом (плагином), без дополнительных накладных расходов и без "протечки абстракции" внутрь движка хранения.
Нет очередей.
Технически очередь (FIFO или с приоритетами) тривиально реализуется поверх key-value. В случае LMDB при этом в качестве ключа можно использовать номер транзакции (если требуется FIFO), а в MDBX также есть генераторы последовательностей.
Если же требуется "тупая" очередь в виде максимально эффективного FIFO с полной durability, то специализированные решения на базе кольцевых буферов будут все равно эффективнее.
Однако, если это тянуть в key-value движок хранения, то снова получится "швейцарский нож", но не действительно надежный охотничий или удобный перочинный.
Полезная фича с точки зрения пользователя, но очень сомнительная с точки зрения движка хранения.
"Репликация" требует принятия ряда архитектурных решений и их последующее навязывание пользователю, в частности использование WAL.
Зачем тут WAL? Кажется для репликации достаточно реализовать 2 шага:
- Первичная репликация. При подключении реплики читать базу от корня сверяя со значениями в реплике. Обнаружив не изменённое поддерево — дальше не идём.
- Рилтайм репликация. С начала первичной репликации пишем все изменения в очередь. По завершении первичной репликации — просто читаем очередь и накладываем изменения в свою копию.
Зачем тут WAL?
Начну с "конца". WAL — это по-сути и есть "пишем все изменения в очередь". Разница лишь в том, что если у вас отдельная очередь, то вероятно потребуется WAL и на саму очередь.
Без WAL вам потребуется делать "первичную репликацию" (синхронизацию содержимого) при каждом запуске после любой разсинхронизации (когда в мастер были внесены изменения, а реплика была в off-line). В принципе так тоже можно, но при большой БД (скажем в 100 гигов) это потребует чтения этих данных с обоих сторон.
На всякий — в MithrilDB будет B+Tree совмещенное с Merkle Tree, как для контроля целостности (включая криптографическую надежность), так и для синхронизации (грубо говоря, а-ля rsync рекурсивно от корня дерева).
WAL — это всё же "сначала пишем, что будем менять, дожидаемся подтверждения записи, потом меняем". Тут же речь про "меняем и асинхронно пишем, что поменяли".
Тут время первичной репликации не от размера ДБ зависит, а от размера разницы. Так что после любой рассинхронизации реплика всё же должна быстро нагнать мастер.
Вот, кстати, тут интересный вопрос: как с такой схемой работы, как у LMDB реализовать мастер-мастер репликацию?
Касательно Merkle Tree меня смущают накладные расходы на постоянное хеширование всего и вся. И хранение длинных хешей. А если хеши не длинные, то любая коллизия — это сломанная база.
А что вы будете делать в случае нарушения целостности? Писать "ваша база сломана, несите следующую"? Тут скорее наоборот избыточность нужна для восстановления.
WAL — это всё же "сначала пишем, что будем менять, дожидаемся подтверждения записи, потом меняем". Тут же речь про "меняем и асинхронно пишем, что поменяли".
Это не важно.
Суть же в том, что в WAL у вас есть история операций (тот самый аналог очереди).
Т.е. если у вас уже есть WAL, но рациональнее его доработать для возможности remote replay в целях репликации, нежели чем делать отдельную очередь (см. репликацию в Tarantool).
Опять-таки, проблема отдельной очереди в разрастании её размере.
Для MDBX/LMDB достаточно обычный кейс — несколько сотен/тысяч транзакций в секунду, очередь будет расти с огромной скоростью.
время первичной репликации не от размера ДБ зависит, а от размера разницы.
В общем случае, вам потребуется прочитать и сверить данные с обоих сторон (прочитать replication scope в обоих БД почти полностью), либо держать/обслуживать какие-то вспомогательные индексы/данные.
интересный вопрос: как с такой схемой работы, как у LMDB реализовать мастер-мастер репликацию?
Принципиально/кардинально сильно зависит что на самом деле надо.
В качестве работающего примера погуглите multi-master репликацию в ReOpenLDAP.
Касательно Merkle Tree меня смущают накладные расходы на постоянное хеширование всего и вся. И хранение длинных хешей. А если хеши не длинные, то любая коллизия — это сломанная база.
Хм, вы видимо не умеет его готовить.
Хешировать требуется только каждую изменяемую страницу и только при фиксации транзакции. Т.е. накладных расходов конечно всё-таки больше, но поддержка MVCC через Shadow paging при изменении листовой страницы всё равно требует апдейта всех родительских включая корневую.
Что касается размера хеша, то 128 бит обеспечат вероятность пропуска ошибки намного порядков меньше чем чтение неверных данных из-за попадания заряженной частицы в транзистор и т.п.
А что вы будете делать в случае нарушения целостности? Писать "ваша база сломана, несите следующую"? Тут скорее наоборот избыточность нужна для восстановления.
А что вы делали когда вам в крайний раз такое сказала ваша файловая система или БД?
Это не важно.
Ну это как называть человеками всех человекообразных обезьян. Write Ahead Log — частный случай Log. Но если называть любой лог WAL-ом — никто вас не поймёт.
если у вас уже есть WAL
В том-то и дело, что у нас с вами нет WAL by design.) К тому же репликация на уровне WAL как в Postgre — не самая эффективная штука.
Для MDBX/LMDB достаточно обычный кейс — несколько сотен/тысяч транзакций в секунду, очередь будет расти с огромной скоростью.
Тут, кстати, можно посмотреть в сторону чего-нибудь типа delta-crdt, позволяющего мёржить несколько баз в одну. То есть при репликации писать не просто в очередь, а во временную базу имеющую ту же структуру, которую можно подклеить к реплике минимальными телодвижениями.
В качестве работающего примера погуглите multi-master репликацию в ReOpenLDAP.
Не нашёл как они это реализовали.
А что вы делали когда вам в крайний раз такое сказала ваша файловая система или БД?
Файловая система мне выдаёт несколько битых файлов.
PavelOsipov Варианты, что можно тут сделать, ограничиваются лишь вашей фантазией. Все они сводятся к ручному или автоматическому переименованию на клиенте или на сервере.
Вот именно, что одна версия переименовывается, но остаётся тем же самым файлом, а не выкачивается как новый файл.
В том-то и дело, что у нас с вами нет WAL by design.) К тому же репликация на уровне WAL как в Postgre — не самая эффективная штука.
В частности поэтому (и еще массе других причин) я не хочу делать репликацию в MDBX.
Тут, кстати, можно посмотреть в сторону чего-нибудь типа delta-crdt, позволяющего мёржить несколько баз в одну. То есть при репликации писать не просто в очередь, а во временную базу имеющую ту же структуру, которую можно подклеить к реплике минимальными телодвижениями.
Это все частные случаи из моря возможных потребностей и их реализаций. В 80% случаев пользовательские данные не натягиваются на CRDT, либо превращаются в снежный ком. Аналогично с отдельной очередью в виде базы (или наоборот).
Не нашёл как они это реализовали.
https://pro-ldap.ru/tr/rfc/rfc4533.html
Файловая система мне выдаёт несколько битых файлов.
Это если нет контроля и повреждены файлы, а не структуры ФС.
Но в принципе может не выдать ничего или просто мусор.
А еще можно (мысленно) разбить диск молотком или вообще не устанавливать, а на запросы отвечать случайными данными.
Какой вариант вам кажется наиболее правильным?
Вот именно, что одна версия переименовывается, но остаётся тем же самым файлом, а не выкачивается как новый файл.
С этим также всё хорошо. При слиянии для идентификации файла используется ещё и его контрольная сумма, timestamp да другие параметры (и тут очень удобно, что при итерировании курсором по ключам за бесплатно доступны и значения тоже). Однако алгоритмика этого процесса находится в стороне от темы статьи, поэтому затрагивать её сейчас не очень интересно.
Воу, благодарю за развернутый текст. Я отвечу по мере своего опыта.
Хуже, не 1/2, а скорее 1/4 размера страницы. Причина в том, что в "простом" b+tree в branch-странице должно быть минимум 2 ключа и для возможности эффективного split+rebalance это правило должно выполняться после разделения страницы пополам. Соответственно 2*2 = 4.
Howard Chu писал, что Keys must be small enough to fit on a page, and a page must contain at least two keys in order for the B-tree structure to be maintained. So the absolute max is 1/2 the page size; we use 1/3 to avoid size issues when using DUPSORT mixed with other data. https://bugzilla.redhat.com/show_bug.cgi?id=1086784#c5
Нет смысла делать вложенными читающие транзакции, они будут читать одно и тоже и ничего не могут менять. При необходимости такая вложенность может эмулироваться кодом-оберткой со счетчиком ссылок, но ценность и сценарии использования такой возможности (мне) не понятны.
Прекрасно это понимаю, но это неудобно. Так, я не могу абстрагировавшись создать "сверху" родительскую транзакцию (например, в декораторе) и просто передать ее в подчиненную функцию. Мне нужно знать, пишет ли код "снизу" или только читает.
Сквозная нумерация конечно была-бы полезна (например для быстрой оценки range-запросов). Но Howard не стал её реализовывать (видимо) потому, что этого НЕ требовалось в его целевых сценариях (OpenLDAP), но требовало еще больше усложнить исходный код.
Это было вообще киллер-фичей для меня. Молниеносная пагинация и вычисление total по диапазону BTree только один из примеров.
Технически очередь (FIFO или с приоритетами) тривиально реализуется поверх key-value. В случае LMDB при этом в качестве ключа можно использовать номер транзакции (если требуется FIFO), а в MDBX также есть генераторы последовательностей.
Да. Верно. Но технически это не будет дотягивать до DB_QUEUE в Berkeley DB. Во-первых,
процесс может ожидать следующую запись с помощью DB_CONSUME_WAIT, не требуя постоянного опроса БД. В противном случае придется делать опрос и сигнализацию (через ZMQ или сырой UDP-мультикаст). Во-вторых, репликация очереди происходит специальным образом: put реплицируется, а consume — нет (поэтому реплики тоже могут делать локальный consume). Наконец, очередь легко заоптимизировать. В Berkeley DB очереди работают с огромной скоростью.
Если же требуется "тупая" очередь в виде максимально эффективного FIFO с полной durability, то специализированные решения на базе кольцевых буферов будут все равно эффективнее.
Но мы не сможем делать операции с внешней очередью и базой данных атомарно.
Однако, если это тянуть в key-value движок хранения, то снова получится "швейцарский нож", но не действительно надежный охотничий или удобный перочинный.
Проблемы с надежностью у Berkeley DB вызваны главным образом из-за её хрупкой подсистемы блокировок, которая требует внешнего разрешения дедлоков и восстановления. Для DB_BTREE дедлоки иногда возникают вообще by design.
Howard Chu писаk Howard Chu писал, что Keys must be small enough to fit on a page...
Да, максимальная длина ключа завит от типа БД. У себя я в итоге просто добавил соответствующие функции. Кроме этого, точные значения указаны в соответствующем разделе README.
я не могу абстрагировавшись создать "сверху" родительскую транзакцию (например, в декораторе) и просто передать ее в подчиненную функцию. Мне нужно знать, пишет ли код "снизу" или только читает.
Оно так не может работать, точнее может но совсем не всегда.
Если у вас все начинается с читающей транзакции, то начать "дочернюю" пишущую возможно только если после старта родительской читающей не было изменений в данных.
Чтобы устранить это ограничение требуется и/или:
а. отказаться от single writer концепта (и войти в ад блокировок), т.е. сделать еще одну Berkeley DB или PostreSQL (у Константина Осипова было отличное выступление на Highload++, где оно пояснял что стоит за не-single writer).
б. сделать некую среду исполняющую формальный язык (SQL с хранимыми процедурами), чтобы она автоматически могла отменять, рестартовать транзакции чтобы повторно выполнять application код.
Если же у вас все начинается с пишущей транзакции, то опять-таки, либо отказ от single-writer (и все как выше), либо все вложенные транзакции также пишущие.
Это было вообще киллер-фичей для меня. Молниеносная пагинация и вычисление total по диапазону BTree только один из примеров.
Вот мне сейчас тоже потребовалась для оценки костов с целью выбора варианта выполнения запросов, но поздно пить боржоми (
технически это не будет дотягивать до DB_QUEUE в Berkeley DB. Во-первых,
процесс может ожидать следующую запись с помощью DB_CONSUME_WAIT.
Согласен, если нужен WAIT, то при существующем API потребуется полинг, т.е. тут центральная "проблема" в том, что исходно такие сценарии использования (ожидания данных) не рассматривались (и меня уже просили что-нибудь прибить "хотя-бы гвоздями").
Но мы не сможем делать операции с внешней очередью и базой данных атомарно.
Это можно если очередь допускает соответствующие блокировки и commit/revert, но в одном флаконе конечно удобнее (Tarantool).
Проблемы с надежностью у Berkeley DB вызваны главным образом из-за её хрупкой подсистемы блокировок, которая требует внешнего разрешения дедлоков и восстановления. Для DB_BTREE дедлоки иногда возникают вообще by design.
Тут вот есть принципиальная вещь — Проблемы "by design" начинаются если не-single writer.
Поэтому поэтому в MDBX/LMDB сознательно этой проблемы просто не создается, вместо того чтобы героически с ней биться.
Круто, ребята в LMDB реализовали почти все мои идеи. Но есть пара нюансов:
Глобальное key-value дерево это дико не удобно и не особо быстро. Из-за чего у вас куча костылей с компаратором. Моя идея в том, чтобы иметь в качестве значений другие деревья. Таким образом файловая иерархия отобразится наиболее естественным образом. Массивы, словари, любые структуры можно описать таким образом.
Не хватает ссылок между узлами, для описания графа. Сэмулировать их можно, если хранить в качестве значений ключи связанных узлов. А имея граф, таблицы вовсе никакие не нужны. Забудьте про них как про страшный сон. Существенная ваша ошибка — использовать естественные ключи, а не суррогатные. Это приводит к тому, что переименовывание файла выливается в поиск и замену всех вхождений ключа во всём дереве. Это крайне сложно и медленно.
Индексы должны быть всё же в СУБД, чтобы она сама гарантированно обновляла все связанные деревья при обновлении данных. Полагаться на прикладной код в этом вопросе — стрелять себе в ногу. Жаль, что в LMDB этот вопрос не продуман изначально.
Существенная ваша ошибка — использовать естественные ключи, а не суррогатные. Это приводит к тому, что переименовывание файла выливается в поиск и замену всех вхождений ключа во всём дереве. Это крайне сложно и медленно.
Это не ошибка, а осознанное архитектурное решение. Если я вас правильно понимаю, речь о том, что гораздо красивее было бы решение, где в качестве первичного ключа выступает примитивная структура, где есть только суррогатный идентификатор и всё. А все вторичные и индексные ключи просто ссылаются на него, держа его в своей value-части. Таким образом то же переименование не провоцирует большого количества изменений, максимум – перезапись индексных ключей, ориентированных на имя.
Но тут всё дело в нашем API. К сожалению у нод в дереве нет никакого идентификатора, который всегда существует и никогда не изменяется. Единственно на что можно рассчитывать – уникальность имени внутри одной папки. Таким образом процедура вычисления изменений внутри папки, о которой я упоминал в первой главе, строится на сравнении сортированных по имени списков дочерних элементов из локального папки и её серверного аналога. Поскольку эта процедура крайне частая и при полном слиянии двух деревьев (локального и серверного) в ней участвуют все элементы основной таблицы, то именно она должна быть максимально перфомансной, и именно под неё у нас и заточен первичный ключ. Ну а переименование – это суперредкая процедура, в рамках которой трогается перезаписывается крайне небольшое количество записей.
Как с такими ключами вы решаете такую ситуацию: пользователь на двух разных девайсах под одним и тем же именем сохранил разные файлы? И таких файлов >9000.
Глобальное key-value дерево это дико не удобно и не особо быстро. Из-за чего у вас куча костылей с компаратором. Моя идея в том, чтобы иметь в качестве значений другие деревья. Таким образом файловая иерархия отобразится наиболее естественным образом. Массивы, словари, любые структуры можно описать таким образом.
Не стоит делать выводы по одной статье, которая не совсем про саму БД.
В MDBX/LMDB собственно и есть "другие деревья в качестве значений":
- внутри одной "большой БД" (файла на диске) может быть куча вложенных именованных БД (пространства) key-value.
- Отдельная фишка в поддержке массивных multi-value, когда одному ключу соответствует несколько (даже очень много) значений. Исторически (начиная с Berkeley DB) такие кейсы называются "duplicates" и/или "sorted duplicates", т.е. имеется в виду что multi-value можно рассматривать как несколько записей с одинаковым ключом.
Так вот, multi-value в MDBX/LMDB хранятся во вложенных деревьях. При этом экономится как место (один экземпляр ключа на все multi-value), так и обеспечиваетсяOlog(N)для всех операций, включая поиск конкретных значений. Для вторичных индексов это просто killer feature.
Не хватает ссылок между узлами, для описания графа. Сэмулировать их можно, если хранить в качестве значений ключи связанных узлов. А имея граф, таблицы вовсе никакие не нужны. Забудьте про них как про страшный сон. Существенная ваша ошибка — использовать естественные ключи, а не суррогатные. Это приводит к тому, что переименовывание файла выливается в поиск и замену всех вхождений ключа во всём дереве. Это крайне сложно и медленно.
Это продолжение holly war между индексами "как в PostgreSQL" и "как в MySQL". В разных кейсах один из вариантов обычно выигрывает, но не более того (оба варианта не серебряная пуля).
Индексы должны быть всё же в СУБД, чтобы она сама гарантированно обновляла все связанные деревья при обновлении данных. Полагаться на прикладной код в этом вопросе — стрелять себе в ногу. Жаль, что в LMDB этот вопрос не продуман изначально.
Эмм, MDBX/LMDB — это key-value, Карл!
Никто не запрещает (при должной сноровке) забивать шурупы этими молотками.
Автор(ы) статьи сами решили реализовать нужные индексы поверх модели key-value — это их решение, никак не связанное с ограничениями MDBX/LMDB.
Если не хочется так заморачиваться (и пару раз попасть в ногу) с собственными индексами, то следует смотреть на libfpta или всё тот-же SQLite.
внутри одной "большой БД" (файла на диске) может быть куча вложенных именованных БД (пространства) key-value.
Вот, кстати, тоже спорный момент. Я склоняюсь к тому, как это сделано в OrientDB: есть N кластеров (файлов), куда по определённым правилам раскидываются узлы. И эти кластеры могут независимо реплицироваться на разные ноды (сервера). Это позволяет связанные подграфы держать рядом, при этом не держа на одном сервере вообще всю бд. Вот, кстати, партицирования у LMDB я так понимаю тоже нет. Я вот думаю раскидывать так же по файлам. Плюс мета-кластер для хранения мета-страниц в вашей терминологии. Плюс это могло бы дать такую фичу, как параллельная запись. Например, отдельный поток мог бы спокойно писать в свой кластер, не блокируя записи в другие кластеры. И только мета-кластер писался бы одним выделенным потоком, но там записи тривиальные.
Эмм, MDBX/LMDB — это key-value, Карл!
А, ну если так и собираетесь оставаться в детском саду, то вы мне не конкурент.)
следует смотреть на libfpta или всё тот-же SQLite
Спасибо, конечно, но табличками я сыт по горло. Вы работали когда-нибудь с графовыми СУБД?
Я склоняюсь к тому, как это сделано в OrientDB: есть N кластеров (файлов), куда по определённым правилам раскидываются узлы…
Вот, кстати, партицирования у LMDB я так понимаю тоже нет.
А причем тут OrientDB и партиционирование?
MDBX/LMDB — это встраиваемые движки key-value для совместной работы с БД несколькими локальными процессами. В этих целевых сценариях MDBX обеспечивает до 1M пишущих транзакций в секунду и примерно линейно масштабирутся в производительности чтения по ядрам CPU (десятки миллионов запросов в секунду, пока не упирается в memory bandwidth).
Никакому OrientDB в таких сценариях подобное и не снилось.
А для других (не целевых для MDBX) сценариев использования есть другие движки или СУБД, в том числе со всяческим партиционированием и SQL с блекджеком.
А, ну если так и собираетесь оставаться в детском саду, то вы мне не конкурент.)
Хм, а после "детского сада" сколько СУБД (в широком смысле) вы написали (или приняли участие) и довели до production?
Спасибо, конечно, но табличками я сыт по горло.
Каждый "сыт" тем что ему не нужно, и наоборот.
Т.е. "таблички" не в чем не виноваты, это решение предназначенное для некоторого подмножества сценариев использования.
Вы работали когда-нибудь с графовыми СУБД?
Ну делал я их, и видимо скоро снова продолжу (варианты для RDF).
Блеск и нищета key-value базы данных LMDB в приложениях для iOS