13장. 증권 거래소

 

거래소의 기본 기능은 구매자와 판매자가 효율적으로 연결될 수 있도록 돕는 것이다.

 

1단계: 설계 범위

1. 비기능 요구사항

• 가용성: 최소 99.99%, 거래소의 가용성은 매우 중요한 문제. 단 몇 초의 장애로도 평판이 손상될 수 있다.
• 결함 내성: 프로덕션 장애의 파급을 줄이려면 결함 내성과 빠른 복구 메커니즘이 필요하다.
• 지연 시간: 왕복 지연 시간은 밀리초 수준이어야 하며, 특히 p99 지연 시간이 중요하다. 왕복 지연 시간은 주문이 거래소에 들어오는 순간부터 주문의 체결 사신이 반환되는 시점까지다.
• 보안: 거래소는 계정 관리 시스템을 갖추어야 한다. 법률 및 규정 준수를 위해 거래소는 새 계좌 개설 저에 사용자 신원 확인을 위한 KYC 확인을 수행한다.

2. 개략적 규모 추정

• 100가지 주식
• 하루 10억 건의 주문
• 뉴욕증권거래소는 월요일부터 금요일까지, 오전 9시 30분부터 오후 4시까지 영업한다. 총 6.5시간
• QPS: 약 43,000
• 최대 QPS: 215,000. 거래량은 장 시작 직후, 그리고 장 마감 직전에 훨씬 높다.

---

2단계: 개략적 설계

1. 증권 거래 101

1.1 브로커

• 대부분의 개인 고객은 브로커 시스템을 통해 거래소와 거래한다.
• 브로커 시스템은 개인 사용자가 증권을 거래하고 시장데이터를 확인할 수 있도록 편리한 사용자 인터페이스를 제공한다.

1.2 기관 고객

• 기관 고객은 전문 증권 거래 소프트웨어를 사용하여 대량으로 거래한다.
• 이들은 아주 낮은 응답 시간으로 거래하길 원한다.
• 일반 사용자들처럼 웹페이지나 모바일 앱에서 시장 데이터를 확인하게 하면 곤란하다.

1.3 지정가 주문

• 가격이 고정된 매수 또는 매도 주문이다.
• 시장가 주문과는 달리 체결이 즉시 이루어지지 않을 수 있고, 부분적으로만 체결될 수도 있다.

1.4 시장가 주문

• 가격을 지정하지 않은 주문으로, 시장가로 즉시 체결된다.
• 체결은 보장되나 비용 면에서는 손해를 볼 수 있다.
• 급변하는 특정 시장 상황에서 유용하다.

1.5 시장 데이터 수준

• 미국 주식시장에서는 L1, L2, L3의 세 가지 가격 정보 등급이 있다.
• L1은 시장 데이터에는 최고 매수호가, 매도 호가 및 수량이 포함된다.
  • 최고 매수호가는 구매자가 주식에 집루할 의사가 있는 최고 가격이다.
  • 매도 호가는 매도자가 주식을 팔고자 하는 최저 가겨이다.
• L2는 체겨을 기다리는 물량의 호가를 어디까지 보여주는지 나타낸다.
• L3는 L2에서 한 걸음 더 나아가, 각 주문 가격에 체결을 기다리는 물량 정보까지 보여준다.

1.6 봉 차트

• 특정 기간 동안의 주가다.
• 하나의 봉 막대로 일정 시간 간격 동안 시장의 시작가, 종가, 최고가, 최저가를 표시할 수 있다

1.7 FIX

• 금융 정보 교환 프로토콜(Financial Information Exchange Protocol) 의 약어로, 증권 거래 정보 교환을 위한 기업 중립적 통신 프로토콜이다.

2단계: 개략적 설계안

 

거래 흐름을 통해 하나의 주문이 어떤 절차로 처리되는지 살펴본다.

 

1단계: 고객이 브로커의 웹 또는 모바일 앱을 통해 주문한다.

 

