tome

package module
v0.0.0-...-d3d81c4 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 21, 2021 License: MIT Imports: 9 Imported by: 1

README

Toy Order Matching Engine - TOME

TOME matches incoming buy/sell orders to create trades. It follows usual financial market order types, parameters and market behaviour.

CLI

As an example of the matching algorithm I've implemented a CLI that operates the order book.

go run ./examples/cli/ for an interactive playground (enter your orders) , cat examples/cli/example.txt | go run ./examples/cli for a predetermined example.

Instructions follow the following expression syntax:

  • buy or sell
    • <buy/sell> <number of shares> <market/limit> [if limit enter the limit price] [parameters, if stop then next parameter has to be the stop price, if GTD next param has to be the date]
  • print settings - settings
  • print books - print
  • change settings - set <setting> [subsetting...] <yes/no/y/n/true/false/t/f>|value
    • update setting according to its rules, currently supported are:
      1. set print <always/never/trade> - always print books, never print books or print books only when a trade occurs
      2. set clear <yes/no/y/n/true/false/t/f> - clear output on every instructio
      3. set prompt <yes/no/y/n/true/false/t/f> - prompt "enter instruction:" before each instruction
      4. set print instructions <yes/no/y/n/true/false/t/f> - print parsed instructions after each instruction
      5. set print comments <yes/no/y/n/true/false/t/f> - print comments?

Parameters are case insensitive. Comments start with # and are supported.

Examples:

  • buy 20 market gtc stop 25 ioc - buy 20 shares at market price, parameters are GTC (good till cancelled), stop price at 25 and IOC (immediately or cancel)
  • sell 50 limit 24 - sell 50 shares at limit price 24
  • buy 40 market - buy 40 shares at market price
  • sell 20 limit 23.56 stop 24 GFD - sell 20 shares at limit price 23.56, set stop price at 24 + GTD (good for the day)
  • buy 10 limit 26 FOK - buy 10 shares at limit 26 + FOK (fill or kill)
  • settings - print out current settings
  • print - print out the current state of the books

An example is provided at the end of the document and in examples/cli/example.txt.

Currently supported

  • order types
    • market order - execute an order as fast as possible, cross the spread
    • limit order - execute an order with a limit on bid/ask price (e.g. $x or less for a bid, or $y or more for an ask)
  • order params
    • STOP - stop order, set a stop price which will activate the order once the market price crosses it
    • AON - all or nothing, don't allow partial fills
    • IOC - immediate or cancel, immediately fill what's possible, cancel the rest
    • FOK - AON+IOC, immediately match an order in full (without partial fills) or cancel it

TODO

  • stop orders
  • GFD, GTC, GTD parameters
  • logic surrounding the order book - trading hours, pre/after market restrictions
  • basic middle & back office functionalities - risk assessment, limits
  • TCP/UDP server that accepts orders
  • reporting market volume, share price
  • reporting acknowledgments & updates to clients (share price, displayed/hidden orders...)

Market behaviour

Market orders are always given priority above all other orders, then sorted according to time of arrival.

  • orders are FIFO based
    • bids - price (descending), time (ascending)
    • asks - price (ascending), time (ascending)
    • quantity does not matter in sorting
  • market price is set at the last trade price
  • stop bids are activated once the market price is above or equal the stop price
  • stop asks are activated once the market price is below or equal the stop price

When a match occurs between two limit orders the price is set on the bid price. Bid of $25 and ask of $24 will be matched at $25.

Architecture (in development)

Order book & trade books are per-instrument objects, one order book can only handle one instrument.

  • order book - stores active orders in memory, handles order matching
  • trade book - stores daily trades in memory, provides additional data about trading
  • order container - container for efficient order insertion, search, traversal and removal
  • order repository - persistent storage of orders
  • trade repository - persistent storage of trades
Order book
  • order repository is used to persist all orders
  • it uses two treemap data structures for ask and bid orders
    • key is an OrderTracker object which contains necessary info to track an order and sort it
  • active orders are stored in a hashmap for fast lookup (by order ID) and storage
  • order trackers are stored in a hashmap - used to lookup order trackers (usually to be able to search a treemap)

Performance

The current figures are without stop orders used in the benchmark, manual cancellations and persistent storage. They are mostly a representation of in-memory order matching throughput.

