Погрузитесь в структуру файла данных LevelDB SSTable

Пары "ключ-значение" LevelDB хранятся в файлах SSTable с расширением sst. Структура дисковых файлов SSTables относительно сложна. Читатели должны быть морально готовы перед чтением этого раздела. Если вам что-то непонятно, обязательно задавайте вопросы в разделе вопросов и ответов ниже.

Содержимое файла SSTable разделено на 5 частей: нижний колонтитул, IndexBlock, MetaIndexBlock, FilterBlock и DataBlock. Среди них DataBlock хранит содержимое пар ключ-значение, а FilterBlock хранит двоичные данные фильтров Блума. Существует несколько блоков данных, и может быть несколько блоков FilterBlock, но обычно не более одного. Причина создания нескольких рассмотреть Для расширения, другие типы фильтров могут поддерживаться в будущем. Остальные три части представляют собой блоки управления, в которых IndexBlock записывает метаданные, относящиеся к DataBlock, MetaIndexBlock записывает метаданные, относящиеся к фильтру, а нижний колонтитул указывает информацию о смещении IndexBlock и MetaIndexBlock в файле, который является метаинформацией информация о метаданных, которая находится в конце файла sstable. Ниже мы разбираем каждую структуру по очереди сверху вниз

Структура нижнего колонтитула

Он занимает небольшое пространство всего 48 байт, и внутри хранится всего несколько полей. Ниже мы используем псевдокод для описания его структуры.

// 定义了数据块的位置和大小
struct BlockHandler {
  varint offset;
  varint size;
}

struct Footer {
  BlockHandler metaIndexHandler;  // MetaIndexBlock的文件偏移量和长度
  BlockHandler indexHandler; // IndexBlock的文件偏移量和长度
  byte[n] padding;  // 内存垫片
  int32 magicHighBits;  // 魔数后32位
  int32 magicLowBits; // 魔数前32位
}

В среднюю часть структуры нижнего колонтитула добавляется разделитель памяти, и его функция заключается в поддержке пространства нижнего колонтитула до 48 байт. Также в конце структуры есть 64-битное магическое число 0xdb4775248b80fb57.Если 8 байт в конце файла не являются этим числом, файл поврежден. Источник этого магического числа интересен, это первые 64 бита строки, возвращаемой ниже.

$ echo http://code.google.com/p/leveldb/ | sha1sum
db4775248b80fb57d0ce0768d85bcee39c230b61

Существует только один IndexBlock и MetaIndexBlock, поэтому структура BlockHandler используется для хранения смещения и длины соответственно.

Блочная структура

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

struct Block {
  byte[] data;
  int8 compressType;
  int32 crcValue;
}

Каждый блок будет иметь тип сжатия и код проверки циклическим избыточным кодом (crcValue) в конце, который займет 5 байт. Если это сжатый тип, данные данных в блоке будут сжаты. Контрольная сумма вычисляет циклическую избыточную контрольную сумму для данных сжатой суммы и полей типа сжатия. Алгоритм сжатия по умолчанию быстрый, а алгоритм проверки — crc32.

crcValue = crc32(data, compressType)

Во всех структурах Block, описанных ниже, мы больше не упоминаем сжатие и контрольные суммы.

Структура блока данных

Размер DataBlock по умолчанию составляет 4 КБ (до сжатия), и в нем хранится ряд пар ключ-значение. Как упоминалось ранее, ключи в файле sst упорядочены, а это означает, что соседние ключи с высокой вероятностью имеют общую префиксную часть. Именно с учетом этого DataBlock был оптимизирован по структуре, и эта оптимизация позволяет значительно сократить объем хранилища.

Key = sharedKey + unsharedKey

Ключ будет разделен на две части, одна из которых является sharedKey, а другая — unsharedKey. Первый указывает на общее содержание префикса ключа относительной ссылки, а второй указывает на разные части суффикса ключа относительной ссылки.

Например, если эталонный ключ — helloworld, то ключ hellouniverse сравнивается с эталонным ключом, и его sharedKey — это hello, а его unsharedKey — юниверс.

DataBlock хранит непрерывный ряд пар ключ-значение и устанавливает ссылочный ключ через каждые несколько ключей. Характеристикой эталонного ключа является то, что его часть sharedKey представляет собой пустую строку. Положение эталонного ключа, то есть его смещение в блоке, мы называем «точкой перезапуска» RestartPoint, и все положения «точки перезапуска» будут записываться в DataBlock. Положение первой «точки перезапуска» равно нулю, что является первым ключом в DataBlock.

