Matching Engine

The Matching Engine is a Rust microservice that performs deterministic, low-latency order matching using a price-time priority algorithm. It maintains in-memory order books per symbol, processes order commands from Kafka, generates trade executions and book deltas, and publishes them back to Kafka.

Responsibilities

• In-Memory Order Books: Maintain per-symbol order books using BTreeMap (sorted price levels) + HashMap (O(1) order lookup by ID).
• Deterministic Matching: Price-time priority (FIFO) matching. Same input sequence always produces same output.
• Order Type Support: Market, limit orders with GTC/IOC/FOK/GTD time-in-force. Post-only and reduce-only flags.
• Self-Trade Prevention (STP): Prevents a user’s buy order from matching against their own sell order.
• Event Publishing: Produces trade executions, book deltas, order status events, and snapshots to Kafka.
• Snapshots & Recovery: Periodic order book snapshots for fast recovery. Sequence numbers for deterministic replay.
• Metrics & Monitoring: Prometheus metrics for latency, throughput, book depth, and circuit breaker state.

The matching engine does not validate orders (that’s the Order Service), does not manage wallets, and does not compute P&L. It purely matches and produces events.

Architecture

graph TB OrderSvc[Order Service] -->|order.command.v1| Kafka1[Kafka] Kafka1 --> ME[Matching Engine] ME --> OrderBooks[In-Memory Order Books] ME -->|engine.event.v1| Kafka2[Kafka] Kafka2 --> OrderSvc2[Order Service] Kafka2 --> MDS[Market Data Service] Kafka2 --> PosSvc[Position Service] ME --> Redis[(Redis Cache)] ME --> Prometheus[Prometheus Metrics]

Core Data Structures (Rust)

Order

struct Order {
    id: Uuid,
    user_id: Uuid,
    account_id: Uuid,
    symbol: String,
    side: Side,           // Buy or Sell
    order_type: OrderType, // Limit or Market
    price: BigDecimal,     // fraction::BigDecimal for precision
    quantity: BigDecimal,
    remaining_qty: BigDecimal,
    time_in_force: TimeInForce, // GTC, IOC, FOK, GTD
    post_only: bool,
    reduce_only: bool,
    timestamp: u64,        // Epoch microseconds
    sequence: u64,         // Global sequence number
}

OrderBook (per symbol)

struct OrderBook {
    symbol: String,
    bids: BTreeMap<BigDecimal, VecDeque<Order>>,  // Price → FIFO queue (descending)
    asks: BTreeMap<BigDecimal, VecDeque<Order>>,  // Price → FIFO queue (ascending)
    id_map: HashMap<Uuid, (Side, BigDecimal)>,     // O(1) order lookup for cancel
    sequence: AtomicU64,   // Per-symbol sequence counter
}

Multi-Symbol Concurrency

// Concurrent hash map: one OrderBook per symbol
let books: DashMap<String, OrderBook> = DashMap::new();

• One thread per symbol: Each symbol’s order book is processed by a single dedicated thread (no locks needed within a symbol).
• CPU Pinning: Optional core affinity for latency-critical paths.
• No shared mutable state: Symbols are completely isolated from each other.

Matching Algorithm

Price-Time Priority (FIFO)

1. Buy orders: Sorted by price descending (highest bid first). At same price, earliest order first.
2. Sell orders: Sorted by price ascending (lowest ask first). At same price, earliest order first.

Matching Process

1. New order arrives from order.command.v1
2. Assign sequence number via get_next_sequence()
3. Self-Trade Prevention: Check if counterparty orders belong to same user_id — skip if so
4. Post-Only Check: If order would match immediately (take liquidity), reject it
5. Price Matching:
   • For a buy limit: match against asks where ask_price <= buy_price
   • For a sell limit: match against bids where bid_price >= sell_price
   • For market orders: match against all available liquidity at any price
6. Fill Generation: For each matched price level, fill orders in FIFO order
7. Quantity Resolution: Fill min(incoming_remaining, resting_remaining) per match
8. Time-in-Force:
   • GTC: Remaining quantity rests on the book
   • IOC: Cancel any unfilled remainder immediately
   • FOK: If full quantity can’t fill, cancel entire order
   • GTD: Like GTC but with expiry timestamp
9. Publish Events: Trade events, book deltas, and updated order statuses

Self-Trade Prevention (STP)

When an incoming order would match against a resting order from the same user_id:

• The match is skipped (the resting order is preserved)
• The incoming order continues to match against the next price level
• This prevents wash trading and accidental self-fills

Kafka Integration

Consumed Topics

Topic	Description
order.command.v1	Order commands: new, cancel, replace

Published Topics

Topic	Description
engine.event.v1	All engine events (trades, accepts, rejects, cancels, book deltas)
engine.snapshot.v1	Full order book snapshots (periodic)
engine.bookhash.v1	Order book integrity hashes

Event Types (engine.event.v1)

Event Type	Description
ORDER_ACCEPTED	Order added to book
ORDER_REJECTED	Order rejected (invalid, post-only violation, FOK fail)
ORDER_FILLED	Order fully filled
ORDER_PARTIALLY_FILLED	Partial fill
ORDER_CANCELED	Order canceled
ORDER_REPLACED	Order replaced (cancel + new)
ORDER_EXPIRED	GTD order expired
TRADE	Trade execution between two orders
BOOK_DELTA	Order book level change

Reject Reasons

