Глава 3. Форматы файлов

enum NodeType {
   ROOT,     // 0x00h
   INTERNAL, // 0x01h
   LEAF      // 0x02h
};
 	   

int IS_LEAF_MASK         = 0x01h; // bit #1
int VARIABLE_SIZE_VALUES = 0x02h; // bit #2
int HAS_OVERFLOW_PAGES   = 0x04h; // bit #3
 	   

// Установка значения бита
flags |= HAS_OVERFLOW_PAGES;
flags |= (1 << 2);

// Сброс значения бита
flags &= ~HAS_OVERFLOW_PAGES;
flags &= ~(1 << 2);

// Проверка того установлен или нет бит
is_set = (flags & HAS_OVERFLOW_PAGES) != 0;
is_set = (flags & (1 << 2)) != 0;
 	   

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

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

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

Когда вы желаете спроектировать некий формат для каталога своей компании, хранимых имён, дат рождения, налоговых номеров и пола для каждого сотрудника, мы можем применять различные подходы. Мы можем хранить все поля фиксированного размера (такие как дата рождения и налоговый номер) в самом заголовке данной структуры, за которым следуют поля с изменяемым размером:

Fixed-size fields:
| (4 bytes) employee_id                |
| (4 bytes) tax_number                 |
| (3 bytes) date                       |
| (1 byte)  gender                     |
| (2 bytes) first_name_length          |
| (2 bytes) last_name_length           |

Variable-size fields:
| (first_name_length bytes) first_name |
| (last_name_length bytes) last_name   |
 	   

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

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

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

Системы баз данных хранят записи данных в файлах данных и индексации. Эти файлы разделяются на элементы фиксированного размера, имеющие название страниц, которые часто имеют размер произведения блоков файловой системы. Обычно страницы находятся в диапазоне от 4 до 16 кБ.

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

Первоначальная статья B- дерева [BAYER72] описывает простую организацию страниц для записей данных фиксированного размера, в которых каждая страница это всего лишь конкатенация триплетов, как это показано на рисунке 3-4: ключи обозначаются как k, связанные с ними значения как v, а указатели на дочерние страницы обозначаются как p.

Такой подход прост для его реализации, однако он обладает рядом тёмных сторон:

При хранении записей переменной длины основная проблема состоит в управлении свободным пространством: восстановлении того пространства, которое занято удаляемыми записями. Если мы попытаемся поместить запись с размером n в некое пространство, которое изначально было занято записью с размером m, пока не выполняется m == n, или мы не можем отыскать другую запись, которая в точности имеет размер m - n, это пространство остаётся незанятым. Аналогично, некий сегмент с размером m не может применяться для хранения записей с размером k, когда k больше чем m, поэтому последняя будет вставляться без возврата имеющегося неиспользуемым пространства.

Для упрощения управления пространством под записи переменного размера мы можем расщеплять свою страницу на сегменты с фиксированным размером. Однако мы в конце концов когда мы следуем этим путём, мы также получаем трату пространства впустую. Например, когда мы применяем размер сегмента в 64 байта, пока размер соответствующей записи не является произведением с 64, мы теряем 64 - (n modulo 64) байт, где n является размером вставляемой записи. Иными словами, пока запись не кратна 64, один из её блоков будет заполнен лишь частично.

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

Чтобы суммировать, нам необходим некий формат страницы, который позволит нам:

Для эффективного хранения записей переменной длины, таких как строки, BLOB (binary large objects) и т.п., мы можем применять технологию организации с названием Перекидных страниц (то есть страниц с прорезями, slotted page) [SILBERSCHATZ10] или Перекидного каталога [RAMAKRISHNAN03]. Такой подход используется многими базами данных, например, PostgreSQL.

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

Некая перекидная страница обладает заголовком фиксированного размера, который содержит важные сведения относительно самой страницы и её ячеек (см. Заголовок страницы). Ячейки могут отличаться в размере и способны содержать произвольные данные: ключи, указатели, записи данных и т.п.. Рисунок 3-5 отображает организацию Перекидных страниц, при которой каждая страница имеет некую область сопровождения (заголовок), ячейки и указатели на них.

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

Применяя флаги, перечислимые (enums) и примитивные значения, мы можем начинать проектирование схемы ячейки, затем сочетать ячейки в страницу и составлять из таких страниц некое дерево. На уровне некой ячейки у нас имеется разница между ячейками ключей и ключ- значение. Ячейки с ключом содержат некий разделительный ключ и указатель на страницу между двумя соседними указателями. Ячейки ключ- значение содержат ключи и связанные с ними записи данных.

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

