Boson — разработка СУБД «с нуля» (итог)

Напомню о том, что цель проекта Boson — это разработка встроенного движка базы данных документов JSON, написанный на C++. Основные возможности:

• Стандартное хранилище JSON-документов в формате ключ/значениями с постоянным хранением на диске. Размер документов до 4Gb.

• Быстрый поиск документов по ID с использованием индекса B+ дерева.

• Поддержка курсоров для линейного обхода записей.

• База данных в одном файле, без временных файлов.

• Простое, чистое и легкое в использовании API.

• Самодостаточный и не требующий настройки.

В предыдущих двух статьях мы прошли шаги от кэширования файлового ввода/вода (часть I) до построенного на его базе хранилища записей произвольной длины (часть II) с проверкой целостности, возможностью получения записей списком и повторным использованием свободного места. Теперь мы переходим к завершающей части и «сердцу» СУБД — индексу.

Зачем нужен индекс: предположим, что в базе есть 1 млрд не отсортированных записей документов, тогда поиск конкретного документа по ID потребует O(n) операций, то есть до 1 млрд операций в худшем случае. Однако, если бы документы в базе были бы отсортированы по ID, то поиск в сортированной базе, тем же бинарным поиском занял бы O(log n) занял бы 30 операций. Что, теоретически, на базе в 1 млрд записей будет в 33.3 млн раз быстрее.

Замечательная мысль, но осталось понять как в случае вставки документов с произвольным ID записи в базе всегда оставались отсортированными без необходимости «раздвигать» данные в базе при каждой вставке или обновлении записи. Это уже не так тривиально.

Для решения этой проблемы в 1972 году Rudolf Bayer и Edward McCreight была впервые представлена идея B-деревьев, которые являются основой для B+ деревьев — это расширение концепции B-деревьев, в которых все ключи на уровне листьев объединены в связанный список (Linked List), что делает их более эффективными для операций последовательного доступа. И, конечно, алгоритм B+ деревьев даёт выдающуюся производительность: поиск — O(log N), вставка — O(log N), удаление — O(log N).

Для начала немного погрузимся в теорию о том как устроены B+ деревья и какие операции нужны чтобы поддерживать дерево в целостном и сбалансированном виде:

B+ дерево состоит из внутренних узлов и листовых узлов. Внутренние узлы хранят только ключи для направления поиска, в то время как сами данные содержатся в листовых узлах:

• Внутренние узлы (Inner Node): Содержат ключи и указатели на дочерние узлы, но не хранят реальные данные. Каждый внутренний узел может содержать от ⌈M/2⌉ до M-1 ключей и M дочерних узлов. Каждый ключ в узле разделяет дочерние узлы: левый дочерний узел содержит ключи, меньшие ключа родительского узла, а правый дочерний узел содержит ключи, большие или равные ключу родительского узла.

• Листовые узлы (Leaf Node): Хранят пары ключей и указателей на данные. Связаны между собой в двусвязный список для эффективных диапазонных запросов. Каждый листовой узел может также содержать от ⌈M/2⌉ до M-1 ключей и M-1 значений.

Чтобы при произвольных вставках, удалениях и изменениях записей поддерживалась сбалансированность и отсортированность B+ дерева, выполняются следующие операции:

1. Операция поиска: Для поиска определенного ключа в B+ дереве начинают с корневого узла. Сравнивают целевой ключ с ключами в текущем узле, чтобы определить соответствующий дочерний узел. Если целевой ключ меньше, переходят к левому дочернему узлу; если больше или равен, переходят к правому дочернему узлу. Этот процесс повторяется, пока не будет достигнут нужный листовой узел, где и завершается поиск. Поскольку B+ дерево сбалансировано, сложность поиска составляет O(log n).

2. Операция вставки: Вставка ключа начинается с поиска подходящего листового узла с использованием процедуры поиска. Затем ключ вставляется в листовой узел в правильном отсортированном положении. Если узел превышает свою максимальную вместимость (M-1 ключей), происходит разделение. Узел делится на два, и половина ключей переходит в новый дочерний узел. Средний ключ поднимается в родительский узел. Если родительский узел также переполняется, это может вызвать дальнейшие разделения, которые могут распространиться до корня, потенциально увеличивая высоту дерева.

3. Операция удаления: Удаление ключа начинается с поиска целевого ключа в соответствующем листовом узле. Ключ удаляется, но если это приводит к тому, что узел содержит меньше ключей, чем минимум (⌈M/2⌉), требуется корректировка. Дерево может заимствовать ключ у соседнего узла, если у него больше минимального количества ключей. Если заимствование невозможно, узел сливается с соседним, и ключ из родительского узла удаляется или корректируется соответственно. Этот процесс слияния может распространяться вверх по дереву, если необходимо, чтобы сохранить баланс дерева.

