From f0f8194719158759b9d745df7f136312fb09ff13 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Mon, 2 Oct 2023 19:44:36 +0000 Subject: [PATCH] Track historical liquidity update time separately from the bounds In the next commit, we'll start to use the new `ScoreUpdate::decay_liquidity_certainty` to decay our bounds in the background. This will result in the `last_updated` field getting updated regularly on decay, rather than only on update. While this isn't an issue for the regular liquidity bounds, it poses a problem for the historical liquidity buckets, which are decayed on a separate (and by default much longer) timer. If we didn't move to tracking their decays separately, we'd never let the `last_updated` field get old enough for the historical buckets to decay at all. Instead, here we introduce a new `Duration` in the `ChannelLiquidity` which tracks the last time the historical liquidity buckets were last updated. We initialize it to a copy of `last_updated` on deserialization if it is missing. --- lightning/src/routing/scoring.rs | 68 +++++++++++++++++++++++--------- 1 file changed, 50 insertions(+), 18 deletions(-) diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index ee6d515bc..9c03ff40d 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -805,11 +805,14 @@ struct ChannelLiquidity { /// Upper channel liquidity bound in terms of an offset from the effective capacity. max_liquidity_offset_msat: u64, + min_liquidity_offset_history: HistoricalBucketRangeTracker, + max_liquidity_offset_history: HistoricalBucketRangeTracker, + /// Time when the liquidity bounds were last modified. last_updated: T, - min_liquidity_offset_history: HistoricalBucketRangeTracker, - max_liquidity_offset_history: HistoricalBucketRangeTracker, + /// Time when the historical liquidity bounds were last modified. + offset_history_last_updated: T, } /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and @@ -820,6 +823,7 @@ struct DirectedChannelLiquidity, BRT: Deref, capacity_msat: u64, last_updated: U, + offset_history_last_updated: U, now: T, decay_params: ProbabilisticScoringDecayParameters, } @@ -858,7 +862,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU let dir_liq = liq.as_directed(source, target, amt, self.decay_params); let (min_buckets, max_buckets) = dir_liq.liquidity_history - .get_decayed_buckets(now, *dir_liq.last_updated, + .get_decayed_buckets(now, *dir_liq.offset_history_last_updated, self.decay_params.historical_no_updates_half_life) .unwrap_or(([0; 32], [0; 32])); @@ -955,7 +959,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU let (min_buckets, mut max_buckets) = dir_liq.liquidity_history.get_decayed_buckets( - dir_liq.now, *dir_liq.last_updated, + dir_liq.now, *dir_liq.offset_history_last_updated, self.decay_params.historical_no_updates_half_life )?; @@ -988,7 +992,7 @@ impl>, L: Deref, T: Time> ProbabilisticScorerU let dir_liq = liq.as_directed(source, target, capacity_msat, self.decay_params); return dir_liq.liquidity_history.calculate_success_probability_times_billion( - dir_liq.now, *dir_liq.last_updated, + dir_liq.now, *dir_liq.offset_history_last_updated, self.decay_params.historical_no_updates_half_life, ¶ms, amount_msat, capacity_msat ).map(|p| p as f64 / (1024 * 1024 * 1024) as f64); @@ -1008,6 +1012,7 @@ impl ChannelLiquidity { min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), last_updated: T::now(), + offset_history_last_updated: T::now(), } } @@ -1034,6 +1039,7 @@ impl ChannelLiquidity { }, capacity_msat, last_updated: &self.last_updated, + offset_history_last_updated: &self.offset_history_last_updated, now: T::now(), decay_params: decay_params, } @@ -1062,6 +1068,7 @@ impl ChannelLiquidity { }, capacity_msat, last_updated: &mut self.last_updated, + offset_history_last_updated: &mut self.offset_history_last_updated, now: T::now(), decay_params: decay_params, } @@ -1197,7 +1204,8 @@ impl, BRT: Deref, if score_params.historical_liquidity_penalty_multiplier_msat != 0 || score_params.historical_liquidity_penalty_amount_multiplier_msat != 0 { if let Some(cumulative_success_prob_times_billion) = self.liquidity_history - .calculate_success_probability_times_billion(self.now, *self.last_updated, + .calculate_success_probability_times_billion( + self.now, *self.offset_history_last_updated, self.decay_params.historical_no_updates_half_life, score_params, amount_msat, self.capacity_msat) { @@ -1316,7 +1324,7 @@ impl, BRT: DerefMut, BRT: DerefMut, BRT: DerefMut> HistoricalMinMaxBuckets { - pub(super) fn get_decayed_buckets(&self, now: T, last_updated: T, half_life: Duration) + pub(super) fn get_decayed_buckets(&self, now: T, offset_history_last_updated: T, half_life: Duration) -> Option<([u16; 32], [u16; 32])> { - let (_, required_decays) = self.get_total_valid_points(now, last_updated, half_life)?; + let (_, required_decays) = self.get_total_valid_points(now, offset_history_last_updated, half_life)?; let mut min_buckets = *self.min_liquidity_offset_history; min_buckets.time_decay_data(required_decays); @@ -1994,9 +2004,9 @@ mod bucketed_history { Some((min_buckets.buckets, max_buckets.buckets)) } #[inline] - pub(super) fn get_total_valid_points(&self, now: T, last_updated: T, half_life: Duration) + pub(super) fn get_total_valid_points(&self, now: T, offset_history_last_updated: T, half_life: Duration) -> Option<(u64, u32)> { - let required_decays = now.duration_since(last_updated).as_secs() + let required_decays = now.duration_since(offset_history_last_updated).as_secs() .checked_div(half_life.as_secs()) .map_or(u32::max_value(), |decays| cmp::min(decays, u32::max_value() as u64) as u32); @@ -2019,7 +2029,7 @@ mod bucketed_history { #[inline] pub(super) fn calculate_success_probability_times_billion( - &self, now: T, last_updated: T, half_life: Duration, + &self, now: T, offset_history_last_updated: T, half_life: Duration, params: &ProbabilisticScoringFeeParameters, amount_msat: u64, capacity_msat: u64 ) -> Option { // If historical penalties are enabled, we try to calculate a probability of success @@ -2035,7 +2045,7 @@ mod bucketed_history { // Check if all our buckets are zero, once decayed and treat it as if we had no data. We // don't actually use the decayed buckets, though, as that would lose precision. let (total_valid_points_tracked, _) - = self.get_total_valid_points(now, last_updated, half_life)?; + = self.get_total_valid_points(now, offset_history_last_updated, half_life)?; let mut cumulative_success_prob_times_billion = 0; // Special-case the 0th min bucket - it generally means we failed a payment, so only @@ -2128,6 +2138,8 @@ ReadableArgs<(ProbabilisticScoringDecayParameters, G, L)> for ProbabilisticScore impl Writeable for ChannelLiquidity { #[inline] fn write(&self, w: &mut W) -> Result<(), io::Error> { + let offset_history_duration_since_epoch = + T::duration_since_epoch() - self.offset_history_last_updated.elapsed(); let duration_since_epoch = T::duration_since_epoch() - self.last_updated.elapsed(); write_tlv_fields!(w, { (0, self.min_liquidity_offset_msat, required), @@ -2137,6 +2149,7 @@ impl Writeable for ChannelLiquidity { (4, duration_since_epoch, required), (5, Some(self.min_liquidity_offset_history), option), (7, Some(self.max_liquidity_offset_history), option), + (9, offset_history_duration_since_epoch, required), }); Ok(()) } @@ -2152,6 +2165,7 @@ impl Readable for ChannelLiquidity { let mut min_liquidity_offset_history: Option = None; let mut max_liquidity_offset_history: Option = None; let mut duration_since_epoch = Duration::from_secs(0); + let mut offset_history_duration_since_epoch = None; read_tlv_fields!(r, { (0, min_liquidity_offset_msat, required), (1, legacy_min_liq_offset_history, option), @@ -2160,6 +2174,7 @@ impl Readable for ChannelLiquidity { (4, duration_since_epoch, required), (5, min_liquidity_offset_history, option), (7, max_liquidity_offset_history, option), + (9, offset_history_duration_since_epoch, option), }); // On rust prior to 1.60 `Instant::duration_since` will panic if time goes backwards. // We write `last_updated` as wallclock time even though its ultimately an `Instant` (which @@ -2173,6 +2188,13 @@ impl Readable for ChannelLiquidity { let last_updated = if wall_clock_now > duration_since_epoch { now - (wall_clock_now - duration_since_epoch) } else { now }; + + let offset_history_duration_since_epoch = + offset_history_duration_since_epoch.unwrap_or(duration_since_epoch); + let offset_history_last_updated = if wall_clock_now > offset_history_duration_since_epoch { + now - (wall_clock_now - offset_history_duration_since_epoch) + } else { now }; + if min_liquidity_offset_history.is_none() { if let Some(legacy_buckets) = legacy_min_liq_offset_history { min_liquidity_offset_history = Some(legacy_buckets.into_current()); @@ -2193,6 +2215,7 @@ impl Readable for ChannelLiquidity { min_liquidity_offset_history: min_liquidity_offset_history.unwrap(), max_liquidity_offset_history: max_liquidity_offset_history.unwrap(), last_updated, + offset_history_last_updated, }) } } @@ -2368,18 +2391,21 @@ mod tests { fn liquidity_bounds_directed_from_lowest_node_id() { let logger = TestLogger::new(); let last_updated = SinceEpoch::now(); + let offset_history_last_updated = SinceEpoch::now(); let network_graph = network_graph(&logger); let decay_params = ProbabilisticScoringDecayParameters::default(); let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated, + min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, + last_updated, offset_history_last_updated, min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), }) .with_channel(43, ChannelLiquidity { - min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, last_updated, + min_liquidity_offset_msat: 700, max_liquidity_offset_msat: 100, + last_updated, offset_history_last_updated, min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), }); @@ -2446,12 +2472,14 @@ mod tests { fn resets_liquidity_upper_bound_when_crossed_by_lower_bound() { let logger = TestLogger::new(); let last_updated = SinceEpoch::now(); + let offset_history_last_updated = SinceEpoch::now(); let network_graph = network_graph(&logger); let decay_params = ProbabilisticScoringDecayParameters::default(); let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated, + min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, + last_updated, offset_history_last_updated, min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), }); @@ -2505,12 +2533,14 @@ mod tests { fn resets_liquidity_lower_bound_when_crossed_by_upper_bound() { let logger = TestLogger::new(); let last_updated = SinceEpoch::now(); + let offset_history_last_updated = SinceEpoch::now(); let network_graph = network_graph(&logger); let decay_params = ProbabilisticScoringDecayParameters::default(); let mut scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, last_updated, + min_liquidity_offset_msat: 200, max_liquidity_offset_msat: 400, + last_updated, offset_history_last_updated, min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), }); @@ -2616,6 +2646,7 @@ mod tests { fn constant_penalty_outside_liquidity_bounds() { let logger = TestLogger::new(); let last_updated = SinceEpoch::now(); + let offset_history_last_updated = SinceEpoch::now(); let network_graph = network_graph(&logger); let params = ProbabilisticScoringFeeParameters { liquidity_penalty_multiplier_msat: 1_000, @@ -2628,7 +2659,8 @@ mod tests { let scorer = ProbabilisticScorer::new(decay_params, &network_graph, &logger) .with_channel(42, ChannelLiquidity { - min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, last_updated, + min_liquidity_offset_msat: 40, max_liquidity_offset_msat: 40, + last_updated, offset_history_last_updated, min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), }); -- 2.39.5