2단계: 브로커가 주문을 거래소에 전송한다.

 

3단계: 주문이 클라이언트 게이트웨이를 통해 거래소로 들어간다.
클라이언트 게이트웨이는 입력 유효성 검사, 속도 제한, 인증, 정규화 등과 같은 기본적인 게이트 키핑 기능을 수행한다.

 

4~5단계: 주문 관리자 위험 관리자가 설정한 규칙에 따라 위험성 점검을 수행한다.

 

6단계: 위험성 점검 과정을 통과한 주문에 대해, 주문 관리자는 지갑에 주문 처리 자금이 충분한지 확인한다.

 

7~9단계: 주문이 체결 엔진으로 전송된다. 체결 가능 주문이 발견되면 체결 엔진은 매수 측과 매도 측에 각각 하나씩 두 개의 집행 기록을 생성한다. 나중에 그 과정을 재생할 대 항상 결정론적으로 동일한 결과가 나오도록 보장하기 위해 시퀀서는 주문 및 집행 기록을 일정 순서로 정렬한다.

 

10~14단계: 주문 집행 사실을 클라이언트에 전송한다.

 

 

시장 데이터 흐름을 따라서, 하나의 주문이 체결 엔진부터 데이터 서비스를 거쳐 브로커로 전달되어 집행되기까지의 과정을 추적한다.

 

M1 단계: 체결 엔진은 주문이 체결되면 집행 기록 스트림을 만든다. 이 스트림은 시장 데이터 게시 서비스로 전송된다.

 

M2 단계: 시장 데이터 게시 서비스는 집행 기록 및 주문 스트림에서 얻은 데이터를 시장 데이터로 사용하여 봉 차트와 호가 창을 구성한다. 그런 다음 시장 데이터를 데이터 서비스로 보낸다.

 

M3 단계; 시장 데이터는 실시간 분석 전용 스토리지에 저장된다. 브로커는 데이터 서비스를 통해 실시간 시장 데이터를 읽는다. 브로커는 이 시장 데이터를 고객에게 전달한다.

 

보고흐름을 살펴본다.

 

R1~R2 단계: 보고 서비스는 주문 및 실행 기록에서 보고에 필요한 모든 필드의 값을 모은 다음 그 값을 종합해 만든 레코드를 데이터베이스에 기록한다.

3. 거래 흐름

3.1 체결 엔진

체결 엔진의 주요 역할

1. 각 주식 심벌에 대한 주문서 내지 호가 창을 유지 관리한다. 주문서 또는 호가창은 특정 주식에 대한 매수 및 매도 주문 목록이다.
2. 매수 줌누과 매도 주문을 연결한다. 주문 체결 결과로 두 개의 집행 기록이 만들어진다. 체결은 빠르고 신속하게 처리되어야 한다.
3. 집행 기록 스트림을 시장 데이터로 배포한다.

가용성 높은 체결 엔진 구현체가 만드는 체결 순서는 결정론적이어야 한다.

입력으로 주어지는 주문 순서가 같으면 체결 엔진이 만드는 집행 기록 순서도 언제나 동일해야 한다.

 

3.2 시퀀서

시퀀서는 체결 엔진을 결정론적으로 만드는 핵심 구성 요소다.

• 시퀀서는 체결 엔진에 주문을 전달하기 전에 순서 ID를 붙여 보낸다.
• 체결 엔진이 끝낸 모든 집행 기록 쌍에도 순서 ID를 붙인다.
• 시퀀서에는 입력 시퀀서와 출력 시퀀서 두 가지가 있으며, 각각 고유한 순서를 유지한다.

 

 

입력 되는 주문과 출력하는 실행 명령에 순서 ID를 찍은 이유는 아래와 같다.

1. 시의성 및 공성정
2. 빠른 복구 및 재생
3. 정확한 1회 실행 보증

시퀀서는 메세지 큐 역할도 한다.

• 하나는 체결 엔진에 메세지를 보내는 큐 역할을 한다.
• 다른 하나는 주문관리자에게 메세지를 회신하는 큐 역할을 한다.
• 주문과 집행 기록을 위한 이벤트 저장소로도  볼수도 있다.

 

두 개 카프카 이벤트 스트림과 연결되어 있는 것과 비슷하다.

만약 카프카의 지연 시간이 더짧고 예측 간으했다면 사용했을 수도 있다.

 

3.3 주문 관리자

주문 관리자는 한쪽에서는 주문을 받고 다른 한쪽에서는 집행 기록을 받는다.

주문 상태를 관리하는 것이 주문관리자의 역할이다.

 

주문 관리자는 클라이언트 게이트웨이를 통해 주문을 수신하고 다음을 실행한다.

• 종합적 위험 점검 담당 컴포넌트에 주문을 보내어 위험성을 검토한다.
• 사용자의 지갑에 거래를 처리하기에 충분한 자금이 있는지 확인한다.
• 주문을 시퀀서에 전달한다.

또한, 주문 관리자는 시퀀서를 통해 체결 엔진으로부터 집행 기록을 받는다.

• 체결된 주문에 대한 집행 기록을 클라이언트 게이트웨이를 통해 브로커에 반환한다.

3.4 클라이언트 게이트웨이

 

클라이언트 게이트웨이는 거래소의 문지기이다.

• 중요 경로상에 놓이며, 지연 시간에 민감하다.
• 가벼워야 하며 가능한 빨리 올바른 목적지로 주문을 전달해야 한다.
• 일반적으로 복잡한 기능이라면 체결 엔진이나 위험 점검 컴포넌트에 맡겨야 한다.

고객 유형별로 클라이언트 게이트웨이는 다양하다.

• 주요 고려 사항은 지연 시간, 거래량, 보안 요구사항이다.
• 예를들어 시장 조성자 같은 기관은 거래소에 유동성의 상당 부분을 공급하는데, 매우 낮은 지연시간을 요구한다.

3.5 시장 데이터 흐름

• 시장 데이터 게시 서비스는 체결 엔진에서 집행 기록을 수신하고 집행 기록 스트림에서 호가 창과 봉 차트를 만들어 낸다.
• 시장 데이터는 데이터 서비스로 전송되어 해당 서비스의 구독자가 사용할 수 있게 된다.

3.6 보고 흐름

• 거래소에 필수적인 부분 가운데 하나는 보고다.
• 보고 서비스는 거래 이력, 세금 보고, 규정 준수 여부 보고, 결산 등의 기능을 제공한다.
• 정확성과 규정 준수가 핵심이다.

4. API 설계

브로커와 클라이언트 게이트웨이 간의 인터페이스 명세 작성에는 RESTful 컨벤션을 사용한다.

헤지 펀트와 같은 기관 고객의 지연 시간 요구사항을 충족하지 못한다.

이러한 기관에 공급되는 특수 소프트웨어는 다른 프로토콜을 사용할 가능성이 있다.

 

4.1 주문

주문을 처리한다. 인증이 필요

• POST /v1/order
• 인자
  • symbol: 주식을 나타내는 심벌
  • side: buy(매수) 또는 sell(매도)
  • price: 지정가 주문의 가격
  • orderType: limit(지정가) 또는 market(시장가).
  • quantity: 주문 수량
• 본문(body)
  
  • id: 주문ID
  • createTime: 주문이 시스템에 생성된 시간
  • filledQuantity: 집행이 완료된 수량
  • remainingQuantity: 아직 체결되지 않은 주문 수량
  • status: new/canceled/filled

4.2 집행

집행 정보를 질의한다. 인증이 필요

• GET /v1/excution?symbol={:symbol}&orderId={:orderId}&startTime={:startTime}&endTime={:endTime}
• 인자
  • symbol: 주식 심벌
  • orderId: 주문의 ID
  • startTime: 질의 시작 시간
  • endTime: 질의 종료 시간
