Vortex - Định dạng tệp cột hiệu năng cao

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

"The LLVM of columnar file formats" Định dạng tệp kiểu cột kèm bộ công cụ để xử lý các mảng Apache Arrow đã nén qua bộ nhớ, đĩa và mạng Là người kế nhiệm đầy tham vọng của Apache Parquet, hỗ trợ đọc truy cập ngẫu nhiên nhanh hơn 100-200 lần và quét nhanh hơn 2-10 lần, đồng thời vẫn giữ tỷ lệ nén và thông lượng ghi gần như tương đương với Parquet dùng zstd Cũng hỗ trợ các bảng rất lớn (hàng chục nghìn cột) và giải nén trên GPU Vortex được thiết kế để làm cho định dạng tệp cột những gì Apache DataFusion làm cho engine truy vấn Tức là nổi bật ở khả năng mở rộng cao, tốc độ rất nhanh và tính năng đầy đủ sẵn dùng [!Caution] Vẫn đang được phát triển rất tích cực Các tính năng chính: Logical Types - Định nghĩa schema không đưa ra giả định nào về bố cục vật lý Zero-Copy to Arrow - Các mảng Vortex đã được chuẩn hoá (canonicalized) có thể chuyển đổi zero-copy sang mảng Apache Arrow Extensible Encodings - Tập hợp bố cục vật lý theo kiểu plugin. Ngoài các encoding tương thích Arrow, còn cung cấp các encoding hiện đại (FastLanes, ALP, FSST, v.v.) dưới dạng mở rộng Cascading Compression - Có thể nén dữ liệu đệ quy bằng nhiều encoding lồng nhau Pluggable Compression Strategies - Compressor tích hợp sẵn dựa trên BtrBlocks, nhưng cũng có thể dễ dàng dùng các chiến lược khác Compute - Các kernel tính toán cơ bản hoạt động trên dữ liệu đã được encoding (ví dụ: filter pushdown) Statistics - Mỗi mảng có thống kê tóm tắt được tính tuỳ chọn tại thời điểm đọc. Có thể dùng trong kernel tính toán và compressor Serialization - Tuần tự hoá zero-copy của mảng cho IPC và định dạng tệp Columnar File Format (đang tiến hành) - Định dạng tệp hiện đại để lưu dữ liệu mảng đã nén bằng thư viện serde của Vortex. Tối ưu cho đọc truy cập ngẫu nhiên và quét cực nhanh. Hướng tới việc trở thành hậu duệ của Apache Parquet Tổng quan: Logical vs Physical Một trong những nguyên tắc thiết kế cốt lõi của Vortex là tách biệt nghiêm ngặt giữa mối quan tâm logic và mối quan tâm vật lý Ví dụ: mảng Vortex được xác định bởi kiểu dữ liệu logic (kiểu của phần tử vô hướng) và encoding vật lý (kiểu của chính mảng đó) Các encoding tích hợp chủ yếu được thiết kế để mô hình hoá định dạng in-memory của Apache Arrow. Ngoài ra còn có các encoding tích hợp (sparse, chunked) được dùng như thành phần hữu ích cho các encoding khác. Các encoding mở rộng chủ yếu nhằm mô hình hoá các mảng in-memory đã nén như encoding độ dài hoặc encoding từ điển vortex-serde được thiết kế để xử lý các chi tiết vật lý cấp thấp của mảng Vortex. Việc dùng encoding nào hay chia dữ liệu thành các chunk logic như thế nào được giao cho phần triển khai Compressor Một trong những thuộc tính độc đáo của định dạng tệp Vortex (đang phát triển) là mã hoá bố cục vật lý của dữ liệu vào footer của tệp. Nhờ đó định dạng tệp trở nên tự mô tả một cách hiệu quả và có thể tiến hoá mà không phá vỡ tính tương thích của đặc tả định dạng tệp Hệ thống được thiết kế để hỗ trợ tương thích tiến bằng cách tuỳ chọn nhúng bộ giải mã WASM ngay trong chính tệp. Điều này sẽ giúp tránh tình trạng cứng hoá quá nhanh vốn đã làm khổ nhiều định dạng tệp cột khác Thành phần Logical Types Hệ thống kiểu của Vortex vẫn đang thay đổi. Các kiểu logic hiện tại: Null Bool Integer(8, 16, 32, 64) Float(16, b16, 32, 64) Binary UTF8 Struct List (mới triển khai một phần) Date/Time/DateTime/Duration (được triển khai dưới dạng extension type) TODO: Decimal, FixedList, Tensor, Union Canonical/Flat Encodings Vortex mặc định bao gồm các encoding "Flat" được thiết kế để zero-copy với Apache Arrow. Đây là biểu diễn chuẩn của từng kiểu dữ liệu logic. Các encoding chuẩn hiện được hỗ trợ: Null Bool Primitive (Integer, Float) Struct VarBin (Binary, UTF8) VarBinView (Binary, UTF8) Extension Sẽ bổ sung thêm nhiều encoding khác Compressed Encodings Vortex bao gồm một tập encoding có tính song song dữ liệu và vector hoá cao. Mỗi encoding này tương ứng với một triển khai mảng in-memory đã nén, cho phép trì hoãn việc giải nén. Hiện có các encoding sau: 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 Sẽ bổ sung thêm nhiều encoding khác Compression Chiến lược nén mặc định của Vortex dựa trên bài báo BtrBlocks Nói ngắn gọn, hệ thống lấy mẫu tối thiểu khoảng ~1% dữ liệu cho mỗi chunk dữ liệu Sau đó thử nén (đệ quy) bằng một tập encoding nhẹ Chọn tổ hợp encoding cho hiệu năng tốt nhất để mã hoá toàn bộ chunk Nghe có vẻ rất tốn kém, nhưng chỉ với thống kê cơ bản của chunk, nhiều encoding có thể được cắt tỉa với chi phí thấp để tránh không gian tìm kiếm bùng nổ Compute Vortex cung cấp khả năng để mỗi encoding chuyên biệt hoá phần triển khai của các hàm tính toán, từ đó tránh giải nén nhiều nhất có thể. Ví dụ, khi lọc một mảng UTF8 được mã hoá từ điển, việc lọc từ điển trước sẽ rẻ hơn Vortex không cố trở thành một engine tính toán hoàn chỉnh, mà chỉ triển khai các phép toán tính toán cơ bản có thể cần cho việc quét hiệu quả và pushdown Statistics Các mảng Vortex có thống kê tóm tắt được tính toán trì hoãn Khác với các thư viện mảng khác, các thống kê này có thể được điền từ định dạng trên đĩa như Parquet và được giữ nguyên đến tận engine tính toán Thống kê có thể được dùng trong kernel tính toán và compressor Các thống kê hiện tại: BitWidthFreq TrailingZeroFreq IsConstant IsSorted IsStrictSorted Max Min RunCount TrueCount NullCount Serialization / Deserialization (Serde) Mục tiêu của phần triển khai vortex-serde: Hỗ trợ quét (column projection + row filtering) với zero-copy và zero heap allocation Hỗ trợ truy cập ngẫu nhiên trong thời gian hằng số hoặc gần hằng số Truyền tải thông tin thống kê như việc có được sắp xếp hay không tới bên tiêu thụ Cung cấp định dạng IPC để gửi mảng giữa các tiến trình Cung cấp định dạng tệp có khả năng mở rộng và đẳng cấp cao nhất để lưu dữ liệu cột trên đĩa hoặc object storage Tích hợp với Apache Arrow Apache Arrow là tiêu chuẩn thực tế về khả năng tương tác cho dữ liệu mảng dạng cột. Vì vậy, Vortex đương nhiên được thiết kế để tương thích với Apache Arrow ở mức tối đa Mọi mảng Arrow đều có thể được chuyển thành mảng Vortex theo kiểu zero-copy. Các mảng Vortex được tạo từ mảng Arrow cũng có thể được chuyển ngược lại sang Arrow theo kiểu zero-copy Cần lưu ý rằng Vortex và Arrow có các mục tiêu khác nhau nhưng bổ trợ cho nhau Vortex khác biệt với Arrow ở chỗ phân tách rõ ràng giữa kiểu logic và encoding vật lý. Nhờ đó Vortex có thể mô hình hoá các mảng phức tạp hơn mà vẫn cung cấp giao diện logic Ví dụ: Vortex có thể mô hình hoá một ChunkedArray UTF8 trong đó chunk thứ nhất được mã hoá run-length và chunk thứ hai được mã hoá từ điển. Trong Arrow, RunLengthArray và DictionaryArray là các kiểu riêng biệt không tương thích nên không thể kết hợp theo cách này

(github.com/spiraldb)

9 điểm bởi xguru 2024-10-17 | Chưa có bình luận nào. | Chia sẻ qua WhatsApp

"The LLVM of columnar file formats"
Định dạng tệp kiểu cột kèm bộ công cụ để xử lý các mảng Apache Arrow đã nén qua bộ nhớ, đĩa và mạng
Là người kế nhiệm đầy tham vọng của Apache Parquet, hỗ trợ đọc truy cập ngẫu nhiên nhanh hơn 100-200 lần và quét nhanh hơn 2-10 lần, đồng thời vẫn giữ tỷ lệ nén và thông lượng ghi gần như tương đương với Parquet dùng zstd
- Cũng hỗ trợ các bảng rất lớn (hàng chục nghìn cột) và giải nén trên GPU
Vortex được thiết kế để làm cho định dạng tệp cột những gì Apache DataFusion làm cho engine truy vấn
- Tức là nổi bật ở khả năng mở rộng cao, tốc độ rất nhanh và tính năng đầy đủ sẵn dùng

[!Caution] Vẫn đang được phát triển rất tích cực

Các tính năng chính:
- Logical Types - Định nghĩa schema không đưa ra giả định nào về bố cục vật lý
- Zero-Copy to Arrow - Các mảng Vortex đã được chuẩn hoá (canonicalized) có thể chuyển đổi zero-copy sang mảng Apache Arrow
- Extensible Encodings - Tập hợp bố cục vật lý theo kiểu plugin. Ngoài các encoding tương thích Arrow, còn cung cấp các encoding hiện đại (FastLanes, ALP, FSST, v.v.) dưới dạng mở rộng
- Cascading Compression - Có thể nén dữ liệu đệ quy bằng nhiều encoding lồng nhau
- Pluggable Compression Strategies - Compressor tích hợp sẵn dựa trên BtrBlocks, nhưng cũng có thể dễ dàng dùng các chiến lược khác
- Compute - Các kernel tính toán cơ bản hoạt động trên dữ liệu đã được encoding (ví dụ: filter pushdown)
- Statistics - Mỗi mảng có thống kê tóm tắt được tính tuỳ chọn tại thời điểm đọc. Có thể dùng trong kernel tính toán và compressor
- Serialization - Tuần tự hoá zero-copy của mảng cho IPC và định dạng tệp
- Columnar File Format (đang tiến hành) - Định dạng tệp hiện đại để lưu dữ liệu mảng đã nén bằng thư viện serde của Vortex. Tối ưu cho đọc truy cập ngẫu nhiên và quét cực nhanh. Hướng tới việc trở thành hậu duệ của Apache Parquet

