Comments 28
А сравнивали с JSON внутри sqlite? Какие есть преимущества у Boson?
Написано же, какие преимущества: своё, родное.
важно понимать, что это лишь учебный пример реализации СУБД движимый моим любопытством и поделиться впечатлениями от исследования
Преимущество - наглядность реализации. Хоть sqlite самая легкая СУБД, не самая простая, если почитаете исходный код, с ходу не поймете что и почему. В случае с Boson относительно не сложно разобраться, а потом и понять как работают промышленные СУБД.
Boson относительно не сложно разобраться, а потом и понять как работают промышленные СУБД.
Как разработчик движка СУБД скажу, что B+ деревья занимают в лучшем случае 1% от всей разработки промышленной СУБД, более того это самая простая и понятная часть всей этой “истории”.
Реальные сложности начинаются в реализации непосредственно самого SQL движка, совсем космос это реализации оптимизатора там просто “темная магия”, так же сложная область транзакции, консистентность, WAL, если мы говорим про промышленную СУБД то тут появляются кластера, бэкапы (дифференциальные, логов транзакций), репликация, сжатие данных, отдельно, пользователи, роли, клиент-сервер и т.д.
Вы правы. В масштабах промышленной СУБД образовательный пример Boson лишь малая часть - скорее всего 1%.
Из перечисленного о том как делать компилятор и виртуальную машину (VM) для условного Domain Specific Language (DSL) рассказывал в отдельной серии статей (можно и простое подмножество SQL сделать):
https://habr.com/ru/articles/571758/
WAL, транзакции, клиент/сервер - это большое путешествие которое на текущем этапе избыточно для исследования основ СУБД.
Было бы очень интересно прочесть статью, хотя бы с поверхностным обзором всего этого
Неплоха обзорная статья (оригинал у меня почемуто не доступен)
Как работает реляционная БД
https://habr.com/ru/companies/vk/articles/266811/
Есть на мой взгляд фундаментальная книга (хоть и немного устаревшая)
Database Systems: The Complete Book
дальше можно почитать по конкретным СУБД, например по Ораклу, тоже уже старая книга, но хорошо излагается связь между структурами данных и производительностью запросов
Cost-Based Oracle Fundamentals (Expert's Voice in Oracle)
по MSSQL, достаточно неплохой обзор внутренней архитектуры
Pro SQL Server Internals
про внутреннее устройство PosgreSQL есть хорошие русскоязычные книги:
https://postgrespro.ru/education/books\
и, к слову, я не согласен с автором (если не его цитата то прошу прощения), что код sqlite сложный, на мой взгляд это просто вопрос времени и в нем можно разобраться и понять как работает sqlite, на ютубе есть видео где "на основе" sqlite создается база данных
Writing My Own Database From Scratch
https://www.youtube.com/watch?v=5Pc18ge9ohI&t=1753s&ab_channel=TonySaro
...Строим свою СУБД. Для быстрого поиска нужен индекс. Индекс реализуется с использованием B+ дерева. А В+ дерево реализуется вот так: <...> Статья готова!
Рыбы это не млекопитающие. Шерстью не покрыты. Покрыты чешуей, но если
бы они были покрыты шерстью, то в ней бы водились блохи... <дальше про блох>
Спасибо за обратную связь. А какой информации не хватило или какой вопрос не раскрыт? Алгоритм расписал. Думаю, вы язык и основы знаете хорошо. Хотел не перегружать читателя очевидностями, но в исходном коде почти каждую строчку прокомментировал (на английском), если будут интересны детали реализации. Даже специально жертвовал местами производительностью в пользу наглядности.
Чем это дерево отличается от std::map?
В двух словах:
1) std::map — сбалансированное бинарное дерево (красно-черное дерево), очень эффективно на относительно малых объемах данных в оперативной памяти, но менее эффективно по памяти и не оптимально для больших данных, тогда как B+ Tree имеет узлы с множеством ключей и связные листья, что обеспечивает лучшую плотность хранения и быстрые диапазонные запросы, оптимально для работы с большими объемами данных.
2) во вторых std::map - это реализация для оперативной памяти, а в Boson B+ Tree сохраняет на диске с оптимизацией количества операций ввода/вывода (снизу реализация хранилища записей и алгоритмы кэширования).
Мне так видится.
А если в std::map подсунуть свой аллокатор, который хранит данные не в памяти, в на диске?
Например, с помощью memory mapped file. Не будет ли это примерно тем же самым?
Тогда это так или иначе выродится в B+ дерево.
Теоретически можно. Чтобы увеличить эффективность придётся большей ключей/значений держать в узлах и добавить двусвязные списки. Получится B+ Tree.
Использование mmap упростит реализацию, но мы становимся зависимыми от механизмов подкачки в ОС - сложно применять оптимизационные стратегии управления кэшированием. Добавим сюда необходмые механизмы защиты для многопоточности на уровне узлов и страниц - всё станет сложнее.
Вот статья которая объясняет почему использование mmap в DBMS может быть не очень хорошей идеей:
https://www.cidrdb.org/cidr2022/papers/p13-crotty.pdf
Есть перевод на Хабре - https://habr.com/ru/articles/820591/
А также есть комментарий Леонида (автор libmdbx - одной из лучших встраиваемых БД построенной на основе b+ деревьев и mmap) - https://t.me/libmdbx/5837
Нет, не будет. Как автор выше написал rb-tree отличается от b+-tree, тем что последнее значения хранит только в листьях и «блоки» листьев между собой связаны.
Вот довольно не плохая иллюстрация для b+ деревьев:
Добрый день, а не подскажите, почему B+ дерево предпочтительнее чем хеш?
И еще вопрос, а правильно я понимаю, что при удалении или модификации объекта память или место на диске не освобождаются? Спасибо
Спасибо за вопросы!
Hash Map использует хэш-функцию для определения позиции в фиксированном массиве, элементы которого могут быть связанными списками для разрешения коллизий хэш функции:
Hash Map не сохраняет порядок ключей, что делает его непригодным для диапазонных запросов и сортировки, в отличие от B+ Tree.
Hash Map менее эффективно использует дисковое пространство при работе с диском, так как требует предварительной аллокации массива, вне зависимости от количества элементов.
Да, при удалении записей файл меньше не становится. Удаленные записи оставляют "пустоты" в файлах (файл базы данных не дефрагментируем, чтобы не проиграть в скорости удаления), но эти "пустоты" используются повторно при вставке новых записей, если ёмкость удаленной записи достаточна для хранения вновь создаваемой.
Это даёт некий сбалансированный компромис между скоростью работы и эффективностью использования свободного пространства на диске. Многие СУБД используют аналогичную логику.
Об этом подробно рассказывал в предыдущей части статьи вот тут:
А выводы-то какие по итогу? Да, автор познал некоторые базовые идеи под капотом у баз данных, я правда рад за него, но в чем тут ценность для меня?
Вывод - реализация СУБД по описанному в начале тех заданию выполнима каждым, кто знаком с методами и алгоритмами описанными с цикле статей.
Ценность цикла статей о Boson - это пошаговый разбор алгоритмов и подходов реализации минимальной документальной СУБД с key/value хранилищем для тех кому интересно как это устроено:
Кэширование (Cached File I/O). https://habr.com/ru/articles/708768/
Хранилище (Recrods Storage I/O). https://habr.com/ru/articles/712896/
Индекс (Persisted B+ Tree). https://habr.com/ru/articles/856876/
Вторая ценность - это сам факт завершенности цикла статей и примера реализации. Этот вклад в хабы HABR, где я не нашел завершенных циклов статей по разработке учебной, но рабочей СУБД "с нуля".
Если для вас всё описанное тривиально и прозрачно - моё почтение, возможно, вы просто не являетесь целевой аудиторией этой серии статей для тех, кому любопытно.
P.S. И, в конце концов, ценность представляет даже иллюстрация структуры B+ Tree, которую, заметьте, рисовал "от руки" 😎, потому что не нашел подходящих иллюстраций (достаточно точных и наглядных) в Google Search.
Более наглядные, на мой взгляд, иллюстрации есть в книге Database Internals (или, в русском переводе, Распределенные данные — там только вторая половина книги про распределенные СУБД, а первая про то как они устроены внутри) — главы вторая, четвертая и шестая. Ваша иллюстрация, тем кто не знает, что такое B+ дерево ничего особо не объясняет.
По поводу вашего вывода — реализация СУБД по описанному в начале тех заданию выполнима каждым, кто знаком с методами и алгоритмами описанными с цикле статей — то это очень смелое заявление. Сказать, что реализация документного хранилища возможна — да уместно, но не СУБД. Даже если оставить за скобками ACID, то надежность это неотъемлемое (опять же на мой взгляд) качество СУБД, потому что если последняя не дает гарантии получить из те же данные, которые ты ранее в ней сохранил то называть это системой управления базами данных некорректно.
Ценность цикла статей о Boson - это пошаговый разбор алгоритмов и подходов реализации минимальной документальной СУБД с key/value хранилищем для тех кому интересно как это устроено - вот тут вы тоже немного лукавите, например, в этой статье нет никакого пошагового разбора алгоритмов. Есть ссылки на ваш код, базовое описание алгоритма, но пошагового разбора нет.
Ценность цикла статей о Boson - это пошаговый разбор алгоритмов и подходов реализации минимальной документальной СУБД с key/value хранилищем для тех кому интересно как это устроено:
Я все-таки склоняюсь, что если писать серии статей про создание СУБД, то в первую очередь это задача “про дизайн”, а не про низкоуровневые алгоритмы, сначала стоит выделить сущности, описать их интерфейсами, реализовать какие то части алгоритмов на этих интерфейса, сейчас попробую в крантце объяснить что я имею ввиду.
Наша СУБД начинается с файловой страницы, поэтому для нее, собственно, так и введём такую сущность (я буду пропускать описание конструкторов/деструкторов и пр)
class IFilePage
{
public:
virtual byte_t* GetData() = 0;
virtual byte_t* GetSize() = 0;
virtual int64_t GetAddr() = 0;
}
typedef std::shared_ptr<IFilePage> FilePagePtr;
Собственно, для работы с файловыми страницами напрашивается какое-то файловое хранилище:
class IStorage
{
public:
virtual FilePagePtr GetNewFilePage() = 0;
virtual FilePagePtr ReadFilePage(int64_t nAddr) = 0;
virtual void WriteFilePage(FilePagePtr ptrPage) = 0;
}
typedef std::shared_ptr<IStorage> StoragePtr;
дальше нам нужна абстракция транзакции
class ITransaction : public IStorage
{
public:
virtual void Begin() = 0;
virtual void Commit() = 0;
virtual void Rollback() = 0;
};
Потом могут быть конкретные реализации механизмов транзакции простая двухфазная блокировка, WAL и т.д.
Следом определим B+ дерево, что то типа такого:
template<class TKey, class TValue, class TComporator>
class TBPlusTree{
private:
FilePagerPtr m_ptrFilePager;
int64_t m_nRootPage;
//тут класс итератор
class iterator
........
public:
TBPlusTree(FilePagerPtr ptrFilePager) { ........ }
void insert(const Tkey& key, const TValue& value) { ......... }
iterator begin(){}
iterator find(const TKey& key{}
iterator upper_bound(const TKey& key){}
iterator lower_bound() {}
};
По сути B+ дереву достаточно (в первом приближении, когда конечно начинается гонка за перфоманс, “красивый и простой” интерфейс сильно “портится”) интерфейса стораджа (за которым будет реализация конкретного типа транзакция) для создания, чтения и записи файловых страниц.
Потом имея шаблонное B+ дерево, можно вводить интерфейс для поля, где каждая запись имеет свой rowId, значение
class IField
{
public:
virtual void Insert(int64_t nRowID, IVariantPtr ptrVal) = 0;
virtual void Update(int64_t nRowID, IVariantPtr ptrVal) = 0;
virtual void Remove(int64_t nRowID) = 0;
virtual IVariantPtr Find(int64_t nRowID) = 0;
};
И простого индекса
class IIndex
{
public:
virtual void Insert(IVariantPtr ptrVal, int64_t nRowID ) = 0;
virtual void Update(IVariantPtr ptrOldVal, IVariantPtr ptrNewVal) = 0;
virtual void Remove(IVariantPtr ptrVal) = 0;
virtual int64 Find(IVariantPtr ptrVal) = 0;
};
В реальности, конечно, нужно реализовать итераторы для поля и индекса, плюс добавить методы в интерфейсы для получения имени поля, типа поля (число, строка, дата и т.д.), так же нужны интерфейсы для составных индексов и т.д.
Дальше у нас есть поля и индексы, можно делать таблицу
class ITable
{
public:
virtual IFieldPtr CreateFiled(....);
virtual IFieldPtr FindFiled(....);
virtual Indextr CreateIndexd(....);
........
};
После таблицы идет схема
class ISchema
{
public:
virtual ITablePtr GetTable(...) const = 0;
virtual void CreateTable(...)= 0;
virtual void DropTable(....)= 0;
};
Так же нужно будет добавить интерфейсы для описания рестрикшенов в схеме данных, разных отношений и пр.
Теперь когда будут определенны интерфейсы, можно начать делать их реализации, причем опять в первом варианте нам даже не нужно реальное B+дерево, под шаблоном B+ дерева может быть “обвернута” обычная std::map, под стораджем даже не файл, а просто буфер в памяти (это очень полезно в юнитестах с моками, когда например тестируется SQL движок)
Какая скорость вставки, поиска по миллиону json записей?
А чтобы ответить на этот вопрос, автор должен пойти немного дальше просто реализации B+ дерева (в которое он в примерах клал лишь строки) и построить реальный индекс по JSON структурам. А может и не один, если под поиском вы понимаете поиск по ключам JSON с учетом их вложенной структуры.
Без настройки размера узлов и размера кэша под производительность, запись происходит объективно медленно из-за построения дерева (всего 194Мб полезных данных записано, также записано 1275Мб включая служебную информацией за 12.7 сек). А поиск и получение 10 записей происходит быстро - 0.001 сек. Думаю, тут есть простор для оптимизаций. Но пока так, как есть.
Boson — разработка СУБД «с нуля» (итог)