• 본문(body)
  • executions: 범위 내 모든 집행 기록의 배열
  • id: 집행 기록 ID
  • orderId: 주문 ID
  • symbol: 주식 심벌
  • side: buy(매수) 또는 sell(매도)
  • price: 체결 가격
  • orderType: limit(지정가) 또는 market(시장가)
  • quantity: 체결 수량

4.3 호가 창/주문서

주어진 주식 심벌, 주어진 깊이 값에 대한 L2 호가 창 질의 결과를 반환

• GET /v1/marketdata/orderBook/L2?symbol={:symbol}&depth={:depth}
• 인자
  • symbol: 주식 심벌
  • depth: 반환할 호가 창의 호가 깊이
  • startTime: 질의 시작 시간
  • endTime: 질의 종료 시간
• 본문
  • bids: 가격과 수량 정보를 담은 배열
  • asks: 가격과 수량 정보를 담은 배열

4.4 가격 변동 이력(봉 차트)

주어진 시간 범위, 해상도, 심벌에 대한 봉 차트 데이터 질의 결과를 반환

• GET /v1/marketdata/candles?symbol={:symbol}&resolution={:resolution}&startTime={:startTime}&endTime={:endTime}
• 인자
  • symbol: 주식 심벌
  • resolution: 봉 차트의 윈도 길이
  • startTime: 질의 시작 시간
  • endTime: 질의 종료 시간
• 본문
  • candles: 각 봉의 데이터를 담은 배열
  • open: 해당 봉의 시가
  • close: 해당 봉의 종가
  • high: 해당 봉의 고가
  • low: 해당 봉의 저가

5. 데이터 모델

증권 거래소에는 세 가지 유형의 주요 데이터가 있다.

 

5.1 상품, 주문, 집행

상품(product)은 거래 대상 주식(심벌)이 가진 소석으로 정의된다.

• 상품의 유형, 거래에 쓰이는 심벌, UI에 표시될 심벌, 결산에 이용되는 통화 단위, 매매 수량 단위, 호가 가격 단위 등이다.
• 데이터는 자주 변경되지 않는다.
• 주로 UI 표시를 위한 데이터로 아무 데이터베이스에나 저장 가능하며 캐시를 적용하기 좋다.

주문은 매수 또는 매도를 실행하라는 명령이며, 집행 기록은 체결이 이루어진 결과다.

• 집행 기록은 충족이라고 부른다.
• 체결 엔진은 하나의 주문 체결에 관여한 매수 행위와 매도 행위를 나타내는 두 개의 집행 기록을 결과로 출력한다.

주문과 집행 기록은 거래소가 취급하는 가장 중요한 ㄷ게이터이다.

• 중요 거래 경로는 주문과 집행 기록을 데이터베이스에 저장하지 않는다.
  • 메모리에서 거래를 체결하고 하드디스크나 공유 메모리를 활용하여 저장한다.
  • 빠른 복구를 위해 시퀀서에 저장하며, 장 마감 후에 보관한다.
• 보고 서비스는 조정이나 세금 보고 등을 위해 데이터베이스에 주문 및 집행 기록을 저장한다.
• 집행 기록은 시장 데이터 프로세서로 전달되어 호가 창/주문서와 봉 차트 데이터 재구성에 쓰인다.

5.2 호가 창

호가 창은 특정 증권 또는 금융 상품에 대한 매수 및 매도 주문 목록으로, 가격 수준별로 정리되어 잇다.

체결 엔진이 빠른 주문 체결을 위해 사용하는 핵심 자료 구조다.

호가 창의 자료 구조는 아래 요구사항을 만족할 수 있는 효율성이 높은 것이어야 한다.

