암호화폐 거래소 구축을 위한 주문 매칭 알고리즘 분석 #1

개요

암호화폐 거래소를 구축하기 위해 주문(호가) 매칭 알고리즘을 찾아보던 중 좋은 글이 있어 번역과 사족을 달았다.

David Veksler 라는 소프트웨어 아키택트의 글이고, 설계한 암호화페 거래소를 중국 시장에 런칭까지 했다고 한다. 

원문과 더불어 중국 시장 거래소 런칭에 관련된 글도 있으니 같이 보면 좋겠다. 

번역은 녹색으로 표현하고 사족은 검은색으로 달았다.

결론

아주 단순한 구조의 설계지만 꼼꼼히 살펴볼수록 튼튼해 보인다.

Buy/Sell 주문을 하나의 테이블에 넣기 때문에 RDB 저장소를 사용하여도 괜찮은 IO를 보장할 것같다. (사실 IO 성능이 아닌 확장성 문제 때문이긴 하지만 하나의 마스터DB와 슬레이브들로 어느정도 서비스 가능한 TPS를 보장해 줄 수 있을듯)

아래에 사족을 달았듯이 Order 의 Status 검증을 주문 요청 전에 진행한다면 트래픽을 분산시켜 성능 높일 수 있을것 같다. 

테이블 구조도에서 Type 값들을 모두 정규화 했는데 반정규화해서 사용해도 무방해 보이고 (미약하나마 성능향상위해) OrderBook 과 Transaction 이 가지는 관계, 남은 거래량을 처리하는 방법이 단순하지만 명시적이라 좋은 방법이라 생각한다.

또한 매칭 모듈 시작 트리거를 고객이 주문한 시점으로만 제한하고있어서 개인적으로 모호했던 부분을 분명히 할 수 있어서 좋았다.

본문

비트코인 거래소 프로젝트 파트 2: 주문 매칭 알고리즘

요약

통화 거래소는 구매자와 판매자가 자신이 가진 통화를 서로 다른 통화 유형으로 교환 할 수 있는 시스템이다.  

본문

주문 매칭 모듈은 구매/판매 주문을 매칭하고 거래를 만들어 거래의 흐름을 기록하고 고객들의 잔고를 업데이트 한다.

트리거: 한명의 고객이 거래량과 가격을 입력하고 주문버튼(Buy 또는 Sell)을  클릭 한다.

본문에서는 액션으로 적혀있지만 트리거라고 이해하면 더 좋을것 같다. 이제부터 나오는 1~12번까지의 과정은 고객의 주문 트리거를 통해 실행된다.

1. 웹사이트는 고객의 Order를 Pending 상태로 OrderBook 이라는 테이블에 저장한다. 우선 주문을 처리하기 위해 쌓는다(filed).

그런 다음 오더 매칭 서비스는 Pending된 Order를 순차적으로 훑어본다.

[public int PlaceBuyBid(int customerId, decimal quantityOfBTC, decimal pricePerBTC, DateTime ?expirationDate = null) ,

public int PlaceSellOffer(int customerId, decimal quantityOfBTC, decimal pricePerBTC, DateTime ?expirationDate = null)]

2. 이 때 주문이 취소되었거나 만료되었는지를 확인하여 Order의 상태를 재검증 한다.

3. order 마다 자금 검증을 하고, 고객은 order 가 필요로 하는 자금을 가지고 있어야만 해당 order의 상태룰 active로 변경한다.

그렇지 않을 경우엔 suspended 되는데 고객이 이후에 자금을 입금하면 다시 활성화 한다.

검증을 통과하면 

a: order 의 상태가 Active로 변경된다.

b: 비용 지불이 필요한 order면(sell order를 뜻하는 듯) Frozen Balance를 더한다. (고객이  자신이 가진 자산보다 더 많은 주문생성을 못하게 하기 위함) - 하지만 이 기능은 나중에 제거했다 - 우리는 Available balance보다 더 많은 주문 생성을 가능하게 했고 거래 전에 검증하는 쪽으로 방향을 바꾸었다. 

Order suspended 는 그냥 pending 상태로 둔다는 말 같다. 앞서 말한 트리거가 발동할때마다 잔고를 확인해서 pending 또는 active로 처리한다. 잔고 확인하는 부분이 특이한데, 잔고 확인없이 주문을 생성해줄 경우 고객입장에서 주문생성을 빠르게 진행할 수 있지만 어뷰징이 걱정되고, 그냥 주문 요청시 잔고 체크하여 걸러 내는게 더 좋을것 같다. David는 이걸로도 부족했는지 order 검증시에도 잔액 검증을 빼고 거래 시점에 검증하는 쪽으로 바꿨다고한다.

