▲

Vortex - 고성능 Columnar 파일 포맷

 (github.com/spiraldb)
9P by xguru 1달전 | favorite | 댓글과 토론
  • "The LLVM of columnar file formats"
  • 압축된 Apache Arrow 배열을 메모리, 디스크, 네트워크를 통해 다루기 위한 툴킷을 포함한 Columnar 형식 파일 포맷
  • Apache Parquet의 야심찬 후계자로, 100-200배 빠른 랜덤 액세스 읽기와 2-10배 빠른 스캔을 지원하면서도 zstd를 사용한 Parquet과 거의 동일한 압축률과 쓰기 처리량을 유지함
    • 매우 큰 테이블(수만개의 컬럼)과 GPU 상에서의 압축 해제도 지원
  • Vortex는 열 기반 파일 형식에 대해 Apache DataFusion이 쿼리 엔진에 대해 제공하는 것과 같은 기능을 하도록 설계됨
    • 즉, 높은 확장성, 매우 빠른 속도, 배터리 포함 기능이 특징

[!주의] > 아직 활발히 개발 진행 중임

  • 주요 기능:
    • Logical Types - 물리적 레이아웃에 대해 어떤 가정도 하지 않는 스키마 정의
    • Zero-Copy to Arrow - 정규화(canonicalized)된 Vortex 배열은 Apache Arrow 배열과 제로 카피 변환이 가능함
    • Extensible Encodings - 플러그인 방식의 물리적 레이아웃 집합. Arrow 호환 인코딩 외에도 최신 인코딩(FastLanes, ALP, FSST 등)을 확장으로 제공
    • Cascading Compression - 데이터를 여러 중첩된 인코딩으로 재귀적 압축 가능
    • Pluggable Compression Strategies - 내장 Compressor는 BtrBlocks 기반이지만, 다른 전략도 쉽게 사용 가능
    • Compute - 인코딩된 데이터에서 동작하는 기본 계산 커널(예: 필터 푸시다운)
    • Statistics - 각 배열은 읽기 시점에 선택적으로 계산되는 요약 통계를 가지고 있음. 계산 커널과 압축기에서 사용 가능
    • Serialization - IPC와 파일 포맷을 위한 배열의 제로 카피 직렬화
    • Columnar File Format (진행 중) - Vortex serde 라이브러리를 사용해 압축된 배열 데이터를 저장하는 현대적 파일 포맷. 랜덤 액세스 읽기와 매우 빠른 스캔에 최적화됨. Apache Parquet의 후속을 목표로 함

개요: Logical vs Physical

  • Vortex의 핵심 설계 원칙 중 하나는 논리적 관심사와 물리적 관심사의 엄격한 분리임
    • 예: Vortex 배열은 논리적 데이터 타입(스칼라 요소의 타입)과 물리적 인코딩(배열 자체의 타입)으로 정의됨
  • 내장 인코딩은 주로 Apache Arrow 인메모리 포맷을 모델링하기 위해 설계됨. 또한 다른 인코딩의 유용한 구성 요소로 사용되는 내장 인코딩(sparse, chunked)도 있음. 확장 인코딩은 주로 길이 인코딩이나 사전 인코딩 같은 압축된 인메모리 배열을 모델링하기 위한 것임
  • vortex-serde는 Vortex 배열의 저수준 물리적 세부 사항을 다루도록 설계됨. 어떤 인코딩을 사용할지나 데이터를 어떻게 논리적으로 청크화할지는 Compressor 구현에 맡겨짐
  • (개발 중인) Vortex 파일 포맷의 독특한 속성 중 하나는 데이터의 물리적 레이아웃을 파일의 푸터에 인코딩한다는 점임. 이를 통해 파일 포맷은 효과적으로 자기 기술적이 되고, 파일 포맷 명세의 호환성을 깨지 않고도 진화할 수 있음
  • WASM 디코더를 파일 자체에 선택적으로 포함시켜 전방 호환성을 지원하도록 설계됨. 이는 다른 columnar 파일 포맷을 괴롭혀 온 빠른 경화를 피하는 데 도움이 될 것임

구성 요소

Logical Types

  • Vortex 타입 시스템은 아직 변화 중임. 현재의 논리적 타입:
    • Null
    • Bool
    • Integer(8, 16, 32, 64)
    • Float(16, b16, 32, 64)
    • Binary
    • UTF8
    • Struct
    • List (부분 구현됨)
    • Date/Time/DateTime/Duration (확장 타입으로 구현됨)
    • TODO: Decimal, FixedList, Tensor, Union

