{ "cells": [ { "cell_type": "markdown", "id": "4a9cb7d4-0c09-4587-a2a6-198c9e4603e2", "metadata": {}, "source": [ "# Chapter 5: Deep Dive into OpenBook V2 Program\n", "\n", "```sh\n", "\n", " +-----------------------+\n", " | RootNode |\n", " |-----------------------|\n", " | tag: 0 |\n", " | padding: [0, 0, 0] |\n", " | prefix_len: 2 |\n", " | key: 10 |\n", " | children: [0, 1] |\n", " | child_earliest_expiry|\n", " | [1844674407370..] |\n", " | reserved: [0,..] |\n", " +-----------------------+\n", " |\n", " +---------------+---------------+\n", " | |\n", " +-----------v-----------+ +------------v------------+\n", " | InnerNode | | InnerNode |\n", " | tag: 1 | | tag: 1 |\n", " | padding: [0, 0, 0] | | padding: [0, 0, 0] |\n", " |-----------------------| |-------------------------|\n", " | prefix_len: 3 | | prefix_len: 4 |\n", " | key: 5 | | key: 6 |\n", " | children: [2, 2] | | children: [4, 5] |\n", " | child_earliest_expiry| | child_earliest_expiry |\n", " | [184467440737095, ..] | | [184467440737095, ..] |\n", " | reserved: [0, ...] | | reserved: [0, ...] |\n", " +--------+--------------+ +-------------+-----------+\n", " | |\n", " +-----------v--------+ +------------v------------+\n", " | | | LeafNode |\n", "+--------v--------+ +--------v--------+ |-------------------------|\n", "| LeafNode | | InnerNode | | tag: 2 |\n", "| tag: 2 | | tag: 1 | | padding: [0, 0, 0] |\n", "|-----------------| |-----------------| | owner_slot: 1 |\n", "| owner_slot: 2 | | prefix_len: 5 | | time_in_force: 2 |\n", "| time_in_force: 3| | key: 7 | | key: 7 |\n", "| key: 15 | | children: [5] | | owner: [0x21..], |\n", "| owner: [0x21..]| +--------+--------+ | quantity: 22 |\n", "| quantity: 50 | | | timestamp: 12345 |\n", "| timestamp: 6789| | | peg_limit: 0 |\n", "+-----------------+ | | client_order_id: 0 |\n", " +-------v--------+ +-------------------------+\n", " | FreeNode |\n", " |----------------|\n", " | tag: 3 |\n", " | padding: [0,] |\n", " | next: 0 |\n", " | reserved: [0,]|\n", " +----------------+\n", "```\n", "\n", "## Table of Contents\n", "\n", "* [**Introduction**](#Introduction)\n", " * [**1. OpenBook V2 📘**](#1.-OpenBook-V2-📘)\n", " * [**2. Architecture Overview 🏛️**](#2.-Architecture-Overview-🏛️)\n", " * [**3. OpenBook V2 Central Limit Orderbook (CLOB) 📚**](#3.-OpenBook-V2-Central-Limit-Orderbook-(CLOB)-📚)\n", " * [**4. Order Matching and Execution ⚖️**](#4.-Order-Matching-and-Execution-⚖️)\n", " * [**5. Events Iteration and Processing 🔄**](#5.-Events-Iteration-and-Processing-🔄)\n", " * [**6. Orders Tree Operations 🌳**](#6.-Orders-Tree-Operations-🌳)\n", "* [**Conclusion**](#Conclusion)\n", "\n", "\n", "### Introduction\n", "\n", "Welcome to the fifth chapter of our series exploring the world of Web3 in Rust, with a particular focus on the Solana blockchain. In the previous chapters, we explored the internals of OpenBook v1. This chapter will take an in-depth look at each component of the OpenBook V2 Central Limit Order Book (CLOB), examining their roles, interactions, and implementation details within the OpenBook v2 DEX. We'll also highlight the key differences and similarities between OpenBook v1 and v2.\n", "\n", "Let's start with an introduction to OpenBook V2." ] }, { "cell_type": "markdown", "id": "018d729a-6ca3-4f21-bbf4-5ec56548c9ff", "metadata": {}, "source": [ "### 1. OpenBook V2 📘\n", "\n", "Like OpenBook V1, OpenBook V2 is a DEX program built on the [**Solana blockchain**](https://solana.com/), aimed at enabling efficient and transparent trading of digital assets. Leveraging Solana's high throughput and low transaction costs, OpenBook V2 facilitates peer-to-peer trading through its decentralized [**order book**](https://www.investopedia.com/terms/o/order-book.asp) mechanism. This chapter explores the architecture, operation, and key components of OpenBook V2, highlighting its role in [**the DeFi**](https://www.investopedia.com/decentralized-finance-defi-5113835) ecosystem.\n", "\n", "Like OpenBook V1, OpenBook V2 operates as a decentralized order book where buyers and sellers can interact directly, eliminating the need for intermediaries like traditional exchanges. This setup ensures that trades are executed peer-to-peer using programs, aka [**smart contracts**](https://ethereum.org/en/developers/docs/smart-contracts/) in the solana world, deployed on the Solana blockchain. By leveraging Solana's infrastructure, OpenBook V2 achieves near-instant transaction finality and supports a high volume of trades per second." ] }, { "cell_type": "markdown", "id": "2b64f170-7f28-4e86-91eb-a447bdc63c8a", "metadata": {}, "source": [ "### 2. Architecture Overview 🏛️\n", "\n", "```sh\n", " +------------------------------------------------+\n", " | OpenBook V2 Components |\n", " +------------------------------------------------+\n", " | +--------------------------+ |\n", " | | Order Book | |\n", " | +--------------------------+ |\n", " | | Event Heap | |\n", " | +--------------------------+ |\n", " | | Market | |\n", " | +--------------------------+ |\n", " | | Open Orders Indexer | |\n", " | +--------------------------+ |\n", " | | Open Orders Account | |\n", " | +--------------------------+ |\n", " | | Oracle | |\n", " | +--------------------------+ |\n", " +------------------------------------------------+\n", "```\n", "\n", "The architecture of OpenBook V2 consists of several key components/modules:\n", "\n", "- [**Orderbook**](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/orderbook/book.rs): Manages the actual order matching and bookkeeping operations, including bid and ask sides.\n", "\n", "- [**Event Heap**](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/orderbook/heap.rs): Stores pending events such as order fills, ensuring sequential processing.\n", "\n", "- [**Market**](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/market.rs): Stores market-specific parameters and handles order validation and execution logic.\n", "\n", "- [**Open Orders Account**](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/open_orders_account.rs): Tracks [owner's account](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/open_orders_account.rs#L17), [their orders](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/open_orders_account.rs#L36), and [positions](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/open_orders_account.rs#L34), among other components.\n", "\n", "- [**Open Orders Indexer**](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/open_orders_indexer.rs): This component is designed to index open orders in the DEX, ensuring efficient access and management of orders. Each Open Order account must be created under at least one indexer account.\n", "\n", "- [**Oracle**](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/oracle.rs): Oracles provide market data and are essential for accurate pricing and other market operations. The oracle module is extensive, with configurations and implementations for different types of oracles such as Pyth, SwitchboardV1, SwitchboardV2, and RaydiumCLMM.\n", "\n", "The [**`orderbook/book`**](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/orderbook/book.rs) module in OpenBook V2 serves as the core component responsible for matching buy and sell orders. It maintains separate records for [**bids (buy orders)**](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/book.rs#L21) and [**asks (sell orders)**](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/book.rs#L22), organized by price, asks from lowest to highest and bids from highest to lowest price. This structure ensures fair execution of trades based on the best available prices, enhancing market efficiency and [**liquidity**](https://www.investopedia.com/terms/l/liquidity.asp).\n", "\n", "```rust\n", "pub struct Orderbook<'a> {\n", " pub bids: RefMut<'a, BookSide>,\n", " pub asks: RefMut<'a, BookSide>,\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/book.rs#L20-L23)\n", "\n", "The [**`EventHeap`**](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/heap.rs#L18) object is designed to handle various types of events that occur within the OpenBook V2 DEX.\n", "\n", "```rust\n", "pub struct EventHeap {\n", " pub header: EventHeapHeader,\n", " pub nodes: [EventNode; MAX_NUM_EVENTS as usize],\n", " pub reserved: [u8; 64],\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/heap.rs#L18)\n", "\n", "These events include fill and out events:\n", "\n", "```rust\n", "pub struct OutEvent {\n", " pub event_type: u8,\n", " pub side: u8,\n", " pub owner_slot: u8,\n", " padding0: [u8; 5],\n", " pub timestamp: u64,\n", " pub seq_num: u64,\n", " pub owner: Pubkey,\n", " pub quantity: i64,\n", " padding1: [u8; 80],\n", "}\n", "\n", "pub struct FillEvent {\n", " pub event_type: u8,\n", " pub taker_side: u8,\n", " pub maker_out: u8,\n", " pub maker_slot: u8,\n", " pub padding: [u8; 4],\n", " pub timestamp: u64,\n", " pub market_seq_num: u64,\n", " pub maker: Pubkey,\n", " pub maker_timestamp: u64,\n", " pub taker: Pubkey,\n", " pub taker_client_order_id: u64,\n", " pub price: i64,\n", " pub peg_limit: i64,\n", " pub quantity: i64,\n", " pub maker_client_order_id: u64,\n", " pub reserved: [u8; 8],\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/heap.rs#L314)\n", "\n", "By maintaining a dedicated heap for events, and like its v1 predecessor, OpenBook V2 ensures that all events are processed in a timely and orderly fashion, which is critical for maintaining market integrity and responsiveness.\n", "\n", "The [**`Market`**](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/market.rs#L21) object is a fundamental part of the OpenBook V2 DEX, responsible for storing and managing market-specific parameters. These parameters include the number of decimals for base and quote tokens, lot sizes, fee rates, and other crucial settings.\n", "\n", "```rust\n", "pub struct Market {\n", " /// PDA bump\n", " pub bump: u8,\n", "\n", " /// Number of decimals used for the base token.\n", " ///\n", " /// Used to convert the oracle's price into a native/native price.\n", " pub base_decimals: u8,\n", " pub quote_decimals: u8,\n", "\n", " pub padding1: [u8; 5],\n", "\n", " // Pda for signing vault txs\n", " pub market_authority: Pubkey,\n", "\n", " /// No expiry = 0. Market will expire and no trading allowed after time_expiry\n", " pub time_expiry: i64,\n", "\n", " /// Admin who can collect fees from the market\n", " pub collect_fee_admin: Pubkey,\n", " /// Admin who must sign off on all order creations\n", " pub open_orders_admin: NonZeroPubkeyOption,\n", " /// Admin who must sign off on all event consumptions\n", " pub consume_events_admin: NonZeroPubkeyOption,\n", " /// Admin who can set market expired, prune orders and close the market\n", " pub close_market_admin: NonZeroPubkeyOption,\n", "\n", " /// Name. Trailing zero bytes are ignored.\n", " pub name: [u8; 16],\n", "\n", " /// Address of the BookSide account for bids\n", " pub bids: Pubkey,\n", " /// Address of the BookSide account for asks\n", " pub asks: Pubkey,\n", " /// Address of the EventHeap account\n", " pub event_heap: Pubkey,\n", "\n", " /// Oracles account address\n", " pub oracle_a: NonZeroPubkeyOption,\n", " pub oracle_b: NonZeroPubkeyOption,\n", " /// Oracle configuration\n", " pub oracle_config: OracleConfig,\n", "\n", " /// Number of quote native in a quote lot. Must be a power of 10.\n", " ///\n", " /// Primarily useful for increasing the tick size on the market: A lot price\n", " /// of 1 becomes a native price of quote_lot_size/base_lot_size becomes a\n", " /// ui price of quote_lot_size*base_decimals/base_lot_size/quote_decimals.\n", " pub quote_lot_size: i64,\n", "\n", " /// Number of base native in a base lot. Must be a power of 10.\n", " ///\n", " /// Example: If base decimals for the underlying asset is 6, base lot size\n", " /// is 100 and and base position lots is 10_000 then base position native is\n", " /// 1_000_000 and base position ui is 1.\n", " pub base_lot_size: i64,\n", "\n", " /// Total number of orders seen\n", " pub seq_num: u64,\n", "\n", " /// Timestamp in seconds that the market was registered at.\n", " pub registration_time: i64,\n", "\n", " /// Fees\n", " ///\n", " /// Fee (in 10^-6) when matching maker orders.\n", " /// maker_fee < 0 it means some of the taker_fees goes to the maker\n", " /// maker_fee > 0, it means no taker_fee to the maker, and maker fee goes to the referral\n", " pub maker_fee: i64,\n", " /// Fee (in 10^-6) for taker orders, always >= 0.\n", " pub taker_fee: i64,\n", "\n", " /// Total fees accrued in native quote\n", " pub fees_accrued: u128,\n", " /// Total fees settled in native quote\n", " pub fees_to_referrers: u128,\n", "\n", " /// Referrer rebates to be distributed\n", " pub referrer_rebates_accrued: u64,\n", "\n", " /// Fees generated and available to withdraw via sweep_fees\n", " pub fees_available: u64,\n", "\n", " /// Cumulative maker volume (same as taker volume) in quote native units\n", " pub maker_volume: u128,\n", "\n", " /// Cumulative taker volume in quote native units due to place take orders\n", " pub taker_volume_wo_oo: u128,\n", "\n", " pub base_mint: Pubkey,\n", " pub quote_mint: Pubkey,\n", "\n", " pub market_base_vault: Pubkey,\n", " pub base_deposit_total: u64,\n", "\n", " pub market_quote_vault: Pubkey,\n", " pub quote_deposit_total: u64,\n", "\n", " pub reserved: [u8; 128],\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/market.rs#L21)\n", "\n", "The Market struct also implements logic for validating and executing orders, ensuring that all trades adhere to the market's rules and regulations. The struct is designed to support various administrative roles, manage fees, handle oracles for price feeds, and maintain state information such as order counts and timestamps. Additionally, the Market struct includes fields for vault management, fee accrual and distribution, and oracle configuration to provide accurate pricing data.\n", "\n", "The [**OpenOrdersAccount**](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/open_orders_account.rs#L16) object in the OpenBook V2 program tracks individual associated tokens accounts. Each account contains information about the owner's open orders, balances, and trade history. This component is crucial for ensuring that users can manage their orders and assets effectively, and for the system to accurately track and settle trades.\n", "\n", "```rust\n", "pub struct OpenOrdersAccount {\n", " pub owner: Pubkey,\n", " pub market: Pubkey,\n", "\n", " pub name: [u8; 32],\n", "\n", " // Alternative authority/signer of transactions for a openbook account\n", " pub delegate: NonZeroPubkeyOption,\n", "\n", " pub account_num: u32,\n", "\n", " pub bump: u8,\n", "\n", " // Introducing a version as we are adding a new field bids_quote_lots\n", " pub version: u8,\n", "\n", " pub padding: [u8; 2],\n", "\n", " pub position: Position,\n", "\n", " pub open_orders: [OpenOrder; MAX_OPEN_ORDERS],\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/open_orders_account.rs#L16)" ] }, { "cell_type": "markdown", "id": "9e6f930c-28ff-4d24-bc8b-880c8ac81f90", "metadata": {}, "source": [ "### 3. OpenBook V2 Central Limit Orderbook (CLOB) 📚\n", "\n", "```sh\n", "+------------------------------------------------+ +------------------------------------------------+\n", "| Bids (Buy Orders) | | Asks (Sell Orders) |\n", "| |-------------------| | | |-------------------| |\n", "| | Order 1: $105 | | | | Order 1: $110 | |\n", "| |-------------------| | | |-------------------| |\n", "| | Order 2: $100 | | | | Order 2: $115 | |\n", "| |-------------------| | | |-------------------| |\n", "| ... | | ... |\n", "+------------------------------------------------+ +------------------------------------------------+\n", "```\n", "\n", "Just like OpenBook V1, and as previously mentioned, the central limit orderbook in OpenBook V2 organizes buy (bids) and sell (asks) orders by price. This structure ensures fair execution of trades based on the best available prices. Each side of the orderbook, bids, and asks, is managed independently but interacts during order matching.\n", "\n", "The orderbook maintains two main structures:\n", "\n", "- **Bids**: Contains buy orders sorted from highest to lowest price.\n", " \n", "- **Asks**: Contains sell orders sorted from lowest to highest price.\n", "\n", "These structures use efficient data structures like critbit-trees to enable quick insertion, deletion, and lookup operations of orders, crucial for [**high-frequency trading**](https://www.investopedia.com/terms/h/high-frequency-trading.asp) environments. When a new order is placed, the DEX checks against the opposite side (bids for sell orders and asks for buy orders) to find matches based on price and order size.\n", "\n", "The efficient matching engine within the orderbook ensures that trades are executed at the best possible prices. For instance, if a buy order is placed at a price higher than the current best sell price, the program will immediately match the buy order with the sell order, ensuring that both parties get the best possible deal. This matching process continues until all possible matches are made, ensuring optimal market liquidity.\n", "\n", "Additionally, the orderbook handles various types of orders, including [**limit orders**](https://www.investopedia.com/terms/l/limitorder.asp), and [**market orders**](https://www.investopedia.com/terms/m/marketorder.asp).\n", "\n", "```rust\n", "ub enum PlaceOrderType {\n", " /// Take existing orders up to price, max_base_quantity and max_quote_quantity.\n", " /// If any base_quantity or quote_quantity remains, place an order on the book\n", " Limit = 0,\n", "\n", " /// Take existing orders up to price, max_base_quantity and max_quote_quantity.\n", " /// Never place an order on the book.\n", " ImmediateOrCancel = 1,\n", "\n", " /// Never take any existing orders, post the order on the book if possible.\n", " /// If existing orders can match with this order, do nothing.\n", " PostOnly = 2,\n", "\n", " /// Ignore price and take orders up to max_base_quantity and max_quote_quantity.\n", " /// Never place an order on the book.\n", " ///\n", " /// Equivalent to ImmediateOrCancel with price=i64::MAX.\n", " Market = 3,\n", "\n", " /// If existing orders match with this order, adjust the price to just barely\n", " /// not match. Always places an order on the book.\n", " PostOnlySlide = 4,\n", "\n", " /// Take existing orders up to price, max_base_quantity and max_quote_quantity.\n", " /// Abort if partially executed, never place an order on the book.\n", " FillOrKill = 5,\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/order_type.rs#L20)\n", "\n", "Each order type has specific rules for execution and prioritization, contributing to a dynamic and flexible trading environment. For instance, limit orders are executed only at the specified price or better, ensuring precise execution conditions. In contrast, market orders execute immediately at the best available price without price restrictions. The `PlaceOrderType` enum further outlines various order behaviors such as `ImmediateOrCancel`, which prioritizes immediate execution over order placement on the book, and `FillOrKill`, which mandates complete order execution or none at all, with no order placement. These distinctions allow traders to choose strategies that best suit their trading objectives and market conditions." ] }, { "cell_type": "markdown", "id": "c1e703e5-9a22-43be-aa7d-463381bc499a", "metadata": {}, "source": [ "### 4. Order Matching and Execution ⚖️\n", "\n", "```sh\n", " +------------------------------------------------+\n", " | Matching Engine |\n", " +------------------------------------------------+\n", " | +-----------------+ |\n", " | | Order Validation| |\n", " | +-----------------+ |\n", " | +-----------------+ |\n", " | | Order Matching | |\n", " | +-----------------+ |\n", " | +-----------------+ |\n", " | | Trade Execution | |\n", " | +-----------------+ |\n", " +------------------------------------------------+\n", "```\n", "\n", "The matching process is the core component of OpenBook V2 that handles order matching and execution. It compares incoming orders with existing orders in the order book to find matches based on price and order size.\n", "\n", "#### Order Validation\n", "\n", "The order validation step ensures the incoming order meets all required criteria, such as minimum size and price limits, and verifies the owner's balance. If the order fails any of these checks, it is rejected and not added to the order book.\n", "\n", "```rust\n", "// Validation checks\n", "require_gte!(market.max_base_lots(), order_max_base_lots, OpenBookError::InvalidInputLotsSize);\n", "require_gte!(market.max_quote_lots(), order_max_quote_lots, OpenBookError::InvalidInputLotsSize);\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/book.rs#L99-L109)\n", "\n", "These checks ensure the order size and price are within acceptable limits. The function also verifies that the user has sufficient funds to place the order.\n", "\n", "#### Order Matching\n", "\n", "In the order matching step, the process compares the incoming order with existing orders on the opposite side of the order book. The matching engine uses a price priority algorithm to find the best possible matches, ensuring that orders are matched based on the best available prices and the order in which they were received.\n", "\n", "```rust\n", "// Iterate through book and match against this new order.\n", "for best_opposing in opposing_bookside.iter_all_including_invalid(now_ts, oracle_price_lots) {\n", " if remaining_base_lots == 0 || remaining_quote_lots == 0 {\n", " break;\n", " }\n", "\n", " if !best_opposing.is_valid() {\n", " // Remove the order from the book\n", " continue;\n", " }\n", "\n", " if !side.is_price_within_limit(best_opposing_price, price_lots) {\n", " break;\n", " }\n", "\n", " // Matching logic\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/book.rs#L124)\n", "\n", "This loop iterates over the order book to find the best matching orders based on the given order price.\n", "\n", "#### Trade Execution\n", "\n", "The trade execution step involves executing the matched trades, and updating the order book. This process includes removing matched orders from the order book, and recording the trade in the event heap.\n", "\n", "```rust\n", "// Execute matched trades\n", "process_fill_event(fill, market, event_heap, remaining_accs, &mut number_of_processed_fill_events)?;\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/book.rs#L249)\n", "\n", "This function call processes the fill event, updating the necessary state and ensuring all events are handled correctly." ] }, { "cell_type": "markdown", "id": "786fd6ed-cc0f-4bc0-96fb-a8a29bf91a59", "metadata": {}, "source": [ "### 5. Events Iteration and Processing 🔄\n", "\n", "```sh\n", " +------------------------------------------------+\n", " | EventHeap Mechanism |\n", " +------------------------------------------------+\n", " | +-----------------+ |\n", " | | Event Storage | |\n", " | +-----------------+ |\n", " | +-----------------+ |\n", " | | Event Iteration | |\n", " | +-----------------+ |\n", " | +-----------------+ |\n", " | |Event Processing | |\n", " | +-----------------+ |\n", " +------------------------------------------------+\n", "```\n", "\n", "#### EventHeap Mechanism\n", "\n", "The [`EventHeap`](https://github.com/openbook-dex/openbook-v2/blob/master/programs/openbook-v2/src/state/orderbook/heap.rs) in OpenBook V2 handles event processing and settlement. It stores pending events like order fills, ensuring they are processed sequentially.\n", "\n", "The `EventHeap` operates through the following steps:\n", "\n", "1. **Event Storage**: Incoming events are added to the EventHeap. \n", "\n", "```rust\n", "pub fn push_back(&mut self, value: AnyEvent) {\n", " // Ensure the heap is not full\n", " assert!(!self.is_full());\n", "\n", " // Get the slot to store the new event\n", " let slot = self.header.free_head;\n", " self.header.free_head = self.nodes[slot as usize].next;\n", "\n", " // Update pointers for the circular buffer / linked list\n", " let new_next: u16;\n", " let new_prev: u16;\n", "\n", " if self.is_empty() {\n", " new_next = slot;\n", " new_prev = slot;\n", "\n", " self.header.used_head = slot;\n", " } else {\n", " new_next = self.header.used_head;\n", " new_prev = self.nodes[new_next as usize].prev;\n", "\n", " self.nodes[new_prev as usize].next = slot;\n", " self.nodes[new_next as usize].prev = slot;\n", " }\n", "\n", " // Increment counters and store the fill event\n", " self.header.incr_count();\n", " self.header.incr_event_id();\n", " self.nodes[slot as usize].event = value;\n", " self.nodes[slot as usize].next = new_next;\n", " self.nodes[slot as usize].prev = new_prev;\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/heap.rs#L76)\n", "\n", "2. **Event Processing**: Events are processed in a FIFO (First-In, First-Out) manner, ensuring timely execution.\n", "\n", "```rust\n", "pub fn pop_front(&mut self) -> Result {\n", " self.delete_slot(self.header.used_head()) // Process the first event in the heap\n", "}\n", "\n", "pub fn delete_slot(&mut self, slot: usize) -> Result {\n", " // Check if the slot is valid and the heap is not empty\n", " if slot >= self.nodes.len() || self.is_empty() || self.nodes[slot].is_free() {\n", " return Err(OpenBookError::SomeError.into());\n", " }\n", "\n", " // Update pointers for the circular linked list\n", " let prev_slot = self.nodes[slot].prev;\n", " let next_slot = self.nodes[slot].next;\n", " let next_free = self.header.free_head;\n", "\n", " self.nodes[prev_slot as usize].next = next_slot;\n", " self.nodes[next_slot as usize].prev = prev_slot;\n", "\n", " // Update the head if necessary\n", " if self.header.count() == 1 {\n", " self.header.used_head = NO_NODE;\n", " } else if self.header.used_head() == slot {\n", " self.header.used_head = next_slot;\n", " };\n", "\n", " // Decrement counters and mark the slot as free\n", " self.header.decr_count();\n", " self.header.free_head = slot.try_into().unwrap();\n", " self.nodes[slot].next = next_free;\n", " self.nodes[slot].prev = NO_NODE;\n", "\n", " // Return the processed event\n", " Ok(self.nodes[slot].event)\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/heap.rs#L105)\n", "\n", "3. **Event Iteration**: Iterate over the events for further processing or querying. This step ensures all events can be accessed in a sequence.\n", "\n", "```rust\n", "pub fn iter(&self) -> impl Iterator {\n", " EventHeapIterator {\n", " heap: self,\n", " index: 0,\n", " slot: self.header.used_head(),\n", " }\n", "}\n", "\n", "struct EventHeapIterator<'a> {\n", " heap: &'a EventHeap,\n", " index: usize,\n", " slot: usize,\n", "}\n", "\n", "impl<'a> Iterator for EventHeapIterator<'a> {\n", " type Item = (&'a AnyEvent, usize);\n", " fn next(&mut self) -> Option {\n", " if self.index == self.heap.len() {\n", " None\n", " } else {\n", " let current_slot = self.slot;\n", " self.slot = self.heap.nodes[current_slot].next as usize;\n", " self.index += 1;\n", " Some((&self.heap.nodes[current_slot].event, current_slot))\n", " }\n", " }\n", "}\n", "```\n", "\n", "**Reference**: [openbook-dex/openbook-v2](https://github.com/openbook-dex/openbook-v2/blob/f3e17421e675b083b584867594bf3cf4f675d156/programs/openbook-v2/src/state/orderbook/heap.rs#L135)\n", "\n", "The `EventHeap` is designed to handle a high volume of events efficiently. By processing events in a FIFO manner, the system ensures that all events are handled in the order they are received, maintaining the integrity and fairness of the exchange. This is particularly important in high-frequency trading environments, where the timely processing of events is critical for market efficiency." ] }, { "cell_type": "markdown", "id": "d5c3e435-4dbb-49eb-8d97-a5e34b7b8f4c", "metadata": {}, "source": [ "### 6. Orders Tree Operations 🌳\n", "\n", "Similar to OpenBook v1, tree node insertion and removal follow a comparable process.\n", "\n", "#### Insert Operation: Insert LeafNode with Key 8\n", "\n", "#### Before Insertion:\n", "\n", "```sh\n", " +-----------------------+\n", " | RootNode |\n", " |-----------------------|\n", " | tag: 0 |\n", " | padding: [0, 0, 0] |\n", " | prefix_len: 2 |\n", " | key: 10 |\n", " | children: [0, 1] |\n", " | child_earliest_expiry|\n", " | [1844674407370..] |\n", " | reserved: [0,..] |\n", " +-----------------------+\n", " |\n", " +---------------+---------------+\n", " | |\n", " +-----------v-----------+ +------------v------------+\n", " | InnerNode | | InnerNode |\n", " | tag: 1 | | tag: 1 |\n", " | padding: [0, 0, 0] | | padding: [0, 0, 0] |\n", " |-----------------------| |-------------------------|\n", " | prefix_len: 3 | | prefix_len: 4 |\n", " | key: 5 | | key: 6 |\n", " | children: [2, 2] | | children: [4, 5] |\n", " | child_earliest_expiry| | child_earliest_expiry |\n", " | [184467440737095, ..] | | [184467440737095, ..] |\n", " | reserved: [0, ...] | | reserved: [0, ...] |\n", " +--------+--------------+ +-------------+-----------+\n", " | |\n", " +-----------v----------+ +----------v--------------+\n", " | LeafNode | | LeafNode |\n", " |----------------------| |-------------------------|\n", " | tag: 2 | | tag: 2 |\n", " | padding: [0, 0, 0] | | padding: [0, 0, 0] |\n", " | owner_slot: 1 | | owner_slot: 1 |\n", " | time_in_force: 2 | | time_in_force: 2 |\n", " | key: 7 | | key: 8 |\n", " | owner: [0x21..], | | owner: [0x21..], |\n", " | quantity: 22 | | quantity: 50 |\n", " | timestamp: 12345 | | timestamp: 6789 |\n", " | peg_limit: 0 | | peg_limit: 0 |\n", " | client_order_id: 0 | | client_order_id: 0 |\n", " +----------------------+ +-------------------------+\n", " |\n", " +---------------v---------------+\n", " | FreeNode |\n", " |-------------------------------|\n", " | tag: 3 |\n", " | padding: [0,] |\n", " | next: 0 |\n", " | reserved: [0,] |\n", " +-------------------------------+\n", "```\n", "\n", "#### After Insertion (Insert LeafNode with Key 8):\n", "\n", "```sh\n", " +-----------------------+\n", " | RootNode |\n", " |-----------------------|\n", " | tag: 0 |\n", " | padding: [0, 0, 0] |\n", " | prefix_len: 2 |\n", " | key: 10 |\n", " | children: [0, 1] |\n", " | child_earliest_expiry|\n", " | [1844674407370..] |\n", " | reserved: [0,..] |\n", " +-----------------------+\n", " |\n", " +---------------+---------------+\n", " | |\n", " +-----------v-----------+ +------------v------------+\n", " | InnerNode | | LeafNode |\n", " | tag: 1 | |-------------------------|\n", " | padding: [0, 0, 0] | | tag: 2 |\n", " |-----------------------| | padding: [0, 0, 0] |\n", " | prefix_len: 3 | | owner_slot: 1 |\n", " | key: 5 | | time_in_force: 2 |\n", " | children: [2, 2] | | key: 7 |\n", " | child_earliest_expiry| | owner: [0x21..], |\n", " | [184467440737095, ..] | | quantity: 22 |\n", " | reserved: [0, ...] | | timestamp: 12345 |\n", " +--------+--------------+ | peg_limit: 0 |\n", " | | client_order_id: 0 |\n", " +-----------v----------+ +-------------------------+\n", " | LeafNode |\n", " |----------------------|\n", " | tag: 2 |\n", " | padding: [0, 0, 0] |\n", " | owner_slot: 1 |\n", " | time_in_force: 2 |\n", " | key: 8 |\n", " | owner: [0x21..], |\n", " | quantity: 50 |\n", " | timestamp: 6789 |\n", " | peg_limit: 0 |\n", " | client_order_id: 0 |\n", " +----------------------+\n", " |\n", " +---------------v----------------+\n", " | FreeNode |\n", " |-------------------------------|\n", " | tag: 3 |\n", " | padding: [0,] |\n", " | next: 0 |\n", " | reserved: [0,] |\n", " +-------------------------------+\n", "```\n", "\n", "#### Remove Operation: Remove LeafNode with Key 7\n", "\n", "#### Before Removal:\n", "\n", "```sh\n", " +-----------------------+\n", " | RootNode |\n", " |-----------------------|\n", " | tag: 0 |\n", " | padding: [0, 0, 0] |\n", " | prefix_len: 2 |\n", " | key: 10 |\n", " | children: [0, 1] |\n", " | child_earliest_expiry|\n", " | [1844674407370..] |\n", " | reserved: [0,..] |\n", " +-----------------------+\n", " |\n", " +---------------+---------------+\n", " | |\n", " +-----------v-----------+ +------------v------------+\n", " | InnerNode | | LeafNode |\n", " | tag: 1 | |-------------------------|\n", " | padding: [0, 0, 0] | | tag: 2 |\n", " |-----------------------| | padding: [0, 0, 0] |\n", " | prefix_len: 3 | | owner_slot: 1 |\n", " | key: 5 | | time_in_force: 2 |\n", " | children: [2, 2] | | key: 8 |\n", " | child_earliest_expiry| | owner: [0x21..], |\n", " | [184467440737095, ..] | | quantity: 50 |\n", " | reserved: [0, ...] | | timestamp: 6789 |\n", " +--------+--------------+ | peg_limit: 0 |\n", " | | client_order_id: 0 |\n", " +-----------v----------+ +-------------------------+\n", " | LeafNode |\n", " |----------------------|\n", " | tag: 2 |\n", " | padding: [0, 0, 0] |\n", " | owner_slot: 1 |\n", " | time_in_force: 2 |\n", " | key: 7 |\n", " | owner: [0x21..], |\n", " | quantity: 50 |\n", " | timestamp: 6789 |\n", " | peg_limit: 0 |\n", " | client_order_id: 0 |\n", " +----------------------+\n", " |\n", " +---------------v---------------+\n", " | FreeNode |\n", " |-------------------------------|\n", " | tag: 3 |\n", " | padding: [0,] |\n", " | next: 0 |\n", " | reserved: [0,] |\n", " +-------------------------------+\n", "```\n", "\n", "#### After Removal (Remove LeafNode with Key 7):\n", "\n", "```sh\n", " +-----------------------+\n", " | RootNode |\n", " |-----------------------|\n", " | tag: 0 |\n", " | padding: [0, 0, 0] |\n", " | prefix_len: 2 |\n", " | key: 10 |\n", " | children: [0, 1] |\n", " | child_earliest_expiry|\n", " | [1844674407370..] |\n", " | reserved: [0,..] |\n", " +-----------------------+\n", " |\n", " +---------------+---------------+\n", " | |\n", " +-----------v-----------+ +------------v------------+\n", " | InnerNode | | LeafNode |\n", " | tag: 1 | |-------------------------|\n", " | padding: [0, 0, 0] | | tag: 2 |\n", " |-----------------------| | padding: [0, 0, 0] |\n", " | prefix_len: 3 | | owner_slot: 1 |\n", " | key: 5 | | time_in_force: 2 |\n", " | children: [2, 2] | | key: 8 |\n", " | child_earliest_expiry| | owner: [0x21..], |\n", " | [184467440737095, ..] | | quantity: 50 |\n", " | reserved: [0, ...] | | timestamp: 6789 |\n", " +--------+--------------+ | peg_limit: 0 |\n", " | | client_order_id: 0 |\n", " | +-------------------------+\n", " |\n", " |\n", " |\n", " +---------------v---------------+\n", " | FreeNode |\n", " |-------------------------------|\n", " | tag: 3 |\n", " | padding: [0,] |\n", " | next: 0 |\n", " | reserved: [0,] |\n", " +-------------------------------+\n", "```" ] }, { "cell_type": "markdown", "id": "bb559e5a-40e6-40e2-abeb-498d9f474a5f", "metadata": {}, "source": [ "---\n", "### Conclusion\n", "\n", "In conclusion, the evolution from OpenBook V1 to OpenBook V2 marks a substantial leap forward in decentralized exchange technology. OpenBook V2 improved the tree-based data structures for order management by introducing tree nodes fields such as `child_earliest_expiry`, enhancing scalability and performance in handling high-frequency trading volumes. By integrating advanced order matching algorithms and real-time event processing capabilities, OpenBook V2 ensures optimal trade execution efficiency and market liquidity. Overall, OpenBook V2 stands as a pivotal innovation in the DEX world, aimed to redefine the standards of DeFi and empower traders with enhanced trading capabalities.\n", "\n", "---\n", "---" ] } ], "metadata": { "kernelspec": { "display_name": "Rust", "language": "rust", "name": "rust" }, "language_info": { "codemirror_mode": "rust", "file_extension": ".rs", "mimetype": "text/rust", "name": "Rust", "pygment_lexer": "rust", "version": "" } }, "nbformat": 4, "nbformat_minor": 5 }