Katkat
Back

Design a Compact Columnar File Format

Jump TradingSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Design an append-friendly, compact columnar file format optimized for fast analytical scans over tabular financial market data (e.g., tick feeds or order book snapshots). Define the on-disk binary layout, reader/writer abstractions, serialization rules, and operational trade-offs.

Scenario

High-frequency trading research and backtesting engines ingest terabytes of tick-level order book events daily. Row-oriented storage (like CSV or line-delimited JSON) causes excessive I/O when strategies query only a subset of fields (e.g., just timestamp and mid_price across billions of records).

Design a compact, self-contained, read-heavy columnar file format (a simplified Parquet-like format) along with the class interfaces for writing and reading data.

Requirements

Functional

  1. Data Model: Support strongly-typed tabular data with fixed-width primitive types (INT32, INT64, FLOAT64) and nullability.
  2. Chunking / Page Layout: Support dividing rows into horizontal "Row Groups" (e.g., 64K to 1M rows per group), with each row group storing columnar data chunks contiguously.
  3. Projection & Predicate Pushdown: The read API must allow reading only a subset of columns without decoding unused columns, and allow skipping row groups using column-level chunk metadata (min/max bounds).
  4. Self-Describing: The file must contain a schema and metadata footer so it can be parsed without external catalogs.

Non-Functional & Layout Constraints

  • Fixed-size header and a tail-end metadata footer (with a fixed-size footer length and magic bytes at the very end of the file).
  • Minimize random I/O: Contiguous sequential reads within a requested column chunk.
  • Compression: Support pluggable block compression (e.g., Raw, Snappy/LZ4, or Bit-packing/Delta encoding for timestamps).

Expected Deliverables

  1. Binary Layout Specification: Define the exact byte-level layout (magic bytes, headers, row groups, column chunks, data pages, dictionary pages, and footer metadata).
  2. Class Interfaces: Define explicit interfaces in Python or C++ pseudo-code for ColumnarFileWriter and ColumnarFileReader, demonstrating how chunks are buffered, flushed, and projected.
  3. Invariants & Edge Cases: Detail file corruption handling, partial writes, all-null columns, and variable row group sizes.
  4. Testing Strategy: Describe how you would validate correctness, zero-copy read paths, and encoding regressions.

Hints

Hint 1

Placing the metadata footer and its size at the end of the file allows single-pass streaming writes without needing to seek back to update a header.

Hint 2

For columnar projection, store the byte offset and compressed/uncompressed byte length of each column chunk in the footer index.

Hint 3

Consider dictionary encoding and run-length encoding (RLE) for repeated values or null-indicator bitmasks to maximize compression efficiency.

Follow-up questions

  • How would you support variable-length strings or binary payloads (e.g., order IDs or execution reports) without losing predictable chunk offsets?
  • If your trading strategies run on NVMe drives with direct I/O (`O_DIRECT`), what alignment requirements does that impose on your page boundaries and row group layouts?
  • How would you evolve the file schema over time (e.g., adding an optional column) while maintaining backward and forward compatibility?