Skip to content

Hashiru trading engine - The core matching algorithm of the exchange

Notifications You must be signed in to change notification settings

hashiruhq/engine

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Trading Engine

Stop implementation

Any order that is received by the engine can have a stop flag set along with a stop price. These flags control when the order will be added in the orderbook with the type set at creation: Market or Limit.

The StopPrice is required for any Stop order.

There are three types of Stop orders:

  • None: which means that the order is not a stop order and the it should be processed imediatelly
  • Loss: which means that the order triggers when the last trade price changes to a value at or below the StopPrice
  • Entry: which means that the order triggers when the last trade price changes to a value at or above the StopPrice

Stop orders will only be activated by the next trade. When it's added no checks will be done based on the previous last trade price.

The processing flow for stop orders is as follows:

  1. When an order that has the stop flag and price set the order is added to an ordered list based on the flag.
  2. When a new batch of trades is generated the system will check if the last price can activate any stop order.
  3. If it can then the found orders are removed from the pending list.
  4. Every stop order activated is added in the system as limit/market order in the correct side of the market.
  5. For every activated order an event with order activated is generated by the engine.
  6. The order is then processed normally by the engine and can generate trades.

Development Notes

Generate protobuf classes

# download protoc C++ binaries for mac from https://github.com/protocolbuffers/protobuf/releases
# install protoc for golang
go get github.com/golang/protobuf/protoc-gen-go

# regenerate the golang classes based on the proto model
~/tools/protoc/bin/protoc -I=./model --go_out=./model ./model/market.proto
~/tools/protoc/bin/protoc -I=./model --go_out=./model ./model/order.proto
~/tools/protoc/bin/protoc -I=./model --go_out=./model ./model/trade.proto
~/tools/protoc/bin/protoc -I=./model --go_out=./model ./model/event.proto

Testing

# local benchmarks using data loaded from a file
go test -bench=^BenchmarkWithRandomData -run=^$ -timeout 10s -benchmem -cpu 8 -cpuprofile cpu.prof -memprofile mem.prof -gcflags="-m" ./benchmarks --gen
go-torch benchmarks.test cpu.prof
# local benckmarks using data from Apache Kafka
go test -bench=^BenchmarkKafkaConsumer -run=^$ -timeout 10s -benchmem -cpu 8 -cpuprofile cpu.prof -memprofile mem.prof -gcflags="-m" ./benchmarks --gen
# if the sample data was already generated remove the --gen flag from the commands above

Create flame chart out of active server

go-torch -u http://127.0.0.1:6060

Start GoConvey

govendor install
goconvey .

How to build a trading engine

In this section I will try to document step by step how to build a trading engine in Golang from scratch.

Orders

Every trading engine needs to listen for orders from some sort of external system. This can be a web socket, a queue system, a database, etc. The point is that we need a way to encapsulate each type of order received.

The trading engine will therefore keep a list of trade orders and match incomming orders against that list based on the type of order that is received.

For example if there is an unprocessed buy order of 200 for 0.41 and an incomming order of sell for 100 for 0.40 then the incomming order is satisfied on the spot, the buy order is decreased by 100 and a buy signal is triggerred.

Such an order may look like the following data structure:

{
  action: 0, // 0=sell, 1=buy, 2=cancel-sell, 3=cancel-buy
  category: 0, // 0=market, 1=limit, 2=stop-loss, 3=... // see https://www.investopedia.com/university/intro-to-order-types/ for other possible types
  price: 100,
  amount: 124,
  id: 51987123,
}

Engine

The engine will maintain two lists of orders. Buy orders and Sell orders. It should then listen for new orders and try to satisfy them against these lists.

The engine should support the following actions:

  • Done: Fill a new buy/sell order or add it to the list if it can't be filled yet
  • Cancel an existing order and remove it from the lists
  • Listen for new incomming commands/orders
  • Send every trade made to an external system
  • Handle over 1.000.000 trades/second
  • Done: 100% test converage
  • Fully tested with historical data

Benchmarks

Process orders rates

This bechmark checks the performance of executing orders after they are available in memory.

// Old benchmarks

Total Orders: 1000000
Total Trades: 996903
Orders/second: 667924.145191
Trades/second: 665855.584113
Pending Buy: 2838
Lowest Ask: 9940629
Pending Sell: 2838
Highest Bid: 7007361
Duration (seconds): 1.497176

1000000	      1497 ns/op	     642 B/op	       6 allocs/op

// New Benchmarks without decoding/encoding orders/trades
Total Orders: 100
Orders/second: 980392.156863
Pending Buy: 18
Lowest Ask: 999705600000000
Pending Sell: 10
Highest Bid: 999622700000000
Duration (seconds): 0.000102

Total Orders: 10000
Orders/second: 1511944.360448
Pending Buy: 591
Lowest Ask: 996920900000000
Pending Sell: 662
Highest Bid: 996859500000000
Duration (seconds): 0.006614

Total Orders: 1000000
Orders/second: 1160515.547427
Pending Buy: 2244
Lowest Ask: 996670000000000
Pending Sell: 1038
Highest Bid: 700948400000000
Duration (seconds): 0.861686

Total Orders: 2000000
Orders/second: 1058599.293173
Pending Buy: 4207
Lowest Ask: 994008100000000
Pending Sell: 1350
Highest Bid: 402202500000000
Duration (seconds): 1.889289

 2000000	       944 ns/op	     505 B/op	       3 allocs/op

// New Benchmarks with decoding/encoding orders/trades

Total Orders: 100
Orders/second: 735294.117647
Pending Buy: 18
Lowest Ask: 999705600000000
Pending Sell: 10
Highest Bid: 999622700000000
Duration (seconds): 0.000136

Total Orders: 10000
Orders/second: 831393.415364
Pending Buy: 591
Lowest Ask: 996920900000000
Pending Sell: 662
Highest Bid: 996859500000000
Duration (seconds): 0.012028

Total Orders: 1000000
Orders/second: 600300.990917
Pending Buy: 2244
Lowest Ask: 996670000000000
Pending Sell: 1038
Highest Bid: 700948400000000
Duration (seconds): 1.665831

 1000000	      1665 ns/op	     698 B/op	       7 allocs/op

Consumer and Producer

The following benchmark refers to consuming orders from a Kafka server, processing them by the trading engine and saving generated trades back to the Kafka server.

Total Orders: 300000
Total Trades Generated: 295126
Orders/second: 248929.396155
Trades Generated/second: 244885.123232
Pending Buy: 3970
Lowest Ask: 3967957
Pending Sell: 3970
Highest Bid: 3706215
Duration (seconds): 1.205161

 300000          4043 ns/op       2437 B/op       22 allocs/op

Further optimizations

  • Add support for FIX formats
  • Optimize Kafka Producer rate
  • Use the golang profiler to see where the bottlenecks are in the code
  • Write to multiple partitions at once when generating trades
  • Optimize allocations with buffers bytes (see minute 23 of the video): https://www.youtube.com/watch?v=ZuQcbqYK0BY

Resources

Architecture Design

Trading Engine

Golang Docs

Communication

Performance

Performance: To Read

Algorithms

Liquidity

Testing References

Benchmarking

Testing

About

Hashiru trading engine - The core matching algorithm of the exchange

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages