Orderbook Update 1: Core Data Structures

 Introduction

When implementing an orderbook system, the foundation lies in choosing the right data structures and abstractions. In this post, I'll walk through the key design decisions in building the core components of our C++ orderbook implementation.

Type Definitions and Performance Considerations

The first critical decision was selecting appropriate types for our core primitives:

using Price = std::int32_t;

using Quantity = std::uint32_t;

using OrderId = std::uint64_t;

These choices reflect careful consideration of both performance and practical requirements. Using fixed-width integer types ensures consistent behavior across platforms while providing sufficient range for practical trading scenarios. The decision to use signed integers for prices allows for negative values in certain market conditions, while quantities and order IDs are naturally unsigned.

Managing Price Levels

Price level management is crucial for orderbook performance. Our implementation uses a two-tiered approach:

struct LevelInfo {

    Price price_;

    Quantity quantity_;

};

using LevelInfos = std::vector<LevelInfo>;

The LevelInfo struct provides a compact representation of each price level, tracking only the essential price and quantity information. We use std::vector for LevelInfos to maintain cache-friendly memory access patterns when iterating through price levels.

The OrderbookLevelInfos class manages the separation between bid and ask sides:

class OrderbookLevelInfos {

public:

    OrderbookLevelInfos(const LevelInfos& bids, const LevelInfos& asks)

        : bids_{ bids }, asks_{ asks } {}

    const LevelInfos& GetBids() const { return bids_; }

    const LevelInfos& GetAsks() const { return asks_; }

private:

    LevelInfos bids_;

    LevelInfos asks_;

};

This design allows for efficient access to either side of the book while maintaining clear separation of concerns.

Order Management

The Order class forms the cornerstone of our implementation:

class Order {

public:

    Order(OrderType orderType, OrderId orderId, Side side, 

          Price price, Quantity quantity)

        : orderType_{ orderType }

        , orderId_{ orderId }

        , side_{ side }

        , price_{ price }

        , initialQuantity_{ quantity }

        , remainingQuantity_{ quantity }

    { }

    // ... getters and utility methods ...

};

Several key design decisions are reflected in this implementation:

Immutable Core Properties: OrderId, Side, and Price are immutable after construction, preventing accidental modifications during order processing.

Quantity Tracking: We maintain both initialQuantity_ and remainingQuantity_ to support partial fills while preserving order history.

State Management: The IsFilled() method provides a clear interface for checking order status, abstracting the underlying quantity comparisons.

Performance Implications

Our design choices prioritize performance in several ways:

Memory Layout: Using compact, fixed-size types minimizes cache misses and memory fragmentation.

Const Correctness: Extensive use of const member functions enables compiler optimizations and prevents accidental state mutations.

Pass-by-Reference: The LevelInfos vectors are passed by const reference to avoid unnecessary copying of price level data.

What's Next?

In the upcoming posts, I’ll dive into the details of:

1. Implementing the core functionality of the Order book.

2. Adding more complex order types and matching algorithms.

3. Optimizing for performance and low latency.

4. Implementing a simple interface for interacting with the Order book.

Thank you for following along on this journey. Stay tuned for more updates on the Order book.