Vortex - formato de arquivo columnar de alto desempenho

xguru · 2024-10-17T11:01:27+09:00

"The LLVM of columnar file formats" Formato de arquivo columnar que inclui um toolkit para lidar com arrays Apache Arrow comprimidos em memória, disco e rede Um sucessor ambicioso do Apache Parquet, oferecendo leituras de acesso aleatório 100-200x mais rápidas e scans 2-10x mais rápidos, enquanto mantém taxa de compressão e throughput de escrita quase idênticos ao Parquet com zstd Também oferece suporte a tabelas muito grandes (dezenas de milhares de colunas) e descompressão em GPU O Vortex foi projetado para fazer pelos formatos de arquivo columnar o que o Apache DataFusion faz pelos motores de consulta Ou seja, com foco em alta extensibilidade, altíssima velocidade e recursos inclusos [!Aviso] > Ainda está em desenvolvimento ativo Principais recursos: Logical Types - definição de esquema que não faz nenhuma suposição sobre o layout físico Zero-Copy to Arrow - arrays Vortex canonicalizados podem ser convertidos para arrays Apache Arrow com zero-copy Extensible Encodings - conjunto de layouts físicos em estilo plug-in. Além de encodings compatíveis com Arrow, oferece como extensões encodings modernos (FastLanes, ALP, FSST etc.) Cascading Compression - permite comprimir dados recursivamente com vários encodings aninhados Pluggable Compression Strategies - o compressor embutido é baseado em BtrBlocks, mas outras estratégias também podem ser usadas facilmente Compute - kernels básicos de computação que operam sobre dados codificados (ex.: filter pushdown) Statistics - cada array possui estatísticas resumidas calculadas opcionalmente no momento da leitura. Podem ser usadas por kernels de computação e compressores Serialization - serialização zero-copy de arrays para IPC e formatos de arquivo Columnar File Format (em andamento) - formato de arquivo moderno para armazenar dados de arrays comprimidos usando a biblioteca serde do Vortex. Otimizado para leituras com acesso aleatório e scans muito rápidos. Tem como objetivo suceder o Apache Parquet Visão geral: Logical vs Physical Um dos principais princípios de projeto do Vortex é a separação rigorosa entre preocupações lógicas e físicas Ex.: um array Vortex é definido por seu tipo de dado lógico (o tipo dos elementos escalares) e sua codificação física (o tipo do próprio array) Os encodings embutidos foram projetados principalmente para modelar o formato in-memory do Apache Arrow. Também há encodings embutidos (sparse, chunked) usados como componentes úteis de outros encodings. Os encodings de extensão servem principalmente para modelar arrays in-memory comprimidos, como length encoding ou dictionary encoding vortex-serde foi projetado para lidar com os detalhes físicos de baixo nível dos arrays Vortex. A decisão sobre quais encodings usar e como dividir logicamente os dados em chunks fica a cargo da implementação de Compressor Uma das propriedades únicas do formato de arquivo Vortex (em desenvolvimento) é codificar o layout físico dos dados no footer do arquivo. Isso torna o formato efetivamente autodocumentado e permite sua evolução sem quebrar a compatibilidade da especificação do formato Ele foi projetado para suportar compatibilidade futura por meio da inclusão opcional de um decoder WASM no próprio arquivo. Isso deve ajudar a evitar a cristalização precoce que afetou outros formatos de arquivo columnar Componentes Logical Types O sistema de tipos do Vortex ainda está mudando. Tipos lógicos atuais: Null Bool Integer(8, 16, 32, 64) Float(16, b16, 32, 64) Binary UTF8 Struct List (implementado parcialmente) Date/Time/DateTime/Duration (implementados como tipos de extensão) TODO: Decimal, FixedList, Tensor, Union Canonical/Flat Encodings O Vortex inclui por padrão encodings "Flat" projetados para zero-copy com Apache Arrow. Eles são a representação canônica de cada tipo de dado lógico. Encodings canônicos atualmente suportados: Null Bool Primitive (Integer, Float) Struct VarBin (Binary, UTF8) VarBinView (Binary, UTF8) Extension Mais encodings serão adicionados Compressed Encodings O Vortex inclui um conjunto de encodings altamente paralelos em dados e vetorizados. Cada um deles corresponde a uma implementação de array in-memory comprimido, o que permite adiar a descompressão. Atualmente há os seguintes encodings: Adaptive Lossless Floating Point (ALP) BitPacked (FastLanes) Constant Chunked Delta (FastLanes) Dictionary Fast Static Symbol Table (FSST) Frame-of-Reference Run-end Encoding RoaringUInt RoaringBool Sparse ZigZag Mais encodings serão adicionados Compression A estratégia de compressão padrão do Vortex é baseada no artigo BtrBlocks Em linhas gerais, para cada chunk de dados, é coletada uma amostra de pelo menos ~1% dos dados Em seguida, tenta-se a compressão (recursiva) com um conjunto de encodings leves A combinação de encodings com melhor desempenho é escolhida para codificar o chunk inteiro Isso pode parecer muito custoso, mas com apenas estatísticas básicas do chunk é possível podar muitos encodings de forma barata, evitando que o espaço de busca exploda Compute O Vortex fornece mecanismos para que cada encoding especialize a implementação das funções de computação e assim evite ao máximo a descompressão. Por exemplo, ao filtrar um array UTF8 codificado por dicionário, é mais barato filtrar primeiro o dicionário O Vortex não tenta se tornar um motor de computação completo; ele implementa apenas as operações básicas de computação que podem ser necessárias para scans eficientes e pushdown Statistics Arrays Vortex possuem estatísticas resumidas calculadas sob demanda Diferentemente de outras bibliotecas de arrays, essas estatísticas podem ser preenchidas a partir de formatos em disco como Parquet e preservadas até o motor de computação As estatísticas podem ser usadas por kernels de computação e compressores Estatísticas atuais: BitWidthFreq TrailingZeroFreq IsConstant IsSorted IsStrictSorted Max Min RunCount TrueCount NullCount Serialization / Deserialization (Serde) Objetivos da implementação de vortex-serde: suportar scan (projeção de colunas + filtragem de linhas) com zero-copy e zero alocação no heap suportar acesso aleatório em tempo constante ou quase constante transmitir ao consumidor informações estatísticas como ordenação fornecer um formato IPC para enviar arrays entre processos fornecer um formato de arquivo extensível e de primeira linha para armazenar dados columnar em disco ou object storage Integração com Apache Arrow Apache Arrow é o padrão de fato para interoperabilidade de dados de arrays columnar. Naturalmente, o Vortex foi projetado para ser o mais compatível possível com Apache Arrow Todos os arrays Arrow podem ser convertidos para arrays Vortex com zero-copy. Arrays Vortex criados a partir de arrays Arrow podem ser convertidos de volta para Arrow também com zero-copy É importante notar que Vortex e Arrow têm objetivos diferentes, embora complementares O Vortex se diferencia do Arrow ao separar explicitamente tipos lógicos e encodings físicos. Isso permite que o Vortex modele arrays mais complexos enquanto expõe uma interface lógica Ex.: o Vortex pode modelar um ChunkedArray UTF8 em que o primeiro chunk usa run-length encoding e o segundo usa dictionary encoding. No Arrow, RunLengthArray e DictionaryArray são tipos separados e incompatíveis, então eles não podem ser combinados dessa forma