Tổng quan: Logical vs Physical

Một trong những nguyên tắc thiết kế cốt lõi của Vortex là tách biệt nghiêm ngặt giữa mối quan tâm logic và mối quan tâm vật lý
- Ví dụ: mảng Vortex được xác định bởi kiểu dữ liệu logic (kiểu của phần tử vô hướng) và encoding vật lý (kiểu của chính mảng đó)
Các encoding tích hợp chủ yếu được thiết kế để mô hình hoá định dạng in-memory của Apache Arrow. Ngoài ra còn có các encoding tích hợp (sparse, chunked) được dùng như thành phần hữu ích cho các encoding khác. Các encoding mở rộng chủ yếu nhằm mô hình hoá các mảng in-memory đã nén như encoding độ dài hoặc encoding từ điển
vortex-serde được thiết kế để xử lý các chi tiết vật lý cấp thấp của mảng Vortex. Việc dùng encoding nào hay chia dữ liệu thành các chunk logic như thế nào được giao cho phần triển khai Compressor
Một trong những thuộc tính độc đáo của định dạng tệp Vortex (đang phát triển) là mã hoá bố cục vật lý của dữ liệu vào footer của tệp. Nhờ đó định dạng tệp trở nên tự mô tả một cách hiệu quả và có thể tiến hoá mà không phá vỡ tính tương thích của đặc tả định dạng tệp
Hệ thống được thiết kế để hỗ trợ tương thích tiến bằng cách tuỳ chọn nhúng bộ giải mã WASM ngay trong chính tệp. Điều này sẽ giúp tránh tình trạng cứng hoá quá nhanh vốn đã làm khổ nhiều định dạng tệp cột khác

Thành phần

Logical Types

Hệ thống kiểu của Vortex vẫn đang thay đổi. Các kiểu logic hiện tại:
- Null
- Bool
- Integer(8, 16, 32, 64)
- Float(16, b16, 32, 64)
- Binary
- UTF8
- Struct
- List (mới triển khai một phần)
- Date/Time/DateTime/Duration (được triển khai dưới dạng extension type)
- TODO: Decimal, FixedList, Tensor, Union

