python

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

  • вторник, 25 июня 2019 г. в 00:18:18
https://habr.com/ru/company/alfastrah/blog/457102/
  • Блог компании АльфаСтрахование (Сервис будущего в настоящем)
  • Python
  • Data Mining
  • Big Data


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


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


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


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