In our example, if Fred didn't look at the book and decides to put in a buy for $10.05, he'll get his 10 shares at $10.05 and Pete would make out like a bandit and the price would briefly shoot up to $10.05.
There is no market in the world that I know of that works that way. In the real world if you submit a marketable buy order (limit price > best offered price) the match will happen at the best offered price which is $10.00 in your example. If it clears out all the shares available at that price level it will continue to match at the next best price until the order is fully matched or the matching sweeps up to the order limit price.
Limit orders are the fundemental building block of a market. There are other order types but they're always built using one or more limit orders.
This is not technically true either. A market order by definition has no limit price.
I'm glad to see this article on HN. For you next step you might think about how you can make money by placing orders on both sides of the market (making a market).
> In the real world if you submit a marketable buy order (limit price > best offered price) the match will happen at the best offered price which is $10.00 in your example. If it clears out all the shares available at that price level it will continue to match at the next best price until the order is fully matched or the matching sweeps up to the order limit price.
Thanks, this makes a lot more sense. I'll fix the article.
> This is not technically true either. A market order by definition has no limit price.
I figured that a market order was implemented as a limit order with a bid over the ask, but it makes sense that real world markets would have a special case order type for it.
Limit order books need to need to be very very quick as they usually live in exchanges and process a lot of orders. I've written a few limit order books, I found it difficult to beat this approach.
Deal with prices as an int not a float. This important as the price can then form the key of a hash table. Size of the hash table should be the limits of price in your book (including decimal places you support). This seems like a lot of memory, however the structures we're dealing with are small. Insertion into the book is then largely O(1) as few people bid/offers are exactly the same price.
Bid and offer can share the same hash table as they will be at opposite ends of the table (apart from orders that cross).
We can preallocate all active orders and form a link list of nodes inside the order book. Never allocate any memory on the fly as it is very expensive.
Order
{
Order *next;
int price;
int size;
int side;
}
This will allow fast insertion/removal and will keep a lot of the data in the level 2 cache. Of course you need to keep the list big enough to support all active orders.
Processing an order would involve working out if it's a buy or sell, then hashing the price, if a value exists at that key you fill the order (or partial fill).
Finally use taskset or something similar to make sure the OS puts your process on a dedicated hardware thread.
> Insertion into the book is then largely O(1) as few people bid/offers are exactly the same price.
This is very much not true in my experience. Automated trades of any sort often hit the same prices, and trading strategies such as Iceberg which put many, many small orders will nearly always overrun with existing orders.
Which markets were you building this order book for?
I am curious about how you deal with matches that are not exact?
> if a value exists at that key you fill the order (or partial fill)
If there is an existing sell for 100 and a buy comes in for 101 your hash will miss the 100 entry, do you need to do a scan down the array looking for potential matches?
You're not going to be able to get away from traversing the order book for every match. Another subtle differentiating factor is the time at which the potential matches entered the order book. Obviously priority is always given to price (better price always taken first) but assuming 2 potential orders came into the book for the same price, the one that got there first will be matched.
Another thing to think about is that some firms also don't always want price improvement for an asset. Typically these firms are custodians of other peoples assets and need to trade with equal and offsetting amounts between multiple accounts. If they get price improvement then they end up buying or selling a different quantity which then leaves them responsible for explaining the difference. A lot of times it's just more trouble than its worth.
You can definitely get away with traversals - and they are often required. The simplest method would be to use a sorted list. The head of the list is always the best price, so comparing the best bid against the best offer is linear and can be performed every time the orders are modified. Order insertion is naively O(log n) as the list is sorted, but this can be optimized by keeping a journal of orders and only immediately inserting orders close to the best price. You can then insert from the journal into the order book as time allows or if the best price moves a large enough amount.
There are a lot of other techniques too, but you definitely can't just let people buy or sell a different quantity. At least on any formal market I know of?
I'm thinking about FX where I work. If the price you get executed at is better than what you wanted your term currency amount changes. Often times what ends up happening is that some someone upstream (e.g. broker) ends up keeping the improvement.
Cool, this sounds like a fast approach. The implementation I wrote is very much not optimized at all. I wanted it to be correct-ish and easy to understand.
Though less helpful if you're trying to simulate an actual market rather than building a new one, another approach to designing a trading market is to use market scoring rules, which can be somewhat simpler conceptually (as least as far as the code goes):
Would love to read about the process, mistakes made and overall architecture of building a stock exchange. If you guys are willing to share, that'd be awesome.
First time I've heard of Readme Driven Development, is this a thing?
I always lambast myself for continually rewriting the Readme as I go. Part of me sees it as a time drain, or at the very least an admission I've not done sufficient high level strategising upfront.
One of my software engineering professors told how back in the 70s when he was promoted into management, he had his teams write a user manual before starting on coding. He said it brought up all the important fuzzy-requirement problems much earlier in the process, for much lower cost.
Plus, you ensured that there was a manual written. That might not happen otherwise, or it might be done in a rush because of the next project.
It was a different time, but I always found it to be an interesting anecdote.
it seems like MinHeap and MaxHead from the algorithms gem would do the same thing as your red-black tree and are built to hold ascending and descending keys
That would work but a heap isn't a totally ordered data structure so if we were to display the order book it may look weird with things slightly out of place. An RB tree guarantees the order.
There is no market in the world that I know of that works that way. In the real world if you submit a marketable buy order (limit price > best offered price) the match will happen at the best offered price which is $10.00 in your example. If it clears out all the shares available at that price level it will continue to match at the next best price until the order is fully matched or the matching sweeps up to the order limit price.
Limit orders are the fundemental building block of a market. There are other order types but they're always built using one or more limit orders.
This is not technically true either. A market order by definition has no limit price.
I'm glad to see this article on HN. For you next step you might think about how you can make money by placing orders on both sides of the market (making a market).