BenchmarkOrderBook_Add-12 921057 1315 ns/op 557 B/op 8 allocs/op

Each order insertion to the order book takes about 1.4 μs, which means we can (theoretically) match ~725k orders in 1 second.

After all insertions 504755456B bytes (~504MB in use for about 281 active orders + 919787 executed trades - ~548B/trade) are in use, before insertions 238263296 bytes. Reported allocations are around 553 B/op. About 52% of total memory usage comes through the Add method, 111% increase from the setup state.

A big performance hit was suffered after stop orders were implemented - further optimizations will be necessary. Memory ballast definitely improves performance (about 3% improvement).

Huge performance improvements came from OrderTracker tracking only nanoseconds as timestamps, prices as float64s and smarter memory management. My goal is to hit 500 ns/op to be able to hit 2 million operations per second.

Current benchmark figures are currently without stop orders, but they will be included as a separate benchmark.

cockroachdb/apd gave a significant performance improvement over shopspring/decimal mainly because of huge memory usage improvement which drastically lowered the allocation rates (from 44 alloc/op to 4 alloc/op).

CLI example

Example entries and explanation can be found at ./examples/cli/example.txt

> cat examples/cli/example.txt | go run ./examples/cli

instructions: [set clear false]
enter instruction:instructions: [set prompt no ]
instructions: [set print instructions n ]
# buy 200 shares at market price
# following stop bids will be activated when market price reaches above their stop prices,
# but the order price is not the same as stop price
# set a stop bid at limit 25, activated when market price passes 24
# set a stop bid at limit 24, activated when market price passes 23
+----+--------+--------+------------+--------------------------------+-----+-----------+--------+
| ID |  TYPE  | PRICE  | STOP PRICE |              TIME              | QTY | FILLEDQTY | PARAMS |
+----+--------+--------+------------+--------------------------------+-----+-----------+--------+
|  1 | Market | 0.0000 |     0.0000 | 2021-02-20 14:00:12.438923503  | 200 |         0 |        |
|    |        |        |            | +0100 CET m=+0.001610273       |     |           |        |
+----+--------+--------+------------+--------------------------------+-----+-----------+--------+
bids
+----+------+-------+------------+------+-----+-----------+--------+
| ID | TYPE | PRICE | STOP PRICE | TIME | QTY | FILLEDQTY | PARAMS |
+----+------+-------+------------+------+-----+-----------+--------+
+----+------+-------+------------+------+-----+-----------+--------+
asks
+----+-------+---------+------------+--------------------------------+-----+-----------+--------+
| ID | TYPE  |  PRICE  | STOP PRICE |              TIME              | QTY | FILLEDQTY | PARAMS |
+----+-------+---------+------------+--------------------------------+-----+-----------+--------+
|  3 | Limit | 24.0000 |    23.0000 | 2021-02-20 14:00:12.438945514  |  30 |         0 | STOP   |
|    |       |         |            | +0100 CET m=+0.001632269       |     |           |        |
|  2 | Limit | 25.0000 |    24.0000 | 2021-02-20 14:00:12.438936978  |  20 |         0 | STOP   |
|    |       |         |            | +0100 CET m=+0.001623736       |     |           |        |
+----+-------+---------+------------+--------------------------------+-----+-----------+--------+
stop bids
+----+------+-------+------------+------+-----+-----------+--------+
| ID | TYPE | PRICE | STOP PRICE | TIME | QTY | FILLEDQTY | PARAMS |
+----+------+-------+------------+------+-----+-----------+--------+
+----+------+-------+------------+------+-----+-----------+--------+
stop asks
+------+-------+-------+-----+-------+-------+
| TIME | BIDID | ASKID | QTY | PRICE | TOTAL |
+------+-------+-------+-----+-------+-------+
+------+-------+-------+-----+-------+-------+
trades
Market price: 20.25
# fill-or-kill sell 100 shares at limit of 23.5 (don't sell below that)
+----+--------+---------+------------+--------------------------------+-----+-----------+--------+
| ID |  TYPE  |  PRICE  | STOP PRICE |              TIME              | QTY | FILLEDQTY | PARAMS |
+----+--------+---------+------------+--------------------------------+-----+-----------+--------+
|  1 | Market |  0.0000 |     0.0000 | 2021-02-20 14:00:12.438923503  | 200 |       100 |        |
|    |        |         |            | +0100 CET m=+0.001610273       |     |           |        |
|  3 | Limit  | 24.0000 |    23.0000 | 2021-02-20 14:00:12.438945514  |  30 |         0 | STOP   |
|    |        |         |            | +0100 CET m=+0.001632269       |     |           |        |
+----+--------+---------+------------+--------------------------------+-----+-----------+--------+
bids
+----+------+-------+------------+------+-----+-----------+--------+
| ID | TYPE | PRICE | STOP PRICE | TIME | QTY | FILLEDQTY | PARAMS |
+----+------+-------+------------+------+-----+-----------+--------+
+----+------+-------+------------+------+-----+-----------+--------+
asks
+----+-------+---------+------------+--------------------------------+-----+-----------+--------+
| ID | TYPE  |  PRICE  | STOP PRICE |              TIME              | QTY | FILLEDQTY | PARAMS |
+----+-------+---------+------------+--------------------------------+-----+-----------+--------+
|  2 | Limit | 25.0000 |    24.0000 | 2021-02-20 14:00:12.438936978  |  20 |         0 | STOP   |
|    |       |         |            | +0100 CET m=+0.001623736       |     |           |        |
+----+-------+---------+------------+--------------------------------+-----+-----------+--------+
stop bids
+----+------+-------+------------+------+-----+-----------+--------+
| ID | TYPE | PRICE | STOP PRICE | TIME | QTY | FILLEDQTY | PARAMS |
+----+------+-------+------------+------+-----+-----------+--------+
+----+------+-------+------------+------+-----+-----------+--------+
stop asks
+--------------------------------+-------+-------+-----+---------+-------+
|              TIME              | BIDID | ASKID | QTY |  PRICE  | TOTAL |
+--------------------------------+-------+-------+-----+---------+-------+
| 2021-02-20 14:00:12.439841334  |     1 |     4 | 100 | 23.5000 |  2350 |
| +0100 CET m=+0.002528089       |       |       |     |         |       |
+--------------------------------+-------+-------+-----+---------+-------+
trades
Market price: 23.5000
# last order will be matched with the first order, market price is now set at 23.5
# market price 23.5 activates the stop order set at 23, it's added to the books but isn't matched since there aren't opposing sellers
# sell 150 shares at market price
+----+------+-------+------------+------+-----+-----------+--------+
| ID | TYPE | PRICE | STOP PRICE | TIME | QTY | FILLEDQTY | PARAMS |
+----+------+-------+------------+------+-----+-----------+--------+
+----+------+-------+------------+------+-----+-----------+--------+
bids
+----+------+-------+------------+------+-----+-----------+--------+
| ID | TYPE | PRICE | STOP PRICE | TIME | QTY | FILLEDQTY | PARAMS |
+----+------+-------+------------+------+-----+-----------+--------+
+----+------+-------+------------+------+-----+-----------+--------+
asks
+----+------+-------+------------+------+-----+-----------+--------+
| ID | TYPE | PRICE | STOP PRICE | TIME | QTY | FILLEDQTY | PARAMS |
+----+------+-------+------------+------+-----+-----------+--------+
+----+------+-------+------------+------+-----+-----------+--------+
stop bids
+----+------+-------+------------+------+-----+-----------+--------+
| ID | TYPE | PRICE | STOP PRICE | TIME | QTY | FILLEDQTY | PARAMS |
+----+------+-------+------------+------+-----+-----------+--------+
+----+------+-------+------------+------+-----+-----------+--------+
stop asks
+--------------------------------+-------+-------+-----+---------+-------+
|              TIME              | BIDID | ASKID | QTY |  PRICE  | TOTAL |
+--------------------------------+-------+-------+-----+---------+-------+
| 2021-02-20 14:00:12.439841334  |     1 |     4 | 100 | 23.5000 |  2350 |
| +0100 CET m=+0.002528089       |       |       |     |         |       |
| 2021-02-20 14:00:12.440757787  |     1 |     5 | 100 | 24.0000 |  2400 |
| +0100 CET m=+0.003444541       |       |       |     |         |       |
| 2021-02-20 14:00:12.440759688  |     2 |     5 |  20 | 25.0000 |   500 |
| +0100 CET m=+0.003446443       |       |       |     |         |       |
| 2021-02-20 14:00:12.440760289  |     3 |     5 |  30 | 24.0000 |   720 |
| +0100 CET m=+0.003447043       |       |       |     |         |       |
+--------------------------------+-------+-------+-----+---------+-------+
trades
Market price: 24.0000
# sell order is matched with the recently activated stop order and sold at price of 24
# the new market price is now 24, which activates the first stop order and is sold at price of 25
# the sell order has been matched first against the order 1 market bid, then the last stop bid at price 25 and
# then at the first stop bid at price 24
# stop orders have not been matched in order of time when they were added to the books, but ordered by price and then time

Acknowledgements

Documentation

Overview

Package treemap provides a generic key-sorted map. It uses red-black tree under the hood. You can use it as a template to generate a sorted map with specific key and value types. Iterators are designed after C++.

Example: 

package main

import "fmt"

//go:generate gotemplate "github.com/igrmk/treemap" "intStringTreeMap(int, string)"

func less(x, y int) bool { return x < y }

func main() {
    tr := newIntStringTreeMap(less)
    tr.Set(0, "Hello")
    tr.Set(1, "World")

    for it := tr.Iterator(); it.Valid(); it.Next() {
        fmt.Println(it.Key(), it.Value())
    }
}

Index

Constants

View Source 
const (
	MinQty = 1
)

Variables

View Source 
var (
	ErrInvalidQty         = errors.New("invalid quantity provided")
	ErrInvalidMarketPrice = errors.New("price has to be zero for market orders")
	ErrInvalidLimitPrice  = errors.New("price has to be set for limit orders")
	ErrInvalidStopPrice   = errors.New("stop price has to be set for a stop order")

	BaseContext = apd.Context{
		Precision:   0,
		MaxExponent: apd.MaxExponent,
		MinExponent: apd.MinExponent,
		Traps:       apd.DefaultTraps,
	}
)
View Source 
var NOPOrderRepository = &nopOrderRepository{}

