Arquivos QVD - o que há dentro, parte 3

No primeiro artigo sobre a estrutura do arquivo QVD, descrevi a estrutura geral e me baseiei em metadados com detalhes suficientes, e o segundo no armazenamento de colunas (caracteres). Neste artigo, descreverei o formato para armazenar informações sobre cadeias, resumir e falar sobre planos e realizações.

Portanto, lembre-se: o arquivo QVD corresponde à tabela relacional. No arquivo QVD, a tabela é armazenada em duas partes conectadas indiretamente:

As tabelas de caracteres (meu termo) contêm valores exclusivos para cada coluna na tabela de origem. Eu falei sobre eles no segundo artigo.

A tabela de linhas contém as linhas da tabela de origem, cada linha armazena os índices dos valores da coluna (campo) da linha na tabela de símbolos correspondente. É sobre isso que este artigo será.

No exemplo do nosso prato (lembre-se - da primeira parte)

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

Na tabela de linhas do nosso arquivo QVD, esse rótulo corresponde a 5 linhas - sempre uma correspondência exata: quantas linhas estão na tabela, quantas linhas estão na tabela de linhas do arquivo QVD.

Uma linha na tabela de linhas consiste em números inteiros não negativos, cada um desses números é um índice na tabela de símbolos correspondente. No nível lógico, tudo é simples, resta esclarecer as nuances e dar um exemplo (desmonte - como nossa placa de identificação é apresentada em QVD).

Formato da tabela de linhas

A tabela de linhas consiste em K * N bytes, em que

• K - o número de linhas na tabela de origem (o valor da tag de metadados "NoOfRecords")
• N - comprimento de byte da linha da tabela de símbolos (o valor da tag de metadados "RecordByteSize")

A tabela de linhas começa com o deslocamento "Deslocamento" (tag de metadados) relativo ao início da parte binária do arquivo.

As informações sobre a tabela de linhas (comprimento, tamanho da linha, deslocamento) são armazenadas na parte geral dos metadados.

Formato da linha da tabela de linhas

Todas as linhas da tabela de linhas têm o mesmo formato e são uma concatenação de "números não assinados". O comprimento do número é minimamente suficiente para representar um campo específico: o comprimento depende do número de valores exclusivos de um campo específico.

Para campos com um valor (como já escrevi), esse comprimento será zero (esse valor é o mesmo em cada linha da tabela de origem e é armazenado na tabela de símbolos correspondente).

Para campos com dois valores, esse comprimento será igual a um (os possíveis valores de índice na tabela de símbolos são 0 e 1) e assim por diante.

Como o comprimento total da linha da tabela de linhas deve ser múltiplo do byte, o comprimento do "último caractere" é alinhado ao limite do byte (veja abaixo quando analisaremos nossa placa).

As informações sobre o formato de cada campo são armazenadas na seção de metadados dedicada a esse campo (veremos um pouco mais abaixo), o comprimento da representação de bits do campo é armazenado na tag "BitWidth".

Armazenando valores NULL

Como armazenar valores ausentes? Abstendo-me de discutir o tópico do porquê, responderei desta maneira: como eu o entendo, a seguinte combinação corresponde aos valores NULL

• a tag "Viés" do campo correspondente assume o valor "-2" (no total, me deparei com dois valores possíveis dessa tag - "0" e "-2")
• o índice do campo para a linha em que esse campo é NULL é 0

Assim, todos os outros índices na coluna com valores NULL aumentam em 2 - veremos em nosso exemplo um pouco mais baixo.

A ordem dos campos na linha

A ordem dos campos na linha da tabela de linhas corresponde ao deslocamento de bits do campo, que é armazenado na tag "BitOffset" da seção de metadados relacionada a esse campo.

Vamos analisar nosso exemplo (consulte os metadados na primeira parte desta série).

Campo ID

• deslocamento de bit 0 - o campo será o "mais à direita"
• bit length 3 - o campo ocupará 3 bits em uma linha de uma tabela de linhas
• A polarização é "-2" - o campo tem valores NULL, todos os índices são aumentados em 2

Campo "NAME"

• deslocamento de bit 3 - o campo está localizado à esquerda do campo ID por 3 bits
• bit length 5 - o campo ocupará 5 bits na linha da tabela de linhas (alinhada ao limite de bytes)
• A polarização é "0" - o campo não possui valores NULL, todos os índices são "honestos"

Apresentação da nossa placa de identificação.

Vejamos os verdadeiros "zeros e uns" - darei fragmentos do arquivo QVD como uma representação binária "em formato hexadecimal" (tão compacto).

Primeiro, toda a parte binária (destacada em rosa, os metadados são truncados - dói muitos deles ...)

Compacto o suficiente, concordo. Vamos dar uma olhada mais de perto - logo após os metadados, existem tabelas de símbolos (a propósito, os metadados neste arquivo terminam com avanço de linha e zero byte - tecnicamente isso acontece, zero bytes depois que os metadados precisam ser ignorados ...).

