Vortex - ฟอร์แมตไฟล์ Columnar ประสิทธิภาพสูง

• "The LLVM of columnar file formats"
• ฟอร์แมตไฟล์แบบ columnar พร้อมชุดเครื่องมือสำหรับจัดการอาร์เรย์ Apache Arrow ที่ถูกบีบอัดผ่านหน่วยความจำ ดิสก์ และเครือข่าย
• ถูกวางตำแหน่งให้เป็นผู้สืบทอดที่ทะเยอทะยานของ Apache Parquet โดยรองรับการอ่านแบบ random access ที่เร็วขึ้น 100-200 เท่า และการสแกนที่เร็วขึ้น 2-10 เท่า ขณะเดียวกันยังคงอัตราการบีบอัดและ throughput การเขียนใกล้เคียงกับ Parquet ที่ใช้ zstd
  • รองรับทั้งตารางขนาดใหญ่มาก (หลายหมื่นคอลัมน์) และการคลายการบีบอัดบน GPU
• Vortex ถูกออกแบบให้ทำหน้าที่กับฟอร์แมตไฟล์แบบคอลัมน์ในลักษณะเดียวกับที่ Apache DataFusion ทำกับ query engine
  • กล่าวคือ เน้นการขยายตัวได้สูง ความเร็วสูงมาก และมีฟีเจอร์พร้อมใช้งานในตัว

[!Caution] > ยังอยู่ระหว่างการพัฒนาอย่างต่อเนื่อง

• ฟีเจอร์หลัก:
  • Logical Types - นิยามสคีมาที่ไม่ตั้งสมมติฐานใด ๆ เกี่ยวกับ physical layout
  • Zero-Copy to Arrow - อาร์เรย์ Vortex ที่ผ่านการทำให้เป็น canonicalized แล้วสามารถแปลงเป็นอาร์เรย์ Apache Arrow ได้แบบ zero-copy
  • Extensible Encodings - ชุด physical layout แบบปลั๊กอิน นอกจาก encoding ที่เข้ากันได้กับ Arrow แล้ว ยังมี encoding สมัยใหม่ (FastLanes, ALP, FSST ฯลฯ) ให้ใช้เป็นส่วนขยาย
  • Cascading Compression - สามารถบีบอัดข้อมูลแบบเรียกซ้อนด้วย encoding หลายชั้นได้
  • Pluggable Compression Strategies - Compressor ในตัวอิงจาก BtrBlocks แต่สามารถใช้กลยุทธ์อื่นได้ง่าย
  • Compute - เคอร์เนลคำนวณพื้นฐานที่ทำงานบนข้อมูลที่ถูกเข้ารหัส (เช่น filter pushdown)
  • Statistics - แต่ละอาร์เรย์มีสถิติสรุปที่คำนวณแบบเลือกได้ในช่วงเวลาอ่าน และสามารถใช้ในเคอร์เนลคำนวณและตัวบีบอัดได้
  • Serialization - การ serialize แบบ zero-copy ของอาร์เรย์สำหรับ IPC และฟอร์แมตไฟล์
  • Columnar File Format (กำลังพัฒนา) - ฟอร์แมตไฟล์สมัยใหม่สำหรับจัดเก็บข้อมูลอาร์เรย์ที่บีบอัดโดยใช้ไลบรารี Vortex serde ปรับให้เหมาะกับการอ่านแบบ random access และการสแกนที่เร็วมาก โดยตั้งเป้าเป็นรุ่นถัดไปของ Apache Parquet

ภาพรวม: Logical vs Physical

• หนึ่งในหลักการออกแบบสำคัญของ Vortex คือการแยก concerns เชิงตรรกะและเชิงกายภาพออกจากกันอย่างเคร่งครัด
  • ตัวอย่าง: อาร์เรย์ Vortex ถูกนิยามด้วยชนิดข้อมูลเชิงตรรกะ (ชนิดขององค์ประกอบสเกลาร์) และ physical encoding (ชนิดของอาร์เรย์เอง)
