(OMS 5) 오더북 구성

이전 글: 오더북이 필요한 이유

이 글은 매매 시스템 시리즈의 글입니다.

이전 글에서 오더북이 왜 필요한지 살펴봤습니다. 이번 글에서는 효율적으로 동작하는 오더북을 작성해 보겠습니다. 실무에서는 사용자에 따라 훨씬 더 많은 요소가 추가되지만, 이 글에서는 핵심적인 부분만 다루겠습니다.

---

용어 정리

먼저 이 글에서 사용하는 용어를 정리하겠습니다.

• Level: 한 가격에 걸린 주문들의 나열
• Ladder: 한 방향(매수 또는 매도)의 Level들을 모은 것
• Orderbook: 매수 Ladder와 매도 Ladder를 합친 것

---

자료구조 선택

use ahash::AHashMap;
use std::collections::{BTreeMap, VecDeque};

type OrderId = u64;
type BookPrice = i64;
type BookQuantity = i64;

/// 한 가격의 주문 큐
struct Level {
    price: BookPrice,
    orders: VecDeque<(OrderId, BookQuantity)>,
    total_quantity: BookQuantity,
}

/// 한 방향(매수 또는 매도)의 가격 레벨들
struct Ladder {
    levels: BTreeMap<BookPrice, Level>,
    cache: AHashMap<OrderId, BookPrice>,
}

/// 매수 + 매도
struct Orderbook {
    bids: Ladder,
    asks: Ladder,
}

왜 이런 자료구조를 선택했는지 하나씩 살펴보겠습니다.

---

AHashMap

cache에 사용한 AHashMap은 Rust 표준 라이브러리의 HashMap보다 빠른 해시맵입니다. 표준 HashMap은 HashDoS 공격 방어를 위해 SipHash를 사용하는데, 이 해싱 자체가 느립니다. AHashMap은 비암호학적 해시 함수를 사용해서 해시 연산이 대략 2~5배 빠릅니다.

Rust의 표준 라이브러리는 의도적으로 최소한의 기능만 포함합니다. 비동기 런타임도, JSON 파서도, HTTP 클라이언트도 없습니다. HashMap 역시 안전성에 중점을 둔 범용 구현이라, 성능이 중요한 상황에서는 더 나은 대체제가 있는지 항상 확인해 봐야 합니다.

---

cache: 주문 ID → 가격

cache: AHashMap<OrderId, BookPrice>

이 변수가 없으면 주문 ID로 주문을 찾을 때 모든 가격 레벨을 순회해야 합니다. 주문 취소나 수정 요청이 들어오면 해당 주문이 어느 가격에 있는지 바로 알아야 하는데, 가격 레벨을 전부 순회하면 느립니다. cache가 있으면 O(1)에 가격을 찾고, 그 가격의 Level에서 바로 처리할 수 있습니다.

---

Ladder: BTreeMap

levels: BTreeMap<BookPrice, Level>

가격 레벨은 정렬되어 있어야 합니다. best price 갱신이 빈번하게 일어나고, 대량 주문이 여러 가격을 뜯어갈 때 최우선 호가부터 차례대로 체결됩니다. 정렬되어 있지 않으면 매번 best price를 찾기 위해 전체를 탐색해야 하고, 이 비용이 누적되면 성능상 큰 손실이 발생합니다.

BTreeMap은 키를 정렬된 상태로 유지하므로, 최솟값이나 최댓값을 O(log n)에 가져올 수 있습니다.

---

Level: VecDeque

orders: VecDeque<(OrderId, BookQuantity)>

주문의 체결은 앞에서 일어나고, 주문의 추가는 뒤에서 일어납니다. 전형적인 FIFO 큐이므로 양방향 큐인 VecDeque가 자연스럽습니다.

그런데 취소는 어떨까요? 통계적으로 취소의 80~90%는 큐 뒤쪽에서 발생하지만, 정확한 위치를 알기는 어렵습니다. 저는 비율 하나를 고정해서 사용합니다. 앞쪽과 뒤쪽을 대략 1:3 정도의 비율로 설정하고 탐색합니다.

---

관련 글

• 오더북이 필요한 이유: 오더북의 용도
• 중요한 숫자 관리는 정수로: 가격을 정수로 관리하는 이유