개요

앞 편에서 본 매칭 알고리즘은 모두 한 가지 전제에서 출발했습니다. 누군가 주문의 도착 순서를 정한다는 전제입니다. Price-Time Priority의 "같은 가격이면 먼저 온 주문이 먼저"라는 규칙은 "먼저"가 무엇인지 정해져 있어야 작동합니다.

시리즈의 마지막 편인 이번 글에서는 이 전제를 CEX와 DEX 양쪽에서 비교합니다. 1편에서 Coinbase Exchange, Uniswap, dYdX 세 가지 구조를 짧게 나란히 놓아 봤는데, 이번에는 각 구조를 더 깊이 들여다보고 온체인 오더북이라는 네 번째 구조를 더합니다.

• CEX: 매칭엔진 한 곳이 순서를 정하는 구조와, 그 구조로 저지연을 만드는 방법 (Coinbase Exchange, LMAX)
• AMM: 오더북과 매칭을 없애고 pool과 수식으로 거래하는 구조 (Uniswap v2)
• 온체인 오더북: 오더북 자체를 블록체인 상태로 두는 구조 (Hyperliquid, Sui DeepBookV3)
• 오프체인 매칭: 오더북은 노드 메모리에 두고 결과만 합의로 확정하는 구조 (dYdX)

그리고 네 구조를 "체결 순서를 정하는 권한이 누구에게 있는가"라는 질문으로 다시 묶어 성능과 탈중앙성의 트레이드오프를 정리하고, 시리즈 전체를 돌아보겠습니다.

CEX — 매칭엔진 한 곳이 순서를 정한다

매칭엔진에 도착한 순서가 기준이다

1편과 3편에서 여러 번 인용한 Coinbase Exchange 문서의 첫 문장을 다시 보겠습니다.

Coinbase Exchange operates a continuous first-come, first-serve order book. Orders are executed in price-time priority as received by the matching engine.

(Coinbase Exchange는 선착순으로 처리되는 연속 오더북을 운영합니다. 주문은 매칭엔진이 받은 순서를 기준으로 price-time priority에 따라 체결됩니다.)

1편에서는 "as received by the matching engine"을 두고 기준 시각이 주문을 낸 시각이 아니라 매칭엔진에 도착한 시각이라는 점을 짚었습니다. 이번 편의 질문으로 바꿔 읽으면 이렇습니다. CEX에서 순서를 정하는 주체는 매칭엔진 하나입니다. 주문이 어느 경로로 들어오든 매칭엔진이 받은 순서가 곧 공식 순서이고, 거기에 다른 참여자가 이의를 제기할 수단은 없습니다.

이 구조는 단순하다는 것이 가장 큰 장점입니다. 순서를 두고 합의할 상대가 없으니 주문이 도착하는 즉시 체결 여부를 판단할 수 있습니다. 대신 참여자는 운영 주체가 그 순서를 공정하게 지킨다고 믿어야 합니다.

그렇다면 그 매칭엔진은 내부적으로 어떻게 생겼을까요? 이번 편에서 참고한 Coinbase 문서에는 매칭 규칙과 주문 상태만 나와 있고 내부 구현은 나와 있지 않습니다. 그래서 중앙 매칭엔진의 구조는 설계를 공개한 다른 거래 플랫폼의 사례로 살펴보겠습니다.

LMAX — 단일 스레드와 인메모리로 만든 저지연

LMAX는 금융 파생상품을 개인 투자자도 거래할 수 있게 만든 리테일 거래 플랫폼입니다. 코인 거래소는 아니지만, 거래소 매칭엔진의 설계를 상세히 공개한 드문 사례입니다. Martin Fowler가 2011년에 정리한 글은 이렇게 시작합니다.

The system is built on the JVM platform and centers on a Business Logic Processor that can handle 6 million orders per second on a single thread. The Business Logic Processor runs entirely in-memory using event sourcing.

(이 시스템은 JVM 위에 만들어졌고, 단일 스레드에서 초당 600만 건의 주문을 처리하는 Business Logic Processor가 중심에 있습니다. Business Logic Processor는 event sourcing을 사용해 전적으로 메모리 안에서 동작합니다.)

