QVD-файлы — что внутри, часть 324.06.2019 16:35

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

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

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

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

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

SET NULLINTERPRET =;
tab1:
LOAD * INLINE [
    ID, NAME
    123.12,"Pete"
    124,12/31/2018
    -2,"Vasya"   
    1,"John"
    ,"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, который я упомянул в первой части (своего рода катализатор). Дальше уже было дело техники. Себе и всем на заметку (еще одно подтверждение) — в программировании все можно сделать, вопрос во времени и мотивации.

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