(github.com/spiraldb)

9 pontos por xguru 2024-10-17 | Ainda não há comentários. | Compartilhar no WhatsApp

"The LLVM of columnar file formats"
Formato de arquivo columnar que inclui um toolkit para lidar com arrays Apache Arrow comprimidos em memória, disco e rede
Um sucessor ambicioso do Apache Parquet, oferecendo leituras de acesso aleatório 100-200x mais rápidas e scans 2-10x mais rápidos, enquanto mantém taxa de compressão e throughput de escrita quase idênticos ao Parquet com zstd
- Também oferece suporte a tabelas muito grandes (dezenas de milhares de colunas) e descompressão em GPU
O Vortex foi projetado para fazer pelos formatos de arquivo columnar o que o Apache DataFusion faz pelos motores de consulta
- Ou seja, com foco em alta extensibilidade, altíssima velocidade e recursos inclusos

[!Aviso] > Ainda está em desenvolvimento ativo

Principais recursos:
- Logical Types - definição de esquema que não faz nenhuma suposição sobre o layout físico
- Zero-Copy to Arrow - arrays Vortex canonicalizados podem ser convertidos para arrays Apache Arrow com zero-copy
- Extensible Encodings - conjunto de layouts físicos em estilo plug-in. Além de encodings compatíveis com Arrow, oferece como extensões encodings modernos (FastLanes, ALP, FSST etc.)
- Cascading Compression - permite comprimir dados recursivamente com vários encodings aninhados
- Pluggable Compression Strategies - o compressor embutido é baseado em BtrBlocks, mas outras estratégias também podem ser usadas facilmente
- Compute - kernels básicos de computação que operam sobre dados codificados (ex.: filter pushdown)
- Statistics - cada array possui estatísticas resumidas calculadas opcionalmente no momento da leitura. Podem ser usadas por kernels de computação e compressores
- Serialization - serialização zero-copy de arrays para IPC e formatos de arquivo
- Columnar File Format (em andamento) - formato de arquivo moderno para armazenar dados de arrays comprimidos usando a biblioteca serde do Vortex. Otimizado para leituras com acesso aleatório e scans muito rápidos. Tem como objetivo suceder o Apache Parquet

Visão geral: Logical vs Physical

