A Simple CDA Implementation in Clojure

28 Feb 2016 in Software Last modified at: 2020-07-24

This post describes a minimal Continuous Double Auction algorithm and provides an implementation in Clojure.

I’ve just dug up some code I’ve written a couple of months ago. I basically wanted to implement a CDA algorithm, as used in most stock exchanges, in order to better understand the mechanism.

Note that this algorithm deals with limit orders only and is only concerned with maintaining a consistent state of the bid and ask queues, not performing or keeping a log of the transactions.

Inception

I’ve rewritten it a couple of times, mostly focusing around the idea of having to two different routines for buy and sell orders. The idea was to check if the order could be matched before adding it to any queue. This lead to a lot of conditionals (that I later tried to get rid of using protocols).

Eventually I realized that it could be done with a single routine, by just adding new orders to the front of either queue and have a separate routine that resolves the new, potentially invalid state of the system.

This routine doesn’t care if the new order was a buy or sell order, all it sees is an invalid state that needs to be resolved by matching orders until it is valid again. I find this approach much more elegant.

The algorithm basically does this:

1. Check if a trade is possible.
   1. No? Return queues as is.
   2. Yes? Create a “diffed” order from the orders at the front of each queue (more about that later).
   3. Is the diffed order zero, i.e. did the orders match perfectly?
      1. Yes? Return the queues.
      2. No? Add the diffed order to the queues and start over.

Implementation

Expressed in Clojure, modeling the queues as a vector of 2 (sorted) lists:

(defn place-order
  "Place a limit order using Continuous Double Auction."
  [order queues]
  (loop [[bids asks :as queues] (add-to-queues order queues)] ;;!! (1)
    (let [[first-bid] bids
          [first-ask] asks]
      (if (not (trade-possible? first-bid first-ask))  ;;!! (2)
        queues
        (let [rest-queues  [(rest bids) (rest asks)]
              diffed-order (diff-order first-bid first-ask)] ;;!! (3)
          (if (nil? diffed-order)
            rest-queues
            (recur (add-to-front diffed-order rest-queues)))))))) ;;!! (4)

As you can see it maps pretty nicely to the abstract description of the algorithm.

(1)

Let’s take a look at add-to-queues. It uses a helper function insert-by, which inserts elements into a list maintaining an ordering. It’s basically insert from insertion sort. It could be replaced with something more performant.

The queues are sorted by price, but in different order. We want quick access to the highest bid and the lowest ask, so these go to the front of their respective list.

(defn insert-by [f c e]
  (let [[lt gt] (split-with #(f % e) c)]
    (concat lt [e] gt)))

(defn add-to-queues
  "Inserts an order into the matching queue, sorted by its price
   and returns a new pair of queues."
  [{:keys [quantity] :as order} [bids asks :as queues]]
  (cond
    (> quantity 0) [(insert-by #(> (:price %1) (:price %2)) bids order)
                    asks]
    (< quantity 0) [bids
                    (insert-by #(< (:price %1) (:price %2)) asks order)]
    :else queues))

(2)

trade-possible? is straight-forward, though it is important to deal with empty queues, i.e. when either bid or ask is nil.

(defn trade-possible?
  "Checks if a trade is possible based on the prices of two orders.
   The bid price has to be higher than or equal to the ask price."
  [bid ask]
  (and
    (some? bid)
    (some? ask)
    (>= (:price bid) (:price ask))))

(3)

“Diffing” the orders is probably the core idea behind this algorithm. diff-order takes two orders and returns a new order, which retains the price of the larger one, but is reduced by the quantity of the smaller one. In finance mumbo, it’s partially filling one order using the other.

By modeling sell orders with a negative quantity, we can simply add the two quantities together:

(defn diff-order
  "Returns the 'difference' between two orders."
  [bid ask]
  ; using the fact that asks are modeled w/ a negative quantity:
  (let [diff (+ (:quantity bid) (:quantity ask))]
    (cond
      (> diff 0) (assoc bid :quantity diff)
      (< diff 0) (assoc ask :quantity diff)
      :else nil)))

(4)

At this point we’ve reached a valid state of the system again (assuming it was valid before the new order came in) but we also have a “new” order, the one returned by diff-order.

This is almost exactly the condition that we’ve started with, so we can recur. The difference is that we know that the diffed-order goes to the front of either queue, because that’s where it came from.

(defn- add-to-front
  "Adds a new order to the front of the appropriate queue."
  [order [bids asks :as queues]]
  (cond
    (> (:quantity order) 0) [(cons order bids) asks]
    (< (:quantity order) 0) [bids (cons order asks)]
    :else queues))

You can find the full code including basic tests in this gist.