This project implements an elementary version of a matching engine in a stock market exchange. It uses data structures and algorithms to describe an efficient system that handles asynchronous BUY and SELL requests from buyers and sellers for a pool of financial instruments (equity in this case). The system fills the requests or keeps them pending as per the availability, and keeps track of all transactions and their timestamp in the order book.

NOTICE: The matching engine code is in WindowsOS_code/Exchange.cpp (implementation) and WindowsOS_code/Exchange.hpp (definition) files. The rest of the system components are supporting functionality for the engine to be implemented as realistic as possible.

The system consists of several components, shown below, and its purpose is to emulate an elementary and naive version of a Stock Exchange, with main focus on the matching engine, which handles new incoming trade requests.

To achieve high performance, most system components are purely built in native C++ using C-style data types and structures. Although STL is very efficient and compiler optimized, my implementation of the described hybrid data structures mimics the STL equivalent. Another reason for choosing native C++ is customization and elimination of redundant-for-the-underlying-system functionality that STL provides. As a result, the implementation below can safely be considered as a low level solution -- which is confirmed by the stress testing demo.

Briefly, the system components include:

1. Request interface: handles the information of a trade request i.e. price, quantity, side, etc.

2. Trader interface: handles a trader account, the current cash position, the trader's id, etc.

3. TradeHeap interface: handles trader requests to the stock exchange by storing the trader and request info in a max heap, sorted as per the price and seniority of a request

4. Exchange interface: handles asynchronous trader requests for multiple stocks and runs the matching engine parallely to execute these requests, to log them in the order and fill books, to update each trader's account etc.

As seen below, the current implementation with limited RAM and CPU power can handled a relatively high volume (2000 requests and 2000 and executions) relatively fast -- in less than 1.5 second. This was achieved by two thread pools of "BUY" and "SELL" side Trader and Request object tuples, as described in the code files. The screenshot below can be found in img/StressTesting.jpg and was generated by DEMO2.cpp file in WindowsOS_code directory.

Additionally, the results of an typical trading example look accurate -- as per the following screenshots. This was achieved by hard-coding trading examples with simple values and confirming results manually. The screenshot below can be found in img/Test1.jpg and img/Test2.jpg and were both generated by DEMO1.cpp file in WindowsOS_code directory.

1. Request interface: instantiates Requests in O(1)

2. Trader interface: instantiates Traders in O(1)

3. TradeHeap interface: in-sort insertion of trades in O(lg n) average time and O(n) worst case. Extracts max trades in O(1)

4. Exchange interface: submits requests in 0(1) and in O(lg n) if we further check existence of stock. Executes in O(1) but the matching engine is implemented with a linear check. This can be avoided with further multithreading techniques i.e. multiple worker-type egnines.

The Request hierarchy models a basic SELL/BUY request from a trader. It encapsulates basic parameters such as the financial instrument (equity) name, the quantity and price of the trade, the trade side (BUY side or SELL side), and the timestamp of the initiated transaction trade.

The base class implements a basic access interface to these parameters (getters) and a convenient getData() method that returns a tuple with all these parameters. It also provides a pure virtual (abstract) method to be implemented in the derived classes. One of the reasons for making the Request base class abstract is that we don't want the trader (user) to instantiate it, since there are currently two different options for initializing a trade request: an automated option and a manual one.

The automated request object basically uses one parameter constructor to get the trade input upon construction -- which input could be coming from another software component that determines each trade. This would work for algorithmic trading where these processes are all automated and different components instantiate trade requests automatically.

The manual request object is for traders who manually want to specify the trade parameters. Thus upon construction of a manual trade, the trader (user) can interactively select the trade parameters via the init() method of the ManualRequest class. Notice that since there is internal heap allocation and memory handling, it won't be wise to write init()'s code inside of the constructor cause we want to be able to handle bad input and other run time errors without risking a crash or memory leak. That being said, init() only serves as a safe interactive interface for the user, thus we keep it private.

Finally, notice that the copy constructor and assignment operator of the entire Request hierarchy are set to be private. The prevents any Request instance to be accidentally or intentionally copied in the exchange. All submitted requests must be unique.