Functions

func NewOrderContainer 

func NewOrderContainer(bidLess, askLess LessFunc) *orderContainer

Create a new order container with specified LessFuncs.

Types

type LessFunc 

type LessFunc func(a, b OrderTracker) bool

function that compares two OrderTrackers and returns true if a is less or equal than b

type Order 

type Order struct {
	ID         uint64
	Instrument string
	CustomerID uuid.UUID
	Timestamp  time.Time // local timestamp - when did the order arrive

	Type      OrderType   // order type - market or limit
	Params    OrderParams // order parameters which change the way an order is stored and matched
	Qty       int64       // quantity - no fractional prices available, no unsigned to prevent accidental huge orders
	FilledQty int64       // currently filled quantity
	Price     apd.Decimal // used in limit orders
	StopPrice apd.Decimal // used in stop orders
	Side      OrderSide   // determines whether an order is a bid (buy) or an ask (sell)
	Cancelled bool        // determines if an order is cancelled. A partially filled order can be cancelled.
}

Represents an order by a customer to buy/sell an Instrument at a specified Price for a certain quantity (Qty). It stores additional data such as an order Timestamp, OrderType, StopPrice etc.

func (*Order) Cancel 

func (o *Order) Cancel()

func (*Order) IsAsk 

func (o *Order) IsAsk() bool

func (*Order) IsBid 

func (o *Order) IsBid() bool

func (*Order) IsCancelled 

func (o *Order) IsCancelled() bool

func (*Order) IsFilled 

func (o *Order) IsFilled() bool

func (Order) UnfilledQty 

func (o Order) UnfilledQty() int64

type OrderBook 

type OrderBook struct {
	Instrument string // instrument name
	// contains filtered or unexported fields
}

Order book contains all active orders for an instrument, handles matching and storage of orders and subsequent trades.

func NewOrderBook 

func NewOrderBook(instrument string, marketPrice apd.Decimal, tradeBook *TradeBook, orderRepo OrderRepository) *OrderBook

Create a new order book.

func (*OrderBook) Add 

func (o *OrderBook) Add(order Order) (bool, error)

Add a new order. Order can be matched immediately or later (or never), depending on order parameters and order type. Returns true if order was matched (partially or fully), false otherwise.

func (*OrderBook) Cancel 

func (o *OrderBook) Cancel(id uint64) error

Cancel an order.

func (*OrderBook) GetAsks 

