Skip to content

askrene: getroutes with maxparts=1 spends seconds before the search starts (quadratic in the channels below the amount) #9739

Open

Description

@ksedgwic

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.

  1. For maxparts == 1, do_getroutes() calls remove_small_channel_layer(). It builds the temporary layer auto.remove_small_channels, with a disabling update for both directions of every channel whose capacity is below the amount.
  2. add_layer() applies that layer with layer_add_localmods(), which calls gossmap_local_updatechan() once per update.
  3. gossmap_local_updatechan() calls find_localmod(), which scans the array of local modifications from the start. With n channels below the amount that is about n² comparisons.
  4. This runs in the plugin's main process, before the child is forked. askrene answers no other command meanwhile. The time is outside askrene-timeout and outside the "get_routes completed in N ms" line.
  5. 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, and get_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 capacities array.
  • 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.

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

  1. added 3 commits that reference this issue on Nov 19, 2026
    99003a2
    bb5d6a5
    4edaad5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions