penumbra_sdk_dex/component/
eviction_manager.rs

1use crate::component::StateReadExt;
2use crate::{component::position_manager::counter::PositionCounterRead, lp::position};
3use futures::{StreamExt as _, TryStreamExt};
4use std::collections::BTreeSet;
5
6use crate::state_key::eviction_queue;
7use anyhow::Result;
8use cnidarium::StateWrite;
9use tracing::instrument;
10
11use crate::{component::PositionManager, DirectedTradingPair, TradingPair};
12
13pub(crate) trait EvictionManager: StateWrite {
14    /// Evict liquidity positions that are in excess of the trading pair limit.
15    ///
16    /// # Overview
17    /// This method enforce the approximate limit on the number of
18    /// positions that can be active for a given trading pair, as defined
19    /// by [`max_positions_per_pair`](DexParameters#max_positions_per_pair).
20    ///
21    /// # Mechanism
22    ///
23    /// The eviction mechanism functions by inspecting every trading pair which
24    /// had LP opened during the block. For each of them, it computes the "excess"
25    /// amount of positions `M`, defined as follow:
26    /// `M = N - N_max` where N is the number of positions,
27    ///                   and N_max is a chain parameter.
28    ///
29    /// Since a [`TradingPair`] defines two possible directed pairs, we need
30    /// to ensure that we don't evict LPs if they provide important liquidity
31    /// to at least one direction of the pair.
32    ///
33    /// To do this effectively, we maintain a liquidity index which orders LPs
34    /// by ascending liquidity for each direction of a trading pair. This allow
35    /// us to easily fetch the worst M positions for each index, and only evict
36    /// overlapping LPs.
37    ///
38    /// This approach sidestep the problem of adjudicating which position deserve
39    /// to be preserved depending on the trading direction, and limit the number
40    /// of reads to 2*M. On the other hand, it means that the actual maximum number
41    /// of positions per pair is 2*N_max.
42    ///
43    /// ## Diagram
44    ///
45    ///                                                      Q_1: A -> B
46    ///    ╔════════════╦━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
47    ///    ║  Bottom M  ┃  M+1  │  M+2  │    . . .       │  N-1  │   N   ┃
48    ///    ╚════════════╩━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
49    ///     ▽▼▼▼▼▼▼▼▽▽▼▽
50    /// ┌─▶ find overlap
51    /// │   ▲▲▲▲△△△▲▲▲▲▲                                     Q_2: B -> A
52    /// │  ╔════════════╦━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
53    /// │  ║  Bottom M  ┃  M+1  │  M+2  │    . . .       │  N-1  │   N   ┃
54    /// │  ╚════════════╩━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
55    /// │    ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━▶
56    /// │                                                         Ordered by inventory
57    /// │
58    /// │         ▽▼▼▼▼▼▼▼▽▽▼▽
59    /// └───────▶      ∩       Across both indices, the
60    ///           ▲▲▲▲△△△▲▲▲▲▲ bottom M positions overlap
61    ///                        k times where 0 <= k <= M
62    ///                        for N < 2*N_max
63    ///
64    #[instrument(skip_all, err, level = "trace")]
65    async fn evict_positions(&mut self) -> Result<()> {
66        let hot_pairs: BTreeSet<TradingPair> = self.get_active_trading_pairs_in_block();
67        let max_positions_per_pair = self.get_dex_params().await?.max_positions_per_pair;
68
69        for pair in hot_pairs.iter() {
70            let total_positions = self.get_position_count(pair).await;
71            let overhead_size = total_positions.saturating_sub(max_positions_per_pair);
72            if overhead_size == 0 {
73                continue;
74            }
75
76            let pair_ab = DirectedTradingPair::new(pair.asset_1(), pair.asset_2());
77            let pair_ba = pair_ab.flip();
78            let key_ab = eviction_queue::inventory_index::by_trading_pair(&pair_ab);
79            let key_ba = eviction_queue::inventory_index::by_trading_pair(&pair_ba);
80
81            let stream_ab = self.nonverifiable_prefix_raw(&key_ab).boxed();
82            let stream_ba = self.nonverifiable_prefix_raw(&key_ba).boxed();
83
84            let overhead_ab = stream_ab
85                .take(overhead_size as usize)
86                .and_then(|(k, _)| async move {
87                    let raw_id = eviction_queue::inventory_index::parse_id_from_key(k)?;
88                    Ok(position::Id(raw_id))
89                })
90                .try_collect::<BTreeSet<position::Id>>()
91                .await?;
92
93            let overhead_ba = stream_ba
94                .take(overhead_size as usize)
95                .and_then(|(k, _)| async move {
96                    let raw_id = eviction_queue::inventory_index::parse_id_from_key(k)?;
97                    Ok(position::Id(raw_id))
98                })
99                .try_collect::<BTreeSet<position::Id>>()
100                .await?;
101
102            let overlap = overhead_ab.intersection(&overhead_ba);
103
104            for id in overlap {
105                self.close_position_by_id(id).await?;
106            }
107        }
108        Ok(())
109    }
110}
111
112impl<T: StateWrite + ?Sized> EvictionManager for T {}
penumbra_sdk_dex/component/eviction_manager.rs

penumbra_sdk_dex/component/
eviction_manager.rs
