X-Git-Url: http://git.bitcoin.ninja/index.cgi?a=blobdiff_plain;f=lightning%2Fsrc%2Frouting%2Fscoring.rs;h=42a565aee95b908b4a60ddf6c99b10ba98899987;hb=d8748b05c5ae3917656a5debc77e14a7767225c6;hp=0161c5549bca7a0fb7a57681e011b7f8bea99a09;hpb=331c3a55a5bb835ec15028dec6fff6fed8531633;p=rust-lightning diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 0161c554..42a565ae 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -787,8 +787,7 @@ 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, + liquidity_history: HistoricalLiquidityTracker, /// Time when the liquidity bounds were last modified as an offset since the unix epoch. last_updated: Duration, @@ -800,10 +799,10 @@ struct ChannelLiquidity { /// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and /// decayed with a given half life. -struct DirectedChannelLiquidity, BRT: Deref, T: Deref> { +struct DirectedChannelLiquidity, HT: Deref, T: Deref> { min_liquidity_offset_msat: L, max_liquidity_offset_msat: L, - liquidity_history: HistoricalMinMaxBuckets, + liquidity_history: DirectedHistoricalLiquidityTracker, capacity_msat: u64, last_updated: T, offset_history_last_updated: T, @@ -840,8 +839,8 @@ impl>, L: Deref> ProbabilisticScorer whe let amt = directed_info.effective_capacity().as_msat(); let dir_liq = liq.as_directed(source, target, amt); - let min_buckets = &dir_liq.liquidity_history.min_liquidity_offset_history.buckets; - let max_buckets = &dir_liq.liquidity_history.max_liquidity_offset_history.buckets; + let min_buckets = &dir_liq.liquidity_history.min_liquidity_offset_history_buckets(); + let max_buckets = &dir_liq.liquidity_history.max_liquidity_offset_history_buckets(); log_debug!(self.logger, core::concat!( "Liquidity from {} to {} via {} is in the range ({}, {}).\n", @@ -934,8 +933,8 @@ impl>, L: Deref> ProbabilisticScorer whe let amt = directed_info.effective_capacity().as_msat(); let dir_liq = liq.as_directed(source, target, amt); - let min_buckets = dir_liq.liquidity_history.min_liquidity_offset_history.buckets; - let mut max_buckets = dir_liq.liquidity_history.max_liquidity_offset_history.buckets; + let min_buckets = *dir_liq.liquidity_history.min_liquidity_offset_history_buckets(); + let mut max_buckets = *dir_liq.liquidity_history.max_liquidity_offset_history_buckets(); // Note that the liquidity buckets are an offset from the edge, so we inverse // the max order to get the probabilities from zero. @@ -980,8 +979,7 @@ impl ChannelLiquidity { Self { min_liquidity_offset_msat: 0, max_liquidity_offset_msat: 0, - min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), - max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + liquidity_history: HistoricalLiquidityTracker::new(), last_updated, offset_history_last_updated: last_updated, } @@ -991,23 +989,19 @@ impl ChannelLiquidity { /// `capacity_msat`. fn as_directed( &self, source: &NodeId, target: &NodeId, capacity_msat: u64, - ) -> DirectedChannelLiquidity<&u64, &HistoricalBucketRangeTracker, &Duration> { - let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) = - if source < target { - (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat, - &self.min_liquidity_offset_history, &self.max_liquidity_offset_history) + ) -> DirectedChannelLiquidity<&u64, &HistoricalLiquidityTracker, &Duration> { + let source_less_than_target = source < target; + let (min_liquidity_offset_msat, max_liquidity_offset_msat) = + if source_less_than_target { + (&self.min_liquidity_offset_msat, &self.max_liquidity_offset_msat) } else { - (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat, - &self.max_liquidity_offset_history, &self.min_liquidity_offset_history) + (&self.max_liquidity_offset_msat, &self.min_liquidity_offset_msat) }; DirectedChannelLiquidity { min_liquidity_offset_msat, max_liquidity_offset_msat, - liquidity_history: HistoricalMinMaxBuckets { - min_liquidity_offset_history, - max_liquidity_offset_history, - }, + liquidity_history: self.liquidity_history.as_directed(source_less_than_target), capacity_msat, last_updated: &self.last_updated, offset_history_last_updated: &self.offset_history_last_updated, @@ -1018,23 +1012,19 @@ impl ChannelLiquidity { /// `capacity_msat`. fn as_directed_mut( &mut self, source: &NodeId, target: &NodeId, capacity_msat: u64, - ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalBucketRangeTracker, &mut Duration> { - let (min_liquidity_offset_msat, max_liquidity_offset_msat, min_liquidity_offset_history, max_liquidity_offset_history) = - if source < target { - (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat, - &mut self.min_liquidity_offset_history, &mut self.max_liquidity_offset_history) + ) -> DirectedChannelLiquidity<&mut u64, &mut HistoricalLiquidityTracker, &mut Duration> { + let source_less_than_target = source < target; + let (min_liquidity_offset_msat, max_liquidity_offset_msat) = + if source_less_than_target { + (&mut self.min_liquidity_offset_msat, &mut self.max_liquidity_offset_msat) } else { - (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat, - &mut self.max_liquidity_offset_history, &mut self.min_liquidity_offset_history) + (&mut self.max_liquidity_offset_msat, &mut self.min_liquidity_offset_msat) }; DirectedChannelLiquidity { min_liquidity_offset_msat, max_liquidity_offset_msat, - liquidity_history: HistoricalMinMaxBuckets { - min_liquidity_offset_history, - max_liquidity_offset_history, - }, + liquidity_history: self.liquidity_history.as_directed_mut(source_less_than_target), capacity_msat, last_updated: &mut self.last_updated, offset_history_last_updated: &mut self.offset_history_last_updated, @@ -1135,8 +1125,8 @@ fn success_probability( (numerator, denominator) } -impl, BRT: Deref, T: Deref> -DirectedChannelLiquidity< L, BRT, T> { +impl, HT: Deref, T: Deref> +DirectedChannelLiquidity< L, HT, T> { /// Returns a liquidity penalty for routing the given HTLC `amount_msat` through the channel in /// this direction. fn penalty_msat(&self, amount_msat: u64, score_params: &ProbabilisticScoringFeeParameters) -> u64 { @@ -1241,8 +1231,8 @@ DirectedChannelLiquidity< L, BRT, T> { } } -impl, BRT: DerefMut, T: DerefMut> -DirectedChannelLiquidity { +impl, HT: DerefMut, T: DerefMut> +DirectedChannelLiquidity { /// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`. fn failed_at_channel( &mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log @@ -1288,11 +1278,10 @@ DirectedChannelLiquidity { /// state"), we allow the caller to set an offset applied to our liquidity bounds which /// represents the amount of the successful payment we just made. fn update_history_buckets(&mut self, bucket_offset_msat: u64, duration_since_epoch: Duration) { - self.liquidity_history.min_liquidity_offset_history.track_datapoint( - *self.min_liquidity_offset_msat + bucket_offset_msat, self.capacity_msat - ); - self.liquidity_history.max_liquidity_offset_history.track_datapoint( - self.max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), self.capacity_msat + self.liquidity_history.track_datapoint( + *self.min_liquidity_offset_msat + bucket_offset_msat, + self.max_liquidity_offset_msat.saturating_sub(bucket_offset_msat), + self.capacity_msat, ); *self.offset_history_last_updated = duration_since_epoch; } @@ -1458,19 +1447,12 @@ impl>, L: Deref> ScoreUpdate for Probabilistic if elapsed_time > decay_params.historical_no_updates_half_life { let half_life = decay_params.historical_no_updates_half_life.as_secs_f64(); if half_life != 0.0 { - let divisor = powf64(2048.0, elapsed_time.as_secs_f64() / half_life) as u64; - for bucket in liquidity.min_liquidity_offset_history.buckets.iter_mut() { - *bucket = ((*bucket as u64) * 1024 / divisor) as u16; - } - for bucket in liquidity.max_liquidity_offset_history.buckets.iter_mut() { - *bucket = ((*bucket as u64) * 1024 / divisor) as u16; - } + liquidity.liquidity_history.decay_buckets(elapsed_time.as_secs_f64() / half_life); liquidity.offset_history_last_updated = duration_since_epoch; } } liquidity.min_liquidity_offset_msat != 0 || liquidity.max_liquidity_offset_msat != 0 || - liquidity.min_liquidity_offset_history.buckets != [0; 32] || - liquidity.max_liquidity_offset_history.buckets != [0; 32] + liquidity.liquidity_history.has_datapoints() }); } } @@ -1600,7 +1582,7 @@ mod bucketed_history { /// in each of 32 buckets. #[derive(Clone, Copy)] pub(super) struct HistoricalBucketRangeTracker { - pub(super) buckets: [u16; 32], + buckets: [u16; 32], } /// Buckets are stored in fixed point numbers with a 5 bit fractional part. Thus, the value @@ -1609,7 +1591,7 @@ mod bucketed_history { impl HistoricalBucketRangeTracker { pub(super) fn new() -> Self { Self { buckets: [0; 32] } } - pub(super) fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) { + fn track_datapoint(&mut self, liquidity_offset_msat: u64, capacity_msat: u64) { // We have 32 leaky buckets for min and max liquidity. Each bucket tracks the amount of time // we spend in each bucket as a 16-bit fixed-point number with a 5 bit fractional part. // @@ -1645,18 +1627,118 @@ mod bucketed_history { impl_writeable_tlv_based!(HistoricalBucketRangeTracker, { (0, buckets, required) }); impl_writeable_tlv_based!(LegacyHistoricalBucketRangeTracker, { (0, buckets, required) }); + #[derive(Clone, Copy)] + pub(super) struct HistoricalLiquidityTracker { + min_liquidity_offset_history: HistoricalBucketRangeTracker, + max_liquidity_offset_history: HistoricalBucketRangeTracker, + total_valid_points_tracked: u64, + } + + impl HistoricalLiquidityTracker { + pub(super) fn new() -> HistoricalLiquidityTracker { + HistoricalLiquidityTracker { + min_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + max_liquidity_offset_history: HistoricalBucketRangeTracker::new(), + total_valid_points_tracked: 0, + } + } + + pub(super) fn from_min_max( + min_liquidity_offset_history: HistoricalBucketRangeTracker, + max_liquidity_offset_history: HistoricalBucketRangeTracker, + ) -> HistoricalLiquidityTracker { + let mut res = HistoricalLiquidityTracker { + min_liquidity_offset_history, + max_liquidity_offset_history, + total_valid_points_tracked: 0, + }; + res.recalculate_valid_points(); + res + } + + pub(super) fn has_datapoints(&self) -> bool { + self.min_liquidity_offset_history.buckets != [0; 32] || + self.max_liquidity_offset_history.buckets != [0; 32] + } + + pub(super) fn decay_buckets(&mut self, half_lives: f64) { + let divisor = powf64(2048.0, half_lives) as u64; + for bucket in self.min_liquidity_offset_history.buckets.iter_mut() { + *bucket = ((*bucket as u64) * 1024 / divisor) as u16; + } + for bucket in self.max_liquidity_offset_history.buckets.iter_mut() { + *bucket = ((*bucket as u64) * 1024 / divisor) as u16; + } + self.recalculate_valid_points(); + } + + fn recalculate_valid_points(&mut self) { + self.total_valid_points_tracked = 0; + for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() { + for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(32 - min_idx) { + self.total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); + } + } + } + + pub(super) fn writeable_min_offset_history(&self) -> &HistoricalBucketRangeTracker { + &self.min_liquidity_offset_history + } + + pub(super) fn writeable_max_offset_history(&self) -> &HistoricalBucketRangeTracker { + &self.max_liquidity_offset_history + } + + pub(super) fn as_directed<'a>(&'a self, source_less_than_target: bool) + -> DirectedHistoricalLiquidityTracker<&'a HistoricalLiquidityTracker> { + DirectedHistoricalLiquidityTracker { source_less_than_target, tracker: self } + } + + pub(super) fn as_directed_mut<'a>(&'a mut self, source_less_than_target: bool) + -> DirectedHistoricalLiquidityTracker<&'a mut HistoricalLiquidityTracker> { + DirectedHistoricalLiquidityTracker { source_less_than_target, tracker: self } + } + } + /// A set of buckets representing the history of where we've seen the minimum- and maximum- /// liquidity bounds for a given channel. - pub(super) struct HistoricalMinMaxBuckets> { - /// Buckets tracking where and how often we've seen the minimum liquidity bound for a - /// channel. - pub(super) min_liquidity_offset_history: D, - /// Buckets tracking where and how often we've seen the maximum liquidity bound for a - /// channel. - pub(super) max_liquidity_offset_history: D, + pub(super) struct DirectedHistoricalLiquidityTracker> { + source_less_than_target: bool, + tracker: D, + } + + impl> DirectedHistoricalLiquidityTracker { + pub(super) fn track_datapoint( + &mut self, min_offset_msat: u64, max_offset_msat: u64, capacity_msat: u64, + ) { + if self.source_less_than_target { + self.tracker.min_liquidity_offset_history.track_datapoint(min_offset_msat, capacity_msat); + self.tracker.max_liquidity_offset_history.track_datapoint(max_offset_msat, capacity_msat); + } else { + self.tracker.max_liquidity_offset_history.track_datapoint(min_offset_msat, capacity_msat); + self.tracker.min_liquidity_offset_history.track_datapoint(max_offset_msat, capacity_msat); + } + self.tracker.recalculate_valid_points(); + } } - impl> HistoricalMinMaxBuckets { + impl> DirectedHistoricalLiquidityTracker { + pub(super) fn min_liquidity_offset_history_buckets(&self) -> &[u16; 32] { + if self.source_less_than_target { + &self.tracker.min_liquidity_offset_history.buckets + } else { + &self.tracker.max_liquidity_offset_history.buckets + } + } + + pub(super) fn max_liquidity_offset_history_buckets(&self) -> &[u16; 32] { + if self.source_less_than_target { + &self.tracker.max_liquidity_offset_history.buckets + } else { + &self.tracker.min_liquidity_offset_history.buckets + } + } + #[inline] pub(super) fn calculate_success_probability_times_billion( &self, params: &ProbabilisticScoringFeeParameters, amount_msat: u64, @@ -1672,11 +1754,20 @@ mod bucketed_history { let payment_pos = amount_to_pos(amount_msat, capacity_msat); if payment_pos >= POSITION_TICKS { return None; } - let mut total_valid_points_tracked = 0; - for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate() { - for max_bucket in self.max_liquidity_offset_history.buckets.iter().take(32 - min_idx) { - total_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); + let min_liquidity_offset_history_buckets = + self.min_liquidity_offset_history_buckets(); + let max_liquidity_offset_history_buckets = + self.max_liquidity_offset_history_buckets(); + + let total_valid_points_tracked = self.tracker.total_valid_points_tracked; + #[cfg(debug_assertions)] { + let mut actual_valid_points_tracked = 0; + for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate() { + for max_bucket in max_liquidity_offset_history_buckets.iter().take(32 - min_idx) { + actual_valid_points_tracked += (*min_bucket as u64) * (*max_bucket as u64); + } } + assert_eq!(total_valid_points_tracked, actual_valid_points_tracked); } // If the total valid points is smaller than 1.0 (i.e. 32 in our fixed-point scheme), @@ -1694,10 +1785,10 @@ mod bucketed_history { // datapoint, many of which may have relatively high maximum-available-liquidity // values, which will result in us thinking we have some nontrivial probability of // routing up to that amount. - if self.min_liquidity_offset_history.buckets[0] != 0 { + if min_liquidity_offset_history_buckets[0] != 0 { let mut highest_max_bucket_with_points = 0; // The highest max-bucket with any data let mut total_max_points = 0; // Total points in max-buckets to consider - for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate() { + for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate() { if *max_bucket >= BUCKET_FIXED_POINT_ONE { highest_max_bucket_with_points = cmp::max(highest_max_bucket_with_points, max_idx); } @@ -1708,16 +1799,16 @@ mod bucketed_history { let (numerator, denominator) = success_probability(payment_pos as u64, 0, max_bucket_end_pos as u64, POSITION_TICKS as u64 - 1, params, true); let bucket_prob_times_billion = - (self.min_liquidity_offset_history.buckets[0] as u64) * total_max_points + (min_liquidity_offset_history_buckets[0] as u64) * total_max_points * 1024 * 1024 * 1024 / total_valid_points_tracked; cumulative_success_prob_times_billion += bucket_prob_times_billion * numerator / denominator; } } - for (min_idx, min_bucket) in self.min_liquidity_offset_history.buckets.iter().enumerate().skip(1) { + for (min_idx, min_bucket) in min_liquidity_offset_history_buckets.iter().enumerate().skip(1) { let min_bucket_start_pos = BUCKET_START_POS[min_idx]; - for (max_idx, max_bucket) in self.max_liquidity_offset_history.buckets.iter().enumerate().take(32 - min_idx) { + for (max_idx, max_bucket) in max_liquidity_offset_history_buckets.iter().enumerate().take(32 - min_idx) { let max_bucket_end_pos = BUCKET_START_POS[32 - max_idx] - 1; // Note that this multiply can only barely not overflow - two 16 bit ints plus // 30 bits is 62 bits. @@ -1742,7 +1833,7 @@ mod bucketed_history { } } } -use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, HistoricalMinMaxBuckets}; +use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, DirectedHistoricalLiquidityTracker, HistoricalLiquidityTracker}; impl>, L: Deref> Writeable for ProbabilisticScorer where L::Target: Logger { #[inline] @@ -1783,8 +1874,8 @@ impl Writeable for ChannelLiquidity { (2, self.max_liquidity_offset_msat, required), // 3 was the max_liquidity_offset_history in octile form (4, self.last_updated, required), - (5, Some(self.min_liquidity_offset_history), option), - (7, Some(self.max_liquidity_offset_history), option), + (5, self.liquidity_history.writeable_min_offset_history(), required), + (7, self.liquidity_history.writeable_max_offset_history(), required), (9, self.offset_history_last_updated, required), }); Ok(()) @@ -1830,8 +1921,9 @@ impl Readable for ChannelLiquidity { Ok(Self { min_liquidity_offset_msat, max_liquidity_offset_msat, - min_liquidity_offset_history: min_liquidity_offset_history.unwrap(), - max_liquidity_offset_history: max_liquidity_offset_history.unwrap(), + liquidity_history: HistoricalLiquidityTracker::from_min_max( + min_liquidity_offset_history.unwrap(), max_liquidity_offset_history.unwrap() + ), last_updated, offset_history_last_updated: offset_history_last_updated.unwrap_or(last_updated), }) @@ -1840,7 +1932,7 @@ impl Readable for ChannelLiquidity { #[cfg(test)] mod tests { - use super::{ChannelLiquidity, HistoricalBucketRangeTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorer}; + use super::{ChannelLiquidity, HistoricalLiquidityTracker, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters, ProbabilisticScorer}; use crate::blinded_path::{BlindedHop, BlindedPath}; use crate::util::config::UserConfig; @@ -2012,15 +2104,13 @@ mod tests { ChannelLiquidity { 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(), + liquidity_history: HistoricalLiquidityTracker::new(), }) .with_channel(43, ChannelLiquidity { 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(), + liquidity_history: HistoricalLiquidityTracker::new(), }); let source = source_node_id(); let target = target_node_id(); @@ -2093,8 +2183,7 @@ mod tests { ChannelLiquidity { 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(), + liquidity_history: HistoricalLiquidityTracker::new(), }); let source = source_node_id(); let target = target_node_id(); @@ -2154,8 +2243,7 @@ mod tests { ChannelLiquidity { 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(), + liquidity_history: HistoricalLiquidityTracker::new(), }); let source = source_node_id(); let target = target_node_id(); @@ -2274,8 +2362,7 @@ mod tests { ChannelLiquidity { 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(), + liquidity_history: HistoricalLiquidityTracker::new(), }); let source = source_node_id();