Low-Latency Matching Engine

C++23 Modules Implementation for high-performance trading with optimized memory and IPC.

Overview

This project implements a low-latency trading engine using C++23 modules, semantic aliases, and lock-free design.

Key Features

Performance

• Throughput: 2,069,403 orders/second
• Latency: p50 = 0 ns, p99 = 100 ns, p99.9 = 200 ns
• Burst Performance: Up to 4,482,094 orders/second

Technical Specifications

• Execution Model: Single-threaded matching core; lock-free critical path.
• IPC Interface: SPSC ring buffers, UDP multicast, POSIX shared memory.
• Memory Management: Intrusive linked lists, object pools, and lock-free structures.
• Language Standards: ISO C++23 (Concepts, Templates, PMR).
• Modules: Semantic alias-based design with dependency graph: types → constants → engine_types → orderbook → engine.

Architecture

• Modules: matching_engine.types.ixx, matching_engine.constants.ixx, matching_engine.engine.ixx, matching_engine.orderbook.ixx, matching_engine.marketdata.ixx.
• Semantic Aliases: All raw types replaced (e.g., OrderId, Price, TimestampNs).
• OS Interface: Linux epoll (Edge-Triggered), POSIX Shared Memory, UDP Multicast.
• Protocol: Binary packed structures for network/IPC serialization.

System Architecture

Logical Components

┌─────────────────────────────────────────────────────────────────┐
│                     TCP Order Gateway                           │
│                    (epoll, non-blocking)                        │
└────────────────────────┬────────────────────────────────────────┘
                         │
                         ▼
┌─────────────────────────────────────────────────────────────────┐
│                    Matching Engine Core                          │
│              (single-threaded, lock-free)                        │
│  ┌──────────────────────────────────────────────────────────┐  │
│  │                    Order Book                              │  │
│  │  ┌─────────────┐  ┌─────────────┐  ┌─────────────┐      │  │
│  │  │  Bid Levels │  │  Ask Levels │  │  Order Map  │      │  │
│  │  └─────────────┘  └─────────────┘  └─────────────┘      │  │
│  └──────────────────────────────────────────────────────────┘  │
└────────────────────────┬────────────────────────────────────────┘
                         │
                         ▼
┌─────────────────────────────────────────────────────────────────┐
│              Lock-Free Ring Buffer (SPSC)                        │
│                   (trade notifications)                          │
└────────────────────────┬────────────────────────────────────────┘
                         │
                         ▼
┌─────────────────────────────────────────────────────────────────┐
│              Market Data Publisher                               │
│         ┌──────────────┐          ┌──────────────┐              │
│         │ UDP Publisher │          │ Shared Memory│              │
│         └──────────────┘          └──────────────┘              │
└─────────────────────────────────────────────────────────────────┘

Component Architecture

include/
├── engine/
│   ├── order.hpp              # Order structures and enums
│   └── matching_engine.hpp    # Core matching engine
├── orderbook/
│   ├── price_level.hpp        # Price level with intrusive list
│   └── order_book.hpp         # Order book with price levels
├── network/
│   ├── tcp_gateway.hpp        # TCP gateway with epoll
│   └── udp_publisher.hpp      # UDP multicast publisher
├── ipc/
│   ├── ring_buffer.hpp        # Lock-free SPSC ring buffer
│   └── shared_memory.hpp      # Shared memory IPC
├── memory/
│   └── object_pool.hpp        # Object pool allocator
└── utils/
    └── (utility functions)

Performance

Target Metrics

• Throughput: 4M+ orders/second
• p50 Latency: < 2 μs
• p99 Latency: < 10 μs
• p999 Latency: < 20 μs

Benchmark Results

Run the benchmark suite:

mkdir build && cd build
cmake ..
make benchmark
./benchmark

Example output:

========================================
  Low-Latency Matching Engine Benchmark  
========================================

=== Throughput Benchmark ===
Orders: 1000000
Trades: 500000
Time: 250000 μs
Throughput: 4000.0 orders/sec

=== Latency Benchmark ===
Samples: 50000
p50: 1500 ns
p99: 8500 ns
p999: 18000 ns

=== Burst Benchmark ===
Total Orders: 1000000
Total Time: 300000 μs
Average Throughput: 3333.33 orders/sec

Design Decisions

Why Single-Threaded Matching?

• Deterministic Latency: No thread contention or lock overhead
• Cache Locality: All data fits in CPU cache, minimal cache misses
• Simplified Logic: No race conditions or complex synchronization
• Predictable Performance: Consistent latency regardless of load

Why Lock-Free Queues?

• Zero-Wait Communication: No blocking between producer/consumer
• Cache Efficiency: Proper memory ordering and cache line alignment
• Scalability: No contention points in critical path
• Modern Hardware: Leverages atomic operations efficiently

Why Cache Locality Matters?

• Memory Bandwidth: Main memory is ~100x slower than L1 cache
• False Sharing: Cache line bouncing kills performance
• Prefetching: Contiguous memory enables hardware prefetching
• NUMA Awareness: Critical for multi-socket systems

Why Shared Memory IPC?

• Zero-Copy: No serialization/deserialization overhead
• Low Latency: Direct memory access between processes
• High Throughput: No context switching or syscalls
• Scalability: Multiple consumers can read same data

Low-Latency Optimizations

Memory Management

• Object Pools: Preallocated memory blocks eliminate heap allocations
• Slab Allocators: Fixed-size blocks for order book nodes
• Cache Line Alignment: 64-byte aligned structures to avoid false sharing
• Contiguous Storage: Arrays and vectors for cache-friendly access

CPU Optimizations

• CPU Affinity: Pin threads to specific cores (pthread_setaffinity_np)
• Huge Pages: Reduce TLB misses for large memory regions
• NUMA Awareness: Allocate memory on local NUMA node
• Instruction Cache: Hot code paths kept small and linear

Network Optimizations

• epoll: Scalable I/O event notification
• Non-Blocking Sockets: No thread blocking on I/O
• Binary Protocol: Packed structs, no parsing overhead
• Zero-Copy: Direct memory access for network buffers

Data Structure Optimizations

• Intrusive Linked Lists: Nodes embedded in structures, no extra allocations
• Price-Time Priority: Efficient order matching with O(1) operations
• Hash Maps: O(1) order lookup by ID
• Preallocated Buffers: No runtime memory allocation in hot path

Build Instructions

Prerequisites

• C++23 compatible compiler (GCC 13+, Clang 16+)
• CMake 3.20 or higher
• Linux operating system (kernel 5.0+)
• pthread library
• librt (real-time extensions)

Building

# Clone the repository
git clone https://github.com/yourusername/cpp-low-latency-matching-engine.git
cd cpp-low-latency-matching-engine

# Create build directory
mkdir build && cd build

# Configure with CMake
cmake -DCMAKE_BUILD_TYPE=Release ..

# Build
make -j$(nproc)

# Run tests
ctest

# Run benchmarks
./benchmark

Build Options

# Debug build with symbols
cmake -DCMAKE_BUILD_TYPE=Debug ..

# Release build with optimizations
cmake -DCMAKE_BUILD_TYPE=Release ..

# Enable additional compiler warnings
cmake -DCMAKE_CXX_FLAGS="-Wall -Wextra -Wpedantic" ..

Usage

The repository builds several executable targets that demonstrate engine usage, networking integration, and performance characteristics.

Executable targets

demo

• Purpose: Runs an integrated demonstration of the matching engine with throughput, latency, order book visualization, and burst analysis.
• Build: cmake --build build --target demo
• Run: cd build && ./demo
• Alternative target: cmake --build build --target run_demo
• Output interpretation:
  • Throughput Benchmark reports orders processed per second.
  • Latency Distribution Benchmark prints p50, p90, p99, p999, and maximum latency in nanoseconds.
  • Order Book Depth Visualizer shows example book state after order submission.
  • Burst Benchmark reports burst order throughput and average throughput.

benchmark

• Purpose: Measures engine performance and prints benchmark metrics.
• Build: cmake --build build --target benchmark
• Run: cd build && ./benchmark
• Output interpretation:
  • Orders: number of orders submitted in the benchmark stage.
  • Trades: number of matched trades produced.
  • Time: elapsed time for the benchmark stage.
  • Throughput: orders per second; higher is better.
  • Latency percentiles show distribution stability.

matching_engine_example