A primeira tabela de símbolos é destacada na figura abaixo.

Vemos:

O primeiro valor exclusivo do campo ID é

• o tipo "6" (o primeiro byte alocado) é um número de ponto flutuante com uma string (consulte o segundo artigo)
• após o primeiro byte, 8 dos próximos bytes são um número de ponto flutuante representado binário
• depois deles vem a representação da string - muito conveniente (não é preciso lembrar - qual era o número), terminando com um byte zero

Os três valores únicos restantes são do tipo 5 (um número inteiro com uma sequência) - os valores são "124", "-2" e "1" (fáceis de ver ao longo das linhas).

Na figura abaixo, destaquei a segunda tabela de símbolos (para o campo "NAME")

O primeiro valor exclusivo do campo "NAME" é do tipo "4" (o primeiro byte alocado) - uma sequência que termina com zero.

Os outros quatro valores exclusivos também são as strings "31/12/2018", "Vaysa", "John" e "None".

Agora - a tabela de linhas (destacada na figura abaixo)

Como esperado - 5 bytes (5 linhas por um byte).

A primeira linha (correspondente à linha 123.12, "Pete" do nosso prato)

O valor da sequência é o byte "02" (binário 000000010).

Separe-o (lembre-se da descrição acima)

• 3 bits corretos (010 binário, em nossa opinião, é 2) - este é um índice na tabela de símbolos do campo "ID"
• como o campo "ID" contém NULL, o índice é aumentado em 2, ou seja, o índice resultante é 0, que corresponde ao caractere "123.12".
• os próximos 5 bits (0 binário e decimal 0) são o índice na tabela de símbolos do campo "NAME"; ele não contém NULL; portanto, este é o índice "Pete" na tabela de símbolos.

Segunda linha (124.12 / 31/2018) na tabela de linhas

Valor - byte "0B" (binário 00001011)

• 3 bits à direita (binário 011, em nossa opinião, é 3) - este é o índice na tabela de símbolos do campo "ID"
• como o campo "ID" contém NULL, o índice é aumentado em 2, ou seja, o índice resultante é 1, que corresponde ao símbolo "124".
• os próximos 5 bits (binário e decimal 1) são o índice na tabela de símbolos do campo "NAME"; ele não contém NULL; portanto, este é o índice "31/12/2018" na tabela de símbolos.

Bem, e assim por diante, vamos dar uma rápida olhada na última linha - lá estava, "None" (ou seja, NULL e a string "None"):

O valor é o byte "20" (binário 0010000)

• 3 bits à direita (binário e decimal 0) - este é o índice na tabela de símbolos do campo "ID"
• como o campo "ID" contém NULL, o índice é aumentado em 2, ou seja, o índice final é -2, que corresponde ao valor NULL.
• os próximos 5 bits (binário 100, decimal 4) são o índice na tabela de símbolos do campo "NAME"; ele não contém NULL; portanto, este é o índice "None" na tabela de símbolos.

IMPORTANTE Não consigo encontrar um exemplo confirmando isso, mas me deparei com arquivos que continham um índice final de -1 para valores NULL. Portanto, nos meus programas, considero NULL todos os campos cujo índice final é negativo.

Linhas mais longas em uma tabela de linhas

No final da análise do formato QVD, vou abordar brevemente algumas nuances importantes - linhas longas na tabela de linhas armazenam os campos na ordem da direita para a esquerda, onde o campo com deslocamento de bit zero será o mais à direita (como descrito acima). MAS a ordem dos bytes é inversa, ou seja, o primeiro byte será o mais à direita (e conterá o campo "direito" - um campo com deslocamento de zero bits), o último byte será o primeiro (ou seja, conterá o campo mais "esquerdo" - um campo com deslocamento de bits máximo).

Um exemplo deve ser dado, mas não sobrecarregado com detalhes. Vejamos esse rótulo (cito um fragmento - para obter linhas longas na tabela de linhas, você precisa aumentar o número de valores exclusivos).

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

Informações breves sobre os campos (extraídos de metadados):

• ID: largura 8 bits, deslocamento de bit - 0, polarização - 0
• VAL: largura 5 bits, deslocamento de bit - 8, viés - 0
• NOME: largura 6 bits, deslocamento de bit - 18, viés - 0
• TELEFONE: largura 5 bits, deslocamento de bit - 13, viés - 0
• ÚNICO: largura 0 bits (tem um valor)

A tabela de linhas consiste em cadeias de caracteres com um comprimento de 3 bytes, respectivamente. Na linha da tabela de linhas, os dados sobre os campos serão decompostos logicamente da seguinte maneira:

• primeiros 6 bits - campo "NAME"
• próximos 5 bits - campo "TELEFONE"
• então 5 bits - campo "VAL"
• últimos 8 bits - campo ID

A sequência lógica é convertida em bytes físicos na ordem inversa, ou seja,

