Skip to main content

Online Stock Exchange

A tiny exchange: traders place buy and sell orders on an instrument, and something has to decide which ones turn into a trade. The class model matters more than the matching algorithm here - get Order and OrderBook right and the matching logic is a dozen lines.

Requirements​

Functional

  • A trader places a buy or sell order for a quantity of an instrument, either at a fixed price (limit order) or at whatever the best available price is (market order).
  • A buy order matches a sell order when their prices cross; a trade is created for the overlapping quantity.
  • Partially filled orders stay on the book for their remaining quantity.
  • A trader can cancel an order that hasn't fully filled yet.

Non-functional

  • Matching must always prefer the best price first (highest bid, lowest ask), then earliest order at that price - price-time priority, not first-come-first-served across all prices.
  • Adding a new order type (say, stop-loss) should extend Order, not require rewriting OrderBook's matching loop.

Design​

OrderBook holds two sides - bids and asks - each kept sorted by price-time priority, and its match method only ever looks at the best order on each side. Order itself carries whether it's a limit or market order as data (a price, or none), so the book doesn't need a different code path per order type.

TraderExchangeOrderBookTradeplaceOrder(order)1addOrder(order)2match()3new Trade(buy, sell, qty, price)4cancelOrder(orderId)5
  1. 1The trader submits an order for one instrument - the exchange routes by instrument symbol.
  2. 2The order lands on the correct side (bids or asks) of that instrument’s book, sorted by price-time priority.
  3. 3The book peeks at the best bid and best ask; if they cross, a fill happens for the overlapping quantity.
  4. 4A trade is recorded once a match is found; both orders’ remaining quantities are reduced.
  5. 5A trader can pull an order that hasn’t fully filled; the book removes it from its side.

A Trade is the one output of matching that outlives the match call - it's what both traders and any downstream settlement system actually care about, independent of how the book got there.

Class diagram​

Exchange- books: Map<Instrument, OrderBook>+ placeOrder(order): void+ cancelOrder(orderId): voidOrderBook- instrument: Instrument- bids: List<Order>- asks: List<Order>+ addOrder(order): void+ match(): List<Trade>Instrument- symbol: stringOrder- id: string- side: Side- price: Optional<double>- quantity: int- placedAt: datetimeTrade- buyOrderId: string- sellOrderId: string- price: double- quantity: int
usescreates
OrderBook holds two priority-ordered sides of Orders on one Instrument and emits Trades when a bid and an ask cross.

Code​

import java.time.Instant;
import java.util.*;
 
enum Side { BUY, SELL }
 
class Instrument {
final String symbol;
 
Instrument(String symbol) {
this.symbol = symbol;
}
}
 
class Order {
final String id;
final Side side;
final Double price;
int quantity;
final Instant placedAt;
 
Order(String id, Side side, Double price, int quantity) {
this.id = id;
this.side = side;
this.price = price;
this.quantity = quantity;
this.placedAt = Instant.now();
}
 
boolean isMarketOrder() {
return price == null;
}
}
 
class Trade {
final String buyOrderId;
final String sellOrderId;
final double price;
final int quantity;
 
Trade(String buyOrderId, String sellOrderId, double price, int quantity) {
this.buyOrderId = buyOrderId;
this.sellOrderId = sellOrderId;
this.price = price;
this.quantity = quantity;
}
}
 
class OrderBook {
final Instrument instrument;
private final List<Order> bids = new ArrayList<>();
private final List<Order> asks = new ArrayList<>();
 
OrderBook(Instrument instrument) {
this.instrument = instrument;
}
 
void addOrder(Order order) {
List<Order> side = order.side == Side.BUY ? bids : asks;
side.add(order);
side.sort((a, b) -> {
double pa = a.isMarketOrder() ? (order.side == Side.BUY ? Double.MAX_VALUE : 0) : a.price;
double pb = b.isMarketOrder() ? (order.side == Side.BUY ? Double.MAX_VALUE : 0) : b.price;
int byPrice = order.side == Side.BUY ? Double.compare(pb, pa) : Double.compare(pa, pb);
return byPrice != 0 ? byPrice : a.placedAt.compareTo(b.placedAt);
});
}
 
void cancelOrder(String orderId) {
bids.removeIf(o -> o.id.equals(orderId));
asks.removeIf(o -> o.id.equals(orderId));
}
 
List<Trade> match() {
List<Trade> trades = new ArrayList<>();
while (!bids.isEmpty() && !asks.isEmpty()) {
Order bestBid = bids.get(0);
Order bestAsk = asks.get(0);
boolean crosses = bestBid.isMarketOrder() || bestAsk.isMarketOrder()
|| bestBid.price >= bestAsk.price;
if (!crosses) break;
 
int qty = Math.min(bestBid.quantity, bestAsk.quantity);
double price = bestAsk.isMarketOrder() ? bestBid.price : bestAsk.price;
trades.add(new Trade(bestBid.id, bestAsk.id, price, qty));
 
bestBid.quantity -= qty;
bestAsk.quantity -= qty;
if (bestBid.quantity == 0) bids.remove(0);
if (bestAsk.quantity == 0) asks.remove(0);
}
return trades;
}
}
 
class Exchange {
private final Map<String, OrderBook> books = new HashMap<>();
 
void registerInstrument(Instrument instrument) {
books.put(instrument.symbol, new OrderBook(instrument));
}
 
List<Trade> placeOrder(String symbol, Order order) {
OrderBook book = books.get(symbol);
book.addOrder(order);
return book.match();
}
 
void cancelOrder(String symbol, String orderId) {
books.get(symbol).cancelOrder(orderId);
}
}

Design decisions​

  • OrderBook is per-instrument, never a single book for the whole exchange. Orders for AAPL and orders for GOOG never interact, so keeping one book per instrument means matching is naturally scoped and one busy instrument's order volume never slows down matching for a quiet one.
  • A market order is a limit order with no price, not a separate class. Both are the same object with the same fields; a market order simply matches against the best available price on the other side instead of requiring its own price to cross. Splitting it into its own class would duplicate every field except one.
  • Price-time priority is an ordering rule on the book's data structure, not a loop condition scattered through match. Bids are kept sorted highest-price-first (ties broken by earlier timestamp), asks lowest-price-first, so match only ever has to peek at the head of each side rather than scan for "the best one."
  • What's missing for a real system: this book is single-threaded and in-memory; a real exchange needs the match step to be atomic under concurrent order submission (a lock per instrument, or a single-writer queue per book), and needs every fill to be durably logged before being acknowledged, since a trade can't be un-happened once reported to a trader.
0%0 of 122 pages studied