• Purpose: Minimal example of direct matching engine usage from application code.
• Build: cmake --build build --target matching_engine_example
• Run: cd build && ./matching_engine_example
• Output interpretation:
  • The example prints trade execution lines when matching occurs.
  • If no trades are printed, the sample order flow did not cross.

tcp_gateway_example

• Purpose: Demonstrates the TCP gateway accepting orders over TCP and submitting them to the engine.
• Build: cmake --build build --target tcp_gateway_example
• Run: cd build && ./tcp_gateway_example
• Behavior:
  • Listens on 0.0.0.0:9000.
  • Incoming TCP messages are processed by the gateway and forwarded to the matching engine.
  • Matched trades are printed to stdout.
• Output interpretation:
  • If the gateway starts successfully, it is ready to accept connections.
  • Trade log lines show successful matching of orders received over TCP.

Example TCP Client (Python)

You can use a simple Python script to send NewOrder messages to the tcp_gateway_example.

1. Save the following code as tcp_client.py:

   import socket
   import struct
   import time
   
   # Define message types and order sides/types as per your C++ structs
   MESSAGE_TYPE_NEW_ORDER = 1
   ORDER_SIDE_BUY = 0
   ORDER_SIDE_SELL = 1
   ORDER_TYPE_LIMIT = 0
   
   # NewOrderMessage struct format:
   # OrderId (uint64_t)
   # UserId (uint64_t)
   # m_side (uint8_t)
   # m_type (uint8_t)
   # Price (uint32_t)
   # Quantity (uint32_t)
   NEW_ORDER_FORMAT = "<QQBBII" # Little-endian: 2x unsigned long long, 2x unsigned char, 2x unsigned int
   
   # MessageHeader struct format:
   # m_type (uint8_t)
   # m_length (uint16_t)
   HEADER_FORMAT = "<BH" # Little-endian: unsigned char, unsigned short
   
   def send_new_order(order_id, user_id, side, order_type, price, quantity):
       order_message_data = struct.pack(NEW_ORDER_FORMAT, order_id, user_id, side, order_type, price, quantity)
       header_data = struct.pack(HEADER_FORMAT, MESSAGE_TYPE_NEW_ORDER, len(order_message_data))
   
       try:
           with socket.socket(socket.AF_INET, socket.SOCK_STREAM) as sock:
               sock.connect(("127.0.0.1", 9000))
               sock.sendall(header_data + order_message_data)
               print(f"Sent Order: ID={order_id}, User={user_id}, Side={side}, Type={order_type}, Price={price}, Qty={quantity}")
       except ConnectionRefusedError:
           print("Error: Connection refused. Is tcp_gateway_example running?")
       except Exception as e:
           print(f"An error occurred: {e}")
   
   def send_orders_batch(count, start_id, start_user, start_price, side):
       for i in range(count):
           send_new_order(
               order_id=start_id + i,
               user_id=start_user + i,
               side=side,
               order_type=ORDER_TYPE_LIMIT,
               price=start_price + i,
               quantity=100 + i * 10
           )
           time.sleep(0.01) # Small delay to simulate real-world order flow
   
   if __name__ == "__main__":
       print("Sending sample orders to TCP Gateway...")
       
       # Send BUY orders
       send_orders_batch(100, start_id=1000, start_user=1, start_price=1000, side=ORDER_SIDE_BUY)
       time.sleep(1) # Wait a bit before sending sell orders
       
       # Send SELL orders
       send_orders_batch(100, start_id=2000, start_user=200, start_price=998, side=ORDER_SIDE_SELL)
       print("Finished sending orders.")

udp_feed_example

• Purpose: Demonstrates UDP multicast market data publishing for trades and book updates.
• Build: cmake --build build --target udp_feed_example
• Run: cd build && ./udp_feed_example
• Behavior:
  • Starts a UDP publisher on multicast address 239.255.0.1:9001.
  • Publishes trade and top-of-book update messages.
• Output interpretation:
  • Running the executable indicates the publisher is active.
  • Running the executable indicates the publisher is active.
  • To verify the feed, you need a multicast listener.

Example UDP Multicast Listener (Python)

Market data is published as packed binary structures. Use this script to join the multicast group and decode the messages.

1. Save the following code as udp_listener.py:

   import socket
   import struct
   
   MCAST_GRP = '239.255.0.1'
   MCAST_PORT = 9001
   
   # Binary formats based on #pragma pack(push, 1) structs in include/network/udp_publisher.hpp
   # I = uint32, Q = uint64, B = uint8
   TRADE_FORMAT = "<IQQQIIQ"      # 44 bytes
   TOB_FORMAT = "<IIIIIQ"         # 28 bytes
   DEPTH_FORMAT = "<IIIBQ"        # 21 bytes
   
   def start_listening():
       sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM, socket.IPPROTO_UDP)
       sock.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1)
       
       # Bind to the port
       sock.bind(('', MCAST_PORT))
   
       # Join the multicast group
       mreq = struct.pack("4sl", socket.inet_aton(MCAST_GRP), socket.INADDR_ANY)
       sock.setsockopt(socket.IPPROTO_IP, socket.IP_ADD_MEMBERSHIP, mreq)
   
       print(f"Joined Multicast Group {MCAST_GRP}:{MCAST_PORT}. Waiting for data...")
   
       while True:
           data, addr = sock.recvfrom(1024)
           data_len = len(data)
   
           if data_len == 44:  # TradeMessage
               msg = struct.unpack(TRADE_FORMAT, data)
               print(f"[TRADE] Sym: {msg[0]}, Price: {msg[4]}, Qty: {msg[5]}, ID: {msg[1]}")
           elif data_len == 28:  # TopOfBookMessage
               msg = struct.unpack(TOB_FORMAT, data)
               print(f"[TOB]   Sym: {msg[0]}, Bid: {msg[1]}@{msg[2]}, Ask: {msg[3]}@{msg[4]}")
           elif data_len == 21:  # DepthUpdateMessage
               msg = struct.unpack(DEPTH_FORMAT, data)
               side = "BUY" if msg[3] == 0 else "SELL"
               print(f"[DEPTH] Sym: {msg[0]}, {side} {msg[1]}@{msg[2]}")
           else:
               print(f"Unknown message length received: {data_len}")
   
   if __name__ == "__main__":
       start_listening()

2. How to run:

   • In one terminal, run the publisher: ./udp_feed_example
   • In another terminal, run the listener: python3 udp_listener.py
   • You will see Trade and Top-of-Book updates decoded on the screen.

Test targets

The repository also builds unit-test executables:

• test_orderbook
• test_matching_engine
• test_ring_buffer

How to run tests

• Build tests: cmake --build build --target all
• Run all tests: cd build && ctest --output-on-failure
• Run a single binary: cd build && ./test_orderbook

Interpreting test results

• Exit code 0 means the test passed.
• Any non-zero exit indicates a failure in that component.
• Use ctest --verbose for detailed output on failing assertions.

Example usage patterns

Build and run the full example set:

mkdir -p build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
cmake --build . --target all
./demo

Run the benchmark directly:

cd build
cmake --build . --target benchmark
./benchmark

Validate the core components with tests:

cd build
ctest --output-on-failure

Testing

Running Tests

cd build
ctest --verbose

Test Coverage

• Order Book Tests: Basic operations, price levels, order management
• Matching Engine Tests: Limit orders, market orders, cancellation, modification
• Ring Buffer Tests: Basic operations, concurrent access, edge cases

Writing Tests

Tests are located in the tests/ directory and use simple assert-based testing:

#include "engine/matching_engine.hpp"
#include <cassert>

void test_limit_order() {
    MatchingEngine engine;
    Order order(1, 1, OrderSide::BUY, OrderType::LIMIT, 1000, 100);
    OrderStatus status = engine.submit_order(order);
    assert(status == OrderStatus::PENDING);
}

Future Improvements

• Persistence: Write-ahead log for crash recovery
• Multi-Symbol Support: Multiple instruments with partitioned order books
• Risk Management: Position limits, credit checks
• Market Data Protocol: FIX/FAST protocol support
• FPGA Acceleration: Offload matching to FPGA
• Kernel Bypass: DPDK or Solarflare for ultra-low latency networking
• GPU Acceleration: Use CUDA for parallel order matching
• Distributed Deployment: Multi-region deployment with consensus

License

MIT License - See LICENSE file for details

Contributing

Contributions are welcome! Please read CONTRIBUTING.md for guidelines.

Contact

For questions or support, please open an issue on GitHub.