clob_engine/order_book/
matching_engine.rs

1use crate::order_book::{
2    orderbook::OrderBook, types::{
3        BookDepth, CancelOrder, CancelOutcome, GlobalOrderRegistry, ModifyOrder, ModifyOutcome, NewOrder, OrderLocation, OrderNode, OrderType
4    }
5};
6use anyhow::{Context, anyhow};
7use std::collections::HashMap;
8use tracing::{Span, instrument};
9use uuid::Uuid;
10
11#[derive(Debug)]
12pub struct MatchingEngine {
13    _book: HashMap<Uuid, OrderBook>,
14    _global_registry: GlobalOrderRegistry,
15}
16
17impl MatchingEngine {
18
19    pub fn new() -> Self{
20        Self { _book: HashMap::new(), _global_registry: GlobalOrderRegistry::new() }
21    }
22
23    #[instrument(
24        name = "get_orderbook",
25        skip(self),
26        fields(
27            order_id = %global_order_id,
28        ),
29    )]
30    fn get_orderbook(
31        &mut self,
32        global_order_id: Uuid,
33        span: &Span
34    ) -> Option<(usize, bool,Uuid, &mut OrderBook)> {
35        let order_location = match self._global_registry.get_details(&global_order_id){
36            Some(location) => {
37                location
38            }
39            None => {
40                span.record("reason", "order not found in global registry");
41                return None;
42            }
43        };
44        let Some(book) = self._book.get_mut(&order_location.security_id) else {
45            span.record("reason", "orderbook doesn't exist");
46            return None;
47        };
48        Some((order_location.order_index, order_location.is_buy_side,order_location.security_id, book))
49    }
50
51    pub fn modify(
52        &mut self,
53        global_order_id: Uuid,
54        new_price: Option<u32>,
55        new_qty: Option<u32>,
56        span: &Span,
57    ) -> Result<(), anyhow::Error> {
58        let _gaurd = span.enter();
59        let (order_index, is_buy_side,security_id, orderbook) = self
60            .get_orderbook(global_order_id, span)
61            .context("Could not find the orderbook")?;
62        if let Ok(potential_modfication) = orderbook.modify_order(
63            global_order_id,
64            ModifyOrder {
65                new_price,
66                order_index,
67                is_buy_side,
68                new_quantity: new_qty,
69            },
70        ) {
71            if let Some(modification_result) = potential_modfication {
72                match modification_result {
73                    ModifyOutcome::Both {
74                        new_price,
75                        new_initial_qty,
76                        old_current_qty,
77                    } => {
78                        span.record("modify_outcome", "price & qty");
79                        if let Some(_) = self._global_registry.delete(&global_order_id){
80                            let _ = self.match_order(
81                            NewOrder {
82                                engine_order_id: global_order_id,
83                                price: Some(new_price),
84                                initial_quantity: new_initial_qty,
85                                current_quantity : old_current_qty,
86                                is_buy_side,
87                                security_id,
88                                order_type: OrderType::Limit,
89                            },
90                            span);
91                            return Ok(());
92                        }
93                        span.record("intermediate_error", "Failed to delete from global registry");
94                    },
95                    ModifyOutcome::Repriced { new_price, old_initial_qty, old_current_qty } => 
96                        {
97                        span.record("modify_outcome", "price");
98                        if let Some(_) = self._global_registry.delete(&global_order_id){
99                            let _ = self.match_order(
100                            NewOrder {
101                                engine_order_id: global_order_id,
102                                price: Some(new_price),
103                                initial_quantity: old_initial_qty,
104                                current_quantity : old_current_qty,
105                                is_buy_side,
106                                security_id,
107                                order_type: OrderType::Limit,
108                            },
109                            span);
110                            return Ok(());
111                        }
112                        span.record("intermediate_error", "Failed to delete from global registry");
113                    },
114                    ModifyOutcome::Requantized { old_price, new_initial_qty, old_current_qty } => {
115                        span.record("modify_outcome", "qty");
116                        if let Some(_) = self._global_registry.delete(&global_order_id){
117                            let _ = self.match_order(
118                            NewOrder {
119                                engine_order_id: global_order_id,
120                                price: Some(old_price),
121                                initial_quantity: new_initial_qty,
122                                current_quantity : old_current_qty,
123                                is_buy_side,
124                                security_id,
125                                order_type: OrderType::Limit,
126                            }, span);
127                            return Ok(());
128                        }
129                        span.record("intermediate_error", "Failed to delete from global registry");
130                    },
131                    ModifyOutcome::Inplace => {
132                        span.record("modify_outcome", "qty reduction");
133                        return Ok(());
134                    }
135                }
136            }
137        } else {
138            return Ok(());
139        }
140        Ok(())
141    }
142
143    pub fn cancel(&mut self, global_order_id: Uuid, span: &Span) -> Result<CancelOutcome, anyhow::Error>{
144        let (order_index, is_buy_side,_, orderbook) = self
145            .get_orderbook(global_order_id, span)
146            .context("Could not find the orderbook")?;
147        if let Err(_) = orderbook.cancel_order(global_order_id, CancelOrder{is_buy_side, order_index}){
148            span.record("reason", "orderbook cancellation failed");
149            span.record("success_status", false);
150            return Ok(CancelOutcome::Failed);
151        }; 
152        if let Some(_) = self._global_registry.delete(&global_order_id){
153            span.record("success_status", true);
154            return Ok(CancelOutcome::Success)
155        };
156        span.record("reason", "Registry cancellation failed");
157        span.record("success_status", false);
158        Ok(CancelOutcome::Failed)
159    }
160
161    pub fn depth(&self, security_id : Uuid, levels_count :Option<u32>, span: &Span ) -> Result<BookDepth, anyhow::Error>{
162        let _gaurd = span.enter();
163        span.record("security_id", security_id.to_string());
164        let Some(order_book) = self._book.get(&security_id) else {
165            span.record("status", "failed");
166            span.record("reason", "orderbook doesn't exist");
167            return Err(anyhow!(""))
168        };
169        match order_book.depth(levels_count){
170            Ok(book_depth) => {
171                span.record("status", "success");
172                span.record("reason", "None");
173                Ok(book_depth)
174            },
175            Err(e) => Err(anyhow!("{}", e))
176        }
177    }
178
179    pub fn match_order(&mut self, order: NewOrder, span: &Span) -> Result<Option<usize>, anyhow::Error> {
180        
181        let _gaurd = span.enter();
182
183        let orderbook = match self._book.get_mut(&order.security_id){
184            Some(orderbook) => {
185                orderbook
186            }
187            None => {
188                self._book.entry(order.security_id).or_insert(OrderBook::new(1))
189            }
190        };
191
192        if !order.is_buy_side {
193            // for ASK order
194            match order.order_type {
195                OrderType::Market(None) => {
196                    // need to immediatly execute the order on the best of other half
197                    let mut fill_quantity = order.initial_quantity;
198                    let mut levels_consumed = 0;
199                    let mut orders_touched = 0;
200                    while fill_quantity > 0 {
201                        let remove_node: bool;
202                        {
203                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
204                                break;
205                            };
206                            let price_level = price_node.get_mut();
207                            while price_level.total_quantity > 0 && fill_quantity > 0 {
208                                if let Some(head_idx) = price_level.head{
209
210                                    let first_order_node =
211                                        orderbook.bid.order_pool[head_idx].as_mut().unwrap();
212                                    if fill_quantity >= first_order_node.current_quantity {
213                                        fill_quantity -= first_order_node.current_quantity;
214                                        price_level.total_quantity -= first_order_node.current_quantity;
215                                        let next = first_order_node.next;
216                                        orderbook.bid.order_pool[head_idx] = None;
217                                        orderbook.bid.free_list.push(head_idx);
218                                        orders_touched += 1;
219                                        if let Some(next_order_idx) = next {
220                                            price_level.head = Some(next_order_idx);
221                                        } else {
222                                            span.record("reason", "exhausted");
223                                            price_level.total_quantity = 0;
224                                            break;
225                                        }
226                                    } else {
227                                        first_order_node.current_quantity -= fill_quantity;
228                                        price_level.total_quantity -= fill_quantity;
229                                        fill_quantity = 0;
230                                        orders_touched += 1;
231                                        span.record("filled", true);
232                                    }
233                                }else {
234                                    break;
235                                }
236                            }
237                            remove_node = price_level.total_quantity == 0;
238                        }
239                        if remove_node {
240                            orderbook.bid.price_map.pop_last();
241                            levels_consumed += 1;
242                        }
243                    }
244                    span.record("order_type", "market");
245                    span.record("is_buy_side", false);
246                    span.record("levels_consumed", levels_consumed);
247                    span.record("orders_touched", orders_touched);
248                    Ok(None)
249                }
250                OrderType::Market(market_limit) => {
251                    let mut fill_quantity = order.initial_quantity;
252                    let mut levels_consumed = 0;
253                    let mut orders_touched = 0;
254                    while fill_quantity > 0 {
255                        let remove_node: bool;
256                        {
257                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
258                                break;
259                            };
260                            if market_limit.unwrap() > *price_node.key() {
261                                break;
262                            }
263                            let price_level = price_node.get_mut();
264                            while price_level.total_quantity > 0 && fill_quantity > 0 {
265                                if let Some(head_idx) = price_level.head{
266
267                                    let first_order_node =
268                                        orderbook.bid.order_pool[head_idx].as_mut().unwrap();
269                                    if fill_quantity >= first_order_node.current_quantity {
270                                        fill_quantity -= first_order_node.current_quantity;
271                                        price_level.total_quantity -= first_order_node.current_quantity;
272                                        let next = first_order_node.next;
273                                        orderbook.bid.order_pool[head_idx] = None;
274                                        orderbook.bid.free_list.push(head_idx);
275                                        orders_touched += 1;
276                                        if let Some(next_order_idx) = next {
277                                            price_level.head = Some(next_order_idx);
278                                        } else {
279                                            span.record("reason", "exhausted");
280                                            price_level.total_quantity = 0;
281                                            break;
282                                        }
283                                    } else {
284                                        first_order_node.current_quantity -= fill_quantity;
285                                        price_level.total_quantity -= fill_quantity;
286                                        fill_quantity = 0;
287                                        orders_touched += 1;
288                                        span.record("filled", true);
289                                    }
290                                }else {
291                                    break;
292                                }
293                            }
294                            remove_node = price_level.total_quantity == 0;
295                        }
296                        if remove_node {
297                            orderbook.bid.price_map.pop_last();
298                            levels_consumed += 1;
299                        }
300                    }
301                    span.record("order_type", "market");
302                    span.record("is_buy_side", false);
303                    span.record("levels_consumed", levels_consumed);
304                    span.record("orders_touched", orders_touched);
305                    Ok(None)
306                }
307                OrderType::Limit => {
308                    let mut fill_quantity = order.initial_quantity;
309                    let mut levels_consumed = 0;
310                    let mut orders_touched = 0;
311                    while fill_quantity > 0 {
312                        let remove_node: bool;
313                        {
314                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
315                                break;
316                            };
317                            if order.price > Some(*price_node.key()) {
318                                break;
319                            }
320                            let price_level = price_node.get_mut();
321                            while price_level.total_quantity > 0 && fill_quantity > 0 {
322                                if let Some(head_idx) = price_level.head{
323                                    let first_order_node = orderbook.bid.order_pool[head_idx].as_mut().unwrap();
324                                    if fill_quantity >= first_order_node.current_quantity {
325                                        fill_quantity -= first_order_node.current_quantity;
326                                        price_level.total_quantity -= first_order_node.current_quantity;
327                                        let next = first_order_node.next;
328                                        orderbook.bid.order_pool[head_idx] = None;
329                                        orderbook.bid.free_list.push(head_idx);
330                                        orders_touched += 1;
331                                        if let Some(next_order_idx) = next {
332                                            price_level.head = Some(next_order_idx);
333                                        } else {
334                                            span.record("reason", "partially_filled");
335                                            price_level.total_quantity = 0;
336                                            break;
337                                        }
338                                    } else {
339                                        first_order_node.current_quantity -= fill_quantity;
340                                        price_level.total_quantity -= fill_quantity;
341                                        fill_quantity = 0;
342                                        orders_touched += 1;
343                                        span.record("filled", true);
344                                    }
345                                }else {
346                                    break;
347                                }
348                            }
349                            remove_node = price_level.total_quantity == 0;
350                        }
351                        if remove_node {
352                            orderbook.bid.price_map.pop_last();
353                            levels_consumed += 1;
354                        }
355                    }
356                    if fill_quantity > 0 {
357                        let alloted_index = orderbook.create_sell_order(
358                            order.engine_order_id,
359                            OrderNode {
360                                initial_quantity: order.initial_quantity,
361                                current_quantity: fill_quantity,
362                                market_limit: order.price.unwrap(),
363                                next: None,
364                                prev: None,
365                            },
366                        )?;
367                        let order_location = OrderLocation {
368                            security_id : order.security_id,
369                            is_buy_side : order.is_buy_side,
370                            order_index : alloted_index
371                        };
372                        self._global_registry.insert(order.engine_order_id, order_location);
373                        span.record("order_type", "limit");
374                        span.record("is_buy_side", false);
375                        span.record("levels_consumed", levels_consumed);
376                        span.record("orders_touched", orders_touched);
377                        return Ok(Some(alloted_index))
378                    }
379                    Ok(None)
380                }
381            }
382        } else {
383            match order.order_type {
384                OrderType::Market(None) => {
385                    // need to immediatly execute the order on the best of other half
386                    let mut fill_quantity = order.initial_quantity;
387                    let mut levels_consumed = 0;
388                    let mut orders_touched = 0;
389                    while fill_quantity > 0 {
390                        let remove_node: bool;
391                        {
392                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
393                                break;
394                            };
395                            let price_level = price_node.get_mut();
396                            while price_level.total_quantity > 0 && fill_quantity > 0 {
397                                if let Some(head_idx) = price_level.head{
398                                    let first_order_node =
399                                        orderbook.ask.order_pool[head_idx].as_mut().unwrap();
400                                    if fill_quantity >= first_order_node.current_quantity {
401                                        fill_quantity -= first_order_node.current_quantity;
402                                        price_level.total_quantity -= first_order_node.current_quantity;
403                                        let next = first_order_node.next;
404                                        orderbook.ask.order_pool[head_idx] = None;
405                                        orderbook.ask.free_list.push(head_idx);
406                                        orders_touched += 1;
407                                        if let Some(next_order_idx) = next {
408                                            price_level.head = Some(next_order_idx);
409                                        } else {
410                                            span.record("reason", "exhausted");
411                                            price_level.total_quantity = 0;
412                                            break;
413                                        }
414                                    } else {
415                                        first_order_node.current_quantity -= fill_quantity;
416                                        price_level.total_quantity -= fill_quantity;
417                                        fill_quantity = 0;
418                                        orders_touched += 1;
419                                        span.record("filled", true);
420                                    }
421                                }
422                                else {
423                                    break;
424                                }
425                            }
426                            remove_node = price_level.total_quantity == 0;
427                        }
428                        if remove_node {
429                            orderbook.bid.price_map.pop_first();
430                            levels_consumed += 1;
431                        }
432                    }
433                    span.record("order_type", "market");
434                    span.record("is_buy_side", true);
435                    span.record("levels_consumed", levels_consumed);
436                    span.record("orders_touched", orders_touched);
437                    Ok(None)
438                }
439                OrderType::Market(market_limit) => {
440                    let mut fill_quantity = order.initial_quantity;
441                    let mut levels_consumed = 0;
442                    let mut orders_touched = 0;
443                    while fill_quantity > 0 {
444                        let remove_node: bool;
445                        {
446                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
447                                break;
448                            };
449                            if market_limit.unwrap() < *price_node.key() {
450                                break;
451                            }
452                            let price_level = price_node.get_mut();
453                            while price_level.total_quantity > 0 && fill_quantity > 0 {
454                                let head_pointer = price_level.head;
455                                if let Some(head_idx) = head_pointer{
456                                    let first_order_node =
457                                        orderbook.ask.order_pool[head_idx].as_mut().unwrap();
458                                    if fill_quantity >= first_order_node.current_quantity {
459                                        fill_quantity -= first_order_node.current_quantity;
460                                        price_level.total_quantity -= first_order_node.current_quantity;
461                                        let next = first_order_node.next;
462                                        orderbook.ask.order_pool[head_idx] = None;
463                                        orderbook.ask.free_list.push(head_idx);
464                                        orders_touched += 1;
465                                        if let Some(next_order_idx) = next {
466                                            price_level.head = Some(next_order_idx);
467                                        } else {
468                                            span.record("reason", "exhausted");
469                                            price_level.head = None;
470                                            price_level.total_quantity = 0;
471                                            break;
472                                        }
473                                    } else {
474                                        first_order_node.current_quantity -= fill_quantity;
475                                        price_level.total_quantity -= fill_quantity;
476                                        fill_quantity = 0;
477                                        orders_touched += 1;
478                                        span.record("filled", true);
479                                    }
480                                }
481                                else {
482                                    break;
483                                }
484                            }
485                            remove_node = price_level.total_quantity == 0;
486                        }
487                        if remove_node {
488                            orderbook.bid.price_map.pop_first();
489                            levels_consumed += 1;
490                        }
491                    }
492                    span.record("order_type", "market");
493                    span.record("is_buy_side", true);
494                    span.record("levels_consumed", levels_consumed);
495                    span.record("orders_touched", orders_touched);
496                    Ok(None)
497                }
498                OrderType::Limit => {
499                    let mut fill_quantity = order.initial_quantity;
500                    let mut levels_consumed = 0;
501                    let mut orders_touched = 0;
502                    while fill_quantity > 0 {
503                        let remove_node: bool;
504                        {
505                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
506                                break;
507                            };
508                            if order.price < Some(*price_node.key()) {
509                                break;
510                            }
511                            let price_level = price_node.get_mut();
512                            while price_level.total_quantity > 0 && fill_quantity > 0 {
513                                if let Some(head_idx) = price_level.head{
514
515                                    let first_order_node = orderbook.ask.order_pool[head_idx].as_mut().unwrap();
516                                    if fill_quantity >= first_order_node.current_quantity {
517                                        fill_quantity -= first_order_node.current_quantity;
518                                        price_level.total_quantity -= first_order_node.current_quantity;
519                                        let next = first_order_node.next;
520                                        orderbook.ask.order_pool[head_idx] = None;
521                                        orderbook.ask.free_list.push(head_idx);
522                                        orders_touched += 1;
523                                        if let Some(next_order_idx) = next {
524                                            price_level.head = Some(next_order_idx);
525                                        } else {
526                                            span.record("reason", "partially_filled");
527                                            price_level.total_quantity = 0;
528                                            break;
529                                        }
530                                    } else {
531                                        first_order_node.current_quantity -= fill_quantity;
532                                        price_level.total_quantity -= fill_quantity;
533                                        fill_quantity = 0;
534                                        orders_touched += 1;
535                                        span.record("filled", true);
536                                    }
537                                }else {
538                                    break;
539                                }
540                            }
541                            remove_node = price_level.total_quantity == 0;
542                        }
543                        if remove_node {
544                            orderbook.bid.price_map.pop_first();
545                            levels_consumed += 1;
546                        }
547                    }
548                    if fill_quantity > 0{
549                        let alloted_index = orderbook.create_buy_order(
550                            order.engine_order_id,
551                            OrderNode {
552                                initial_quantity: order.initial_quantity,
553                                current_quantity: fill_quantity,
554                                market_limit: order.price.unwrap(),
555                                next: None,
556                                prev: None,
557                            },
558                        )?;
559                        let order_location = OrderLocation {
560                            security_id : order.security_id,
561                            is_buy_side : order.is_buy_side,
562                            order_index : alloted_index
563                        };
564                        self._global_registry.insert(order.engine_order_id, order_location);
565                        span.record("order_type", "limit");
566                        span.record("is_buy_side", true);
567                        span.record("levels_consumed", levels_consumed);
568                        span.record("orders_touched", orders_touched);
569                        return Ok(Some(alloted_index))
570                    }
571                    Ok(None)
572                }
573            }
574        }
575    }
576}
clob_engine/order_book/matching_engine.rs

clob_engine/order_book/
matching_engine.rs