Business Logic Processor라는 이름은 LMAX 팀이 아니라 Fowler가 설명을 위해 붙인 이름입니다. 600만이라는 수치는 3GHz 듀얼 소켓 쿼드코어 Nehalem 기반 Dell 서버(RAM 32GB)에서 측정한 벤치마크라고 글의 각주에 적혀 있습니다.

이 프로세서가 주문 하나를 받을 때 하는 일도 글에 나옵니다.

• 대상 시장이 주문을 받을 수 있는 상태인지 확인합니다.
• 주문이 그 시장에서 유효한지 확인합니다.
• 주문 유형에 맞는 매칭 정책을 고릅니다.
• 주문이 가능한 최선의 가격에, 알맞은 유동성과 체결되도록 순서를 정합니다.
• 매칭으로 생긴 체결을 만들고 공개합니다.
• 새 체결을 바탕으로 가격을 갱신합니다.

2편과 3편에서 다룬 내용이 이 목록 안에 들어 있습니다. 매칭 정책을 고르는 것은 3편의 매칭 알고리즘이고, 최선의 가격과 알맞은 유동성을 찾는 것은 2편의 오더북을 훑는 과정입니다.

눈여겨볼 것은 이 모든 일을 단일 스레드에서 한다는 점입니다. 멀티코어 시대에 성능을 내려면 병렬 처리를 해야 한다는 것이 상식이고, LMAX 팀도 처음에는 그렇게 시작했습니다. 하지만 주문 처리는 병렬화하기 어려운 일이었습니다. 글은 그 이유를 이렇게 설명합니다.

Processing an order changes market conditions and these conditions need to be communicated.

(주문을 처리하면 시장 상황이 바뀌고, 바뀐 상황은 다른 쪽에 전달되어야 합니다.)

주문 하나가 체결되면 오더북이 바뀌고, 다음 주문은 바뀐 오더북을 기준으로 처리되어야 합니다. 3편에서 본 Price-Time Priority가 바로 이 성질을 요구합니다. 앞 주문이 어느 가격 레벨을 얼마나 소진했는지 알아야 뒤 주문의 체결 상대를 정할 수 있기 때문입니다. LMAX 팀이 Actor 모델로 만든 프로토타입에서는 프로세서가 실제 로직보다 큐를 관리하는 데 더 많은 시간을 썼고, 결국 팀은 비즈니스 로직 전체를 한 스레드에서 순서대로 처리하는 쪽을 택했습니다.

단일 스레드가 빠를 수 있는 이유는 모든 데이터가 메모리에 있기 때문입니다. 글에 따르면 Business Logic Processor에는 데이터베이스가 없습니다. 느린 IO도 없고, 처리가 순차적이므로 트랜잭션 처리도 필요 없습니다. 글에 따르면 이것만으로 초당 1만 건 수준이 나오고, 메서드를 작게 나누는 등 코드를 잘 다듬으면 10만 건 수준까지 올라갑니다. 마지막 한 자릿수는 캐시와 garbage collection을 고려한 컬렉션을 직접 구현하고 성능 테스트에 공을 들여 얻었다고 합니다.

장애가 나도 순서를 지키는 방법

모든 상태를 메모리에만 두면 서버가 꺼질 때 어떻게 될까요? LMAX의 답은 Event Sourcing입니다. Business Logic Processor의 현재 상태는 입력 이벤트를 처음부터 다시 처리하면 그대로 재현됩니다. 그래서 입력 이벤트만 디스크에 빠짐없이 기록해 두면 상태를 언제든 복구할 수 있습니다.

LMAX는 여기에 몇 가지를 더합니다. 매일 밤 상태의 스냅샷을 만들어 두어서, JVM 재시작부터 최근 스냅샷 적재와 하루치 기록 재생까지 전체 재시작이 1분 안에 끝납니다. 또 Business Logic Processor를 여러 개 동시에 돌립니다. 글이 쓰일 당시에는 주 데이터센터에 두 개, 재해 복구 사이트에 한 개가 같은 입력 이벤트를 처리했고, 그중 하나의 출력만 사용했습니다. 살아 있던 프로세서가 죽으면 마이크로초 단위로 다른 프로세서로 전환할 수 있습니다. 이 복제 덕분에 매일 밤 프로세서를 재시작하면서도 중단 없이 24/7로 거래를 처리합니다.

