어쩌다, 블로그

개요

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

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 로 변경한다.

Java로 몇년간 서버개발을 하고, 안드로이드 개발을 최근에 시작했다.

그래도 자바 개발자인데 GC에 대해서 확실하게 설명할 수 있어야지! 하는 생각에 Java GC를 요약해본다.

요약을 위한 포스트임으로 자세한 내용은 아래 참고를 확인 바란다.

자바의 신 이상민님이 NAVER D2에 올리신 글과 '자바 고양이 Tomcat 이야기' 도서를 참고했다.

Garbage Collection

GC는 Garbage Collection의 약자다. (Garbage Collector 아님ㅋ) Java는 Garbage Collector가 메모리 관리(Garbage Collection)를 자동으로 해주기 때문에 메모리 해제를 위한 별도의 코드가 필요없다. (Java 1.2부터 GC에 관여할 수 있는 클래스가 추가 됨) 하지만 GC에 대한 고민없이 Garbage Collector만 믿고 규모있는 어플리케이션을 서비스하면 어김없이 장애가 발생한다. 왜일까?

STW (Stop-The-World)

Full GC가 발생하면 JVM은 어플리캐이션 실행을 멈추고 GC를 실행하는 쓰레드만 작동한다. 만약 웹서버에서 Full GC가 발생하면 서비스는 중단될 것이고 서비스가 중단 된 동안 각종 Time Out이 발생할 것이고 미뤄진 작업들이 누적되어 또 다른 Full GC를 발생시켜 장시간 장애가 발생 할 수 있다.

메모리 공간(heap)을 늘리면 Full GC를 피할 수 있을까? 메모리공간을 늘리면 Full GC의 첫 수행 시점은 늦출 수 있겠다. 하지만 STW의 시간은 heap 크기에 비례하기 때문에 메모리 공간이 클수록 더 많은 시간과 노력이 필요하다. 때문에 Heap을 많이 할당하는 것이 반드시 좋은 것만은 아니다.

어떤 GC알고리즘을 사용하더라도 Full GC와 STW는 발생한다. Full GC를 어떻게 제거할 것인가!? 하는 질문 보다 Full GC는 왜 발생하는가? 그리고 어떻게 피할것인가? 어떻게 최소화 할 것인가? 라는 질문에 초점을 맞춰 보자.

Garbage Collector

Garbage Colletor는 두 가지 일을 한다.

• 힙(heap)내의 객체 중에서 garbage를 찾아낸다.
• 찾아낸 garbage를 처리해서 heap의 메모리를 회수한다.

그리고 두 가지의 전제조건 아래에서 만들어졌다.

• 대부분의 객체는 금방 접근 불가능 상태(unreachable)가 된다.
• 오래된 객체에서 젊은 객체로의 참조는 아주 적게 존재한다.

이러한 전제조건 아래에서 garbage를 처리하기 위해 HotSpot Vm)에서는 2개의 물리적 공간을 만들었다.

• Young Generation 영역 : 새롭게 생성한 객체의 대부분이 이곳에 위치. 대부분의 객체가 금방 접근 불가능 상태가 되기 때문에 대부분의 객체가 Young 영역에 생성되었다가 사라진다. 이 영역에서 객체가 사라질 때 Minor GC가 발생했다고 말한다.
• Old Generation 영역 : Minor GC이후에도 Young 역역에서 사라남은 객체가 여기로 복사 된다. 대부분 Young 영역보다 크게 할당하며, 크기가 큰 만큼 Young 영역보다 GC는 적게 발생한다. 이 영역에서 객체가 사라질 때 Major GC(혹은 Full GC)가 발생한다고 말한다.

Heap Area 구조 : https://www.journaldev.com/2856/java-jvm-memory-model-memory-management-in-java

위 그림에는 Perm(Permanent Generation) 영역이 추가로 보이는데 이곳은 클래스 로더에 의해 로드되는 클래스, 메소드 등에 대한 메타정보가 저장되는 영역으로 어플리케이션이 아닌 JVM에 의해 사용된다. 리플렉션을 사용하여 동적으로 클래스가 로딩되는 경우에 사용되기도한다.

Young Generation 영역의 구성

위 그림을 보면 Young 영역은 Eden과 S0, S1영역으로 나누어져 있다. S는 Survivor를 뜻한다.

Young 영역에서 객체 처리절차는 이상민님의 글을 그대로 인용하겠다.

• 새로 생성한 대부분의 객체는 Eden 영역에 위치한다.
• Eden 영역에서 GC가 한 번 발생한 후 살아남은 객체는 Survivor 영역 중 하나로 이동된다.
• Eden 영역에서 GC가 발생하면 이미 살아남은 객체가 존재하는 Survivor 영역으로 객체가 계속 쌓인다.
• 하나의 Survivor 영역이 가득 차게 되면 그 중에서 살아남은 객체를 다른 Survivor 영역으로 이동한다. 그리고 가득 찬 Survivor 영역은 아무 데이터도 없는 상태로 된다.
• 이 과정을 반복하다가 계속해서 살아남아 있는 객체는 Old 영역으로 이동하게 된다.

