Биржа: matching engine

<?php

declare(strict_types=1);

enum OrderSide: int
{
    case Buy = 1;
    case Sell = 2;
}

enum OrderType: int
{
    case Limit     = 1;
    case Market    = 2;
    case StopLimit = 3;
    case IOC       = 4;
    case FOK       = 5;
}

final readonly class NewOrderRequest
{
    public function __construct(
        public string $clientOrderId,
        public string $symbol,
        public OrderSide $side,
        public OrderType $type,
        public int $price,    // in ticks, integer math only
        public int $quantity,
        public string $timeInForce,
    ) {}
}

final readonly class ExecutionReport
{
    public function __construct(
        public int $orderId,
        public string $clientOrderId,
        public string $status,
        public int $filledQty,
        public int $avgPrice,
        public \DateTimeImmutable $ts,
    ) {}
}

package api

import "time"

// OrderSide is Buy or Sell.
type OrderSide uint8

const (
    SideBuy  OrderSide = 1
    SideSell OrderSide = 2
)

// OrderType enumerates supported order types.
type OrderType uint8

const (
    OrderLimit     OrderType = 1
    OrderMarket    OrderType = 2
    OrderStopLimit OrderType = 3
    OrderIOC       OrderType = 4 // immediate-or-cancel
    OrderFOK       OrderType = 5 // fill-or-kill
)

// NewOrderRequest is what the gateway forwards to the engine.
type NewOrderRequest struct {
    ClientOrderID string    `json:"client_order_id"`
    Symbol        string    `json:"symbol"`
    Side          OrderSide `json:"side"`
    Type          OrderType `json:"type"`
    Price         int64     `json:"price"` // ticks, not float
    Quantity      int64     `json:"quantity"`
    TimeInForce   string    `json:"tif"`
    Ts            time.Time `json:"ts"`
}

// ExecutionReport is an ack/fill notification sent to the client.
type ExecutionReport struct {
    OrderID       uint64    `json:"order_id"`
    ClientOrderID string    `json:"client_order_id"`
    Status        string    `json:"status"` // NEW, PARTIALLY_FILLED, FILLED, CANCELED, REJECTED
    FilledQty     int64     `json:"filled_qty"`
    AvgPrice      int64     `json:"avg_price"`
    Ts            time.Time `json:"ts"`
}

using System.Text.Json.Serialization;

namespace Exchange.Api;

// OrderSide is Buy or Sell.
public enum OrderSide : byte
{
    Buy = 1,
    Sell = 2,
}

// OrderType enumerates supported order types.
public enum OrderType : byte
{
    Limit = 1,
    Market = 2,
    StopLimit = 3,
    Ioc = 4, // immediate-or-cancel
    Fok = 5, // fill-or-kill
}

// NewOrderRequest is what the gateway forwards to the engine.
public sealed record NewOrderRequest(
    [property: JsonPropertyName("client_order_id")] string ClientOrderId,
    [property: JsonPropertyName("symbol")] string Symbol,
    [property: JsonPropertyName("side")] OrderSide Side,
    [property: JsonPropertyName("type")] OrderType Type,
    [property: JsonPropertyName("price")] long Price, // ticks, not decimal/double
    [property: JsonPropertyName("quantity")] long Quantity,
    [property: JsonPropertyName("tif")] string TimeInForce,
    [property: JsonPropertyName("ts")] DateTimeOffset Ts);

// ExecutionReport is an ack/fill notification sent to the client.
public sealed record ExecutionReport(
    [property: JsonPropertyName("order_id")] ulong OrderId,
    [property: JsonPropertyName("client_order_id")] string ClientOrderId,
    // NEW, PARTIALLY_FILLED, FILLED, CANCELED, REJECTED
    [property: JsonPropertyName("status")] string Status,
    [property: JsonPropertyName("filled_qty")] long FilledQty,
    [property: JsonPropertyName("avg_price")] long AvgPrice,
    [property: JsonPropertyName("ts")] DateTimeOffset Ts);

from __future__ import annotations

from dataclasses import dataclass
from datetime import datetime
from enum import IntEnum

# OrderSide is Buy or Sell.
class OrderSide(IntEnum):
    BUY = 1
    SELL = 2

# OrderType enumerates supported order types.
class OrderType(IntEnum):
    LIMIT = 1
    MARKET = 2
    STOP_LIMIT = 3
    IOC = 4  # immediate-or-cancel
    FOK = 5  # fill-or-kill

# NewOrderRequest is what the gateway forwards to the engine.
@dataclass(frozen=True, slots=True)
class NewOrderRequest:
    client_order_id: str
    symbol: str
    side: OrderSide
    type: OrderType
    price: int  # ticks, not float
    quantity: int
    time_in_force: str
    ts: datetime

