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< &'static str, 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("Both")
92                        }
93                        span.record("intermediate_error", "Failed to delete from global registry");
94                        return Ok("Error occured while deleting from global registry")
95                    },
96                    ModifyOutcome::Repriced { new_price, old_initial_qty, old_current_qty } => 
97                        {
98                        span.record("modify_outcome", "price");
99                        if let Some(_) = self._global_registry.delete(&global_order_id){
100                            let _ = self.match_order(
101                            NewOrder {
102                                engine_order_id: global_order_id,
103                                price: Some(new_price),
104                                initial_quantity: old_initial_qty,
105                                current_quantity : old_current_qty,
106                                is_buy_side,
107                                security_id,
108                                order_type: OrderType::Limit,
109                            },
110                            span);
111                            return Ok("Repriced")
112                        }
113                        span.record("intermediate_error", "Failed to delete from global registry");
114                        return Ok("Error occured while deleting from global registry")
115                    },
116                    ModifyOutcome::Requantized { old_price, new_initial_qty, old_current_qty } => {
117                        span.record("modify_outcome", "qty");
118                        if let Some(_) = self._global_registry.delete(&global_order_id){
119                            let _ = self.match_order(
120                            NewOrder {
121                                engine_order_id: global_order_id,
122                                price: Some(old_price),
123                                initial_quantity: new_initial_qty,
124                                current_quantity : old_current_qty,
125                                is_buy_side,
126                                security_id,
127                                order_type: OrderType::Limit,
128                            }, span);
129                            return Ok("Requantized")
130                        }
131                        span.record("intermediate_error", "Failed to delete from global registry");
132                        return Ok("Error occured while deleting from global registry")
133                    },
134                    ModifyOutcome::Inplace => {
135                        span.record("modify_outcome", "qty reduction");
136                        return Ok("Inplace")
137                    }
138                }
139            }
140            return Ok("No potential modification")
141        } else {
142            return Ok("No modification occured");
143        }
144    }
145
146    pub fn cancel(&mut self, global_order_id: Uuid, span: &Span) -> Result<CancelOutcome, anyhow::Error>{
147        let (order_index, is_buy_side,_, orderbook) = self
148            .get_orderbook(global_order_id, span)
149            .context("Could not find the orderbook")?;
150        if let Err(_) = orderbook.cancel_order(global_order_id, CancelOrder{is_buy_side, order_index}){
151            span.record("reason", "orderbook cancellation failed");
152            span.record("success_status", false);
153            return Ok(CancelOutcome::Failed);
154        }; 
155        if let Some(_) = self._global_registry.delete(&global_order_id){
156            span.record("success_status", true);
157            return Ok(CancelOutcome::Success)
158        };
159        span.record("reason", "Registry cancellation failed");
160        span.record("success_status", false);
161        Ok(CancelOutcome::Failed)
162    }
163
164    pub fn depth(&self, security_id : Uuid, levels_count :Option<u32>, span: &Span ) -> Result<BookDepth, anyhow::Error>{
165        let _gaurd = span.enter();
166        span.record("security_id", security_id.to_string());
167        let Some(order_book) = self._book.get(&security_id) else {
168            span.record("status", "failed");
169            span.record("reason", "orderbook doesn't exist");
170            return Err(anyhow!(""))
171        };
172        match order_book.depth(levels_count){
173            Ok(book_depth) => {
174                span.record("status", "success");
175                span.record("reason", "None");
176                Ok(book_depth)
177            },
178            Err(e) => Err(anyhow!("{}", e))
179        }
180    }
181
182    pub fn match_order(&mut self, order: NewOrder, span: &Span) -> Result<Option<usize>, anyhow::Error> {
183        
184        let _gaurd = span.enter();
185
186        let orderbook = match self._book.get_mut(&order.security_id){
187            Some(orderbook) => {
188                orderbook
189            }
190            None => {
191                self._book.entry(order.security_id).or_insert(OrderBook::new())
192            }
193        };
194
195        if !order.is_buy_side {
196            // for ASK order
197            match order.order_type {
198                OrderType::Market(None) => {
199                    // need to immediatly execute the order on the best of other half
200                    let mut fill_quantity = order.initial_quantity;
201                    let mut levels_consumed = 0;
202                    let mut orders_touched = 0;
203                    while fill_quantity > 0 {
204                        let remove_node: bool;
205                        {
206                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
207                                break;
208                            };
209                            let price_level = price_node.get_mut();
210                            while price_level.total_quantity > 0 && fill_quantity > 0 {
211                                if let Some(head_idx) = price_level.head{
212
213                                    let first_order_node =
214                                        orderbook.bid.order_pool[head_idx].as_mut().unwrap();
215                                    if fill_quantity >= first_order_node.current_quantity {
216                                        fill_quantity -= first_order_node.current_quantity;
217                                        price_level.total_quantity -= first_order_node.current_quantity;
218                                        let next = first_order_node.next;
219                                        orderbook.bid.order_pool[head_idx] = None;
220                                        orderbook.bid.free_list.push(head_idx);
221                                        orders_touched += 1;
222                                        if let Some(next_order_idx) = next {
223                                            price_level.head = Some(next_order_idx);
224                                        } else {
225                                            span.record("reason", "exhausted");
226                                            price_level.total_quantity = 0;
227                                            price_level.head = None;
228                                            price_level.tail = None;
229                                            price_level.order_count = 0;
230                                            break;
231                                        }
232                                    } else {
233                                        first_order_node.current_quantity -= fill_quantity;
234                                        price_level.total_quantity -= fill_quantity;
235                                        fill_quantity = 0;
236                                        orders_touched += 1;
237                                        span.record("filled", true);
238                                    }
239                                }else {
240                                    // price level has no head. i.e head = None
241                                    break;
242                                }
243                            }
244                            remove_node = price_level.total_quantity == 0;
245                        }
246                        if remove_node {
247                            match orderbook.bid.price_map.pop_last(){
248                                Some(_) => {
249                                    levels_consumed += 1;
250                                }
251                                None => {
252                                    break;
253                                }
254                            };
255                        }
256                    }
257                    span.record("order_type", "market");
258                    span.record("is_buy_side", false);
259                    span.record("levels_consumed", levels_consumed);
260                    span.record("orders_touched", orders_touched);
261                    Ok(None)
262                }
263                OrderType::Market(market_limit) => {
264                    let mut fill_quantity = order.initial_quantity;
265                    let mut levels_consumed = 0;
266                    let mut orders_touched = 0;
267                    while fill_quantity > 0 {
268                        let remove_node: bool;
269                        {
270                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
271                                break;
272                            };
273                            if market_limit.unwrap() > *price_node.key() {
274                                break;
275                            }
276                            let price_level = price_node.get_mut();
277                            while price_level.total_quantity > 0 && fill_quantity > 0 {
278                                if let Some(head_idx) = price_level.head{
279
280                                    let first_order_node =
281                                        orderbook.bid.order_pool[head_idx].as_mut().unwrap();
282                                    if fill_quantity >= first_order_node.current_quantity {
283                                        fill_quantity -= first_order_node.current_quantity;
284                                        price_level.total_quantity -= first_order_node.current_quantity;
285                                        let next = first_order_node.next;
286                                        orderbook.bid.order_pool[head_idx] = None;
287                                        orderbook.bid.free_list.push(head_idx);
288                                        orders_touched += 1;
289                                        if let Some(next_order_idx) = next {
290                                            price_level.head = Some(next_order_idx);
291                                        } else {
292                                            span.record("reason", "exhausted");
293                                            price_level.total_quantity = 0;
294                                            price_level.head = None;
295                                            price_level.tail = None;
296                                            price_level.order_count = 0;
297                                            break;
298                                        }
299                                    } else {
300                                        first_order_node.current_quantity -= fill_quantity;
301                                        price_level.total_quantity -= fill_quantity;
302                                        fill_quantity = 0;
303                                        orders_touched += 1;
304                                        span.record("filled", true);
305                                    }
306                                }else {
307                                    break;
308                                }
309                            }
310                            remove_node = price_level.total_quantity == 0;
311                        }
312                        if remove_node {
313                            match orderbook.bid.price_map.pop_last(){
314                                Some(_) => {
315                                    levels_consumed += 1;
316                                }
317                                None => {
318                                    break;
319                                }
320                            };
321                        }
322                    }
323                    span.record("order_type", "market");
324                    span.record("is_buy_side", false);
325                    span.record("levels_consumed", levels_consumed);
326                    span.record("orders_touched", orders_touched);
327                    Ok(None)
328                }
329                OrderType::Limit => {
330                    let mut fill_quantity = order.initial_quantity;
331                    let mut levels_consumed = 0;
332                    let mut orders_touched = 0;
333                    while fill_quantity > 0 {
334                        let remove_node: bool;
335                        {
336                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
337                                break;
338                            };
339                            if order.price > Some(*price_node.key()) {
340                                break;
341                            }
342                            let price_level = price_node.get_mut();
343                            while price_level.total_quantity > 0 && fill_quantity > 0 {
344                                if let Some(head_idx) = price_level.head{
345                                    let first_order_node = orderbook.bid.order_pool[head_idx].as_mut().unwrap();
346                                    if fill_quantity >= first_order_node.current_quantity {
347                                        fill_quantity -= first_order_node.current_quantity;
348                                        price_level.total_quantity -= first_order_node.current_quantity;
349                                        let next = first_order_node.next;
350                                        orderbook.bid.order_pool[head_idx] = None;
351                                        orderbook.bid.free_list.push(head_idx);
352                                        orders_touched += 1;
353                                        if let Some(next_order_idx) = next {
354                                            price_level.head = Some(next_order_idx);
355                                        } else {
356                                            span.record("reason", "partially_filled");
357                                            price_level.total_quantity = 0;
358                                            price_level.head = None;
359                                            price_level.tail = None;
360                                            price_level.order_count = 0;
361                                            break;
362                                        }
363                                    } else {
364                                        first_order_node.current_quantity -= fill_quantity;
365                                        price_level.total_quantity -= fill_quantity;
366                                        fill_quantity = 0;
367                                        orders_touched += 1;
368                                        span.record("filled", true);
369                                    }
370                                }else {
371                                    break;
372                                }
373                            }
374                            remove_node = price_level.total_quantity == 0;
375                        }
376                        if remove_node {
377                            match orderbook.bid.price_map.pop_last(){
378                                Some(_) => {
379                                    levels_consumed += 1;
380                                }
381                                None => {
382                                    break;
383                                }
384                            };
385                        }
386                    }
387                    if fill_quantity > 0 {
388                        let alloted_index = orderbook.create_sell_order(
389                            order.engine_order_id,
390                            OrderNode {
391                                initial_quantity: order.initial_quantity,
392                                current_quantity: fill_quantity,
393                                market_limit: order.price.unwrap(),
394                                next: None,
395                                prev: None,
396                            },
397                        )?;
398                        let order_location = OrderLocation {
399                            security_id : order.security_id,
400                            is_buy_side : order.is_buy_side,
401                            order_index : alloted_index
402                        };
403                        self._global_registry.insert(order.engine_order_id, order_location);
404                        span.record("order_type", "limit");
405                        span.record("is_buy_side", false);
406                        span.record("levels_consumed", levels_consumed);
407                        span.record("orders_touched", orders_touched);
408                        return Ok(Some(alloted_index))
409                    }
410                    Ok(None)
411                }
412            }
413        } else {
414            match order.order_type {
415                OrderType::Market(None) => {
416                    // need to immediatly execute the order on the best of other half
417                    let mut fill_quantity = order.initial_quantity;
418                    let mut levels_consumed = 0;
419                    let mut orders_touched = 0;
420                    while fill_quantity > 0 {
421                        let remove_node: bool;
422                        {
423                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
424                                break;
425                            };
426                            let price_level = price_node.get_mut();
427                            while price_level.total_quantity > 0 && fill_quantity > 0 {
428                                if let Some(head_idx) = price_level.head{
429                                    let first_order_node =
430                                        orderbook.ask.order_pool[head_idx].as_mut().unwrap();
431                                    if fill_quantity >= first_order_node.current_quantity {
432                                        fill_quantity -= first_order_node.current_quantity;
433                                        price_level.total_quantity -= first_order_node.current_quantity;
434                                        let next = first_order_node.next;
435                                        orderbook.ask.order_pool[head_idx] = None;
436                                        orderbook.ask.free_list.push(head_idx);
437                                        orders_touched += 1;
438                                        if let Some(next_order_idx) = next {
439                                            price_level.head = Some(next_order_idx);
440                                        } else {
441                                            span.record("reason", "exhausted");
442                                            price_level.total_quantity = 0;
443                                            price_level.head = None;
444                                            price_level.tail = None;
445                                            price_level.order_count = 0;
446                                            break;
447                                        }
448                                    } else {
449                                        first_order_node.current_quantity -= fill_quantity;
450                                        price_level.total_quantity -= fill_quantity;
451                                        fill_quantity = 0;
452                                        orders_touched += 1;
453                                        span.record("filled", true);
454                                    }
455                                }
456                                else {
457                                    break;
458                                }
459                            }
460                            remove_node = price_level.total_quantity == 0;
461                        }
462                        if remove_node {
463                            match orderbook.ask.price_map.pop_first(){
464                                Some(_) => {
465                                    levels_consumed += 1;
466                                }
467                                None => {
468                                    break;
469                                }
470                            };
471                        }
472                    }
473                    span.record("order_type", "market");
474                    span.record("is_buy_side", true);
475                    span.record("levels_consumed", levels_consumed);
476                    span.record("orders_touched", orders_touched);
477                    Ok(None)
478                }
479                OrderType::Market(market_limit) => {
480                    let mut fill_quantity = order.initial_quantity;
481                    let mut levels_consumed = 0;
482                    let mut orders_touched = 0;
483                    while fill_quantity > 0 {
484                        let remove_node: bool;
485                        {
486                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
487                                break;
488                            };
489                            if market_limit.unwrap() < *price_node.key() {
490                                break;
491                            }
492                            let price_level = price_node.get_mut();
493                            while price_level.total_quantity > 0 && fill_quantity > 0 {
494                                let head_pointer = price_level.head;
495                                if let Some(head_idx) = head_pointer{
496                                    let first_order_node =
497                                        orderbook.ask.order_pool[head_idx].as_mut().unwrap();
498                                    if fill_quantity >= first_order_node.current_quantity {
499                                        fill_quantity -= first_order_node.current_quantity;
500                                        price_level.total_quantity -= first_order_node.current_quantity;
501                                        let next = first_order_node.next;
502                                        orderbook.ask.order_pool[head_idx] = None;
503                                        orderbook.ask.free_list.push(head_idx);
504                                        orders_touched += 1;
505                                        if let Some(next_order_idx) = next {
506                                            price_level.head = Some(next_order_idx);
507                                        } else {
508                                            span.record("reason", "exhausted");
509                                            price_level.head = None;
510                                            price_level.total_quantity = 0;
511                                            price_level.head = None;
512                                            price_level.tail = None;
513                                            price_level.order_count = 0;
514                                            break;
515                                        }
516                                    } else {
517                                        first_order_node.current_quantity -= fill_quantity;
518                                        price_level.total_quantity -= fill_quantity;
519                                        fill_quantity = 0;
520                                        orders_touched += 1;
521                                        span.record("filled", true);
522                                    }
523                                }
524                                else {
525                                    break;
526                                }
527                            }
528                            remove_node = price_level.total_quantity == 0;
529                        }
530                        if remove_node {
531                            match orderbook.ask.price_map.pop_first(){
532                                Some(_) => {
533                                    levels_consumed += 1;
534                                }
535                                None => {
536                                    break;
537                                }
538                            };
539                        }
540                    }
541                    span.record("order_type", "market");
542                    span.record("is_buy_side", true);
543                    span.record("levels_consumed", levels_consumed);
544                    span.record("orders_touched", orders_touched);
545                    Ok(None)
546                }
547                OrderType::Limit => {
548                    let mut fill_quantity = order.initial_quantity;
549                    let mut levels_consumed = 0;
550                    let mut orders_touched = 0;
551                    while fill_quantity > 0 {
552                        let remove_node: bool;
553                        {
554                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
555                                break;
556                            };
557                            if order.price < Some(*price_node.key()) {
558                                break;
559                            }
560                            let price_level = price_node.get_mut();
561                            while price_level.total_quantity > 0 && fill_quantity > 0 {
562                                if let Some(head_idx) = price_level.head{
563
564                                    let first_order_node = orderbook.ask.order_pool[head_idx].as_mut().unwrap();
565                                    if fill_quantity >= first_order_node.current_quantity {
566                                        fill_quantity -= first_order_node.current_quantity;
567                                        price_level.total_quantity -= first_order_node.current_quantity;
568                                        let next = first_order_node.next;
569                                        orderbook.ask.order_pool[head_idx] = None;
570                                        orderbook.ask.free_list.push(head_idx);
571                                        orders_touched += 1;
572                                        if let Some(next_order_idx) = next {
573                                            price_level.head = Some(next_order_idx);
574                                        } else {
575                                            span.record("reason", "partially_filled");
576                                            price_level.total_quantity = 0;
577                                            price_level.head = None;
578                                            price_level.tail = None;
579                                            price_level.order_count = 0;
580                                            break;
581                                        }
582                                    } else {
583                                        first_order_node.current_quantity -= fill_quantity;
584                                        price_level.total_quantity -= fill_quantity;
585                                        fill_quantity = 0;
586                                        orders_touched += 1;
587                                        span.record("filled", true);
588                                    }
589                                }else {
590                                    break;
591                                }
592                            }
593                            remove_node = price_level.total_quantity == 0;
594                        }
595                        if remove_node {
596                            match orderbook.ask.price_map.pop_first(){
597                                Some(_) => {
598                                    levels_consumed += 1;
599                                }
600                                None => {
601                                    break;
602                                }
603                            };
604                        }
605                    }
606                    if fill_quantity > 0{
607                        let alloted_index = orderbook.create_buy_order(
608                            order.engine_order_id,
609                            OrderNode {
610                                initial_quantity: order.initial_quantity,
611                                current_quantity: fill_quantity,
612                                market_limit: order.price.unwrap(),
613                                next: None,
614                                prev: None,
615                            },
616                        )?;
617                        let order_location = OrderLocation {
618                            security_id : order.security_id,
619                            is_buy_side : order.is_buy_side,
620                            order_index : alloted_index
621                        };
622                        self._global_registry.insert(order.engine_order_id, order_location);
623                        span.record("order_type", "limit");
624                        span.record("is_buy_side", true);
625                        span.record("levels_consumed", levels_consumed);
626                        span.record("orders_touched", orders_touched);
627                        return Ok(Some(alloted_index))
628                    }
629                    Ok(None)
630                }
631            }
632        }
633    }
634}
clob_engine/order_book/matching_engine.rs

clob_engine/order_book/
matching_engine.rs
