Каждый день появляется так много новых технологий, чтобы решить одну и ту же проблему или немного разные проблемы. Чтобы лучше понять эти технологии в нашем случае использования, мы должны сначала понять их внутреннее устройство. Поэтому я напишу серию статей, чтобы помочь нам лучше понять внутреннее устройство. В центре внимания этой статьи будет не одна конкретная технология, а их группа.
Последовательная запись выполняется намного быстрее, чем произвольная запись в память. Потому что случайная запись влечет за собой больше времени поиска. При создании любых баз данных необходимо учитывать следующие моменты: иметь высокую пропускную способность записи и иметь быстрый доступ для чтения.
Чтобы иметь базу данных с высокой пропускной способностью записи, трудно превзойти производительность простого добавления в файл, потому что это простейшие возможные операции записи. Чтобы сделать доступ к быстрому чтению, мы используем структуры индексации. Мы создаем индексы для оптимизации чтения. Поддержание индексации влечет за собой большие накладные расходы. Любой индекс замедляет запись, поскольку индекс необходимо обновлять при каждой записи; это решающий компромисс в системах хранения.
ХЭШ-ИНДЕКСЫ
Давайте создадим систему хранения пар "ключ-значение" только с добавлением в файл. Кроме того, поддерживайте смещение ключевого байта Hashmap, простую стратегию индексации. В этом случае оптимизированы как запись, так и чтение, но при таком подходе возникает несколько проблем. Поскольку мы только добавляем в файл, скоро нам не хватит места на диске. Более того, по мере увеличения количества уникальных ключей нам становится все труднее поддерживать их в памяти.
Чтобы решить проблему с нехваткой места на диске, мы можем разбить файл на сегменты. Сегмент имеет определенный размер; мы продолжаем запись в новый сегмент после того, как сегмент заполнен. Во время записи мы можем выполнять уплотнение сегментов.
Сжатие означает удаление повторяющихся ключей в журнале с сохранением только самых последних обновлений каждого ключа. (Ссылка)
Мы также можем выполнить объединение сегментов, и новый объединенный сегмент создается путем объединения нескольких сегментов. Поскольку сегменты никогда не изменяются, поэтому при слиянии для нового сегмента создается новый файл. Сжатие и слияние выполняется фоновым потоком, поэтому записи не затрагиваются. Запросы на чтение перенаправляются на новый объединенный сегмент, когда он готов, до тех пор, пока старые сегменты не обслуживают запросы на чтение.
Каждый сегмент имеет свою хэш-карту смещения ключа. Проблема с хеш-индексами заключается в том, что хеш-карта не помещается в памяти, если имеется много уникальных ключей. Запросы по диапазону тоже неэффективны. Эти ограничения индексации в хеш-индексах преодолеваются стратегией индексирования SSTables и LSM-деревьев.
SSTables и LSM-деревья
До сих пор мы видели, что каждый сегмент с логической структурой представляет собой последовательность пар ключ-значение, появляющихся в том же порядке, в котором он написан. Чтобы оптимизировать наши операции, необходимо изменить способ хранения пар ключ-значение в файле. Теперь давайте отсортируем данные в сегментах по ключам, также известным как таблица сортированных строк (SSTable).
Структура отсортированных ключей улучшает производительность слияния и сжатия.
Поскольку ключи отсортированы, нам не нужно хранить всю пару ключ-смещение в хэш-карте. Мы можем быстро определить смещение любого ключа в отсортированном наборе ключей. Это позволяет нам иметь разреженную хеш-карту, которая легко помещается в хранилище в памяти.
Мы также можем сжать значение, а затем сохранить его на диске для ряда ключей. Это помогает нам уменьшить количество операций ввода-вывода во время запросов диапазона.
Чтобы поддерживать сортированный структурный ключ, мы можем использовать красно-черное дерево или дерево AVL в памяти.
Работая здесь над системой хранения, всякий раз, когда поступает запись, мы записываем ее в структуру отсортированных ключей в памяти, известную как memtable. Каждый раз, когда превышается порог, мы записываем его на диск как сегмент файла SSTable. Кроме того, эти отсортированные сегменты затем объединяются и уплотняются фоновым потоком.
Эта структура индексации известна как дерево слияния с лог-структурой. Более того, механизмы хранения, построенные на основе принципа слияния и сжатия отсортированных файлов, известны как механизм хранения LSM. Lucene использует аналогичные методы.
Cassandra, HBase, Elastic Search, Solr и т. Д. Используют эти стратегии с некоторыми изменениями.
В следующей части мы рассмотрим B-деревья.
