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(1))
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                                            break;
228                                        }
229                                    } else {
230                                        first_order_node.current_quantity -= fill_quantity;
231                                        price_level.total_quantity -= fill_quantity;
232                                        fill_quantity = 0;
233                                        orders_touched += 1;
234                                        span.record("filled", true);
235                                    }
236                                }else {
237                                    break;
238                                }
239                            }
240                            remove_node = price_level.total_quantity == 0;
241                        }
242                        if remove_node {
243                            orderbook.bid.price_map.pop_last();
244                            levels_consumed += 1;
245                        }
246                    }
247                    span.record("order_type", "market");
248                    span.record("is_buy_side", false);
249                    span.record("levels_consumed", levels_consumed);
250                    span.record("orders_touched", orders_touched);
251                    Ok(None)
252                }
253                OrderType::Market(market_limit) => {
254                    let mut fill_quantity = order.initial_quantity;
255                    let mut levels_consumed = 0;
256                    let mut orders_touched = 0;
257                    while fill_quantity > 0 {
258                        let remove_node: bool;
259                        {
260                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
261                                break;
262                            };
263                            if market_limit.unwrap() > *price_node.key() {
264                                break;
265                            }
266                            let price_level = price_node.get_mut();
267                            while price_level.total_quantity > 0 && fill_quantity > 0 {
268                                if let Some(head_idx) = price_level.head{
269
270                                    let first_order_node =
271                                        orderbook.bid.order_pool[head_idx].as_mut().unwrap();
272                                    if fill_quantity >= first_order_node.current_quantity {
273                                        fill_quantity -= first_order_node.current_quantity;
274                                        price_level.total_quantity -= first_order_node.current_quantity;
275                                        let next = first_order_node.next;
276                                        orderbook.bid.order_pool[head_idx] = None;
277                                        orderbook.bid.free_list.push(head_idx);
278                                        orders_touched += 1;
279                                        if let Some(next_order_idx) = next {
280                                            price_level.head = Some(next_order_idx);
281                                        } else {
282                                            span.record("reason", "exhausted");
283                                            price_level.total_quantity = 0;
284                                            break;
285                                        }
286                                    } else {
287                                        first_order_node.current_quantity -= fill_quantity;
288                                        price_level.total_quantity -= fill_quantity;
289                                        fill_quantity = 0;
290                                        orders_touched += 1;
291                                        span.record("filled", true);
292                                    }
293                                }else {
294                                    break;
295                                }
296                            }
297                            remove_node = price_level.total_quantity == 0;
298                        }
299                        if remove_node {
300                            orderbook.bid.price_map.pop_last();
301                            levels_consumed += 1;
302                        }
303                    }
304                    span.record("order_type", "market");
305                    span.record("is_buy_side", false);
306                    span.record("levels_consumed", levels_consumed);
307                    span.record("orders_touched", orders_touched);
308                    Ok(None)
309                }
310                OrderType::Limit => {
311                    let mut fill_quantity = order.initial_quantity;
312                    let mut levels_consumed = 0;
313                    let mut orders_touched = 0;
314                    while fill_quantity > 0 {
315                        let remove_node: bool;
316                        {
317                            let Some(mut price_node) = orderbook.bid.price_map.last_entry() else {
318                                break;
319                            };
320                            if order.price > Some(*price_node.key()) {
321                                break;
322                            }
323                            let price_level = price_node.get_mut();
324                            while price_level.total_quantity > 0 && fill_quantity > 0 {
325                                if let Some(head_idx) = price_level.head{
326                                    let first_order_node = orderbook.bid.order_pool[head_idx].as_mut().unwrap();
327                                    if fill_quantity >= first_order_node.current_quantity {
328                                        fill_quantity -= first_order_node.current_quantity;
329                                        price_level.total_quantity -= first_order_node.current_quantity;
330                                        let next = first_order_node.next;
331                                        orderbook.bid.order_pool[head_idx] = None;
332                                        orderbook.bid.free_list.push(head_idx);
333                                        orders_touched += 1;
334                                        if let Some(next_order_idx) = next {
335                                            price_level.head = Some(next_order_idx);
336                                        } else {
337                                            span.record("reason", "partially_filled");
338                                            price_level.total_quantity = 0;
339                                            break;
340                                        }
341                                    } else {
342                                        first_order_node.current_quantity -= fill_quantity;
343                                        price_level.total_quantity -= fill_quantity;
344                                        fill_quantity = 0;
345                                        orders_touched += 1;
346                                        span.record("filled", true);
347                                    }
348                                }else {
349                                    break;
350                                }
351                            }
352                            remove_node = price_level.total_quantity == 0;
353                        }
354                        if remove_node {
355                            orderbook.bid.price_map.pop_last();
356                            levels_consumed += 1;
357                        }
358                    }
359                    if fill_quantity > 0 {
360                        let alloted_index = orderbook.create_sell_order(
361                            order.engine_order_id,
362                            OrderNode {
363                                initial_quantity: order.initial_quantity,
364                                current_quantity: fill_quantity,
365                                market_limit: order.price.unwrap(),
366                                next: None,
367                                prev: None,
368                            },
369                        )?;
370                        let order_location = OrderLocation {
371                            security_id : order.security_id,
372                            is_buy_side : order.is_buy_side,
373                            order_index : alloted_index
374                        };
375                        self._global_registry.insert(order.engine_order_id, order_location);
376                        span.record("order_type", "limit");
377                        span.record("is_buy_side", false);
378                        span.record("levels_consumed", levels_consumed);
379                        span.record("orders_touched", orders_touched);
380                        return Ok(Some(alloted_index))
381                    }
382                    Ok(None)
383                }
384            }
385        } else {
386            match order.order_type {
387                OrderType::Market(None) => {
388                    // need to immediatly execute the order on the best of other half
389                    let mut fill_quantity = order.initial_quantity;
390                    let mut levels_consumed = 0;
391                    let mut orders_touched = 0;
392                    while fill_quantity > 0 {
393                        let remove_node: bool;
394                        {
395                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
396                                break;
397                            };
398                            let price_level = price_node.get_mut();
399                            while price_level.total_quantity > 0 && fill_quantity > 0 {
400                                if let Some(head_idx) = price_level.head{
401                                    let first_order_node =
402                                        orderbook.ask.order_pool[head_idx].as_mut().unwrap();
403                                    if fill_quantity >= first_order_node.current_quantity {
404                                        fill_quantity -= first_order_node.current_quantity;
405                                        price_level.total_quantity -= first_order_node.current_quantity;
406                                        let next = first_order_node.next;
407                                        orderbook.ask.order_pool[head_idx] = None;
408                                        orderbook.ask.free_list.push(head_idx);
409                                        orders_touched += 1;
410                                        if let Some(next_order_idx) = next {
411                                            price_level.head = Some(next_order_idx);
412                                        } else {
413                                            span.record("reason", "exhausted");
414                                            price_level.total_quantity = 0;
415                                            break;
416                                        }
417                                    } else {
418                                        first_order_node.current_quantity -= fill_quantity;
419                                        price_level.total_quantity -= fill_quantity;
420                                        fill_quantity = 0;
421                                        orders_touched += 1;
422                                        span.record("filled", true);
423                                    }
424                                }
425                                else {
426                                    break;
427                                }
428                            }
429                            remove_node = price_level.total_quantity == 0;
430                        }
431                        if remove_node {
432                            orderbook.bid.price_map.pop_first();
433                            levels_consumed += 1;
434                        }
435                    }
436                    span.record("order_type", "market");
437                    span.record("is_buy_side", true);
438                    span.record("levels_consumed", levels_consumed);
439                    span.record("orders_touched", orders_touched);
440                    Ok(None)
441                }
442                OrderType::Market(market_limit) => {
443                    let mut fill_quantity = order.initial_quantity;
444                    let mut levels_consumed = 0;
445                    let mut orders_touched = 0;
446                    while fill_quantity > 0 {
447                        let remove_node: bool;
448                        {
449                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
450                                break;
451                            };
452                            if market_limit.unwrap() < *price_node.key() {
453                                break;
454                            }
455                            let price_level = price_node.get_mut();
456                            while price_level.total_quantity > 0 && fill_quantity > 0 {
457                                let head_pointer = price_level.head;
458                                if let Some(head_idx) = head_pointer{
459                                    let first_order_node =
460                                        orderbook.ask.order_pool[head_idx].as_mut().unwrap();
461                                    if fill_quantity >= first_order_node.current_quantity {
462                                        fill_quantity -= first_order_node.current_quantity;
463                                        price_level.total_quantity -= first_order_node.current_quantity;
464                                        let next = first_order_node.next;
465                                        orderbook.ask.order_pool[head_idx] = None;
466                                        orderbook.ask.free_list.push(head_idx);
467                                        orders_touched += 1;
468                                        if let Some(next_order_idx) = next {
469                                            price_level.head = Some(next_order_idx);
470                                        } else {
471                                            span.record("reason", "exhausted");
472                                            price_level.head = None;
473                                            price_level.total_quantity = 0;
474                                            break;
475                                        }
476                                    } else {
477                                        first_order_node.current_quantity -= fill_quantity;
478                                        price_level.total_quantity -= fill_quantity;
479                                        fill_quantity = 0;
480                                        orders_touched += 1;
481                                        span.record("filled", true);
482                                    }
483                                }
484                                else {
485                                    break;
486                                }
487                            }
488                            remove_node = price_level.total_quantity == 0;
489                        }
490                        if remove_node {
491                            orderbook.bid.price_map.pop_first();
492                            levels_consumed += 1;
493                        }
494                    }
495                    span.record("order_type", "market");
496                    span.record("is_buy_side", true);
497                    span.record("levels_consumed", levels_consumed);
498                    span.record("orders_touched", orders_touched);
499                    Ok(None)
500                }
501                OrderType::Limit => {
502                    let mut fill_quantity = order.initial_quantity;
503                    let mut levels_consumed = 0;
504                    let mut orders_touched = 0;
505                    while fill_quantity > 0 {
506                        let remove_node: bool;
507                        {
508                            let Some(mut price_node) = orderbook.ask.price_map.first_entry() else {
509                                break;
510                            };
511                            if order.price < Some(*price_node.key()) {
512                                break;
513                            }
514                            let price_level = price_node.get_mut();
515                            while price_level.total_quantity > 0 && fill_quantity > 0 {
516                                if let Some(head_idx) = price_level.head{
517
518                                    let first_order_node = orderbook.ask.order_pool[head_idx].as_mut().unwrap();
519                                    if fill_quantity >= first_order_node.current_quantity {
520                                        fill_quantity -= first_order_node.current_quantity;
521                                        price_level.total_quantity -= first_order_node.current_quantity;
522                                        let next = first_order_node.next;
523                                        orderbook.ask.order_pool[head_idx] = None;
524                                        orderbook.ask.free_list.push(head_idx);
525                                        orders_touched += 1;
526                                        if let Some(next_order_idx) = next {
527                                            price_level.head = Some(next_order_idx);
528                                        } else {
529                                            span.record("reason", "partially_filled");
530                                            price_level.total_quantity = 0;
531                                            break;
532                                        }
533                                    } else {
534                                        first_order_node.current_quantity -= fill_quantity;
535                                        price_level.total_quantity -= fill_quantity;
536                                        fill_quantity = 0;
537                                        orders_touched += 1;
538                                        span.record("filled", true);
539                                    }
540                                }else {
541                                    break;
542                                }
543                            }
544                            remove_node = price_level.total_quantity == 0;
545                        }
546                        if remove_node {
547                            orderbook.bid.price_map.pop_first();
548                            levels_consumed += 1;
549                        }
550                    }
551                    if fill_quantity > 0{
552                        let alloted_index = orderbook.create_buy_order(
553                            order.engine_order_id,
554                            OrderNode {
555                                initial_quantity: order.initial_quantity,
556                                current_quantity: fill_quantity,
557                                market_limit: order.price.unwrap(),
558                                next: None,
559                                prev: None,
560                            },
561                        )?;
562                        let order_location = OrderLocation {
563                            security_id : order.security_id,
564                            is_buy_side : order.is_buy_side,
565                            order_index : alloted_index
566                        };
567                        self._global_registry.insert(order.engine_order_id, order_location);
568                        span.record("order_type", "limit");
569                        span.record("is_buy_side", true);
570                        span.record("levels_consumed", levels_consumed);
571                        span.record("orders_touched", orders_touched);
572                        return Ok(Some(alloted_index))
573                    }
574                    Ok(None)
575                }
576            }
577        }
578    }
579}
clob_engine/order_book/matching_engine.rs

clob_engine/order_book/
matching_engine.rs