Reason	Description
INSUFFICIENT_LIQUIDITY	Market order with no matching orders
POST_ONLY_VIOLATION	Post-only order would take liquidity
FOK_NOT_FILLABLE	FOK order can’t be completely filled
INSTRUMENT_HALTED	Trading halted for this symbol
DUPLICATE_ORDER_ID	Order ID already exists
INVALID_PRICE	Price not valid for instrument
INVALID_QUANTITY	Quantity not valid for instrument
SELF_TRADE	Would result in self-trade (if configured to reject)

Trade Event Structure

{
  "trade_id": "UUID",
  "symbol": "BTCUSDT-PERP",
  "price": "50000.00",
  "quantity": "1.5",
  "taker_side": "BUY",
  "maker_order_id": "UUID",
  "taker_order_id": "UUID",
  "maker_user_id": "UUID",
  "taker_user_id": "UUID",
  "maker_account_id": "UUID",
  "taker_account_id": "UUID",
  "is_buyer_maker": true,
  "sequence": 12345,
  "timestamp": 1700000000000
}

Snapshots & Recovery

Snapshotting

• Frequency: Every 5 seconds or every 10,000 sequence numbers (whichever comes first)
• Content: Full order book state (all resting orders per symbol)
• Storage: Published to engine.snapshot.v1 Kafka topic; cached in Redis
• Integrity: Book hash published to engine.bookhash.v1 for verification

Recovery

1. On startup, load latest snapshot from Redis (or Kafka)
2. Replay order.command.v1 events from the snapshot’s sequence number forward
3. Verify book hash matches expected state
4. Resume normal processing

Target recovery time: < 5 seconds

Sequence Numbers

• Each symbol has an independent sequence counter
• Every event includes the symbol’s current sequence number
• Consumers can detect gaps and request replay
• Deterministic: same input sequence always produces same output

Fencing

• Epoch-based fencing: The engine tracks an epoch counter that increments on recovery
• Prevents stale commands from a previous instance from being processed
• Incoming commands with an old epoch are rejected

Circuit Breakers

The engine implements circuit breakers that can halt processing:

• Consumer lag: If Kafka consumer falls behind by more than a configurable threshold
• Error rate: If error rate exceeds threshold
• Circuit breaker state is tracked and exposed via Prometheus metrics
• State transitions: CLOSED (normal) → OPEN (tripped) → HALF_OPEN (testing recovery)

Performance Characteristics

Targets

Metric	Target
Matching latency (p50)	< 200 microseconds
Matching latency (p99)	< 2 ms
Throughput per symbol	50,000 messages/second
Recovery time	< 5 seconds
Memory per 100K orders	~200 MB

Optimizations

• BigDecimal arithmetic: fraction::BigDecimal for exact decimal math (no floating-point errors)
• BTreeMap for price levels: O(log n) insert/remove, ordered iteration for matching
• VecDeque per price level: O(1) FIFO push/pop for time priority
• HashMap id_map: O(1) cancel by order ID (avoids linear scan)
• Zero-copy Kafka: Minimize allocations in the hot path

Observability

Metrics (Prometheus)

Exposed at /metrics endpoint:

• orders_processed_total{symbol,type} — Counter of processed orders
• matches_generated_total{symbol} — Counter of trade executions
• order_book_depth{symbol,side} — Gauge of resting orders per side
• matching_latency_seconds{symbol} — Histogram of matching time
• kafka_consumer_lag{topic} — Consumer lag
• circuit_breaker_state{component} — 0=closed, 1=open, 2=half-open
• snapshot_latency_seconds — Snapshot generation time

Health Check

GET /health → { "status": "healthy", "symbols": 5, "uptime_seconds": 3600 }

Logging

Structured logging via tracing crate: symbol, order_id, event_type, sequence, latency_us, trace_id.

Configuration

Variable	Description	Default
KAFKA_BROKERS	Kafka broker addresses	Required
REDIS_URL	Redis connection string	Required
SCHEMA_REGISTRY_URL	Avro schema registry	Required
HEALTH_CHECK_PORT	Health/metrics HTTP port	8086
SNAPSHOT_INTERVAL_SECS	Snapshot frequency	5
SNAPSHOT_INTERVAL_SEQS	Snapshot by sequence count	10000
LOG_LEVEL	Logging level	info

Project Structure

src/
├── main.rs                 # Entry point, Kafka consumer/producer setup
├── config/                 # Configuration loading
├── types/
│   ├── order.rs           # Order, Side, OrderType, TimeInForce
│   └── events.rs          # Engine event types
├── engine/
│   ├── matching_engine.rs # Core matching logic
│   └── orderbook.rs       # OrderBook struct and operations
├── kafka/
│   ├── consumer.rs        # Kafka consumer with Avro deserialization
│   └── producer.rs        # Kafka producer with Avro serialization
├── redis/
│   └── client.rs          # Redis client for snapshots
├── monitoring/
│   └── metrics.rs         # Prometheus metrics, circuit breakers
└── grpc/
    └── generated/         # Generated protobuf stubs

Technology Stack

• Language: Rust (stable)
• Async Runtime: Tokio
• Decimal Math: fraction::BigDecimal
• Concurrent Maps: dashmap::DashMap
• Kafka: rdkafka (librdkafka wrapper)
• Redis: redis-rs
• Metrics: prometheus crate
• Serialization: Apache Avro + Protobuf
• Build: Cargo with --release optimization

Related Documentation

• Order Service
• Market Data Service
• Kafka Events
• Architecture Overview