# ExecutionReport is an ack/fill notification sent to the client.
@dataclass(frozen=True, slots=True)
class ExecutionReport:
    order_id: int
    client_order_id: str
    status: str  # NEW, PARTIALLY_FILLED, FILLED, CANCELED, REJECTED
    filled_qty: int
    avg_price: int
    ts: datetime

package engine

import (
    "container/list"
    "sync/atomic"
)

// Order represents a single resting order at a price level.
type Order struct {
    ID        uint64
    ClientID  string
    Side      OrderSide
    Price     int64
    Qty       int64
    Remaining int64
    SeqNo     uint64 // for strict time priority (cheaper than time.Time)
}

// priceLevel holds a FIFO queue of orders at the same price.
type priceLevel struct {
    Price  int64
    Orders *list.List // list.Element.Value = *Order
    Total  int64      // aggregate remaining qty for fast L2 snapshots
}

// OrderBook stores bids and asks for a single symbol. Not thread-safe:
// each symbol runs on its own goroutine.
type OrderBook struct {
    Symbol string
    Bids   *SkipList // sorted DESC by price
    Asks   *SkipList // sorted ASC by price
    orders map[uint64]*Order
    nextID atomic.Uint64
}

// Match attempts to fill an incoming order against the opposite side.
// Returns trades executed and the remaining order (if any).
func (ob *OrderBook) Match(in *Order) ([]Trade, *Order) {
    trades := make([]Trade, 0, 4)
    book := ob.Asks
    if in.Side == SideSell {
        book = ob.Bids
    }

    for in.Remaining > 0 {
        top := book.Top()
        if top == nil {
            break
        }
        // Price check depending on side
        if in.Side == SideBuy && top.Price > in.Price {
            break
        }
        if in.Side == SideSell && top.Price < in.Price {
            break
        }

        for e := top.Orders.Front(); e != nil && in.Remaining > 0; {
            maker := e.Value.(*Order)
            fillQty := min64(in.Remaining, maker.Remaining)

            trades = append(trades, Trade{
                Price:    maker.Price,
                Qty:      fillQty,
                TakerID:  in.ID,
                MakerID:  maker.ID,
            })
            in.Remaining -= fillQty
            maker.Remaining -= fillQty
            top.Total -= fillQty

            next := e.Next()
            if maker.Remaining == 0 {
                top.Orders.Remove(e)
                delete(ob.orders, maker.ID)
            }
            e = next
        }

        if top.Orders.Len() == 0 {
            book.RemoveTop()
        }
    }

    if in.Remaining == 0 {
        return trades, nil
    }
    return trades, in
}

// Add places a resting order into the book (after matching did not fully fill).
func (ob *OrderBook) Add(o *Order) {
    book := ob.Bids
    if o.Side == SideSell {
        book = ob.Asks
    }
    lvl := book.GetOrInsert(o.Price)
    lvl.Orders.PushBack(o)
    lvl.Total += o.Remaining
    ob.orders[o.ID] = o
}

func min64(a, b int64) int64 {
    if a < b {
        return a
    }
    return b
}

using System.Collections.Generic;
using System.Linq;

namespace Exchange.Engine;

// Order represents a single resting order at a price level.
// A class (not a struct): the book hands out shared references, like *Order in Go.
public sealed class Order
{
    public required ulong Id { get; init; }
    public required string ClientId { get; init; }
    public required OrderSide Side { get; init; }
    public required long Price { get; init; }
    public required long Qty { get; init; }
    public required long Remaining { get; set; }
    public required ulong SeqNo { get; init; } // for strict time priority (cheaper than DateTime)
}

// Trade is emitted for every fill. Readonly struct: no allocation in the hot path.
public readonly record struct Trade(long Price, long Qty, ulong TakerId, ulong MakerId);

// PriceLevel holds a FIFO queue of orders at the same price.
public sealed class PriceLevel(long price)
{
    public long Price { get; } = price;
    public LinkedList<Order> Orders { get; } = new();
    public long Total { get; set; } // aggregate remaining qty for fast L2 snapshots
}

// OrderBook stores bids and asks for a single symbol. Not thread-safe:
// each symbol runs on its own dedicated thread.
public sealed class OrderBook(string symbol)
{
    // .NET has no skip list in the BCL. SortedDictionary is a red-black tree:
    // same O(log N) insert/remove and ordered traversal for L2 snapshots.
    // The bid side uses a reversed comparer, so the first key is always the best price.
    private readonly SortedDictionary<long, PriceLevel> _bids =
        new(Comparer<long>.Create(static (a, b) => b.CompareTo(a)));

    private readonly SortedDictionary<long, PriceLevel> _asks = new();
    private readonly Dictionary<ulong, Order> _orders = new();

    public string Symbol { get; } = symbol;

