fastme (fast golang matching engine) library

Design

The library solves the task of recalculating the exchange order book. A classic matching engine consists of limit orders (orders) for buying or selling (exchanging) some commodity for another commodity, usually currency.

The distinctive feature of the library is that:

• No predetermined price levels
• There is no restriction on the types of numeric values used
• When working within integers, performance is achieved up to 500k transactions per second
• Contains all necessary dependencies
• There is support for write-off of commissions like maker and taker for working on cryptocurrency assets

Description of interfaces and data types

All mathematical recalculation operations of the order book are designed to work in the system of business logic, so the engine itself works with the input interfaces and notifies the business logic about the events that occurred during the exchange of goods. BL decides what to do with this data (e.g., write off funds from the corresponding wallet). For the correct operation of the exchange it is necessary to implement the interfaces described in the file ```echange.go``.

Asset

type Asset string

Describes the name of some exchange asset. Matching engine notifies the business logic of the event with the product and Asset type, not string, for clarity.

Volume

type Volume struct {
	Price    Value
	Quantity Value
}

When making a transaction or closing a position, the matching engine also notifies about the volume of the transaction of Volume type. It contains the value of the amount and quantity of the exchange asset.

Value

// Value calculates math operations
type Value interface {
	// Add is an "+" operation
	Add(Value) Value

	// Sub is an "-" operation
	Sub(Value) Value

	// Mul is an "*" operation
	Mul(Value) Value

	// Cmp returns 1 if self > given, -1 if self < given and 0 if self == given
	Cmp(Value) int

	// Sign returns 1 if Value > 0, -1 if Value < 0 and 0 if Value == 0
	Sign() int

	// Hash returns any string representation of the Value
	Hash() string
}

For recalculation and storage of numbers in the order of the order book it is necessary to implement certain mathematical operations. To dwell on a certain type of data (eg int.Big) is obviously inconvenient because of the subsequent severe restriction on the related type. Therefore, the type Value has appeared, in which you can wrap this interface (example in the file ```engine_test.go``).

Add, Sub и Mul

Must return a new object, not a changed current one.

Cmp и Sign

Must return the sign of a number to be able to compare the two numbers, as indicated in the help.

Hash

Does not have to return the hash number. It is enough to return a unique string for a specific single number. In most cases, the conversion of a number to a string will do. This function is used to store price levels and add orders to the queue at a specific price. This interface is enough to implement all the mathematics of exchange.

Wallet

type Wallet interface {
	// Balance returns current wallet balance for given asset
	Balance(context.Context, Asset) Value

	// UpdateBalance calls by matching engine to update wallet balance
	UpdateBalance(context.Context, Asset, Value)

	// InOrder returns amount of asset in order
	InOrder(context.Context, Asset) Value

	// UpdateInOrder calls by matching engine to inform about freezed amount in order
	UpdateInOrder(context.Context, Asset, Value)
}

In the course of the transaction, the matching engine uses the interface Wallet in order to correctly transfer or write off funds in exchange wallets. In a wallet there is an obligatory balance Balance, which contains the current balance of a wallet, and also InOrder balance, which denotes the quantity of an asset in an order book.

Functions are called by the engine when calculating the request. Context is passed through from the functions of placing and canceling an order, so it is possible to place, for example, database record objects.

Functions marked as optional may be plugged and do not affect the operation of the engine, but are useful for taking into account the number of assets in the order book when calculating the exchange business logic.

Balance и InOrder

Must return the current balance of the wallet for further recalculation operations.

UpdateBalance и UpdateInOrder

Must update the balance of the wallet when the transaction.

Order

type Order interface {
	// ID returns any unique string for order
	ID() string

	// Owner returns wallet to debit or credit asset on exchange process
	Owner() Wallet

	// Sell returns true if order for selling, true otherwise
	Sell() bool

	// Price retuns order price
	Price() Value

	// Quantity returns current order quantity
	Quantity() Value

	// UpdateQuantity calls by matching engine to set new order quantity
	UpdateQuantity(Value)
}

The main unit of exchange is an order. Limit requests are stored in the RAM of the matching engine and are deleted from it as soon as the specified quantity is completed. For engine operation it is necessary to implement the specified methods.

ID

Must return the unique identifier of the order. In case of repetition, the request will be rejected.

Owner

Must return wallet, which owns this order. This method can be implemented in various ways, for example, through the wallet manager when creating an order. Or keep a pointer to the wallet in the request and return it.

Sell

Returns true if the order for sale.

Price

Returns the desired limit value at which you are willing to buy or sell the asset. If the value is zero, the order will be fully executed at the current market price (market order) if there are sufficient funds in your wallet to buy or sell.

