중앙 거래소 호가 매칭 알고리즘 설계

개요

호가창 무결성을 보장하고 트랜잭션을 쉽게 관리하기위해서  RDB를 이용한 구현을 찾아봤다.

하지만 RDB를 이용한 구현은 수평적으로 확장이 어렵기 때문에 IO를 담당할 하나의 MASTER DB에 의존성이 매우 높다.

또한 물리적 성능 향상을 위해서는 더 좋은 장비를 구매해야하고 단일장비의 성능엔 한계가 존재한다. (물리적으로나 비용적으로나)

그래서 호가 매칭 알고리즘에서 IO가 많이 발생하는 사용자 주문 생성, 주문 매칭 단계는 수평적 확장이  쉬운 Redis를 사용하여 처리하고

매칭된 주문 트랜잭션 생성 및 처리는 Mysql에서 관리하는 방향으로 설계해 보았다.

Redis 살펴보기

1. 레디스는 메모리 기반 저장소라서 클러스터 서버 전체 다운시 데이터가 날아간다??
   
   1. Redis가 Memory 기반 저장소라서 캐시 전용 저장소로 오해하는 부분이 많은데, Redis도 옵션에 따라 텍스트 형태의 파일로 데이터를 저장할 수 있다.
      때문에 클러스터가 전체 다운되어도 파일을 통해 데이터를 복구할 수 있다.
2. 트랜잭션 관리가 어렵다??
   1. 레디스는 싱글 쓰레드 기반이라 트랜잭션 관리가 쉬운편이다.
      또한 Lua Script 를 사용하거나 트랜잭션을 지원하는 명령어 (MULTI) 를 통해서 트랜잭션을 보장할 수 있다.
   2. 오히려 싱글 쓰레드라 대량 작업시 블럭되는 점을 조심해야 한다. (keys 명령어나, 대용량 삭제와 같은 작업을 조심해야한다.)
3. 대용량 데이터 저장이 어렵다??
   1. 하나의 Key 당 최대 512MB까지 저장가능하다. 적지않은 사이즈지만 히스토리 정보까지 모두 메모리에 올려두기엔 부담스러운게 사실이다.
      그래서 IO 관련 데이터들만 redis에 저장하고 거래/히스토리 데이터는 RDB에서 관리하는 방향으로 설계해야한다.
4. 클러스터링을 지원하여 가용성이 높다?
   1. Redis를 사용하는 가장 큰 이유이기도하지만 가장 조심해야할 부분이기도 하다.
      클러스터 구성에 따라 다르지만 보통 레디스 클러스터는 Master - Slave 구조로 구성된다.
      Master가 다운될 시 Slave가 자동으로 Master로 승격되는데 이때 승격될 Slave 에 데이터가 비어있으면 모든 클러스터의 데이터가 비워지게 된다.
      우리는 Redis 클러스터를 직접 구현하지않고 AWS 를 사용할거라 다행이다 ^^

설계

필요한 자료구조

1. 주문 상황판
   (buy/sell 주문의 order price 별로 order quantity 를 가지는 Sorted Set<score, orderSum>)
   
2. 주문 리스트
   (Map<typeAndCoinAndPrice, List<order>> buyList, Map<typeAndCoinAndPrice, List<order>> sellList ) 
   
3. 내 주문
   (내 주문 상태를 관리하고 목록을 확인할 수 있는 Map<memberNo, Map<orderId, order>>)
   
   
4. 매칭된 두개의 Order 를 저장/처리할 Transaction RDB 테이블
   
   

동작 시나리오

1. 주문생성 (Create)  - (주문 생성 전 주문이 필요로하는 코인/현금만큼 사용자의 잔고를 freeze 해야한다.)
   1. 새로운 주문이 들어오면 시퀀스 시작. 
   2. (redis 트랜잭션 시작)
      '주문 상황판'을보고 매칭할 주문 리스트 진입점을 찾는다. (매칭되는 진입점이 없으면 v 단계로 이동)
      1. 주문 타입이 Buy면 주문 가격이하의 Sell List중 가장 저렴한 리스트를 찾는다.
      2. 주문 타입이 Sell이면 주문 가격 이상의 Buy List중 가장 비싼 리스트를 찾는
   3. 매칭되는 리스트가 있으면 LPOP으로 order를 꺼내오고, '주문 상황판'과 '내 주문'에서 해당 order를 제거한다. 
   4. 요청 들어온 주문과 매칭된 주문의 거래량을 비교하여 분기 시퀀스를 따른다. 
      1. IF (RequestOrder.quantity > MatchedOrder.quantity)면  두개의 주문을 갖는 Transaction 객체를 생성하고,
         RequestOrder.quantity 를 차감한다. 
         처리된 MatchedOrder를 상황판과 사용자별 주문에 반영한다.
         (redis 트랜잭션 커밋 후 다시 ii 단계부터 시작)
      2. ELSE IF (RequestOrder.quantity <= MatchedOrder.quantity) Matched Order을 RequestOrder.quantity 기준으로 분리한 후
         Transaction 객체를 추가하고, 분리된 여유분의 Order를  다시 주문리스트로 LPUSH한다. (RequestOrder 의 주문량은 0이됨)
         스플릿되어 처리된 MatchedOrder를 상황판과 사용자별 주문에 반영한다.
         (redis 트랜잭션 커밋후 vi 단계로 이동) 
   5. 매칭되는 리스트가 없으면 Request Order의 가격 리스트에 RPUSH 하고 상황판과 내 주문에 반영한다. 
      (redis 트랜잭션 커밋)
   6. 생성된 Transaction 객체들을 처리한다.
      
      1. 주문 밸리데이션 (잔고, 요청내용 2중 검증)
      2. 사용자별 잔고 증감 및 수수료 취득 
2. 주문 관리 (Read)
   1. 고객별 My 주문 리스트는 사용자 별 '내 주문' 모델을 통해 관리한다.
   2. 전체 주문량은 '주문 상환판' 모델을 통해 관리한다.
   3. 체결내역은 Transaction 테이블을 통해 관리한다.
3. 주문 수정 (Update)
   1. 주문량/주문가 수정의 경우
      (redis 트랜잭션 시작)
      대상 주문을 리스트에서 POP 하여 값 수정 후 RPUSH 
      주문 상황판, 내 주문도 업데이트
      (redis 트랜잭션 종료)
4. 주문 취소(Delete)
   1. 주문 취소의 경우
      (redis 트랜잭션 시작)
      대상 주문을 리스트에서 POP
      주문 상황판, 내 주문도 업데이트
      (redis 트랜잭션 종료)

예외 처리

1. 모든 주문은 요청 전에 검증(잔고확인, 소유자 확인, 권한 확인)을 통과해야한다.
2. 검증된 주문이라도 트랜잭션 처리 전에 한번 더 검증한다.
3. 주문처리 우선순위는 가격 > 시간이다.
4. 트랜잭션 생성을 위해 주문을 LPOP 하여 거래량 차감 후 LPUSH 하는사이 시간 우선순위를 위배할 수 있다.