Rust 维护 Lighter 交易所本地 Orderbook 练习——从 220µs 到 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"
}

+-----------------------------------------------------------------------+
|                    🧠 核心思路: "直观映射" (Intuitive)                 |
|             "JSON 是什么样，我就定义什么样的 Struct，存下来再说！"          |
+-----------------------------------------------------------------------+
        |
        |  1. JSON 输入 (Incoming Data)
        V
+--------------------------+
| JSON Object              |
|  {                       |
|    "type": "...",        |     serde 自动反序列化
|    "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                                                 |
|                                                             |
| [!] 列表直接转 Vec (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 🐢)  |
+----------------------------+    +----------------------------+
       ^                                ^
       |                                |
       +--- "既然是 List，那就存俩 List 本地更新完事" ---+

#[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 是一样的道理
    }
}

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 耗时： {:?}", duration);
println!(
    "update_order_book_data 平均耗时： {:?}",
    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 加权耗时： {:?}, 实际总耗时： {:?}",
    ratio_duration, duration
);
println!(
    "update_order_book_data 加权平均耗时： {:?}",
    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. 指针跳转)
                                 v
                        +---------------------------+
                        | Heap Addr: 0x1000 (Root)  | <--- 第一次内存读取
                        |---------------------------|      (耗时 ~70ns)
                        | Keys: [88000, 89000...]   |
                        | Children Ptrs:            |
                        |  [0x5000, 0x9000...]      |
                        +------------+--------------+
                                     |
                                     | (2. 指针跳转 - Pointer Chasing)
                                     v
                        +---------------------------+
                        | Heap Addr: 0x9000 (Node)  | <--- 第二次内存读取
                        |---------------------------|      (耗时 ~70ns)
                        | Keys: [88700, 88800...]   |
                        | Children Ptrs:            |
                        |  [0x2000, 0x3000...]      |
                        +------------+--------------+
                                     |
                                     | (3. 指针跳转 - Pointer Chasing)
                                     v
                        +---------------------------+
                        | Heap Addr: 0x3000 (Leaf)  | <--- 第三次内存读取
                        |---------------------------|      (耗时 ~70ns)
                        | Key: 88797.9              |
                        | Value: 0.03268            | <--- 终于找到数据
                        +---------------------------+

const TICK_SIZE_MULTIPLIER: f64 = 10.0; // 对应 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 {
    // 加 0.5 是为了处理浮点数精度误差 (epsilon)，例如 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; // 流动性没了
                    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;
        
        // 剩余部分和上面 Bids 差不多
    }
}