QVD-файлы — что внутри, часть 3

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

Итак (вспоминаем) QVD-файл соответствует реляционной таблице, в QVD файле таблица хранится в виде двух косвенно связанных частей:

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

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

На примере нашей таблички (помните — из первой части)

SET NULLINTERPRET =<sym>;
tab1:
LOAD * INLINE [
    ID, NAME
    123.12,"Pete"
    124,12/31/2018
    -2,"Vasya"   
    1,"John"
    <sym>,"None"
];

В таблице строк нашего QVD файла этой табличке будет соответствовать 5 строк — всегда точное соответствие: сколько строк в таблице, столько строк в таблице строк QVD файла.

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

Формат таблицы строк

Таблица строк состоит из K * N байт, где

• K — количество строк исходной таблицы (значение тэга "NoOfRecords" метаданных)
• N — байтовая длина строки таблицы симовлов (значение тэга "RecordByteSize" метаданных)

Таблица строк начинается со смещения "Offset" (тэг метаданных) относительно начала бинарной части файла.

Информация о таблице строк (длина, размер строки, смещение) хранится в общей части метаданных.

Формат строки таблицы строк

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

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

Для полей с двумя значениями эта длина будет равна единице (возможные значения индекса в таблице символов — 0 и 1), и так далее.

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

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

Хранение значений NULL

Как хранить отсутствующие значения? Воздерживаясь от рассуждений на тему "почему", отвечу так: насколько я понял, NULL значениям соответствует следующая комбинация

• тэг "Bias" соответствующего поля принимает значение "-2" (всего же мне попалось два возможных значения этого тэга — "0" и "-2")
• индекс поля для той строки, где это поле есть NULL, равен 0

Соответственно, все остальные индексы в колонке, имеющей NULL значения, увеличены на 2 — увидим на нашем примере чуть ниже.

Порядок следования полей в строке

Порядок следования полей в строке таблицы строк соответствует битовому смещению поля, которое хранится в тэге "BitOffset" раздела метаданных, относящихся к данному полю.

Разберем наш пример (см. метаданные в части первой этой серии).

Поле "ID"

• битовое смещение 0 — поле будет "самым правым"
• битовая длина 3 — поле будет занимать в строке таблицы строк 3 бита
• Bias равен "-2" — поле имеет NULL значения, все индексы увеличены на 2

Поле "NAME"

• битовое смещение 3 — поле расположено "левее" поля ID на 3 бита
• битовая длина 5 — поле будет занимать в строке таблицы строк 5 бит (выровнено до границы байта)
• Bias равен "0" — поле не имеет NULL значений, все индексы "честные"

Представление нашей таблички

Давайте посмотрим на реальные "нолики и единички" — я буду приводить фрагменты QVD файла в виде двоичного представления "в шестнадцатеричном формате" (так компактнее).

Сначала вся бинарная часть целиком (выделена розовым, метаданные обрезаны — уж больно их много...)

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

Первая таблица символов выделена на рисунке ниже.

Видим:

Первое уникальное значение поля "ID" это

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

Остальные три уникальных значения имеют тип 5 (целое число со строкой) — значения "124", "-2" и "1" (легко видеть по строкам).

На рисунке ниже выделил вторую таблицу символов (для поля "NAME")

Первое уникальное значение поля "NAME" — тип "4" (первый выделенный байт) — строка, заканчивающаяся нулем.

Остальные четыре уникальных значения — также строки "12/31/2018", "Vaysa", "John" и "None".

Теперь — таблица строк (выделил на рисунке ниже)

Как и ожидалось — 5 байт (5 строк по одному байту).

Первая строка (соответствующая строке 123.12, "Pete" нашей таблички)

Значение строки — байт "02" (бинарно 000000010).

Разделим его (вспоминаем описание выше)

• правые 3 бита (двоичные 010, по-нашему это 2) — это индекс в таблицу символов поля "ID"
• у нас поле "ID" содержит NULL, поэтому индекс увеличен на 2, т.е. итоговый индекс равен 0, что соответствует символу "123.12".
• следующие 5 бит (двоичный и десятичный 0) — это индекс в таблицу символов поля "NAME", оно NULL не содержит, поэтому это и есть индекс "Pete" в таблице символов.

Вторая строка (124,12/31/2018) в таблице строк

Значение — байт "0B" (бинарно 00001011)

• правые 3 бита (двоичные 011, по-нашему это 3) — это индекс в таблицу символов поля "ID"
• у нас поле "ID" содержит NULL, поэтому индекс увеличен на 2, т.е. итоговый индекс равен 1, что соответствует символу "124".
• следующие 5 бит (двоичная и десятичная 1) — это индекс в таблицу символов поля "NAME", оно NULL не содержит, поэтому это и есть индекс "12/31/2018" в таблице символов.

Ну и так далее, давайте посмотрим быстренько на последнюю строку — там у нас было ,"None" (т.е. NULL и строка "None"):

Значение — байт "20" (бинарно 0010000)

