Разработка стакана ордеров (order book)

Разработка стакана ордеров (order book)

Order book — центральный компонент любой биржи. Это упорядоченный список заявок на покупку и продажу актива. Производительность order book напрямую определяет возможности всей торговой системы: от latency исполнения до максимального throughput.

Структура данных

In-memory order book

Order book живёт в оперативной памяти. Доступ к диску при каждом matching — неприемлемо по latency.

Классическая структура: два отсортированных контейнера — bid side (покупки, по убыванию цены) и ask side (продажи, по возрастанию цены). На каждом ценовом уровне — очередь ордеров (FIFO для price-time priority).

type Order struct {
    ID        string
    UserID    int64
    Side      Side      // Buy | Sell
    Type      OrderType // Limit | Market
    Price     decimal.Decimal
    Quantity  decimal.Decimal
    FilledQty decimal.Decimal
    CreatedAt int64     // nanosecond timestamp
}

type PriceLevel struct {
    Price  decimal.Decimal
    Orders []*Order  // FIFO queue
}

type OrderBook struct {
    Bids    *redblacktree.Tree  // Price -> *PriceLevel, descending
    Asks    *redblacktree.Tree  // Price -> *PriceLevel, ascending
    Orders  map[string]*Order   // OrderID -> Order (для быстрой отмены)
    mu      sync.RWMutex
}

Выбор tree-структуры:

• Red-black tree: O(log n) для всех операций. emirpasic/gods — хорошая Go реализация
• Skip list: конкурентный, но сложнее в реализации. Lockfree skip list даёт лучшую масштабируемость
• Sorted slice + binary search: O(n) insert, O(log n) search. Работает для небольших books (< 1000 levels)

Операции order book

// Добавление ордера
func (ob *OrderBook) Add(order *Order) ([]Trade, error) {
    ob.mu.Lock()
    defer ob.mu.Unlock()
    
    // Сначала пробуем match
    trades := ob.matchOrder(order)
    
    // Если ордер не исполнен полностью — помещаем в book
    if order.FilledQty.LessThan(order.Quantity) && order.Type == Limit {
        ob.placeInBook(order)
    }
    
    return trades, nil
}

// Отмена ордера — O(1) через hashmap
func (ob *OrderBook) Cancel(orderID string) error {
    ob.mu.Lock()
    defer ob.mu.Unlock()
    
    order, exists := ob.Orders[orderID]
    if !exists {
        return ErrOrderNotFound
    }
    
    level := ob.getLevel(order.Side, order.Price)
    level.removeOrder(orderID)
    delete(ob.Orders, orderID)
    
    if len(level.Orders) == 0 {
        ob.removeLevel(order.Side, order.Price)
    }
    
    return nil
}

Важный момент: отмена ордера должна работать за O(1) по orderID, не O(n) с поиском по всем уровням. Для этого — hashmap Orders map[string]*Order с прямым доступом.

Matching алгоритм

Price-Time Priority (FIFO)

Стандарт для большинства бирж. Ордер с лучшей ценой исполняется первым. При одинаковой цене — более ранний по времени.

func (ob *OrderBook) matchOrder(taker *Order) []Trade {
    var trades []Trade
    
    counterSide := ob.getCounterBook(taker.Side)
    
    for taker.RemainingQty().IsPositive() {
        bestLevel := ob.getBestLevel(counterSide)
        if bestLevel == nil {
            break
        }
        
        if !ob.priceCrosses(taker, bestLevel.Price) {
            break // нет match по цене
        }
        
        for len(bestLevel.Orders) > 0 && taker.RemainingQty().IsPositive() {
            maker := bestLevel.Orders[0]
            fillQty := decimal.Min(taker.RemainingQty(), maker.RemainingQty())
            
            trade := Trade{
                Price:        bestLevel.Price,
                Quantity:     fillQty,
                TakerOrderID: taker.ID,
                MakerOrderID: maker.ID,
                TakerSide:    taker.Side,
                Timestamp:    time.Now().UnixNano(),
            }
            trades = append(trades, trade)
            
            taker.FilledQty = taker.FilledQty.Add(fillQty)
            maker.FilledQty = maker.FilledQty.Add(fillQty)
            
            if maker.RemainingQty().IsZero() {
                bestLevel.Orders = bestLevel.Orders[1:]
                delete(ob.Orders, maker.ID)
            }
        }
        
        if len(bestLevel.Orders) == 0 {
            ob.removeLevel(counterSide, bestLevel.Price)
        }
    }
    
    return trades
}

Pro-Rata matching

Используется на некоторых деривативных биржах (CME). Объём распределяется пропорционально размеру ордеров на уровне, а не по времени прихода.

func (ob *OrderBook) proRataMatch(taker *Order, level *PriceLevel) []Trade {
    totalSize := level.TotalSize()
    fillQty := decimal.Min(taker.RemainingQty(), totalSize)
    
    var trades []Trade
    for _, maker := range level.Orders {
        // Пропорциональный fill
        makerShare := maker.RemainingQty().Div(totalSize)
        makerFill := fillQty.Mul(makerShare).RoundDown(8)
        
        if makerFill.IsPositive() {
            trades = append(trades, Trade{
                Price: level.Price, Quantity: makerFill,
                TakerOrderID: taker.ID, MakerOrderID: maker.ID,
            })
        }
    }
    return trades
}

