Years ago a friend and I tried starting a start-up, called Gimmeview, which warrants its own blog post, needless to say it didn’t workout :P Without going into details it involved trading subscriptions in real-time. I originally had developed the trading algorithm with C# and SQL with terribly inefficient Entity Framework code that had multiple round trips, lots of JOIN clauses, which all of that was in a nice 500+ line method block. Sounds beautiful doesn’t it?
Even though the Gimmeview didn’t fly, I still find bid and ask algorithms interesting. So I thought I’d share a simple solution to match users that want to exchange assets (we dealt with subscriptions specifically as you’ll see in the code).
Lets get to it. As you can see 3 main classes:
Limit - represents a certain price point
Order - represents the number of shares a user would like to buy or sell
Subscription - the amount of owned shares for a user
We need to store a collection of Limits objects in a data structure that is sorted. Wheather it's ascending or descending doesn’t matter but lets sort by ascending order for this example. When a bid is requested, a buyer wants the lowest price in the market and since the collection is sorted in ascending order, we can always start at the beginning of the collection. When the Limit has been selected we then can iterate through the Orders to start the filling process. Hopefully you’re still following along but here’s a diagram of the relationships between classes:
There is a couple interesting properties of this object graph. The Orders (bids and asks) is a doubly-linked list where each order has a reference back to the parent limit price the order has been made at. The operations we’re going to support are: Bid, Ask, Add Subscription and Cancel. Here’s the model classes:
We are going to use the models within an OrderBook class which will represent a single asset (a.k.a Subscription). You can think of this like a single stock ticker like MSFT. Having multiple subscription types would just be a list of OrderBook’s.
I’ve used a RankedSet<T> because I needed to have the prices sorted but also need to do look-ups but also be able to iterate through each price as you will see later on. I decided to use the KaosCollections NuGet package to get around this. Using a Dictionary<T> is good for look-ups but isn’t ideal for iterations. The Subscriptions Dictionary is for looking up a users’ subscription to validate they have the amount of owned shares when they place an Ask order and the Orders Dictionary is for cancellations.
I originally had the the Limit.Price be of type decimal but saw a significance performance increase when changing the type to a long and used my own decimal place scale factor. For now I’m OK with supporting down to 4 decimal places for prices. Any interactions with a price must either multiply or divide the price by the ScaleFactor depending on if it’s outputting or receive input from outside the OrderBook class.
Alright, on to the methods. Lets start with the easiest first: AddSubscription().
That’s self explanatory so the next method is Cancel().
When cancelling an order we need to re-linked the previous and next nodes in the linked-list and make sure the head of the list is intact.
Now to the meat of it all. Bid().
As you can see we need some basic up front validation followed by making sure we scale the price. I use a lock in the class to make sure everything is consistent. Maybe I’ll explore doing something lock-free some other time but nothing came to mind so I left it for now. Moving on, we need to loop through the Limits until we reach the end or the bidders shares they’ve request have not been filled. If we start at the front of the Limits and the price is over then there’s no matching asks for the bidder.
For the actual filling of the orders and transfer of subscription shares that looks like:
We need to make sure when we run into an order that’s the current bidders order we have to skip it. Also, I didn’t want to incur the performance cost of removing an Order if all the asking request shares are filled, so I just set it to 0 and move on. This has the potential for wasted memory but I’m OK with that for now. If that same user placed another ask order that same order would be changed. If all of the asks where filled from the current bid under a certain price we need to iterate to the next price provided it’s still under the bidders limit price.
Now that both sides have been filled, weather partially or in full we can now take care of the current bidders subscription and order if any shares are remaining to be filled.
A Subscription is added if the current bidder doesn’t have one. Using some basic calculations we changed the owned shares based off what was filled but since there was shares left over we need to add a new Order with the remaining shares and augment the linked-list at the price point of the original bid.
For the Ask() it’s almost exactly the same as Bid() but requires extra validation to make sure the requester actually owns the subscription.
When executing as ask we need to reverse the calculation when transferring owned subscription shares that we had in the Bid() method.
You can view the full project with unit tests in the Subtrader GitHub repository.
