High-Frequency Trading Order Matching System

Overview

This C++ program simulates a high-frequency trading (HFT) order matching system. It processes buy and sell orders, matches them based on price and timestamp priority, and records executed trades. The system uses multi-threading to simulate fast order placements and order matching.

Code Flow

1. Order Structure (struct Order)

   • Represents a buy or sell order.
   • Includes attributes such as order_id, price, quantity, company, and timestamp.
   • Implements a comparator for priority-based ordering.

2. Data Structures Used:

   • std::priority_queue<Order> for buy orders (max-heap by price, earliest timestamp priority for tie-breaking).
   • std::priority_queue<Order, std::vector<Order>, OrderComparator> for sell orders (min-heap by price, earliest timestamp priority for tie-breaking).
   • std::unordered_map<double, std::unordered_map<int, Order>> for efficient order book storage and retrieval.
   • std::vector<Order> for maintaining trade history.

3. Order Placement (place_order)

   • Acquires a lock to ensure thread safety.
   • Stores the order in the order book (unordered_map).
   • Pushes the order into the appropriate priority queue (buy or sell).

4. Order Matching (match_orders)

   • Acquires a lock to ensure safe access.
   • Matches the highest buy order with the lowest sell order if the buy price is greater than or equal to the sell price.
   • Executes a transaction and updates the order book.
   • If an order is only partially matched, the remaining portion is pushed back into the priority queue.

5. High-Frequency Trading Simulation (simulate_hft)

   • Randomly generates buy and sell orders at high speed.
   • Uses multi-threading to continuously generate and match orders.

6. Main Function (main)

   • Starts the HFT simulation in a separate thread.
   • Periodically prints the size of the trade history.

---

gRPC Integration and Proto Usage

Why Use Proto?

• Serialization: Ensures efficient message transmission between the client and server.
• Cross-Language Support: Allows seamless communication between C++ and Python.
• Scalability: Enables easy expansion of message structures without breaking compatibility.

Setting Up gRPC

Generating C++ Proto Files

protoc --cpp_out=. --grpc_out=. --plugin=protoc-gen-grpc=`which grpc_cpp_plugin` trading.proto

Compiling the gRPC Server

g++ -std=c++17 trading.cpp trading_server.cpp trading.grpc.pb.cc trading.pb.cc \
    -I. -I/usr/local/include -lgrpc++ -lprotobuf -pthread -o trading_server

Generating Python gRPC Files

Ensure you have grpcio-tools installed:

pip install grpcio grpcio-tools

Then run:

python -m grpc_tools.protoc -I. --python_out=. --grpc_python_out=. trading.proto

This will generate trading_pb2.py and trading_pb2_grpc.py, which are required for the Python gRPC client.

---

Time Complexities of STL Operations

Operation	Data Structure	Complexity
Insert Order	std::priority_queue (buy/sell queue)	O(log N)
Remove Top Order	std::priority_queue	O(log N)
Lookup Order	std::unordered_map	O(1) (average)
Remove Order	std::unordered_map	O(1) (average)
Order Matching	Priority Queue Processing	O(log N) per match
Storing Trade History	std::vector	O(1) append

---

Design Choices and Justifications

1. Priority Queue for Buy & Sell Orders

   • Why? Orders need to be prioritized based on price and timestamp.
   • Alternative? A sorted set (std::set<Order>) could have been used, but std::priority_queue provides more efficient top-order access.

2. Unordered Map for Order Book

   • Why? Provides O(1) average-time complexity for order insertion, lookup, and deletion.
   • Alternative? std::map (RB-tree) offers O(log N) lookup but is slower compared to unordered_map.

3. Vector for Trade History

   • Why? Appending completed trades is O(1), and we don't frequently remove or search trades.
   • Alternative? A linked list would add unnecessary overhead.

4. Mutex for Thread Safety

   • Why? Prevents race conditions when multiple threads access shared data structures.
   • Alternative? std::shared_mutex for read-write separation, but a single mutex suffices for this case.

---