The Trader class is much simpler than the Request class. We implement some basic attributes of a trader (id, trading eligibility, etc.) and we are solely focusing on the cash position of the trader. The Trader class additionally provides a buy() and a sell() method to be used for the transactions -- which directly affect the current cash position of the trader. Moreover, auxiliary methods are implemented to give a more realistic sense of a general Trader object, but also for extendability demonstration reasons.

For simplicity reasons we are making three major assumptions for the Trader object. These assumptions can be eliminated once further system details are provided.

1. We do not check whether or not a trader has a certain stock he/she wants to sell. The restriction is that you cannot sell more than your current cash value V.

2. If a Trader can no longer trade at some point i.e. V < lower_bound, then all remaining BUY/SELL requests are removed from the exchange

3. Every trader starts with a random amount between $500,000 - $1,000,000

Again, keep in mind that the objective of this system is to emulate a matching machine in an exchange, thus we don't want to over-engineer supporting system components and overfit the underlying problem.

Last but not least, notice that the copy constructor and assignment operator are set to be private. This ensures that no copies of a Trader object will be created anywhere in the program on runtime. This enhances security in the system cause we don't want replications of any trader account at all times. Every trader must be unique.

The TradeHeap data structure implements a priority queue using a dynamic C-style primitive array and overloading the key functionality of a priority queue. This structure is an alternative implementation of STL's std::priority_queue. The reason that it is build in native C++ instead is for demonstration reasons and further customization.

The type of the priority queue TradeHeap -- which is a max heap, is the TradeNode data structure which models a trade request, namely the Request, the Trader, and the submission id timestamp i.e. the exact time a trade is submitted in the exchange. This timestamp is different from the timestamp of the Request creation.

The push() and pop() methods are inserting trades (TradeNode objects) in the heap in-order, defined as "the highest trade price is of higher priority. If two prices are the same, then an earlier trade has priority".

This data structure will be used by the matching engine which will querry the top elements of two trade queues, namely a BUY trading queue and a SELL trading queue. As a result, this data structure provides a constant time access interface (the pop() method) that contains all the necessary information for the matching engine.

This class encapsulates a naive version of a Stock Exchange. One can submit trading requests to the Stock Exchange, and its the responsibility of the Exchange's matching engine to handle all requests and execute those which are possible. As a result, the matching engine is ignited upon opening of the Stock Exchange and continuously runs in the background until the Stock Exchange closes for the day.

All remaining requests that are not executed remain in the database (in our case are discarded). Due to the high volume of requests in an exchange, we need to protect the submit method from two or more brokers (threads) trying to submit at the same time to the exchange.

Sequential submission is required, thus we are using STL's mutual exclusion mechanisms and condition variables. Additionally, all the matching engine methods are encapsulated (declared private) as its only the Exchange's responsibility to execute requests. In a case of a dark pool, that might not hold.

1. Not everything is parallelized.

2. The hash function in the Exchange is hard-coded and works for certain stocks only. The issue is that a good hash function is still an open problem in research and since is a secondary feature of the application, for the sake of the demo I decided to assume naive hashing.

3. Not all components support multithreading right now. We can easily add mutex mechanisms everywhere, but currently there is some unecessary overhead due to lack of parallelization.

4. The current code files work error-free in WindowsOS and with compilers that support C++11. Modifications needed to successfully build in Linux/UNIX OS

5. The execution of trades is inaccurate and based on false assumptions. For simplicity reasons when there is price mismatch between the BUY side and SELL side traders, the current implementation for demo purposes performs the trade to an average price anyway. This is easy to fix but further details and trading definitions are needed.

6. Under no circumstances this is production level code. Although the implementation is as safe as possible and although all obvious vulnerabilities are properly handled by the system components, there are still security and performance issues. This project is for demo only and emulates a Stock Exchange -- it doesn't implement it.

1. Visual Studio 2015 or newer and CodeBlocks

• Create a new project and include all code files with a single test file (or all test files but with only on included in the build)
• Build with a single test file at the time

You can get Visual Studio Community version for free here: https://www.visualstudio.com/downloads/

You can get CodeBlocks and installation instructions here: https://www.ntu.edu.sg/home/ehchua/programming/howto/CodeBlocks_HowTo.html

2. Windows command line

Instructions can be found here: https://www.youtube.com/watch?v=SvEPC3d85ZA