/// 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,
/// A snapshot of [`ChannelLiquidity`] in one direction assuming a certain channel capacity and
/// decayed with a given half life.
-struct DirectedChannelLiquidity<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Deref<Target = Duration>> {
+struct DirectedChannelLiquidity<L: Deref<Target = u64>, HT: Deref<Target = HistoricalLiquidityTracker>, T: Deref<Target = Duration>> {
min_liquidity_offset_msat: L,
max_liquidity_offset_msat: L,
- liquidity_history: HistoricalMinMaxBuckets<BRT>,
+ liquidity_history: DirectedHistoricalLiquidityTracker<HT>,
capacity_msat: u64,
last_updated: T,
offset_history_last_updated: T,
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",
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.
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,
}
/// `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,
/// `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,
(numerator, denominator)
}
-impl<L: Deref<Target = u64>, BRT: Deref<Target = HistoricalBucketRangeTracker>, T: Deref<Target = Duration>>
-DirectedChannelLiquidity< L, BRT, T> {
+impl<L: Deref<Target = u64>, HT: Deref<Target = HistoricalLiquidityTracker>, T: Deref<Target = Duration>>
+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 {
}
}
-impl<L: DerefMut<Target = u64>, BRT: DerefMut<Target = HistoricalBucketRangeTracker>, T: DerefMut<Target = Duration>>
-DirectedChannelLiquidity<L, BRT, T> {
+impl<L: DerefMut<Target = u64>, HT: DerefMut<Target = HistoricalLiquidityTracker>, T: DerefMut<Target = Duration>>
+DirectedChannelLiquidity<L, HT, T> {
/// Adjusts the channel liquidity balance bounds when failing to route `amount_msat`.
fn failed_at_channel<Log: Deref>(
&mut self, amount_msat: u64, duration_since_epoch: Duration, chan_descr: fmt::Arguments, logger: &Log
/// 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;
}
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()
});
}
}
/// 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
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.
//
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<D: Deref<Target = HistoricalBucketRangeTracker>> {
- /// 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<D: Deref<Target = HistoricalLiquidityTracker>> {
+ source_less_than_target: bool,
+ tracker: D,
+ }
+
+ impl<D: DerefMut<Target = HistoricalLiquidityTracker>> DirectedHistoricalLiquidityTracker<D> {
+ 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<D: Deref<Target = HistoricalBucketRangeTracker>> HistoricalMinMaxBuckets<D> {
+ impl<D: Deref<Target = HistoricalLiquidityTracker>> DirectedHistoricalLiquidityTracker<D> {
+ 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,
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),
// 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);
}
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.
}
}
}
-use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, HistoricalMinMaxBuckets};
+use bucketed_history::{LegacyHistoricalBucketRangeTracker, HistoricalBucketRangeTracker, DirectedHistoricalLiquidityTracker, HistoricalLiquidityTracker};
impl<G: Deref<Target = NetworkGraph<L>>, L: Deref> Writeable for ProbabilisticScorer<G, L> where L::Target: Logger {
#[inline]
(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(())
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),
})
#[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;
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();
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();
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();
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();
projects / rust-lightning / blobdiff