6

I am working on design of a financial xchange system and especially the order-matching part.

I couldn't find a clear/complete design article especially for scalable/high available order-maching system. There lots of implementations which gives an idea about the system but none of the solutions are scalable and high available.

I want to give details about the problem and a possible solution. I want to ask whether such a solution work, applicable and you have any suggestions.

Let me start with the algoritm definition.

Order-matching algorithm

Although the algorithm has variations and will be possibly more complex in real world, it can be simply summarized as below. You have buyers and sellers in the system. Buyers creates buying orders while sellers creates selling orders in realtime. Order-matching algorithms duty is to match suitable selling orders with buying orders ( and vice versa ) again in real-time.

Assume that some traders enter the orders shown below. (Below 2 tables and explanation is taken from https://www.apress.com/gp/book/9781590595640 which is a great book. )

| Time  | Trader   | Buy/Sell | Quantity | Price                      |
|-------|----------|----------|----------|----------------------------|
| 10:01 | Anthony  | Buy      | 300      | $20                        |
| 10:05 | Anu      | Sell     | 300      | $20.10                     |
| 10:08 | Nicola   | Buy      | 200      | $20                        |
| 10:09 | Jason    | Sell     | 500      | $19.80                     |
| 10:10 | Jeff     | Sell     | 400      | $20.20                     |
| 10:15 | Nicholas | Buy      | 500      | Market Price Order ( MPO ) |
| 10:18 | Kumar    | Buy      | 300      | $20.10                     |
| 10:20 | Doe      | Sell     | 600      | $20                        |
| 10:29 | Sally    | Buyy     | 700      | $19.80                     |

The exchange will send an order acknowledgment to the traders’ trading terminals and fill the order book as below

|---------------------------------------------|---|-------------------------------------------|
|                 Buyer                       |   |                  Seller                   |
|---------------------------------------------|---|-------------------------------------------|
| Timestamp | Name     | Quantity | Buy Price |   | Sell Price | Quantity | Name  | Timestamp |
|-----------|----------|----------|-----------|---|------------|----------|-------|-----------|
| 10:15     | Nicholas | 500      | Market    |   | $19.80     | 500      | Jason | 10:09     |
| 10:18     | Kumar    | 300      | $20.10    |   | $20        | 600      | Doe   | 10:20     |
| 10:01     | Anthony  | 300      | $20       |   | $20.10     | 300      | Anu   | 10:05     |
| 10:08     | Nicola   | 200      | $20       |   | $20.20     | 400      | Jeff  | 10:10     |
| 10:29     | Sally    | 700      | $19.80    |   |            |          |       |           |
|-----------|----------|----------|-----------|---|------------|----------|-------|-----------|

If the traders in the previous table submit their orders, the market will match the orders as follows:

  • Nicholas’s buy order at market price will match Jason’s sellorder.This will result in the first trade, and both the orders will be removed from the order book.
  • Kumar’s order of 300 buy will get matched to Doe’s order of 600 sell. Interestingly, this order will get matched at $20.10 even though Doe wanted to sell at $20. Exchange systems are designed to protect the interests of both buyers and sellers. Since there was a passive order from Kumar willing to buy at $20.10 and Doe’s order comes in later asking only for $20, she will still get $20.10. Since Kumar’s order is completely filled, it will be removed completely from the order book. However, Doe’s order of 600 is only half-filled. So, 300 shares of Doe will remain in the order book.
  • In the next step, Anthony’s buy order of 300 shares will get fully filled by Doe’s balance of 300 at $20, and both orders will be removed from the order book.
  • Now Nicola wants to buy 200 at $20, but Jeff will sell only at $20.20. There is no agreement in price; hence, there will be no further matching, and the matching system will wait either for one of the parties to adjust the price or for a new order at a price where either a buy or a sell can be matched.

Questions, questions and questions

Trading platforms are living systems which means you have all the time selling orders and buying orders coming into system and prices are changes rapidly. Matching-algorithm should have very little latency because any latency may result in money loss for users.

( As I understood but not sure ) it is very hard ( if not impossible ) to implement matching algorithm in distributed manner. Where you have a google/pubsub and consumers listening on orders and doing their matching magic. Because (again) latency is a very hard requirement and putting extra queues may break it. Also sequentiality of orders is very important because all the algorithm based on this. Putting a distributed or concurrent matching logic possibly will break the sequentiality.

  • If a single-threaded solution is implemented how can these systems scale?
  • If a single-threaded and not distributed solution is implemented how can we ensure high availability?
  • Because latency is one of the most critical requirements when we should persist orders, or trades to db? All these operations are async?
  • Seems lmax-disruptor is a solution for solving latency problem within a single machine pushing limits of performance. If yes, how we can make it high available?

Possible Architecture

I am trying to put a solution at least working for some assumptions. Please comment on architecture and flow also.

 Seller/Buyer

          +
          |
          | 1 - place order
          |
          |
          |
    2     |
  +-------v-------+
  |               |      3      +--------------------+           6
  | Order Service +------------->   orders queue     +----------------------+
  |               |             +---------+----------+                      |
  +---------------+                       |                                 |
          |4                              |5                                |
          |                               |                                 |
     +----v-----+                         |                                 |
     |          |               +---------v----------+            +---------v----------+
     | Database |          7    |                    |   8        |                    |
     |          <---------------+  Trading Service   +------------>  Trading Service   |
     +----------+               |  (order+matching)  |            |  (order+matching)  |
                                |                    |            |   cold instance    |
                                |                    |            |                    |
                                +--------------------+            +--------------------+
  • Seller or buyer places order
  • Order service gets this order ( REST )
  • Order is put into queue for further processing
  • Order is saved into DB async
  • Order is fetched by trading-service. Trading service fills its own in-memory structure for order-matching. Order matching is continuosly works on data set.
  • Cold instance also fetches the same data from queue.
  • When trading service finds some matcing it send this matching to database Async.
  • In order to maintain cold instance up to date, matched orders are notified to cold instance also in async.

More and more questions

  • Is there any way to eliminate the latency originating from order-queue
  • Maintaning hot and cold Trading Service is a very hard job. A distributed cache like hazelcast can be used for distributed memory management but I think it would be slower than lmax disruptor. Is it right?
  • Is there any way to distribute lmax-disruptors on distrubuted machines?
7
  • What is a "Bec?" Jan 12, 2018 at 16:13
  • 3
    Low latency means they run into (silently ignored) buffer overrun errors, turning "because" into "bec" and "exchange" in "xchange". We're lucky enough OP didn't ask how to unit-test such a mess.
    – user44761
    Jan 12, 2018 at 16:22
  • 1
    "I couldn't find a clear/complete design article especially for scalable/high available order-maching system. There lots of implementations which gives an idea about the system but none of the solutions are scalable and high available." We obviously can't design and test a world-class architecture for you here in Q&A form. And we don't recommend tools or articles. So, how might you expect us to help?
    – Erik Eidt
    Jan 12, 2018 at 17:12
  • @ErikEidt I have questions in the post, if you want to answer you can; if not no one forces you. If you have any comments or directions it will help
    – ygk
    Jan 13, 2018 at 6:28
  • The table (and book) is wrong. Every exchange I know will execute the first trade at 10:09, at a price of $20.00. Athony buys 300 @ $20.00, Nicola buys 200 @ $20.00, and Jason sells 500 @ $20.00. At that point in time, there is no knowledge about the future order by Nicholas, so the trade possible at that time is executed.
    – Sjoerd
    Feb 11, 2018 at 18:25

1 Answer 1

2

Make a prototype.

Make a prototype.

Make a prototype!

Now test it. Does it fulfill your performance expectations? No? OK, make a new prototype, or modify the existing one. Lather, rinse, repeat.

While you're making your prototypes, enlist the help of your (or your lead's) design skills. Are you using sensible techniques? Are you using data structures having suitable performance characteristics? Is what your doing improving things?

Don't build it unless you need it. You mentioned the lMax Disruptor. That's a good possibility. If it works, you may not need some complicated distributed multithreading concurrency model.

There's nothing like the cold, hard reality of pragmatism and the writing of actual working code to shine the light of day on a project and get it moving forward towards a successful outcome.

Architecture isn't going to solve your problem. Code will. Architecture is just a way to provide maintainability and organization.

3
  • thank you @Robert . at least I understood disruptor is a possibility
    – ygk
    Jan 13, 2018 at 6:30
  • 1
    @ygk the key in this answer is not whether disruptor is a possiblity or not. It's just an starting point :-). A good one maybe.
    – Laiv
    Feb 11, 2018 at 18:50
  • @Laiv: A fairly promising one if a financial services company already uses it in Java to do automated trading with a throughput of a million transactions per second. Feb 11, 2018 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.