[Review] 시스템 디자인 스터디3 - 7주차 후기 (完) - 증권 거래소 시스템 디자인

안녕하세요!
K-DEVCON (이하 “데브콘”) 그로스 매니저 박종훈입니다.

7회차의 스터디를 마지막으로 시스템 디자인 스터디 3기를 마치게 되었습니다.
다음 스터디와 관련된 모집글도 조만간에 공지드려볼 수 있도록 하겠습니다.

이번 7회차 스터디에서는 “증권 거래소” 의 디자인에 대해서 함께 이야기를 나눠보았습니다.

---

매칭 엔진 (체결 엔진, matching engine)


매칭 엔진은 거래소의 핵심 역할을 합니다. 주식에 대한 주문서를 유지 관리합니다. 매수 주문과 매도 주문을 연결합니다. 연결된 두 주문은 체결로 이어집니다. 체결은 빠르고 신속하게 처리되어야 합니다.

책에 참고자료로 소개되어 있는 아래 글을 보면 어떻게 아키텍처를 잡을지 알아 볼 수 있습니다.

How to Build a Fast Limit Order Book
https://web.archive.org/web/20110219163448/http://howtohft.wordpress.com/2011/02/15/how-to-build-a-fast-limit-order-book/ 

위 방식을 사용하면 아래와 같은 시간 복잡도를 달성할 수 있습니다.

Add – O(log M) for the first order at a limit, O(1) for all others
Cancel – O(1)
Execute – O(1)
GetVolumeAtLimit – O(1)
GetBestBid/Offer – O(1)

구체적으로 어떤 방식을 사용했는지 알아보겠습니다. 대부분의 컨셉은 책에 있는것과 거의 동일하긴 합니다.

우선 아래와 같은 객체들을 활용합니다.

Order
  int idNumber;
  bool buyOrSell;
  int shares;
  int limit;
  int entryTime;
  int eventTime;
  Order *nextOrder;
  Order *prevOrder;
  Limit *parentLimit;

Limit  // representing a single limit price
  int limitPrice;
  int size;
  int totalVolume;
  Limit *parent;
  Limit *leftChild;
  Limit *rightChild;
  Order *headOrder;
  Order *tailOrder;

Book
  Limit *buyTree;
  Limit *sellTree;
  Limit *lowestSell;
  Limit *highestBuy;

매수 호가창과 매도 호가창은 따로 구성합니다.

[Review] 시스템 디자인 스터디3 - 7주차 후기 (完) - 증권 거래소 시스템 디자인


책에서는 그냥 double linked list 로 각 가격을 연결하였지만, 이럴 경우 새로운 가격을 추가하기 위해서 쓰이는 시간복잡도는 O(n) 이 됩니다. 그래서 위 소개글 에서는 Limit 객체의 limitPrice 를 기준으로 Tree 를 구성합니다. 이렇게 하면 삽입 시 속도를 O(Log N) 으로 가져갈 수 있어 “O(log M) for the first order at a limit” 라는 설명이 올바르게 동작합니다. 그 외의 처리들은 Double Linked List 와 Map 을 사용하여 O(1)으로 동작할 수 있도록 하여 빠른 속도를 달성합니다.

매칭 엔진과 관련된 이야기들을 보면서 또 재밌던 부분은 최대한 딜레이가 발생되지 않도록 하기 위해서, JVM 계열의 시스템을 쓰는 경우 GC 가 최대한 발생되지 않을 수 있도록 설계된다는 점이였습니다. (Object Pooling 사용)
찰나의 딜레이라 하더라도, 주식 거래에서는 치명적일 수 있기 때문입니다. 최근 나온 ZGC 라고 하더라도 10ms 내의 GC 를 보장한다고 하지만, 이 역시도 주식 시장에서는 큰 딜레이가 될 수 있습니다.

매칭 엔진은 하나여야할까?


또 흥미로웠던 부분은 주 체결 엔진(Matching Engine)의 구조였습니다. 대규모 트래픽 처리를 위해 수평 확장을 선택하는 일반적인 서비스와 달리, 거래소의 체결 엔진은 '순서 보장'이 최우선이기 때문에 단일 노드에서 시퀀셜하게 처리하는 구조를 가집니다. (그래서 Kafka 같은 시스템도 사용하기 어렵습니다. 순서가 깨지기 쉽거든요.)

