Coinbase - Order Book & Matching Engine

Dados da empresa e da vaga

Empresa: Coinbase Global, Inc.
Sede: Remota / Estados Unidos (com presença global e contratação remota internacional)
Perfil da vaga: Senior Software Engineer — Core Exchange & Matching Engine
Modelo de trabalho: Remoto global (Remote-First)
Faixa salarial estimada da vaga:
- Sênior nos EUA: $185.000 a $240.000 (Base) / $380.000 a $550.000 USD/ano (Total Comp com ações na NASDAQ: COIN)
- Sênior Internacional Remoto (LATAM/Europa): $90.000 a $140.000 USD/ano
Stack principal do time: Go, Docker, Kubernetes, AWS, PostgreSQL, Redis, Apache Kafka, gRPC, WebSockets

Contexto do desafio técnico

A Coinbase opera uma das maiores e mais líquidas exchanges de criptoativos do mundo. O núcleo da plataforma é a Matching Engine (Motor de Cruzamento de Ordens), responsável por processar dezenas de milhares de ordens de compra e venda por segundo com latência determinística na casa dos microssegundos.

Em entrevistas técnicas avançadas para o time de Core Exchange da Coinbase, os candidatos são avaliados sobre estruturas de dados complexas, prioridade estrita de ordens, integridade contábil e concorrência segura sem corrupção de estado.

O desafio clássico consiste em construir um Order Book (Livro de Ofertas) e Matching Engine em memória para um par de negociação específico (como BTC/USD), garantindo correspondência de ordens com a regra de prioridade preço-tempo (Price-Time Priority).

Regras de negócio e funcionamento da bolsa

1. Tipos de ordens

Limit Order (Ordem Limitada):
- O usuário especifica o lado (Buy ou Sell), a quantidade e o preço limite desejado.
- Uma ordem de compra com preço limite $P$ só pode ser executada por um preço menor ou igual a $P$.
- Uma ordem de venda com preço limite $P$ só pode ser executada por um preço maior ou igual a $P$.
- Se a ordem não puder ser totalmente executada de imediato contra o livro existente, a quantidade remanescente deve ser inserida no livro de ofertas (resting order).
Market Order (Ordem a Mercado):
- O usuário especifica o lado e a quantidade, sem determinar preço.
- Deve ser executada imediatamente contra as melhores ofertas disponíveis no livro oposto até ser totalmente preenchida ou até o livro esgotar a liquidez disponível.

2. Regra de Prioridade Preço-Tempo (Price-Time Priority / FIFO)

Melhor Preço: Ordens de compra com preços maiores têm prioridade de execução sobre compras de preços menores. Ordens de venda com preços menores têm prioridade sobre vendas mais caras.
Critério de Desempate Temporal: Quando duas ordens estão no mesmo nível de preço, a ordem que entrou primeiro no livro deve ser executada primeiro (comportamento de fila FIFO).

3. Execuções parciais (Partial Fills)

Uma ordem grande de 10 BTC pode ser satisfeita pelo cruzamento de várias ordens menores no lado oposto (ex.: 2 BTC + 3 BTC + 5 BTC).
A cada cruzamento bem-sucedido, um evento de negociação (Trade) é gerado com: TradeID, MakerOrderID, TakerOrderID, Price, Quantity e Timestamp.

Estrutura de dados recomendada de alta performance

Em engines profissionais de bolsa, o livro de ofertas não pode ser implementado com varreduras em fatias (slices), pois isso resultaria em complexidade ineficiente $O(N)$ por inserção ou cancelamento.

A arquitetura padrão ouro combina:

Árvore de Busca Balanceada (ou Heap/SkipList): Ordena os níveis de preço.
- Lado de Compra (Bids): ordenação decrescente (maior preço no topo).
- Lado de Venda (Asks): ordenação crescente (menor preço no topo).
Lista Duplamente Ligada (Doubly Linked List): Em cada nível de preço, mantém a fila de ordens ativas para inserção no fim e remoção na cabeça em tempo constante $O(1)$.
Mapa Hash (map[string]*Order): Permite cancelamento ou localização de qualquer ordem em $O(1)$.

Exemplo de implementação central em Go

package exchange

import (
	"container/list"
	"errors"
	"sync"
	"time"
)

type Side string

const (
	Buy  Side = "BUY"
	Sell Side = "SELL"
)

type Order struct {
	ID        string
	Side      Side
	Price     float64
	Amount    float64
	Timestamp time.Time
}

type Trade struct {
	MakerOrderID string
	TakerOrderID string
	Price        float64
	Amount       float64
	Timestamp    time.Time
}

type LimitLevel struct {
	Price  float64
	Orders *list.List // Fila FIFO de ordens com mesmo preço
}

type OrderBook struct {
	mu     sync.Mutex
	bids   map[float64]*LimitLevel // Compras
	asks   map[float64]*LimitLevel // Vendas
	orders map[string]*list.Element
	trades []Trade
}