• encoding ในตัวถูกออกแบบมาเพื่อจำลองฟอร์แมต Apache Arrow ในหน่วยความจำเป็นหลัก นอกจากนี้ยังมี encoding ในตัว (sparse, chunked) ที่ใช้เป็นองค์ประกอบมีประโยชน์สำหรับ encoding อื่น ๆ ส่วน encoding แบบขยายถูกออกแบบมาเพื่อจำลองอาร์เรย์ในหน่วยความจำที่ถูกบีบอัด เช่น length encoding หรือ dictionary encoding
• vortex-serde ถูกออกแบบมาเพื่อจัดการรายละเอียดเชิงกายภาพระดับต่ำของอาร์เรย์ Vortex ส่วนการเลือกว่าจะใช้ encoding ใด หรือจะแบ่งข้อมูลเป็นชิ้นเชิงตรรกะอย่างไร เป็นหน้าที่ของ implementation ของ Compressor
• หนึ่งในคุณสมบัติที่โดดเด่นของฟอร์แมตไฟล์ Vortex (ที่กำลังพัฒนา) คือการเข้ารหัส physical layout ของข้อมูลไว้ใน footer ของไฟล์ ทำให้ฟอร์แมตไฟล์มีลักษณะ self-describing อย่างมีประสิทธิภาพ และสามารถพัฒนาเปลี่ยนแปลงต่อได้โดยไม่ทำลายความเข้ากันได้ของสเปกฟอร์แมตไฟล์
• ออกแบบให้สามารถใส่ WASM decoder ไว้ในไฟล์เองได้แบบเลือกใช้ เพื่อรองรับ forward compatibility ซึ่งน่าจะช่วยหลีกเลี่ยงปัญหาการแข็งตัวของฟอร์แมตเร็วเกินไปที่เคยเกิดกับฟอร์แมตไฟล์แบบ columnar อื่น ๆ

องค์ประกอบ

Logical Types

• ระบบชนิดข้อมูลของ Vortex ยังอยู่ระหว่างการเปลี่ยนแปลง ปัจจุบันมี logical type ดังนี้:
  • Null
  • Bool
  • Integer(8, 16, 32, 64)
  • Float(16, b16, 32, 64)
  • Binary
  • UTF8
  • Struct
  • List (มีการทำไว้บางส่วน)
  • Date/Time/DateTime/Duration (ทำเป็น extension type)
  • TODO: Decimal, FixedList, Tensor, Union

Canonical/Flat Encodings

• Vortex มี "Flat" encoding มาให้โดยปริยาย ซึ่งถูกออกแบบให้ทำงานแบบ zero-copy กับ Apache Arrow ได้ สิ่งเหล่านี้คือรูปแบบมาตรฐานของแต่ละ logical data type โดยปัจจุบันรองรับ canonical encoding ดังนี้:
  • Null
  • Bool
  • Primitive (Integer, Float)
  • Struct
  • VarBin (Binary, UTF8)
  • VarBinView (Binary, UTF8)
  • Extension
  • จะมีการเพิ่ม encoding อื่นอีก

Compressed Encodings

• Vortex มีชุด encoding ที่ออกแบบให้ขนานกับข้อมูลได้สูงและทำงานแบบเวกเตอร์ได้ แต่ละ encoding สอดคล้องกับ implementation ของอาร์เรย์ในหน่วยความจำที่ถูกบีบอัด จึงสามารถเลื่อนการคลายการบีบอัดออกไปได้ ปัจจุบันมี encoding ดังนี้:
  • 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
  • จะมีการเพิ่ม encoding อื่นอีก

Compression

• กลยุทธ์การบีบอัดเริ่มต้นของ Vortex อิงจากงานวิจัย BtrBlocks
  • โดยคร่าว ๆ จะสุ่มตัวอย่างข้อมูลอย่างน้อยประมาณ 1% สำหรับแต่ละ data chunk
  • จากนั้นลองบีบอัดแบบ (เรียกซ้อน) ด้วยชุด encoding น้ำหนักเบา
  • แล้วเลือกชุด encoding ที่ให้ประสิทธิภาพดีที่สุดมาใช้เข้ารหัสทั้ง chunk
  • ฟังดูเหมือนมีต้นทุนสูงมาก แต่หากมีเพียงสถิติพื้นฐานของ chunk ก็สามารถตัดตัวเลือก encoding จำนวนมากออกได้อย่างประหยัด เพื่อไม่ให้พื้นที่ค้นหาเพิ่มขึ้นแบบระเบิด