4. Диапазонные запросы: B+ деревья особенно хорошо подходят для диапазонных запросов благодаря связной структуре листовых узлов. Чтобы выполнить диапазонный запрос, начинают с поиска первого ключа в нужном диапазоне, используя процедуру поиска. После нахождения начального ключа переходят по двусвязному списку листовых узлов, пока не достигнут конца диапазона. Эта связная структура делает сканирование последовательности значений эффективным и простым.

5. Операция обновления: Обновление значения ключа включает поиск ключа в соответствующем листовом узле с использованием поиска. После нахождения ключа связанное значение изменяется. Если значение требует перемещения из-за ограничений по вместимости записей, может быть выделена новая запись в хранилище без изменения ключа.

Операции вставки и удаления могут создавать ситуацию, когда возникает переполнение узла или, наоборот, недостаток элементов. В таких случаях выполняются операции поддерживающие сбалансированность B+ дерева:

1. Разделение (Split) — выполняется когда узел в B+ дереве превышает свою максимальную вместимость (M-1 ключей). Процесс деления заключается в следующем:

   1. Узел делится на два, при этом половина ключей остается в исходном узле, а другая половина переносится в новый узел.

   2. Продвижение ключа вверх (Push Key Up) — средний ключ из исходного узла перемещается в родительский узел. Это обеспечивает обновление родительского узла, чтобы отразить изменения структуры дерева.

   3. Если родительский узел также переполняется, процесс разделения и продвижения ключа вверх может распространяться вверх по дереву, вплоть до корня (root). Если корень разделяется, создается новый корень, увеличивая высоту дерева. То есть дерево по количеству уровней растёт от корня, а не от листьев.

   Пример: Если в узле M=5 и он содержит 5 ключей (1, 2, 3, 4, 5), при переполнении узел делится на два: (1, 2) и (4, 5), а ключ 3 продвигается вверх.

2. Слияние (Merge) — выполняется когда в результате удаления ключа количество ключей в узле становится меньше минимально допустимого значения (⌈M/2⌉). Процесс слияния включает:

   1. Объединение узла с его соседним узлом (левым или правым), чтобы создать один узел.

   2. Ключ из родительского узла, который разделял эти два узла, перемещается вниз и становится частью объединенного узла.

   3. Если после слияния родительский узел остается с недостаточным количеством ключей, операция слияния может распространиться вверх по дереву.

      Пример: Если два соседних листовых узла содержат ключи (1, 2) и (3, 4), они могут объединиться в один узел (1, 2, 3, 4), и разделяющий ключ из родительского узла удаляется.

3. Заимствование у соседнего узла (Borrow from Sibling) — это операция, выполняемая, когда узел содержит меньше минимально допустимого числа ключей (⌈M/2⌉), но его соседний узел (левый или правый) имеет больше ключей, чем минимум.

   1. Ключ из родительского узла перемещается вниз в узел с недостаточным количеством ключей.

   2. Соседний узел передает один из своих ключей в родительский узел для поддержания баланса.

   Пример: Если узел содержит 1 ключ, а его соседний узел содержит 3 ключа, то один ключ может быть передан из соседнего узла, а родительский узел обновляется соответствующим образом.

Эти операции важны для поддержания сбалансированности B+ дерева, чтобы все узлы оставались сбалансированными и все листовые узлы находились на одном уровне, обеспечивая сложность операций O(log n).

Визуализацию как работает этот алгоритм B+ дерева можно посмотреть здесь.

Теперь приступим к реализации самого алгоритма, в данной статье я приведу лишь заголовок, а саму реализацию B+ Tree индекса вы можете посмотреть здесь.

Вот какой заголовочный файл получился у меня при реализации индекса B+ Tree:

namespace Boson {       constexpr uint64_t TREE_ORDER = 5;     constexpr uint64_t MAX_DEGREE = TREE_ORDER - 1;     constexpr uint64_t MIN_DEGREE = TREE_ORDER / 2;     constexpr uint32_t KEY_NOT_FOUND = -1;      typedef enum : uint32_t { INNER = 1, LEAF = 2 } NodeType;     typedef enum : uint32_t { KEYS = 1, CHILDREN = 2, VALUES = 2 } NodeArray;       //-------------------------------------------------------------------------      class NodeData {     public:         uint64_t parent;         uint64_t leftSibling;         uint64_t rightSibling;         NodeType nodeType;         uint32_t keysCount;         union {             uint32_t childrenCount;             uint32_t valuesCount;         };         uint64_t keys[TREE_ORDER];         union {             uint64_t children[TREE_ORDER];             uint64_t values[TREE_ORDER];         };          NodeData();          void pushBack(NodeArray mode, uint64_t value);         void insertAt(NodeArray mode, uint32_t index, uint64_t value);         void deleteAt(NodeArray mode, uint32_t index);         void resize(NodeArray mode, uint32_t newSize);     };      //-------------------------------------------------------------------------      class BalancedIndex;     class LeafNode;     class InnerNode;      class Node {         friend class BalancedIndex;         friend class LeafNode;         friend class InnerNode;     public:         Node(BalancedIndex& bi, NodeType type);                 ~Node();         uint64_t getPosition();         uint64_t persist();         NodeType getNodeType();         uint32_t getKeyCount();         bool     isRootNode();         bool     isOverflow();         bool     isUnderflow();         bool     canLendAKey();         uint64_t getKeyAt(uint32_t index);         void     setKeyAt(uint32_t index, uint64_t key);         uint64_t getParent();         void     setParent(uint64_t parentPosition);         uint64_t getLeftSibling();         void     setLeftSibling(uint64_t siblingPosition);         uint64_t getRightSibling();         void     setRightSibling(uint64_t siblingPosition);         uint64_t dealOverflow();         uint64_t dealUnderflow();      protected:          BalancedIndex& index;         // reference to index            uint64_t position;            // offset in file         NodeData data;                // node data         bool isPersisted;             // is data persisted to storage                      Node(BalancedIndex& bi);         static std::shared_ptr<Node> loadNode(BalancedIndex& bi, uint64_t offsetInFile);         static void deleteNode(BalancedIndex& bi, uint64_t offsetInFile);          virtual uint32_t search(uint64_t key) = 0;         virtual uint64_t split() = 0;         virtual uint64_t pushUpKey(uint64_t key, uint64_t leftChild, uint64_t rightChild) = 0;         virtual uint64_t mergeChildren(uint64_t leftChild, uint64_t rightChild) = 0;         virtual void     mergeWithSibling(uint64_t key, uint64_t rightSibling) = 0;         virtual uint64_t borrowFromSibling(uint64_t key, uint64_t sibling, uint32_t borrowIndex) = 0;         virtual void     borrowChildren(uint64_t borrow0er, uint64_t lender, uint32_t borrowIndex) = 0;         virtual std::shared_ptr<std::string> toString() = 0;     };      //-------------------------------------------------------------------------      class InnerNode : public Node {         friend class BalancedIndex;         friend class Node;         friend class LeafNode;             public:         InnerNode(BalancedIndex& bi);         InnerNode(BalancedIndex& bi, uint64_t offsetInFile, NodeData& loadedData);         ~InnerNode();         uint32_t   search(uint64_t key);         uint64_t   getChildAt(uint32_t index);         void       setChildAt(uint32_t index, uint64_t childNode);         void       insertAt(uint32_t index, uint64_t key, uint64_t leftChild, uint64_t rightChild);         void       deleteAt(uint32_t index);                 NodeType   getNodeType();         std::shared_ptr<std::string> toString();     protected:         uint64_t   split();         uint64_t   pushUpKey(uint64_t key, uint64_t leftChild, uint64_t rightChild);         void       borrowChildren(uint64_t borrower, uint64_t lender, uint32_t borrowIndex);         uint64_t   borrowFromSibling(uint64_t key, uint64_t sibling, uint32_t borrowIndex);         uint64_t   mergeChildren(uint64_t leftChild, uint64_t rightChild);         void       mergeWithSibling(uint64_t key, uint64_t rightSibling);     };       //-------------------------------------------------------------------------      class LeafNode : public Node {         friend class BalancedIndex;         friend class Node;         friend class InnerNode;     public:         LeafNode(BalancedIndex& bi);         LeafNode(BalancedIndex& bi, uint64_t offsetInFile, NodeData& loadedData);         ~LeafNode();         uint32_t search(uint64_t key);         std::shared_ptr<std::string> getValueAt(uint32_t index);         void     setValueAt(uint32_t index, const std::string& value);         bool     insertKey(uint64_t key, const std::string& value);         bool     insertKey(uint64_t key, uint64_t valuePosition);         void     insertAt(uint32_t index, uint64_t key, const std::string& value);         void     insertAt(uint32_t index, uint64_t key, uint64_t valuePosition);         bool     deleteKey(uint64_t key);         void     deleteAt(uint32_t index);                 NodeType getNodeType();         std::shared_ptr<std::string> toString();     protected:         uint64_t split();         uint64_t pushUpKey(uint64_t key, uint64_t leftChild, uint64_t rightChild);         void     borrowChildren(uint64_t borrower, uint64_t lender, uint32_t borrowIndex);         uint64_t mergeChildren(uint64_t leftChild, uint64_t rightChild);         void     mergeWithSibling(uint64_t key, uint64_t rightSibling);         uint64_t borrowFromSibling(uint64_t key, uint64_t sibling, uint32_t borrowIndex);         uint32_t searchPlaceFor(uint64_t key);     };      //-------------------------------------------------------------------------       class IndexHeader {     public:         uint64_t treeOrder;       // Tree order         uint64_t rootPosition;    // Root node position in the storage file         uint64_t recordsCount;    // Total records count         uint64_t indexCounter;    // Index key counter     };       class BalancedIndex {         friend class Node;         friend class LeafNode;         friend class InnerNode;         friend class BosonAPI;     public:         BalancedIndex(RecordFileIO& rf);         ~BalancedIndex();                 uint64_t size();          bool insert(uint64_t key, const std::string& value);         bool update(uint64_t key, const std::string& value);         std::shared_ptr<std::string> search(uint64_t key);         bool erase(uint64_t key);          std::pair<uint64_t, std::shared_ptr<std::string>> first();         std::pair<uint64_t, std::shared_ptr<std::string>> last();         std::pair<uint64_t, std::shared_ptr<std::string>> next();         std::pair<uint64_t, std::shared_ptr<std::string>> previous();          void printTree();              protected:          uint64_t getNextIndexCounter();         RecordFileIO& getRecordsFile();         std::shared_ptr<LeafNode> findLeafNode(uint64_t key);                         void updateRoot(uint64_t newRootPosition);         void persistIndexHeader();         void printTreeLevel(std::shared_ptr<Node> node, int level);      private:         RecordFileIO& recordsFile;         IndexHeader indexHeader;         std::shared_ptr<Node> root;          std::shared_ptr<LeafNode> cursorNode;         uint32_t cursorIndex;         bool isTreeChanged;     };   }

Напишем реализацию NodeData, Node, InnerNode, LeafNode, BalancedIndex и проверим как строится B+ дерево…

Каждый алгоритм и его техническая реализации в отдельности не представляли большой сложности (бинарный поиск, двусвязные списки, деревья, рекурсии многие знают со школы), пока всё это делалось в оперативной памяти и по отдельности. Однако, чтобы отладить и заставить это работать на диске (вместо new/delete нужно было использовать аналог хранения на диске — RecordFileIO), всё вместе и слаженно — это был вызов, который занял почти месяц на осознание и разработку. Тут видимо уже мои интеллектуальные ограничения. Очень сильно выручили умные указатели (smart pointers) чтобы проуправлять постоянной загрузкой и выгрузкой узлов из памяти и сохранением их на диске не создав утечку памяти. Спасибо разработчикам языка C++.

Итак посмотрим, как работает реализация. Сработало. На логах в консоли можно разглядеть структуру дерева, и ссылки на позиции в файле базы данных:

Завершив реализацию посмотрим как это примерно работает. Для статьи и удобства разглядывания скриншота взял малое количество записей, в реальных тестах проверял на больших объемах. Вставим N записей, последовательно вытащим их (проверим, что поиск работает), удалим N записей, вставим заново N записей (проверив что свободное место используется), удалим и посмотрим как отработало.

Теперь когда все три основных слоя базы данных реализованы (cache, storage и index), можно реализовать простой API и завершить этот образовательный проект.

namespace Boson {      class BosonAPI {     public:          BosonAPI();         ~BosonAPI();          bool open(char* filename, bool readOnly = false);         bool close();          uint64_t size();         bool isExists(uint64_t key);          uint64_t insert(std::string value);         bool insert(uint64_t key, std::string value);         std::shared_ptr<std::string> get(uint64_t key);         bool erase(uint64_t key);          std::pair<uint64_t, std::shared_ptr<std::string>> first();         std::pair<uint64_t, std::shared_ptr<std::string>> last();         std::pair<uint64_t, std::shared_ptr<std::string>> next();         std::pair<uint64_t, std::shared_ptr<std::string>> previous();          double getCacheHits();          void printTreeState();      private:         CachedFileIO* cachedFile;         RecordFileIO* recordFile;         BalancedIndex* balancedIndex;         bool isReadOnly;     };  }

Вот и всё! Цель проекта достигнута. Исходный код Boson вы можете посмотреть здесь. Спасибо что дочитали до конца!

Disclaimer: важно понимать, что это лишь учебный пример реализации СУБД движимый моим любопытством и поделиться впечатлениями от исследования. Для применения Boson в ваших реальных проектах необходимо реализовать защиту для многопоточности (locks) и на уровне хранилища/процессов. И нужно ли это делать — вопрос. Посмотрим.