이 절차를 확인해 보면 알겠지만 Survivor 영역 중 하나는 반드시 비어 있는 상태로 남아 있어야 한다. 만약 두 Survivor 영역에 모두 데이터가 존재하거나, 두 영역 모두 사용량이 0이라면 여러분의 시스템은 정상적인 상황이 아니라고 생각하면 된다.

이렇게 Minor GC를 통해서 Old 영역까지 데이터가 쌓인 것을 간단히 나타내면 다음과 같다.

Old Generation의 GC

Old 영역은 기본적으로 할당 된 메모리에 데이터가 가득 차면 GC를 실행한다. 기본적으로 Young와 Old 영역크기는 1:2의 비율을 가지기 때문에 Old Generation의 GC가 더 많은 시간을 소요한다.

JDK버전이 올라가면서 GC를 위한 방식들이 추가되었다. GC의 방식은 Young 영역과 Old 역역 모두에 영향을 미치며 JDK7 기준으로 5가지 방식이 있다. (최근 JDK 8은 G1GC 방식을 Default로 한다.)

5가지의 GC에 대한 설명도 이상민님의 글을 그대로 인용하겠다.
다만 해당 이상민님의 글은 2011년에 작성되어서 G1GC방식의 안정성에 대해 걱정하고 있지만, 지금은 G1GC 안정화 과정을 마치고 대부분의 서비스에서 채택하고있다.

Old 영역은 기본적으로 데이터가 가득 차면 GC를 실행한다. GC 방식에 따라서 처리 절차가 달라지므로, 어떤 GC 방식이 있는지 살펴보면 이해가 쉬울 것이다. GC 방식은 JDK 7을 기준으로 5가지 방식이 있다.

• Serial GC
• Parallel GC
• Parallel Old GC(Parallel Compacting GC)
• Concurrent Mark & Sweep GC(이하 CMS)
• G1(Garbage First) GC

이 중에서 운영 서버에서 절대 사용하면 안 되는 방식이 Serial GC다. Serial GC는 데스크톱의 CPU 코어가 하나만 있을 때 사용하기 위해서 만든 방식이다. Serial GC를 사용하면 애플리케이션의 성능이 많이 떨어진다.

그럼 각 GC 방식에 대해서 살펴보자.

Serial GC (-XX:+UseSerialGC)

Young 영역에서의 GC는 앞 절에서 설명한 방식을 사용한다. Old 영역의 GC는 mark-sweep-compact이라는 알고리즘을 사용한다. 이 알고리즘의 첫 단계는 Old 영역에 살아 있는 객체를 식별(Mark)하는 것이다. 그 다음에는 힙(heap)의 앞 부분부터 확인하여 살아 있는 것만 남긴다(Sweep). 마지막 단계에서는 각 객체들이 연속되게 쌓이도록 힙의 가장 앞 부분부터 채워서 객체가 존재하는 부분과 객체가 없는 부분으로 나눈다(Compaction).

Serial GC는 적은 메모리와 CPU 코어 개수가 적을 때 적합한 방식이다.

Parallel GC (-XX:+UseParallelGC)

Parallel GC는 Serial GC와 기본적인 알고리즘은 같지다. 그러나 Serial GC는 GC를 처리하는 스레드가 하나인 것에 비해, Parallel GC는 GC를 처리하는 쓰레드가 여러 개이다. 그렇기 때문에 Serial GC보다 빠른게 객체를 처리할 수 있다. Parallel GC는 메모리가 충분하고 코어의 개수가 많을 때 유리하다. Parallel GC는 Throughput GC라고도 부른다.

다음 그림은 Serial GC와 Parallel GC의 스레드를 비교한 그림이다.

그림 4 Serial GC와 Parallel GC의 차이 (이미지 출처: "Java Performance", p. 86)

Parallel Old GC(-XX:+UseParallelOldGC)

Parallel Old GC는 JDK 5 update 6부터 제공한 GC 방식이다. 앞서 설명한 Parallel GC와 비교하여 Old 영역의 GC 알고리즘만 다르다. 이 방식은 Mark-Summary-Compaction 단계를 거친다. Summary 단계는 앞서 GC를 수행한 영역에 대해서 별도로 살아 있는 객체를 식별한다는 점에서 Mark-Sweep-Compaction 알고리즘의 Sweep 단계와 다르며, 약간 더 복잡한 단계를 거친다.

CMS GC (-XX:+UseConcMarkSweepGC)

다음 그림은 Serial GC와 CMS GC의 절차를 비교한 그림이다. 그림에서 보듯이 CMS GC는 지금까지 설명한 GC 방식보다 더 복잡하다.

그림 5 Serial GC와 CMS GC(이미지 출처)

초기 Initial Mark 단계에서는 클래스 로더에서 가장 가까운 객체 중 살아 있는 객체만 찾는 것으로 끝낸다. 따라서, 멈추는 시간은 매우 짧다. 그리고 Concurrent Mark 단계에서는 방금 살아있다고 확인한 객체에서 참조하고 있는 객체들을 따라가면서 확인한다. 이 단계의 특징은 다른 스레드가 실행 중인 상태에서 동시에 진행된다는 것이다.

그 다음 Remark 단계에서는 Concurrent Mark 단계에서 새로 추가되거나 참조가 끊긴 객체를 확인한다. 마지막으로 Concurrent Sweep 단계에서는 쓰레기를 정리하는 작업을 실행한다. 이 작업도 다른 스레드가 실행되고 있는 상황에서 진행한다.

이러한 단계로 진행되는 GC 방식이기 때문에 stop-the-world 시간이 매우 짧다. 모든 애플리케이션의 응답 속도가 매우 중요할 때 CMS GC를 사용하며, Low Latency GC라고도 부른다.

그런데 CMS GC는 stop-the-world 시간이 짧다는 장점에 반해 다음과 같은 단점이 존재한다.

• 다른 GC 방식보다 메모리와 CPU를 더 많이 사용한다.
• Compaction 단계가 기본적으로 제공되지 않는다.

따라서, CMS GC를 사용할 때에는 신중히 검토한 후에 사용해야 한다. 그리고 조각난 메모리가 많아 Compaction 작업을 실행하면 다른 GC 방식의 stop-the-world 시간보다 stop-the-world 시간이 더 길기 때문에 Compaction 작업이 얼마나 자주, 오랫동안 수행되는지 확인해야 한다.

G1 GC

마지막으로 G1(Garbage First) GC에 대해서 알아보자. G1 GC를 이해하려면 지금까지의 Young 영역과 Old 영역에 대해서는 잊는 것이 좋다.

다음 그림에서 보다시피, G1 GC는 바둑판의 각 영역에 객체를 할당하고 GC를 실행한다. 그러다가, 해당 영역이 꽉 차면 다른 영역에서 객체를 할당하고 GC를 실행한다. 즉, 지금까지 설명한 Young의 세가지 영역에서 데이터가 Old 영역으로 이동하는 단계가 사라진 GC 방식이라고 이해하면 된다. G1 GC는 장기적으로 말도 많고 탈도 많은 CMS GC를 대체하기 위해서 만들어 졌다.

그림 6 G1 GC의 레이아웃(이미지 출처: "The Garbage-First Garbage Collector" (TS-5419), JavaOne 2008, p. 19)

G1 GC의 가장 큰 장점은 성능이다. 지금까지 설명한 어떤 GC 방식보다도 빠르다. 하지만, JDK 6에서는 G1 GC를 early access라고 부르며 그냥 시험삼아 사용할 수만 있도록 한다. 그리고 JDK 7에서 정식으로 G1 GC를 포함하여 제공한다.

그러나 JDK 7을 실서비스에서 사용하려면 많은 검증 기간(1년은 필요하다는 생각이다)을 거쳐야 할 것으로 보이기 때문에, G1 GC를 당장 사용하고 싶어도 더 기다리는 것이 좋다는 것이 개인적인 생각이다. JDK 6에서 G1 GC를 적용했다가 JVM Crash가 발생했다는 말도 몇 번 들었기에 더더욱 안정화될 때까지 기다리는 것이 좋겠다.

GC 방식 보충

Parallel GC

이름처럼 여러 Thread를 동원해 GC를 처리한다. 정확히 말하면 Young Generation의 GC를 병렬 처리하는 것이며 Parallel Copy 알고리즘을 사용한다. Old Generation은 Serial GC와 같은 Mark-compact 알고리즘을 사용한다. 자바 1.5부터 Parallel Old GC가 소개 됐고, Old Generation도 병렬처리 하게 되었다.

CMS GC

Low Latency GC 혹은 Low Pause GC라고도 부른다. Old Generation GC시 발생하는 STW 시간을 최소화 하는는게 목적이어서 Old Generation 의 GC 알고리즘만 차이가 있다. Young Generation은 Serial GC나 Parallel GC와 같다.

GC를 줄이기 위한 JVM 튜닝

http://d2.naver.com/helloworld/37111 이곳 만한곳이 없다. 하하하!

정리/요약으로 JVM 튜닝작업을 내것으로 만들기는 어려울 것 같다.

GC에 대하여 요약한 내용을 바탕으로 서비스를 해보고 직접 헤딩해보는게 최선일 듯! 

헤딩하게 되면 그 내용을 추가하겠다.