Rust Practice: Maintaining Lighter Exchange Local Orderbook — A Note on Going from 220µs to 492ns

{
    "type": "subscribe",
    "channel": "order_book/{MARKET_INDEX}"
}

{
  "channel": "order_book:1",
  "offset": 12837513,
  "order_book": {
    "code": 0,
    "asks": [
      {
        "price": "87194.4",
        "size": "1.03736"
      },
      {
        "price": "87194.5",
        "size": "0.02980"
      }
    ],
    "bids": [
      {
        "price": "87194.0",
        "size": "0.00020"
      },
      {
        "price": "87191.6",
        "size": "0.03676"
      }
    ],
    "offset": 12837513,
    "nonce": 3901590619
  },
  "timestamp": 1766059985139,
  "type": "subscribed/order_book"
}

{
  "channel": "order_book:1",
  "offset": 12837556,
  "order_book": {
    "code": 0,
    "asks": [
      {
        "price": "87208.2",
        "size": "0.00000"
      }
    ],
    "bids": [
      {
        "price": "87173.2",
        "size": "0.01389"
      }
    ],
    "offset": 12837556,
    "nonce": 3901590736
  },
  "timestamp": 1766059985417,
  "type": "update/order_book"
}

+-----------------------------------------------------------------------+
|             🧠 Core Idea: "Intuitive Mapping" (Intuitive)              |
|   "Whatever the JSON looks like, I'll define that Struct and save it!" |
+-----------------------------------------------------------------------+
        |
        |  1. JSON Input (Incoming Data)
        V
+--------------------------+
| JSON Object              |
|  {                       |
|    "type": "...",        |     serde automatic deserialization
|    "bids": [...],        | ========================>
|    "asks": [...]         |
|  }                       |
+--------------------------+
        |
        |  2. Rust Memory Layout
        V
+-------------------------------------------------------------+
| struct LighterOrderBook (Root)                              |
+-------------------------------------------------------------+
| - channel:   Option<String>                                 |
| - offset:    Option<u64>                                    |
| - type_:     String                                         |
| - timestamp: Option<u64>                                    |
|                                                             |
| [!] Nested Layer                                            |
| - order_book: Option -------------------------------------> +
+-------------------------------------------------------------+
                                                              |
          +---------------------------------------------------+
          |
          v
+-------------------------------------------------------------+
| struct LighterOrderBookData                                 |
+-------------------------------------------------------------+
| - code: u32                                                 |
|                                                             |
| [!] List -> Vec                                             |
| - asks: Vec<LighterOrderBookEntry> ---+                     |
| - bids: Vec<LighterOrderBookEntry> ---|---+                 |
+-------------------------------------------------------------+
                                        |   |
          +-----------------------------+   |
          |                                 |
          v                                 v
+----------------------------+    +----------------------------+
| Entry (Ask)                |    | Entry (Bid)                |
+----------------------------+    +----------------------------+
| - price: String (Heap 🐢)  |    | - price: String (Heap 🐢)  |
| - size:  String (Heap 🐢)  |    | - size:  String (Heap 🐢)  |
+----------------------------+    +----------------------------+
       ^                                ^
       |                                |
       +--- "Since it's a List, I'll save two Lists and update locally" ---+

#[derive(Debug, Deserialize)]
pub struct LighterOrderBookEntry {
    pub price: String,
    pub size: String,
}

#[derive(Debug, Deserialize)]
pub struct LighterOrderBookData {
    pub code: u32,
    pub asks: Vec<LighterOrderBookEntry>,
    pub bids: Vec<LighterOrderBookEntry>,
}

#[derive(Debug, Deserialize)]
pub struct LighterOrderBook {
    pub channel: Option<String>,
    pub offset: Option<u64>,
    pub order_book: Option<LighterOrderBookData>,
    #[serde(rename = "type")]
    pub type_: String,
    pub timestamp: Option<u64>,
}

fn update_order_book_data(
    order_book_data: &mut LighterOrderBookData,
    updated_entries: &LighterOrderBookData,
) {
    for update_order in &updated_entries.asks {
        let new_size_float: f64 =
            update_order.size.parse().unwrap();

        if new_size_float == 0.0 {
            order_book_data.asks.retain(|order| {
                order.price != update_order.price
            });
        } else if let Some(existing_order) = order_book_data
            .asks
            .iter_mut()
            .find(|order| order.price == update_order.price)
        {
            existing_order.size = update_order.size.clone();
        } else {
            order_book_data.asks.push(
                LighterOrderBookEntry {
                    price: update_order.price.clone(),
                    size: update_order.size.clone(),
                },
            );
        }
    }

    for update_order in &updated_entries.bids {
        // bids work the same way
    }
}

let start_time = Instant::now();
update_order_book_data(order_book_data, update_order_book);
let duration = start_time.elapsed();
total_parsed_txs += 1;
total_parse_time_cost += duration;
let average_parse_time_cost =
    total_parse_time_cost / total_parsed_txs;
println!("update_order_book_data time cost: {:?}", duration);
println!(
    "update_order_book_data average time cost: {:?}",
    average_parse_time_cost
);

#[derive(Debug, Deserialize, Default)]
pub struct FastLighterOrderBookData {
    pub code: u32,
    // Key: Price, Value: Size
    pub asks: BTreeMap<OrderedFloat<f64>, String>,
    pub bids: BTreeMap<OrderedFloat<f64>, String>,
}