여기서 이번 편의 질문과 맞닿는 문장이 나옵니다. 여러 노드가 같은 입력을 처리하려면 모든 노드가 같은 순서로 입력을 받아야 합니다. LMAX는 노드 사이 통신에 IP multicast를 쓰는데, 그것만으로는 부족하다고 글은 설명합니다.

Even with IP multicasting, replication is still needed because IP messages can arrive in a different order on different nodes. The leader node provides a deterministic sequence for the rest of the processing.

(IP multicast를 쓰더라도 복제는 여전히 필요합니다. IP 메시지는 노드마다 다른 순서로 도착할 수 있기 때문입니다. 리더 노드가 나머지 처리를 위한 결정적인 순서를 제공합니다.)

입력 이벤트를 직접 받는 것은 리더 노드뿐이고, 리더가 정한 순서를 나머지 노드에 복제합니다. 리더가 죽으면 다른 노드가 리더가 되어 그 역할을 이어받습니다. 노드가 여러 개여도 순서를 정하는 곳은 언제나 한 곳입니다.

이 문제는 뒤에서 dYdX를 볼 때 다시 나옵니다. 메시지가 노드마다 다른 순서로 도착한다는 문제는 CEX에도 DEX에도 똑같이 있습니다. 차이는 그 순서를 누가 정하느냐입니다. LMAX는 운영사가 지정한 리더 노드에게 맡겼습니다.

DEX — 오더북을 어디에 둘 것인가

AMM — 오더북 대신 pool과 수식

1편에서 봤듯이 블록체인에 상태를 쓰는 데는 비용이 들고, 체결되지도 않을 주문을 매초 쓰고 지우는 오더북은 그 비용을 감당하기 어렵습니다. AMM 프로토콜을 체계적으로 정리한 Xu 등의 서베이 논문 「SoK: Decentralized Exchanges (DEX) with Automated Market Maker (AMM) Protocols」(이하 SoK 논문)도 같은 점을 짚습니다.

AMMs implement a peer-to-pool method, where liquidity providers (LPs) contribute assets to liquidity pools while individual users exchange assets with a pool or pools containing the input and the output assets. ... Furthermore, by using a conservation function for price setting, AMMs render moot the necessity of maintaining the state of an order book, which would be costly on a distributed ledger.

(AMM은 peer-to-pool 방식을 구현합니다. 유동성 공급자(LP)가 유동성 pool에 자산을 넣고, 개별 사용자는 입력 자산과 출력 자산을 담은 pool과 자산을 교환합니다. ... 또한 가격 결정에 conservation function을 쓰기 때문에, 분산 원장에서 비용이 많이 드는 오더북 상태를 유지할 필요 자체가 없어집니다.)

CEX와 오더북 DEX는 매수자와 매도자를 짝지어 주는 peer-to-peer 구조입니다. AMM은 거래 상대를 pool 하나로 고정한 peer-to-pool 구조입니다. 상대를 찾을 필요가 없으니 매칭도, 3편에서 본 매칭 알고리즘도 필요 없습니다.

가격을 정하는 것은 Conservation Function, 즉 거래 전후에 지켜야 하는 수식입니다. Uniswap v2는 두 자산 reserve의 곱이 줄어들 수 없다는 constant product 수식을 씁니다. 백서는 0.3% 수수료를 포함해 컨트랙트가 강제하는 조건을 이렇게 적습니다.

(x1 − 0.003 · xin) · (y1 − 0.003 · yin) >= x0 · y0

x0, y0은 거래 전 두 자산의 reserve, x1, y1은 거래 후 reserve, xin, yin은 각 자산이 pool에 들어온 양입니다. 한 자산을 넣고 다른 자산을 받는 보통의 교환이라면 한쪽 입력은 0입니다. 들어온 양에서 수수료만큼을 뺀 값으로 계산한 곱이 거래 전의 곱보다 작아지지 않아야 거래가 성립합니다.

이 구조에서는 슬리피지가 피할 수 없는 성질이 됩니다. SoK 논문은 이렇게 설명합니다.