func (o *OrderBook) GetAsks() []Order

Get all asks ordered the same way they are matched.

func (*OrderBook) GetBids 

func (o *OrderBook) GetBids() []Order

Get all bids ordered the same way they are matched.

func (*OrderBook) GetStopAsks 

func (o *OrderBook) GetStopAsks() []Order

Get all stop asks.

func (*OrderBook) GetStopBids 

func (o *OrderBook) GetStopBids() []Order

Get all stop bids.

func (*OrderBook) MarketPrice 

func (o *OrderBook) MarketPrice() apd.Decimal

Get a market price.

func (*OrderBook) SetMarketPrice 

func (o *OrderBook) SetMarketPrice(price apd.Decimal, fPrice float64)

Set a market price.

type OrderCallback 

type OrderCallback interface {
	Execute(order Order)
}

type OrderCallbackFunc 

type OrderCallbackFunc func(order Order)

type OrderParams 

type OrderParams uint64

determines order parameters. Each bit turns on a different parameter which changes the way an order is stored and matched 

const (
	ParamStop OrderParams = 0x1                 // stop order (has to have stop price set)
	ParamAON  OrderParams = 0x2                 // all-or-nothing - complete fill or cancel https://www.investopedia.com/terms/a/aon.asp
	ParamIOC  OrderParams = 0x4                 // immediate-or-cancel - immediately fill what you can, cancel the rest
	ParamFOK  OrderParams = ParamIOC | ParamAON // IOC + AON - immediately try to fill the whole order
	ParamGTC  OrderParams = 0x10                // good-till-cancelled -  keep order active until manually cancelled
	ParamGFD  OrderParams = 0x20                // good-for-day keep order active until the end of the trading day
	ParamGTD  OrderParams = 0x40                // good-till-date - keep order active until the provided date (including the date)
)

func (OrderParams) Is 

func (o OrderParams) Is(param OrderParams) bool

returns true if a parameter value matches the provided parameters (if param is a subset of o) e.g. ParamFOK.Is(ParamAON) is true, ParamFOK.Is(ParamStop) is false. ParamAON.Is(ParamAON) is true.

func (OrderParams) String 

func (o OrderParams) String() string

type OrderRepository 

type OrderRepository interface {
	Save(order Order) error
	GetByID(id uint64) (Order, error)
}

type OrderSide 

type OrderSide bool

determines the order "side" - buy or sell 

const (
	SideBuy  OrderSide = true
	SideSell OrderSide = false
)

func (OrderSide) String 

func (o OrderSide) String() string

type OrderTracker 

type OrderTracker struct {
	OrderID   uint64
	Type      OrderType
	Price     float64
	Side      OrderSide
	Timestamp int64 // nanoseconds since Epoch
}

Used as a transport object in matching and quick retrieval, represents an order stored somewhere else.

type OrderType 

type OrderType byte

determines the order "type" - basic types are market and limit 

const (
	TypeMarket OrderType = iota + 1
	TypeLimit
)

func (OrderType) String 

func (o OrderType) String() string

type Trade 

type Trade struct {
	ID            uint64
	Buyer, Seller uuid.UUID
	Instrument    string
	Qty           int64
	Price         apd.Decimal
	Total         apd.Decimal
	Timestamp     time.Time

	BidOrderID uint64
	AskOrderID uint64
}

Trade represents two opposed matched orders.

type TradeBook 

type TradeBook struct {
	Instrument string
	// contains filtered or unexported fields
}

Trade book stores all daily trades in-memory. It flushes new trades periodically to persistent storage. (TODO)

func NewTradeBook 

func NewTradeBook(instrument string) *TradeBook

Create a new trade book.

func (*TradeBook) DailyTrades 

func (t *TradeBook) DailyTrades() []Trade

Return all daily trades in a trade book.

func (*TradeBook) Enter 

func (t *TradeBook) Enter(trade Trade)

Enter a new trade.

type TradeCallback 

type TradeCallback interface {
	Execute(trade Trade)
}

type TradeCallbackFunc 

type TradeCallbackFunc func(trade Trade)

type TradeRepository 

type TradeRepository interface {
	Store(trade Trade) error
	GetByID(id uint64) (Trade, error)
}

Source Files

View all Source files

Directories

Path Synopsis
examples
cli command

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.