    // Match attempts to fill an incoming order against the opposite side.
    // Returns trades executed and the remaining order (null if fully filled).
    public (List<Trade> Trades, Order? Rest) Match(Order incoming)
    {
        var trades = new List<Trade>(4);
        var book = incoming.Side == OrderSide.Sell ? _bids : _asks;

        while (incoming.Remaining > 0 && book.Count > 0)
        {
            var top = book.First().Value;

            // Price check depending on side
            if (incoming.Side == OrderSide.Buy && top.Price > incoming.Price)
            {
                break;
            }

            if (incoming.Side == OrderSide.Sell && top.Price < incoming.Price)
            {
                break;
            }

            for (var node = top.Orders.First; node is not null && incoming.Remaining > 0;)
            {
                var maker = node.Value;
                var fillQty = Math.Min(incoming.Remaining, maker.Remaining);

                trades.Add(new Trade(maker.Price, fillQty, incoming.Id, maker.Id));
                incoming.Remaining -= fillQty;
                maker.Remaining -= fillQty;
                top.Total -= fillQty;

                var next = node.Next;
                if (maker.Remaining == 0)
                {
                    top.Orders.Remove(node);
                    _orders.Remove(maker.Id);
                }

                node = next;
            }

            if (top.Orders.Count == 0)
            {
                book.Remove(top.Price);
            }
        }

        return incoming.Remaining == 0 ? (trades, null) : (trades, incoming);
    }

    // Add places a resting order into the book (after matching did not fully fill).
    public void Add(Order o)
    {
        var book = o.Side == OrderSide.Sell ? _asks : _bids;
        if (!book.TryGetValue(o.Price, out var level))
        {
            level = new PriceLevel(o.Price);
            book.Add(o.Price, level);
        }

        level.Orders.AddLast(o);
        level.Total += o.Remaining;
        _orders[o.Id] = o;
    }
}

from __future__ import annotations

from bisect import insort
from collections import deque
from dataclasses import dataclass, field

from exchange.api import OrderSide

# Order represents a single resting order at a price level.
@dataclass(slots=True)
class Order:
    id: int
    client_id: str
    side: OrderSide
    price: int
    qty: int
    remaining: int
    seq_no: int  # for strict time priority (cheaper than a timestamp)

# Trade is emitted for every fill.
@dataclass(frozen=True, slots=True)
class Trade:
    price: int
    qty: int
    taker_id: int
    maker_id: int

# PriceLevel holds a FIFO queue of orders at the same price.
@dataclass(slots=True)
class PriceLevel:
    price: int
    orders: deque[Order] = field(default_factory=deque)
    total: int = 0  # aggregate remaining qty for fast L2 snapshots

# OrderBook stores bids and asks for a single symbol. Not thread-safe:
# each symbol runs in its own process (the GIL makes threads pointless here).
class OrderBook:
    def __init__(self, symbol: str) -> None:
        self.symbol = symbol
        self._bids: dict[int, PriceLevel] = {}
        self._asks: dict[int, PriceLevel] = {}
        # No skip list in the stdlib: price keys are kept in a bisect-sorted
        # list (ASC), so best ask is prices[0] and best bid is prices[-1].
        self._bid_prices: list[int] = []
        self._ask_prices: list[int] = []
        self._orders: dict[int, Order] = {}

    # Matches an incoming order against the opposite side.
    # Returns trades executed and the remaining order (None if fully filled).
    def match(self, incoming: Order) -> tuple[list[Trade], Order | None]:
        trades: list[Trade] = []
        buying = incoming.side is OrderSide.BUY
        levels = self._asks if buying else self._bids
        prices = self._ask_prices if buying else self._bid_prices

        while incoming.remaining > 0 and prices:
            best_price = prices[0] if buying else prices[-1]

            # Price check depending on side
            if buying and best_price > incoming.price:
                break
            if not buying and best_price < incoming.price:
                break

            top = levels[best_price]
            # Fills always consume the head of the queue, so a filled maker
            # is always at the left end -- popleft keeps time priority intact.
            while top.orders and incoming.remaining > 0:
                maker = top.orders[0]
                fill_qty = min(incoming.remaining, maker.remaining)

                trades.append(Trade(maker.price, fill_qty, incoming.id, maker.id))
                incoming.remaining -= fill_qty
                maker.remaining -= fill_qty
                top.total -= fill_qty

                if maker.remaining == 0:
                    top.orders.popleft()
                    del self._orders[maker.id]

            if not top.orders:
                del levels[best_price]
                if buying:
                    prices.pop(0)
                else:
                    prices.pop()

        return (trades, None) if incoming.remaining == 0 else (trades, incoming)

    # Places a resting order into the book (after matching did not fully fill).
    def add(self, order: Order) -> None:
        selling = order.side is OrderSide.SELL
        levels = self._asks if selling else self._bids
        prices = self._ask_prices if selling else self._bid_prices

        level = levels.get(order.price)
        if level is None:
            level = PriceLevel(order.price)
            levels[order.price] = level
            insort(prices, order.price)

        level.orders.append(order)
        level.total += order.remaining
        self._orders[order.id] = order