Этот раздел очень информативен, и мы хотим понять структуру здания LevelDB в целом. Когда мы познакомимся с общей структурой, мы сможем разбить каждую из них, чтобы детально понять ее различные тонкие детали.
метафора
LevelDB чем-то похож на здание.Оно разделено на две части: фундамент и основание, то есть диск и память.Фундамент подобен структуре земной коры, разделенной на множество уровней, и данные на разных уровнях будут периодически перемещаться сверху вниз дно - осаждение. Если холодные данные на нижнем слое диска будут изменены, они снова попадут в память и через некоторое время будут настойчиво сбрасываться обратно на неглубокий слой файла диска, а затем медленно перемещаться вниз к нижний слой, и круговорот подобен круговороту воды на Земле.
структура памяти
LevelDB поддерживает в памяти два списка переходов, один из которых предназначен только для чтения, а другой — изменяемый wtable. Список прыжков подробно описан в моей другой книге «Redis Deep Adventures», поэтому я не буду подробно повторять его здесь. Проще говоря, список переходов представляет собой набор упорядоченных наборов ключей.Правило упорядочения определяется глобальным «компаратором», а по умолчанию используется лексикографический порядок. Временная сложность операций поиска и обновления списка переходов равна Log(n).
Список пропуска состоит из нескольких уровней связанных списков, из которых самый нижний связанный список хранит все упорядоченные ключи. Обычный связанный список не поддерживает быстрый бинарный поиск, но специальная структура переходного связанного списка позволяет самому нижнему связанному списку найти указанный узел с эффективностью алгоритма приближенного бинарного поиска. Простое понимание состоит в том, что список переходов обладает как возможностью быстрого позиционирования упорядоченного массива, так и возможностью эффективного добавления и удаления связанного списка. Но это будет платить определенную цену и иметь определенную сложность в реализации.
Если в списке переходов хранится только ключ, где хранится значение? Ответ заключается в том, что значение также существует в ключе списка пропуска. Ключ, хранящийся в списке переходов, является особым.Это составная строка структуры, содержащая как ключ, так и значение пары ключ-значение.
type — тип данных, флаг — операция «Поместить» или «Удалить», значений всего два, 0 означает «Удалить», 1 означает «Поместить».
internal_key = key + sequence + type
Key = internal_key_size + internal_key + value_size + value
Если это операция удаления, значение следующего поля value_size равно 0, а значение поля значения пусто. Мы хотим приравнять операцию Удалить к операции Поместить. В то же время в целях экономии места для хранения как internal_key_size, так и value_size кодируются целыми числами varint.
После записи журналов операций «Поместить» и «Удалить» в файл журнала пары «ключ-значение» объединяются в «составной ключ» и вставляются в указанное расположение wtable.
Поскольку wtable поддерживает многопоточное чтение и запись, доступ к нему требует контроля блокировки. А rtable только для чтения, он не нужен, но время его существования очень короткое, как только rtable будет сгенерирован, он скоро сериализуется на диск асинхронными потоками, а потом будет пуст. Однако сериализация асинхронных потоков тоже требует определенного времени, если wtable будет расти слишком быстро, то он быстро заполнится, на данный момент rtable еще не завершил сериализацию, и wtable нужно срочно трансформировать. В это время поток записи заблокируется и будет ждать завершения сериализации асинхронного потока.Это одна из точек задержки LevelDB и точка оптимизации RocksDB в будущем.
На рисунке также есть файл журнала, в котором записан журнал последних операций записи. Если LevelDB столкнется с внезапным простоем, несохраненные данные wtable и rtable будут потеряны. В это время потерянные данные должны быть восстановлены путем воспроизведения данных команды в файле журнала. Обратите внимание, что есть также два файла журнала, которые точно соответствуют списку переходов в память. Когда wtable будет преобразован, файл журнала также будет преобразован. После успешного размещения rtable файл журнала, доступный только для чтения, можно удалить.
структура диска
LevelDB хранит много файлов sst на диске, sst представляет таблицу отсортированных строк, и все ключи в файле будут отсортированы. Каждый файл будет соответствовать уровню, и каждый уровень будет иметь несколько файлов. Содержимое базового файла поступает из предыдущего уровня, и в конечном итоге все они происходят из файла 0-го уровня, а файл 0-го уровня поступает из сериализации rtable в памяти. rtable сериализуется как полный файл уровня 0. Это «эффект погружения», о котором мы упоминали ранее.
Сериализация из rtable в памяти в 0-уровневый файл sst называется «незначительным уплотнением», а переход из n-уровневого sst-файла в n+1-слойный файл sst называется «основным уплотнением». Причина этого различия в том, что Minor работает быстро и потребляет меньше ресурсов, а также выполняется полная сериализация rtable в файл sst. Major будет включать операцию слияния между несколькими файлами, которая потребляет много ресурсов и выполняется медленно. Чем глубже уровень, тем больше общая емкость файла.В исходном коде LevelDB есть формула емкости уровня, и емкость и уровень связаны экспоненциально. Обычно размер каждого файла sst одинаков, а разница в том, что количество файлов в каждом слое разное.
capacity = level > 0 && 10^(level+1) M
Ключи в каждом файле упорядочены, то есть значение ключа внутри него будет иметь определенный диапазон. Очевидное отличие файла 0-го слоя от файлов других слоев заключается в том, что области действия файлов в других слоях не будут перекрываться, и они строго разделены по порядку ключа. Содержимое файла на уровне 0 выгружается напрямую из памяти, поэтому диапазоны значений ключа нескольких файлов на уровне 0 будут перекрываться.
При промахе чтения в памяти и поиске на диске сначала будет выполняться поиск с уровня 0, а если не удастся найти, будет выполняться поиск на более глубоком уровне.
На других уровнях поиск выполняется быстро, поскольку по диапазону ключа можно быстро определить, в каком файле он может находиться. Но для уровня 0, поскольку диапазон ключей файла будет перекрываться, он может существовать в нескольких файлах, поэтому необходимо выполнить поиск в этих нескольких файлах. Из-за этого LevelDB ограничивает количество файлов уровня 0. Если число превышает установленное по умолчанию 4, оно должно «опуститься» до уровня 1. Эта операция «погружения» называется основным уплотнением.
Диапазоны значений ключей, уровни и другая метаинформация для всех файлов хранятся в файле MANIFEST в каталоге базы данных. Когда база данных открыта, прочитайте этот файл, чтобы узнать уровень и диапазон значений ключа всех файлов.
Файлы MANIFEST также имеют номер версии, который отражается в имени файла как MANIFEST-000361. Каждый раз при повторном открытии базы данных создается новый файл МАНИФЕСТА с другим номером версии, а затем старый файл МАНИФЕСТА необходимо удалить.
В каталоге базы данных есть еще один файл CURRENT, и его содержимое очень простое: это имя файла текущего МАНИФЕСТА. LevelDB сначала читает ТЕКУЩИЙ файл, чтобы узнать, какой файл МАНИФЕСТА является допустимым файлом. В случае отключения электроэнергии будет небольшая вероятность промежуточного состояния, когда в каталоге базы данных сосуществуют старый и новый файлы МАНИФЕСТА.
Мы знаем, что каталог базы данных LevelDB не позволяет нескольким процессам обращаться к нему одновременно, так как же он предотвращает случайное чтение и запись этого файла каталога другими процессами? Присмотревшись к каталогу базы данных, вы также найдете файл с именем LOCK, который является ключом к управлению многопроцессным доступом к базе данных. Когда процесс открывает базу данных, к файлу добавляется блокировка файла мьютекса, которая автоматически снимается по завершении процесса.
Существует также последний, менее важный файл журнала операций, LOG, в котором записывается ряд журналов ключевых операций базы данных, таких как информация о каждом незначительном и значительном уплотнении.
множественное слияние
Сжатие является относительно ресурсоемкой операцией, поэтому, чтобы не влиять на оперативные операции чтения и записи, LevelDB назначает работу по сжатию одному асинхронному потоку для завершения. Если рабочая нагрузка огромна, этот единственный асинхронный поток также может быть немного перегружен. Когда асинхронный поток не может этого выдержать, операции чтения и записи оперативной памяти также будут затронуты. Поскольку на диск записывается только rtable, wtable можно преобразовать. Только после преобразования wtable будет создана новая wtable для размещения большего количества последующих пар ключ-значение. В общем, все в одном кольце.
Давайте посмотрим на уплотнение. Незначительное уплотнение хорошо известно, то есть пространство содержимого ограничено, поэтому данные в rtable необходимо сбросить в файл уровня диска 0. Итак, зачем вам нужно переходить от файла 0-го уровня Compact к файлу 1-го уровня? Потому что, если файлов уровня 0 слишком много, это повлияет на эффективность поиска. Ранее мы упоминали, что диапазон ключей между файлами уровня 0 будет перекрываться, поэтому один ключ может существовать в нескольких файлах, а количество операций чтения ввода-вывода будет увеличиваться на количество файлов. Благодаря основному уплотнению количество файлов нулевого уровня может быть уменьшено, а эффективность чтения может быть повышена. Нужно ли погружаться только в 1 слой файлов? Так зачем же LevelDB нужно так много слоев?
Итак, как именно LevelDB это делает? Он использует алгоритм многоканального слияния, принимает в качестве входных данных соответствующие файлы 0-го уровня и 1-слойные файлы sst, выполняет многопутевое слияние, генерирует несколько новых одноуровневых файлов sst, а затем уничтожает старые файлы sst, а также генерирует новые файлы MANIFEST. Для каждого файла слоя 0 он будет искать файл sst в файле слоя 1, который перекрывается с его диапазоном в соответствии с диапазоном значений ключа. Если в 1-м слое слишком много файлов, количество файлов, участвующих в каждом многостороннем слиянии, слишком велико, и алгоритм слияния будет очень ресурсоемким. Следовательно, LevelDB также должен контролировать количество файлов уровня 1. Когда емкость уровня 1 заполнена, она будет продолжать опускаться до уровня 2, уровня 3, уровня 4 и т. д.
Потребление ресурсов при многостороннем слиянии не на уровне 0 меньше, поскольку диапазон значений ключа одного файла ограничен, количество файлов, которые могут быть перенесены на следующий уровень, ограничено, а входные файлы, участвующие в многостороннем слиянии, ограничены. способ слияния намного меньше. Но в этой логике есть лазейка, то есть существует 10-кратная разница между количеством файлов в верхнем и нижнем слоях.Рассчитывается по интервалу среднего диапазона, значит, средний диапазон значений одного файла в верхний слой покроет 10 файлов следующего слоя. Таким образом, потребление ресурсов при многоканальном слиянии не уровня 0 на самом деле не является низким.Основное уплотнение является относительно ресурсоемкой операцией.
В следующем разделе мы углубимся во внутреннюю структуру файла диска и посмотрим, как выглядит каждый sstable внутри.