Instead of matching buy and sell orders, AMMs determine exchange rates on a continuous curve, and every trade will encounter slippage conditioned upon the trade size relative to the pool size and the exact design of the conservation function.

(AMM은 매수·매도 주문을 매칭하는 대신 연속적인 곡선 위에서 교환 비율을 정하며, 모든 거래는 pool 크기 대비 거래 크기와 conservation function의 설계에 따라 슬리피지를 겪습니다.)

설명을 위해 만든 가상의 예시로 계산해 보겠습니다. 수수료는 빼고 constant product만 적용합니다. 10 ETH와 30,000 USDC가 들어 있는 pool이 있습니다. 거래 전 가격은 30,000 ÷ 10 = 3,000 USDC/ETH입니다. 여기에 3,000 USDC를 넣어 ETH를 삽니다.

받는 ETH는 10 − 9.0909 ≈ 0.9091 ETH이고, 실제 체결 가격은 3,000 ÷ 0.9091 ≈ 3,300 USDC/ETH입니다. SoK 논문의 정의대로 실제 교환 비율을 거래 전 spot 비율로 나눈 뒤 1을 빼면 3,300 ÷ 3,000 − 1 = 10%, 즉 거래 전 가격보다 10% 비싸게 산 셈입니다.

같은 3,000 USDC를 100 ETH와 300,000 USDC가 든 pool에 넣으면 USDC reserve는 303,000이 되고 ETH reserve는 30,000,000 ÷ 303,000 ≈ 99.0099가 됩니다. 받는 ETH는 약 0.9901 ETH, 체결 가격은 약 3,030 USDC/ETH로 슬리피지는 1%입니다. pool이 열 배 커지자 슬리피지가 열 배 줄었습니다.

2편에서 시장가 주문이 여러 가격 레벨을 먹어 들어가며 슬리피지가 생기는 과정을 봤습니다. 오더북에서는 최우선 호가의 잔량 안에서 체결되면 슬리피지가 0일 수 있지만, AMM에서는 아무리 작은 거래도 곡선 위를 움직이므로 슬리피지가 0이 되지 않습니다. 오더북의 깊이에 해당하는 것이 AMM에서는 pool의 크기입니다.

완전 온체인 오더북 — Hyperliquid와 DeepBook

AMM과 반대로 오더북을 포기하지 않고 블록체인 상태로 그대로 올린 DEX도 있습니다. Hyperliquid 문서는 자사 오더북을 이렇게 소개합니다.

The order book works in essentially the same way as all centralized exchanges but is fully on-chain. Orders are added where price is an integer multiple of the tick size, and size is an integer multiple of lot size. The orders are matched in price-time priority.

(오더북은 본질적으로 모든 중앙화 거래소와 같은 방식으로 동작하지만 완전히 온체인입니다. 주문은 가격이 tick size의 정수배이고 수량이 lot size의 정수배인 경우에만 추가됩니다. 주문은 price-time priority로 매칭됩니다.)

Tick Size는 가격의 최소 단위, Lot Size는 수량의 최소 단위입니다. 2편에서 본 가격 레벨이 tick size 간격으로 늘어서는 것입니다. 체결 규칙은 3편의 Price-Time Priority 그대로입니다. 문서 표현대로 CEX와 같은 방식을 체인 위에서 돌리는 구조입니다.

Sui의 DeepBookV3는 이 구조가 스마트 컨트랙트 수준에서 어떻게 생겼는지 보여 줍니다. 문서에 따르면 시장 하나는 Pool이라는 shared object 하나이고, Pool은 세 부분으로 나뉩니다.

오더북 자료구조인 BigVector는 온체인 B+ Tree로 구현되어 있고, 트리의 각 노드는 BigVector에 매달린 dynamic field로 저장됩니다. 2편에서 본 오더북이 정말로 체인 위의 자료구조로 존재하는 것입니다.

지정가 주문이 들어올 때 Book이 하는 일도 3편의 내용과 겹칩니다. 문서의 설명을 옮기면 다음과 같습니다.