4. 주문 매칭 시스템은 buy와 sell order 를 매칭하기 위해 동작한다. 주문을 매칭하기위해 모든 Acitve 상태인 Order의 가격을 검색한다.

* 만약 트리거 주문이 buy 이면 가격이 작거나 같은 주문을 찾는다.

* sell 이면 가격이 크거나 같은 주문을 찾는다.

* 시장가의 sell 이면 가장 비싼 주문을, buy 만 가장 싼 주문을 찾는다.

Order 인입시 검증을 해서 바로 Active 상태로 들여온 다음 1, 2, 3 과정을 생략하고 바로 4번으로 하는건 어떨까?

pending -> active 대신 active -> pending 으로 상태변경 과정을 바꾸고 외부 배치 작업으로 order 의 pending -> active, expired 작 업을 진행하는것도 좋을것 같다. 

우리는 buy order를 위해서 오름차순으로 매칭하고 sell order를 위해서 내림차순으로 매칭한다. 그럼 다음 가격이 매칭되면 시간순으로 정렬한다.

[ISpecification IsMatchingOrderQuery(decimal price, int orderTypeId, int wantAssetTypeId,int offerAssetTypeId, bool? isMarketOrder)]

5. 우리는 상위 3개의 매치들을 메모리로 불러온다. 3개까지 가져오는 이유는 매칭된 주문들이 추후 검증에서 실패할 수 있기 때문이다.

메모리로 불러온다는 말은 단순히 DB에서 시스템상으로 SELECT 해온다는 말 같다.

6. 우리는 order 와 match를 비교한다. 이것은 C#은 이용한 이중 검증이다. - Order가 이전 데이터베이스 쿼리 결과와 일치해야한다.

order는 다음 조건은 만족해야한다. ($/BTC, order types[buy/sell], non-two market orders, matching prices)  

     [OrderComparisonResult CompareOrders(Order firstOrder, Order secondOrder)]

쿼리로 매칭하는 주문들을 불러왔지만 시스템 상에서 다시 한번 검증한다는 말인듯.

7. 만약 order 비교가 성공하면 매칭됨을 기록(record)하는 transaction 을 만든다.

 [Transaction GetTransactionForTwoOrders(OrderComparisonResult comparisonResult)]

      * A_Order 는 buy order 

* B_Order 는 sell order

(A와 B를 사용하는 이유는 아직 어떤 주문이 Buy/Sell 이 될지 확실하지 않기 때문이다.)

Buy/Sell 두개의 오더를 가지는 하나의 Transaction 생성

Transaction 에 들어간 Order Status도 변경하는게 좋지 않을까?

8. 만약 주문간에 주문량이 정확히 일치하지 않으면 주문량이 남은 쪽 주문을 쪼개서 새로운 주문을 생성한다.

9.  [ActivateTakeProfitAndStopLossOrders(Order order)]  를 실행한다. 

TODO - 여기서 바로 시작하는게 아니라 스케쥴링한다. 자세한 내용은 다른 포스트 참고

무슨내용인지 궁금한데 연결된 포스트가 없다 ㅠㅠ

10. 주문이 매칭된 거래 (Transaction)을 처리하고 결과를 기록(record)한다.  

[public Order ProcessTransaction(Transaction transaction)] (note: this module is a database transaction)

a: 거래와 쪼개진 주문을 DB에 추가한다.

b: 거래에 포함된 두 주문 모두에게 

* 인출 금액을 차감한다. (고객의 달러나 BTC 계좌에서)

* 신용자산을 더한다. (고객의 달러나 BTC 계좌에서))

* 수수료 계좌에 수수료를 기록(record)한다.

* 동결 자산을 녹인다.

* 변경점들을 저장한다.

11. 쪼개진 주문의 남은 거래량이 0이 될때까지 대상으로 과정을 반복하거나, 매칭되는 주문이 없을때까지 반복 한 뒤 해당 주문을 active 상태로 유지한다.

foreach (OrderProcessResultModel n in ProcessOrder(splitOrder.OrderId)){
    yield return n;
}

거래량이 남았을경우 처리가 궁금했는데 단순하게 푼것 같다.

필요한 거래량만큼 여러 주문을 불러와서 트랜잭션 진행하는것보다 직관적인 방법이지만

시간 복잡도 N이 추가된다. 안정성이 중요하다면 이정도는 감수하는것도 좋을듯..

12. 만약 남은 거개량이 0이되면 status를 Completed 로 변경한다.