Canonical/Flat Encodings

  • Vortex는 Apache Arrow와 제로 카피가 되도록 설계된 "Flat" 인코딩들을 기본으로 포함하고 있음. 이들은 각 논리적 데이터 타입의 정규 표현임. 현재 지원되는 정규 인코딩:
    • Null
    • Bool
    • Primitive (Integer, Float)
    • Struct
    • VarBin (Binary, UTF8)
    • VarBinView (Binary, UTF8)
    • Extension
    • 더 많은 인코딩이 추가될 예정

Compressed Encodings

  • Vortex는 고도로 데이터 병렬적이고 벡터화된 인코딩 집합을 포함함. 이 인코딩들은 각각 압축된 인메모리 배열 구현에 대응되어, 압축 해제를 지연시킬 수 있음. 현재 다음과 같은 인코딩이 있음:
    • 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
    • 더 많은 인코딩이 추가될 예정

Compression

  • Vortex의 기본 압축 전략은 BtrBlocks 논문을 기반으로 함
    • 대략적으로, 각 데이터 청크에 대해 최소 ~1%의 데이터 샘플을 취함
    • 그런 다음 경량 인코딩 집합으로 (재귀적) 압축을 시도함
    • 그 중 가장 성능이 좋은 인코딩 조합을 선택해 전체 청크를 인코딩함
    • 이는 매우 비용이 클 것처럼 들리지만, 청크에 대한 기본 통계만 있으면 많은 인코딩을 저렴하게 가지치기하여 검색 공간이 폭발적으로 커지지 않도록 할 수 있음

Compute

  • Vortex는 각 인코딩이 계산 함수의 구현을 특수화하여 가능한 한 압축 해제를 피할 수 있는 기능을 제공함. 예를 들어, 사전 인코딩된 UTF8 배열을 필터링하는 것은 먼저 사전을 필터링하는 것이 더 저렴함
  • Vortex는 효율적인 스캔과 푸시다운에 필요할 수 있는 기본 계산 연산을 구현할 뿐, 완전한 계산 엔진이 되려고 하지는 않음

Statistics

  • Vortex 배열은 지연 계산된 요약 통계를 가지고 있음
  • 다른 배열 라이브러리와 달리, 이 통계는 Parquet 같은 디스크 포맷에서 채워져서 계산 엔진까지 그대로 보존될 수 있음
  • 통계는 계산 커널과 압축기에서 사용 가능함
  • 현재의 통계:
    • BitWidthFreq
    • TrailingZeroFreq
    • IsConstant
    • IsSorted
    • IsStrictSorted
    • Max
    • Min
    • RunCount
    • TrueCount
    • NullCount

Serialization / Deserialization (Serde)

  • vortex-serde 구현의 목표:
    • 제로 카피와 제로 힙 할당으로 스캔(열 프로젝션 + 행 필터링) 지원
    • 상수 시간 또는 준상수 시간으로 랜덤 액세스 지원
    • 정렬 여부 같은 통계 정보를 소비자에게 전달
    • 프로세스 간에 배열을 보내기 위한 IPC 포맷 제공
    • 디스크나 오브젝트 스토리지에 columnar 데이터를 저장하기 위한 확장 가능하고 최고 수준의 파일 포맷 제공

Apache Arrow와의 통합

  • Apache Arrow는 columnar 배열 데이터에 대한 상호운용의 사실상 표준임. 당연히 Vortex는 Apache Arrow와 최대한 호환되도록 설계됨
  • 모든 Arrow 배열은 제로 카피로 Vortex 배열로 변환될 수 있음. Arrow 배열에서 생성된 Vortex 배열은 다시 제로 카피로 Arrow로 변환될 수 있음
  • Vortex와 Arrow는 서로 다르지만 상호 보완적인 목표를 가지고 있다는 점에 유의해야 함
  • Vortex는 논리적 타입과 물리적 인코딩을 명시적으로 구분하여 Arrow와 차별화됨. 이를 통해 Vortex는 더 복잡한 배열을 모델링하면서도 논리적 인터페이스를 노출할 수 있음
    • 예: Vortex는 첫 번째 청크가 run-length 인코딩되고 두 번째 청크가 사전 인코딩된 UTF8 ChunkedArray를 모델링할 수 있음. Arrow에서는 RunLengthArray와 DictionaryArray가 호환되지 않는 별개의 타입이므로 이런 식으로 결합될 수 없음