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 файла в виде двоичного представления «в шестнадцатеричном формате» (так компактнее).

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

image

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

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

image

Видим:

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


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

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

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

image

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

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

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

image

Как и ожидалось — 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 бит третьего байта

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

image

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


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

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

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

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

image

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


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

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

© Habrahabr.ru