This repo contrais an amateurism attempt to make a central limit order book using hyper SDK for avalanche(i mean cant be done in 6 hrs :/ )
This project implements a Centralized Limit Order Book (CLOB) in Go, designed to efficiently process and match buy and sell orders in a trading system. The implementation focuses on clean code organization, efficient data structures, and clear separation of concerns.
This README provides a detailed explanation of the approach, code organization, data structures used, and the workflow for processing orders. Accompanying mermaid diagrams illustrate the interactions between components and the flow of order processing.
The code is organized into a package named CLOB, with the following files:
orderbook/
├── order.go
├── order_queue.go
├── price_level.go
├── heap.go
├── order_book_side.go
├── order_book.go
├── matching_engine.go
├── utils.go
Each file serves a specific purpose, ensuring modularity and maintainability.
Purpose: Defines the Order struct and related types.
// orderbook/order.gopackage orderbook
import"time"// Side represents the side of an order: Buy or SelltypeSidestringconst (
BuySide="buy"SellSide="sell"
)
// OrderType represents the type of an order: Limit or MarkettypeOrderTypestringconst (
LimitOrderType="limit"MarketOrderType="market"
)
// Order represents an individual order in the order booktypeOrderstruct {
IDstringSideSidePricefloat64// 0 for market ordersQuantityfloat64Timestamp time.TimeOrderTypeOrderTypenext*Order// For linked list (unexported)prev*Order// For linked list (unexported)
}Explanation:
Side: Enumerated type indicating buy or sell.OrderType: Enumerated type indicating limit or market order.Order: Struct representing an order, including fields for order ID, side, price, quantity, timestamp, and order type.nextandprev: Unexported fields used internally for linked list implementation.
Purpose: Implements a doubly linked list (OrderQueue) to manage orders at the same price level.
// orderbook/order_queue.gopackage orderbook
// OrderQueue represents a doubly linked list of orderstypeOrderQueuestruct {
head*Ordertail*OrderSizeint
}
// NewOrderQueue creates a new empty order queuefuncNewOrderQueue() *OrderQueue {
return&OrderQueue{}
}
// Enqueue adds an order to the end of the queuefunc (oq*OrderQueue) Enqueue(order*Order) {
ifoq.tail==nil {
oq.head=orderoq.tail=order
} else {
oq.tail.next=orderorder.prev=oq.tailoq.tail=order
}
oq.Size++
}
// Dequeue removes and returns the order from the front of the queuefunc (oq*OrderQueue) Dequeue() *Order {
ifoq.head==nil {
returnnil
}
order:=oq.headoq.head=oq.head.nextifoq.head!=nil {
oq.head.prev=nil
} else {
oq.tail=nil
}
order.next=niloq.Size--returnorder
}
// Remove removes a specific order from the queuefunc (oq*OrderQueue) Remove(order*Order) {
iforder.prev!=nil {
order.prev.next=order.next
} else {
oq.head=order.next
}
iforder.next!=nil {
order.next.prev=order.prev
} else {
oq.tail=order.prev
}
order.next=nilorder.prev=niloq.Size--
}Explanation:
OrderQueue: Manages orders in a FIFO manner at a specific price level.- Methods
Enqueue,Dequeue, andRemovemanage the linked list operations.
Purpose: Defines the PriceLevel struct, representing all orders at a specific price.
// orderbook/price_level.gopackage orderbook
// PriceLevel represents a level in the order book at a specific pricetypePriceLevelstruct {
Pricefloat64Orders*OrderQueue
}Explanation:
PriceLevel: Contains the price and a pointer to anOrderQueueof orders at that price.
Purpose: Implements heap interfaces (BuyHeap and SellHeap) for managing price levels in a priority queue.
// orderbook/heap.gopackage orderbook
import"container/heap"// BuyHeap implements heap.Interface for a max-heap (buy side)typeBuyHeap []*PriceLevelfunc (bhBuyHeap) Len() int { returnlen(bh) }
func (bhBuyHeap) Swap(i, jint) { bh[i], bh[j] =bh[j], bh[i] }
func (bhBuyHeap) Less(i, jint) bool { returnbh[i].Price>bh[j].Price }
func (bh*BuyHeap) Push(xinterface{}) {
*bh=append(*bh, x.(*PriceLevel))
}
func (bh*BuyHeap) Pop() interface{} {
old:=*bhn:=len(old)
x:=old[n-1]
*bh=old[0 : n-1]
returnx
}
// SellHeap implements heap.Interface for a min-heap (sell side)typeSellHeap []*PriceLevelfunc (shSellHeap) Len() int { returnlen(sh) }
func (shSellHeap) Swap(i, jint) { sh[i], sh[j] =sh[j], sh[i] }
func (shSellHeap) Less(i, jint) bool { returnsh[i].Price<sh[j].Price }
func (sh*SellHeap) Push(xinterface{}) {
*sh=append(*sh, x.(*PriceLevel))
}
func (sh*SellHeap) Pop() interface{} {
old:=*shn:=len(old)
x:=old[n-1]
*sh=old[0 : n-1]
returnx
}Explanation:
BuyHeap: Max-heap for buy orders, prioritizing higher prices.SellHeap: Min-heap for sell orders, prioritizing lower prices.- Both implement the
heap.Interfacefor use with Go'scontainer/heappackage.
Purpose: Manages one side of the order book (OrderBookSide), either buy or sell.
// orderbook/order_book_side.gopackage orderbook
import"container/heap"// OrderBookSide represents one side of the order book (buy or sell)typeOrderBookSidestruct {
SideSidePriceLevelsmap[float64]*PriceLevelPrices heap.Interface
}
// NewOrderBookSide creates a new OrderBookSidefuncNewOrderBookSide(sideSide) *OrderBookSide {
obSide:=&OrderBookSide{
Side: side,
PriceLevels: make(map[float64]*PriceLevel),
}
ifside==Buy {
bh:=&BuyHeap{}
heap.Init(bh)
obSide.Prices=bh
} else {
sh:=&SellHeap{}
heap.Init(sh)
obSide.Prices=sh
}
returnobSide
}
// AddPriceLevel adds a new price level to the heapfunc (obs*OrderBookSide) AddPriceLevel(priceLevel*PriceLevel) {
heap.Push(obs.Prices, priceLevel)
}
// RemovePriceLevel removes a price level from the heap// Note: Direct removal from heap middle is complex; additional logic requiredfunc (obs*OrderBookSide) RemovePriceLevel(priceLevel*PriceLevel) {
// Placeholder for removal logic
}
// PeekBestPriceLevel returns the best price level without removing itfunc (obs*OrderBookSide) PeekBestPriceLevel() *PriceLevel {
ifobs.Prices.Len() ==0 {
returnnil
}
return (*obs.Prices).([]*PriceLevel)[0]
}Explanation:
OrderBookSide: Contains the side (buy/sell), a map of price levels, and a heap of prices.NewOrderBookSide: Initializes the side with the appropriate heap.- Methods manage adding and removing price levels.
Purpose: Defines the OrderBook struct, which contains both sides and a map of all orders.
// orderbook/order_book.gopackage orderbook
// OrderBook represents the entire order booktypeOrderBookstruct {
Bids*OrderBookSideAsks*OrderBookSideOrderMapmap[string]*Order
}
// NewOrderBook creates a new OrderBookfuncNewOrderBook() *OrderBook {
return&OrderBook{
Bids: NewOrderBookSide(Buy),
Asks: NewOrderBookSide(Sell),
OrderMap: make(map[string]*Order),
}
}Explanation:
OrderBook: ContainsBids,Asks, andOrderMap.NewOrderBook: Initializes a new order book.
Purpose: Implements the matching engine logic to process and match orders.
// orderbook/matching_engine.gopackage orderbook
import (
"container/heap""fmt"
)
// AddOrder processes and adds an order to the order bookfunc (ob*OrderBook) AddOrder(order*Order) error {
// Add order to OrderMapob.OrderMap[order.ID] =order// Process order based on typeswitchorder.OrderType {
caseLimit:
returnob.matchLimitOrder(order)
caseMarket:
returnob.matchMarketOrder(order)
default:
returnfmt.Errorf("unknown order type: %v", order.OrderType)
}
}
// matchMarketOrder processes a market orderfunc (ob*OrderBook) matchMarketOrder(order*Order) error {
oppositeSide:=ob.getOppositeSide(order.Side)
remainingQty:=order.QuantityforremainingQty>0&&oppositeSide.Prices.Len() >0 {
// Get the best price levelbestPriceLevel:=heap.Pop(oppositeSide.Prices).(*PriceLevel)
ordersQueue:=bestPriceLevel.OrdersforordersQueue.Size>0&&remainingQty>0 {
headOrder:=ordersQueue.Dequeue()
tradeQty:=min(remainingQty, headOrder.Quantity)
// Execute trade (log trade details)settleTrade(order, headOrder, tradeQty)
remainingQty-=tradeQtyheadOrder.Quantity-=tradeQtyifheadOrder.Quantity==0 {
// Remove order from OrderMapdelete(ob.OrderMap, headOrder.ID)
} else {
// Re-enqueue the remaining quantityordersQueue.Enqueue(headOrder)
break
}
}
ifordersQueue.Size==0 {
// No more orders at this price leveldelete(oppositeSide.PriceLevels, bestPriceLevel.Price)
} else {
// Push back the price level as there are still orders leftheap.Push(oppositeSide.Prices, bestPriceLevel)
}
}
ifremainingQty>0 {
// Market order could not be fully matchedreturnfmt.Errorf("market order could not be fully matched")
}
// Order fully processeddelete(ob.OrderMap, order.ID)
returnnil
}
// matchLimitOrder processes a limit orderfunc (ob*OrderBook) matchLimitOrder(order*Order) error {
oppositeSide:=ob.getOppositeSide(order.Side)
compare:=getPriceComparator(order.Side)
remainingQty:=order.QuantityforremainingQty>0&&oppositeSide.Prices.Len() >0 {
bestPriceLevel:=oppositeSide.PeekBestPriceLevel()
// Check if the price satisfies the limit order's conditionifcompare(bestPriceLevel.Price, order.Price) {
heap.Pop(oppositeSide.Prices)
ordersQueue:=bestPriceLevel.OrdersforordersQueue.Size>0&&remainingQty>0 {
headOrder:=ordersQueue.Dequeue()
tradeQty:=min(remainingQty, headOrder.Quantity)
// Execute trade (log trade details)settleTrade(order, headOrder, tradeQty)
remainingQty-=tradeQtyheadOrder.Quantity-=tradeQtyifheadOrder.Quantity==0 {
// Remove order from OrderMapdelete(ob.OrderMap, headOrder.ID)
} else {
// Re-enqueue the remaining quantityordersQueue.Enqueue(headOrder)
break
}
}
ifordersQueue.Size==0 {
// No more orders at this price leveldelete(oppositeSide.PriceLevels, bestPriceLevel.Price)
} else {
// Push back the price level as there are still orders leftheap.Push(oppositeSide.Prices, bestPriceLevel)
}
} else {
// Price doesn't satisfy the limit order conditionbreak
}
}
ifremainingQty>0 {
// Add the remaining order to the bookorder.Quantity=remainingQtyside:=ob.getSide(order.Side)
ob.addLimitOrder(side, order)
} else {
// Order fully filleddelete(ob.OrderMap, order.ID)
}
returnnil
}
// addLimitOrder adds a limit order to the appropriate sidefunc (ob*OrderBook) addLimitOrder(side*OrderBookSide, order*Order) {
priceLevel, exists:=side.PriceLevels[order.Price]
if!exists {
// Create new price levelpriceLevel=&PriceLevel{
Price: order.Price,
Orders: NewOrderQueue(),
}
// Add to PriceLevels mapside.PriceLevels[order.Price] =priceLevel// Add price level to heapside.AddPriceLevel(priceLevel)
}
// Enqueue orderpriceLevel.Orders.Enqueue(order)
}
// Helper methodsfunc (ob*OrderBook) getSide(sideSide) *OrderBookSide {
ifside==Buy {
returnob.Bids
}
returnob.Asks
}
func (ob*OrderBook) getOppositeSide(sideSide) *OrderBookSide {
ifside==Buy {
returnob.Asks
}
returnob.Bids
}Explanation:
AddOrder: Entry point to process new orders.matchMarketOrder: Matches market orders against the opposite side until fulfilled.matchLimitOrder: Matches limit orders considering the price limit.addLimitOrder: Adds unmatched limit orders to the order book.- Helper methods for side retrieval.
Purpose: Contains utility functions used across the package.
// orderbook/utils.gopackage orderbook
import"fmt"// min returns the minimum of two float64 numbersfuncmin(a, bfloat64) float64 {
ifa<b {
returna
}
returnb
}
// settleTrade simulates the settlement of a trade between two ordersfuncsettleTrade(order1, order2*Order, quantityfloat64) {
// Log the trade executionfmt.Printf("Trade executed: %s and %s for %.2f units at price %.2f\n",
order1.ID, order2.ID, quantity, order2.Price)
}
// getPriceComparator returns a comparison function based on the sidefuncgetPriceComparator(sideSide) func(float64, float64) bool {
ifside==Buy {
returnfunc(a, bfloat64) bool { returna<=b }
}
returnfunc(a, bfloat64) bool { returna>=b }
}Explanation:
min: Utility to find the minimum of two values.settleTrade: Simulates trade execution (can be expanded for real settlement).getPriceComparator: Returns a comparison function based on the order side.
- An order is created and passed to the
AddOrdermethod of theOrderBook. - The order is added to the
OrderMapfor tracking.
Objective: Execute immediately against the best available prices.
Workflow:
- Identify the opposite side (
Asksfor a buy order,Bidsfor a sell order). - While the order is not fully matched and there are price levels:
- Get the best price level from the heap.
- Iterate through orders in the
OrderQueueat that price level. - Execute trades, updating quantities.
- Remove fully matched orders from the queue and
OrderMap.
- If the order is fully matched, remove it from the
OrderMap. - If not fully matched, return an error indicating partial fill.
Mermaid Diagram:
Objective: Match within the limit price; otherwise, add to the order book.
Workflow:
- Identify the opposite side.
- While the order is not fully matched and there are price levels satisfying the limit price:
- Peek at the best price level.
- If the price satisfies the limit condition, proceed to match.
- Iterate through orders in the
OrderQueueat that price level. - Execute trades, updating quantities.
- Remove fully matched orders from the queue and
OrderMap.
- If the order is not fully matched, add it to the order book on the appropriate side.
Mermaid Diagram:
Mermaid Class Diagram:
To optimize the performance, scalability, and reliability of the prediction market, we fine-tune the HyperSDK VM using the Config struct. Adjusting these configuration parameters allows us to simulate realistic trading environments, manage transaction loads efficiently, and ensure smooth operation under varying conditions.
typeConfigstruct {
uris []stringauthFactory chain.AuthFactorysZipffloat64vZipffloat64txsPerSecondintminTxsPerSecondinttxsPerSecondStepintnumClientsintnumAccountsint
}further im storing all these in the state db throughuse of Hypersdk to make the stuff faster
it was hard to get this to work in 6hrs so this is just a proof of concept given enough time ,would love to work with this toolkit and get this to work