Лог-структурированное хранилище

Дерево слияния с логарифмической структурой (LSM-деревья) + хэш-индекс

Описанный здесь алгоритм, по сути, используется в Riak/Bitcask. Для внутреннего использования используется журнал, который представляет собой файл данных только для добавления, где каждая строка содержит пару "ключ-значение". Добавление к файлу, как правило, очень эффективно (O(1)), однако для получения значения необходимо просмотреть весь файл базы данных от начала до конца в поисках вхождений ключа (O(n)).

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

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

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

Дизайн только для добавления оказывается хорошим по нескольким причинам:

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

Некоторые из вопросов, которые важны при реализации:

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

Индекс хеш-таблицы также имеет ограничения:

  • Должен уместиться в памяти
  • Запросы диапазона неэффективны.

LSM + SSTables

Описанный здесь алгоритм, по сути, используется в LevelDB [6] и RocksDB. Подобные механизмы хранения используются в Cassandra и HBase.

Формат файлов сегментов изменен: последовательность пар ключ-значение сортируется по ключу (таблица сортированных строк или SSTable). У этого есть несколько больших преимуществ по сравнению с сегментами журнала с хэш-индексами:

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

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

Чтобы обслужить запрос на чтение, сначала попытайтесь найти ключ в memtable, затем в самом последнем сегменте на диске, затем в следующем более старом сегменте и т. д. Время от времени запускайте процесс слияния и сжатия. Чтобы восстановить memtable после сбоя, мы можем вести отдельный журнал на диске, к которому немедленно добавляется каждая запись, как и в предыдущем разделе.

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

Постраничное хранилище

B-деревья

Они по-прежнему остаются стандартной реализацией индексов почти во всех реляционных базах данных. Как и SSTables, B-деревья хранят пары ключ-значение, отсортированные по ключу, но имеют совершенно другую философию разработки. Он разбивает базу данных на блоки или страницы фиксированного размера. Одна страница ссылаться на другую — аналогично указателю, и находится на диске, а не в памяти. В конце концов мы переходим на страницу, содержащую отдельные ключи (конечная страница), которая либо содержит значение для каждого встроенного ключа, либо содержит ссылки на страницы, на которых можно найти эти значения. Число ссылок на дочерние страницы известно как коэффициент ветвления. Большинство баз данных могут вписаться в B-дерево с глубиной в три или четыре уровня, поэтому вам не нужно нужно следовать многим ссылкам на страницы, чтобы найти страницу. Четырехуровневое дерево страниц размером 4 КБ с коэффициентом ветвления 500 может хранить до 256 ТБ.

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

Чтобы сделать базу данных устойчивой к сбоям, реализации B-дерева обычно включают дополнительную структуру данных на диск: журнал с упреждающей записью (WAL, также известный как журнал повторов). Когда база данных восстанавливается после сбоя, этот журнал используется для восстановления B-дерева до согласованного состояния.

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

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

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

Сравнение B-деревьев и LSM-деревьев

Как правило, LSM-деревья обычно быстрее при записи, тогда как B-деревья считаются более быстрыми при чтении.

Чтение обычно медленнее в LSM-деревьях, потому что они должны проверить несколько различных структур данных и SSTables на разных этапах уплотнения. Время отклика запросов к механизмам хранения с логической структурой иногда может быть довольно большим, а B-деревья могут быть более предсказуемыми. Кроме того, LSM-деревья обычно способны поддерживать более высокую запись пропускную способность, чем B-деревья, отчасти потому, что они иногда иметь меньшее усиление записи (хотя это зависит от конфигурации механизма хранения и рабочей нагрузки) и последовательно записывать компактные файлы SSTable, а не перезаписывать несколько страниц в дереве. LSM-деревья могут быть сжаты лучше, поэтому на диске часто создаются файлы меньшего размера, чем B-деревья.

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