DEV Community

Cover image for Price first, time second: a limit order book in about 50 lines of Rust
Ritik Kumar
Ritik Kumar

Posted on

Price first, time second: a limit order book in about 50 lines of Rust

#rust #100daysofsolana #web3

Last week I posted a quiz: three sell orders, one buy order, who gets filled first? Here is the answer, in Rust.

Most order books follow one rule: the better price goes first, and at the same price the earlier order goes first.

rust
use std::collections::{BTreeMap, VecDeque};

#[derive(Default)]
struct Book {
    // price -> queue of (id, size), oldest order at the front
    asks: BTreeMap<u64, VecDeque<(&'static str, u64)>>,
}

impl Book {
    fn sell(&mut self, id: &'static str, price: u64, size: u64) {
        self.asks.entry(price).or_default().push_back((id, size));
    }

    // buy `size` units, paying at most `limit`
    fn buy(&mut self, mut size: u64, limit: u64) {
        while size > 0 {
            let Some(mut level) = self.asks.first_entry() else { break };
            let price = *level.key();
            if price > limit { break; }
            let queue = level.get_mut();
            let (id, avail) = queue.front_mut().unwrap();
            let qty = size.min(*avail);
            println!("{id}: {qty} @ {price}");
            size -= qty;
            *avail -= qty;
            if *avail == 0 { queue.pop_front(); }
            if queue.is_empty() { level.remove(); }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

The BTreeMap keeps prices sorted, so the best price is always first. Each price holds a VecDeque, so the oldest order is always first. There is no timestamp anywhere. The queue is the clock.


Now A, B and C sell, then someone buys 10 with a limit of 100.20:
Enter fullscreen mode Exit fullscreen mode 
fn main() {
    // prices are integer ticks: 10010 = 100.10
    let mut book = Book::default();
    book.sell("A", 10020, 5);
    book.sell("B", 10010, 3);
    book.sell("C", 10010, 4);
    book.buy(10, 10020);
}
Enter fullscreen mode Exit fullscreen mode 
B: 3 @ 10010
C: 4 @ 10010
A: 3 @ 10020
Enter fullscreen mode Exit fullscreen mode
Enter fullscreen mode Exit fullscreen mode

A arrived first and was filled last. B beat C because both were at 100.10 and B was earlier. And the buyer paid 100.10 on seven units even though the limit was 100.20.

This toy has no cancel, no sell side and no balance check. On Solana the book also has to fit into one account with a fixed compute budget, so the same rule has to work inside fixed slots.

I work on Privora, where the book stays public and the position behind an order stays private (devnet, test funds).

If you have put an order book onchain, which limit hit you first, account size or compute?

Top comments (0)