• 일정한 조회 시간: 특정 가격 수준의 주문량 조회, 특정 가격 범위 내의 주문량 조회 등이 포함
• 빠른 추가/취소/실행 속도: 가갑적 O(1) 시간 복잡도를 만족해야 한다. 새 주문 넣기, 기존 주문 취소하기, 주문 체결하기 등이 있다.
• 빠른 업데이트: 주문 교체
• 최고 매수 호가/최저 매도 호가 질의
• 가격 수준 순회

 

호가창이 실제로 어떻게 구현되는지 보여준다.

class PriceLevel {
    private Price limitPrice;
    private long totalVolume;
    private List<Order> orders;
}

class Book<Side> {
	private Side side;
    private Map<Price, PriceLevel> listMap;
}

class OrderBook {
    private Book<Buy> buyBook;
    private Book<Sel> sellBook;
    private PriceLevel bestBid;
    private PriceLevel vestOffer;
    Private Map<ORderId, order> orderMap;
}

 

지정가 주문을 추가/취소하는 시간 복잡도가 O(1)인가?

• 일반 리스트를 사용하고 있으므로 대답은 '아니요'다.
• 보다 효율적인 호가 창을 만들려면 orders의 자료 구조는 이중 연결 리스트(doubly linked list)로 변경하여 모든 삭제 연산이 O(1)에 처리되도록 해야 한다. 

이러한 연산들이 어떻게 O(1)이 되는지 알아보자.

1. 새 주문을 넣는다는 것은 PriceLevel 리스트 마지막에 새 order를 추가하는 것을 의마한다. 이중 연결 리스트에서 이 연산은 O(1)에 처리된다.
2. 주문을 체결한다는 것은 PriceLevel 리스트의 맨 앞(head)에 있는 Order를 삭제한다는 것과 같다. 이중 연결 리스트의 경우 이 연산의 시간 복잡도는 O(1)이다.
3. 주문을 취소한다는 것은 호가 창, 즉 OrderBook에서 Order를 삭제한다는 뜻이다. OrderBook에 포함되어 있는 도움 자료 구조 Map<OrderId, Order> orerMap을 활용하면 O(1) 시간 내에 취소할 주문을 찾을 수 있다.

5.3 봉 차트

• 봉 차트는 시장 데이터 프로세서가 시장 데이터를 만들 때 호가 창과 더불어 사용하는 핵심 자료 구조다.
• 봉차트를 모델링하기 위해서 Candlestick 클래스와 CandlestickChart 클래스를 사용한다.
• 하나의 봉이 커버하는 시간 범위가 경과하면 다음 주기를 커버할 새 Candlestick클래스 객체를 생성하여 CandlestickChart 객체 내부 연결 리스트에 추가한다.

class Candlestick {
    private long openPrice;
    private long closePrice;
    private long highPrice;
    private long lowPrice;
    private long volume;
    private long timestamp;
    private int interval;
}


class CandlestickChar {
    private LinkedList<Candlestick> sticks;
}

 

 

봉 차트에서 많은 종목의 가격 이력을 다양한 시간 간격을 사용해 추적하려면 메모리가 많이 필요하다.

어떻게 최적화할 수 있을까?

1. 미리 메모리를 할당해 둔 링 버퍼에 봉을 보관하면 새 객체 할당 횟수를 줄일 수 있다.
2. 메모리에 두는 봉의 개수를 제한하고 나머지는 디스크에 보관한다.

 

---

3단계: 상세 설계

일부 대형 거래소는 하나의 거대 서버로 거의 모든 것을 운영한다.

여기서 좋은 교훈들을 얻을 수 있다.

1. 성능

지연 시간은 거래소에 아주 중요한 문제다.

평균 지연 시간은 낮아야 하고, 전반적인 지연 시간 분포는 안정적이어야 한다.

 

지연 시간은 아래 공식과 같이 굿어 요소별로 분할할 수 있다.

 

지연 시간 = Σ 중요 경로상의 컴포넌트 실행 시간

 

지연 시간을 줄이는 방법 두 가지