Quantity

Must return the remaining amount in the unfulfilled order.

UpdateQuantity

It is called by the engine when recalculating and executing a transaction, notifying the business logic about the current amount of the asset remaining.

FeeHandler

type FeeHandler interface {
	// HandleFeeMaker calls by  matching engine and provide data to correct output value for fee processing
	HandleFeeMaker(context.Context, Order, Asset, Value) (out Value)

	// HandleFeeTaker calls by  matching engine and provide data to correct output value for fee processing
	HandleFeeTaker(context.Context, Order, Asset, Value) (out Value)
}

Called at the time of the transaction in order to write off the commission. In the current version, the commission is written off by processing. For example, 1 unit of goods has been sold and 0.9 units will be credited to the balance due to the specifics of the engine. This parameter is optional. The handler is divided into Maker - market maker. That is a limit order. And Taker - a market order (or a market part of a limit order).

HandleFeeMaker, HandleFeeTaker

The context of a constraint, information on a certain asset transaction is received at the entrance. The function should return inValue - feeValue to out value.

EventListener

type EventListener interface {
	OnIncomingOrderPartial(context.Context, Order, Volume)
	OnIncomingOrderDone(context.Context, Order, Volume)
	OnIncomingOrderPlaced(context.Context, Order)

	OnExistingOrderPartial(context.Context, Order, Volume)
	OnExistingOrderDone(context.Context, Order, Volume)
	OnExistingOrderCanceled(context.Context, Order)

	OnBalanceChanged(context.Context, Wallet, Asset, Value)
	OnInOrderChanged(context.Context, Wallet, Asset, Value)
}

The interface takes part in the operations of placing and withdrawing an order. It is used to notify the higher business logic about all events that occurred during order processing. There are 2 order types - incoming and existing. Existing order is a limit order (with it's balance), which is located in the order book.

OnIncomingOrderPartial

Called at partial execution of an incoming order.

OnIncomingOrderDone

Called when an incoming order is completed.

OnIncomingOrderPlaced

Called when the incoming order (or the balance of partial execution) has entered the queue of the matching engine.

OnExistingOrderPartial

Called at partial limit order execution.

OnExistingOrderDone

Called when the limit order is completed.

OnExistingOrderCanceled

Called when the limit order is canceled.

OnBalanceChanged

Called when the balance on your wallet changes as a result of processing the order. Notifies the recipient about the new balance.

OnInOrderChanged

Called in case of change of balance in orders on your wallet as a result of processing the order. Notifies the recipient of the new value of the amount of asset in the order book.

Functionality

The main functions of processing incoming orders have been implemented to manage the order book.

func NewEngine(base, quote Asset) *Engine

Initializes the matching engine. Allocates memory for data.

func (e *Engine) SetFeeHandler(h FeeHandler)

Sets the fee handler.

func (e *Engine) PlaceOrder(ctx context.Context, listener EventListener, o Order) (err error)

Processes incoming order. Recalculates the state of the order book. Returns the following errors in case of impossibility to process the order:

var (
	ErrInvalidQuantity      = errors.New("Quantity could not be less or equal zero")
	ErrInvalidPrice         = errors.New("Price could not be less zero")
	ErrInsufficientQuantity = errors.New("Insufficient quantity to calculate market price")
	ErrInsufficientFunds    = errors.New("Insufficient funds to process order")
	ErrOrderExists          = errors.New("Order with given ID already exists")
	ErrOrderNotFound        = errors.New("Order with given ID not found")
)

func (e *Engine) CancelOrder(ctx context.Context, listener EventListener, o Order)

Removes the specified order from the order book.

func (e *Engine) PushOrder(ctx context.Context, o Order)

Puts the order in a queue without applying mathematical recalculation. It is used to restore the glass from the database.

func (e *Engine) Quantity(sell bool, priceLim Value) Value

Returns the volume of the asset to a certain price.

func (e *Engine) Price(sell bool, quantity Value) (Value, error)

Returns the market value for the specified amount of asset.

func (e *Engine) Spread() (bestAsk, bestBid Value)

Returns the value of the price spread in the order book. nil if there are no bids in one or two directions.

func (e *Engine) FindOrder(id string) (Order, error)

Returns an order by its identifier or error ErrOrderNotFound

func (e *Engine) Orders() (orders []Order)

Returns the list of limit orders that are in the order book.

func (e *Engine) OrderBook(iter func(asks bool, price, volume Value, len int))

Iterates price levels by returning information about price, order volume and queue length.

Work algorithm

The engine structure contains a linked list of orders and a search tree for the optimal price to insert or place.