Это будет серия постов, взятых из моих уроков Проектирование приложений с интенсивным использованием данных, написанных Мартином Клеппманном.

Голый минимальный

Мы начнем с создания более простой версии базы данных и продолжим наш анализ, построив ее.

#!/bin/bash
db_set(){
  echo "$1,$2" >> database
}
db_get(){
 grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

Работающий

База данных bash принимает пару ключей и значений как $ 1 и $ 2 для сохранения пары данных с помощью db_set. Это записывает «ключ, значение» в файл с именем «база данных». Поскольку это реализация только для добавления для хранения, если значение необходимо обновить, она просто добавляет новую строку обновленного «ключ, значение» в конец файла. db_get использует хвост, чтобы получить последнее вхождение ключа, чтобы показать последнее значение ключа

Анализ

Запись: db_set, являющийся простой реализацией только для добавления, эффективно работает для минимальной реализации, даже если он не влияет на реальные проблемы, с которыми мы сталкиваемся, например, управление параллелизмом. , освобождение неиспользуемого дискового пространства, обработка ошибок и частичная запись, стоимость записи составляет O (1)

Чтение: у db_get есть небольшая проблема с производительностью, когда записывается большое количество записей, это требует времени для поиска ключа, сканирование всего файла для каждого чтения, стоимость чтения O (n)

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

Хеш-индексы

Самый простой подход для начала - сохранить хеш-карту в памяти с каждым ключом, сопоставленным с байтовым смещением в файле данных, когда мы хотим прочитать, мы просто находим смещение, ищем местоположение и получаем значение для ключа . (см. Bitcask).

Анализ

Поскольку это смещает картину к парадигме смещения ключа, а не к предыдущей парадигме "ключ-значение", мы можем решить проблему переполнения дискового пространства, разбив журналы на сегменты и удалив повторяющиеся ключи (уплотнение, сделано в фоновом режиме). Комбинация добавления и слияния, представляющая собой одну последовательную операцию записи, работает быстрее, чем произвольная запись.

Однако у нас есть узкое место из-за того, что наши ключи, хранящиеся в оперативной памяти, должны уместиться в оперативной памяти. Это также неэффективно по любым диапазонным запросам для данных.

Анализ реального слова

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

Восстановление после сбоя: в таких случаях, вместо того, чтобы перестраивать сегмент для генерации хэш-карты, лучше было бы сохранить на диске моментальные снимки хэш-карты каждого сегмента.

Частично записанные записи: добавление контрольной суммы вместе с записью может решить эту проблему.

Параллелизм: будучи последовательным при записи, он допускает только один поток записи, но поддерживает одновременно несколько потоков чтения.

SSTable (сортированная таблица se̶g̶m̶e̶n̶t̶e̶d)

Это позволяет использовать логически структурированную последовательную запись с добавлением хэш-индекса с одной настройкой сортировки пар ключ-значение по ключу. При объединении n сегментов используется знаменитый алгоритм сортировка-слияние для получения одного объединенного сегмента с сортируемыми ключами.

Анализ

Теперь, чтобы использовать возможности сортировки, вместо того, чтобы иметь все карты смещения ключей для всех сохраненных данных, мы можем иметь разреженный индекс карты смещения клавиш с одним ключом каждые несколько килобайт сегмента. . Более того, сегменты могут быть сжаты перед записью на диск, таким образом, каждая запись разреженного массива отображается на начальный индекс одного сжатого блока, который записывается на диск.

Чтобы поддерживать сортированную структуру в памяти, мы можем использовать дерево AVL (memtable), которое обеспечивает вставку ключей в любом порядке, но считывает обратно в отсортированном порядке. . Чтобы справиться со случаем сбоя БД, мы можем иметь механизм резервного копирования нашего первоначального подхода, работающий параллельно на диске, ведя отдельный несортированный журнал каждой записи, который немедленно добавляется.

Анализ реального слова

Дерево LSM (лог-структурированное слияние) - это дерево, которое используется в LvelDB и RocksDB, механизмы хранения, построенные на его основе, называются механизмами хранения LSM. В Lucene индексации Elasticsearch и Solar используется аналогичная методология.

B-Tress

Давайте посмотрим на знаменитую структуру B-дерева, которая используется для структурирования хранилища на диске (обратите внимание, что предыдущие были в памяти).

Вместо того, чтобы разбивать базу данных на сегменты переменного размера, B-дерево разбивает базу данных на блоки или страницы размером примерно 4 КБ для выполнения чтения и написать. Каждая страница имеет адрес, и одно место на ней может ссылаться на другую страницу на диске. одна страница будет сделана корнем дерева B и может ссылаться на количество дочерних страниц. Когда на странице нет места для нового ключа, она разделяется на две наполовину заполненные страницы и обновляет родительскую страницу. Дерево B с n ключами будет иметь глубину O (log n).

Анализ

Давайте более подробно рассмотрим случай, когда страница заполнена и добавлен новый ключ, а не фактическая страница разделяется на две наполовину заполненные страницы путем копирования всех ссылок на эти 2 страницы, а родительская страница должна быть перезаписана на обновите 2 дочерние ссылки. При большом количестве движущихся частей один сбой БД может выбросить эту конструкцию. Чтобы сделать его устойчивым к сбоям, каждое изменение дерева перед применением записывается в файл, предназначенный только для добавления, это называется журнал повторов (журнал упреждающей записи). Необходимо добавить тщательный контроль параллелизма, чтобы предотвратить чтение дерева в несогласованном состоянии при использовании многопоточного чтения.

Оптимизация

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

Деревья LSM быстрее для записи, B-деревья быстрее для чтения.