Для составления некой ячейки ключей нам требуется знать:

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

0                4               8
+----------------+---------------+-------------+
| [int] key_size | [int] page_id | [bytes] key |
+----------------+---------------+-------------+
 	   

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

Ячейки ключ- значение содержат записи данных вместо значений идентификаторов дочерних страниц. Во всём остальном их структура аналогична:

0              1                5 ...
+--------------+----------------+
| [byte] flags | [int] key_size |
+--------------+----------------+

5                  9                    .. + key_size
+------------------+--------------------+----------------------+
| [int] value_size |     [bytes] key    | [bytes] data_record  |
+------------------+--------------------+----------------------+
 	   

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

Для организации ячеек в страницы, мы можем пользоваться той техникой Перекидных страниц, которую мы обсудили в разделе Перекидные страницы. Мы добавляем ячейки в правую сторону такой страницы (со стороны её конца) и сохраняем смещения/ указатели в левой стороне данной страницы, как это показано на Рисунке 3-6.

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

Давайте рассмотрим некий пример страницы, содержащей имена. В данную страницу добавляются два имени, причём порядок их вставки таков: Tom и Leslie. Как вы можете видеть на Рисунке 3-7, их логический порядок (в данном случае алфавитный), не соответствует порядку вставки (тому порядку, в котором они вставлялись в конец этой страницы). Ячейки располагаются в порядке вставки, но смещения сортируются повторно делая для наз возможным двоичный поиск.

Теперь мы бы хотели добавить в эту страницу ещё одно имя: Ron. Новые данные добавляются к верхней границе свободного пространства этой страницы, однако смещениям ячеек приходится предохранять установленный лексикографический порядок ключей: Leslie, Ron, Tom. Для этого нам приходится повторно упорядочить смещения ячеек: указатели после такой точки вставки сдвигаются вправо для предоставления пространства под ячейку Ron, как это можно видеть на Рисунке 3-8.

Удаление некого элемента из определённой страницы не удаляет реальную ячейку и не сдвигает прочие ячейки для перераспределения высвобождающегося свободного пространства. Вместо этого ячейка может быть помечена как удалённая, а расположенный в памяти список доступности может быть обновлён этим значением освобождаемой памяти с освобождением данного значения указателя. Такой список доступности хранит смещения освобождённых сегментов и их размеров. При вставке новой ячейки мы вначале проверяем список доступности для обнаружения того имеется ли некий сегмент, в котором она могла бы уместиться. На Рисунке 3-9 вы можете видеть некий образец фрагментированной памяти с доступными сегментами.

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

Подгонка вычисляется на основании определённой стратегии:

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

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

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

Это можно выполнять различными способами. Например, Apache Cassandra применяет в названиях файлов префиксы используемых версий. Таким образом, вы можете сказать какая версия у данного файла даже не открывая его. Когда версия 4.0, некое название файла имеет префикс названия файла na, скажем, na-1-big-Data.db. Более старые файлы имеют иные префиксы: записанные с версией 3.0 файлы имеют префикс ma.

В качестве альтернативы, номер версии может храниться в неком отдельном файле. Например, PostgreSQL хранит номера версий в своём файле PG_VERSION.

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

Файлы на диске могут разрушаться или искажаться за счёт ошибок программного обеспечения и отказов оборудования. Для предварительного выявления таких проблем и чтобы избегать распространения нарушенных данных в прочие системы или даже узлы мы можем применять контрольные суммы и циклические проверки избыточности (CRC, cyclic redundancy checks).

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

Контрольные суммы предоставляют самый слабый вид гарантии и не способны выявлять нарушения во множестве бит. Обычно они вычисляются при помощи XOR с частичными проверками или суммированиями [KOOPMAN15].

CRC способны способствовать выявлению ошибок разрушений (например, когда получены нарушения во множестве) [STONE98]. Критически важно выявлять ошибки во множестве бит, так как значительное процентное соотношение отказов в сетевых средах взаимодействия и устройствах хранения выявляется именно так.

Перед записью своих данных на диск, мы вычисляем их контрольные суммы и записываем их вместе с этими данными. При обратном считывании мы вычисляем их контрольную сумму снова и сопоставляем её с записанным значением. Если имеется некое расхождение в контрольных суммах, мы знаем что произошло разрушение и нам не следует пользоваться считанными данными.

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

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

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

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

Эти принципы могут применяться для составления двоичных форматов дисковых структур и сетевых протоколов.