struct Entry {
  varint sharedKeyLength;
  varint unsharedKeyLength;
  varint valueLength;
  byte[] unsharedKeyContent;
  byte[] valueContent;
}

struct DataBlock {
  Entry[] entries;
  int32 [] restartPointOffsets;
  int32 restartPointCount;
}

Эталонный ключ в DataBlock по умолчанию устанавливается через каждые 16 ключей. Это не разумная стратегия с точки зрения экономии места. Например, 26 последовательных ключей отличаются только последней буквой, а DataBlock вынужден "перезапускать" каждые 16 ключей, что явно не оптимально. Это также означает, что sharedKey является пустым ключом, и этот ключ не обязательно является ссылочным ключом.

Размер DataBlock по умолчанию составляет всего 4 КБ, поэтому количество пар ключ-значение, содержащихся в нем, обычно составляет всего несколько десятков. Что делать, если содержимое одной пары ключ-значение слишком велико, чтобы поместиться в DataBlock?

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

Структура блока фильтра

Если фильтр Блума не включен, блок FilterBlock не существует. В файле SSTable может быть несколько блоков FilterBlock, и каждый блок хранит данные одного фильтра. Однако, что касается текущей реализации LevelDB, она может иметь не более одного фильтра, то есть фильтра Блума.

Фильтр Блума используется для повышения эффективности определения местоположения ключей дисковых файлов SSTable. Если фильтра Блума нет, то ему нужно выполнить бинарный поиск по SSTable, если Ключа в нем нет, то для его определения нужно выполнить несколько IO-чтений, после проверки оказывается, что он пустой. Роль фильтра Блума состоит в том, чтобы избежать ненужных операций ввода-вывода, когда ключ не существует. Запросив фильтр Блума, вы можете узнать, может ли ключ быть в нем в какой-то момент.

Один фильтр Блума хранит массив растровых изображений фиксированной длины, а массив растровых изображений хранит информацию об отпечатках нескольких ключей. Эти несколько ключей происходят из непрерывного диапазона в DataBlock. В блоке FilterBlock есть несколько последовательных массивов растровых изображений фильтра Блума, каждый из которых отвечает за снятие отпечатков части данных в SSTable.

struct FilterEntry {
  byte[] rawbits;
}

struct FilterBlock {
  FilterEntry[n] filterEntries;
  int32[n] filterEntryOffsets;
  int32 offsetArrayOffset;
  int8 baseLg;  // 分割系数
}

По умолчанию для baseLg установлено значение 11, что означает, что через каждые 2 КБ (2

// 每个 Key 占用 10bit 存放指纹信息
options.SetFilterPolicy(levigo.NewBloomFilter(10))

Интервал в 2 Кбайт здесь является строгим интервалом, так что положение соответствующего фильтра Блума можно быстро определить по смещению и размеру DataBlock, FilterOffset, а затем можно дополнительно получить соответствующие данные растрового изображения фильтра Блума.

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

Структура МетаИндексБлок

MetaIndexBlock хранит метаинформацию предыдущей серии блоков FilterBlock.Он аналогичен структуре DataBlock, за исключением того, что Key, хранящийся в Entry, представляет собой имя фильтра с фиксированным префиксом, а Value представляет собой смещение и соответствующий FilterBlock в файл.длина.

key = "filter." + filterName
// value 定义了数据块的位置和大小
struct BlockHandler {
  varint offset;
  varint size;
}

Что касается текущей LevelDB, то здесь максимум одна запись, поэтому ее структура очень проста, как показано на следующем рисунке.

Структура индексного блока

Подобно структуре MetaIndexBlock, она также хранит набор пар ключ-значение. Каждая пара ключ-значение хранит метаданные блока данных. В SSTable есть несколько блоков данных, а в IndexBlock — несколько пар ключ-значение. Ключ пары ключ-значение — это самый большой ключ в соответствующем блоке данных, а значение — это смещение и длина блока данных. Независимо от разделения префикса между ключами и «точкой перезапуска», его структура показана на следующем рисунке.

Здесь упоминается структура SSTable, в следующем разделе мы продолжим рассмотрение структуры лог-файла.