• 입력값(수량, 가격, 타임스탬프, 주문 유형)이 허용 범위 안에 있는지 검증합니다.
• 반대편 오더북의 주문들을 차례로 훑습니다. 가격이 겹치고 그 maker 주문이 만료되지 않았으면 수량을 맞춰 체결(Fill)을 만들고, 전량 체결되었거나 만료된 maker 주문은 오더북에서 제거합니다.
• 남은 수량이 있으면 지정가 주문으로 오더북에 넣습니다.

3편에서 본 부분 체결과 잔량 처리의 흐름과 같습니다. 문서는 "Regardless of direction or order type, all DeepBookV3 matching is processed in a single function"이라고 덧붙이는데, 매수인지 매도인지, 주문 유형이 무엇인지와 상관없이 모든 매칭이 함수 하나에서 처리된다는 뜻입니다. 다만 이 문서는 같은 가격 안에서 어느 주문을 먼저 체결하는지는 명시하지 않습니다. 그래서 이 글에서도 DeepBook의 같은 가격 내 순서 규칙은 단정하지 않겠습니다.

그렇다면 DeepBook에서 주문의 도착 순서는 누가 정할까요? 실마리는 Pool이 shared object라는 점에 있습니다. 이 블로그의 Sui Object 시리즈에서 정리했듯이, 누구나 읽고 쓸 수 있는 Shared Object를 사용하는 트랜잭션은 합의(Consensus) 과정을 거쳐 순서를 결정합니다. 같은 Pool에 들어온 주문들의 순서는 매칭엔진 하나가 아니라 네트워크의 합의가 정하는 것입니다.

수수료 같은 거래 파라미터를 정하는 방식도 CEX와 다릅니다. DeepBookV3의 taker 수수료와 maker 수수료는 운영사가 정하지 않고, 해당 pool에 DEEP 토큰을 stake한 사용자들이 epoch마다 제안하고 투표해서 바꿉니다. 제안할 수 있는 범위도 정해져 있어서, 예를 들어 Volatile pool의 taker 수수료는 1~10 bps, maker 수수료는 0~5 bps 사이에서만 정할 수 있습니다.

오프체인 매칭과 온체인 확정 — dYdX

dYdX는 1편에서 본 대로 오더북을 각 노드의 메모리에 둡니다. 문서에 따르면 dYdX Chain은 CosmosSDK와 CometBFT로 만든 블록체인이고, 누구나 오픈소스 소프트웨어로 full node를 돌릴 수 있으며, 위임받은 거버넌스 토큰이 충분한 full node가 validator로 블록 생성에 참여합니다.

Each full node in the network maintains an in-memory order book, which undergoes state changes in real time as traders submit order instructions. Block proposers use trades from their local order book to build blocks, with matches generated by price-time priority. Since message arrival order varies between nodes, the order book may differ across the network at any given point in time.

(네트워크의 각 full node는 in-memory order book을 유지하며, 트레이더가 주문 지시를 제출할 때마다 실시간으로 상태가 바뀝니다. 블록 제안자는 자기 로컬 오더북의 체결로 블록을 만들고, 매칭은 price-time priority로 생성됩니다. 메시지 도착 순서가 노드마다 다르기 때문에, 어느 시점에서든 오더북은 네트워크 안에서 서로 다를 수 있습니다.)

"message arrival order varies between nodes"라는 문장은 앞에서 본 LMAX의 문장과 같은 문제를 가리킵니다. LMAX는 리더 노드가 순서를 정해 모든 노드를 맞췄습니다. dYdX에는 운영사가 지정한 리더가 없습니다. 대신 블록마다 제안자가 자기 로컬 오더북 기준으로 매칭을 만들고, 그 블록이 합의되면 그것이 공식 순서가 됩니다.

합의된 블록을 받은 노드가 하는 일도 문서에 나옵니다.

• 직전 블록의 상태에서 시작합니다. 블록을 제안하려고 쓰던 로컬 상태는 잠시 무시합니다.
• 새 블록의 변경 사항을 적용합니다.
• 그 위에 자기 로컬 상태를 다시 재생(replay)합니다. 이때 취소는 유지되고, 직전 로컬 상태에서 매칭됐던 주문은 다시 오더북에 놓입니다. 새 상태에서는 주문이 다르게 매칭되거나, 취소 때문에 놓이지 못하거나, 아예 매칭되지 않을 수도 있습니다.