그렇다면 확장이 안 되는 구조 아닌가? 라는 질문도 나왔습니다. 맞습니다. 하지만 주체결 엔진은 순서 보장이 생명이기 때문에, 병렬 처리보다 직렬 처리와 안정성을 선택한 케이스 입니다.

만약 이러한 구조에서 장애가 발생되면 어떻게 할까요? 이러한 문제를 방지하기 위해 스탠바이 서버를 구성하는 형태를 가져갑니다.

스터디에서 나온 질문중 하나는 다음과 같았습니다. 만약 코드의 문제로 주 서버가 다운되었다면, 부 서버로 전환해도 버그가 따라올텐데 이 문제는 어떻게 해야할까요? 이에 대한 토론 결론은 다음과 같았습니다.

부 서버는 인프라 장애를 대비하는 용도이다. 코드 레벨 장애는 그것의 책임 범위가 아니다. 코드 버그는 충분한 사전 검증으로 해결해야 한다.

매도 주문이 먼저 차감될까? 매수 주문이 먼저 차감될까?


또 재밌었던 질문 중 하나는 “매도 주문이 먼저 차감될까? 매수 주문이 먼저 차감될까?” 였습니다. 스터디 당일에는 답을 정확하게 하지 못했던 것 같은데, 누가 먼저 대기하고 있었는가를 생각해보니 답이 명확해졌습니다.
매칭엔진은 위에서 이야기 한대로 순차적으로 처리하는데 특화된 서버입니다. 따라서 양쪽 큐에 요청이 쌓여있는 경우는 존재하지 않을 것입니다. 먼저 만들어진 대기자(Maker)가 있을 것이고, 그것을 차감시키는 요청자(Taker) 가 있을 것이기 때문에, Taker의 주문건은 큐에 쌓이지 않고 바로 Maker 가 만든 수량을 차감시키게 됩니다. 즉, 매칭이 성사되면 엔진은 데이터 무결성을 위해 장부에 미리 기록되어 있던 Maker의 수량을 최우선적으로 차감하고, 그 결과에 따라 Taker의 남은 수량을 처리합니다.


네트워크 최적화


속도를 극한으로 끌어올리기 위한 인프라 전략에 대한 이야기도 인상적이었습니다. 서버를 거래소 서버와 물리적으로 가까운 곳에 두는 콜로케이션이나, 인터넷 망이 아닌 물리적인 직통 선(Direct Connect)을 연결해 네트워크 홉(Hop)을 줄이는 방식이 실제 HFT(고빈도 매매)에서 얼마나 유의미한 차이를 만드는지 공유되었습니다.


마무리


스터디에서 실제로 경험했던 이야기들을 포함하여 더 많은 이야기들을 함께 나눠보았지만, 리뷰글은 여기서 마무리 해보겠습니다.

이번장에서 나온 이야기를 마인드 맵으로 정리해보면 다음과 같습니다.


[Review] 시스템 디자인 스터디3 - 7주차 후기 (完) - 증권 거래소 시스템 디자인 - 이미지 2



우리 스터디에서는 실제 사례들을 통해 문제를 어떻게 해결해 나갔을까 많은 고민을 해보고 이야기를 나눠보고 있습니다. 이번주도 다들 열심히 참여해주셔서 더 풍성한 스터디가 될 수 있었습니다.

[Review] 시스템 디자인 스터디3 - 7주차 후기 (完) - 증권 거래소 시스템 디자인 - 이미지 3
스터디 마지막 날이라고 모든 스터디원들이 참여해주셨습니다 : )

다음 스터디는 책보다는 좀 더 실제로 설계해보면서 스터디원들이 참여할 수 있는 형태로 운영해보려고 생각중입니다.
많은 관심 부탁드립니다. 함께 머리를 맞대고 시스템의 설계를 해보고 싶은 분들의 합류를 기다립니다.


✅ 직접 스터디를 개설해보고 싶은 분이 계시다면, K-DEVCON에서 운영을  도와드리겠습니다. 데브콘의 '랩짱'에 도전하여 커뮤니티 성장을 함께 이끌어주세요!  K-DEVCON Linkedin 에 DM 부탁드리겠습니다😉