README
¶
High Performance Order Book for matching engines
An experimental low latency, high throughput order book in Go.
Why?
Becuase it's fun!
Why Go?
The initial goal of the project was to see how far I could take a practical low-latency workload in a GC'd language like Go, which seems to have been (mostly) achieved.
Add/Cancel latency is pretty good (see below) and the jitter is not too bad. The impact of GC has been reduced to nonexistence. However, there is still room for improvement in jitter caused by the Go scheduler.
Features
- Simple API
- Standard price-time priority
- Market and limit orders
- Order cancellation. (No in-book updates. Updates will have to be handled with Cancel+Create, and all that entails)
- Stop loss / take profit orders (limit and market)
- AoN, IoC, FoK, etc. Probably not trailing stops. They're probably better handled outside the order book.
- Snapshot the ordebook state for recovery
- Handle any GC latency shenanigans
- Extensive tests and benchmarks
- Add metrics counters
- Improve consistent latency
- Extremely high throughput (see below)
Latency
On 2.1 Ghz Base Freq 12th Gen i& with 5200 MHz LPDD5, Hyperthreading off, Turbo off, AND GOMAXPROCS=2
Results are generally similar with test run without OS thread locking or run in a goroutine locked to an OS thread which in turn is run on an isolated CPU core on an unmodified -generic ubuntu kernel. Results are also similar with GOMAXPROCS=1
Other threads run by the Go scheduler don't seem to make a notable difference whether run on isolated cores or not, as long as they're not all pinned to the same core.
The nohz_full column represents tests run with GOMAXPROCS=1 on a nohz_full isolated core on a -generic ubuntu kernel compiled with nohz_full and all possible IRQs moved out of that core. The primary thread was pinned to this isolated core and all other threads were left on non-isolated cores.
The sched_manual column represents the settings of nohz_full mentioned above along with calls to runtime.Gosched() before and after the calls being benchmarked. This is because majority of the large latency spikes seems to be introduced due to the Go scheduler pauses in between the runs. I have not found a way to get rid of these. Running Gosched() seems to mitigate these to the point where pinning goroutine to a thread introduces significant stabilitizing of the jitter. However, this comes at about 10% cost to the throughput, and incrased latencies at p50/o90 due to increased context switching which in matching engines might be an acceptable tradeoff for reduced jitter.
| AddOrder | Latency (approx.) | nohz_full | sched_manual |
|---|---|---|---|
| p50 | 170ns | 164ns | 546ns |
| p99 | 229ns | 256ns | 735ns |
| p99.99 | 2.4us | 2.3us | 2.4us |
| p99.9999 | 12us | 6.5us | 7.9us |
| Max | 36us | 15us | 8.5us |
| CancelOrder | Latency (approx.) | nohz_full | sched_manual |
|---|---|---|---|
| p50 | 35ns | 33ns | 50ns |
| p99 | 50ns | 50ns | 59ns |
| p99.99 | 86ns | 60ns | 165ns |
| p99.9999 | 3.9us | 3.1us | 1.9us |
| Max | 25us | 6.8us | 1.9us |
Throughput
-
12.5 million Order Add/Cancel per second:
- 2.1 Ghz Base Frequency 12th Gen i7 with 5200 Mhz LPDDR5
- Turbo Boost disbabled
- Hyperthreading disabled
-
21 million Order Add/Cancel per second:
- 2.1 Ghz Base Frequency 12th Gen i7 with 5200 Mhz LPDDR5
- Turbo Boost enabled 4.7 Ghz
- Hyperthreading disabled
Limitations
- 8 decimal places due to decimal library used. This should be fine for most use cases.
- Consider LMAX Disruptor to maintain the throughput while post-processing with a matching engine, although this level of thoughput is probably not necessary for most use cases.
How do I use this?
You probably shouldn't use this as-is. It'll ideally at least require more thorough test coverage.
That said, it should be extremely simple to use this. Create an OrderBook object as a starting point.
There's a bug
Please create an issue. Also PRs are welcome!
Documentation
¶
Overview ¶
Package redblacktree implements a red-black tree.
Used by TreeSet and TreeMap.
Structure is not thread safe.
References: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Package redblacktree implements a red-black tree.
Used by TreeSet and TreeMap.
Structure is not thread safe.
References: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree
Index ¶
Constants ¶
const ( None FlagType = 0 IoC = 1 AoN = 2 FoK = 4 StopLoss = 8 TakeProfit = 16 Snapshot = 32 )
Market or Limit
Variables ¶
var ( ErrInvalidQuantity = errors.New("orderbook: invalid order quantity") ErrInvalidPrice = errors.New("orderbook: invalid order price") ErrInvalidTriggerPrice = errors.New("orderbook: invalid trigger price") ErrOrderID = errors.New("orderbook: order id is less than previous order ids") ErrOrderExists = errors.New("orderbook: order already exists") ErrOrderNotExists = errors.New("orderbook: order does not exist") ErrInsufficientQuantity = errors.New("orderbook: insufficient quantity to calculate price") ErrNoMatching = errors.New("orderbook: matching disabled") )
OrderBook erros
Functions ¶
Types ¶
type NotificationHandler ¶
type NotificationHandler interface {
PutOrder(m MsgType, s OrderStatus, orderID uint64, qty decimal.Decimal, err error)
PutTrade(makerOrderID, takerOrderID uint64, makerStatus, takerStatus OrderStatus, qty, price decimal.Decimal)
}
NotificationHandler handles notification updates
type Option ¶
type Option func(*OrderBook)
func WithNodeTreePoolSize ¶
WithNodeTreePoolSize sets the size of the node tree pool
func WithOrderPoolSize ¶
WithOrderPoolSize sets the size of the order pool
func WithOrderQueuePoolSize ¶
WithOrderQueuePoolSize sets the size of the order queue pool
func WithOrderTreeNodePoolSIze ¶
WithOrderTreeNodePoolSize sets the size of the order tree node pool
type Order ¶
type Order struct {
ID uint64 `json:"id" `
Class ClassType `json:"class" `
Side SideType `json:"side" `
Flag FlagType `json:"flag" `
Qty decimal.Decimal `json:"qty" `
Price decimal.Decimal `json:"price" `
TrigPrice decimal.Decimal `json:"trigPrice" `
// contains filtered or unexported fields
}
Order strores information about request
func NewOrder ¶
func NewOrder(orderID uint64, class ClassType, side SideType, qty, price, trigPrice decimal.Decimal, flag FlagType) *Order
NewOrder creates new constant object Order
type OrderBook ¶
type OrderBook struct {
// contains filtered or unexported fields
}
OrderBook implements standard matching algorithm
func NewOrderBook ¶
func NewOrderBook(n NotificationHandler, opts ...Option) *OrderBook
NewOrderBook creates Orderbook object
func (*OrderBook) AddOrder ¶
func (ob *OrderBook) AddOrder(tok, id uint64, class ClassType, side SideType, quantity, price, trigPrice decimal.Decimal, flag FlagType)
AddOrder places new order to the OrderBook Arguments:
orderID - unique order ID in depth (uint64) class - what class of order do you want to place (ob.Market or ob.Limit) side - what do you want to do (ob.Sell or ob.Buy) quantity - how much quantity you want to sell or buy (decimal) price - no more expensive (or cheaper) this price (decimal) trigPrice - create a stop/take order until market price reaches this price (decimal) flag - immediate or cancel, all or none, fill or kill, Cancel (ob.IoC or ob.AoN or ob.FoK or ob.Cancel) * to create new decimal number you should use udecimal.New() func read more at https://github.com/geseq/udecimal
func (*OrderBook) CancelOrder ¶
CancelOrder removes order with given ID from the order book
type OrderStatus ¶
type OrderStatus byte
OrderStatus of the order
const ( Rejected OrderStatus = iota Canceled FilledPartial FilledComplete Accepted )
func (OrderStatus) String ¶
func (o OrderStatus) String() string
String implements Stringer interface
type Trade ¶
type Trade struct {
MakerOrderID uint64 `json:"makerOrderId" `
TakerOrderID uint64 `json:"takerOrderId" `
MakerStatus OrderStatus `json:"makerStatus" `
TakerStatus OrderStatus `json:"takerStatus" `
Qty decimal.Decimal `json:"qty"`
Price decimal.Decimal `json:"price" `
}
Trade strores information about request
Source Files
Directories