노드가 주문을 받자마자 만드는 로컬 매칭은 문서 표현대로 "optimistic", 즉 낙관적인 결과일 뿐입니다. 합의된 블록이 그 결과를 덮어쓸 수 있습니다. CEX에서는 매칭엔진이 체결을 만든 순간이 곧 확정이지만, dYdX에서는 체결과 확정 사이에 합의가 끼어 있습니다.

성능과 탈중앙성의 트레이드오프

네 가지 구조 한눈에 보기

지금까지 본 네 가지 구조를 같은 기준으로 놓으면 다음과 같습니다. 1편의 비교표에 온체인 오더북을 더하고, "순서를 정하는 쪽" 행을 추가했습니다.

왼쪽에서 오른쪽으로 갈수록 순서를 정하는 권한이 운영사 한 곳에서 네트워크로 옮겨 갑니다. 그 대가로 체결이 확정되기까지 합의가 끼어들고, 상태를 쓰는 비용이 생깁니다. Fowler의 글은 LMAX 속도의 핵심을 모든 일을 순차적으로, 메모리 안에서 처리하는 데서 찾습니다. 순서를 정하는 곳이 한 곳이고 상태가 한 시스템의 메모리에 있다는 조건입니다. 탈중앙화는 바로 그 두 조건을 내려놓는 일입니다.

각 DEX는 이 대가를 서로 다른 곳에서 치릅니다. AMM은 오더북 상태를 없애 상태 비용을 피하는 대신 모든 거래에 슬리피지가 생기고, SoK 논문이 divergence loss라고 부르는 위험을 LP가 집니다. 온체인 오더북은 CEX와 같은 체결 규칙을 유지하는 대신 주문 하나하나가 체인의 상태 변경이 됩니다. dYdX는 오래 남지 않을 주문을 노드 메모리에만 두어 상태 비용을 피하는 대신, 노드마다 오더북이 어긋날 수 있다는 문제를 합의된 블록 기준의 재생으로 풉니다.

체결 순서를 정하는 권한

CEX에서 순서를 정하는 매칭엔진은 운영사가 통제합니다. 블록체인에서 그 역할에 해당하는 것은 트랜잭션을 블록에 담는 쪽입니다. 1편에서 Uniswap 백서가 오라클 조작 시나리오를 설명하며 "a miner who controls the ordering of transactions within a block"을 언급했다는 점을 짚었는데, SoK 논문은 이 권한을 더 직접적으로 다룹니다.

While transactions within a block share the same timestamp, miners can order transactions, and choose to include or exclude certain transactions at their discretion. Malicious miners can abuse their "power" to prioritize transactions in their favor, profiting from the miner extractable value (MEV) ...

(블록 안의 트랜잭션들은 같은 타임스탬프를 공유하지만, 채굴자는 트랜잭션의 순서를 정하고 특정 트랜잭션을 넣거나 뺄 수 있습니다. 악의적인 채굴자는 이 "권한"을 남용해 자기에게 유리하게 트랜잭션의 우선순위를 정하고 miner extractable value(MEV)로 이익을 얻을 수 있습니다.)

순서에 개입하는 것은 블록 생산자만이 아닙니다. SoK 논문에 따르면 Ethereum의 대표적인 노드 소프트웨어인 geth를 포함해 대부분의 채굴 소프트웨어는 트랜잭션을 gas price와 nonce 기준으로 정렬합니다. 그래서 누군가 mempool에 올라온 다른 사람의 트랜잭션을 보고 더 높은 gas price로 자기 트랜잭션을 보내면 그 앞에 끼어들 수 있습니다. 이것이 Frontrunning입니다.