1. 중요 경로에서 실행할 작업 수를 줄인다.
2. 각 작업의 소요 시간을 줄인다.
   • 네트워크 및 디스크 사용량 경감
   • 각 작업의 실행 시간 경감

 

첫 번째 방법에서 중요 매매 경로에 있는 컴포넌트는 아래와 같다.

 

게이트 웨이 → 주문 관리자 → 시퀀서 → 체결 엔진

 

중요 경로에는 꼭 필요한 구성 요소만 둔다. 로깅도 지연시간을 줄이기 위해 경로에서 뺀다.

 

두 번째 방법으로는 모든 것을 동일한 서버에 배치하여 네트워크를 통하는 구간을 없애는 것이다.

• 핵심 경로의 구성요소가 네트워크를 통해 연결된 개별 서버에서 실행된다고 가정했을 때, 왕복 지연 시간은 500마이크로초다.
• 통신하는 컴포넌트가 많으면 총 네트워크 지연 시간은 한 자리수 밀리초까지 늘어난다.
• 경쟁에 앞서 나가기 위해 거래소는 주로 네트워크 및 디스크 액세스 지연 시간을 줄이거나 없애는 방안을 통해 중요 경로의 단대단 지연 시간을 마이크로초로 줄였다.
• 같은 서버 내 컴포넌트 간 통신은 이벤트 저장소인 mmap를 통한다.

애플리케이션 루프를 살펴보면 주된 작업 실행 메커니즘은 while 순환문을 통해 실행할 작업을 계속 폴링(pooling)하는 것이다.

• 엄격한 지연 시간 요건을 만족하려면 목적 달성에 가장 중요한 작업만 이 순환문 안에서 처리해야 한다.
• 메커니즘의 목표는 각 구성 요소의 실행 시간을 줄여 전체적인 실행 시간이 예측 가능하도록 보장하는 것이다.
• 컴포넌트는 서버의 프로세스이고, CPU 효율성을 극대화하기 위해 애플리케이션 루프는 단일 스레드로 구현하며, 특정 CPU 코어에 고정시킨다.

애플리케이션 루프를 CPU에서 고정하면 이점

1. 문맥 전환, 즉 컨텍스트 스위치가 없다. CPU 1이 주문 관리자의 애플리케이션 루프 처리에 온전히 할당된다.
2. 상태를 업데이트하는 스레드가 하나뿐이라서 락을 사용할 필요가 없고 잠금 경합도 없다.

애플리케이션 루프를 CPU에서 고정하면 단점

1. 코딩이 더 복잡해진다는 것이다.
   • 엔지니어는 각 작업이 애플리케이션 루프 스레드를 너무 오래 점유하지 않도록 각 작업에 걸리는 시간을 신중하게 분석해야 한다.
     그렇지 않으면 후속 작업을 제때 실행하지 못할 수도 있다.
   •  

mmap 컴포넌트는 파일을 프로세스의 메모리에 매핑하는 mmap(2)라는 이름의 POSIX 호환 UNIX 시스템 콜(system call)을 일컫는다.

• mmap(2)는 프로세스 간 고성능 메모리 공유 메키니즘을 제공한다.
  • 메모리에 매핑할 파일이 /dev/shm에 있을 때 성능 이점은 더욱 커진다.
  • /dev/shm은 메모리 기반 파일 시스템이다.
  • /dev/shm에 위치한 파일에 mmap(2)를 수행하면 공유 메모리에 접근해도 디스크 I/O는 발생하지 않는다.
• 서버에서 mmap(2)를 사용하여 중요 경로에 놓인 구성요사가 서로 통신할 때 이용할 메세지 버스를 구현하는 것이다.
  • 해당 통신 경로를 사용하면 네트워크나 디스크에 접근하는 일은 없으며, 메세지 전송에 마이크로초 미만이 걸린다.

1.1 이벤트 소싱

2. 고가용성

 

 

3. 결함 내성