func NewOrderBook() *OrderBook {
	return &OrderBook{
		bids:   make(map[float64]*LimitLevel),
		asks:   make(map[float64]*LimitLevel),
		orders: make(map[string]*list.Element),
	}
}

// ProcessLimitOrder processa e cruza uma ordem limitada
func (ob *OrderBook) ProcessLimitOrder(order *Order) []Trade {
	ob.mu.Lock()
	defer ob.mu.Unlock()

	var executedTrades []Trade

	if order.Side == Buy {
		// Tenta casar contra o melhor preço de venda (menor Ask)
		executedTrades = ob.matchBuy(order)
	} else {
		// Tenta casar contra o melhor preço de compra (maior Bid)
		executedTrades = ob.matchSell(order)
	}

	// Se sobrou saldo na ordem, adiciona ao livro
	if order.Amount > 0 {
		ob.addOrderToBook(order)
	}

	return executedTrades
}

func (ob *OrderBook) matchBuy(taker *Order) []Trade {
	var trades []Trade

	for taker.Amount > 0 {
		bestAskPrice, exists := ob.getBestAskPrice()
		if !exists || bestAskPrice > taker.Price {
			break // Não há vendedores aceitando esse preço
		}

		level := ob.asks[bestAskPrice]
		trades = append(trades, ob.matchLevel(level, taker)...)

		if level.Orders.Len() == 0 {
			delete(ob.asks, bestAskPrice)
		}
	}

	return trades
}

func (ob *OrderBook) matchSell(taker *Order) []Trade {
	var trades []Trade

	for taker.Amount > 0 {
		bestBidPrice, exists := ob.getBestBidPrice()
		if !exists || bestBidPrice < taker.Price {
			break // Não há compradores pagando esse preço
		}

		level := ob.bids[bestBidPrice]
		trades = append(trades, ob.matchLevel(level, taker)...)

		if level.Orders.Len() == 0 {
			delete(ob.bids, bestBidPrice)
		}
	}

	return trades
}

func (ob *OrderBook) matchLevel(level *LimitLevel, taker *Order) []Trade {
	var trades []Trade

	currElem := level.Orders.Front()
	for currElem != nil && taker.Amount > 0 {
		nextElem := currElem.Next()
		maker := currElem.Value.(*Order)

		tradedAmount := maker.Amount
		if taker.Amount < tradedAmount {
			tradedAmount = taker.Amount
		}

		trade := Trade{
			MakerOrderID: maker.ID,
			TakerOrderID: taker.ID,
			Price:        maker.Price, // O preço de execução é sempre o da ordem que já estava no livro (maker)
			Amount:       tradedAmount,
			Timestamp:    time.Now(),
		}
		trades = append(trades, trade)

		maker.Amount -= tradedAmount
		taker.Amount -= tradedAmount

		if maker.Amount == 0 {
			level.Orders.Remove(currElem)
			delete(ob.orders, maker.ID)
		}

		currElem = nextElem
	}

	return trades
}

func (ob *OrderBook) addOrderToBook(order *Order) {
	targetMap := ob.bids
	if order.Side == Sell {
		targetMap = ob.asks
	}

	level, exists := targetMap[order.Price]
	if !exists {
		level = &LimitLevel{
			Price:  order.Price,
			Orders: list.New(),
		}
		targetMap[order.Price] = level
	}

	elem := level.Orders.PushBack(order)
	ob.orders[order.ID] = elem
}

func (ob *OrderBook) getBestAskPrice() (float64, bool) {
	var minPrice float64
	first := true
	for p := range ob.asks {
		if first || p < minPrice {
			minPrice = p
			first = false
		}
	}
	return minPrice, !first
}

func (ob *OrderBook) getBestBidPrice() (float64, bool) {
	var maxPrice float64
	first := true
	for p := range ob.bids {
		if first || p > maxPrice {
			maxPrice = p
			first = false
		}
	}
	return maxPrice, !first
}

O que os avaliadores da Coinbase procuram

Determinação do preço de execução (Maker vs. Taker): O preço do negócio deve ser rigorosamente o preço da ordem que já repousava no livro (Maker), e não o preço da ordem que acabou de chegar ao mercado (Taker).
Concorrência determinística: No exemplo acima, um mutex protege o livro. Em sistemas de ultra-alta frequência, a Coinbase valoriza candidatos que discutem a alternativa do Padrão Actor / Single-Thread Worker: canal serializador em Go onde uma única goroutine processa todas as ordens de um par de trading sequencialmente, eliminando a necessidade de mutexes e garantindo latência estável sem contenção de threads.
Integridade de saldos e ausência de arredondamento espúrio: Em implementações completas, o uso de representação em inteiros baseados em unidades mínimas (como Satoshis para Bitcoin ou Centavos/Micros para moedas fiduciárias) é fortemente apreciado para evitar erros de ponto flutuante.
Tratamento de cancelamento eficiente: Capacidade de cancelar uma ordem em $O(1)$ usando o ponteiro indexado no mapa sem percorrer a lista linearmente.

Neste texto