AMM에서 이 문제는 앞에서 본 슬리피지와 결합합니다. 슬리피지가 항상 있으니 사용자는 거래할 때 어느 정도의 슬리피지까지 허용할지 정해야 하고, SoK 논문은 바로 이 허용치가 Sandwich Attack에 악용될 수 있다고 지적합니다. 공격자는 피해자의 거래 바로 앞에 같은 방향의 거래를 넣어 가격을 밀어 올리고, 피해자가 그 나빠진 가격에 체결된 직후 반대 거래로 이익을 챙깁니다. 논문은 2021년 9월 30일 Uniswap V2의 STARL/ETH 쌍에서 3분 사이에 일어난 두 건의 sandwich attack을 예로 드는데, 각각 약 0.031 ETH의 이익을 냈습니다.

방어 수단도 논문에 정리되어 있습니다. 사용자는 슬리피지 허용치를 낮게 잡을 수 있지만, 너무 낮게 잡으면 큰 거래일수록 트랜잭션이 실패해 gas만 날릴 수 있습니다. 거래소 차원에서는 트랜잭션 순서를 강제하는 방법이 있고, 논문은 EtherDelta와 0x처럼 오프체인 오더북에서 시간에 민감한 기능을 중앙화한 사례를 듭니다. 순서를 지키려고 순서를 정하는 권한을 다시 한 곳으로 모으는 셈입니다.

CEX의 중앙 매칭엔진에도 순서 경쟁은 있습니다. 1편에서 본 대로 같은 가격이라면 1밀리초라도 먼저 매칭엔진에 도착하는 쪽이 이깁니다. 차이는 경쟁의 규칙을 누가 쥐고 있느냐입니다. CEX에서는 운영사가 정한 규칙 안에서 도착 시각을 겨루고, 블록체인에서는 트랜잭션을 블록에 담는 쪽의 정렬 방식과 재량이 순서를 정합니다.

취소는 언제 확정되는가

순서 문제는 체결뿐 아니라 취소에도 영향을 줍니다. 3편에서 본 Coinbase Exchange의 주문 생명주기에서 done 상태는 "A partial order filled or canceled (and no longer eligible for matching)", 즉 취소된 주문은 더 이상 매칭 대상이 아니라는 뜻입니다. 매칭엔진이 취소를 처리하는 순간 그 주문은 체결될 수 없습니다.

dYdX에서는 사정이 다릅니다. 노드는 취소 지시를 받으면 이미 로컬에서 매칭된 경우가 아니라면 주문을 취소하지만, 그 취소가 모든 블록 제안자에게 전달된다는 보장은 없습니다. 문서는 이 위험을 직접 적어 둡니다.

