Repository navigation
Description
A getroutes call with maxparts=1 spends seconds in the askrene plugin before the route search starts. The time grows with the square of the number of channels smaller than the amount. On the test gossip snapshot the call takes 1.9 s at 100,000 sat, 13.9 s at 2,000,000 sat and 42 s at 20,000,000 sat; the search itself takes under 0.1 s, and so does the whole call without maxparts. A mainnet node on v26.06.10 shows 1.6 s at 160,000 sat and 6.2 s at 1,320,000 sat.
- For
maxparts == 1,do_getroutes()callsremove_small_channel_layer(). It builds the temporary layerauto.remove_small_channels, with a disabling update for both directions of every channel whose capacity is below the amount. add_layer()applies that layer withlayer_add_localmods(), which callsgossmap_local_updatechan()once per update.gossmap_local_updatechan()callsfind_localmod(), which scans the array of local modifications from the start. With n channels below the amount that is about n² comparisons.- This runs in the plugin's main process, before the child is forked. askrene answers no other command meanwhile. The time is outside
askrene-timeoutand outside the "get_routes completed in N ms" line. - The single-path solver then runs and returns in under 0.1 s.
Step 2 takes 82% to 96% of the call. The plugin process is CPU-bound for the whole time.
Who sends maxparts=1: xpay itself, and other plugins.
xpay sets it for a BOLT11 or BOLT12 invoice without the MPP feature, for xkeysend, and for the last allowed part of a payment with a parts limit (a destination that is not in the gossip map gets a limit of 6). CLBOSS sends its probes with maxparts=1 since v0.17.0. #9691 asks for a maxparts option in xpay.
Effect on the mainnet node: each CLBOSS probe holds askrene for 1.6 s or 6.2 s, about 9 minutes a day.
Requests sent together are answered together, after the sum of their setups: four requests at 160,000 sat took 7.5 s. A run of fourteen requests at 1,320,000 sat held askrene for 87 s. Other getroutes callers wait behind them.
Possible directions, smallest first. I have not tried any of them and have no preference; which one fits askrene's plans (#9380 also changes the layer code) is for its maintainers to say.
- Skip the layer when the single-path solver is used.
init_linear_network_single_path()already leaves out a channel when the amount is above its known upper bound, andget_capacities()rounds capacities down. The layer was written for the MCF solver (xpay: don't MPP if we're told not to #8059), before the single-path solver existed (Askrene single path solver #8299). On the snapshot, 44 calls give the same routes or the same failure code with and without the layer; the numbers are below. - Make applying a large layer linear. For example a hash lookup in
find_localmod(). This also covers any other layer with many channel updates, or with a disabled node that has many channels; they take the same path. - Mark the small channels without localmods. Each request already has its own copy of the
capacitiesarray. - Do the per-request preparation in the child. Then a slow request does not hold the others, and the deadline covers it.
Workaround: a caller that only prefers a single path can ask without maxparts and accept several parts. There is none for a non-MPP invoice or a keysend.
Related: #8059, #8299, #8448, #9110 (how this path came about), #9691.
Setup. master c0e8d89; remove_small_channel_layer() and find_localmod() are identical in v26.06.9 and v26.06.10. tests/data/gossip-store-2026-02-03.compressed in the test_real_data setup: about 50,800 channels, and the node has one 1 BTC channel into the graph. getroutes with layers auto.sourcefree and auto.localchans, maxfee_msat 1% of the amount, one call at a time. The step times come from timing lines added to do_getroutes() for this measurement. CPU is utime + stime of the cln-askrene process over the call.
| amount (sat) | channels below the amount | call with maxparts=1 |
CPU of the plugin process | build the layer | apply it (layer_add_localmods) |
rest before the fork | call without maxparts |
|---|---|---|---|---|---|---|---|
| 10,000 | 1,448 | 0.16 s | 0.12 s | 35 ms | 57 ms | 19 ms | 0.06 s |
| 100,000 | 9,135 | 1.92 s | 1.89 s | 169 ms | 1,576 ms | 110 ms | 0.07 s |
| 500,000 | 16,400 | 5.67 s | 5.65 s | 324 ms | 5,068 ms | 192 ms | 0.08 s |
| 2,000,000 | 26,717 | 13.91 s | 13.90 s | 454 ms | 13,019 ms | 326 ms | 0.08 s |
| 5,000,000 | 34,925 | 24.45 s | 24.42 s | 595 ms | 23,227 ms | 471 ms | 0.08 s |
| 20,000,000 | 46,668 | 41.90 s | 41.87 s | 800 ms | 40,268 ms | 633 ms | 0.08 s |
The time to apply the layer divided by the square of the number of channels is 1.8e-5 to 1.9e-5 ms in every row from 9,135 channels up. The calls at 5,000,000 and 20,000,000 sat end with code 205; they take the same time.
With and without the layer. Each call was made twice: with maxparts=1, and with dev_algorithm=single-path and no maxparts, which runs the same solver without the layer. 10,000 to 2,000,000 sat to ten destinations each, 5,000,000 and 20,000,000 sat to two each: 44 pairs.
- 37 pairs succeed, and the two answers are identical (routes and
probability_ppm). - 7 pairs fail with code 205 both ways. In 4 of them only the explanation differs, for example "marked disabled by layer auto.remove_small_channels" with the layer and "isn't big enough to carry ...msat" without it.
| amount (sat) | with maxparts=1 |
dev_algorithm=single-path, no maxparts |
|---|---|---|
| 10,000 | 0.16 s | 0.05 s |
| 100,000 | 1.9 s | 0.05 s |
| 500,000 | 5.5 s | 0.05 s |
| 2,000,000 | 13.9 s | 0.06 s |
| 5,000,000 | 23.7 s | 0.07 s |
| 20,000,000 | 41.6 s | 0.07 s |
Mainnet node, v26.06.10. Time from the caller's request to the answer, for a request sent alone (197 requests over about a day):
| amount (sat) | time |
|---|---|
| 19 | 0.05 s |
| 11,496 | 0.12 s |
| 57,016 | 0.62 s |
| 99,725 | 0.88 s |
| 160,000 | 1.57 s (median of 113) |
| 1,320,000 | 6.2 s (12 requests) |
For these requests askrene logs "get_routes completed in" 30 to 45 ms. When requests queue, that line can include the setup of the request behind it: one shows "completed in 1530 ms".
How this path came about.
- xpay: don't MPP if we're told not to #8059 (v25.02) added the
auto.no_mpp_supportlayer and, for it, the small-channel layer in front of the MCF solver. - Askrene single path solver #8299 (v25.09) added the single-path solver, selected by that layer or by
dev_algorithm=single-path. - Xpay limit parts #8448 (v25.09) added
maxparts. - Deprecate pay, keysend, renepay and getroute #9110 (v26.06) deprecated
auto.no_mpp_supportin favour ofmaxparts=1, which now selects both the small-channel layer and the single-path solver.
Test for the call times (run with pytest -s; about two minutes without valgrind)
from fixtures import * # noqa: F401,F403
from pyln.client import RpcError
import re
import subprocess
import tempfile
import time
def test_single_part_setup_time(node_factory, bitcoind):
"""getroutes with maxparts=1 on real gossip: time of the whole call
against the search time askrene logs for it."""
outfile = tempfile.NamedTemporaryFile(prefix='gossip-store-')
nodeids = subprocess.check_output(['devtools/gossmap-compress',
'decompress',
'--node-map=2134=033845802d25b4e074ccfd7cd8b339a41dc75bf9978a034800444b51d42b07799a',
'tests/data/gossip-store-2026-02-03.compressed',
outfile.name]).decode('utf-8').splitlines()
l1, l2 = node_factory.line_graph(2, fundamount=100000000,
opts=[{'gossip_store_file': outfile.name,
'allow_warning': True,
'dev-throttle-gossip': None,
'broken_log': '.*',
'askrene-timeout': 600},
{'allow_warning': True}])
for amount_sat in (10_000, 100_000, 500_000, 2_000_000, 5_000_000, 20_000_000):
for maxparts in (None, 1):
l1.daemon.logs_catchup()
start = len(l1.daemon.logs)
args = dict(source=l1.info['id'],
destination=nodeids[0],
amount_msat=amount_sat * 1000,
layers=['auto.sourcefree', 'auto.localchans'],
maxfee_msat=amount_sat * 10,
final_cltv=18)
if maxparts is not None:
args['maxparts'] = maxparts
t0 = time.time()
try:
l1.rpc.getroutes(**args)
result = 'ok'
except RpcError as e:
result = e.error['code']
call = time.time() - t0
l1.daemon.logs_catchup()
search = [int(m.group(1)) for line in l1.daemon.logs[start:]
for m in [re.search(r'get_routes (?:failed after|completed in) (\d+) ms', line)] if m]
print(f"{amount_sat} sat maxparts={maxparts}: call {call:.3f} s, search {search[-1]} ms, {result}")
Activity
askrene: skip redundant small-channel layer for single-path routing
askrene: skip redundant small-channel layer for single-path routing
askrene: skip redundant small-channel layer for single-path routing