7 ms·

Why use a Vec instead of a B-Tree?

by evdubs 7y ago

evdubs 7y ago
Also, why use Uuids instead of a pair of user_id: u64, order_id: u64?
- cstein2 7y ago
  Leaking the number of orders seemed like a bad idea
  - evdubs 7y ago
    Are you planning to hook your order book up to a data feed like, for example, binance[1] to see how your book performs? [1] https://github.com/binance-exchange/binance-official-api-docs/blob/master/web-socket-streams.md#how-to-manage-a-local-order-book-correctly https://github.com/binance-exchange/binance-official-api-doc...
    - cstein2 7y ago
      Yeah I was planning on playing around with the performance/optimizing it. Didn't know about that binance data feed though, thanks.
cstein2 7y ago
I was imagining inserts at an unoccupied price level would be relatively rare in normal order book operation, so a Vec just seemed simpler
- seanhunter 7y ago
  They aren't that unusual on an absolute basis but relative to the number of orders in a stock they are quite rare (iirc - it's been a while since I was directly involved in this). This is a cool project btw - I'm looking for my first chance to really sink my teeth into rust so found it interesting. A few non-rust observations (you probably know all this but kept your orderbook simple which is totally cool but just in case): An actual order book has a "tick ladder" which specifies which price points are valid for a given ticker on a given venue. This means you actually know all the possible prices ahead of time. If you ever wanted to productionize this you could probably take advantage of that and make a custom data structure that used the fact that you had all the keys preset and did the insert and lookup in O(1). Secondly in real life the matching logic is quite a bit more complex because of order flags and venue logic. If you're just covering US venues you don't need to worry about venues because of Reg NMS but anywhere else you'll want the order books to actually by venue and symbol not just symbol. Order flags interfere with matching in a number of ways. Firstly a normal limit order will partially match up to the limit and any remaining quantity will sit on the book waiting to be matched. You can flag the order as "fill or kill" to say fill the whole order or nothing and you can flag it as "immediate or cancel" to say don't put any remaining quantity passively on the book. There are many other order flags but those are probably the most important ones for matching. Secondly on many venues orders can have an iceberg order type which means that only the "tip" quantity gets shown on the book but they will actually match up to a larger quantity at that price. Finally you can add a "minimum executed quantity" on any passive orders to prevent pinging (information leakage). This will only match with incoming orders bigger than the MXQ, so messes with the normal price, time ordering. Orders behind that order could match first potentially. MXQ is more important for dark venues or order types so maybe you don't need to consider it.
  - cstein2 7y ago
    Thanks for the info! I definitely did not know all of that :). I do work at a crypto exchange, but on the custody/stablecoin side, not the exchange team. Can you elaborate a little on the "pinging" process to extract information? Sounds interesting
    - seanhunter 7y ago
      You are most welcome. I'd be somewhat surprised if crypto exchanges supported all the same stuff I mentioned - it's based on my history on equity exchanges and I'd expect crypto to be different. Anyway the way MXQ and pinging works is imagine you have an orderbook where passive orders are not visible to other participants (ie the venue is dark or you have a grey venue where some orders can be flagged as dark). It's possible fro participants to pay to learn what orders are in the book by making some very small aggressive orders and seeing where they match. In the world of equities this would be buy 1 share agressively, sell 1 share agressively with a limit in each case. This is called "pinging" because it's like ICMP ping discovering whether hosts are alive. The concept in crypto (if it applies) would be the smallest quantity the exchange allows you to buy or sell. Assuming the venue supports it, you can prevent your dark orders matching these pings by setting an MXQ. If your MXQ is 100 say, they would need to buy 100 shares for your order to match. You would set the size to a point where you don't mind giving up the information about where your order level is because the match is meaningful enough.
