From c98e3f750349ca2c8037ecfdbcb3935f94044011 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sun, 10 Dec 2023 18:23:17 +0000 Subject: [PATCH] Use a real (probing-generated) scorer in benchmarks Until now, our routing benchmarks used a synthetic scorer, generated by scoring random paths to build up some history. This is pretty far removed from real-world routing conditions, as alternative paths generally have no scoring information and even the paths we do take have only one or two past scoring results. Instead, we fetch a static serialized scorer, generated using minutely probes. This means future changes to the scorer's data may be harder to benchmark, but makes for substantially more realistic benchmarks for changes which don't impact the serialized state. --- .github/workflows/build.yml | 29 ++++-- lightning/src/routing/gossip.rs | 4 +- lightning/src/routing/router.rs | 162 +++++++++++++------------------ lightning/src/routing/scoring.rs | 39 +------- 4 files changed, 93 insertions(+), 141 deletions(-) diff --git a/.github/workflows/build.yml b/.github/workflows/build.yml index 00ef76f7..38aa319b 100644 --- a/.github/workflows/build.yml +++ b/.github/workflows/build.yml @@ -90,19 +90,36 @@ jobs: id: cache-graph uses: actions/cache@v3 with: - path: lightning/net_graph-2023-01-18.bin - key: ldk-net_graph-v0.0.113-2023-01-18.bin + path: lightning/net_graph-2023-12-10.bin + key: ldk-net_graph-v0.0.118-2023-12-10.bin - name: Fetch routing graph snapshot if: steps.cache-graph.outputs.cache-hit != 'true' run: | - curl --verbose -L -o lightning/net_graph-2023-01-18.bin https://bitcoin.ninja/ldk-net_graph-v0.0.113-2023-01-18.bin - echo "Sha sum: $(sha256sum lightning/net_graph-2023-01-18.bin | awk '{ print $1 }')" - if [ "$(sha256sum lightning/net_graph-2023-01-18.bin | awk '{ print $1 }')" != "${EXPECTED_ROUTING_GRAPH_SNAPSHOT_SHASUM}" ]; then + curl --verbose -L -o lightning/net_graph-2023-12-10.bin https://bitcoin.ninja/ldk-net_graph-v0.0.118-2023-12-10.bin + echo "Sha sum: $(sha256sum lightning/net_graph-2023-12-10.bin | awk '{ print $1 }')" + if [ "$(sha256sum lightning/net_graph-2023-12-10.bin | awk '{ print $1 }')" != "${EXPECTED_ROUTING_GRAPH_SNAPSHOT_SHASUM}" ]; then echo "Bad hash" exit 1 fi env: - EXPECTED_ROUTING_GRAPH_SNAPSHOT_SHASUM: da6066f2bddcddbe7d8a6debbd53545697137b310bbb8c4911bc8c81fc5ff48c + EXPECTED_ROUTING_GRAPH_SNAPSHOT_SHASUM: e94b38ef4b3ce683893bf6a3ee28d60cb37c73b059403ff77b7e7458157968c2 + - name: Cache scorer snapshot + id: cache-scorer + uses: actions/cache@v3 + with: + path: lightning/scorer-2023-12-10.bin + key: ldk-scorer-v0.0.118-2023-12-10.bin + - name: Fetch scorer snapshot + if: steps.cache-scorer.outputs.cache-hit != 'true' + run: | + curl --verbose -L -o lightning/scorer-2023-12-10.bin https://bitcoin.ninja/ldk-scorer-v0.0.118-2023-12-10.bin + echo "Sha sum: $(sha256sum lightning/scorer-2023-12-10.bin | awk '{ print $1 }')" + if [ "$(sha256sum lightning/scorer-2023-12-10.bin | awk '{ print $1 }')" != "${EXPECTED_SCORER_SNAPSHOT_SHASUM}" ]; then + echo "Bad hash" + exit 1 + fi + env: + EXPECTED_SCORER_SNAPSHOT_SHASUM: 570a26bb28870fe1da7e392cdec9fb794718826b04c43ca053d71a8a9bb9be69 - name: Fetch rapid graph sync reference input run: | curl --verbose -L -o lightning-rapid-gossip-sync/res/full_graph.lngossip https://bitcoin.ninja/ldk-compressed_graph-285cb27df79-2022-07-21.bin diff --git a/lightning/src/routing/gossip.rs b/lightning/src/routing/gossip.rs index 9044a275..28c0291d 100644 --- a/lightning/src/routing/gossip.rs +++ b/lightning/src/routing/gossip.rs @@ -3625,7 +3625,7 @@ pub mod benches { pub fn read_network_graph(bench: &mut Criterion) { let logger = crate::util::test_utils::TestLogger::new(); - let mut d = crate::routing::router::bench_utils::get_route_file().unwrap(); + let (mut d, _) = crate::routing::router::bench_utils::get_graph_scorer_file().unwrap(); let mut v = Vec::new(); d.read_to_end(&mut v).unwrap(); bench.bench_function("read_network_graph", |b| b.iter(|| @@ -3635,7 +3635,7 @@ pub mod benches { pub fn write_network_graph(bench: &mut Criterion) { let logger = crate::util::test_utils::TestLogger::new(); - let mut d = crate::routing::router::bench_utils::get_route_file().unwrap(); + let (mut d, _) = crate::routing::router::bench_utils::get_graph_scorer_file().unwrap(); let net_graph = NetworkGraph::read(&mut d, &logger).unwrap(); bench.bench_function("write_network_graph", |b| b.iter(|| black_box(&net_graph).encode() diff --git a/lightning/src/routing/router.rs b/lightning/src/routing/router.rs index 57efd9f7..7f11f319 100644 --- a/lightning/src/routing/router.rs +++ b/lightning/src/routing/router.rs @@ -6942,11 +6942,11 @@ mod tests { #[test] #[cfg(not(feature = "no-std"))] fn generate_routes() { - use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters}; + use crate::routing::scoring::ProbabilisticScoringFeeParameters; let logger = ln_test_utils::TestLogger::new(); - let graph = match super::bench_utils::read_network_graph(&logger) { - Ok(f) => f, + let (graph, mut scorer) = match super::bench_utils::read_graph_scorer(&logger) { + Ok(res) => res, Err(e) => { eprintln!("{}", e); return; @@ -6954,7 +6954,6 @@ mod tests { }; let params = ProbabilisticScoringFeeParameters::default(); - let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger); let features = super::Bolt11InvoiceFeatures::empty(); super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 0, 2); @@ -6963,11 +6962,11 @@ mod tests { #[test] #[cfg(not(feature = "no-std"))] fn generate_routes_mpp() { - use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters}; + use crate::routing::scoring::ProbabilisticScoringFeeParameters; let logger = ln_test_utils::TestLogger::new(); - let graph = match super::bench_utils::read_network_graph(&logger) { - Ok(f) => f, + let (graph, mut scorer) = match super::bench_utils::read_graph_scorer(&logger) { + Ok(res) => res, Err(e) => { eprintln!("{}", e); return; @@ -6975,7 +6974,6 @@ mod tests { }; let params = ProbabilisticScoringFeeParameters::default(); - let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger); let features = channelmanager::provided_bolt11_invoice_features(&UserConfig::default()); super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 0, 2); @@ -6987,8 +6985,8 @@ mod tests { use crate::routing::scoring::{ProbabilisticScorer, ProbabilisticScoringFeeParameters}; let logger = ln_test_utils::TestLogger::new(); - let graph = match super::bench_utils::read_network_graph(&logger) { - Ok(f) => f, + let (graph, mut scorer) = match super::bench_utils::read_graph_scorer(&logger) { + Ok(res) => res, Err(e) => { eprintln!("{}", e); return; @@ -6996,7 +6994,7 @@ mod tests { }; let params = ProbabilisticScoringFeeParameters::default(); - let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &graph, &logger); + let mut scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &*graph, &logger); let features = channelmanager::provided_bolt11_invoice_features(&UserConfig::default()); super::bench_utils::generate_test_routes(&graph, &mut scorer, ¶ms, features, random_init_seed(), 1_000_000, 2); @@ -8322,7 +8320,6 @@ mod tests { pub(crate) mod bench_utils { use super::*; use std::fs::File; - use std::time::Duration; use bitcoin::hashes::Hash; use bitcoin::secp256k1::{PublicKey, Secp256k1, SecretKey}; @@ -8334,46 +8331,63 @@ pub(crate) mod bench_utils { use crate::ln::channelmanager::{self, ChannelCounterparty, ChannelDetails}; use crate::ln::features::Bolt11InvoiceFeatures; use crate::routing::gossip::NetworkGraph; + use crate::routing::scoring::ProbabilisticScorer; use crate::util::config::UserConfig; use crate::util::ser::ReadableArgs; use crate::util::test_utils::TestLogger; + use crate::sync::Arc; /// Tries to open a network graph file, or panics with a URL to fetch it. - pub(crate) fn get_route_file() -> Result { - let res = File::open("net_graph-2023-01-18.bin") // By default we're run in RL/lightning - .or_else(|_| File::open("lightning/net_graph-2023-01-18.bin")) // We may be run manually in RL/ - .or_else(|_| { // Fall back to guessing based on the binary location - // path is likely something like .../rust-lightning/target/debug/deps/lightning-... - let mut path = std::env::current_exe().unwrap(); - path.pop(); // lightning-... - path.pop(); // deps - path.pop(); // debug - path.pop(); // target - path.push("lightning"); - path.push("net_graph-2023-01-18.bin"); - File::open(path) - }) - .or_else(|_| { // Fall back to guessing based on the binary location for a subcrate - // path is likely something like .../rust-lightning/bench/target/debug/deps/bench.. - let mut path = std::env::current_exe().unwrap(); - path.pop(); // bench... - path.pop(); // deps - path.pop(); // debug - path.pop(); // target - path.pop(); // bench - path.push("lightning"); - path.push("net_graph-2023-01-18.bin"); - File::open(path) - }) - .map_err(|_| "Please fetch https://bitcoin.ninja/ldk-net_graph-v0.0.113-2023-01-18.bin and place it at lightning/net_graph-2023-01-18.bin"); + pub(crate) fn get_graph_scorer_file() -> Result<(std::fs::File, std::fs::File), &'static str> { + let load_file = |fname, err_str| { + File::open(fname) // By default we're run in RL/lightning + .or_else(|_| File::open(&format!("lightning/{}", fname))) // We may be run manually in RL/ + .or_else(|_| { // Fall back to guessing based on the binary location + // path is likely something like .../rust-lightning/target/debug/deps/lightning-... + let mut path = std::env::current_exe().unwrap(); + path.pop(); // lightning-... + path.pop(); // deps + path.pop(); // debug + path.pop(); // target + path.push("lightning"); + path.push(fname); + File::open(path) + }) + .or_else(|_| { // Fall back to guessing based on the binary location for a subcrate + // path is likely something like .../rust-lightning/bench/target/debug/deps/bench.. + let mut path = std::env::current_exe().unwrap(); + path.pop(); // bench... + path.pop(); // deps + path.pop(); // debug + path.pop(); // target + path.pop(); // bench + path.push("lightning"); + path.push(fname); + File::open(path) + }) + .map_err(|_| err_str) + }; + let graph_res = load_file( + "net_graph-2023-12-10.bin", + "Please fetch https://bitcoin.ninja/ldk-net_graph-v0.0.118-2023-12-10.bin and place it at lightning/net_graph-2023-12-10.bin" + ); + let scorer_res = load_file( + "scorer-2023-12-10.bin", + "Please fetch https://bitcoin.ninja/ldk-scorer-v0.0.118-2023-12-10.bin and place it at scorer-2023-12-10.bin" + ); #[cfg(require_route_graph_test)] - return Ok(res.unwrap()); + return Ok((graph_res.unwrap(), scorer_res.unwrap())); #[cfg(not(require_route_graph_test))] - return res; + return Ok((graph_res?, scorer_res?)); } - pub(crate) fn read_network_graph(logger: &TestLogger) -> Result, &'static str> { - get_route_file().map(|mut f| NetworkGraph::read(&mut f, logger).unwrap()) + pub(crate) fn read_graph_scorer(logger: &TestLogger) + -> Result<(Arc>, ProbabilisticScorer>, &TestLogger>), &'static str> { + let (mut graph_file, mut scorer_file) = get_graph_scorer_file()?; + let graph = Arc::new(NetworkGraph::read(&mut graph_file, logger).unwrap()); + let scorer_args = (Default::default(), Arc::clone(&graph), logger); + let scorer = ProbabilisticScorer::read(&mut scorer_file, scorer_args).unwrap(); + Ok((graph, scorer)) } pub(crate) fn payer_pubkey() -> PublicKey { @@ -8433,9 +8447,7 @@ pub(crate) mod bench_utils { let nodes = graph.read_only().nodes().clone(); let mut route_endpoints = Vec::new(); - // Fetch 1.5x more routes than we need as after we do some scorer updates we may end up - // with some routes we picked being un-routable. - for _ in 0..route_count * 3 / 2 { + for _ in 0..route_count { loop { seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; let src = PublicKey::from_slice(nodes.unordered_keys() @@ -8453,37 +8465,6 @@ pub(crate) mod bench_utils { get_route(&payer, &route_params, &graph.read_only(), Some(&[&first_hop]), &TestLogger::new(), scorer, score_params, &random_seed_bytes).is_ok(); if path_exists { - // ...and seed the scorer with success and failure data... - seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; - let mut score_amt = seed % 1_000_000_000; - loop { - // Generate fail/success paths for a wider range of potential amounts with - // MPP enabled to give us a chance to apply penalties for more potential - // routes. - let mpp_features = channelmanager::provided_bolt11_invoice_features(&UserConfig::default()); - let params = PaymentParameters::from_node_id(dst, 42) - .with_bolt11_features(mpp_features).unwrap(); - let route_params = RouteParameters::from_payment_params_and_value( - params.clone(), score_amt); - let route_res = get_route(&payer, &route_params, &graph.read_only(), - Some(&[&first_hop]), &TestLogger::new(), scorer, score_params, - &random_seed_bytes); - if let Ok(route) = route_res { - for path in route.paths { - if seed & 0x80 == 0 { - scorer.payment_path_successful(&path, Duration::ZERO); - } else { - let short_channel_id = path.hops[path.hops.len() / 2].short_channel_id; - scorer.payment_path_failed(&path, short_channel_id, Duration::ZERO); - } - seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; - } - break; - } - // If we couldn't find a path with a higer amount, reduce and try again. - score_amt /= 100; - } - route_endpoints.push((first_hop, params, amt_msat)); break; } @@ -8513,7 +8494,7 @@ pub mod benches { use crate::ln::channelmanager; use crate::ln::features::Bolt11InvoiceFeatures; use crate::routing::gossip::NetworkGraph; - use crate::routing::scoring::{FixedPenaltyScorer, ProbabilisticScorer, ProbabilisticScoringFeeParameters, ProbabilisticScoringDecayParameters}; + use crate::routing::scoring::{FixedPenaltyScorer, ProbabilisticScoringFeeParameters}; use crate::util::config::UserConfig; use crate::util::logger::{Logger, Record}; use crate::util::test_utils::TestLogger; @@ -8527,7 +8508,7 @@ pub mod benches { pub fn generate_routes_with_zero_penalty_scorer(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let (network_graph, _) = bench_utils::read_graph_scorer(&logger).unwrap(); let scorer = FixedPenaltyScorer::with_penalty(0); generate_routes(bench, &network_graph, scorer, &Default::default(), Bolt11InvoiceFeatures::empty(), 0, "generate_routes_with_zero_penalty_scorer"); @@ -8535,7 +8516,7 @@ pub mod benches { pub fn generate_mpp_routes_with_zero_penalty_scorer(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let (network_graph, _) = bench_utils::read_graph_scorer(&logger).unwrap(); let scorer = FixedPenaltyScorer::with_penalty(0); generate_routes(bench, &network_graph, scorer, &Default::default(), channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 0, @@ -8544,18 +8525,16 @@ pub mod benches { pub fn generate_routes_with_probabilistic_scorer(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap(); let params = ProbabilisticScoringFeeParameters::default(); - let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); generate_routes(bench, &network_graph, scorer, ¶ms, Bolt11InvoiceFeatures::empty(), 0, "generate_routes_with_probabilistic_scorer"); } pub fn generate_mpp_routes_with_probabilistic_scorer(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap(); let params = ProbabilisticScoringFeeParameters::default(); - let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); generate_routes(bench, &network_graph, scorer, ¶ms, channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 0, "generate_mpp_routes_with_probabilistic_scorer"); @@ -8563,9 +8542,8 @@ pub mod benches { pub fn generate_large_mpp_routes_with_probabilistic_scorer(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap(); let params = ProbabilisticScoringFeeParameters::default(); - let scorer = ProbabilisticScorer::new(ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); generate_routes(bench, &network_graph, scorer, ¶ms, channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 100_000_000, "generate_large_mpp_routes_with_probabilistic_scorer"); @@ -8573,11 +8551,9 @@ pub mod benches { pub fn generate_routes_with_nonlinear_probabilistic_scorer(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap(); let mut params = ProbabilisticScoringFeeParameters::default(); params.linear_success_probability = false; - let scorer = ProbabilisticScorer::new( - ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); generate_routes(bench, &network_graph, scorer, ¶ms, channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 0, "generate_routes_with_nonlinear_probabilistic_scorer"); @@ -8585,11 +8561,9 @@ pub mod benches { pub fn generate_mpp_routes_with_nonlinear_probabilistic_scorer(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap(); let mut params = ProbabilisticScoringFeeParameters::default(); params.linear_success_probability = false; - let scorer = ProbabilisticScorer::new( - ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); generate_routes(bench, &network_graph, scorer, ¶ms, channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 0, "generate_mpp_routes_with_nonlinear_probabilistic_scorer"); @@ -8597,11 +8571,9 @@ pub mod benches { pub fn generate_large_mpp_routes_with_nonlinear_probabilistic_scorer(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); + let (network_graph, scorer) = bench_utils::read_graph_scorer(&logger).unwrap(); let mut params = ProbabilisticScoringFeeParameters::default(); params.linear_success_probability = false; - let scorer = ProbabilisticScorer::new( - ProbabilisticScoringDecayParameters::default(), &network_graph, &logger); generate_routes(bench, &network_graph, scorer, ¶ms, channelmanager::provided_bolt11_invoice_features(&UserConfig::default()), 100_000_000, "generate_large_mpp_routes_with_nonlinear_probabilistic_scorer"); diff --git a/lightning/src/routing/scoring.rs b/lightning/src/routing/scoring.rs index 1ee15651..f4d48185 100644 --- a/lightning/src/routing/scoring.rs +++ b/lightning/src/routing/scoring.rs @@ -3680,44 +3680,7 @@ pub mod benches { pub fn decay_100k_channel_bounds(bench: &mut Criterion) { let logger = TestLogger::new(); - let network_graph = bench_utils::read_network_graph(&logger).unwrap(); - let mut scorer = ProbabilisticScorer::new(Default::default(), &network_graph, &logger); - // Score a number of random channels - let mut seed: u64 = 0xdeadbeef; - for _ in 0..100_000 { - seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; - let (victim, victim_dst, amt) = { - let rong = network_graph.read_only(); - let channels = rong.channels(); - let chan = channels.unordered_iter() - .skip((seed as usize) % channels.len()) - .next().unwrap(); - seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; - let amt = seed % chan.1.capacity_sats.map(|c| c * 1000) - .or(chan.1.one_to_two.as_ref().map(|info| info.htlc_maximum_msat)) - .or(chan.1.two_to_one.as_ref().map(|info| info.htlc_maximum_msat)) - .unwrap_or(1_000_000_000).saturating_add(1); - (*chan.0, chan.1.node_two, amt) - }; - let path = Path { - hops: vec![RouteHop { - pubkey: victim_dst.as_pubkey().unwrap(), - node_features: NodeFeatures::empty(), - short_channel_id: victim, - channel_features: ChannelFeatures::empty(), - fee_msat: amt, - cltv_expiry_delta: 42, - maybe_announced_channel: true, - }], - blinded_tail: None - }; - seed = seed.overflowing_mul(6364136223846793005).0.overflowing_add(1).0; - if seed % 1 == 0 { - scorer.probe_failed(&path, victim, Duration::ZERO); - } else { - scorer.probe_successful(&path, Duration::ZERO); - } - } + let (network_graph, mut scorer) = bench_utils::read_graph_scorer(&logger).unwrap(); let mut cur_time = Duration::ZERO; cur_time += Duration::from_millis(1); scorer.decay_liquidity_certainty(cur_time); -- 2.30.2