clob_engine/order_book/
orderbook.rs

1use std::collections::{BTreeMap, HashMap, btree_map::Entry};
2use anyhow::anyhow;
3use tracing::instrument;
4use crate::order_book::types::{BookDepth, EngineCancelOrder, EngineModifyOrder, ModifyOutcome, OrderNode, PriceLevel, PriceLevelDepth};
5
6#[derive(Debug)]
7pub struct OrderBook{
8    pub ask : HalfBook,
9    pub bid : HalfBook
10}
11impl OrderBook {
12    pub fn new () -> Self{
13        Self { ask : HalfBook::new(), bid : HalfBook::new() }
14    }
15
16    #[instrument( // used for auto span creation & drop.
17        name = "create_buy_order",
18        skip(self),
19        fields(
20            order_id = %order_id,
21            price = resting_order.market_limit
22        ),
23        err
24    )]
25    pub fn create_buy_order(&mut self, order_id : u64, resting_order : OrderNode) -> Result<usize, anyhow::Error>{
26        
27        let mut order = resting_order;
28        let order_quantity = order.current_quantity;
29        let price = order.market_limit;
30        let order_id = resting_order.order_id;
31
32        match self.bid.price_map.entry(price){ // here price is not moved, bcoz u32 implements Copy
33            Entry::Occupied(mut entry) => {
34                let price_level = entry.get_mut();
35                if price_level.total_quantity == 0 || price_level.head == None || price_level.tail == None{
36                    entry.remove();
37                } else {
38                     order.prev = price_level.tail;
39                if let Some(free_index) = self.bid.free_list.pop(){
40                    self.bid.order_registry.insert(order_id, free_index);
41                    self.bid.order_pool[free_index] = Some(order);
42                    let prev_tail_idx = price_level.tail.unwrap();
43                    price_level.tail = Some(free_index);
44                    price_level.total_quantity += order_quantity;
45                    price_level.order_count += 1;
46                        if let Some(prev_order) = self.bid.order_pool.get_mut(prev_tail_idx).unwrap(){
47                            prev_order.next = Some(free_index);
48                        };
49                    return Ok(free_index);
50                }
51                else {
52                self.bid.order_pool.push(Some(order));
53                let new_tail = self.bid.order_pool.len() - 1;
54                self.bid.order_registry.insert(order_id, new_tail);
55                let pre_tail_idx = price_level.tail.unwrap();
56                price_level.tail = Some(new_tail);
57                price_level.total_quantity += order_quantity;
58                price_level.order_count += 1;
59                if let Some(prev_order) = self.bid.order_pool.get_mut(pre_tail_idx).unwrap(){
60                    prev_order.next = Some(new_tail);
61                };
62                return Ok(new_tail);
63                }
64                }
65            }
66            Entry::Vacant(_) => {
67                // it means price_level doesn't exist. we create below
68            }
69        }
70
71        let mut new_price_level = PriceLevel{
72            head : None,
73            tail : None,
74            order_count : 0,
75            total_quantity : 0
76        };
77        if let Some(free_index) = self.bid.free_list.pop(){
78            self.bid.order_registry.insert(order_id, free_index);
79            self.bid.order_pool[free_index] = Some(order);
80            new_price_level.head = Some(free_index);
81            new_price_level.tail = Some(free_index);
82            new_price_level.order_count += 1;
83            new_price_level.total_quantity += order_quantity;
84            self.bid.price_map.entry(price).or_insert(new_price_level);
85            return Ok(free_index)
86        }
87        self.bid.order_pool.push(Some(order));
88        let new_index = self.bid.order_pool.len()-1;
89        self.bid.order_registry.insert(order_id, new_index);
90        new_price_level.head = Some(new_index);
91        new_price_level.tail = Some(new_index);
92        new_price_level.order_count += 1;
93        new_price_level.total_quantity += order_quantity;
94        self.bid.price_map.entry(price).or_insert(new_price_level);
95        
96        Ok(new_index)
97    }
98
99    #[instrument( 
100        name = "create_sell_order",
101        skip(self),
102        fields(
103            order_id = %order_id,
104            price = resting_order.market_limit 
105        ),
106        err
107    )]
108    pub fn create_sell_order(&mut self, order_id : u64, resting_order : OrderNode) -> Result<usize, anyhow::Error>{
109        let mut order = resting_order;
110        let order_quantity = order.current_quantity;
111        let price = order.market_limit;
112        let order_id = resting_order.order_id;
113
114        match self.ask.price_map.entry(price){
115            Entry::Occupied(mut entry) => {
116                let price_level = entry.get_mut();
117                if price_level.total_quantity == 0 || price_level.head == None || price_level.tail == None{
118                    entry.remove();
119                }else {
120                    order.prev = price_level.tail;
121                if let Some(free_index) = self.ask.free_list.pop(){
122                    self.ask.order_registry.insert(order_id, free_index);
123                    self.ask.order_pool[free_index] = Some(order);
124                    let prev_tail_idx = price_level.tail.unwrap();
125                    price_level.tail = Some(free_index);
126                    price_level.total_quantity += order_quantity;
127                    price_level.order_count += 1;
128                    if let Some(prev_order) = self.ask.order_pool.get_mut(prev_tail_idx).unwrap(){
129                        prev_order.next = Some(free_index);
130                    };
131                    return Ok(free_index);
132                }
133                else {
134                self.ask.order_pool.push(Some(order));
135                let new_tail = self.ask.order_pool.len() - 1;
136                self.ask.order_registry.insert(order_id, new_tail);
137                let prev_tail_idx = price_level.tail.unwrap();
138                price_level.tail = Some(new_tail);
139                price_level.total_quantity += order_quantity;
140                price_level.order_count += 1;
141                if let Some(prev_order) = self.ask.order_pool.get_mut(prev_tail_idx).unwrap(){
142                    prev_order.next = Some(new_tail);
143                };
144                return Ok(new_tail);
145                }
146                }
147            }
148            Entry::Vacant(_) => {
149                //do nothing
150            }
151        }
152        
153        let mut new_price_level = PriceLevel{
154            head : None,
155            tail : None,
156            order_count : 0,
157            total_quantity : 0
158        };
159        if let Some(free_index) = self.ask.free_list.pop(){
160            self.ask.order_registry.insert(order_id, free_index);
161            self.ask.order_pool[free_index] = Some(order);
162            new_price_level.head = Some(free_index);
163            new_price_level.tail = Some(free_index);
164            new_price_level.order_count += 1;
165            new_price_level.total_quantity += order_quantity;
166            self.ask.price_map.entry(price).or_insert(new_price_level);
167            return Ok(free_index)
168        }
169        self.ask.order_pool.push(Some(order));
170        let new_index = self.ask.order_pool.len()-1;
171        self.ask.order_registry.insert(order_id, new_index);
172        new_price_level.head = Some(new_index);
173        new_price_level.tail = Some(new_index);
174        new_price_level.order_count += 1;
175        new_price_level.total_quantity += order_quantity;
176        self.ask.price_map.entry(price).or_insert(new_price_level);
177        
178        Ok(new_index)
179    }
180
181    #[instrument( 
182        name = "cancel_order",
183        skip(self),
184        fields(
185            order_id = %order_id
186        ),
187        err
188    )]
189    pub fn cancel_order(&mut self, order_id : u64, order : EngineCancelOrder) -> Result<(), anyhow::Error>{
190        if order.is_buy_side {
191            let existing_index = self.bid.order_registry.get(&order_id);
192            if existing_index.is_none(){
193                return Err(anyhow!("index for the order doesn't exist in the local registry"));
194            }
195                            let (prev, next, old_price, old_quantity) = {
196                                match self.bid.order_pool[*existing_index.unwrap()].as_ref(){
197                                    Some(node) => {
198                                        (node.prev, node.next, node.market_limit, node.current_quantity)
199                                    }
200                                    None => { 
201                                        return Err(anyhow!("order node doesn't exist at index for cancellation"));
202                                    }
203                                }
204                            };
205                    if let Some(price_level) = self.bid.price_map.get_mut(&old_price){
206
207                        if price_level.head.is_some() && price_level.tail.is_some(){
208                            if *existing_index.unwrap() == price_level.head.unwrap() && *existing_index.unwrap() == price_level.tail.unwrap(){
209                                self.bid.order_pool[*existing_index.unwrap()] = None;
210                                price_level.head = None;
211                                price_level.tail = None;
212                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
213                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
214                                self.bid.free_list.push(*existing_index.unwrap());
215                                return Ok(());
216                            }
217                            else if *existing_index.unwrap() == price_level.tail.unwrap() {
218                               if let Some(prev_index) = prev{
219                                    if let Some(possible_prev_node) = self.bid.order_pool.get_mut(prev_index){
220                                        if let Some(prev_node) = possible_prev_node{
221                                            prev_node.next = None;
222                                            price_level.tail = Some(prev_index);
223                                        }           
224                                    }
225                                self.bid.order_pool[*existing_index.unwrap()] = None;
226                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
227                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
228                                self.bid.free_list.push(*existing_index.unwrap());
229                                return Ok(()); 
230                                } else {
231                                    return Err(anyhow!("no prev node found for deletion of tail node"));
232                                }
233                            }
234                            else if *existing_index.unwrap() == price_level.head.unwrap() {
235                                if let Some(next_index) = next{
236                                    if let Some(possible_next_node) = self.bid.order_pool.get_mut(next_index){
237                                        if let Some(next_node) = possible_next_node{
238                                            next_node.prev = None;
239                                            price_level.head = Some(next_index);
240                                        }
241                                    }
242                                    self.bid.order_pool[*existing_index.unwrap()] = None;
243                                    price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
244                                    price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
245                                    self.bid.free_list.push(*existing_index.unwrap());
246                                    return Ok(());
247                                } else {
248                                    return Err(anyhow!("no next node found for deletion of head node"));
249                                }                    
250                            }
251                            else {
252                                if let Some(prev_index) = prev{
253                                    if let Some(possible_prev_node) = self.bid.order_pool.get_mut(prev_index){
254                                        if let Some(prev_node) = possible_prev_node{
255                                            prev_node.next = next
256                                        }
257                                    }
258                                }
259                                else {
260                                    return Err(anyhow!("no prev node found for deletion of middle node"));
261                                }
262                                if let Some(next_index) = next{
263                                    if let Some(possible_next_node) = self.bid.order_pool.get_mut(next_index){
264                                        if let Some(next_node) = possible_next_node{
265                                            next_node.prev = prev
266                                        }
267                                    }
268                                }
269                                else {
270                                    return Err(anyhow!("no next node found for deletion of middle node"));
271                                }
272                                self.bid.order_pool[*existing_index.unwrap()] = None;
273                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
274                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
275                                self.bid.free_list.push(*existing_index.unwrap());
276                                return Ok(());
277                            }
278                        } else {
279                            self.bid.price_map.remove(&old_price);
280                            return Err(anyhow::anyhow!("head and tail corrupted so deleted"));
281                        }
282                    } else {
283                        return Err(anyhow!("unable to get old price node to perform cancellation"));
284                    }
285        } else {
286            let existing_index = self.ask.order_registry.get(&order_id);
287            if existing_index.is_none(){
288                return Err(anyhow!("index for the order doesn't exist in the local registry"));
289            }
290                    let (prev, next, old_price, old_quantity) = {
291                                match self.ask.order_pool[*existing_index.unwrap()].as_ref(){
292                                    Some(node) => {
293                                        (node.prev, node.next, node.market_limit, node.current_quantity)
294                                    }
295                                    None => {
296                                        return Err(anyhow!("order node doesn't exist at index for cancellation"));
297                                    }
298                                }
299                            };
300                    if let Some(price_level) = self.ask.price_map.get_mut(&old_price){
301
302                        if price_level.head.is_some() && price_level.tail.is_some(){
303                            if *existing_index.unwrap() == price_level.head.unwrap() && *existing_index.unwrap() == price_level.tail.unwrap(){
304                                self.ask.order_pool[*existing_index.unwrap()] = None;
305                                price_level.head = None;
306                                price_level.tail = None;
307                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
308                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
309                                self.ask.free_list.push(*existing_index.unwrap());
310                                return Ok(());
311                            }
312                            else if *existing_index.unwrap() == price_level.tail.unwrap() {
313                               if let Some(prev_index) = prev{
314                                    if let Some(possible_prev_node) = self.ask.order_pool.get_mut(prev_index){
315                                        if let Some(prev_node) = possible_prev_node{
316                                            prev_node.next = None;
317                                            price_level.tail = Some(prev_index);
318                                        }           
319                                    }
320                                self.ask.order_pool[*existing_index.unwrap()] = None;
321                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
322                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
323                                self.ask.free_list.push(*existing_index.unwrap());
324                                return Ok(()); 
325                                } else {
326                                    return Err(anyhow!("no prev node found for deletion of tail node"));
327                                }
328                            }
329                            else if *existing_index.unwrap() == price_level.head.unwrap() {
330                                if let Some(next_index) = next{
331                                    if let Some(possible_next_node) = self.ask.order_pool.get_mut(next_index){
332                                        if let Some(next_node) = possible_next_node{
333                                            next_node.prev = None;
334                                            price_level.head = Some(next_index);
335                                        }
336                                    }
337                                    self.ask.order_pool[*existing_index.unwrap()] = None;
338                                    price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
339                                    price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
340                                    self.ask.free_list.push(*existing_index.unwrap());
341                                    return Ok(());
342                                } else {
343                                    return Err(anyhow!("no next node found for deletion of head node"));
344                                }                    
345                            }
346                            else {
347                                if let Some(prev_index) = prev{
348                                    if let Some(possible_prev_node) = self.ask.order_pool.get_mut(prev_index){
349                                        if let Some(prev_node) = possible_prev_node{
350                                            prev_node.next = next
351                                        }
352                                    }
353                                }
354                                else {
355                                    return Err(anyhow!("no prev node found for deletion of middle node"));
356                                }
357                                if let Some(next_index) = next{
358                                    if let Some(possible_next_node) = self.ask.order_pool.get_mut(next_index){
359                                        if let Some(next_node) = possible_next_node{
360                                            next_node.prev = prev
361                                        }
362                                    }
363                                }
364                                else {
365                                    return Err(anyhow!("no next node found for deletion of middle node"));
366                                }
367                                self.ask.order_pool[*existing_index.unwrap()] = None;
368                                price_level.total_quantity = price_level.total_quantity.checked_sub(old_quantity).ok_or(anyhow!("error in subtracting total qty in order cancellation"))?;
369                                price_level.order_count = price_level.order_count.checked_sub(1).ok_or(anyhow!("error is subtracting order qty in cancellation"))?;
370                                self.ask.free_list.push(*existing_index.unwrap());
371                                return Ok(());
372                            }
373                        } else {
374                            self.ask.price_map.remove(&old_price);
375                            return Err(anyhow::anyhow!("head and tail corrupted so deleted"));
376                        }
377                    } else {
378                        return Err(anyhow!("unable to get old price node to perform cancellation"));
379                    }
380        }
381    }
382
383    #[instrument( 
384        name = "modify_order",
385        skip(self),
386        fields(
387            order_id = %order_id,
388        ),
389        err
390    )]
391    pub fn modify_order(&mut self, order_id : u64, order : EngineModifyOrder) -> Result<Option<ModifyOutcome>, anyhow::Error>{
392        if order.is_buy_side{
393            let existing_index = self.bid.order_registry.get(&order_id);
394            if existing_index.is_none(){
395                return Err(anyhow!("index for the order doesn't exist in the local registry"));
396            }
397                let (old_initial_qty, old_current_qty, old_price) = {
398                    match self.bid.order_pool[*existing_index.unwrap()].as_ref(){
399                        Some(node) => {
400                            (node.initial_quantity, node.current_quantity, node.market_limit)
401                        }
402                        None => {
403                            return Err(anyhow!("order node not found at index for modification (buy)"));
404                        }
405                    }
406                };
407                if let Some(new_price) = order.new_price && let Some(new_qty) = order.new_quantity{
408                    if new_price != old_price{
409                        if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_id : order.order_id, security_id : order.security_id, is_buy_side: order.is_buy_side,}){
410                            return Ok(Some(ModifyOutcome::Both {new_price, new_initial_qty: new_qty, old_current_qty }));
411                            }
412                        }
413                    return Ok(None);
414                } else if let Some(new_qty) = order.new_quantity  {
415                    if new_qty > old_initial_qty{
416                        if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_id : order.order_id,security_id : order.security_id, is_buy_side: order.is_buy_side,}){
417                            return Ok(Some(ModifyOutcome::Requantized {old_price, new_initial_qty: new_qty, old_current_qty }))
418                        }
419                        return Ok(None);
420                    }
421                    else {
422                        match self.bid.order_pool[*existing_index.unwrap()].as_mut(){
423                            Some(order_node) => {
424                                order_node.initial_quantity = new_qty;
425                                return Ok(Some(ModifyOutcome::Inplace));
426                            }
427                            None => {
428                                return Err(anyhow!("couldn't find order node to modify qty in-place (buy)"));
429                            }
430                        }
431                    }
432                } else {
433                    if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_id : order.order_id,security_id : order.security_id, is_buy_side: order.is_buy_side,}){
434                        return Ok(Some(ModifyOutcome::Repriced {new_price : order.new_price.unwrap(), old_initial_qty, old_current_qty }));
435                    }
436                    return Ok(None);
437                }
438        } else {
439            let existing_index = self.ask.order_registry.get(&order_id);
440            if existing_index.is_none(){
441                return Err(anyhow!("index for the order doesn't exist in the local registry"));
442            }
443                let (old_initial_qty, old_current_qty, old_price) = {
444                    match self.ask.order_pool[*existing_index.unwrap()].as_ref(){
445                        Some(node) => {
446                            (node.initial_quantity, node.current_quantity, node.market_limit)
447                        }
448                        None => {
449                            return Err(anyhow!("order node not found at index for modification (sell)"));
450                        }
451                    }
452                };
453
454                if let Some(new_price) = order.new_price && let Some(new_qty) = order.new_quantity{
455                    if new_price != old_price{
456                        if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_id : order.order_id,security_id : order.security_id, is_buy_side: order.is_buy_side,}){
457                           return Ok(Some(ModifyOutcome::Requantized {old_price, new_initial_qty: new_qty, old_current_qty }))
458                        }
459                    }
460                    return Ok(None);
461                } else if let Some(new_qty) = order.new_quantity  {
462                    if new_qty > old_initial_qty{
463                        if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_id : order.order_id, security_id : order.security_id, is_buy_side: order.is_buy_side,}){
464                            return Ok(Some(ModifyOutcome::Requantized { old_price, new_initial_qty: new_qty, old_current_qty }))
465                        }
466                        return Ok(None);
467                    }
468                    else {
469                        match self.ask.order_pool[*existing_index.unwrap()].as_mut(){
470                            Some(order_node) => {
471                                order_node.initial_quantity = new_qty;
472                                return Ok(Some(ModifyOutcome::Inplace));
473                            }
474                            None => {
475                                return Err(anyhow!("couldn't find order node to modify qty in-place (sell)"));
476                            }
477                        }
478                    }
479                }else {
480                    if let Ok(_) = self.cancel_order(order_id ,EngineCancelOrder { order_id : order.order_id, security_id : order.security_id, is_buy_side: order.is_buy_side,}){
481                        return Ok(Some(ModifyOutcome::Repriced { new_price : order.new_price.unwrap(), old_initial_qty, old_current_qty }));
482                    }
483                    return Ok(None);
484                }
485        }
486    }
487    
488    #[instrument( 
489        name = "book_depth",
490        skip(self),
491        err
492    )]
493    pub fn depth(&self, levels_count : Option<u32>) -> Result<BookDepth, anyhow::Error>{
494
495        let ask_iter = self.ask.price_map.iter().rev();
496        let bid_iter = self.bid.price_map.iter();
497
498        let ask_depth : Vec<_> = match levels_count {
499            Some(n) => ask_iter.take(n as usize)
500            .map(|(price, price_level)| PriceLevelDepth {
501                price_level : *price,
502                quantity : price_level.total_quantity
503            })
504            .collect(),
505            None => ask_iter.map(|(price, price_level)| PriceLevelDepth {
506                price_level : *price,
507                quantity : price_level.total_quantity
508            }).collect()
509        };
510        let bid_depth = match levels_count {
511            Some(n) => bid_iter.take(n as usize)
512            .map(|(price, price_level)| PriceLevelDepth {
513                price_level : *price,
514                quantity : price_level.total_quantity
515            })
516            .collect(),
517            None => bid_iter.map(|(price, price_level)| PriceLevelDepth {
518                price_level : *price,
519                quantity : price_level.total_quantity
520            }).collect()
521        };
522        Ok(BookDepth { bid_depth, ask_depth })
523    }
524}
525
526#[derive(Debug)]
527pub struct HalfBook{
528    pub price_map : BTreeMap<u32, PriceLevel>,
529    pub order_registry : HashMap<u64, usize>,
530    pub order_pool : Vec<Option<OrderNode>>,
531    pub free_list : Vec<usize>, // we're storing the free indices from the price level to keep the cache lines hot.
532}
533
534impl HalfBook {
535    pub fn new() -> Self{
536        Self { price_map: BTreeMap::new(), order_registry : HashMap::new(), order_pool: Vec::new(), free_list: Vec::new()}
537    }
538}
clob_engine/order_book/orderbook.rs

clob_engine/order_book/
orderbook.rs
