Notes
Requirements
Fix the scope. Users have accounts with cash and shares. They place market or limit orders to buy or sell. Before an order is accepted we check they have enough cash or shares, and we block that amount at once. Each stock has its own order book, matched by best price and then by time. Orders can fill partly and can be cancelled. Users see a portfolio with profit and loss. Margin, options and short selling are out of scope.
Ask the questions that change the code. Do we run the matching ourselves? Yes, so the order book is in scope. At what price does a trade happen? At the price of the order that was already resting in the book. What if a market order finds too few sellers? Fill what is there and cancel the rest. Can a user sell shares already promised to another open order? No, they are blocked. And money is a long number of paise, never a double.
- accounts hold cash and shares
- market and limit, buy and sell
- check cash or shares first
- and block them at placement
- order book per stock
- match: best price, then oldest
- partial fills, cancel an order
- portfolio with profit and loss
- trade and price notifications
- out of scope: margin, options
- are we the exchange too?
- yes, we match in-house
- trade at whose price?
- the resting order price
- market order with thin book?
- fill what is there, cancel rest
- can a seller sell shares
- already in an open order?
- no, they are blocked
- money type?
- long paise, never double
Entities
Now the entities. An account places orders. Each stock has an order book with two sides, bids for buyers and asks for sellers. A side is a set of price levels, and each level is a queue of orders at that exact price. When a buy meets a sell, the engine creates a trade, which fills a part of both orders. Notice the user is not a class here; login and profile belong to other services.
Class diagram
Turn them into types. Side, order type and status are enums. A trade is a fact that never changes, so it is a Java record. The order is mutable: it counts how much has been filled, how much cash it still has blocked, and its status. That sounds risky, but there is a rule that makes it safe: an order is only ever changed on the matching thread of its own stock. We will come back to that rule.
enum Side { BUY, SELL }
enum OrderType { MARKET, LIMIT }
enum Status { OPEN, PARTIALLY_FILLED,
FILLED, CANCELLED, REJECTED }
record Trade(id, symbol, buyOrder,
sellOrder, buyer, seller, qty, price)
class Order {
final qty, limitPaise; // 0 if market
long filled, reservedCash;
Status status;
} Pre-trade checks
Each account splits cash and shares into two buckets: free and blocked. A buy order checks there is enough free cash and moves it to blocked in one atomic step, so a second order cannot spend the same money. A sell order does the same with shares. Checking first and blocking later would let two orders pass the same check. Blocked amounts go back to free when an order is cancelled, or leave the account when it trades.
synchronized boolean tryBlockCash(long p) {
if (p > cash) return false;
cash -= p;
blockedCash += p;
return true;
}
limit buy 50 @ 99.00: block 4,950.00
sell 150 with 100 free: REJECTED
total = free + blocked, never changes
except by trades Order book
Here is the order book. Each side is a tree map from price to a queue of orders. Asks are sorted lowest first, because a buyer wants the cheapest seller. Bids are sorted highest first, because a seller wants the richest buyer. Inside one price, the queue keeps arrival order, so the first order to arrive is the first to trade. That rule is called price-time priority, and the tree map plus a queue gives it to us almost for free.
NavigableMap<Long, ArrayDeque<Order>> bids = new TreeMap<>(reverseOrder()); asks = new TreeMap<>(); ASK 103.00 x 200 (1 order) ASK 102.00 x 100 (1 order) ASK 101.00 x 150 (2 orders) ----- firstKey(): best price, O(log n) peekFirst(): oldest order there
Matching engine
The matching loop is short. While the incoming order still wants shares and the other side is not empty, look at the best opposite price. A limit order stops when that price no longer crosses its limit; a market order never stops on price. Take the oldest order at that level, trade the smaller of the two remaining amounts, at the resting price. Drop the resting order when it is done, and drop the level when it is empty.
while (in.remaining() > 0
&& !other.isEmpty()) {
long price = other.firstKey();
if (limit order && !crosses) break;
Order rest = level.peekFirst();
long q = min(in.remaining(),
rest.remaining());
settle(buy, sell, q, price);
if (rest done) level.pollFirst();
if (level empty) other.remove(price);
} Flow: partial fills
Walk one order. Two sellers rest at one hundred and one rupees: the maker with a hundred shares, then a trader with fifty, who arrived later. A fund buys a hundred and twenty at that price. The engine blocks the cash, then fills the maker's hundred first, because that order is older, and takes twenty of the trader's fifty. The fund is filled. The trader is partially filled, and thirty shares stay in the book, still in their place in the queue.
- MAKER sells 100 at 101.00
- TRADER sells 50 at 101.00
- (arrived later)
- FUND buys 120 at 101.00:
- 100 from MAKER: FILLED
- 20 from TRADER: 20 of 50
- TRADER: PARTIALLY_FILLED,
- 30 still rests in the book
Flow: market order
A market order has no price, so how much cash do we block? We walk the asks on the engine thread and add up what two hundred and fifty shares would cost right now. Because nothing else can touch the book in between, that number is exact. The order then sweeps three levels: thirty at one hundred and one, a hundred at one hundred and two, and a hundred and twenty at one hundred and three. If the book runs dry, the rest is cancelled and its cash released.
before: 101.00 x 30, 102.00 x 100,
103.00 x 200
block = book.sweepCost(250)
= 25,590.00, on the same thread
fills: 30 + 100 + 120, avg 102.36
after: 103.00 x 80
thin book: fill what is there,
cancel the rest, release cash Order states
An order is open while it rests untouched, partially filled once some of it trades, and filled when nothing is left. Cancelled and rejected are the other final states. Cancel is allowed only on a live order: remove it from its price level, set it to cancelled, and release whatever it still has blocked. A second cancel simply returns false. The cancel request goes through the same queue as orders, so it can never overtake the order it is cancelling.
- OPEN: resting, nothing filled
- PARTIALLY_FILLED: some filled
- FILLED: final, leftover cash
- released
- CANCELLED: final, the rest of
- the cash or shares released
- REJECTED: failed the checks
- cancel a live order: true
- cancel it again: false
Settlement
Every trade settles into both accounts. The buyer's blocked cash goes down by quantity times price, and their shares go up. The seller's blocked shares go down and their free cash goes up by the same amount. Cash only moves from one account to another, and so do shares, so the totals across all accounts never change. A buyer who bid one hundred and one but traded at one hundred keeps the difference; it is released when the order finishes.
paise = qty * price; buyer.settleBuy(sym, qty, paise); // blocked cash out, shares in buy.reservedCash -= paise; seller.settleSell(sym, qty, paise); // blocked shares out, cash in fill(buy, qty); fill(sell, qty); lastPrice = price; notify listeners
Observer
Trades and price changes go out through the Observer pattern. After each trade the engine calls every market listener. A watchlist is just a listener that keeps a set of symbols and speaks only when one of their prices moves. A market data feed, trade confirmations and risk alerts are more listeners, and the engine never knows they exist. In production these calls go onto a queue, so a slow listener cannot slow down matching.
interface MarketListener {
void onTrade(Trade t);
}
listeners: CopyOnWriteArrayList
Watchlist implements MarketListener
symbols: a concurrent set
speaks only when the price moves
also: market data feed, trade
confirmations, risk alerts Portfolio and P&L
The portfolio view needs two kinds of profit and loss. Each account keeps a cost basis per stock. When shares are sold, the average cost of those shares leaves the basis, and the difference from the sale price is realised profit or loss. For what is still held, the value at the last traded price minus the remaining cost is the unrealised profit or loss. Our fund sold thirty below cost, so it realised a small loss.
- bought 370 ACME, cost 37,710.00
- sold 30 at 99.00
- cost out: 37,710 x 30 / 370
- realised P&L: -87.56
- holds 340, avg 101.91
- last trade 99.00
- value 33,660.00
- unrealised P&L: -992.44
Concurrency
Now the big concurrency choice. We could lock the book, but price-time priority means orders for one stock must be handled one at a time anyway, so locks add cost and bugs while giving no parallel work. Instead each symbol gets one thread with a queue. The book has no locks, and the same input always produces the same trades, so you can replay an order log after a crash. Different symbols run in parallel on different threads, which is how we scale.
Check every shared field. The book and its orders belong to one symbol thread. Accounts are shared, because one user can trade two stocks at once on two threads, so each account method is short and synchronized. Settlement updates the buyer, then the seller, never holding both locks, so there is no deadlock. Cancels use the order queue, ids come from atomic counters, listeners sit in a copy-on-write list, and trades are immutable records.
- matching is in order by nature:
- price-time is a single queue
- locks per level: hard, and
- still one at a time
- one thread: no locks in the book,
- no races, cache friendly
- same input, same trades:
- replay from an order log
- scale: spread symbols over
- threads or machines
- book and orders: one thread
- per symbol, nothing shared
- accounts: shared by symbols,
- small synchronized methods
- one account lock at a time:
- no deadlock possible
- cancel: same queue as orders
- orders map: ConcurrentHashMap
- ids: AtomicLong
- listeners: CopyOnWriteArrayList
- trades: immutable records
Extensibility
Interviewers will stretch it. A stop-loss order does not sit in the visible book. It waits in a separate map keyed by its trigger price, and after each trade the engine checks whether the last price crossed it. If so, it becomes a market order on the same thread, which keeps everything in order. Immediate-or-cancel and fill-or-kill are rules about the remainder. Fees go to a fee account, so cash is still conserved.
- stop-loss: held off the book,
- keyed by trigger price; when
- last price crosses, it becomes
- a market order on that thread
- IOC, fill-or-kill: rules in
- accept() for the remainder
- fees: a fee account, so cash
- is still conserved
- self-trade check in match()
- cancel in O(1): id to node map
Testing
The full code is below the player. The demo builds an ask side, fills a limit buy across two sellers with a partial fill, sweeps three levels with a market buy, partly fills a resting bid with a market sell and cancels the rest. Three orders are rejected for missing cash or shares. Four client threads then trade two symbols at once, and the final check proves total cash and shares are unchanged and blocked amounts match the live orders.
buy 120 @ 101: 100 MAKER, 20 TRADER TRADER ask: PARTIALLY_FILLED 20/50 market buy 250: FILLED, avg 102.36 market sell 30: RETAIL bid 30/50 cancel bid: released 1,980.00 buy 100 @ 103: needs 10,300.00 MAKER sell 150: only 100 free 4 threads, 2 symbols: all settled total cash conserved: true shares conserved: true blocked matches live orders: true
Follow-ups
Expect follow-ups. Why not lock the book? It works, but matching is sequential anyway. What if one stock is very busy? Give that symbol its own core. What if the server crashes? Rebuild the books by replaying the order log. Why tree maps over two heaps? Levels are easy to find and remove for cancels and depth. How much to block for a market buy when you are only a broker? Use a price band above the last price.
- why not one lock on the book?
- correct, but no gain
- a hot stock is too busy?
- one core per hot symbol
- server crashes?
- replay the order log
- why TreeMap and not a heap?
- removing a level is easy
- how big a market buy block?
- sweep cost, or a price band
Say it like this
Here is the short version to say out loud. Accounts block cash or shares when an order is placed, so nothing is spent twice. Each stock has a book of tree maps with a queue per price. The engine matches best price first, then oldest, trades at the resting price, and settles both accounts. Each symbol has one matching thread, so the book needs no locks, and trades go out to observers.
- "Accounts block cash or shares
- when an order is placed. Each
- stock has a book of TreeMaps
- with FIFO queues per price.
- The engine matches best price
- then time, at the resting price,
- and settles both accounts. One
- thread per symbol; trades go
- out to observers."