[멋쟁이사자처럼 백엔드 TIL/ 그때 살껄;;..] 거래 시스템 설계

1. 서론

프로젝트에서 가장 중요한 부분중 하나라고 생각한다. 코인 거래 관련 사이트인 만큼 코인 거래 로직은 설계 단계를 깊게 고민해 봐야 한다고 생각했다. 어떤 알고리즘을 사용해야하는지 그리고 그것의 장단점을 통해서 내가 만드는 프로그램이 단점을 보완하고 장점은 살릴수 있는지 그리고 어떤 소프트웨어를 사용해야 내가 생각한 로직을 잘 녹여낼 수 있는지 고민했다. 오늘은 그것들에 대해서 설명해보려고 한다.

2. 거래 로직 설계

내가 개발하고 있는 거래 프로그램은 이러하다

진짜 거래가 아니다.

거래소를 만드는 것이 아니라 코인의 가격이 매수 혹은 매도 가격 닿으면 바로 채결이 된다.
즉 구매자가 진짜 판매자 한테 사는것도 아니고 판매자가 진짜 구매자한테 파는 것도 아니다.

구매와 판매를 연결해줄 필요가 없다.

이는 거래소를 만드는 것이 아닌 코인 거래를 하는 연습 및 게임 사이트를 만드는 것에 초점을 더 둔 결과이다.

이를 통해 생각 한 큰틀의 설계는 이러하다.

간단한 단어 설명을 하고 가려한다.

• 주문 : 거래 가격을 생성한다. 어느 가격에 살지 어느 가격에 팔지 정한다.
• 체결 : 주문이 성공적으로 이루어져 구매 혹은 판매가 이루어지는 시점이다.
• 매수 : 구매를 뜻한다.
• 매도 : 판매를 뜻한다.

1. 코인의 종류는 여러가지가 있다.
2. 각 코인은 상장될수 있고 폐지될수 있다.
3. 각 코인은 실시간으로 가격이 변화한다.
4. 매수의 경우 코인의 가격이 매수 거래보다 낮아지거나 같아지면 매수가 채결된다.
5. 매도의 경우 코인의 가격이 매도 거래보다 높아지거나 같아지면 매도가 채결된다.
6. 거래를 생성하는 시간보다 거래가 채결되는 시간이 더 빨라야 한다. (접은 글을 참고해주세요)
7. 매수, 매도 거래 생성시 이벤트 처리를 통해서 안전한 보관을 해야만 한다.

6번에 대해서 설명해 보려고 한다.

그 어떤 db, 로직을 사용한다고 해도 무조건적인 장점이 있는 것이 아니다. 그래서 거래를 생성하는 시간, 거래가 채결되는 시간 둘중 하나는 빨라지고 나머지 하나는 느려지게 되어있다. 이는 뒤에 나오는 로직에서 이유가 설명되어 있을 것이다. 그럼 거래를 채결하는 시간이 더 빨라야 하는 이유를 설명해보겠다.

• 슬리피지(Slippage) :
  주문한 가격이 체결될때 체결이 오래걸린다면 체결되는 가격과 실제 코인의 가격이 차이가 날수 있다. 체결 속도가 빨라진다면 이 가격 차이를 줄일 수 있다.
• 사용자 경험 개선 :
  상대적으로 주문을 할때 빠른 거래(단타)를 하는 사람도 있지만 나중을 보고 (장타)를 생각하는 주문도 있다. 즉 빠른 주문을 처리하지 않아도 될 확률이 높다. 반면에 체결의 경우 코인의 유동성에 따라 바로 바로 처리되야 해서 항상 빠른 체결을 처리해줘야 한다.
  또한 단타의 경우에도 거래 체결이 지연된다면 예상치 못한 가격 변동에 의해서 거래가 원하는 시점에 체결되지 않아 잠재적 손실을 만들수 있다.
• 병목 현상 개선 : 
  프로그램에는 항상 제한적인 속도가 존재한다. 아무리 빠른 컴퓨터도 제한적인 속도가 존재하기 때문에 주문이 체결되는 동안 코인의 가격이 변화하여 원래는 체결되야 하지만 체결되지 않는 현상 즉 병목현상이 생길 수도 있다.

3. 거래 로직 구현 설계

구현 프로젝트 구상도

3-1. 코인의 가격이 상승시

1. 서버는 코인 가격 상승 이벤트를 수신한다.
2. 서버는 자료구조를 찾아서 항상 최소값을 찾을 수 있고 이 최소값이 코인 가격보다 높아질 때까지 주문을 체결시켜 최소값이 코인 가격보다 높아진 상태가 되도록 유지한다.

3-2. 코인의 가격이 하락시

1. 서버는 코인 가격 하락 이벤트를 수신한다.
2. 서버는 자료구조를 찾아서 항상 최대값을 찾을 수 있고 이 최대값이 코인 가격보다 높아질 때까지 주문을 체결시켜 최소값이 코인 가격보다 높아진 상태가 되도록 유지한다.

즉 각 코인마다 최소값을 찾는 자료구조 최대값을 찾는 자료구조 해서 2개의 자료구조를 보유하게 된다.

4. 자료구조 선택

그렇다면 최대값 최소값을 O(1) 로 찾을 수 있도록 보장하는 자료구조가 어떤 것이 있을까

1. 우선 순위 큐  :
   항상 최소 혹은 최대값을 접근할 수 있게 해준다. 여러가지 종류가 있다.
   이진힙, 이진 탐색 트리, 피보나치 힙
2. AVL 트리 :
   모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이차를 1로 유지하는 균형 이진 트리
3. Skip List : 
   다중 레벨의 링크드 리스트 삽입이 적절한 위치에 삽입되어 정렬된 구조가 유지된다.
   특정 값을 찾을 때도 O(log n) 시간 복잡도로 이루어진다.

만약 위에 설명한 자료구조가 아닌 일반적 리스트 혹은 선형 DB를 사용할 경우를 비교해 설명해 보겠다.

주문은 체결이되면 삭제되어야한다. 리스트나 DB같은 경우 링크드가나 인덱싱이 됐다고 치자 그리고 삭제하는데 O(1)이 걸린다 가정한다. (아래 리스트는 예시를 들었을뿐 엄청나게 많은 가짓수가 존재한다. 비트맵,인덱싱, 헤쉬맵 사용등등 그렇지만 이들은 생략한다. 이유는 빈번하게 데이터가 갱신되는 주문이라는 행위에 맞지 않는 방식이라던지 찾는건 빠르지만 삭제가 터무니없이 느리다던가하는 단점이 너무 컷다.)

사용자가 주문을 만들때

• m : 사용자가 주문을 만드는 개수이다
• n : 체결을 기다리는 주문의 개수이다.

• 리스트 정렬을 미리 해둘경우 :
  O(m * n) = [정렬된 곳에 자리를 찾아 삽입에 걸리는 시간 O(n)]  * m 주문의 개수
  (DB 인덱스가 설정되어 있다면 삽입 그리고 정렬에 O(log n) 혹은 O(n) 이 걸리게 된다.)
• 리스트 정렬을 미리 정렬을 안할 경우 :
  O(m)  = [삽입에 걸리는 시간 O(1)] * m 주문의 개수
• 우선순위 큐와 비슷하게 동작하는 자료구조 예상 :
  O(m * logn)  = [삽입에 걸리는 시간 O(logn)] * m 주문의 개수

코인 가격 변동에 의해서 체결이 되야 할때

• m : 코인 가격이 변동되는 횟수
• n : 체결을 기다리는 주문의 개수

• 리스트 정렬을 미리 해둘경우 :
  O(m) = [최소혹은 최대값을 찾는데 걸리는 시간 O(1) + 삭제하는데 걸리는 시간 O(1)] * m 코인 가격 변동 횟수
• 리스트 정렬을 미리 정렬을 안할 경우 :
  O(m * n) = [최소혹은 최대값을 찾는데 걸리는 시간 O(n) + 삭제하는데 걸리는 시간 O(1) ] * m 코인 가격 변동 횟수
• 우선순위 큐와 비슷하게 동작하는 자료구조 예상 :
  O(m * logn )  = [최소혹은 최대값을 찾는데 걸리는 시간O(1) + 삭제하는데 걸리는 시간 logn)] * m 코인 가격 변동 횟수

아니 이렇게 정리해보니까 리스트 정렬을 미리 해두는 경우가 가장 빠른데요?

이는 함정이 있다. 주문이 10만개 정도 존재한다고 치자 이런경우가 생길 때 리스트 정렬할때 걸리는 시간이

삽입할때 10만 시간 이걸린다. m 즉 주문의 개수가 하루에 5번만 존재한다고 해도 DB에 50만 시간 복잡도이다. DB혹은 서버를 폭파시킬 생각이 아니라면 사용하면 안된다. 당연 서버에도 저장해선 안된다. (logn으로 하면 10만개 가 존재해도 5 시간복잡도이다.)

 

그럼 이런 자료구조를 사용해야한다는 건 알았다 근데. 우선순위큐를 사용한 서버에 모든 주문 값을 저장하기에는 서버부하가 너무 심해지는 문제가 있다. 또한 서버가 혹시라도 다운되어 버리면 모든 주문이 사라지게된다. 그래서 다른플랫폼 혹은 DB을 찾아봤다.

5. 자료구조를 구현할 소프트웨어

Apache Kafka

거래 저장하면 떠오르는 메세지 브로커

카프카는 큐를 사용해서 이벤트를 처리하는 대표적인 소프트웨어 이며 하드에 저장하는 방식을 생각해 이벤트가 소실되지 않도록하면서도 하드를 사용해도 속도가 느려지지 않게 만들어주는 소프트웨어이다.

하지만 이 소프트웨어는 우선순위 큐를 공식적으로 지원하지 않는다. 우선순위 큐와 비슷 한 방식을 구현할 수 있으나 이것은 파티션을 나눠서 우선순위를 매겨주는 방식이라 개수의 제한이 있어서 가격대가 다양할 나의 거래 로직에는 맞지 않아 채택되지 않았다.

RammbitMQ

kafka 랑 항상 같이 등장하지만 밀리는 메세지 브로커

레빗은 우선순위 큐를 사용할수있다.  x-max-priority를 사용할수 있는데 처음에 제대로 알아보지 않았을 땐 이걸 채택하려 했다. 하지만 이 우선순위는 kafka 파티션 나누는 방식과 별반 차이가 없었고 1~255까지만 우선순위를 나눌 수 있다. 이또한 나의 거래 로직에는 맞지 않다.

Redis

ZSET, Sorted Set을 사용해서 우선순위 큐를 구현할 수 있는 저장소

메모리에 저장되는 만큼 매우 빠른 속도를 가져갈수 있으나. 메모리에 저장하는 만큼 메모리 사용량이 많아질수 있다. 내가 돈이 많으면 ram을 무한정 달겠지만 이세상에 그렇게 하는 회사도 들어보지 못했으니 패스

Apache Cassandra

내가 채택한 NoSQL DB

Clustering key를  잘 설정해서 우선순위 큐랑 비슷한 결과를 만들수 있다(Sorted pages). 이는 삽입의 과정에서의 시간 복잡도를 O(1)로 만들어주기도하며 파티셔닝을 통해서 부하 분산이 가능하며 샤딩을 통해서 빠른 시간복잡도를 가져갈 수 있다. 내가 사용하는 프로그램이 코인이 상장되거나 폐지되거나 할때 유연하게 파티셔닝을 할수 있다는 것 또한 내게 이점으로 다가온다. 삭제또한 비동기로 삭제하며 비용을 줄일수 있다는 장점도 있다. 설계 과정이 복잡하다고 하는데 이는 더 공부를 해 봐야 할것 같다.

5. Architecture Diagram

주문

주문 로직은 이렇게 할것 같다.

1. 사용자가 주문 요청 
2. 서버는 요청을 처리해서 Log용 DB에 저장 및 주문 생성 이벤트 kafka에 전달
3. kafka는 cassandra에 이벤트를 처리가능할때마다 소모시킴

체결

체결 로직은 이렇게 될 것 같다.

1. 서버는 코인 가격이 변동됨을 인지함 이벤트를 생성해서 카프카에 전달
2. 카프카는 주문 채결 요청을 cassandra를 통해서 처리하고 서버는 주문 체결 요청을 기록함
3. 클라이언트는 이를 인지할수 있는 알림을 받거나 기록을 조회할 수 있음

주문 취소도 체결로직과 비슷한 방식을 사용할 것 같다.

6. 결론

처음에는 무지성 kafka를 사용하려고 했는데 아무생각없이 사용한다는 것이 설계과정에서 얼마나 위험한 것인지 인지했다. 그런 반면 기분은 좋다. 평소 자료구조랑 알고리즘을 좋아했고 이를 사용해볼 경험이 프로젝트에서 많지 않았는데 이번에 사용을 해본것 같다. 시간복잡도를 계산하는 과정이 즐거웠고 아키텍처 다이어그램을 그리는 과정도 재미있었다. 내가 구현을 완벽하게 할수 있을 것이라고 확신하진 않고 cassandra를 100%사용해서 설계대로 구현할수 있다고 확신하지도 않는다. 협업 프로젝트인 만큼 팀원의 도움을 받고 좀더 공부를 하면서 개발에 성공한다면, 멋진 설계 단계를 만든 것에 대한 자부심이 생기지 않을까?