Um dos principais princípios de projeto do Vortex é a separação rigorosa entre preocupações lógicas e físicas
- Ex.: um array Vortex é definido por seu tipo de dado lógico (o tipo dos elementos escalares) e sua codificação física (o tipo do próprio array)
Os encodings embutidos foram projetados principalmente para modelar o formato in-memory do Apache Arrow. Também há encodings embutidos (sparse, chunked) usados como componentes úteis de outros encodings. Os encodings de extensão servem principalmente para modelar arrays in-memory comprimidos, como length encoding ou dictionary encoding
vortex-serde foi projetado para lidar com os detalhes físicos de baixo nível dos arrays Vortex. A decisão sobre quais encodings usar e como dividir logicamente os dados em chunks fica a cargo da implementação de Compressor
Uma das propriedades únicas do formato de arquivo Vortex (em desenvolvimento) é codificar o layout físico dos dados no footer do arquivo. Isso torna o formato efetivamente autodocumentado e permite sua evolução sem quebrar a compatibilidade da especificação do formato
Ele foi projetado para suportar compatibilidade futura por meio da inclusão opcional de um decoder WASM no próprio arquivo. Isso deve ajudar a evitar a cristalização precoce que afetou outros formatos de arquivo columnar

Componentes

Logical Types

O sistema de tipos do Vortex ainda está mudando. Tipos lógicos atuais:
- Null
- Bool
- Integer(8, 16, 32, 64)
- Float(16, b16, 32, 64)
- Binary
- UTF8
- Struct
- List (implementado parcialmente)
- Date/Time/DateTime/Duration (implementados como tipos de extensão)
- TODO: Decimal, FixedList, Tensor, Union

Canonical/Flat Encodings

O Vortex inclui por padrão encodings "Flat" projetados para zero-copy com Apache Arrow. Eles são a representação canônica de cada tipo de dado lógico. Encodings canônicos atualmente suportados:
- Null
- Bool
- Primitive (Integer, Float)
- Struct
- VarBin (Binary, UTF8)
- VarBinView (Binary, UTF8)
- Extension
- Mais encodings serão adicionados

Compressed Encodings

O Vortex inclui um conjunto de encodings altamente paralelos em dados e vetorizados. Cada um deles corresponde a uma implementação de array in-memory comprimido, o que permite adiar a descompressão. Atualmente há os seguintes encodings:
- Adaptive Lossless Floating Point (ALP)
- BitPacked (FastLanes)
- Constant
- Chunked
- Delta (FastLanes)
- Dictionary
- Fast Static Symbol Table (FSST)
- Frame-of-Reference
- Run-end Encoding
- RoaringUInt
- RoaringBool
- Sparse
- ZigZag
- Mais encodings serão adicionados

Compression

A estratégia de compressão padrão do Vortex é baseada no artigo BtrBlocks
- Em linhas gerais, para cada chunk de dados, é coletada uma amostra de pelo menos ~1% dos dados
- Em seguida, tenta-se a compressão (recursiva) com um conjunto de encodings leves
- A combinação de encodings com melhor desempenho é escolhida para codificar o chunk inteiro
- Isso pode parecer muito custoso, mas com apenas estatísticas básicas do chunk é possível podar muitos encodings de forma barata, evitando que o espaço de busca exploda

Compute

O Vortex fornece mecanismos para que cada encoding especialize a implementação das funções de computação e assim evite ao máximo a descompressão. Por exemplo, ao filtrar um array UTF8 codificado por dicionário, é mais barato filtrar primeiro o dicionário
O Vortex não tenta se tornar um motor de computação completo; ele implementa apenas as operações básicas de computação que podem ser necessárias para scans eficientes e pushdown

Statistics

Arrays Vortex possuem estatísticas resumidas calculadas sob demanda
Diferentemente de outras bibliotecas de arrays, essas estatísticas podem ser preenchidas a partir de formatos em disco como Parquet e preservadas até o motor de computação
As estatísticas podem ser usadas por kernels de computação e compressores
Estatísticas atuais:
- BitWidthFreq
- TrailingZeroFreq
- IsConstant
- IsSorted
- IsStrictSorted
- Max
- Min
- RunCount
- TrueCount
- NullCount

Serialization / Deserialization (Serde)

Objetivos da implementação de vortex-serde:
- suportar scan (projeção de colunas + filtragem de linhas) com zero-copy e zero alocação no heap
- suportar acesso aleatório em tempo constante ou quase constante
- transmitir ao consumidor informações estatísticas como ordenação
- fornecer um formato IPC para enviar arrays entre processos
- fornecer um formato de arquivo extensível e de primeira linha para armazenar dados columnar em disco ou object storage

Integração com Apache Arrow

Apache Arrow é o padrão de fato para interoperabilidade de dados de arrays columnar. Naturalmente, o Vortex foi projetado para ser o mais compatível possível com Apache Arrow
Todos os arrays Arrow podem ser convertidos para arrays Vortex com zero-copy. Arrays Vortex criados a partir de arrays Arrow podem ser convertidos de volta para Arrow também com zero-copy
É importante notar que Vortex e Arrow têm objetivos diferentes, embora complementares
O Vortex se diferencia do Arrow ao separar explicitamente tipos lógicos e encodings físicos. Isso permite que o Vortex modele arrays mais complexos enquanto expõe uma interface lógica
- Ex.: o Vortex pode modelar um ChunkedArray UTF8 em que o primeiro chunk usa run-length encoding e o segundo usa dictionary encoding. No Arrow, RunLengthArray e DictionaryArray são tipos separados e incompatíveis, então eles não podem ser combinados dessa forma