globular-toast 7y ago
Why a B-tree if it's supposed to be in-memory? A heap would be easier to implement and more efficient.
- evdubs 7y ago
  Rust provides a built in B-tree[1] and it offers this over a binary search tree to avoid pointer chasing. With respect to heaps, are you thinking that a BinaryHeap[2] could be used here? I don't see how such a structure allows you to arbitrarily remove/update orders in the book. Looks like you can just insert arbitrary orders by price (using push(x)) and then get the best bid or offer (using pop()). Am I missing something? If the API was changed to be more like a binary search tree, you don't think the pointer chasing would reduce performance for larger books? [1] https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht... [2] https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html https://doc.rust-lang.org/std/collections/struct.BinaryHeap....
  - globular-toast 7y ago
    I missed the fact that it was supposed to be more than just a priority queue. I would have said binary search tree instead of heap, but it makes sense now I know that B-tree is built in.
logicchains 7y ago
Not the OP, but presumably to minimise the amount of jumping around in memory. Best orderbook is a small matrix, if you can get away with it (for trading you often don't need the whole orderbook, or at least don't need the whole thing on the hot path, but for an exchange obviously there's less scope for approximations).
- evdubs 7y ago
  Assuming you're doing some sort of strategy where the order book is important, like market making or hedging another position, it seems kind of dangerous not to keep a full book, no? If the market starts to move and your limited book starts to represent a lack of bids or offers, that doesn't seem to be a great idea at first glance.
  - logicchains 7y ago
    In a product with a big tick size, to react to any single event you'll probably only need to know what's happening on the top two or three price levels (as it's super unlikely to move more than that in a single market data update). Then after reacting you can update your big, slow book and generate a new fast, approximate book from that, in preparation for the next market data update.
    - evdubs 7y ago
      I agree that can make sense for something like ES, but what about crypto? ;) Edit: maybe non-penny-pilot options trading > $3 are a better example of a product with a large tick size.
      - logicchains 7y ago
        For crypto the network overhead and variance in the exchange probably makes the performance of the order book implementation irrelevant, unless it's horribly slow, haha.
        7y ago

Why use a Vec instead of a B-Tree?

by evdubs 7y ago

Why use a Vec instead of a B-Tree?

evdubs 7y ago

Also, why use Uuids instead of a pair of user_id: u64, order_id: u64?

cstein2 7y ago
Leaking the number of orders seemed like a bad idea
- evdubs 7y ago
  Are you planning to hook your order book up to a data feed like, for example, binance[1] to see how your book performs? [1] https://github.com/binance-exchange/binance-official-api-docs/blob/master/web-socket-streams.md#how-to-manage-a-local-order-book-correctly https://github.com/binance-exchange/binance-official-api-doc...
  - cstein2 7y ago
    Yeah I was planning on playing around with the performance/optimizing it. Didn't know about that binance data feed though, thanks.

cstein2 7y ago

I was imagining inserts at an unoccupied price level would be relatively rare in normal order book operation, so a Vec just seemed simpler

seanhunter 7y ago
They aren't that unusual on an absolute basis but relative to the number of orders in a stock they are quite rare (iirc - it's been a while since I was directly involved in this). This is a cool project btw - I'm looking for my first chance to really sink my teeth into rust so found it interesting. A few non-rust observations (you probably know all this but kept your orderbook simple which is totally cool but just in case): An actual order book has a "tick ladder" which specifies which price points are valid for a given ticker on a given venue. This means you actually know all the possible prices ahead of time. If you ever wanted to productionize this you could probably take advantage of that and make a custom data structure that used the fact that you had all the keys preset and did the insert and lookup in O(1). Secondly in real life the matching logic is quite a bit more complex because of order flags and venue logic. If you're just covering US venues you don't need to worry about venues because of Reg NMS but anywhere else you'll want the order books to actually by venue and symbol not just symbol. Order flags interfere with matching in a number of ways. Firstly a normal limit order will partially match up to the limit and any remaining quantity will sit on the book waiting to be matched. You can flag the order as "fill or kill" to say fill the whole order or nothing and you can flag it as "immediate or cancel" to say don't put any remaining quantity passively on the book. There are many other order flags but those are probably the most important ones for matching. Secondly on many venues orders can have an iceberg order type which means that only the "tip" quantity gets shown on the book but they will actually match up to a larger quantity at that price. Finally you can add a "minimum executed quantity" on any passive orders to prevent pinging (information leakage). This will only match with incoming orders bigger than the MXQ, so messes with the normal price, time ordering. Orders behind that order could match first potentially. MXQ is more important for dark venues or order types so maybe you don't need to consider it.
- cstein2 7y ago
  Thanks for the info! I definitely did not know all of that :). I do work at a crypto exchange, but on the custody/stablecoin side, not the exchange team. Can you elaborate a little on the "pinging" process to extract information? Sounds interesting
  - seanhunter 7y ago
    You are most welcome. I'd be somewhat surprised if crypto exchanges supported all the same stuff I mentioned - it's based on my history on equity exchanges and I'd expect crypto to be different. Anyway the way MXQ and pinging works is imagine you have an orderbook where passive orders are not visible to other participants (ie the venue is dark or you have a grey venue where some orders can be flagged as dark). It's possible fro participants to pay to learn what orders are in the book by making some very small aggressive orders and seeing where they match. In the world of equities this would be buy 1 share agressively, sell 1 share agressively with a limit in each case. This is called "pinging" because it's like ICMP ping discovering whether hosts are alive. The concept in crypto (if it applies) would be the smallest quantity the exchange allows you to buy or sell. Assuming the venue supports it, you can prevent your dark orders matching these pings by setting an MXQ. If your MXQ is 100 say, they would need to buy 100 shares for your order to match. You would set the size to a point where you don't mind giving up the information about where your order level is because the match is meaningful enough.