Compute

• Vortex เปิดโอกาสให้แต่ละ encoding ปรับแต่ง implementation ของฟังก์ชันคำนวณเฉพาะทาง เพื่อลดการคลายการบีบอัดให้มากที่สุด ตัวอย่างเช่น การกรองอาร์เรย์ UTF8 ที่เข้ารหัสแบบ dictionary จะถูกกว่าหากกรองที่ dictionary ก่อน
• Vortex ตั้งใจเพียง implement ปฏิบัติการคำนวณพื้นฐานที่จำเป็นต่อการสแกนอย่างมีประสิทธิภาพและการ pushdown เท่านั้น ไม่ได้ตั้งใจจะเป็น compute engine แบบสมบูรณ์

Statistics

• อาร์เรย์ Vortex มีสถิติสรุปที่คำนวณแบบ lazy
• ต่างจากไลบรารีอาร์เรย์อื่น ๆ สถิติเหล่านี้สามารถถูกเติมมาจากฟอร์แมตบนดิสก์อย่าง Parquet และคงอยู่ต่อไปจนถึง compute engine ได้
• สถิติเหล่านี้สามารถใช้ได้ทั้งในเคอร์เนลคำนวณและตัวบีบอัด
• สถิติที่มีในปัจจุบัน:
  • BitWidthFreq
  • TrailingZeroFreq
  • IsConstant
  • IsSorted
  • IsStrictSorted
  • Max
  • Min
  • RunCount
  • TrueCount
  • NullCount

Serialization / Deserialization (Serde)

• เป้าหมายของ implementation vortex-serde:
  • รองรับการสแกน (column projection + row filtering) แบบ zero-copy และ zero heap allocation
  • รองรับ random access ในเวลา constant หรือใกล้เคียง constant
  • ส่งต่อข้อมูลสถิติ เช่น การจัดเรียงหรือไม่ ให้กับผู้ใช้ปลายทาง
  • ให้ฟอร์แมต IPC สำหรับส่งอาร์เรย์ข้ามโปรเซส
  • ให้ฟอร์แมตไฟล์ที่ขยายต่อได้และอยู่ในระดับสูงสุดสำหรับจัดเก็บข้อมูลแบบ columnar บนดิสก์หรือ object storage

การผสานรวมกับ Apache Arrow

• Apache Arrow คือมาตรฐานโดยพฤตินัยสำหรับการทำงานร่วมกันกับข้อมูลอาร์เรย์แบบ columnar และแน่นอนว่า Vortex ถูกออกแบบให้เข้ากันได้กับ Apache Arrow ให้มากที่สุด
• อาร์เรย์ Arrow ทุกชนิดสามารถแปลงเป็นอาร์เรย์ Vortex ได้แบบ zero-copy และอาร์เรย์ Vortex ที่สร้างจากอาร์เรย์ Arrow ก็สามารถแปลงกลับเป็น Arrow ได้แบบ zero-copy เช่นกัน
• ควรสังเกตว่า Vortex และ Arrow มีเป้าหมายที่ต่างกัน แต่ส่งเสริมกันและกัน
• Vortex สร้างความแตกต่างจาก Arrow ด้วยการแยก logical type และ physical encoding ออกจากกันอย่างชัดเจน ทำให้ Vortex สามารถจำลองอาร์เรย์ที่ซับซ้อนกว่าได้ ขณะเดียวกันก็ยังเปิดเผย logical interface ออกมา
  • ตัวอย่าง: Vortex สามารถจำลอง ChunkedArray ของ UTF8 ที่ chunk แรกเข้ารหัสแบบ run-length และ chunk ที่สองเข้ารหัสแบบ dictionary ได้ ขณะที่ใน Arrow RunLengthArray และ DictionaryArray เป็นคนละชนิดที่ไม่เข้ากัน จึงไม่สามารถรวมกันในลักษณะนี้ได้