Отличная подборка методов, как некий ориентир для тех кто думает, как оптимизировать. Кстати, кэширование каталогов товаров в e-commerce прям отлично работает и без него вообще никак.
Мне кажется, нераскрыто несколько вопросов: canary releasing отдельный "ад" при изменении схемы данных при обновлениях.
В финансовых системах бывают большие/длинные транзакции и требуется более высокая целостность данных, её обеспечение с масштабируемостью - тоже своеобразный квест. Было бы классно это раскрыть.
P.S. перевод терминов местами непривычный (gpt-like).
Мне кажется, что в статье не раскрыты несколько тем:
1) Реальная БД имеют некую степень локальности запросов ~10-15% от объема БД. Много операций осуществляется еще на уровне кэша, и даже с WAL не каждая операция сразу пишется в файл базы (fsync).
2) Асинхронный вывод же использует какой то механизм callback и сигналов, чтобы сообщить результат IO операции. Это вроде как означает, что в ACID транзакциях надо дождаться завершения всех операций. В таком случае даст ли асинхронность ускорение?
Вроде бы это язык D (dlang.org) - свободный от диалектов, гораздо более чистый и зрелый язык чем Carbon или Rust, но плохо освещенный. Хотя ему уже 25 лет.
Несколько широко известных проектов, не считая софта написанного для финансового сектора еще с начала 2000х:
Windows OS (~65M+ LoC)
Google Chrome: (~35M LoC)
Mozilla Firefox: (~20M LoC)
Adobe Photoshop: (~10M LoC)
Unreal Engine: (~10M LoC)
LLVM/Clang: (~5M LoC)
Blender (~4M LoC)
MySQL: (~2M LoC)
TensorFlow: (~2M LoC)
PostgreSQL: (~1M LoC)
И это далеко не всё. Если предположить, что в промышленных проектах пишут в среднем 14-15 строк кода в день (это с учетом всего цикла CI/CD). То на переписывание перечисленного нужно около 38732 человеко/года. Или около $3.8 млрд с учетом накладных расходов. И то, если все это напишут с первого раза и без багов. В реальности на порядок больше. Так что гипотеза о триллионах расходов вполне оправдана.
Упрощенный тест сделал - вставка 1 млн JSON, каждое размером 204 байта и затем поиск и получение данных 10 записей начиная с указанного ID (взял простое 6-значное число)
Без настройки размера узлов и размера кэша под производительность, запись происходит объективно медленно из-за построения дерева (всего 194Мб полезных данных записано, также записано 1275Мб включая служебную информацией за 12.7 сек). А поиск и получение 10 записей происходит быстро - 0.001 сек. Думаю, тут есть простор для оптимизаций. Но пока так, как есть.
Вывод - реализация СУБД по описанному в начале тех заданию выполнима каждым, кто знаком с методами и алгоритмами описанными с цикле статей.
Ценность цикла статей о Boson - это пошаговый разбор алгоритмов и подходов реализации минимальной документальной СУБД с key/value хранилищем для тех кому интересно как это устроено:
Вторая ценность - это сам факт завершенности цикла статей и примера реализации. Этот вклад в хабы HABR, где я не нашел завершенных циклов статей по разработке учебной, но рабочей СУБД "с нуля".
Если для вас всё описанное тривиально и прозрачно - моё почтение, возможно, вы просто не являетесь целевой аудиторией этой серии статей для тех, кому любопытно.
P.S. И, в конце концов, ценность представляет даже иллюстрация структуры B+ Tree, которую, заметьте, рисовал "от руки" 😎, потому что не нашел подходящих иллюстраций (достаточно точных и наглядных) в Google Search.
Да, при удалении записей файл меньше не становится. Удаленные записи оставляют "пустоты" в файлах (файл базы данных не дефрагментируем, чтобы не проиграть в скорости удаления), но эти "пустоты" используются повторно при вставке новых записей, если ёмкость удаленной записи достаточна для хранения вновь создаваемой.
Это даёт некий сбалансированный компромис между скоростью работы и эффективностью использования свободного пространства на диске. Многие СУБД используют аналогичную логику.
Об этом подробно рассказывал в предыдущей части статьи вот тут:
Hash Map использует хэш-функцию для определения позиции в фиксированном массиве, элементы которого могут быть связанными списками для разрешения коллизий хэш функции:
Hash Map не сохраняет порядок ключей, что делает его непригодным для диапазонных запросов и сортировки, в отличие от B+ Tree.
Hash Map менее эффективно использует дисковое пространство при работе с диском, так как требует предварительной аллокации массива, вне зависимости от количества элементов.
Вы правы. В масштабах промышленной СУБД образовательный пример Boson лишь малая часть - скорее всего 1%.
Из перечисленного о том как делать компилятор и виртуальную машину (VM) для условного Domain Specific Language (DSL) рассказывал в отдельной серии статей (можно и простое подмножество SQL сделать):
Теоретически можно. Чтобы увеличить эффективность придётся большей ключей/значений держать в узлах и добавить двусвязные списки. Получится B+ Tree.
Использование mmap упростит реализацию, но мы становимся зависимыми от механизмов подкачки в ОС - сложно применять оптимизационные стратегии управления кэшированием. Добавим сюда необходмые механизмы защиты для многопоточности на уровне узлов и страниц - всё станет сложнее.
Вот статья которая объясняет почему использование mmap в DBMS может быть не очень хорошей идеей:
1) std::map — сбалансированное бинарное дерево (красно-черное дерево), очень эффективно на относительно малых объемах данных в оперативной памяти, но менее эффективно по памяти и не оптимально для больших данных, тогда как B+ Tree имеет узлы с множеством ключей и связные листья, что обеспечивает лучшую плотность хранения и быстрые диапазонные запросы, оптимально для работы с большими объемами данных.
2) во вторых std::map - это реализация для оперативной памяти, а в Boson B+ Tree сохраняет на диске с оптимизацией количества операций ввода/вывода (снизу реализация хранилища записей и алгоритмы кэширования).
Преимущество - наглядность реализации. Хоть sqlite самая легкая СУБД, не самая простая, если почитаете исходный код, с ходу не поймете что и почему. В случае с Boson относительно не сложно разобраться, а потом и понять как работают промышленные СУБД.
Спасибо за обратную связь. А какой информации не хватило или какой вопрос не раскрыт? Алгоритм расписал. Думаю, вы язык и основы знаете хорошо. Хотел не перегружать читателя очевидностями, но в исходном коде почти каждую строчку прокомментировал (на английском), если будут интересны детали реализации. Даже специально жертвовал местами производительностью в пользу наглядности.
У каждого языка своя ниша. Rust и Golang сравнивать с C++ некорректно, они не то что не мультипарадигменные, они даже не ООП. Rust - больше альтернатива C.
Реальной альтернативой C++ мог бы стать Dlang, но к сожалению за ним не стоят корпорации и о нём мало кто знает. На мой взгляд гораздо стройнее Carbon, Swift.
Если сил хватит дожать заявленнный функционал, то обязательно. Алгоритм B+ Tree реализовал пока в оперативке, но пока парюсь с его работой в файле (сериализацией/десериализацией).
Да, можно на индексе самой файловой системы, но тут же вся соль в "реализации с нуля". Boson хоть и игрушечная, но всё таки СУБД. И в ней будет настоящий B+ Tree индекс с бинарным поиском в узлах, чтобы достичь сложности O(log2 t logt n). Пока реализация будет только для ID, но тот же механизм может быть применён и по другим полям документов в будущем.
Отличная подборка методов, как некий ориентир для тех кто думает, как оптимизировать. Кстати, кэширование каталогов товаров в e-commerce прям отлично работает и без него вообще никак.
Мне кажется, нераскрыто несколько вопросов: canary releasing отдельный "ад" при изменении схемы данных при обновлениях.
В финансовых системах бывают большие/длинные транзакции и требуется более высокая целостность данных, её обеспечение с масштабируемостью - тоже своеобразный квест. Было бы классно это раскрыть.
P.S. перевод терминов местами непривычный (gpt-like).
На диаграмме всё верно, это вложенные вызовы.
Мне кажется, что в статье не раскрыты несколько тем:
1) Реальная БД имеют некую степень локальности запросов ~10-15% от объема БД. Много операций осуществляется еще на уровне кэша, и даже с WAL не каждая операция сразу пишется в файл базы (fsync).
2) Асинхронный вывод же использует какой то механизм callback и сигналов, чтобы сообщить результат IO операции. Это вроде как означает, что в ACID транзакциях надо дождаться завершения всех операций. В таком случае даст ли асинхронность ускорение?
Вроде бы это язык D (dlang.org) - свободный от диалектов, гораздо более чистый и зрелый язык чем Carbon или Rust, но плохо освещенный. Хотя ему уже 25 лет.
Несколько широко известных проектов, не считая софта написанного для финансового сектора еще с начала 2000х:
Windows OS (~65M+ LoC)
Google Chrome: (~35M LoC)
Mozilla Firefox: (~20M LoC)
Adobe Photoshop: (~10M LoC)
Unreal Engine: (~10M LoC)
LLVM/Clang: (~5M LoC)
Blender (~4M LoC)
MySQL: (~2M LoC)
TensorFlow: (~2M LoC)
PostgreSQL: (~1M LoC)
И это далеко не всё. Если предположить, что в промышленных проектах пишут в среднем 14-15 строк кода в день (это с учетом всего цикла CI/CD). То на переписывание перечисленного нужно около 38732 человеко/года. Или около $3.8 млрд с учетом накладных расходов. И то, если все это напишут с первого раза и без багов. В реальности на порядок больше. Так что гипотеза о триллионах расходов вполне оправдана.
Без настройки размера узлов и размера кэша под производительность, запись происходит объективно медленно из-за построения дерева (всего 194Мб полезных данных записано, также записано 1275Мб включая служебную информацией за 12.7 сек). А поиск и получение 10 записей происходит быстро - 0.001 сек. Думаю, тут есть простор для оптимизаций. Но пока так, как есть.
Вывод - реализация СУБД по описанному в начале тех заданию выполнима каждым, кто знаком с методами и алгоритмами описанными с цикле статей.
Ценность цикла статей о 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.
Да, при удалении записей файл меньше не становится. Удаленные записи оставляют "пустоты" в файлах (файл базы данных не дефрагментируем, чтобы не проиграть в скорости удаления), но эти "пустоты" используются повторно при вставке новых записей, если ёмкость удаленной записи достаточна для хранения вновь создаваемой.
Это даёт некий сбалансированный компромис между скоростью работы и эффективностью использования свободного пространства на диске. Многие СУБД используют аналогичную логику.
Об этом подробно рассказывал в предыдущей части статьи вот тут:
https://habr.com/ru/articles/712896/
Спасибо за вопросы!
Hash Map использует хэш-функцию для определения позиции в фиксированном массиве, элементы которого могут быть связанными списками для разрешения коллизий хэш функции:
Hash Map не сохраняет порядок ключей, что делает его непригодным для диапазонных запросов и сортировки, в отличие от B+ Tree.
Hash Map менее эффективно использует дисковое пространство при работе с диском, так как требует предварительной аллокации массива, вне зависимости от количества элементов.
Вы правы. В масштабах промышленной СУБД образовательный пример Boson лишь малая часть - скорее всего 1%.
Из перечисленного о том как делать компилятор и виртуальную машину (VM) для условного Domain Specific Language (DSL) рассказывал в отдельной серии статей (можно и простое подмножество SQL сделать):
https://habr.com/ru/articles/571758/
WAL, транзакции, клиент/сервер - это большое путешествие которое на текущем этапе избыточно для исследования основ СУБД.
Теоретически можно. Чтобы увеличить эффективность придётся большей ключей/значений держать в узлах и добавить двусвязные списки. Получится B+ Tree.
Использование mmap упростит реализацию, но мы становимся зависимыми от механизмов подкачки в ОС - сложно применять оптимизационные стратегии управления кэшированием. Добавим сюда необходмые механизмы защиты для многопоточности на уровне узлов и страниц - всё станет сложнее.
Вот статья которая объясняет почему использование mmap в DBMS может быть не очень хорошей идеей:
https://www.cidrdb.org/cidr2022/papers/p13-crotty.pdf
В двух словах:
1) std::map — сбалансированное бинарное дерево (красно-черное дерево), очень эффективно на относительно малых объемах данных в оперативной памяти, но менее эффективно по памяти и не оптимально для больших данных, тогда как B+ Tree имеет узлы с множеством ключей и связные листья, что обеспечивает лучшую плотность хранения и быстрые диапазонные запросы, оптимально для работы с большими объемами данных.
2) во вторых std::map - это реализация для оперативной памяти, а в Boson B+ Tree сохраняет на диске с оптимизацией количества операций ввода/вывода (снизу реализация хранилища записей и алгоритмы кэширования).
Мне так видится.
Преимущество - наглядность реализации. Хоть sqlite самая легкая СУБД, не самая простая, если почитаете исходный код, с ходу не поймете что и почему. В случае с Boson относительно не сложно разобраться, а потом и понять как работают промышленные СУБД.
Спасибо за обратную связь. А какой информации не хватило или какой вопрос не раскрыт? Алгоритм расписал. Думаю, вы язык и основы знаете хорошо. Хотел не перегружать читателя очевидностями, но в исходном коде почти каждую строчку прокомментировал (на английском), если будут интересны детали реализации. Даже специально жертвовал местами производительностью в пользу наглядности.
Наконец-то завершил этот цикл статей. Вот итоговая статья: https://habr.com/ru/articles/856876/
Только завершил всю разработку:
https://habr.com/ru/articles/856876/
У каждого языка своя ниша. Rust и Golang сравнивать с C++ некорректно, они не то что не мультипарадигменные, они даже не ООП. Rust - больше альтернатива C.
Реальной альтернативой C++ мог бы стать Dlang, но к сожалению за ним не стоят корпорации и о нём мало кто знает. На мой взгляд гораздо стройнее Carbon, Swift.
https://dlang.org/
Только после того как вы по индексу нашли где запись.
Если сил хватит дожать заявленнный функционал, то обязательно. Алгоритм B+ Tree реализовал пока в оперативке, но пока парюсь с его работой в файле (сериализацией/десериализацией).
Да, можно на индексе самой файловой системы, но тут же вся соль в "реализации с нуля". Boson хоть и игрушечная, но всё таки СУБД. И в ней будет настоящий B+ Tree индекс с бинарным поиском в узлах, чтобы достичь сложности O(log2 t logt n). Пока реализация будет только для ID, но тот же механизм может быть применён и по другим полям документов в будущем.