• правые 3 бита (двоичный и десятичный 0) — это индекс в таблицу символов поля "ID"
• у нас поле "ID" содержит NULL, поэтому индекс увеличен на 2, т.е. итоговый индекс равен -2, что и соответствует значению NULL.
• следующие 5 бит (двоичные 100, десятичная 4) — это индекс в таблицу символов поля "NAME", оно NULL не содержит, поэтому это и есть индекс "None" в таблице символов.

ВАЖНО не могу найти пример, подтверждающий это, но мне попадались файлы, которые содержали итоговый индекс -1 для NULL значений. Поэтому в своих программах я считаю NULL-ами все поля, итоговый индекс которых отрицателен.

Более длинные строки в таблице строк

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

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

tab2:
LOAD * INLINE [
    ID, VAL, NAME, PHONE, SINGLE
    1, 100001, "Pete1", "1234567890", "single value"
    2, 200002, "Pete2", "2234567890", "single value"
...
];

В кратком виде информация о полях (выжимка из метаданных):

• ID: ширина 8 бит, битовое смещение — 0, bias — 0
• VAL: ширина 5 бит, битовое смещение — 8, bias — 0
• NAME: ширина 6 бит, битовое смещение — 18, bias — 0
• PHONE: ширина 5 бит, битовое смещение — 13, bias — 0
• SINGLE: ширина 0 бит (имеет одно значение)

Таблица строк состоит из строк длиной 3 байта, соответственно, в строке таблицы строк данные о полях логически разложатся так:

• первые 6 бит — поле "NAME"
• следующие 5 бит — поле "PHONE"
• далее 5 бит — поле "VAL"
• последние 8 бит — поле "ID"

Логическая последовательность преобразуется в физическую перестановкой байт в обратном порядке, т.е.

• поле "ID" полностью занимает первый байт (который в логической последовательности — последний)
• поле "VAL" занимает младшие 5 бит второго байта
• поле "PHONE" занимает старшие 3 бита второго байта и младшие 2 бита третьего байта
• поле "NAME" занимает старшие 6 бит третьего байта

Посмотрим на примерах, вот как выглядит первая строка таблицы строк (выделена розовым)

Значения полей

• ID — бинарно 00000000, десятичный 0
• VAL — бинарно 00010, десятичная 2, вычитаем 2 за счет bias — получаем 0
• PHONE — бинарно 00010, десятичная 2, вычитаем 2 за счет bias — получаем 0
• NAME — бинарно 000000, десятичный 0

Т.е первая строка содержит первые символы из соотвествующих таблиц символов.

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

Давайте для закрепления посмотрим еще на вторую строку

Значения полей

• ID — бинарно 00000001, десятичная 1
• VAL — бинарно 00011, десятичная 3, вычитаем 2 за счет bias — получаем 1
• PHONE — бинарно 00011, десятичная 3, вычитаем 2 за счет bias — получаем 1
• NAME — бинарно 000001, десятичная 1

Т.е вторая строка содержит вторые символы из соотвествующих таблиц символов.

Эффективный разбор формата

Немного поделюсь опытом — как я технически "читал" QVD.

Первая версия была написана на питоне (я ее облагорожу и выложу в github).

Достаточно быстро выяснились основные проблемы:

• таблицы символов можно читать только "подряд" (невозможно считать символ номер N, не прочитав всех предыдущих символов)
• реальные файлы "не влезают" в оперативную память
• из наиболее медленных операций (кроме работы с файлами) — битовые операции (распаковка строки таблицы строк)
• производительность сильно "проседает" на "широких" QVD файлах (когда много колонок)

Часть из этих проблем может быть решена сменой языка (с питона на Си, например). Часть потребовала каких-то дополнительных действий.

Текущая достаточно быстрая реализация выглядит так — общая логика реализована на питоне, а наиболее критичные операции вынесены в отдельные Си программы, запускаемые параллельно.

Коротко

• таблицы символов пишутся в файлы, для текстовых полей дополнительно создаются индексы, тем самым есть возможность считать символ номер N
• работа с QVD и файлами с таблицами символов реализована через memory mapped files (так быстрее)
• сначала параллельно (с ограничением по количеству процессоров) создаются файлы с таблицами символами (и индексами)
• далее параллельно (с аналогичным ограничением) читаются строки таблицы строк и создаются csv файлы (в HDFS)
• последним шагом эти файлы преобразуются в ORC таблицу (средствами Hive)
• на Си реализовано создание файлов с таблицами символов и создание CSV файла для диапазона строк

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

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

Планы на будущее

Что дальше:

• планирую выложить Питон версию кода в github (эта версия позволит "исследовать" QVD файл — смотреть метаданные, читать и писать символы, строки. Версия максимально простая и заведомо медленная — без файлов для таблиц символов, с последовательным чтением, использованием стандартных библиотек для работы с битами и т.п.)
• думаю о том, чтобы сделать что-то для pandas (типа read_qvd()), сдерживает то, что на питоне это будет медленно, а также то, что заведомо не всякий QVD "влезет" в память, поэтому
• думаю о том, чтобы сделать QVD файл источником данных для Spark-а — там этой проблемы с "не влезанием" в память быть не должно (да и язык там — scala — более приближен к железу)

Вместо послесловия

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

Надеюсь, не очень утомил подробностями, готов ответить на вопросы (в комментариях или любым другим способом). Если будет продолжение — обязательно напишу.