While rare, it is possible for a cancel instruction to be seen by the current block proposer but not by one or more subsequent proposers (if the instruction isn't gossiped to them in time through the p2p network). In such cases, the order could still match after the sender expects it to have been cancelled.

(드물지만, 취소 지시를 현재 블록 제안자는 봤는데 이후의 제안자 중 하나 이상은 보지 못할 수 있습니다(p2p 네트워크로 제때 전달되지 않은 경우). 이때 주문은 보낸 사람이 취소됐다고 생각한 뒤에도 체결될 수 있습니다.)

그래서 dYdX의 주문과 취소에는 GTB(Good-Til-Block) 필드가 붙습니다. 지시가 만료되는 블록 높이입니다. 문서는 GTB가 지난 주문은 합의 규칙상 체결될 수 없으므로 GTB 만료가 주문을 확실히 체결 불가능하게 만드는 유일한 방법이라고 설명하고, API 트레이더에게 현재 블록 높이에 3을 더한 정도로 GTB를 짧게 잡으라고 권합니다.

주문을 고칠 때도 주의가 필요합니다. 3편에서 본 cancel-replace를 dYdX에서 그대로 하면 "A 주문, A 취소, B 주문"이라는 세 메시지 중 취소만 전달되지 않은 제안자가 A와 B를 둘 다 열린 주문으로 볼 수 있습니다. 그 상태에서 충분한 반대 주문이 들어오면 A와 B가 동시에 체결됩니다. 문서는 이를 막기 위해 같은 주문 ID에 더 큰 GTB를 붙여 보내는 replacement 지시를 쓰라고 권합니다.

CEX에서는 "취소했다"와 "체결될 수 없다"가 같은 순간입니다. 순서를 정하는 곳이 여럿이 되면 이 둘 사이에 시간 차가 생기고, 그 차이를 메우는 장치를 따로 만들어야 합니다.

마무리

이번 편 정리

CEX와 DEX의 매칭엔진은 "체결 순서를 누가 정하는가"라는 질문에 서로 다른 답을 냅니다.

• CEX는 매칭엔진 하나가 순서를 정합니다. LMAX는 그 구조를 단일 스레드와 메모리로 밀어붙여 초당 600만 건을 처리했고, Event Sourcing과 리더 노드로 장애 상황에서도 하나의 순서를 유지했습니다.
• AMM은 오더북과 매칭을 없애고 pool과 Conservation Function으로 가격을 정합니다. 모든 거래에 pool 크기에 따른 슬리피지가 생기고, 같은 블록 안의 순서는 트랜잭션을 블록에 담는 쪽이 정합니다.
• 온체인 오더북은 오더북 자체를 체인 상태로 둡니다. Hyperliquid는 CEX와 같은 Price-Time Priority를 체인 위에서 돌리고, DeepBookV3는 shared object인 Pool 안에 B+ Tree 오더북과 정산 로직을 둡니다.
• dYdX는 오더북을 노드 메모리에 두고 블록 제안자가 매칭한 결과를 합의로 확정합니다. 노드마다 오더북이 어긋날 수 있어 취소 확정에는 GTB라는 별도 장치가 필요합니다.
• 순서를 정하는 권한이 한 곳에서 네트워크로 옮겨 갈수록 신뢰해야 할 대상은 운영사에서 코드와 합의로 바뀌고, 그 대가로 확정까지의 지연, 상태 비용, MEV 같은 새로운 문제가 생깁니다.

시리즈를 마치며

네 편에 걸쳐 매칭엔진을 살펴봤습니다.

1. 매칭엔진의 역사와 진화: 객장의 Specialist에서 Nasdaq의 전산화, Island ECN과 INET을 거쳐 코인 거래소와 DEX까지, 매칭의 주체가 어떻게 옮겨 왔는지 따라갔습니다.
2. 오더북의 구조: Bid와 Ask, 스프레드, 가격 레벨, 지정가와 시장가 주문, 깊이와 슬리피지로 매칭엔진이 들여다보는 장부의 모양을 확인했습니다.
3. 매칭 알고리즘: Price-Time Priority와 Pro-Rata, CME Globex의 조합형 알고리즘, 부분 체결과 Self-Trade Prevention으로 누구에게 얼마를 체결시키는지 정리했습니다.
4. CEX vs DEX 매칭엔진 비교(이 글): 같은 문제를 중앙 매칭엔진, AMM, 온체인 오더북, 오프체인 매칭이 각각 어떻게 푸는지 비교했습니다.

1편의 마무리에서 오더북과 Price-Time Priority는 30년의 이동에도 살아남았다고 적었습니다. 이번 편까지 와서 보면 그 규칙이 살아남은 곳과 사라진 곳의 경계도 보입니다. Hyperliquid와 dYdX는 블록체인 위에서도 CEX와 같은 규칙을 지켰고, Uniswap은 규칙을 없애는 대신 수식을 택했습니다.

그리고 어느 구조든 끝까지 남는 질문은 같았습니다. "먼저 온 주문"의 "먼저"를 누가 정하는가입니다. 객장에서는 Specialist가, 전자 거래소에서는 매칭엔진이, LMAX에서는 리더 노드가, 블록체인에서는 블록을 만드는 쪽과 합의가 그 답이었습니다. 어떤 거래소를 보든 이 질문 하나를 던지면 그 거래소의 매칭엔진이 어떤 구조이고 무엇을 신뢰해야 하는지가 드러납니다.

References

CEX

• Coinbase Exchange — Matching Engine (공식 문서)
• Martin Fowler — The LMAX Architecture (2차 자료)

DEX — AMM

• Uniswap v2 Core Whitepaper (공식 백서)
• Xu et al. — SoK: DEX with AMM Protocols (arXiv 2103.12732, ACM Computing Surveys 2023)

DEX — 오더북

• dYdX Documentation — Limit Orderbook and Matching (공식 문서)
• Hyperliquid Docs — Order book (공식 문서)
• Sui Docs — DeepBookV3 Design (공식 문서)