feat: Rewrite order matching strategy #2539

holzeis · 2024-05-15T14:22:19Z

Refactors the current trading component into a clearly separated orderbook component and a trade execution component. The linking part is the ExecutableMatch which can be derived from the matches stored into the database.

At the moment we assume optimistically that the trade execution will succeed. However, we should consider that a pending match may never get filled or it fails at execution in such a scenario we would need to rollback the matched orders.

An overview of the changes:

Adds the order id to the trade entry so we can link which order created the trade.
Allows for orders to get partially matched and update the matches table accordingly
Matched limit orders are created as Filled from the get go since we do not execute them with our own maker.
(Partially) Matched limit orders are not deleted anymore, but the quantity is updated to how much has already been mapped. (e.g. if an open limit order of $1000 gets deleted with $300 matched it will be updated to Taken with a quantity of $300)

Example of a matches table after opening and closing a position of $3576. Note the maker generates $1000 orders.

orderbook=# select execution_price, quantity, order_id, match_order_id from matches where trader_id='032752136072951607b66dd85f236363efab91b315b1c4fc8d9530ee873875108a' and match_state='Filled' order by created_at;
 execution_price | quantity |               order_id               |            match_order_id            
-----------------+----------+--------------------------------------+--------------------------------------
           60001 |     1000 | 42dd8a30-a20d-4640-bddd-f5467a638d28 | 9acc7260-0f24-405e-ad84-550a797b4464
           60001 |     1000 | 42dd8a30-a20d-4640-bddd-f5467a638d28 | c486a21c-312e-4ae0-ab35-38a8e93d07d5
           60001 |     1000 | 42dd8a30-a20d-4640-bddd-f5467a638d28 | e30ff0dc-4f8a-4888-a3ea-cddf63c94179
           60001 |      576 | 42dd8a30-a20d-4640-bddd-f5467a638d28 | adae6065-d78a-4ed6-bab3-9852f395ef67
           59999 |     1000 | a6be5b42-8817-40f7-8f86-0615df33c57a | 19811f8f-7fe7-4dd1-9b3a-72f24a0fcee5
           59999 |     1000 | a6be5b42-8817-40f7-8f86-0615df33c57a | 6cf3b7bd-2652-4590-afed-f15ece0a1ded
           59999 |     1000 | a6be5b42-8817-40f7-8f86-0615df33c57a | 0c8b6575-2ba2-4e37-8aa2-9c0e8beb055d
           59999 |      576 | a6be5b42-8817-40f7-8f86-0615df33c57a | 17fcb395-4434-4ca8-9cb2-4ca75ec73063
(8 rows)

Example of updated limit orders when deleted.

orderbook=# select order_id, price, direction, quantity, order_type from orders where order_id in ('19811f8f-7fe7-4dd1-9b3a-72f24a0fcee5', '6cf3b7bd-2652-4590-afed-f15ece0a1ded', '0c8b6575-2ba2-4e37-8aa2
               order_id               | price | direction | quantity | order_type 
--------------------------------------+-------+-----------+----------+------------
 19811f8f-7fe7-4dd1-9b3a-72f24a0fcee5 | 59999 | long      |     1000 | limit
 6cf3b7bd-2652-4590-afed-f15ece0a1ded | 59999 | long      |     1000 | limit
 0c8b6575-2ba2-4e37-8aa2-9c0e8beb055d | 59999 | long      |     1000 | limit
 17fcb395-4434-4ca8-9cb2-4ca75ec73063 | 59999 | long      |      576 | limit
(4 rows)

TODO:

Do not await on database transactions when interacting with the orderbook.
Process any order update through the orderbook component.
Rework matching logic to not immediately mutate on every single order.

luckysori

I like the idea of defining an orderbook component which keeps the orders in memory, can be optimised for speed (eventually) and has exclusive access to certain DB tables. I think this is the vision suggested by this PR.

Also, I think the last patch is a continuation of an earlier patch. By default I assume that a PR should be reviewed patch by patch, but in this case I think I wasted some time reviewing an earlier version of the same thing. In the future, if you know this is the case, I would appreciate it if you let me know in the PR description or just squashed some patches.

coordinator/src/orderbook/mod.rs

luckysori · 2024-05-17T06:46:29Z

coordinator/src/orderbook/mod.rs