Canonical/Flat Encodings

Vortex mặc định bao gồm các encoding "Flat" được thiết kế để zero-copy với Apache Arrow. Đây là biểu diễn chuẩn của từng kiểu dữ liệu logic. Các encoding chuẩn hiện được hỗ trợ:
- Null
- Bool
- Primitive (Integer, Float)
- Struct
- VarBin (Binary, UTF8)
- VarBinView (Binary, UTF8)
- Extension
- Sẽ bổ sung thêm nhiều encoding khác

Compressed Encodings

Vortex bao gồm một tập encoding có tính song song dữ liệu và vector hoá cao. Mỗi encoding này tương ứng với một triển khai mảng in-memory đã nén, cho phép trì hoãn việc giải nén. Hiện có các encoding sau:
- 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
- Sẽ bổ sung thêm nhiều encoding khác

Compression

Chiến lược nén mặc định của Vortex dựa trên bài báo BtrBlocks
- Nói ngắn gọn, hệ thống lấy mẫu tối thiểu khoảng ~1% dữ liệu cho mỗi chunk dữ liệu
- Sau đó thử nén (đệ quy) bằng một tập encoding nhẹ
- Chọn tổ hợp encoding cho hiệu năng tốt nhất để mã hoá toàn bộ chunk
- Nghe có vẻ rất tốn kém, nhưng chỉ với thống kê cơ bản của chunk, nhiều encoding có thể được cắt tỉa với chi phí thấp để tránh không gian tìm kiếm bùng nổ

Compute

Vortex cung cấp khả năng để mỗi encoding chuyên biệt hoá phần triển khai của các hàm tính toán, từ đó tránh giải nén nhiều nhất có thể. Ví dụ, khi lọc một mảng UTF8 được mã hoá từ điển, việc lọc từ điển trước sẽ rẻ hơn
Vortex không cố trở thành một engine tính toán hoàn chỉnh, mà chỉ triển khai các phép toán tính toán cơ bản có thể cần cho việc quét hiệu quả và pushdown

Statistics

Các mảng Vortex có thống kê tóm tắt được tính toán trì hoãn
Khác với các thư viện mảng khác, các thống kê này có thể được điền từ định dạng trên đĩa như Parquet và được giữ nguyên đến tận engine tính toán
Thống kê có thể được dùng trong kernel tính toán và compressor
Các thống kê hiện tại:
- BitWidthFreq
- TrailingZeroFreq
- IsConstant
- IsSorted
- IsStrictSorted
- Max
- Min
- RunCount
- TrueCount
- NullCount

Serialization / Deserialization (Serde)

Mục tiêu của phần triển khai vortex-serde:
- Hỗ trợ quét (column projection + row filtering) với zero-copy và zero heap allocation
- Hỗ trợ truy cập ngẫu nhiên trong thời gian hằng số hoặc gần hằng số
- Truyền tải thông tin thống kê như việc có được sắp xếp hay không tới bên tiêu thụ
- Cung cấp định dạng IPC để gửi mảng giữa các tiến trình
- Cung cấp định dạng tệp có khả năng mở rộng và đẳng cấp cao nhất để lưu dữ liệu cột trên đĩa hoặc object storage

Tích hợp với Apache Arrow

Apache Arrow là tiêu chuẩn thực tế về khả năng tương tác cho dữ liệu mảng dạng cột. Vì vậy, Vortex đương nhiên được thiết kế để tương thích với Apache Arrow ở mức tối đa
Mọi mảng Arrow đều có thể được chuyển thành mảng Vortex theo kiểu zero-copy. Các mảng Vortex được tạo từ mảng Arrow cũng có thể được chuyển ngược lại sang Arrow theo kiểu zero-copy
Cần lưu ý rằng Vortex và Arrow có các mục tiêu khác nhau nhưng bổ trợ cho nhau
Vortex khác biệt với Arrow ở chỗ phân tách rõ ràng giữa kiểu logic và encoding vật lý. Nhờ đó Vortex có thể mô hình hoá các mảng phức tạp hơn mà vẫn cung cấp giao diện logic
- Ví dụ: Vortex có thể mô hình hoá một ChunkedArray UTF8 trong đó chunk thứ nhất được mã hoá run-length và chunk thứ hai được mã hoá từ điển. Trong Arrow, RunLengthArray và DictionaryArray là các kiểu riêng biệt không tương thích nên không thể kết hợp theo cách này