Pro-Rata создаёт инцентив к выставлению крупных ордеров, что увеличивает ликвидность. Но провоцирует спам: трейдеры ставят крупные ордера и немедленно уменьшают при fill.

Снэпшот и инкрементальные обновления

Клиент не получает весь order book при подключении — это может быть мегабайты данных. Архитектура:

1. Клиент запрашивает снэпшот (top N levels, например 50) через REST
2. Подписывается на WebSocket channel diff updates
3. Применяет diff к локальной копии

// Снэпшот — top 50 levels bid/ask
type OrderBookSnapshot struct {
    Sequence uint64        `json:"seq"`     // монотонный счётчик
    Bids     []PriceSizeKV `json:"bids"`    // [[price, size], ...]
    Asks     []PriceSizeKV `json:"asks"`
    Timestamp int64        `json:"ts"`
}

// Diff update — изменения с момента последнего sequence
type OrderBookDiff struct {
    Sequence uint64        `json:"seq"`
    Bids     []PriceSizeKV `json:"bids"` // size=0 означает удаление уровня
    Asks     []PriceSizeKV `json:"asks"`
}

Клиент отбрасывает diff с seq <= snapshot.Sequence (уже в снэпшоте), применяет все последующие. Если пропустил несколько updates — запрашивает новый снэпшот.

class OrderBookClient {
  private bids = new Map<string, string>(); // price -> size
  private asks = new Map<string, string>();
  private lastSeq = 0;
  
  applySnapshot(snap: OrderBookSnapshot) {
    this.bids.clear();
    this.asks.clear();
    snap.bids.forEach(([p, s]) => this.bids.set(p, s));
    snap.asks.forEach(([p, s]) => this.asks.set(p, s));
    this.lastSeq = snap.sequence;
  }
  
  applyDiff(diff: OrderBookDiff) {
    if (diff.sequence <= this.lastSeq) return; // outdated
    if (diff.sequence !== this.lastSeq + 1) {
      this.requestSnapshot(); // gap — нужен новый снэпшот
      return;
    }
    
    diff.bids.forEach(([p, s]) => {
      if (s === '0') this.bids.delete(p);
      else this.bids.set(p, s);
    });
    diff.asks.forEach(([p, s]) => {
      if (s === '0') this.asks.delete(p);
      else this.asks.set(p, s);
    });
    
    this.lastSeq = diff.sequence;
  }
}

Визуализация order book

Группировка по тикам

Реальный order book может иметь тысячи ценовых уровней. Для отображения — группировка по "тику" (минимальный шаг отображения):

function groupOrderBook(
  levels: [string, string][], 
  tickSize: number, 
  depth: number
): GroupedLevel[] {
  const grouped = new Map<number, number>();
  
  for (const [priceStr, sizeStr] of levels) {
    const price = parseFloat(priceStr);
    const size = parseFloat(sizeStr);
    const bucket = Math.floor(price / tickSize) * tickSize;
    grouped.set(bucket, (grouped.get(bucket) ?? 0) + size);
  }
  
  return Array.from(grouped.entries())
    .sort((a, b) => b[0] - a[0])  // descending for bids
    .slice(0, depth)
    .map(([price, size]) => ({ price, size }));
}

Тики переключаются пользователем (0.01, 0.1, 1, 10, 100 для BTC/USDT) — это меняет детализацию отображения.

Depth bar (полоска глубины)

Визуальный индикатор относительного объёма на уровне:

const OrderBookRow: React.FC<RowProps> = ({ price, size, total, maxTotal, side }) => {
  const depthPct = (total / maxTotal) * 100;
  
  return (
    <div className="relative flex justify-between px-2 py-0.5 text-xs font-mono">
      {/* Фоновая полоска */}
      <div
        className={`absolute inset-y-0 ${side === 'bid' ? 'left-0' : 'right-0'}`}
        style={{
          width: `${depthPct}%`,
          background: side === 'bid' ? 'rgba(0,177,94,0.1)' : 'rgba(232,66,66,0.1)',
        }}
      />
      <span style={{ color: side === 'bid' ? '#00b15e' : '#e84242' }}>
        {formatPrice(price)}
      </span>
      <span className="text-gray-400">{formatSize(size)}</span>
    </div>
  );
};

Производительность

Для биржи с 10–20 торговыми парами и умеренным объёмом: один Go-процесс обрабатывает > 50,000 ордеров/сек. Latency matching — микросекунды при in-memory операциях.

При необходимости масштабирования: шардинг по парам (каждая пара — независимый inстанс), горизонтальное масштабирование API-слоя с shared order book через Redis Sorted Sets (для read replicas).

База данных

Order book — только in-memory. В PostgreSQL персистируется:

• Все ордера (открытые, исполненные, отменённые)
• Все сделки (trades)
• Снэпшоты order book каждые N минут (для восстановления после рестарта)

При старте: загрузка всех status=open ордеров → восстановление in-memory книги.

Сроки разработки

• In-memory order book с FIFO matching: 3–4 недели
• WebSocket diff feed + снэпшоты: 2–3 недели
• Frontend visualizer с grouping, depth bars: 2–3 недели
• Полный компонент production-ready: 6–8 недель