QVD-файлы — что внутри, часть 3
В первой статье о структуре 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, который я упомянул в первой части (своего рода катализатор). Дальше уже было дело техники. Себе и всем на заметку (еще одно подтверждение) — в программировании все можно сделать, вопрос во времени и мотивации.
Надеюсь, не очень утомил подробностями, готов ответить на вопросы (в комментариях или любым другим способом). Если будет продолжение — обязательно напишу.