bee_tangle/
urts.rs

1// Copyright 2020-2021 IOTA Stiftung
2// SPDX-License-Identifier: Apache-2.0
3
4use crate::{config::TangleConfig, storage::StorageBackend, tangle::Tangle};
5
6use bee_message::MessageId;
7
8use hashbrown::{hash_map::Entry, HashMap, HashSet};
9use log::debug;
10use rand::seq::IteratorRandom;
11
12use std::time::Instant;
13
14#[allow(clippy::enum_variant_names)]
15enum Score {
16    NonLazy,
17    SemiLazy,
18    Lazy,
19}
20
21// C1: the maximum allowed delta value for the YMRSI of a given message in relation to the current SMI before it
22// gets lazy.
23const YMRSI_DELTA: u32 = 8;
24// C2: the maximum allowed delta value between OMRSI of a given message in relation to the current SMI before it
25// gets semi-lazy.
26const OMRSI_DELTA: u32 = 13;
27// If the amount of non-lazy tips exceed this limit, remove the parent(s) of the inserted tip to compensate for the
28// excess. This rule helps to reduce the amount of tips in the network.
29const MAX_LIMIT_NON_LAZY: u8 = 100;
30// The maximum time a tip remains in the tip pool after having the first child.
31// This rule helps to widen the tangle.
32const MAX_AGE_SECONDS_AFTER_FIRST_CHILD: u8 = 3;
33// The maximum amount of children a tip is allowed to have before the tip is removed from the tip pool. This rule is
34// used to widen the cone of the tangle.
35const MAX_NUM_CHILDREN: u8 = 2;
36
37#[derive(Default)]
38struct TipMetadata {
39    children: HashSet<MessageId>,
40    time_first_child: Option<Instant>,
41}
42
43impl TipMetadata {
44    pub(crate) fn new() -> Self {
45        Self::default()
46    }
47}
48
49pub(crate) struct UrtsTipPool {
50    tips: HashMap<MessageId, TipMetadata>,
51    non_lazy_tips: HashSet<MessageId>,
52    below_max_depth: u32,
53}
54
55impl UrtsTipPool {
56    pub(crate) fn new(config: &TangleConfig) -> Self {
57        Self {
58            tips: HashMap::default(),
59            non_lazy_tips: HashSet::default(),
60            below_max_depth: config.below_max_depth(),
61        }
62    }
63
64    pub(crate) fn non_lazy_tips(&self) -> &HashSet<MessageId> {
65        &self.non_lazy_tips
66    }
67
68    pub(crate) async fn insert<B: StorageBackend>(
69        &mut self,
70        tangle: &Tangle<B>,
71        message_id: MessageId,
72        parents: Vec<MessageId>,
73    ) {
74        if let Score::NonLazy = self.tip_score::<B>(tangle, &message_id).await {
75            self.non_lazy_tips.insert(message_id);
76            self.tips.insert(message_id, TipMetadata::new());
77            for parent in &parents {
78                self.add_child(*parent, message_id);
79                self.check_retention_rules_for_parent(parent);
80            }
81        }
82    }
83
84    fn add_child(&mut self, parent: MessageId, child: MessageId) {
85        match self.tips.entry(parent) {
86            Entry::Occupied(mut entry) => {
87                let metadata = entry.get_mut();
88                metadata.children.insert(child);
89                if metadata.time_first_child == None {
90                    metadata.time_first_child = Some(Instant::now());
91                }
92            }
93            Entry::Vacant(entry) => {
94                let mut metadata = TipMetadata::new();
95                metadata.children.insert(child);
96                metadata.time_first_child = Some(Instant::now());
97                entry.insert(metadata);
98            }
99        }
100    }
101
102    fn check_retention_rules_for_parent(&mut self, parent: &MessageId) {
103        // For every tip we add to the pool we call `add_child()`. `add_child()` makes sure that the parents of the tip
104        // are present in the pool. Since `check_retention_rules_for_parent()` will be called after `add_child()` we
105        // can be sure that the parents do exist. Therefore, unwrapping the parents here is fine.
106        if self.non_lazy_tips.len() > MAX_LIMIT_NON_LAZY as usize
107            || self.tips.get(parent).unwrap().children.len() > MAX_NUM_CHILDREN as usize
108            || self
109                .tips
110                .get(parent)
111                .unwrap()
112                .time_first_child
113                .unwrap()
114                .elapsed()
115                .as_secs()
116                > MAX_AGE_SECONDS_AFTER_FIRST_CHILD as u64
117        {
118            self.tips.remove(parent);
119            self.non_lazy_tips.remove(parent);
120        }
121    }
122
123    pub(crate) async fn update_scores<B: StorageBackend>(&mut self, tangle: &Tangle<B>) {
124        let mut to_remove = Vec::new();
125
126        for tip in self.tips.keys() {
127            match self.tip_score::<B>(tangle, tip).await {
128                Score::SemiLazy | Score::Lazy => {
129                    to_remove.push(*tip);
130                }
131                _ => continue,
132            }
133        }
134
135        for tip in to_remove {
136            self.tips.remove(&tip);
137            self.non_lazy_tips.remove(&tip);
138        }
139
140        debug!("Non-lazy tips {}", self.non_lazy_tips.len());
141    }
142
143    async fn tip_score<B: StorageBackend>(&self, tangle: &Tangle<B>, message_id: &MessageId) -> Score {
144        // in case the tip was pruned by the node, consider tip as lazy
145        if !tangle.contains(message_id).await {
146            Score::Lazy
147        } else {
148            let smi = *tangle.get_solid_milestone_index();
149
150            // The tip pool only works with solid tips. Therefore, all tips added to the pool can be considered to
151            // solid. The solid flag will be set together with omrsi and ymrsi values. Therefore, when a
152            // message is solid, omrsi and ymrsi values are available. Therefore, unwrapping here is fine.
153            let omrsi = *tangle.omrsi(message_id).await.unwrap().index();
154            let ymrsi = *tangle.ymrsi(message_id).await.unwrap().index();
155
156            if smi > ymrsi + YMRSI_DELTA || smi > omrsi + self.below_max_depth {
157                Score::Lazy
158            } else if smi > omrsi + OMRSI_DELTA {
159                Score::SemiLazy
160            } else {
161                Score::NonLazy
162            }
163        }
164    }
165
166    pub fn choose_non_lazy_tips(&self) -> Option<Vec<MessageId>> {
167        if self.non_lazy_tips.is_empty() {
168            None
169        } else {
170            Some(if self.non_lazy_tips.len() < self.optimal_num_tips() {
171                self.non_lazy_tips.iter().copied().collect()
172            } else {
173                self.non_lazy_tips
174                    .iter()
175                    .choose_multiple(&mut rand::thread_rng(), self.optimal_num_tips())
176                    .iter()
177                    .map(|t| **t)
178                    .collect()
179            })
180        }
181    }
182
183    pub(crate) fn optimal_num_tips(&self) -> usize {
184        // TODO: hardcoded at the moment
185        4
186    }
187
188    pub(crate) fn reduce_tips(&mut self) {
189        let non_lazy_tips = &mut self.non_lazy_tips;
190        self.tips.retain(|tip, metadata| {
191            metadata
192                .time_first_child
193                .filter(|age| age.elapsed().as_secs() > MAX_AGE_SECONDS_AFTER_FIRST_CHILD as u64)
194                .map(|_| non_lazy_tips.remove(tip))
195                .is_none()
196        });
197    }
198}
bee_tangle/urts.rs

bee_tangle/
urts.rs