+                let order = if !matches.is_empty() {
+                    // order has been at least partially matched.
+                    let matched_quantity = matches.iter().map(|m| m.quantity).sum();
+
+                    orders::set_order_state_partially_taken(&mut conn, order_id, matched_quantity)


❓I don't understand what's going on here. Why do we need to do this when a limit order is being removed?

Because it might have been partially matched already.

Today we are setting an order to deleted regardless if it has been matched or not. IMHO we should only set open orders to deleted, but not taken ones.

However how to deal with orders that have been partially matched? I opted to set the state to taken and reduce the quantity to the amount that has already been matched.

Shouldn't we do that earlier and not on deletion though. Also, why do we go directly against the database instead of updating the state in the ordebook cache? It seems like the state is only in the DB? Why is that?

Also, why do we go directly against the database instead of updating the state in the ordebook cache? It seems like the state is only in the DB? Why is that?

Both states are updated, first the database and then the orderbook.

Shouldn't we do that earlier and not on deletion though.

Can you elaborate on that, when do you think this should happen?

coordinator/src/orderbook/mod.rs

crates/xxi-node/src/commons/message.rs

bonomat

What's the status of this PR? Do we want to continue with it?

coordinator/migrations/2024-05-10-102426_add_order_id_to_trades/up.sql

coordinator/src/orderbook/db/orders.rs

coordinator/src/orderbook/mod.rs

holzeis · 2024-05-22T04:35:25Z

What's the status of this PR? Do we want to continue with it?

I will continue to work on this after the lightning onboarding flow.

This will allow us to implement partial order matching, by summing the quantity of trades related to an order.

This is already done by the maker, also expired orders are not considered for matching.

Refactors the current trading component into a clearly separated orderbook component and a trade execution component. The linking part is the `ExecutableMatch` which can be derived from the matches stored into the database. At the moment we assume optimistically that the trade execution will succeed. However, we should consider that a pending match may never get filled or it fails at execution in such a scenario we would need to rollback the matched orders.

The order and the matches are persisted by async actors. It can happen that the market order has not yet been persisted when the match is processed. Thus it could happen that the matches table is persisted before the order has been persisted, which resulted in a foreign key violation. By dropping the foreign key we don't care if the order is already persisted and can continue with eventual consistency. I think this is the better option than to synchronize the two inserts as we are anyways aiming for decoupling the orderbook from the coordinator.

holzeis · 2024-06-07T12:33:34Z

@luckysori @bonomat this PR turned into more refactoring than originally anticipated, although not all issues are addressed yet I think its in a good spot to get into main, before tackling limit orders.

Below shows the new design of the orderbook.

The orderbook component is solely responsible for the order. It's now the only place where the order gets manipulated.
The match executor takes a matched order and stores that into a matches table. this table keeps record if the execution actually succeeded or not. The orderbook doesn't care anymore if the order execution fails or succeeds. From the point of view of the orderbook, the order has been taken. Eventually we might want to re-add a failed order, but for now we simply ignore it.
The new design also goes a step forward towards decoupling the orderbook from the coordinator.
The OderState::Matched is now deprecated as the matches table takes care of tracking if an order / match is still pending or completed (filled or failed).

There are certainly still some minor things that I'd like to clean up, but its in a good state for your review.

holzeis requested review from bonomat and luckysori May 15, 2024 14:22

holzeis self-assigned this May 15, 2024

holzeis linked an issue May 15, 2024 that may be closed by this pull request

Rewrite order-matching strategy #2270

Open

holzeis force-pushed the feat/rewrite-order-matching-strategy branch from d9a8203 to 77d9bcc Compare May 15, 2024 14:29

luckysori reviewed May 17, 2024

View reviewed changes

bonomat reviewed May 22, 2024

View reviewed changes

holzeis force-pushed the feat/rewrite-order-matching-strategy branch 2 times, most recently from 167979c to 2143ffd Compare May 27, 2024 14:44

holzeis force-pushed the feat/rewrite-order-matching-strategy branch 3 times, most recently from 602eca1 to f8e9991 Compare June 4, 2024 14:28

holzeis added 6 commits June 7, 2024 14:15

chore: Add order id to trades

00a9b35

This will allow us to implement partial order matching, by summing the quantity of trades related to an order.

chore: Remove delete expired orders

8ca29e4

This is already done by the maker, also expired orders are not considered for matching.

refactor: Rename orderbook message to trader message

8cf4dae

chore: Remove unused db functions

37a7a73

holzeis force-pushed the feat/rewrite-order-matching-strategy branch from f8e9991 to 51e49ec Compare June 7, 2024 12:25

holzeis requested review from bonomat and luckysori June 7, 2024 12:33

github-actions bot added the Stale label Jul 8, 2024

github-actions bot closed this Jul 14, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

feat: Rewrite order matching strategy #2539

feat: Rewrite order matching strategy #2539

holzeis commented May 15, 2024 •

edited

Loading

luckysori left a comment •

edited

Loading

luckysori May 17, 2024

holzeis May 17, 2024

luckysori May 17, 2024

holzeis Jun 3, 2024

holzeis Jun 3, 2024

bonomat left a comment

holzeis commented May 22, 2024

holzeis commented Jun 7, 2024

feat: Rewrite order matching strategy #2539

feat: Rewrite order matching strategy #2539

Conversation

holzeis commented May 15, 2024 • edited Loading

luckysori left a comment • edited Loading

Choose a reason for hiding this comment

luckysori May 17, 2024

Choose a reason for hiding this comment

holzeis May 17, 2024

Choose a reason for hiding this comment

luckysori May 17, 2024

Choose a reason for hiding this comment

holzeis Jun 3, 2024

Choose a reason for hiding this comment

holzeis Jun 3, 2024

Choose a reason for hiding this comment

bonomat left a comment

Choose a reason for hiding this comment

holzeis commented May 22, 2024

holzeis commented Jun 7, 2024

holzeis commented May 15, 2024 •

edited

Loading

luckysori left a comment •

edited

Loading