globular-toast 7y ago

Why a B-tree if it's supposed to be in-memory? A heap would be easier to implement and more efficient.

evdubs 7y ago
Rust provides a built in B-tree[1] and it offers this over a binary search tree to avoid pointer chasing. With respect to heaps, are you thinking that a BinaryHeap[2] could be used here? I don't see how such a structure allows you to arbitrarily remove/update orders in the book. Looks like you can just insert arbitrary orders by price (using push(x)) and then get the best bid or offer (using pop()). Am I missing something? If the API was changed to be more like a binary search tree, you don't think the pointer chasing would reduce performance for larger books? [1] https://doc.rust-lang.org/std/collections/struct.BTreeMap.html https://doc.rust-lang.org/std/collections/struct.BTreeMap.ht... [2] https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html https://doc.rust-lang.org/std/collections/struct.BinaryHeap....
- globular-toast 7y ago
  I missed the fact that it was supposed to be more than just a priority queue. I would have said binary search tree instead of heap, but it makes sense now I know that B-tree is built in.

logicchains 7y ago

Not the OP, but presumably to minimise the amount of jumping around in memory. Best orderbook is a small matrix, if you can get away with it (for trading you often don't need the whole orderbook, or at least don't need the whole thing on the hot path, but for an exchange obviously there's less scope for approximations).

evdubs 7y ago
Assuming you're doing some sort of strategy where the order book is important, like market making or hedging another position, it seems kind of dangerous not to keep a full book, no? If the market starts to move and your limited book starts to represent a lack of bids or offers, that doesn't seem to be a great idea at first glance.
- logicchains 7y ago
  In a product with a big tick size, to react to any single event you'll probably only need to know what's happening on the top two or three price levels (as it's super unlikely to move more than that in a single market data update). Then after reacting you can update your big, slow book and generate a new fast, approximate book from that, in preparation for the next market data update.
  - evdubs 7y ago
    I agree that can make sense for something like ES, but what about crypto? ;) Edit: maybe non-penny-pilot options trading > $3 are a better example of a product with a large tick size.
    - logicchains 7y ago
      For crypto the network overhead and variance in the exchange probably makes the performance of the order book implementation irrelevant, unless it's horribly slow, haha.
      - 7y ago