• o campo "ID" ocupa completamente o primeiro byte (que na sequência lógica é o último)
• o campo "VAL" ocupa os 5 bits inferiores do segundo byte
• O campo "PHONE" ocupa os 3 bits superiores do segundo byte e os 2 bits inferiores do terceiro byte
• O campo "NAME" ocupa os 6 bits superiores do terceiro byte

Vejamos exemplos. Aqui está a aparência da primeira linha da tabela de linhas (destacada em rosa)

Valores de campo

• ID - binário 00000000, decimal 0
• VAL - binário 00010, decimal 2, subtrair 2 do viés - obter 0
• Binário 00010, decimal 2, subtrair 2 do viés - obter 0
• NOME - binário 000000, decimal 0

Ou seja, a primeira linha contém os primeiros caracteres das tabelas de caracteres correspondentes.

Em geral, é conveniente começar a analisar a partir da primeira linha - geralmente contém zeros como índice (o arquivo QVD é construído de tal maneira que os valores da primeira linha entram primeiro na tabela de caracteres).

Vamos olhar para a segunda linha para corrigir

Valores de campo

• ID - binário 00000001, decimal 1
• VAL - binário 00011, decimal 3, subtraia 2 do viés - obtenha 1
• PHONE - binário 00011, decimal 3, subtraia 2 do viés - obtenha 1
• NAME - binário 000001, decimal 1

Ou seja, a segunda linha contém os segundos caracteres das tabelas de caracteres correspondentes.

Análise de formato eficiente

Vou compartilhar um pouco de experiência - como tecnicamente "leio" o QVD.

A primeira versão foi escrita em python (eu a enobrecerei e a colocarei no github).

Os principais problemas rapidamente se tornaram claros:

• as tabelas de símbolos só podem ser lidas “seguidas” (é impossível ler o número de símbolo N sem ler todos os caracteres anteriores)
• arquivos reais não cabem na RAM
• das operações mais lentas (exceto para trabalhar com arquivos) - operações de bits (descompactando uma linha de uma tabela de strings)
• o desempenho diminui bastante nos arquivos QVD "amplos" (quando há muitas colunas)

Alguns desses problemas podem ser resolvidos alterando a linguagem (de python para C, por exemplo). Parte exigiu alguma ação adicional.

A implementação atual, bastante rápida, se parece com isso - a lógica geral é implementada em python e as operações mais críticas são realizadas em programas C separados, executando paralelamente.

Em breve

• tabelas de símbolos são gravadas em arquivos, índices são criados adicionalmente para campos de texto, portanto é possível ler o número de símbolo N
• trabalhe com QVD e arquivos com tabelas de símbolos implementadas por meio de arquivos mapeados na memória (muito mais rápido)
• primeiro, em paralelo (com um limite no número de processadores), os arquivos são criados com tabelas de símbolos (e índices)
• em paralelo (com uma restrição semelhante), as linhas da tabela de linhas são lidas e os arquivos csv são criados (no HDFS)
• a última etapa é converter esses arquivos em uma tabela ORC (usando as ferramentas do Hive)
• em C implementou a criação de arquivos com tabelas de símbolos e a criação de um arquivo CSV para várias linhas

Não quero dar números sobre o desempenho - eles exigirão ligação ao hardware; em um nível qualitativo, copia o arquivo QVD para a tabela ORC na velocidade da cópia de dados pela rede. Ou, em outras palavras, obter dados do QVD é bastante realista (no nível doméstico).

Também implementei a lógica de criação de arquivos QVD - ele funciona muito rapidamente em python (aparentemente, ainda não atingi grandes volumes - não há necessidade. Vou chegar lá - vou reescrevê-lo da mesma maneira que a versão de "leitura").

Planos futuros

O que vem a seguir:

• Eu pretendo colocar a versão Python do código no github (esta versão permitirá que você "explore" o arquivo QVD - veja metadados, leia e escreva caracteres, strings. A versão é o mais simples e obviamente mais lenta possível - sem arquivos para tabelas de caracteres, com leitura sequencial, usando bibliotecas padrão para trabalhar com bits etc.)
• Penso em fazer algo para os pandas (como read_qvd ()), ele restringe que será lento no python, bem como o fato de que obviamente nem todo QVD "cabe" na memória, portanto
• Penso em tornar o arquivo QVD uma fonte de dados para o Spark - não deve haver esse problema com "não entrar na memória" (e o idioma - scala - está mais próximo do hardware)

Em vez de um posfácio

Por um longo tempo, percorri os arquivos QVD e parecia que "tudo é complicado por lá". Acabou sendo difícil, mas não muito, um bom ímpeto no github, que mencionei na primeira parte (uma espécie de catalisador). Então era uma questão de tecnologia. Eu e todos observamos (mais uma confirmação) - tudo pode ser feito na programação, a questão é tempo e motivação.

Espero não estar muito cansado dos detalhes, estar pronto para responder a perguntas (nos comentários ou de qualquer outra forma). Se houver uma continuação, eu definitivamente escreverei.