fn update_order_book_data(
    local_order_book_data: &mut FastLighterOrderBookData,
    updated_entries: &LighterOrderBookData,
) {
    for update_order_entry in &updated_entries.asks {
        let new_size_float: f64 =
            update_order_entry.size.parse().unwrap();
        let new_price_float_key = OrderedFloat(
            update_order_entry.price.parse().unwrap(),
        );

        if new_size_float == 0.0 {
            local_order_book_data
                .asks
                .remove(&new_price_float_key);
        } else {
            local_order_book_data.asks.insert(
                new_price_float_key,
                update_order_entry.size.clone(),
            );
        }
    }

    for update_order_entry in &updated_entries.bids {
        let new_size_float: f64 =
            update_order_entry.size.parse().unwrap();
        let new_price_float_key = OrderedFloat(
            update_order_entry.price.parse().unwrap(),
        );

        if new_size_float == 0.0 {
            local_order_book_data
                .bids
                .remove(&new_price_float_key);
        } else {
            local_order_book_data.bids.insert(
                new_price_float_key,
                update_order_entry.size.clone(),
            );
        }
    }
}

let update_order_book_total_length =
update_order_book.asks.len()
    + update_order_book.bids.len();
let start_time = Instant::now();
update_order_book_data(
    &mut local_lighter_order_book,
    update_order_book,
);
let duration = start_time.elapsed();
let ratio_duration = duration
    / update_order_book_total_length.try_into().unwrap();
total_parsed_txs += 1;
total_parse_time_cost += ratio_duration;
let average_parse_time_cost =
    total_parse_time_cost / total_parsed_txs;
println!(
    "update_order_book_data weighted time cost: {:?}, actual total time: {:?}",
    ratio_duration, duration
);
println!(
    "update_order_book_data weighted average time cost: {:?}",
    average_parse_time_cost
);

BTreeMap<OrderedFloat<f64>, String>

#[derive(Debug, Deserialize, Default)]
pub struct FastLighterOrderBookData {
    pub code: u32,
    // Key: Price, Value: Size
    pub asks: BTreeMap<OrderedFloat<f64>, f64>,
    pub bids: BTreeMap<OrderedFloat<f64>, f64>,
}

+------------------+
|   Stack          |
+------------------+
|  root_ptr      ----------------+
+------------------+             | (1. Pointer Jump)
                                 v
                        +---------------------------+
                        | Heap Addr: 0x1000 (Root)  | <--- 1st Memory Read
                        |---------------------------|      (Time ~70ns)
                        | Keys: [88000, 89000...]   |
                        | Children Ptrs:            |
                        |  [0x5000, 0x9000...]      |
                        +------------+--------------+
                                     |
                                     | (2. Pointer Jump - Pointer Chasing)
                                     v
                        +---------------------------+
                        | Heap Addr: 0x9000 (Node)  | <--- 2nd Memory Read
                        |---------------------------|      (Time ~70ns)
                        | Keys: [88700, 88800...]   |
                        | Children Ptrs:            |
                        |  [0x2000, 0x3000...]      |
                        +------------+--------------+
                                     |
                                     | (3. Pointer Jump - Pointer Chasing)
                                     v
                        +---------------------------+
                        | Heap Addr: 0x3000 (Leaf)  | <--- 3rd Memory Read
                        |---------------------------|      (Time ~70ns)
                        | Key: 88797.9              |
                        | Value: 0.03268            | <--- Finally found data
                        +---------------------------+

const TICK_SIZE_MULTIPLIER: f64 = 10.0; // corresponds to tick_size 0.1
const MAX_PRICE_CAPACITY: usize = 2_000_000;

#[derive(Debug, Deserialize, Default)]
pub struct FlatLighterOrderBookData {
    pub code: u32,
    // {"price":"88797.9","size":"0.03268"}
    // ->
    // asks[887979] -> "0.03268"
    pub asks: Vec<f64>,
    pub bids: Vec<f64>,

    pub best_ask_idx: usize,
    pub best_bid_idx: usize,
}

#[inline(always)]
fn price_to_index(price: f64) -> usize {
    // Adding 0.5 is to handle floating point precision errors (epsilon), e.g., 0.999999 -> 1.0
    (price * TICK_SIZE_MULTIPLIER + 0.5) as usize
}

pub fn update(&mut self, price: f64, size: f64, is_bid: bool) {
    let price_idx = Self::price_to_index(price);

    if price_idx >= MAX_PRICE_CAPACITY {
        eprintln!("Error: Price {} out of bounds", price);
        return;
    }

    if is_bid {
        self.bids[price_idx] = size;

        if size > 0.0 {
            if price_idx > self.best_bid_idx {
                self.best_bid_idx = price_idx;
            }
            // Same as current best_bid_idx and size == 0
            // best_bid_idx is deleted
        } else if price_idx == self.best_bid_idx {
            let mut scan_price_idx = price_idx;

            loop {
                if scan_price_idx == 0 {
                    self.best_bid_idx = 0; // liquidity is gone
                    break;
                }
                scan_price_idx -= 1;
                if self.bids[scan_price_idx] > 0.0 {
                    self.best_bid_idx = scan_price_idx;
                    break;
                }
            }
        }
    } else {
        self.asks[price_idx] = size;
        
        // The rest is similar to Bids above
    }
}